컴퓨터과학이 여는 세계

 

교양서 언어로 표현하는 컴퓨터공학 전공서
프로그래밍 언어론, 알고리즘과 P / NP complete문제, 오토마타, 정보이론, 암호학 기초, 통신까지
다양한 분야의 지식을 일관성 있는 이야기로 아우른다.
컴퓨터과학이라는 학문의 기반을 단단히 할 수 있는 디딤돌 같은 책.

 

이 책은, 페이스북에서 팔로우하는 분의 피드 게시글로 처음 알았다.

 

[꼼꼼 리뷰] 개발자를 꿈꾸는 '비전공생'을 위한 추천 도서 Best 3

 

개발자를 꿈꾸는 비전공생을 위한 추천도서. 관심이 안 갈 수 없는 주제였다. 어쩌다보니 경제학과 출신으로 개발자가 되었지만, 공부하면 할수록 배워야 할 지식의 폭은 넓고 깊었다. 업에서 오래 살아남기 위한 기초체력이 컴퓨터과학 / 공학 지식이라는 걸 뼈저리게 느끼고 있었지만, 취직 준비를 하고 있을 때에는 눈앞의 코딩테스트와 기술면접을 해결하기도 벅찼었다.

 

책의 알찬 내용을 내 능력껏 최대한 흡수하려고 노력했고, 그만한 가치가 있었다고 생각한다. 내 소감을 나열하기보다는, 내가 소화한 이 책의 얼개와 핵심을 얼기설기 글로 푸는 게 더 읽을 만할 것 같다.

 

---

 

이 책은 취준생의 니즈와는 결이 다르다. 코딩테스트에 적용할 알고리즘이나, 기술면접에서 언급할 수 있는 전공지식을 다루지 않는다. 컴퓨터과학이라는 학문이 어떤 계기로 등장했는지를 괴델의 불완전성의 정리와 튜링의 튜링머신으로 소개하고, 수학과 논리학의 증명이 튜링머신과 어떻게 맞물려가며 컴퓨터라는 거대한 논리 연산장치가 되었는지 흐름을 보여준다. 논리학과 오토마타를 맛보고 지나간다.

 

이후에는 소프트웨어를 구축하는 두 가지 뿌리인 ‘컴퓨터가 문제를 어떻게 풀 수 있도록 할 것인가' 와 ‘어떻게 컴퓨터가 알아들을 수 있게 표현할 것인가'를 다룬다. 각각 ‘알고리즘'과 ‘프로그래밍 언어론'이라는 전공으로 뻗어가는 내용이다. 

 

소프트웨어에게 문제풀이 방법을 제시하면, 소프트웨어는 방법을 그대로 재현해서 문제를 풀어낸다. 어떤 문제를 풀 수 있도록 해법을 소프트웨어에게 알려주어야 한다. 그게 알고리즘이다. 그렇다면, 현재의 연산 성능과 알고리즘만으로는 풀 수 없는 문제들과, 현실적인 비용으로 해결 가능한 문제를 구분해야 한다.

 

이 과정에서 알고리즘의 시간복잡도 Big O 표기를 설명하고, 다항시간에 풀 수 있는 문제 - Polynomial, 현실적인 비용으로 풀어낼 방법은 현재까지 없지만 운 좋으면 답을 구할 수 있는 문제 - Non Deterministic Polynomial - 의 개념을 소개한다. 대표적으로, NP문제인 해밀턴 경로 (주어진 지도 위의 도시를 한 번씩만 방문하는 경로가 존재하는가?), 주어진 bool식이 참이 되게 할 수 있는가?와 같은 것들이 언급된다. NP 문제들이 앞으로는 P 문제가 될 수 있는지, 즉 P == NP인지 아직 아무도 확답하지 못하며, 현재까지의 소프트웨어로는 P != NP일 가능성이 높다는 것도 덧붙인다.

---

프로그래밍 언어론에서, 저자는 언어론이 마치 중력과 같다고 소개한다. ‘기계에게 명령어를 전달한다’는 철학에 기반한 중력을 튜링기계, ‘함수와, 함수를 통과하는 데이터의 흐름’이라는 논리학에 기반한 중력을 람다 표현식이라고 부른다. 기계에게 명령어를 전달하려면 명령을 기계어로 번역하는 ‘컴파일러'가 필요하다. 하지만 함수와 데이터의 흐름으로 접근한다면 컴퓨터는 기계가 아니므로, 대신 소프트웨어 실행기인 ‘인터프리터' 관점에서 접근한다.

 

두 개의 중력은 같은 결과를 바라보는 다른 시선일 뿐이므로, 배타적이지 않다. 논리학에 기반을 두는 람다 표현식에서 ‘True인 논리식'에 대응되는 ‘데이터 타입'이 대두됐고, 데이터 타입으로 표현하는 ‘Abstraction (요약. 책에서는 추상화라는 번역보다는 ‘요약'이라는 번역을 선호했다)’ 개념이 중요하게 자리잡기도 했다.

 

---

마지막으로, 컴퓨터과학이 만들어낸 인간 지능의 확장을 소개한다. 

 

지식을 확장하는 방법인 Abduction (A이면 B이고 B가 사실이면, A도 사실일 것이다), Deduction(지금까지 수집한 데이터를 보니 아마도 A이면 B일 것이다) 두 가지 방법에서 컴퓨터는 지식 확장에 크게 기여했으며, 머신러닝과 딥러닝같은 핫 키워드뿐만 아니라 인간 유전자 염기서열, 뇌 뉴런지도 프로젝트에도 큰 발전을 이루었다고 소개한다. 구글의 PageRank 알고리즘은 지식의 대중화에 기여했으며, 군중 지능 (크라우드소싱)과 같은 형태의 문제해결 방식도 등장했다.

 

이렇게 지식의 확장에 큰 기여를 한 부분은 통신이었고, 통신이 크게 발전하게 된 계기는 정보이론의 등장이었다.. 컴퓨터와 컴퓨터가 통신할 때 발생하는 노이즈, 정보 손실은 하드웨어 한계가 아니라 메시지가 지닌 정보량 때문이라는 이론은 하나의 혁명이었다고 한다. 아무리 잡음이 많은 채널이라고 해도 채널 용량보다 적은 메시지(정보량)을 전달하기만 한다면 데이터 손실이 발생하지 않는다는 것이 정보이론의 핵심이었고, 메시지를 온전히 전송하고 전송받기 위한 인코딩 / 디코딩 기법이 발전하는 계기가 된다.

 

앞서 보았던 NP문제 - 현실적인 시간 안에 풀 수 없는 문제 - 를 역발상으로 활용하는 암호이론도 등장했다. 서로만 알 수 있는 암호조각을 활용해 둘만 알 수 있도록 암호화하는 디피-헬만 (diffie-hellman key exchange) 방식, 개인키로 암호화하고 공개키로 복호화하는 방식으로 자신을 증명하는(즉 전자서명에 활용하는) RSA 암호기술을 간단히 소개한다. 또한, P == NP의 가능성과 양자컴퓨팅의 발전속도는 현재 암호화 기술이 가진 한계를 보여준다.

 

 

---

저자분은 서울대학교 컴퓨터공학부 교수이며, 강의 내용이 유튜브에도 올라가 있다.

www.youtube.com/playlist?list=PL0Nf1KJu6Ui7yoc9RQ2TiiYL9Z0MKoggH

컴퓨터과학이 여는 세계_이광근

시간이 되면 강의를 보는 것도 좋지만, 한 학기 분량의 강의인만큼 분량이 많다. 책의 내용이 오히려 정수에 가까울 거라 생각한다.