컴퓨터 과학이 여는 세계

컴퓨터 과학이 여는 세계

회사분의 추천으로 읽게 된 책

조금 읽다보니 느낀 점은,

(개발자한텐 좀 쉬운 책이 아니라.. 이 분께 좀 쉬운 책이 아닐까하는..생각이 잠시..(먼산) )

아 알고보니 유튜브 도 있었다.  강의개수가 82개 정도..음.. 

https://www.youtube.com/watch?v=HTWSPoDLmHI&list=PL0Nf1KJu6Ui7yoc9RQ2TiiYL9Z0MKoggH

댓글을 보니 이런 내용들은 그냥 일반학생들을 위한 교양정도였구나..크흠... 크흠..흠.. 

자 그럼 리뷰를 시작해볼까 우선 목차부터.

목차

01 - 마음의 도구

02 - 400년의 축적

03 - 그 도구의 실현

04 - 소프트웨어 지혜로 짓는 세계

05 - 그 도구의 응용

06 - 마치면서

---

01. 마음의 도구 : 프롤로그

 컴퓨터 세계의 혜택을 이야기하고, 어떻게 마음의 도구와 그 도구를 다루는 방법의 원천이 생겼을까를 고민함.

이 고민에 대한 여행에 네개의 코스로 이루어져 있음

1. 400년의 축적

2. 그 도구의 실현

3. 소프트웨어 지혜로 짓는 세계

4. 그 도구의 응용

02. 400년의 축적

2.1 보편만능기계의 탄생

당대 수학계에서는 몇개의 추론 규칙만 가지면 앞으로 수학자들이 증명할 명제들을 모두 술술 찾을 수 있지 않을까 라는 고민을 함.

이에 반박하여 쿠르트 괴델이 1931년 다음의 증명을 발표함

기계적인 방식만으론 수학의 모든 사실을 만들어낼 수 없다

앨런 튜링은 다음과 같은 가설을 증명하기 위하여 간단한 기계부품들을 정의하는데 이것이 바로 보편만능의 기계 즉 컴퓨터의 시초가 된다

참고 링크 : https://www.scienceall.com/현대-컴퓨터의-모델-튜링기계turing-machine의-고안

앨런튜링이 정의한 부품은 

무한히 많은 칸을 가진 테이프, 

테이프에 기록되는 심벌, 

테이프에 기록된 심벌을 읽거나 쓰는 장치, 

그 장치의 상태를 나타내는 심벌들, 

그리고 기계의 작동 규칙표이다. 

(음 여기서 컴퓨터의 스멜이 벌써.. ) 

튜링은 이렇게 정의한 기계부품들로 다양한 일을 하는 기계뜰을 만들어 보이면서 기계적인 계산이란 그렇게 만든 기계로 돌릴 수 있는 것들로 한정해도 충분한 것같다고 설득.

테이프에 0과 1을 반복해서 쓰는 기계에서부터 0을 시작으로 1을 점점 많이 쓰는 기계등을 만들어보인다.. 사칙연산을 하는 기계도 물론 만들 수 있다.

고 하게 되었다고 함.

중간에 튜링에 증명 이야기가 나오는데 이 부분은 리뷰에서는 생략하고.. 

2.2 400년

논리추론이라는 몇가지 방식의 생각패턴을 반복해서 사용하는 것같다는 감을 잡고 그 생각패턴을 명확하게 드러내 보고 싶어했던 사람들.

이러한 논리패턴의 역사는 400년이라고 하는데, 튜링의 논문 이전부터 계산하는 기계장치는 꾸준히 고안되었다고 한다.

라이프니츠가 1600년대에 만든 사칙연산 계산기와 배비지가 1830년대에 만들고 확장했던 자동 계산기가 그렇다고 함.

---

03. 그 도구의 실현

3.2 생각 - 부울의 연구

1854년 조지 부울이 생각의 법칙에 대한 탐구라는 책을 발표함. 이 책이 오늘날 부울대수라는 것의 시작이 됨.

그리고, 또는 아닌 이라는 생각의 선택 조립방식을 고안

3.3 스위치

클로드 섀넌( 자주 보는 이름^^) 이 1937년 릴레이와 스위치 회로를 기호로 분석하기라는 논문을 제출

스위치 회로가 부울논리의 날개를 달면서 디지털 논리회로라는 새로운 이름이 붙게 됨.

3.4 컴퓨터의 실현

앞서 살펴본 논리회로 아이디어에 따라 튜링기계의 모든 부품을 만들 수 있다

만들 것은 튜링기계의 규칙표대로 실행하는 장치, 메모리장치, 그리고 메모리를 읽고 쓰는 장치이다.

여기서 잠시 다룰 내용 : 공학자들이 늘 동원하는 지혜. 복잡한 것을 만들거나 다룰 때 쓰는 솜씨. 

속내용을 감추면서 차곡차곡 쌓기 ( abstraction hierarchy )

예를 들어 자동차를 만든다고 하면 자동차를 사용하는 사람은 자동차가 어떻게 만들어졌는지 알 필요가 없게하는.. 그런 법칙

폰 노이만

1945년 존 폰 노이만이라는 수학자가 컴퓨터를 설계함. EDVAC (전자식 이산 변수 자동 계산기) 라는 컴퓨터

현대에 이르러 트랜지스터라는 작고 싸게 만들 수 있는 전기 스위치가 발명되어서 전자 컴퓨터 하드웨어의 폭발전 발전이 됨.

---

04. 소프트웨어, 지혜로 짓는 세계

소프트웨어는 사람의 지혜를 통과하면서 언어로 짜짓는다. 계획을 짜고 전략을 짜고 가구를 짜고 무늬를 짜듯이, 농사를 짓고 건물을 짓고 이름을 짓고 시를 짓듯이 소프트웨어는 사람이 짜고 짓는다.

4.1 그 도구를 다루는 방법

소프트웨어를 잘 만들 방법은 뭔가? 이 목표를 위해 컴퓨터 과학은 무엇을 밝혀냈는가?

두 줄기로 번졌다. 일하는 방도와 표현하는 방식에 대해

일하는 방도 = 알고리즘의 탐구

표현하는 방식 = 언어에 대한 탐구

4.2 푸는 솜씨, 알고리즘과 복잡도

알고리즘 어떤 것은 우주의 수명이 다할 때까지 기다려도 끝나지 않을 알고리즘도 있는 반면에 컴퓨터는 절대 풀 수 없는 멈춤 문제같은 것들도 있다.

알고리즘의 예 : 책 읽기, 자연수 n 이 주어졌을 때 1*2*3 * n 을 계산하기. 주머니의 숫자 중에서 제일 큰 숫자 찾기, 장보기 목록에 있는 모든 걸 장바구니에 담았는지 확인하기, 패스워드 해킹하기 등

알고리즘의 비용

참고링크는 그림에 :) 

현실적

현실적으로  의 알고리즘 비용이라면 현실적이라고 한다.  다항 알고리즘이 있는 P 클래스 문제라고 함

비현실적

비현실적으로 알고리즘의 실행비용(복잡도)이 상수 위에 지수로 입력 크기(n)가 되면 비현실적이라고 한다. 

NP 클래스 문제

운에 기대면 현실적인 비용으로 해결할 수 있는 문제들

예 : 주어진 지도 위의 모든 도시를 한번씩만 방문하는 경로가 있을까? (헤밀턴 경로) 예를 들어서 방문할 도시가 n개라고 하면 모든 경로들의 후보는 n! = n * (n-1) * ... *  1 개 만큼임. 

건너풀기

NP문제가 어려운 문제쪽에 있지만 쉬운 문제 진영에 바싹 다가서있는 문제들인데, 문제A 가 있으면 문제B를 풀고 그 알고리즘을 이용해서 A를 푸는 것을 말함.  (곱하기를 더하기로 풀 수 있듯이..)

통밥(heuristic) : 모든 것에 대한 답을 내놓지는 않지만 대부분의 입력에 대해서는 그럴듯한 답을 내놓음

추가적으로 무작위(randomization)도 있다.

알고리즘의 기본기

모조리 훑기 ( exhaustive search )

되돌아가기 ( backtracking )

나눠풀어 합치기 ( divide and conquer )

기억하며 풀기 ( dynamic programming ) (ex) 피보나치

질러놓고 다듬기 ( iterative improvement )

양자 알고리즘

양자 알고리즘 소개와 , 양자 인수분해 알고리즘 소개, 양자 탐색 알고리즘 소개

(양자 알고리즘 자세한 내용은 생략하기로..)

4.3 담는 그릇, 언어와 논리

한 언어가 표현할 수 있는 튜링기계를 어떤 언어는 표현할 수 없다면 표현력에 차이가 생김.

표현력이 완전한 프로그래밍 언어를 튜링완전하다고 함

자동번역

자연어 번역은 어려운데 프로그래밍 언어의 번역이 항상 가능한 이유.

컴퓨터 언어 사이의 자동번역은 두개의 단순한 원리를 사용함.

부품에서 전체로, 불변성질 유지

두 중력권

언어로서 표현력은 똑같다. 컴퓨터로 돌릴 수 있는 소프트웨어를 표현할 수 있는 언어들이다. 그 두 원조 프로그래밍 언어는 앞서 이야기한대로 튜링기계와 람다 계산법이다.

책에서 튜링기계와 람다계산법을 다시 한번 설명..

람다계산법에 대한 링크만 붙이자면 이것 ! 
http://www.aistudy.com/computer/lambda_calculus.htm

나머지 주제들

논리는 언어의 거울 : 증명하기와 프로그램 짜기  비교

추론의 징검다리 에서 추론하는 예시 설명

거울의 효능

프로그래머의 두 가지 불안 : 프로그램을 짜기 전, 프로그램을 짜고 난 뒤 어떻게 논리 거울의 도움으로 이 불안을 다독이는지 살펴보자

논리 거울, 짤 프로그램의 구도 잡기

겉 얼개 표현방식 : 타입에 대한 설명

논리 <-> 언어

증명 <-> 프로그램

증명은 어떤 논리식이 참임을 증명해간 경위다 <-> 프로그램은 어떤 데이터를 만드는 경위다

증명은 결론에 해당하는 참인 논리식이 있다 <-> 프로그램은 최종적으로 만드는 데이터의 종류가 있다

증명한 논리식 <-> 프로그램의 타입

타입으로 프로그램 잡아서, 결혼하기 사랑하기 아기만들기, 가족만들기라는 함수를 정의하고 여기에 이몽룡 성춘향이라는 남자여자 타입을 넣는 과정을 설명.. 

그리고 자동검진을 소개하면서 타입체킹을 설명하며 타입검진중에 타입을 자동으로 유추하는 것도 가능해지는 데 논리로부터 기술이전이 이뤄진 결과라고 함.

타입을 계기로 소개할만한 중심 개념이 하나 더 있는데 바로 요약(abstraction) 이다.

새롭게 부상하고 있는 세번째 프로그래밍 중력을 소개하는데, 바로 확률추론 프로그래밍(probabilistic programming) 이다.

우리가 일상에서 늘 하는 질문을 표현하는 프로그래밍.

"내 마음이 어떻길래 이러는 걸까?"

"이런 책들을 즐기는 나의 적성은 뭘까?"

우리가 일상적으로 미뤄 짐작하기를 과학적으로 자동화하기. 여러 원인 중에서 가장 가능성이 높은 원인을 자동으로 선별하기, 대량의 데이터가 이끄는 확률 추론 프로그래밍이라는 것이다.

---

05. 그 도구의 응용

(잠깐 이 챕터를 읽어보자면 컴퓨터의 미래 모습을 얘기한 듯함. )

컴퓨터 덕분에 인간 지능, 본능, 현실의 확장이 이뤄지고 있다.

5.1 인간 지능의 확장

점점 많은 분야에서 컴퓨터가 인간의 지능을 대체할 것이다. 수많은 지식의 등장과 구글, 체스챔피언인 딥블루 등등

지식표현

인간은 서술형 ( 언어 형태) 방정식형 (수학형태 ) 로 표현을 했는데 여기에 컴퓨터의 계산형(computational)지식표현방식이 추가 되었다.

물리학자들은 컴퓨터 프로그램을 통해서 새로운 실험 결과와 새로운 이론을 검증한다.  프로그램을 주고 받아서 검증함.

지식 생성

사람이 새로운 지식을 만들어내는 방법은 대체로 세가지 형태인데, 

디덕 ( deduction : 반드시 이끌기 )

앱덕 (abduction : 원인짐작 ) 

인덕 ( induction : 짐작해서 이끌기 )

기계학습은 앱덕과 인덕에 대한 것이다.

앱덕은 관찰로부터 원인을 가늠하는 것이고 여러 원인 중에 가장 가능성이 높은 원인을 찾는다.

인덕은 특수에서 보편으로 건너뛰는 것.  (-1,1),(1,1),(4,16), (6,36)을 보고서 이 함수는 제곱하는 함수가인가보다 하고 추측하는 것.. 이런 일반화과정은 앱덕이기도 함.

여기서부터는 기술 사례 설명이 나옴.

인간 유전자 지도, 뉴런지도. 구글링

그리고 구글의 설명을 예로 들면서 마르코프 체인이라는 개념을 소개

마르코프 체인 : https://sites.google.com/site/machlearnwiki/RBM/markov-chain

마르코프 체인을 통해서 전세계 모든 페이지에 대하여 마르코프 점화식을 내보면 가로세로 33억 * 33억개의 크기인데 

구글 컴퓨터가 매일 하는 계산이라고 함.. 구글을 사용하는 순간 슈퍼 컴퓨터를 사용하는 것이라고.. 

5.2 인간 본능의 확장

게임, SNS의 등장

클로드 섀넌의 정보이론으로 인하여 정보화시대에서 온전한 통신이 가능

통신의 주인공은 메시지가 가진 정보량이라고 주장.

당시의 통념은 통신의 한계는 전달하는 메시지와는 무관하다고하고 메시지 전달의 속도를 높이려면 통신채널의 주파수를 올리고 통신 중에 끼어들 수 있는 잡음을 극볼하려면 메시지 신호의 강도를 높이는 것으로 해결하려고 했으나

섀넌의 답은 통신의 한계는 그런 물리적인 데 있지 않고고 전달하려는 메시지가 정보량에 그 한계가 있다고 정의.

첫번째 정리 : 잡음이 없는 채널의 경우

전달하고자 하는 정보량이 H이고 채널 용량이 C라고 할 때,

메시지 전달은 최대 초당 C/H로 항상 가능하다

두번째 정리 : 전달 중에 잡음이 끼는 경우

정보량이 초당 H라고 하고 채널 용량은 초당 C라고 할 때

H <= C 이면 온전히 (잡음에 의한 생채기가 충분히 적어지도록) 전달할 수 있다

H > C 이면 잡음에 의한 생체기를 H-C미만으로 줄일 수는 없다

부가적인 (정보량을 줄이는) 방법을 통해 상처날 메시지들을 원상복구시키는 방법으로 메시지를 온전하게 전달하는 방법을 얘기함. 

메시지를 표현하는 (인코딩하는) 방법의 등장

오류 수정 코드

반복해서 전달 :  밥먹자->밥먹자밥먹자밥먹자

메시지를 길게 늘어뜨리기 : 027013 -> 영빵 두울 치일 영빵 하나 석삼

검산치 :467 을 보내면 합이 17이니까 17의 마지막 뒷자리 7을 더 붙여서, 4677 식으로 보낸다

5.3 인간 현실의 확장

시공간 공유

역발상

암호이야기

디피 헬만 열쇠교환의 이야기 https://ko.wikipedia.org/wiki/%EB%94%94%ED%94%BC-%ED%97%AC%EB%A8%BC_%ED%82%A4_%EA%B5%90%ED%99%98

완벽한 하인

암호화를 걸어놓은 데이터를 오직 보관만 하는 것이라면 문제가 없지만, 암호화를 걸어놓은 데이터로 무슨 일을 하고 싶을 때는 어떻게 해야할까? 암호화를 풀어야하는데 컴퓨터를 지켜보는 사람이 도난하진 않을까?

2009년 이런 일이 가능한 암호기술이 발표됨. 데이터가 암호가 걸린 상태에서 모든 일을 할 수 있는 암호기술

동형암호기술이라고 함

진품감정

RSA 암호방식의 소개

마지막 마치면서 단원에서 인용

컴퓨터 과학은

머리로 궁리하는 것에 대한 공부 (science of intelligence) 이고

그 응용은 인간 지능 / 본능 / 현실의 확장이다

이상 컴퓨터 과학이 여는 세계 / 이광근 교수님의 책 리뷰 끝 탕탕

좋은 책 잘 읽었습니다~