컴퓨터 과학으로 들어가게 해주는 강의 101.

컴퓨터 과학이 여는 세계 - 세상을 바꾼 컴퓨터, 소프트웨어의 원천 아이디어 그리고 미래
이광근 지음 / 인사이트 / 2015년 5월

0.

컴퓨터 과학으로 들어가게 해주는 강의 101.

비전공자라면 아주 쉽진 않을수 있겠지만

그래도 이정도 내용을 이렇게 풀어냈다는건 참으로 곱게 쓴 것이다.

오래 살아남을 책이라 생각한다.

1.

물리학, 화학, 생물학이 있듯 컴퓨터 과학이 있다.

이 책은 채 백 년이 되지 않은 역사 속  "컴퓨터 과학 고유의 핵심 아이디어"들과 그 발전을 잘 정리해 보여준다.

• 덧붙여 저자의 모국어로 된 깊이 있는 전공 서적에 대한 바람,

모국어의 시로 표현된 컴퓨터(를 넘어선 세상)에 대한 감흥이 아름답다 생각된다.

2.

튜링이 <계산 가능한 수에 대해서, 수리 명제 자동생성 문제에 응용하면서> 논문을 낸 것은 24세.

괴델의 불완전성 논리는 25세, 클로드 셰넌의 <릴레이와 스위치 회로를 기로로 분석하기> 논문은 21세.

세상의 많은 천재들의 깨달음은 번쩍하고 인생의 시작에 자리잡는다.

3.

1) 다비드 힐베르트 : 몇 개의 추론 규칙만으로 앞으로의 모든 명제들을 찾을 수 있는 게 아닐까?!!

2) 괴델 : 불완전성 정리(incompleteness theorem: 1931) 꿈 깨시라.

3) 튜링 : 괴델의 정리는 이렇게도 증명이 되겠습니다. 예를 들자면 여기 이런 기계가 있다고 해봅시다.

여기서 튜링의 어떤 일이든 할 수 있는 기계(universal machine, Turing machine)의 개념이 나오게 된 것.

4.

1) 부울(George boole) : 사람의 생각은 AND, OR, NOT으로 다 조립되는거다. = 부울 대수

• 대수(Algebra)는 무엇과 무엇이 같은지를 탐구하는 분야. 1+1은 2와 같다.

2) 클로드 셰넌 : 부울 대수 이거 스위치에 적용하면 딱 인걸?

• 결과를 얻기 위한 복잡한 회로들을 부울 대수로 바꿔서 체계를 만들어주기

3) 바든, 브래튼, 쇼클리(1957) : 짜잔, 작고 싼 스위치인 트랜지스터 입니다. 노벨상 주세요. 뿌우.

이러한 AND, OR, NOT을 넘어선 개념으로 만들어지는게 양자 컴퓨터이다.

5.

알고리즘의 실행 비용(복잡도, complexity)은 시간이나 메모리로 볼 수 있으며 big-O 표기법으로 표현한다.

문제는 대충 풀 수 있는 문제 P와 운빨 좋으면 불 수 있는 문제인 NP 문제로 나눠볼 수 있다.

• 현재의 튜링기계로서는 둘은 같지 않지만 미래에는 모른다.
• NP-complete 문제라는 것도 있다. NP중 가장 어려운 문제.

NP 문제를 푸는 법.

• 통밥(Heuristic) : 왠만큼 이렇게 하면, 왠만큼 적당한 답을 얻을 수 있다. 현실세계에서는 이정도만 되어도 제법 의미 있는 것이다.
• 무작위(Randomized algorithm) : 통밥의 약점을 커버해줄 무작위. 둘이 만나 시너지를 이룬다.

6.

프로그래밍 언어는

1) 기계적으로 이렇게 계산가능하다는 튜링 기계와

2) 수학적으로 이렇게 풀어낼 수 있다는 람다가 있다. 대략 이 녀석이 함수형 프로그래밍인가 보다.

• 논리적으로 증명을 하는 것이랑 언어로 프로그래밍을 하는 것이 1:!로 대응이 된다는 것.
• 탄탄하고 빈틈없이 증명을 해낸 후 그것을 바탕으로 프로그래밍을 한다면?!

#요약(abstract)이라는 한글 표현: 추상이라는 번역보다 훨씬 좋다.

3) 그리고 여기에 데이터에 기반하여 확률 추론 프로그래밍이 더해진다.

• 충분히 많아지는 데이터와, 충분히 저렴해지는 컴퓨터 성능의 지원사격
• 그 유명한 월마트는 당신 딸이 임신을 당신보다 먼저 안다!

7.

컴퓨터를 통해

인간의 지능은 잡다한 일에서 해방되어 고유의 지능에 집중하고, 컴퓨터와 협력하여 지능을 향상시킬 수 있게 되고

인간의 소통과 놀기 본능이 고삐 풀리고

인간의 시공간에 의한 제약을 뛰어넘는 현실 확장이 이루어진다.

지능에는

• 서술형, 방정식 형의 지식표현에서 컴퓨터를 통해 계산형 지식 표현을 얻게 되었음
• 지식 생성은
• 디덕(반드시 이끌기, 연역?)
• 앱덕(결과에서 원인 찾기, 가설적 추론)
• 인덕(특수->보편,귀납)을 통한 머신 러닝

소통본능

• 불을 지핀 것은 클로드 셰넌의 정보이론 (information theory)
• 통신은 하드웨어 개선이 아니라 소프트웨어적 개선으로 극복. 물리에서 정보로!
• 통신에서 잦은 것은 정보량이 적고 드문것은 정보량이 많다.
• 안녕안녕안녕안녕사랑해! : 사랑해가 가진 정보량!
• 사랑해사랑해사랑해헤어져! : 헤어져가 가진 정보량!
• 통신채널의 용량보다 정보량이 많으면 에러가 난다. 정보량을 줄여주면 된다.
• 오류 수정코드를 넣으면 결국 정보량은 그만큼 줄어드는 셈.

현실의 확장

• 컴퓨터가 풀 수 없는 문제라는 한계.
• 마누엘 블럼: 오히려 그것을 역이용한 암호화 - 1995년 튜링상
• 공통 비밀번호. 디피-헬만 열쇠교환
• 2^x을 공개된 소수 P로 나눈 나머지를 상대에게 보내고(A)
• 2^y를 공개된 소수 P로 나눈 나머지를 상대에게서 받으면(B)
• 각각 서로의 A, B에서 A^y를 P로 나눈 나머지 == B^x를 P로 나눈 나머지 = 공통의 비밀번호를 가지게 된다.
• https - 128비트 암호화도 이것을 사용. 비밀열쇠가 128비트라는 것이다.
• 자필 서명하기
• 자신만의 비밀열쇠로 암호화를 건 서명하기
• 비밀열쇠와 짝인 짝꿍열쇠는 공개됨.
• 그 짝꿍열쇠는 그 비밀열쇠만 열 수 있음.
• 리베스트, 샤미르, 애들먼 : 셋의 이니셜을 따서 RSA 암호방식 - 2002년 튜링상