Algorithm

• MIT 6.006 Introduction to Algorithms, Spring 2020
• 1. Algorithms and Computation
• 2. Data Structures and Dynamic Arrays
• Word RAM Model

MIT 6.006 Introduction to Algorithms, Spring 2020

1. Algorithms and Computation

문제란?

• input ,output이 있는 이진 관계

이진 관계란, 두 개의 집합 사이에서 정의되는 관계를 말함

알고리즘이란?

• 프로시져이다.

많은 양의 데이터를 비교하여 무엇인가 맞다고 증명할때 어떤 방법을 써야하나?

어떻게 설득할까? 이 알고리즘이 맞는지?

• 귀납적 가설을 사용한다
• Inductive Hypotesis: if first k students contain match alg returns a match before interviewing student k + 1
• 귀납적 가설
  • 기저 사례 base case: 명제가 가장 작은 자연수 n=0n = 0n=0 또는 n=1n = 1n=1에서 참임을 증명
  • 귀납 단계 Inductive Step:
    • 귀납적 가설: 임의의 자연수 k에대해 명제가 참이라고 가정하고, 이를 바탕으로 k+1에서도 명제가 참임을 증명

어떻게 알고리즘이 빠른지 측정할 수 있나?

• 그냥 빠른게 효율적인건 아니다
• 시간을 잰다?
  • 컴퓨터의 힘에 따라 시간이 굉장히 다를 것이다 (IBM's research computer vs my computer)
• Don't measure time, instead count ops
• Expect performance to depend on size of our input
• O(n) upper bound Ω(n) lower bound θ both

32비트 CPU라는 말은 참조할 수 있는 메모리의 주소를 32비트로만 나타낼 수 있다는 말이다. 그럼 메모리 주소는 총 2^32이 된다. 약 4GB이다. 따라서, 물리적으로 최대 램을 4GB밖에 못쓴다.

2. Data Structures and Dynamic Arrays

강의 초입 부분에 인터페이스와 자료구조의 다른점을 짚고 넘어 감.

Interface (API / ADT)

• 인터페이스(API, ADT 추상 데이터 타입)에 대한 내용
• "무엇"에 집중

Specification (어떤 명세를 가지는지)

• 인터페이스의 명세는 인터페이스가 어떤 기능을 제공하는지를 기술
• 사용자가 인터페이스를 통해 수행할 수 있는 작업들을 정의

What data can store (어떤 데이터를 저장할 수 있는지)

• 인터페이스가 다룰 수 있는 데이터의 종류를 정의
• 예를 들어, 리스트 인터페이스는 정수, 문자열 등 다양한 타입의 요소들을 저장할 수 있다는 둥.

What operations are supported (어떤 연산을 지원하는지)

• 인터페이스를 통해 수행할 수 있는 연산들을 정의합
• 예를 들어, 리스트 인터페이스는 요소 추가(add), 삭제(remove), 검색(find) 등의 연산을 지원할 수 있다는 둥.

자료 구조

• 자료 구조는 데이터를 실제로 어떻게 저장하고 관리할지를 정의
• "어떻게"에 집중

Representation (어떻게 표현할지)

• 자료 구조의 표현은 데이터를 메모리나 다른 저장 매체에 어떻게 배치할지를 정의
• 예를 들어,
  • 배열: 연속된 메모리 블록에 데이터를 저장
  • 링크드 리스트: 각 요소가 다음 요소에 대한 참조를 포함하는 방식으로 데이터를 저장

How to store data (어떻게 저장할지)

• 데이터를 실제로 저장하는 방법을 구체적으로 설명
• 예를 들어,
  • 배열: 인덱스를 통해 요소에 접근
  • 트리: 노드와 간선으로 데이터를 저장

Algorithms to support operations (어떻게 연산할지 알고리즘)

• 자료 구조가 제공하는 연산들을 어떻게 구현할지를 설명
• 예를 들어 이진 검색 트리는 삽입, 삭제, 검색 연산을 효율적으로 수행하기 위한 알고리즘을 제공

Word RAM(Random Access Machine) Model

• 우리가 더 흥미로운 데이터 구조에 도달할수록 이 모델이 정말로 필요하게 될 것이며, 점점 더 이 모델에 의존하게 될 것이다.
• 자세한 건 Word RAM Model 페이지에 정리해둠

Word RAM Model

This may seem simple, but we're really going to need this model and really rely on this model increasingly as we get to more insteresting data structures. By Erik Demaine

The Word RAM model is a computational model used to analyze the performance of algorithms and data structures. It assumes a random-access memory (RAM) where the memory is organized as an array of w-bit words.

Key Concepts

• 기억할 것

  • 단순하게 표현하기 때문에 데이터 구조를 이해하는데 직관적
  • 배열 접근 O(1) 안에 이루어지는 것을 이해. 자료 구조를 들어가면 갈수록 그 설계들은 빠른 접근을 전제로 설계됨.

• Memory:

  • The memory is an array of w-bit words.
  • An "array" refers to a consecutive chunk of memory.
  • Accessing an element in the array can be done in O(1) time.
  • array[i] = memory[address(array) + i].

w-bit Words

• Definition:

  • Each word in the memory is w bits wide.
  • "w" represents the word size, which is the number of bits in each word.

• Examples:

  • In a 32-bit system, each word is 32 bits (4 bytes).
  • In a 64-bit system, each word is 64 bits (8 bytes).

Importance

• Data Representation:

  • The size of w determines how much data can be stored in each word.

• Memory Addressing:

  • The word size affects the memory address space. For example, a 64-bit system can address more memory than a 32-bit system.

• Performance:

  • Algorithms assume O(1) time complexity for accessing memory locations. This is crucial for the efficiency of many data structures and algorithms.

Usage

• The Word RAM model is fundamental in computer science for designing and analyzing algorithms.
• It simplifies the theoretical analysis by assuming constant time for basic operations like reading and writing to memory.

By understanding the Word RAM model and the significance of w-bit words, one can better appreciate the design and efficiency of modern data structures and algorithms.