CS study/이산 수학 (2) 썸네일형 리스트형 P-NP problem P-NP problem P-NP문제를 이해하기 위해 차근차근 기초지식부터 공부해보자. 알고리즘과 시간 복잡도 컴퓨터를 사용하여 특정한 계산 문제를 풀기 위해서는, 바로 그 문제에 해당되는 알고리즘을 컴퓨터에게 알려주어야 한다. 그리고 컴퓨터공학자들의 주된 관심사는 그 알고리즘이 문제를 얼마나 빨리 해결할 수 있느냐는 것이다. 시간복잡도 점근적 표기법은 아래와 같다. (Worst case) $ O(1) < O(\log N) < O(N) < O(N \log N) < O(N^2) < O(N^3) < O(2^N) < O(N!) $ 다들 알다시피 어떤 문제를 해결함에 있어 입력의 크기가 N개 일 때, 연산을 해야하는 대략적인 횟수를 가리키는 것이 시간복잡도의 O 표현이다. 컴퓨터에게 쉬운 문제와 어려운 문제를 나.. Halting Problem (정지 문제) Halting Problem 정지 문제는 "주어진 프로그램이 해결하고자 하는 문제를 해결하는지 말해줄 수 있는 일반화된 알고리즘이 존재하는가?" 라는 질문이다. 이 문제 자체가 이해가 안되는 사람들을 위해 쉽게 설명한 영상을 가져왔다. https://www.youtube.com/watch?v=92WHN-pAFCs 위의 영상에서 정지문제 자체에 대한 설명과 귀류증명과정을 정말 알기 쉽게 설명했다. 꼭 한번 보는 것을 추천한다. 정지 문제란? (쉬운 설명) 산술식을 받아서 결과값을 출력하는 기계 A가 있다고 가정해보자. 이 기계 A는 항상 옳은 답을 출력한다. 또 체스를 두는 기계 C가 있다고 가정해보자. 이 기계는 현재의 체스판 상태를 입력을 받아서 다음 수를 출력한다. 이 기계 C는 체스를 너무 잘해서 .. 이전 1 다음