알고리즘의 능력과 한계

일상용어가 되어 버린 알고리즘,
그리고 알고리즘이 무엇인지 모르는 요즘 사람을 위한 책

코딩을 위한 필수지식, 프로그래밍 언어와 알고리즘
알고리즘은 무엇인가

불과 10여 년 전까지만 해도 낯설고 어렵게만 느껴지던 용어 ‘알고리즘’이 이젠 생활 속의 용어가 되어 버렸다. 인공지능 알고리즘, 추천 알고리즘 등등. 그러나 정작 알고리즘이 무엇이며, 어떤 일을 하는지를 정확히 아는 사람은 드물다. 이 책은 그런 사람들을 위해 쓰였다. 알고리즘이 상식이 되 어버린 사회지만, 정작 알고리즘이 무엇인지 모르는 요즘 사람들을 위한 책, 이과 출신이 아니어도 찬찬히 읽기만 해도 알고리즘이 무슨 일을 하는지 이해할 수 있는 책이다.

알고리즘이란 무엇인가, 세상에 알고리즘으로 해결 불가능한 문제는 존재하는가, 왜 어떤 문제는 계산이 가능하고, 어떤 문제는 계산이 가능하지 않은가 등등의 문제에 대한 찾기 위해 이 책에서는 여러 종류의 알고리즘들 및 계산이 불가능한 함수를 소개한다. 또한 알고리즘이 하는 일의 양을 계산하는 방법과 계산 문제들의 구조에 대해 설명하고, 괴델의 제1 불완전성 정리를 계산 가능성 관점에서 소개한다. 이 외에 책 후반부에서는 우리가 현재 사용하고 있는 컴퓨터와는 전혀 다른 방식의 컴퓨터들인 양자컴퓨터와 DNA컴퓨터의 특성을 이용한 알고리즘들을 소개한다. 이 책을 통해 독자들은 알고리즘으로 해결할 수 있는 문제들과 그렇지 못한 문제들에 대한 이해의 폭을 넓힐 수 있다.

고려대학교 교양교육원의 핵심 교양 과목인 ‘하이퍼텍스트와계산가능성’의 교재이기도 하다.

코딩 교육이 열풍이다. 디지털 시대를 살아가기 위해서는 반드시 알아야 할 기술이어서다. 코딩을 위해서는 또 무엇을 알아야 하나. 파이선이나 자바 같은 프로그래밍 언어와 알고리즘을 프로그래밍 언어로 표현하는 법이다. 그럼 알고리즘은 무엇인가. 계산 문제의 입력을 받아 유한 단계 안에서 정확한 출력을 찾는 방법이다. 이 책은 알고리즘의 개념과 알고리즘으로 해결 가능한 계산 문제, 알고리즘 분석 방법, 알고리즘으로 해결할 수 없는 계산 문제 등 알고리즘이 할 수 있는 일과 한계를 이과생이 아니어도 이해할 수 있게 설명한다. 다양한 알고리즘들에 대한 기초 지식을 쌓을 수 있다.

박성빈
고려대학교 컴퓨터학과 교수다. 남가주대학교 컴퓨터과학과에서 박사학위를 받았다. 현재 고려대학교 컴퓨터교육과 학과장 및 교육대학원 컴퓨터교육 전공 주임 교수다. 관심 연구 분야는 시맨틱 웹 기반 교육 및 이론 전산학이며, 최근에 양자컴퓨터를 이용한 코딩 및 알고리즘 교육에 대한 연구를 진행 중이다.

머리말 　

01 알고리즘 　
02 계산 불가능한 함수 　
03 계산복잡도
04 계산 문제는 언제 어려워지는가?
05 P 대 NP 문제
06 NP 완전성과 계산 문제들 간의 구조적 관계 　
07 괴델의 제1 불완전성 정리
08 참이지만 증명 불가능한 문장
09 괴델 문장 　
10 구조 　
11 양자컴퓨터 　
12 DNA컴퓨터 　

용어 정의 　
참고 문헌 　
찾아보기 　

알고리즘과 컴퓨터 프로그램의 가장 큰 차이는 알고리즘의 경우 정의 자체가 해당 계산 문제를 정확하게 유한 단계 안에 해결하는 방법을 기술한 것이기 때문에 하나의 계산 문제를 해결하는 알고리즘이 주어진다면 그 알고리즘에는 오류가 있을 수 없습니다. 반면 컴퓨터 프로그램의 경우는 약간 오류가 있다고 해도 컴퓨터에서 실행된 후 잘못된 결과를 출력하거나 반복을 계속해 끝나지 않고 무한루프를 돌 가능성이 항상 존재합니다.
_ “01 알고리즘 ” 중에서

계산이 가능하다는 것의 의미는 알고리즘이 존재한다는 것입니다. 여기서 계산의 대상이 될 수 있는 것들에는 계산 문제, 함수, 집합이 있습니다. 이 장에서는 바쁜 비버 함수(busy beaver function)가 계산 불가능하다는 증명을 합니다. 바쁜 비버 함수가 계산 불가능하다는 말은 이 함수의 함수 값을 계산하는 알고리즘이 존재하지 않는다는 말입니다.
_ “02 계산 불가능한 함수 ” 중에서

어떤 계산 문제가 해결 가능하다는 것은 해당 계산 문제의 알고리즘이 존재한다는 것이지만, 그렇다고 해서 그 계산 문제가 효율적으로 해결된다는 것을 의미하지는 않습니다. 계산 문제가 효율적으로 해결된다는 것은 그 문제를 해결하는 알고리즘들 중에 하나라도 효율적으로 작동하는 것이 존재하는가 그렇지 않은가를 기준으로 정의합니다.
_ “03 계산복잡도” 중에서

P 대 NP 문제를 직접 언급하지는 않았지만 역사적으로 이 문제의 시작은 1950년대 쿠르트 괴델(Kurt Gödel)이 존 폰 노이만(John von Neumann)에게 보낸 편지에서 언급된 문제[22]라고 알려져 있고 클레이연구재단의 ‘새천년 문제(Millennium Problems)’ 중 하나이기도 합니다.
_ “05 P 대 NP 문제 ” 중에서

우리가 매일 사용하는 컴퓨터 대부분은 1930년대에 앨런 튜링이 제안한 모델에 기반해 만들어진 폰 노이만 구조의 컴퓨터입니다. 그런데 양자컴퓨터는 이와는 달리 양자역학적 특성을 활용해 만들어진 컴퓨터입니다. 아직 상용화 단계는 아니지만 특정 계산 문제들에 대해 일반 컴퓨터보다 효율적이라는 것이 알려지면서 최근 국내외적으로 많은 관심을 받고 있습니다.
_ “11 양자컴퓨터” 중에서

우리는 매일 수많은 문제들을 마주하게 됩니다. 그중에는 계산이 필요한 문제들도 있고 그렇지 않은 문제들도 있는데, 계산이 필요한 문제들은 예외 없이 알고리즘으로 해결해야 하는 문제들입니다. 1930년대에 앨런 튜링이 계산의 수학적 모델인 튜링 기계를 제안한 이래 컴퓨터는 날로 발전을 거듭하고 있고, 4차 산업혁명 시대가 본격적으로 펼쳐지고 있습니다. 인공지능에 대한 관심이 그 어느 때보다도 높고 특히 많은 학생들이 프로그래밍을 배우기 위해 시간과 노력을 투자하고 있는 이때, 이 책에서 친절하게 소개하는 알고리즘들 및 계산 가능/불가능을 판단하는 논리와 구조는 비단 수학과 컴퓨터의 세계에 국한되지 않고, 인생이라는 보다 넓은 세계에 ‘효율적 계산’이라는 인사이트를 던져 줄 수 있으리라 확신합니다.
조영헌_고려대학교 역사교육과 교수

최근에 국내외적으로 소프트웨어 교육에 대한 관심이 높아지고 있습니다. 이 책은 소프트웨어 교육에서 중요한 역할을 하며 논리적 사고 훈련에 도움을 줄 수 있는 다양한 종류의 알고리즘들을 비전공자들도 알기 쉽게 설명합니다. 특히 비결정적 알고리즘, 오라클 알고리즘들과 같이 생소한 개념들을 직관적인 예제들을 이용해 소개하고, 이들을 바탕으로 클레이재단의 새천년문제들 중 하나로 유명한 P 대 NP 문제 및 괴델의 제1 불완전성 정리, 그리고 새로운 방식의 컴퓨터들인 양자컴퓨터와 DNA컴퓨터에 이르기까지 핵심적인 내용들을 명쾌하게 소개하고 있습니다. 독자들에게 계산이 가능한 세상과 계산이 불가능한 세상을 바라볼 수 있게 도와주는 가이드 역할을 적절히 하리라 기대합니다.
강승석_서울여자대학교 디지털미디어학과 교수