(2021.12.01)
알고리즘 수업 들으면서 정리하기 23탄
w14 실강
NP-completeness 내용 시작
계산 복잡도, 튜링 기계에 대해 배웠다
NP-completeness
Computational Complexity
> 알고리즘은 특정 알고리즘의 performance 특성 (성능 특성)에 대한 연구이다. > 계산 복잡도(계산 이론)은 알고리즘보다는 문제의 특성에 대한 연구이다.
우리는 문제를 solvable problem과 unsolvable problem으로 나눌 수 있다.
> unsolvable problem은 다시 세가지로 나뉜다.
1. Unsolvable problems ---> halting problem
2. Solvable problems
a. Provably intractable(infeasible) problems --> provably는 입증된 이라는 의미
b. Probably intractable problems --> probably 는 아마도 라는 의미
c. Tractable problems(feasible problems)
(intractable problem은 efficient algorithm이 존재하지 않는 것을 의미)
finite automaton
> finite tape 에는 input string 이 있다.
> tape는 왼쪽->오른쪽 으로 읽는다. (반대 방향 불가능)
> auxiliary memory를 가지지 않는다. (추가적인 메모리 x)
> controller를 directed graph 라고 생각하면 편함
Turing Machine
> digital computation의 모델 중에서 turing machine보다 강력한 것은 없다.
- slightly different labels on arcs
- plus tape as auxiliary memory (추가적인 메모리 o)
- tape head (or read-write head)
- input : finite-length string of symbols (tape에 놓인다)
- tape head 는 tape cell 중 하나에 놓여진다.
- 초기에 tape head는 input 의 가장 왼쪽 cell (leftmost cell)에 놓여진다.
turing machine은 scanned symbol 과 current state에 기초하여 다음의 작업들을 한번에 수행한다.
- state 바꾸기
- 현재 scan한 tape cell에 new symbol을 overwrite 하기
- tape head를 left or right 로 움직이기
tape의 each cell은 다음의 symbol을 가질 수 있다.
- input alphabet으로 부터의 symbol
- tape alphabet으로부터의 symbol
- blank symbol △
(input alphabet은 tape alphabet에 속한다)
TM transition function
state q와 reading symbol X 는
state p로 move하고, Y로 overwrite되고, tape head는 left or right로 이동될 것이다.
여기서 헷갈렸던 부분이 state와 symbol인데
state는 p와 q에 해당하는 것처럼 해당 상태를 의미하고,
symbol 은 a,b,c,d 처럼 tape cell에 들어가있는 것들을 의미함
δ(q1,b)=(q2,△,R) 을 해석하면
현재 q1 이라는 state에 있으며, tape head가 가리키는 symbol은 b이다.
이를 q2 라는 state로 바꾸고, b는 blank △로 overwrite하며, tape head는 오른쪽으로 옮긴다.
라고 해석할 수 있다.
'Computer Science > algorithms' 카테고리의 다른 글
| [알고리즘] Halting problem (4) | 2021.12.08 |
|---|---|
| [알고리즘] TM transition function (halting, crashing, looping) (2) | 2021.12.07 |
| [알고리즘] N-Queens problem : backtracking algorithm (0) | 2021.11.30 |
| [알고리즘] Maximum Flow : The Ford-Fulkerson method (0) | 2021.11.24 |
| [알고리즘] Minimum Spanning Tree : Generic algorithms & Prim algorithms (3) | 2021.11.17 |
