SNU =10100 =minusby by1000 ÄÄto0.03exÄÄto0.03exÄÄ=10100 =minusby by1000 Ç»to0.03exÇ»to0.03exÇ»=10100 =minusby by1000 ÅÍto0.0

Size: px

Start display at page:

Download "SNU =10100 =minusby by1000 ÄÄto0.03exÄÄto0.03exÄÄ=10100 =minusby by1000 Ç»to0.03exÇ»to0.03exÇ»=10100 =minusby by1000 ÅÍto0.0"

주연 공
5 years ago
Views:

1 차례 SNU 컴퓨터과학이여는 세계 (Computational Civilization) Part 년의축적 2 그도구의실현 Prof. Kwangkeun Yi Department of Computer Science & Engineering 3 소프트웨어, 지혜로짓는세계 4 응용 : 인간지능 / 본능 / 현실의확장 이전 이전 년의축적 년의축적 2 그도구의실현 2 그도구의실현 3 소프트웨어, 지혜로짓는세계 3 소프트웨어, 지혜로짓는세계 4 응용 : 인간지능 / 본능 / 현실의확장 4 응용 : 인간지능 / 본능 / 현실의확장

2 다음 소프트웨어 년의축적 2 그도구의실현 3 소프트웨어, 지혜로짓는세계 컴퓨터 (universal turing machine) 라는 마음의도구 를다루는방법 소프트웨어 (turing machine): 지혜와언어로짜고짓는 소프트웨어는무섭다 : 구체적인실천소프트웨어 4 응용 : 인간지능 / 본능 / 현실의확장 사람이 만들고 기계가 실행하고 소프트웨어를잘만들방법 개괄 알고리즘 (algorithm) 일하는방도푸는솜씨박차 언어 (language) 표현하는방식담는그릇고삐 푸는솜씨, 알고리즘과복잡도 컴퓨터문제풀이법비용의계층컴퓨터로풀수있는쉬운문제와어려운문제의경계 담는그릇, 언어와논리 언어의계층. 번역과실행 프로그래밍언어의두개의중력 프로그래밍 = 논리증명

3 알고리즘 알고리즘은컴퓨터로돌릴수있는문제푸는방도 하나의소프트웨어 = 하나의튜링기계 소프트웨어 ( 튜링기계 ) 는어떤문제를푸는것 컴퓨터는소프트웨어를실행 = 문제풀이를자동으로 진행 묻게된다 : 더좋은 ( 싸고빠른 ) 방법? 있다면얼마나더좋은가? 더좋기는불가능한가? 경계는어디인가? 현실적인비용으로해결가능한문제들 알고리즘예 책읽기 그렇지않은문제들 자연수 n( 2) 이주어졌을때 1 2 n 을 계산하기 주머니의숫자중에서제일큰숫자를찾기 장보기목록에있는모든걸장바구니에담았는지 확인하기 그녀가마음속에품은자연수알아맞추기. 1 부터 n 사이에있다. 그녀는예 / 아니오만답할수있다. a n = a a }{{} n 계산하기 뒤죽박죽인숫자를크기순서로나열하기 패스워드해킹하기 자연수인수분해하기 알고리즘복잡도 복잡도증가속도 시간과메모리소모량 입력크기의함수로 결국어떻게되는지 (asymptotic complexity) n n 2 2 n n! , , , ,024 3,628, ,048,576 2,432,902,008,176,640, ,073,741,824 너무크다! > 10 39

4 알고리즘복잡도표기법 O(f(n)) ( 입력크기 n) = f(n) 의상수배보다작다는뜻 복잡도 O(1) O(log n) O(n) O(n 2 ) 알고리즘스텝횟수가 상수이면 log n + 10, 9871 log n 등이면 n + 10, 999n + 9, 2016n 18 등이면 999n 2 + 9, 2016n n 18 등이면 복잡도 n 이 2 배가되면일컫기를 O(1) 변함없다상수 constant O(log n) 약간의상수만큼커진다로그 logarithmic O(n) 2 배커진다선형 linear O(n log n) 2 배보다약간더커진다엔로그엔 n log n O(n 2 ) 4 배커진다제곱배 quadratic O(n k ) ( 상수 k) 2 k 배커진다 k 승배, 다항 polynomial O(k n ) ( 상수 k > 1) k n 배커진다기하급수배 exponential 알고리즘복잡도예 책읽기 : O(n) O(n!) n n 배정도커진다 2 계승배 factorial 자연수 n( 2) 이주어졌을때 1 2 n 을 계산하기 : O(n) 주머니의숫자중에서제일큰숫자를찾기 : O(n) 장보기목록에있는모든걸장바구니에담았는지 확인하기 : O(n 2 ) 그녀가마음속에품은자연수알아맞추기. 1 부터 n 사이에있다. 그녀는예 / 아니오만답할수있다 : O(n), O(log 2 n) a n = a a }{{} n 계산하기 : O(n), O(log 2 n) 뒤죽박죽인숫자를크기순서로나열하기 : O(n 2 ), O(n log 2 n) n 자리자연수패스워드해킹하기 : O(10 n ) n 자리자연수인수분해하기 : O(10 n ) 현실적 (n k ) vs 비현실적 (k n ) P 클래스문제 그문제를푸는알고리즘의복잡도가 O(n k ) 인문제 n: 입력의크기, k: 상수 O(n k ): 컴퓨터성능이곱하기로빨라지면, 같은시간에처리할수있는입력의크기도곱하기로는다. O(k n ): 컴퓨터성능이곱하기로빨라져도, 같은시간에처리할수있는입력의크기는더하기로는다. k n 의무시무시함 : 초 > 우주의나이 알고리즘복잡도 : O(log n), O(n log n), O(n), O(n 1.5 ), O(n 28 ), 현실적인비용 으로컴퓨터가풀수있는문제실제로는 현실적 이려면 : O(n 3 ) 이하여야 일단 O(n k ) 가찾아졌다면, 우리는늘 k를 3이하로줄일수있었다.

컴퓨터로 풀려고 할 때의 질문 컴퓨터로(자동으로) 풀기 어려운 문제인지 아닌지를 미리 알고 싶다 컴퓨터에게 쉽고 어려운 문제의 경계? 쉬운 문제: P 클래스 문제. 어려운 문제: P 클래스 바깥의 문제. 어려운 문제인지를 판별하는 방법? 알고리즘 찾아나선다 P 알고리즘이 찾아졌다면 쉬운 문제다 P 알고리즘을 못찾겠다면? 계속 열심히 찾으면 나올까?

5 컴퓨터로 풀려고 할 때의 질문 컴퓨터로(자동으로) 풀기 어려운 문제인지 아닌지를 미리 알고 싶다 컴퓨터에게 쉽고 어려운 문제의 경계? 쉬운 문제: P 클래스 문제. 어려운 문제: P 클래스 바깥의 문제. 어려운 문제인지를 판별하는 방법? 알고리즘 찾아나선다 P 알고리즘이 찾아졌다면 쉬운 문제다 P 알고리즘을 못찾겠다면? 계속 열심히 찾으면 나올까? 아예 그런 알고리즘은 없는 것일까? 어려운 문제인지 판별하는 방법? 경계더듬기: P 클래스 vs N P 클래스 N P 클래스 문제의 정의: 어려운 문제 = P 클래스 바깥의 문제 P 바깥의 문제가 존재하나? 그 쪽 경계로 가까이 가보자. 예-아니오 문제(decision problem)이고 예 라는 답을 운에 기대어 현실적인 비용non-deterministic polynomial 으로 할 수 있으면. 그래서, 이렇게도 정의한다: 예 라고 답한 근거를 받아서 그 근거가 맞는지를 현실적인 비용에 확인할 수 있는 문제 답을 받아서 = 운에 기대어 이므로 경계의 문제 = N P지만 P인지는 아직 모르겠는

6 N P 문제의예 아주흔하다 주어진지도위의모든도시들을한번씩만방문하는경로가있을까? ( 해밀턴경로 Hamiltonian path ) 주어진예산으로주어진지도의도시들을다방문하고돌아올수있을까? 주어진부울식 boolean formula 이참이되게할수있을까? 주어진자연수를인수분해하라 1차원의아미노산실을접어서 3차원의단백질구조물을만들라. 단, 만들어진구조를유지하는데필요한에너지가어느이하여야한다 1000만관객을넘기는영화를제작하라. 제작중에 n번디자인선택을해야한다 오리무중 : P N P? 아직아무도모름 정말어려운문제인지가아리송한경계의문제들 (N P) 이것들이혹시쉬운문제 (P) 는아닐까? 현재의디지털컴퓨터 ( 튜링기계 ) 로는아마도 P N P 라고추측 P N P라면 어려운문제의시작 / 경계가 N P이지않을까 아슬아슬하므로 : 운에기대기만하면 P로넘어가지만 P는될수없다니 현실적인알고리즘은없다고판정하는방법 (1/3) N P 문제들의온순한성질때문에가능 : N P 문제중제일어려운문제가존재한다! Cook 1971년 : 모든 N P 문제중에서부울식만족시키기문제 satisfiability problem (SAT) 가제일어렵다 모든 N P 문제를다항비용으로부울식만족시키기문제 satisfiability problem 로각색해서건너풀수있다 현실적인알고리즘은없다고판정하는방법 (2/3) 지렛대 건너풀기 problem reduction 문제 A 를문제 B 로건너풀수있다 reducible = B 를풀면 A 가풀린다 예 ) 곱하기 를 더하기 로 예 ) k- 번째로큰수찾기 를 정열 로 B 는 A 보다어렵다 ( 정확히는, B 는적어도 A 만큼 어렵다 )

7 현실적인알고리즘은없다고판정하는방법 (3/3) N P 문제들중에서제일어려운문제가존재하므로 맞닥뜨린문제가그런 왕초 문제만큼어렵다면 그리고 P N P가사실이라면 ( 그렇다고추측 ) 즉, P 바깥에문제들이존재한다면 맞닥뜨린문제는 P 바깥에있는것이확실하다 즉, 맞닥뜨린문제는컴퓨터로풀수있지만현실적인비용으로는불가능하다주의 : 이방법은가정 P N P 아래에서믿을만 sound 하지만완전하진않다. not complete 어쩔것인가? 주변의흔한문제들이 N P 문제들이다, 컴퓨터로풀고싶다. 알고리즘의조건 = 모든입력에정확한답을내기 조건을느슨하게하면어떨까? 모든입력 을 흔한입력 으로 정답 을 적당한답 으로 동원하는기법 통밥heuristic : 맞을듯한직관. 선택기로에서기대어 지체없이진행 무작위randomization : 통밥의낭패를막는데유효 통밥과무작위 컴퓨터로불가능한문제들 아이러니 / 미스테리 통밥 heuristic 과무작위 randomization 가잘작동 흔한경우에정답에가까운답을내놓는다 ( 통밥 ) 드문경우에만낭패 ( 통밥 ) 왜그럴까? 비현실적인비용의덫에걸리지않는페인팅모션 ( 무작위 ) 알고리즘의복잡도가널뛰는것을안정시킨다 ( 무작위 ) 당연히존재하겠지요 명확히존재 : 예 ) 멈춤문제 halting problem 무수히많다 문제 1개 = 함수 1개 ( 자연수에서예-아니오로가는 ) ( 입력과답의짝을자연수하나로표현가능 ) 그런함수의개수는 2 N 위의개수는자연수의개수 N (sw의개수 ) 보다 무한히많다

8 알고리즘 만들때의 흔한 기본기 모조리 훑기exhaustive search 인구조사 기억하며 풀기dynamic programming 미로찾기: 모든 경우를 차례로하면서 나눠풀어 합치기divide-and-conquer 최대공약수: 2, 3, 4, 로 나눠보기 되돌아가기backtracking 양자 컴퓨팅(quantum computing) 피보나치 수열 값 양자현상을 이용 중첩superposition 얽힘entanglement 확률진폭probability amplitude 양자컴퓨터의 성질 못함 질러놓고 다듬기iterative improvement 로봇-대피소 짝짖기 (일단 짝짖고 겹친경로 바꾸기) 정열 (일단 줄세우고 어긋난 이웃 바꾸기) 양자 알고리즘(quantum algorithm) 튜링기계와 동일: 기계적인 계산의 한계를 넓히지는 단, 훨씬 빨리(시간) 훨씬 알뜰하게(메모리) 계산 양자 인수분해(quantum factorization) 알고리즘 1994 Shor. 수학에서 알려진 사실을 이용: 자연수 N 의 인 근본적으로 확률 알고리즘probabilistic algorithm : 높은 확률 로 답이 나타난다 데이터를 중첩시켜 연산 효율을 높임 답이 다른 후보들과 양자안에 중첩되어 있음 알고리즘 연산 = 답이 매우 높은 확률진폭을 가지도록 하기 연산을 끝내고 양자를 관찰하면 매우 높은 확률로 답이 나타남 수분해 1. N 보다 작은 임의의 자연수 r을 선택 2. GCD(r, N )이 1이 아니면 N 의 인수. 아니면, 3. 아래 숫자열을 계산 r1 mod N, r2 mod N, r3 mod N, 4. 위 숫자열에는 주기 p가 존재한다. 5. GCD(N, rp/2 + 1)와 GCD(N, rp/2 1)가 매우 큰 확률로 1이 아니다(N 의 인수가 된다). (p가 홀수면 다시 반복) 이 과정을 양자 알고리즘으로 옮기자.

9 양자현상을 이용해서 구현 다항시간에 가능 m z } { 1. 입력 큐빗: m개의 큐빗qbit 에 0 1(1) 부터 m z } { 1 1(2m 1)까지 같은 확률로 중첩시킴 2. 출력 큐빗: 입력큐빗과 동일하게 중첩시킴 3. 입출력 큐빗에 서로 해당하는 숫자를 얽혀놓음 양자 탐색(quantum search) 알고리즘 1996 Grove. 데이터가 아무렇게나 널려있는 경우 O( n)에 가능 i 4. 출력 큐빗에 r mod N 을 계산하는 레이저를 쏜다. 번호에 해당하는 데이터라고 하자 i는 m개의 큐빗에 중첩되어 있는 1,, 2m 1. (이만큼의 숫자열 계산이 중첩덕분에 한꺼번에 가능) 5. 출력 큐빗을 관찰; 입력 큐빗에는 관찰한 결과를 데이터들과 일렬번호들은 두 양자에 따로 중첩해 넣는다 (n개의 데이터는 log2 n개의 큐빗에 중첩해서 저장가능) 만들었던 i들만 남는다 6. 숫자열 주기 p = 입력 큐빗에 남은 것들의 차이. 이를 감지하는 레이저를 쏜다 데이터는 일렬번호가 있고, 찾고자 하는 것은 주어진 데이터와 해당 일렬번호를 두 양자사이에 얽혀놓는다 준비 끝 양자 탐색 본 과정 아래 과정을 O( n)번 반복하고 관찰하면 매우 높은 확률로 답이 나타남 (n의 경우마다 예를들어 n 1번, 10 n + 4번 등을 반복하면 충분하다는 뜻) 1. 일렬번호가 중첩되있는 큐빗에 레이저 를 쏴서, 찾고자 하는 번호만 그 확률진폭probability amplitude 을 반대 방향으로 뒤집는다 2. 그렇게 변한 확률진폭의 평균을 구한 후, (대략적으로) 평균의 두배에서 각 확률진폭을 다시 빼는 레이저 를 쏜다 3. 그러면 찾고자 하는 일렬번호의 확률진폭은 증가하고 다른 것은 줄어든다

10 언어(language) 소프트웨어: 사람이 만들고 컴퓨터가 실행 SW의 표현 튜링기계 부품들(유한개의 상태, 유한개의 심볼, 큰 간격 소프트웨어: 사람이 만들고 컴퓨터가 실행 큰 간격: 컴퓨터가 이해하는 언어 vs 사람이 편히쓰는 언 어 유한개의 규칙표)로 폰노이만 기계어로 인텔(x86) 기계어로 보다 상위의 언어들로 SW를 표현하는 언어: 프로그래밍 언어 (programming language) 튜링기계의 규칙표 혹은 기계어는 너무 하위의 언어 나날이 복잡해지는 소프트웨어를 표현하는 컴퓨터가 이해하는 언어 (기계어) Mac: PowerPC 기계어 PC: Pentium 기계어 Galaxy: Arm 기계어 iphone: Arm 기계어 모두 튜링-완전turing-complete 그러나 사람에겐 너무 원시적 그릇으로는 무리 분자배열로 짜장면을 표현하는 셈 해결책 Coq 언어계층과 자동번역 언어의 계층: 상위의 상위의 언어를 고안 그 언어들 사이의 번역사슬 번역사슬의 맨 위는 사람에게 편한 상위의 언어 번역사슬의 맨 아래는 기계에게 편한 기계어

11 ML Scala Python Java

12 C x86 Dalvik 번역기(compiler) 출발어 L, 도착어 L L로 짜여진 모든 프로그램을 같은 일을 하는 L 프로그램으로 번역 컴퓨터 언어들 사이의 번역은 항상 자동으로 가능 단어의 뜻은 하나로 고정되 있다 사용되는 정황에 따라 달라지지 않는다 번역의 원리: 조립식compositional 으로 불변성질invariant 유지하기 전체의 번역 결과는 부분의 번역결과를 가지고 조립 조합이 쉽도록: 각 결과는 같은 조건(invariant)을 만족

13 자동번역원리의예 출발어 E ::= n E + E E E E 도착어 C ::= push n add sub mult C.C 해석실행 (interpretation) 컴퓨터가소프트웨어를실행 컴퓨터를보편만능이게하는핵심아이디어 보편만능의튜링기계 : 테입에표현된 17개심볼의문자열 ( 프로그램, 소프트웨어, 튜링기계 ) 을해석실행 해석실행 : 일상에서우리가늘하는 ( 1+2 ) 컴퓨터는해석실행기 interpreter 전기회로로구현된 ( 폰노이만기계, Pentium, Arm) 실행기 번역사슬의맨아래언어 ( 기계어 ) 의실행기 메모리에표현된기계어프로그램을해석실행소프트웨어구현된해석실행기 interpreter 도가능 해석실행기를컴퓨터가해석실행 ( 해석실행이두겹으로겹침 ) 언어정글 프로그래밍언어의두개의뿌리 튜링기계 turing machine (Alan Turing) 상위로상위로 : 기계에명령하는언어 C, Java, C++, C#, JavaScript, Objective C, Python, PHP, Scala, Swift, Rust 등 람다계산법 lambda calculus (Alonzo Church) 상위로상위로 : 값을계산하는언어 ML, OCaml, Haskell, F#, Lisp, Clojure, Rua, Python, Scala, C++14 등 최신언어들은두방식모두를지원 기계의중력 vs 람다의중력 기계의중력 명령하며기계상태를변화시키는주문 요리법, 장보기목록 a 0 람다의중력 b read a a+b b b+1 기계는없다. 값을계산하는식. 산수스타일 초등학교때부터보아온산수언어. 10 n=1 n2 P Q 이고 P Q 라고하자. 그러면 P c Q = U 이고 P Q c = 이고 P Q c U 이다. 프로그래밍언어의요건 수학언어의요건 다른기원은다른방식의생각을유도하는 프로그래밍언어를탄생시킴

14 람다계산법 (lambda calculus)(1/2) 람다계산법 (lambda calculus) (2/2) x 구슬 ( 색깔대신이름 x) λx.e 눈사람 ( 색깔은 x) E E 나란히있기 3 = λs.(λz. s(s(s z))) }{{} 3 + n m = λs.(λz.ns(msz)) n m = λs.(λz.n(ms)z) T = λx.(λy.x) F = λx.(λy.y) and a b = a b F zero? n = n (λx.f ) T repeat E = (λf.(λx.f(xx))(λx.f(xx))) E 논리는언어의거울 논리추론의징검다리 ( 람다중력권 ) 컴퓨터세계에서언어와논리는동전의양면일뿐, 같은것이다증명하기 프로그램짜기 A B A B A B A A B B 논리적인비약없이새로운사실을확인해가는과정. 참인사실혹은사실이라고가정한것들로부터시작. 공짜없이새로운데이터를만들어가는과정. 기초적인데이터에서부터시작. 기초적인데이터는정수, 문자, 참거짓등. Ạ. B A B A B B A 사실을기반으로해서새로운사실들을만듬. 만들어가는과정은근거없는건너뛰기없이, 논리적으로누구나수긍하는추론의징검다리를밟고가는과정만있다. 이미만든데이터를가지고새로운데이터들을만듬. 새데이터를만드는과정은공짜가없다. 사용하는프로그래밍언어에서제공하는프로그램조립방식을써서만든다. A A B A B A A B Ạ. C C Ḅ. C

15 논리증명나무 거울 : 증명하기 = 프로그램짜기 (1/2) A B A B 데이터뭉치만들기 (A B) (A C) A B A (A B) (A C) A C B C B C A (B C) (A B) (A C) (A (B C)) A A B A A B B 데이터뭉치사용하기 Ạ. B A B 함수만들기 A B A B 함수사용하기 거울 : 증명하기 = 프로그램짜기 (2/2) A A B A B A 데이터뭉뚱그리기 거울의효능 A B Ạ. C Ḅ. C C 뭉뚱그린데이터사용하기 A 함수의인자를사용하기 프로그램짜기전 : 짤프로그램의구도잡기 타입type 이라는언어로겉얼개를표현참논리식 타입 프로그램짜고나서 : 짠프로그램이무난히작동할지살피기 무난히작동 = 타입에맞게돈다 논리분야의타입이활용되던모습 ( 년대) 그렇다면프로그램에서도가능하겠지 (1970-현재)

16 짤프로그램의구도잡기 타입으로 ( 보통명사 로 ) 프로그램얼개를표현 결혼하기 : 남자 여자 부부 사랑하기 : 부부 사랑 아기만들기 : 부부 사랑 아기 가족만들기 : 남자 여자 가족 가족만들기 (x,y) = let couple = 결혼하기 (x,y) ( 남자 와 여자 가 부부 를만들고 ) let love = 사랑하기 (couple) ( 부부 가 사랑 을만들고 ) let baby = 아기만들기 (couple, love) ( 부부 가 사랑 으로 아기 를만들고 ) 짠프로그램이무난히작동할지검진하기 (1/2) 프로그래머의불안 기획한얼개에따라잘메꾼걸까? 그래서제대로작동하는프로그램일까? 만페이지가넘는, 대하소설보다복잡한흐름 프로그램실수는고스란히드러날것이다 in (couple, baby) ( 그런 부부 와 아기 가 가족 이다 ) 프로그램검진 vs 다른분야 만든것 프로그램 기계 / 건물 / 약물디자인 실행기 컴퓨터 자연 바램 실행에대해미리확인 작동에대해미리확인 안심 생각대로돌것이다 생각대로작동할것이다 확인도구 컴퓨터과학의성과 자연과학의성과 짠프로그램이무난히작동할지검진하기 (2/2) 자동검진이가능 과거 : 개인의기예에의존하던프로그램의완성도 현재, 미래 : 누구나의기술로한발전진 자동검진 컴퓨터는더이상맹목적이지않다 프로그램을검진해서통과한것만실행 f(x) = x+1 sum(f) = f(0)+f(1) 무게 ( 춘향이 )+ 무게 ( 그네 )

요약(abstraction)의 그물 SW는 복잡하다 컴퓨터과학에서 늘 동원하는 지혜: 모두 포섭하면서 간 단히

너무 복잡: 기하급수로 커지며 속수무책combinatorial explosion 다양한 수준의 요약을 동원:

SW는 복잡하다 less-382(23,822 LoC) 자연물 만큼 복잡 포유류 뇌의 1만개 뉴런의 넷트웍,

17 요약(abstraction)의 그물 SW는 복잡하다 컴퓨터과학에서 늘 동원하는 지혜: 모두 포섭하면서 간 단히 프로그램 검진에서도: 요약 모든 디테일을 보는 것은 비현실적 외부입력 가짓수가 너무 많고, 만들어지는 현상이 너무 복잡: 기하급수로 커지며 속수무책combinatorial explosion 다양한 수준의 요약을 동원: 10 무게(춘향이) + 8 타입으로 요약: 정수 양수음수로 요약: 양수 구간으로 요약: 100과 3000사이 SW는 복잡하다 less-382(23,822 LoC) 자연물 만큼 복잡 포유류 뇌의 1만개 뉴런의 넷트웍, Ecole Polytechnique Fe de rale de Lausanne, Blue Brain Project, 2008

SW 제작의어려움 고백 : 컴퓨터분야는아직미숙합니다 프로그램의규모와복잡도가점점커짐 프로그램복잡성의증가속도 >> hw 성능의성장속도 sw는가스다. Software is gas.

Newton, Galileo, Curie, 와같이살고있다. 현재의기술수준 : 걸음마 3 발짝, 초보수준 컴퓨터분야발전속도가빠르다?

18 SW 제작의어려움 고백 : 컴퓨터분야는아직미숙합니다 프로그램의규모와복잡도가점점커짐 프로그램복잡성의증가속도 >> hw 성능의성장속도 sw는가스다. Software is gas. 프로그램은기계가자동으로실행함 분야의역사 겨우 5-60 년 기계는우리가바라는바를실행하지않음 기계는 sw 에적힌바를실행할뿐 그래서 장보기 = 우유 1 리터, 신라면 4 봉지, 그리고쌀과자두사오기. 미숙하기때문에 = 기회가많다. 모든상황을고려해야 사소한실수가없어야 프로그램의실행을 미리완벽히알기 가어려움 자동으로는불가능 : 증명됨 (1936년, Alan Turing) 사람이확인해가야 : 다양한도구로비용절감 미숙하기때문에 = 지금 Newton, Galileo, Curie, 와같이살고있다. 현재의기술수준 : 걸음마 3 발짝, 초보수준 컴퓨터분야발전속도가빠르다? (1/3) 컴퓨터속도 : 10 7 배 /50 년발전 컴퓨터분야발전속도가빠르다? (2/3) 다른분야와얼추비슷 : 배발전 /100년 에너지분야 : 10 7 배 /100년발전 10 1 hp/hr ( 하인 ) hp/hr ( 원전 1GW/hr) 10 3 flops/cpu ENAC(1945) flops/core BM Sequoia(2010) 교통분야 : 10 9 배 /100 년발전 10 2 j ( 가마 ) j (Delta )

19 컴퓨터분야발전속도가빠르다? (3/3) 하드웨어 : 다른분야와비슷한발전 소프트웨어 : 많이미개함 크기만증가 : 휴대폰 100만줄아래아한글 200만줄스마트폰 1000만줄윈도우 3000만줄 소프트웨어 : 다른분야가이루어놓은것을아직이루지못했슴 다른분야의현재수준 제대로작동할지를미리검증할수없는기계설계는없다. 제대로작동할지를미리검증할수없는회로설계는없다. 제대로작동할지를미리검증할수없는공장설계는없다. 제대로서있을지를미리검증할수없는건축설계는없다. 뉴튼방정식, 미적분방정식, 통계역학, 무슨무슨방정식... 무엇일까? 모든기술의질문 소프트웨어분야에서의이질문 우리가만든것이우리가의도한대로움직인다는것을어떻게미리확인할수있는가? 작성한 SW의오류를자동으로미리모두찾아주거나, 없으면없다고확인해주는기술들은있는가? ( 사실, 일상에서도잦은질문과답 : 입학시험, 입사시험, 궁합, 클럽 관리 ) 그래서, SW 의오류때문에발생하는 개인 / 기업 / 국가 / 사회적비용을 절감시켜주는기술들은있는가?

쌀과 자두 만약에: 우유 1리터 1병만 있으면? 쌀과 자두? 쌀과자 두?

20 프로그램 검진: 타입오류를 넘어서 SW 오류의 예 SW 오류(bug) 어머니가 전해준 슈퍼마켓 심부름 목록(프로그램) 소프트웨어에 있는 오류 소프트웨어가 생각대로 실행되지 않는 것 1. 우유 1리터 2병 사람이 소프트웨어를 잘못 만들었기 때문 2. 우유가 없으면 오렌지쥬스 1리터 3병 천재지변이 아님 3. 우유가 있으면 식빵 500그람 1봉 4. 쌀과 자두 만약에: 우유 1리터 1병만 있으면? 쌀과 자두? 쌀과자 두? SW 오류의 문제 SW 오류: 사람이 손으로 손쉽게 잡을 수 없다 살다가 병이든다 사회적 비용 해결책 = 경제적기회 SW로 동작하는 제품이 고장난다 엄청나게 커지고 복잡해 진 소프트웨어 새로운 컴퓨팅 환경: 지구 = 컴퓨터 전지구적 네트웍을 타고 불특정 다수의 코드가 내게로 온다(스마트폰 게임/apps) 사회적 비용 자동 기술이 필요 해결책 = 경제적기회

21 SW 오류 검증 기술: 1세대 SW 오류 검증 기술: 2세대 타입 검증(type checking): 90년대에 완성. 문법 검증기: 70년대에 완성된 기술. lexical analyzer & (30년간 프로그래밍언어 분야의 대표 성과) parser 오류 = 생긴것은 멀쩡한데, 잘못된 값이 계산에 흘러드는 오류 = 소프트웨어의 생김새가 틀린 것 1. 우유 1리터 2병 경우 1. 우유를 담은 얼음을 가스 불위에 올려놓고 2. 우유가 없으면 오렌지ㅈㅅ 1리터 3병 데운다 3. 있으면 빵식 우유가 500그람 1봉 2. 식빵을 유리접시에 담고 방아로 빻는다 4. 쌀과 자두 3. 2의 접시에 1의 우유를 튀긴다 4. 남자와 소나무를 결혼시킨다 SW 오류 검증 기술: 3세대 데이터의 중력 프로그램분석검증: 아직 미완성 충분히 많아지는 데이터, 충분히 저렴해지는 컴퓨터 (static analysis, verification, model checking,...) 새로운 프로그래밍 중력 오류 = 생긴것도 멀쩡하고 타입도 맞지만, 바라는 바가 아 확률추론 프로그래밍probabilistic programming 닌것 앱덕abduction 하는 프로그램짜기 오류 = 필요한 조건을 만족시킬 수 없는 경우 프로그램 = 1. 우유를 담은 냄비를 가스 불위에 데운다 인과관계 A = B 관찰한 데이터 B 2. 식빵을 스텐접시에 담고 방아로 빻는다 실행결과 = 짐작하는 원인 A 3. 남자1명과 여자1명을 결혼 시킨다 일상 추측을 자동으로/과학적으로 가스불이 포항제철 용광로가 된다면? 시험점수에서 실력추측 방아가 현대중공업의 프레스가 된다면? 좋아하는 영화에서 성격추측, 등등 남녀 나이의 차가 100살이된다면? 주의: 완전하지 못한 인과관계 & 관찰못한 데이터

22 다음 년의축적 2 그도구의실현 3 소프트웨어, 지혜로짓는세계 4 응용 : 인간지능 / 본능 / 현실의확장

SNU =10100 =minusby by1000 ÄÄto0.03exÄÄto0.03exÄÄ=10100 =minusby by1000 Ç»to0.03exÇ»to0.03exÇ»=10100 =minusby by1000 ÅÍto0.0

SNU =10100 =minusby by1000 ÄÄto0.03exÄÄto0.03exÄÄ=10100 =minusby by1000 Ç»to0.03exÇ»to0.03exÇ»=10100 =minusby by1000 ÅÍto0.0 차례 SNU 046.016 컴퓨터과학이여는 세계 (Computational Civilization) Part 1 400 년의축적 2 그도구의실현 Prof. Kwangkeun Yi School of Computer Science & Engineering 3 SW, 그궁리의세계 4 응용 : 인간지능 / 본능 / 현실의확장 이전 1 400 년의축적 2 그도구의실현