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밖에 못쓴다.