(2021.12.14) 알고리즘 수업 들으면서 정리하기 26탄 w15-2 녹강 + 보충강의 정리 저번 시간에 배우던 solvable problem 나머지 부분에 대해서 배웠따 개념이 너무 뒤죽박죽함 ▷ solvable problems > provably intractable problems (infeasible) : 해결하기 어려움이 입증된 문제 > probably intractable problems : 아마도 해결하기 어려울 것 같은 문제 ---> NP > tractable problems (feasible) : 다루기 쉬운 문제 --> P ▷ deterministic turing machine(DTM) : 주어진 state, 주어진 input 에 대해서 하나의 possible action만 존재하는..

(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..