SNU 046.016 컴퓨터과학이여는 세계 (Computational Civilization) Part III Prof. Kwangkeun Yi School of Computer Science & Engineering 차례 1 400 년의축적 2 그도구의실현 3 SW, 그궁리의세계 4 응용 : 인간지능 / 본능 / 현실의확장
이전 1 400 년의축적 2 그도구의실현 3 SW, 그궁리의세계 4 응용 : 인간지능 / 본능 / 현실의확장
다음 1 400 년의축적 2 그도구의실현 3 SW, 그궁리의세계 4 응용 : 인간지능 / 본능 / 현실의확장
소프트웨어 Software(SW) 하나의소프트웨어 = 하나의튜링기계 하나의컴퓨터 ( 보편만능의튜링기계 Universal TM) 는임의의 SW( 튜링기계 ) 를메모리에싣고그 SW를실행 ( 그튜링기계를모사 ) 소프트웨어, 그궁리의세계 언어 (language & logic). 궁리를표현하는언어와논리. 다양한계층의프로그래밍언어. 언어들사이의자동 번역. 소프트웨어기술의발전과정추적. 알고리즘 (algorithm & complexity) 같은계산을하는다양한방법. 제일효율적인 방법의탐구. 불가능한계산문제의존재. 가능하지만계산비용이 너무큰문제. 복잡성의계층.
소프트웨어, 그궁리의세계 : Part I 언어 (language & logic) 언어 (language & logic) SW의표현 튜링기계부품들 ( 유한개의상태, 유한개의심볼, 유한개의규칙표 ) 로 폰노이만기계어로인텔 (x86) 기계어로보다상위의언어들로 SW를표현하는언어. 프로그래밍언어 (programming language) 하위의언어 : 기계어 ( 튜링기계, 폰노이만기계, 인텔기계등등 ) 상위의언어 : C, Fortran, Java, JavaScript, Phython, Scala, ML, Haskell 등등 Turing-complete : 그언어로모든기계적계산을 표현가능하면
제일하위의기계어 모든컴퓨터의 CPU + 메모리는모두보편만능 튜링기계 ( 메모리가무한하다면 ) 다른점 : 성능과기계어 Mac: PowerPC 기계어 PC: Pentium 기계어 Galaxy: Arm 기계어 iphone: Arm 기계어 모두 Turing-complete 언어의계층과번역 계층예 ) Pentium 기계어 < T < C < ML 실행기 (interpreter) 와번역기 (compiler) 실행기란 번역기란 L로짜여진모든프로그램을자동실행 Pentium기계어프로그램의실행기는 Pentium chip 실행기를 SW로구성할수도있다 L로짜여진모든프로그램을같은일을하는 L 프로그램으로자동번역 번역기원리 귀납적으로전체의결과는부분의결과를가지고조합 조합이쉽도록 : 각결과는같은조건 (invariant) 을 만족하도록
번역기원리의예 E ::= n E + E E E E 에서 C ::= push n add sub mult C.C 상위의언어 L ( 가상 ) pgm ::= ftn + E ftn ::= fx = E 재귀함수 E ::= n integer x variable true false E bop E if E then E else E branch () (E, E) E.1 E.2 pair & select fe ftn call read write E bop ::=
프로그램을연습해보자 함수정의 sum n = fac n = gcd (n,m) = append (a, b) = compile E = SW 는복잡하다
SW는 복잡하다 less-382(23,822 LoC) c Kwangkeun Yi 자연물 만큼 복잡 포유류 뇌의 1만개 뉴런의 넷트웍, Ecole Polytechnique Fe de rale de Lausanne, Blue Brain Project, 2008 c Kwangkeun Yi
SW 제작의어려움 프로그램의규모와복잡도가점점커짐 프로그램복잡성의증가속도 >> hw 성능의성장속도 sw는가스다. Software is gas. 프로그램은기계가자동으로실행함 기계는우리가바라는바를실행하지않음 기계는 sw 에적힌바를실행할뿐 장보기 = 우유 1 리터, 신라면 4 봉지, 그리고쌀과자두사오기. 모든상황을고려해야 사소한실수가없어야 프로그램의실행을 미리완벽히알기 가어려움 자동으로는불가능 : 증명됨 (1936년, Alan Turing) 사람이확인해가야 : 다양한도구로비용절감 현재의기술수준 : 걸음마 3발짝, 초보수준 고백 : 컴퓨터분야는아직미숙합니다 분야의역사 겨우 5-60 년 그래서 미숙하기때문에 = 기회가많다. 미숙하기때문에 = 지금 Newton, Galileo, Curie, 와같이살고있다.
컴퓨터분야발전속도가빠르다? (1/3) 컴퓨터속도 : 10 7 배 /50 년발전 10 3 flops/cpu ENIAC(1945) 2 10 10 flops/core IBM Sequoia(2010) 컴퓨터분야발전속도가빠르다? (2/3) 다른분야와얼추비슷 : 10 7 10 9 배발전 /100년 에너지분야 : 10 7 배 /100년발전 10 1 hp/hr ( 하인 ) 1.35 10 6 hp/hr ( 원전 1GW/hr) 교통분야 : 10 9 배 /100 년발전 10 2 j ( 가마 ) 10 11 j (Delta II)
컴퓨터분야발전속도가빠르다? (3/3) 하드웨어 : 다른분야와비슷한발전 소프트웨어 : 많이미개함 크기만증가 : 휴대폰 100만줄아래아한글 200만줄스마트폰 1000만줄윈도우 3000만줄 소프트웨어 : 다른분야가이루어놓은것을아직이루지못했슴무엇일까? 다른분야의현재수준 제대로작동할지를미리검증할수없는기계설계는없다. 제대로작동할지를미리검증할수없는회로설계는없다. 제대로작동할지를미리검증할수없는공장설계는없다. 제대로서있을지를미리검증할수없는건축설계는없다. 뉴튼방정식, 미적분방정식, 통계역학, 무슨무슨방정식...
모든기술의질문 우리가만든것이우리가의도한대로움직인다는것을어떻게미리확인할수있는가? ( 사실, 일상에서도잦은질문과답 : 입학시험, 입사시험, 궁합, 클럽 관리 ) 소프트웨어분야에서의이질문 작성한 SW의오류를자동으로미리모두찾아주거나, 없으면없다고확인해주는기술들은있는가? 그래서, SW 의오류때문에발생하는 개인 / 기업 / 국가 / 사회적비용을 절감시켜주는기술들은있는가?
SW 오류(bug) I 소프트웨어에 있는 오류 I 소프트웨어가 생각대로 실행되지 않는 것 I 사람이 소프트웨어를 잘못 만들었기 때문 I 천재지변이 아님 c Kwangkeun Yi SW 오류의 예 어머니가 전해준 슈퍼마켓 심부름 목록(프로그램) 1. 우유 1리터 2병 2. 우유가 없으면 오렌지쥬스 1리터 3병 3. 우유가 있으면 식빵 500그람 1봉 4. 쌀과 자두 만약에: 우유 1리터 1병만 있으면? 쌀과 자두? 쌀과자 두? c Kwangkeun Yi
SW 오류의문제 살다가병이든다 사회적비용 해결책 = 경제적기회 SW 로동작하는제품이고장난다 사회적비용 해결책 = 경제적기회 SW 오류 : 사람이손으로손쉽게잡을수없다 엄청나게커지고복잡해진소프트웨어 새로운컴퓨팅환경 : 지구 = 컴퓨터 전지구적네트웍을타고 불특정다수의코드가내게로온다 ( 스마트폰 게임 /apps) 자동기술이필요
SW 오류 검증 기술: 1세대 문법 검증기: 70년대에 완성된 기술. lexical analyzer & parser 오류 = 소프트웨어의 생김새가 틀린 것 1. 우유 1리터 2병 2. 우유가 없으면 오렌지ㅈㅅ 1리터 3병 3. 있으면 빵식 우유가 500그람 1봉 4. 쌀과 자두 c Kwangkeun Yi SW 오류 검증 기술: 2세대 타입 검증(type checking): 90년대에 완성. (30년간 프로그래밍언어 분야의 대표 성과) 오류 = 생긴것은 멀쩡한데, 잘못된 값이 계산에 흘러드는 경우 1. 우유를 담은 얼음을 가스 불위에 올려놓고 데운다 2. 식빵을 유리접시에 담고 방아로 빻는다 3. 2의 접시에 1의 우유를 튀긴다 4. 남자와 소나무를 결혼시킨다 c Kwangkeun Yi
SW 오류 검증 기술: 3세대 프로그램분석검증: 아직 미완성 (static analysis, verification, model checking,...) 오류 = 생긴것도 멀쩡하고 타입도 맞지만, 바라는 바가 아 닌것 오류 = 필요한 조건을 만족시킬 수 없는 경우 1. 우유를 담은 냄비를 가스 불위에 데운다 2. 식빵을 스텐접시에 담고 방아로 빻는다 3. 남자1명과 여자1명을 결혼 시킨다 I 가스불이 포항제철 용광로가 된다면? I 방아가 현대중공업의 프레스가 된다면? I 남녀 나이의 차가 100살이된다면? c Kwangkeun Yi Challenge I 소프트웨어는 오류가 없어야한다 I 소프트웨어는 끊임없이 크고 복잡해 진다 I 소프트웨어의 오류를 자동을 찾아주는 기술이 필요하다 I 이 기술의 현재수준은 이제 겨우 2살 I 이 기술 발전에 필요한 인재: I 수학/논리학/통계학/컴퓨터과학/컴퓨터공학의 긴밀하고 깊이있는 교류와 공부가 필요 c Kwangkeun Yi
전산논리 (logic in computer science) 과목홈페이지 (ropas.snu.ac.kr/~kwang/027.13/12/) 의 박성우교수님 (POSTECH) 특강슬라이드참고 (special-lecture-on-logic). 소프트웨어, 그궁리의세계 : Part II 알고리즘 (algorithm & complexity)
소프트웨어, 그궁리의세계 언어 (language & logic). 궁리를표현하는언어와논리. 다양한계층의프로그래밍언어. 언어들사이의자동 번역. 소프트웨어기술의발전과정추적. 알고리즘 (algorithm & complexity) 같은계산을하는다양한방법. 제일효율적인 방법의탐구. 불가능한계산문제의존재. 가능하지만계산비용이 너무큰문제. 복잡성의계층. 알고리즘 (algorithm & complexity) 알고리즘 SW로구현될문제풀이법 기계적인계산 방식으로자동화되는문제풀이법 예 두자연수의최대공약수? 숫자리스트에서최대수? 주소록에서이름찾기? 지도위의출발지 / 목적지를잇는가장짧은경로? 자연수를소인수분해하기? 카카오톡으로가위바위보하기? 비밀문자를주고받기?
gcd(1892, 2893010) max[9, 28,1, 2998, 21, 22, 189, 29, 882, 1829, 10101, 229, 8, 101, 22, 399, ] factorize(484092029038111) shortest-path( 종로5가, 종합운동장 ) 카카오톡으로가위바위보 누구도믿지않고어떻게? 다음사실을이용 : 소인수분해는매우어렵다솟수인지아닌지판별은쉽다
알고리즘 성격 의분류 결정된과정으로, 무작위없이 (deterministic) 무작위를동원하거나통계적으로 (stochastic) 새로운방식이계속고안되고있다 알고리즘 성격 의분류 A 결정된과정으로, 무작위없이 (deterministic) 순차적으로재귀 (recursion) 혹은반복 (iteration) 같은일을작은부분에서반복 부분으로나누어 (divide & conquer) 부분으로나누고각부분에서해결
알고리즘 성격 의분류 B 무작위를동원하거나통계적으로 (stochastic) 기계학습으로 (machine learning) 많은수 (statistical) 의입력과해답을가지고함수를 추정 (machine learning) 추정한함수로새로운입력에대해서답하기 유전자같은방법으로 (genetic algorithm) 진화과정 ( 무작위, 교배, 돌연변이, 적자생존 ) 을모사하면서최적해찾기 무작위방법으로 (randomized algorithm) 무작위샘플을통해서전체를예측예 ) 도화지에서복잡한도형이차지하는넓이계산 사람을동원해서 (human computation) 컴퓨터로는어렵고사람은쉽게하는문제 예 ) 사람들이재미있게하는게임, 실은문제풀이 의도가숨은게임 알고리즘비용의분류 : 계산복잡도 (complexity) 알고리즘실행비용의증가정도 (order of growth) 계산비용 = 시간과메모리 증가정도 = 입력크기에대한함수로, 단 관심 : 입력이커지면결국어떻게될지 (asymptotic complexity) 계산복잡도 (complexity, order of growth) 가 O(f(n)) 이다 (n은입력의크기 ), 만일그계산비용이 f(n) 를넘지못하면 : k f(n) (k 는 n 과무관한양의상수 ) n 2, 10000 n 2, 3 n 2 + 10000 n 은모두 O(n 2 )
계산복잡도 (complexity) (pictures from Google search) 계산복잡도 (complexity) 계산 n!: 계산 b n : O(n) 로구현가능 O(n) 로구현가능 O(log n) 로구현가능
계산복잡도 (complexity) 순서대로정렬하기 (sorting) O(n 2 ) 로구현가능 (e.g. bubble sort) T n = (n 1) + (n 2) + + 1 대게 O(n log n) 이되게구현가능 (e.g. quick sort) T n = 2 T n/2 + (n 1) 알고리즘의복잡도 : 최악 / 평균 / 최선의경우따지기 계산복잡도 (complexity) 주어진자연수를소인수분해하라 : O(2 n ) 로구현가능 (n 자리수 ) O(poly(n)) 로구현가능? 누구도모름 주어진부울식 (boolean formula) 이참일수 있는가?(satisfiability): O(2 n ) 로구현가능 (n개의변수 ) O(poly(n)) 로구현가능? 누구도모름 k-차정수방정식 (diophantine equation) 을풀어라 : O(2 n ) 로구현가능? 누구도모름 O(n n ) 로구현가능? 누구도모름
문제모델링 (modeling) 까다로운배우들과스태프들캐스팅하기 (satisfiability) 부울식 (boolean formula) e.g. XY Z + XY Z + XY Z ( X 와 Y 가같이있을때 Z 가없으면 안되고... ) 주어진지하철노선도의모든역을지하철로방문하는최단경로는?(traveling salesman problem) 점과연결선 (graph) ( 연결선마다거리를표시 ) 샘많은조카들새해선물준비하기 (fixpoint) 집합연립방정식 (set equations) 문제줄이기 (reduction) A 문제를 B 문제로줄이다 ( Problem A is reducible to problem B. ) A 를푸는데 B 의해법으로가능하면 B 의문제로모델링해서풀고, 그결과를 A 의결과로 재해석 A-빨리풀기문제를 B-빨리풀기문제로줄이다 : A를푸는현실적인비용 (O(poly(n))) 의알고리즘? B를푸는현실적인비용 (O(poly(n))) 의알고리즘으로가능하면.
복잡도계층 컴퓨터로계산할수있는문제중에서, 대표적으로 P 클라스 NP 클라스 복잡도계층 : P 클라스 Polynomial-time algorithms 현실적인비용 (polynomial-time) 으로답을낼수있으면 이런 : O(logn), O(n), O(n 2 ), O(n 3 ) 등등 아닌 : O(2 n ), O(n n ) 등등
복잡도계층 : NP 클라스 Non-deterministic Polynomial-time algorithms 운좋으면 현실적인비용 (polynomial-time) 으로끝낼수있으면 운에기대지않고도현실적인비용으로끝낼수있는지는알수없는 그런문제의예 : 까다로운배우들과스태프들캐스팅하기 (satisfiability) 방문한도시의모든지하철역을반복없이방문하는 지하철경로가있는가?(Hamiltonial path) 방문한도시의모든지하철역을반복없이방문하는 지하철최단경로는?(traveling salesman problem, shortest Hamiltonian path) NP-complete 문제 NP 문제들중에서 종결자 문제가존재! NP의모든문제가그 종결자 문제로줄어들수 (reducible) 있다 : 그문제만 O(poly(n)) 에풀리면 NP의모든문제를 O(poly(n)) 에풀수있다. 빠뜨림없이 (complete). 3-SAT 문제 : 3개변수로표현한부울식이주어지면, 참일수있는지판별하기 따라서 3-SAT 문제의 O(poly(n)) 해법이있으면, N = NP. 찾아보세요. Turing Award(CS의노벨상 ) 보장 + 100만불 ( 참고 : NP-hard 문제 = NP문제들의 종결자, 그런데 NP c Kwangkeun 클라스에 Yi 속하는지는모르는.)
P = NP? 이질문의의미 운좋아야 현실적인비용 (polynomial-time) 으로끝낼수있는일들이 운 에기대지않고도현실적으로가능한가? 좋은작품 ( 시, 소설, 그림, 음악, 영화 ) 을만들어내는것이현실적인비용 (polynomial-time) 으로 (& 자동으로 ) 가능한가? 작가가쉬운가비평가가쉬운가? ( 좋은작품을만드는것과, 좋은작품인지판단하는것, 똑같이어려운가?) 답? 아직아무도모름. 아마도 P NP. 양자컴퓨팅 Quantum Computing
다음 1 400 년의축적 2 그도구의실현 3 SW, 그궁리의세계 4 응용 : 인간지능 / 본능 / 현실의확장