• 어떻게 하면 주어진 복잡한 문제를 이진수 형태의 낮은 수준의 명령어만 이해하는 ‘단순한’ 컴퓨터 상에서 효율적으로 해결할 수 있을까?

  1. [Data Structure] 주어진 추상적인 문제를 어떠한 자료 구조를 사용하여 컴 퓨터의 구조에 최적화된 형태로 표현할 수 있을까?
  2. [Algorithm] 주어진 추상적인 문제를 어떠한 알고리즘을 사용하여 컴퓨터를 사용하여 가장 효율적으로 해결할 수 있을까
  3. [Complexity] 과연 컴퓨터가 주어진 문제를 효율적으로 해결할 수 있을까 ?
  4. [Computability] 과연 컴퓨터가 세상의 모든 문제를 해결할 수 있을까?

• Data Structure & Algorithm \rightarrow 1, 2, 3

• Automata Theory \rightarrow 4

from [Horowitz 1.2]

• An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. In addition, all algorithms must satisfy the following criteria:

  1. Input.
  • Zero or more quantities from the outside.
  • 외부로부터 0개 이상의 수량이 입력으로서 들어온다.
  2. Output.
  • At least one quantity is produced.
  • 하나 이상의 결과값이 수행된다.
  3. Definiteness.
  • Each instruction is clear and unambiguous.
  • 각 지침은 모두 명확하며, 애매하게 쓰여 있지 않다.
  4. Finiteness.
  • If we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite number of steps.
  • 제한된 수의 단계 후 종료된다.
  5. Effectiveness.

  • Every instruction must be basic enough to be carried out, in principle, by a person using only pencil and paper.

  • 손으로 풀 수 있을 만큼 효과적이어야 한다.

  • It is not enough that each operation be definite as in (3);

  • it also must be feasible. 또한 실현 가능하여야 한다.

• Problem (Post’s correspondence problem 포스트 대응 문제)

  • 결정 불가능한 결정 문제의 예시, 1946년 emil post 에 의해 고안
  • Consider a finite set P of ordered pairs of nonempty strings such as P = \{(a, ab), (b, ca), (ca, a), (abc, c)\}
  • A match of P is any string w such that, for some m > 0 and some pairs (u_1, v_1), (u_2, v_2), ..., (u_m, v_m) \in P, w = u_1 u_2...u_m = v_1 v_2...v_m.
  • Design an algorithm that determine, given P, whether P has a match.

• Cheolsu’s algorithm

  For i = 1, 2, 3, ... do 
    For each permutation of P of length i, do
      If it is a match, print ‘yes’ and exit. 
      If not, continue.

  • Can this be regarded as an algorithm?

• An algorithm is regarded as efficient or good if there exist a polynomial P(n) such that the time required for solving any instance of size n is bounded above by P(n).

• NP-Complete problems:

  • Nobody has found so far any good algorithm for any problem in this class.
  • It has been proved that if a good algorithm exists for some algorithm in this class, then a good algorithm exists for all NP-Complete Problem.

• Examples

  • Suppose a CD-ROM can store up to 720MBytes of data. You have a sequence of n files of sizes s_1, s_2, ..., s_n Mbytes, to dump into backup CDs. What is the minimum number of necessary CDs to store all the files?
  • Consider n tasks to be executed on CPU. All the tasks must be finished within the time requirement L (seconds). If the i-th task takes s_i seconds, and you can harness multiple processors, what would be the minimum number of processors needed to accomplish this?
  • Ex. L = 10, n = 6, and $(s_1, s_2, s_3, s_4, s_5, s_6) = (5, 6, 3, 7, 5, 4) $
  • then (5, 5), (6, 4), (7, 3)

어떻게 하면 좀 더 “효율적으로” 문제를 해결할까?

• Sequential search vs binary search

  • Problem: Determine whether x is in the sorted array S of n keys.
  • Inputs: positive integer n, sorted (nondecreasing order) arrays of keys S indexed from 0 to n - 1, a key x.
  • Outputs: the location of x \in S (-1 if x \notin S).

• Sequential search: T(n) = O(n)

• Binary search: T(n) = O(log n)

• 
  • [From Neapolitan] The number of comparisons done by Sequential & Binary Search when x is larger than all the array items
    • 40억 개의 element가 array에 있을 때, Sequential Search는 40억 개 항목과 비교하는 반면에 Binary Search는 단 33개의 항목만을 비교한다.
    • 컴퓨터가 1ns에 whlie loop를 통과할 수 있다고 가정한들 Binary search는 즉각적으로 결정을 내리는 반면 Sequential Search는 4s가 걸린다.

• Why is the binary search more efficient? 왜 이진검색이 더 효율적인가?

• Problem: Determine the n-th term in the Fibonacci sequence.

• Inputs: a nonnegative integer n

• Outputs: the nth term of the Fibonacci sequence.

  f_0 = 0 f_1 = 1 f_n = f_{n-1} + f_{n-2} for n \geq 2

//<recursive: divide-and-conquer>
int fib (int n) {
  if (n == 0) return 0;
  else if (n == 1) return 1;
  else return fib(n-1) + fib(n-2);
}

//<iterative: dynamic programming>
  int fib(int n) {
  index i;
  int f[0 .. n];
  f[0] = 0; 
  if (n > 0) {
  	f[1] = 1;
    for (i = 2; i <= n; i++)
      f[i] = f[i-1] + f[i-2];
  }return f[n];
}

• Recursive: $T(n) = O(2^n) $

• Iterative: T(n) = O(n)

• Why is the iterative version more efficient?

  • 
  • T(n) > 2 ^{\frac n 2} for n \geq 2
  • Mathematical induction을 써서 증명해볼 것!

• Linear versus exponential

  • 

  • [From Neapolitan] This table compares these expressions for various values of n. The execution times are based on the simplifying assumption that one term can be computed in 10^{−9} second.

  • The table shows the time it would take 'Iterative Algorithm' to compute the nth term on a hypothetical computer that could compute each term in a nanosecond, and it shows a lower bound on the time it would take to execute 'Iterative Algorithm'.

  • By the time n is 80, 'Recursive Algorithm' takes at least 18 minutes. When n is 120, it takes more than 36 years, an amount of time intolerable compared with a human life span. Even if we could build a computer one billion times as fast, 'Recursive Algorithm' would take over 40,000 years to compute the 200th term. This result can be obtained by dividing the time for the 200th term by one billion.

  • We see that regardless of how fast computers become, 'Recursive Algorithm' will still take an intolerable amount of time unless n is small. On the other hand, 'Iterative Algorithm' computes the nth Fibonacci term almost instantaneously.

This comparison shows why the efficiency of an algorithm remains an important consideration regardless of how fast computers become