튜링의 1936년 논문에서 시작된 질문: 컴퓨터가 풀 수 없는 문제가 존재한다

Computation as a Universal and Fundamental Concept

Tim Roughgarden 교수가 컴퓨터 과학의 기초를 다지는 강의를 제공합니다. 1936년 Alan Turing의 연구에서 시작해, 정지 문제와 같은 알고리즘으로 해결 불가능한 문제의 존재를 설명합니다. 이어서 빠르게 풀 수 있는 문제와 그렇지 않은 문제를 구분하며, 여행하는 외판원 문제와 NP-완전성 이론을 통해 P-NP 문제가 왜 컴퓨터 과학과 수학의 가장 중요한 미해결 질문인지 탐구합니다. 암호학, 인공지능, 양자 컴퓨팅에 대한 시사점까지 다룹니다. 사전 지식 없이도 들을 수 있는 강의입니다.