**커뮤니케이션북스의 큰글씨책은 약시나 노안으로 독서에 어려움을 겪는 독자를 위해 만든 책입니다. 커뮤니케이션북스의 책은 모두 큰글씨책으로 제작됩니다. 일상용어가 되어 버린 알고리즘, 그리고 알고리즘이 무엇인지 모르는 요즘 사람을 위한 책 코딩을 위한 필수지식, 프로그래밍 언어와 알고리즘 알고리즘은 무엇인가 불과 10여 년 전까지만 해도 낯설고 어렵게만 느껴지던 용어 ‘알고리즘’이 이젠 생활 속의 용어가 되어 버렸다. 인공지능 알고리즘, 추천 알고리즘 등등. 그러나 정작 알고리즘이 무엇이며, 어떤 일을 하는지를 정확히 아는 사람은 드물다. 이 책은 그런 사람들을 위해 쓰였다. 알고리즘이 상식이 되 어버린 사회지만, 정작 알고리즘이 무엇인지 모르는 요즘 사람들을 위한 책, 이과 출신이 아니어도 찬찬히 읽기만 해도 알고리즘이 무슨 일을 하는지 이해할 수 있는 책이다. 알고리즘이란 무엇인가, 세상에 알고리즘으로 해결 불가능한 문제는 존재하는가, 왜 어떤 문제는 계산이 가능하고, 어떤 문제는 계산이 가능하지 않은가 등등의 문제에 대한 찾기 위해 이 책에서는 여러 종류의 알고리즘들 및 계산이 불가능한 함수를 소개한다. 또한 알고리즘이 하는 일의 양을 계산하는 방법과 계산 문제들의 구조에 대해 설명하고, 괴델의 제1 불완전성 정리를 계산 가능성 관점에서 소개한다. 이 외에 책 후반부에서는 우리가 현재 사용하고 있는 컴퓨터와는 전혀 다른 방식의 컴퓨터들인 양자컴퓨터와 DNA컴퓨터의 특성을 이용한 알고리즘들을 소개한다. 이 책을 통해 독자들은 알고리즘으로 해결할 수 있는 문제들과 그렇지 못한 문제들에 대한 이해의 폭을 넓힐 수 있다. 고려대학교 교양교육원의 핵심 교양 과목인 ‘하이퍼텍스트와계산가능성’의 교재이기도 하다.

머리말 　

01 알고리즘 　
02 계산 불가능한 함수 　
03 계산복잡도
04 계산 문제는 언제 어려워지는가?
05 P 대 NP 문제
06 NP 완전성과 계산 문제들 간의 구조적 관계 　
07 괴델의 제1 불완전성 정리
08 참이지만 증명 불가능한 문장
09 괴델 문장 　
10 구조 　
11 양자컴퓨터 　
12 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 Godel)이 존 폰 노이만(John von Neumann)에게 보낸 편지에서 언급된 문제[22]라고 알려져 있고 클레이연구재단의 ‘새천년 문제(Millennium Problems)’ 중 하나이기도 합니다.
- (본문 “05 P 대 NP 문제 ” 중에서)

우리가 매일 사용하는 컴퓨터 대부분은 1930년대에 앨런 튜링이 제안한 모델에 기반해 만들어진 폰 노이만 구조의 컴퓨터입니다. 그런데 양자컴퓨터는 이와는 달리 양자역학적 특성을 활용해 만들어진 컴퓨터입니다. 아직 상용화 단계는 아니지만 특정 계산 문제들에 대해 일반 컴퓨터보다 효율적이라는 것이 알려지면서 최근 국내외적으로 많은 관심을 받고 있습니다.
- (본문 “11 양자컴퓨터” 중에서)알고리즘과 컴퓨터 프로그램의 가장 큰 차이는 알고리즘의 경우 정의 자체가 해당 계산 문제를 정확하게 유한 단계 안에 해결하는 방법을 기술한 것이기 때문에 하나의 계산 문제를 해결하는 알고리즘이 주어진다면 그 알고리즘에는 오류가 있을 수 없습니다. 반면 컴퓨터 프로그램의 경우는 약간 오류가 있다고 해도 컴퓨터에서 실행된 후 잘못된 결과를 출력하거나 반복을 계속해 끝나지 않고 무한루프를 돌 가능성이 항상 존재합니다. _ “01 알고리즘 ” 중에서 계산이 가능하다는 것의 의미는 알고리즘이 존재한다는 것입니다. 여기서 계산의 대상이 될 수 있는 것들에는 계산 문제, 함수, 집합이 있습니다. 이 장에서는 바쁜 비버 함수(busy beaver function)가 계산 불가능하다는 증명을 합니다. 바쁜 비버 함수가 계산 불가능하다는 말은 이 함수의 함수 값을 계산하는 알고리즘이 존재하지 않는다는 말입니다. _ “02 계산 불가능한 함수 ” 중에서 어떤 계산 문제가 해결 가능하다는 것은 해당 계산 문제의 알고리즘이 존재한다는 것이지만, 그렇다고 해서 그 계산 문제가 효율적으로 해결된다는 것을 의미하지는 않습니다. 계산 문제가 효율적으로 해결된다는 것은 그 문제를 해결하는 알고리즘들 중에 하나라도 효율적으로 작동하는 것이 존재하는가 그렇지 않은가를 기준으로 정의합니다. _ “03 계산복잡도” 중에서 P 대 NP 문제를 직접 언급하지는 않았지만 역사적으로 이 문제의 시작은 1950년대 쿠르트 괴델(Kurt G?del)이 존 폰 노이만(John von Neumann)에게 보낸 편지에서 언급된 문제[22]라고 알려져 있고 클레이연구재단의 ‘새천년 문제(Millennium Problems)’ 중 하나이기도 합니다. _ “05 P 대 NP 문제 ” 중에서 우리가 매일 사용하는 컴퓨터 대부분은 1930년대에 앨런 튜링이 제안한 모델에 기반해 만들어진 폰 노이만 구조의 컴퓨터입니다. 그런데 양자컴퓨터는 이와는 달리 양자역학적 특성을 활용해 만들어진 컴퓨터입니다. 아직 상용화 단계는 아니지만 특정 계산 문제들에 대해 일반 컴퓨터보다 효율적이라는 것이 알려지면서 최근 국내외적으로 많은 관심을 받고 있습니다. _ “11 양자컴퓨터” 중에서