Problems
Turing Machine
Big -o notation
♠Problem
◇decision problem: 결정을 하는 문제 답이 ex) 0인지 1인지
1/2보다 높은 확률
보통은 확률 1로 해결했을때
◇search problem: solution이 여러개 있고 그 중에 하나를 고를때
ex) Hamiltonian Circuit problem
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is acycle. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.
1. decision version: Given a graph, determine whether the graph has a Hamiltonian Circuit.
2. search version: Given a graph, find a Hamiltonian Circuit.
보통은 decision version보다 search version이 더 어렵다. search version으로 solve했을때 decision version이 solve되는 것이므로.
♠Reduction
A problem P1 is reduced to a problem P2, if we can construct an algorithm which solves P1 using an algorithm which solves P2.
: P1<=P2 라는 기호로 표현
ex) decisional Hamiltonian circuit problem<=search version of Hamiltonian circuit problem.
문제의 난이도를 define할 수 있다.
■ upper bound of a problem :이것보다는 어렵지 않다.
■ lower bound of a problem :이것보다는 어렵다.
ex) nlogn<= T(n) <=n^2
lower bound upper bound
컴퓨터의 사양과 관계없이 알고리즘의 수행속도를 define할 수 있다.
컴퓨터를 수학적으로 모델링한다.->튜링머신
튜링 머신:
deterministic T.M.
input tape
｜
transition function ― working tape
｜
output tape
transition function: 컴퓨터의 그 이전의 상태를 참조해서 다음 상태를 결정해 나간다.
working tape : 메모리 공간, 하드디스크 공간은 working tape에 저장된다.
output tape : 여기에 값을 써 내려 간다. 파일이 될 수도 있고, 모니터가 될 수도 있다.
transition function은 항상 deterministic하기 때문에 input이 같으면 output이 같을 수밖에 없다.
probabilistic T.M.
input tape
｜
random tape―transition function ― working tape
｜
output tape
random tape: 난수발생
input이 같아도 output이 다를 수 있다.
난수는 진짜 난수인가?
♠Complexity
▷time
▷space-사용하는 메모리
♠Complexity of problems
▷intractable: Halting problem
▷P/NP/BPP/IP
P: 효율적으로 풀수있는 문제 class /polynomial 한 time안에 풀 수 있다.
NP: 효율적으로 풀 수 없는 문제 class /polynomial 한 time 안에 풀 수 없다.
polynomial time algorithm은 무엇인가?
n^2(n: the length of an input)
n, n^2, n^4, n^100....nlogn은 polynomical time algorithm이다.
ex) sum1(a[1], ,a[n])
for i=1 to n
for j=1 to n
s=s+a[j]:
return s;
가장 많이 나타나는 연산(여기선 +)의 횟수
따라서 O(n^2)
sum2(a[1],,,,,a[n])
for j=1 to n
s=s+a[j];
return s*n;
->O(n)
psedo time conplextity
O; big O 이 알고리즘의 upper bound를 말해준다.
다음시간에 O,오메가, o, small 오메가에 대해 알아보자