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 School of Computer Science & Engineering 3 SW, 그궁리의세계 4 응용 : 인간지능 / 본능 / 현실의확장 이전 년의축적 2 그도구의실현 3 SW, 그궁리의세계 4 응용 : 인간지능 / 본능 / 현실의확장

2 다음 년의축적 2 그도구의실현 3 SW, 그궁리의세계 4 응용 : 인간지능 / 본능 / 현실의확장 소프트웨어 Software(SW) 소프트웨어, 그궁리의세계 언어 (language & logic). 궁리를표현하는언어와논리. 하나의소프트웨어 = 하나의튜링기계 하나의컴퓨터 ( 보편만능의튜링기계 Universal TM) 는임의의 SW( 튜링기계 ) 를메모리에싣고그 SW를실행 ( 그튜링기계를모사 ) 다양한계층의프로그래밍언어. 언어들사이의자동 번역. 소프트웨어기술의발전과정추적. 알고리즘 (algorithm & complexity) 같은계산을하는다양한방법. 제일효율적인 방법의탐구. 불가능한계산문제의존재. 가능하지만계산비용이 너무큰문제. 복잡성의계층.

3 소프트웨어, 그궁리의세계 : Part 언어 (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) 을 만족하도록

4 번역기원리의예 상위의언어 L ( 가상 ) 에서 E ::= n E + E E E E C ::= push n add sub mult C.C 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 ::= 프로그램을연습해보자 SW 는복잡하다 함수정의 sum n = fac n = gcd (n,m) = append (a, b) = compile E =

분야의 역사 겨우 5-60년 프로그램은 기계가 자동으로 실행함 기계는 우리가 바라는 바를 실행하지 않음 기계는 sw에 적힌 바를 실행할 뿐 장보기 = 우유 1리터, 신라면 4봉지, 그리고 쌀과자두 사오기.

5 SW는 복잡하다 less-382(23,822 LoC) 자연물 만큼 복잡 포유류 뇌의 1만개 뉴런의 넷트웍, Ecole Polytechnique Fe de rale de Lausanne, Blue Brain Project, 2008 SW 제작의 어려움 고백: 컴퓨터분야는 아직 미숙합니다 프로그램의 규모와 복잡도가 점점커짐 프로그램 복잡성의 증가속도 >> hw 성능의 성장속도 sw는 가스다. Software is gas. 분야의 역사 겨우 5-60년 프로그램은 기계가 자동으로 실행함 기계는 우리가 바라는 바를 실행하지 않음 기계는 sw에 적힌 바를 실행할 뿐 장보기 = 우유 1리터, 신라면 4봉지, 그리고 쌀과자두 사오기. 모든 상황을 고려해야 사소한 실수가 없어야 프로그램의 실행을 미리 완벽히 알기 가 어려움 자동으로는 불가능: 증명됨(1936년, Alan Turing) 사람이 확인해가야: 다양한 도구로 비용절감 현재의 기술수준: 걸음마 3발짝, 초보수준 그래서 미숙하기 때문에 = 기회가 많다. 미숙하기 때문에 = 지금 Newton, Galileo, Curie, 와 같이 살고있다.

컴퓨터분야발전속도가빠르다? (1/3) 컴퓨터속도 : 10 7 배 /50 년발전 컴퓨터분야발전속도가빠르다?

35 10 6 hp/hr ( 원전 1GW/hr) 10 3 flops/cpu ENAC(1945) 2 10 10 flops/core BM Sequoia(2010) 교통분야

(3/3) 하드웨어 : 다른분야와비슷한발전 소프트웨어 : 많이미개함 크기만증가 : 휴대폰 100만줄아래아한글 200만줄스마트폰 1000만줄윈도우 3000만줄 소프트웨어

6 컴퓨터분야발전속도가빠르다? (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 ) 컴퓨터분야발전속도가빠르다? (3/3) 하드웨어 : 다른분야와비슷한발전 소프트웨어 : 많이미개함 크기만증가 : 휴대폰 100만줄아래아한글 200만줄스마트폰 1000만줄윈도우 3000만줄 소프트웨어 : 다른분야가이루어놓은것을아직이루지못했슴 다른분야의현재수준 제대로작동할지를미리검증할수없는기계설계는없다. 제대로작동할지를미리검증할수없는회로설계는없다. 제대로작동할지를미리검증할수없는공장설계는없다. 제대로서있을지를미리검증할수없는건축설계는없다. 뉴튼방정식, 미적분방정식, 통계역학, 무슨무슨방정식... 무엇일까?

7 모든 기술의 질문 소프트웨어 분야에서의 이 질문 작성한 SW의 오류를 우리가 만든 것이 자동으로 미리 모두 찾아주거나, 우리가 의도한대로 움직인다는 것을 없으면 없다고 확인해주는 어떻게 미리 기술들은 있는가? 확인할 수 있는가? 그래서, SW의 오류때문에 발생하는 (사실, 일상에서도 잦은 질문과 답: 입학시험, 입사시험, 궁합, 클럽 개인/기업/국가/사회적 비용을 관리) 절감시켜주는 기술들은 있는가? SW 오류(bug) 소프트웨어에 있는 오류 소프트웨어가 생각대로 실행되지 않는 것 사람이 소프트웨어를 잘못 만들었기 때문 천재지변이 아님 SW 오류의 예 어머니가 전해준 슈퍼마켓 심부름 목록(프로그램) 1. 우유 1리터 2병 2. 우유가 없으면 오렌지쥬스 1리터 3병 3. 우유가 있으면 식빵 500그람 1봉 4. 쌀과 자두 만약에: 우유 1리터 1병만 있으면? 쌀과 자두? 쌀과자 두?

SW 오류의 문제 SW 오류: 사람이 손으로 손쉽게 잡을 수 없다 살다가 병이든다 사회적 비용 해결책 = 경제적기회 엄청나게 커지고 복잡해 진 소프트웨어 새로운 컴퓨팅 환경: 지구 = 컴퓨터 전지구적 네트웍을 타고 불특정 다수의 코드가 내게로 온다(스마트폰 SW로 동작하는 제품이 고장난다 게임/apps) 사회적 비용 자동 기술이 필요 해결책 = 경제적기회

8 SW 오류의 문제 SW 오류: 사람이 손으로 손쉽게 잡을 수 없다 살다가 병이든다 사회적 비용 해결책 = 경제적기회 엄청나게 커지고 복잡해 진 소프트웨어 새로운 컴퓨팅 환경: 지구 = 컴퓨터 전지구적 네트웍을 타고 불특정 다수의 코드가 내게로 온다(스마트폰 SW로 동작하는 제품이 고장난다 게임/apps) 사회적 비용 자동 기술이 필요 해결책 = 경제적기회 SW 오류 검증 기술: 1세대 SW 오류 검증 기술: 2세대 타입 검증(type checking): 90년대에 완성. 문법 검증기: 70년대에 완성된 기술. lexical analyzer & (30년간 프로그래밍언어 분야의 대표 성과) parser 오류 = 생긴것은 멀쩡한데, 잘못된 값이 계산에 흘러드는 오류 = 소프트웨어의 생김새가 틀린 것 1. 우유 1리터 2병 2. 우유가 없으면 오렌지ㅈㅅ 1리터 3병 경우 1. 우유를 담은 얼음을 가스 불위에 올려놓고 데운다 3. 있으면 빵식 우유가 500그람 1봉 2. 식빵을 유리접시에 담고 방아로 빻는다 4. 쌀과 자두 3. 2의 접시에 1의 우유를 튀긴다 4. 남자와 소나무를 결혼시킨다

9 SW 오류 검증 기술: 3세대 Challenge 프로그램분석검증: 아직 미완성 (static analysis, verification, model checking,...) 소프트웨어는 오류가 없어야한다 닌것 소프트웨어는 끊임없이 크고 복잡해 진다 오류 = 필요한 조건을 만족시킬 수 없는 경우 소프트웨어의 오류를 자동을 찾아주는 기술이 오류 = 생긴것도 멀쩡하고 타입도 맞지만, 바라는 바가 아 필요하다 1. 우유를 담은 냄비를 가스 불위에 데운다 이 기술의 현재수준은 이제 겨우 2살 2. 식빵을 스텐접시에 담고 방아로 빻는다 이 기술 발전에 필요한 인재: 3. 남자1명과 여자1명을 결혼 시킨다 가스불이 포항제철 용광로가 된다면? 방아가 현대중공업의 프레스가 된다면? 남녀 나이의 차가 100살이된다면? 전산 논리(logic in computer science) 수학/논리학/통계학/컴퓨터과학/컴퓨터공학의 긴밀하고 깊이있는 교류와 공부가 필요 소프트웨어, 그 궁리의 세계: Part 과목 홈페이지(ropas.snu.ac.kr/~kwang/027.13/12/)의 박성우 교수님(POSTECH) 특강 슬라이드 참고 알고리즘(algorithm & complexity) (special-lecture-on-logic).

불가능한 계산문제의 존재. 가능하지만 계산 비용이 자연수를 소인수 분해하기? 너무 큰 문제. 카카오톡으로 가위바위보하기? 복잡성의 계층. 비밀문자를 주고받기?

10 소프트웨어, 그 궁리의 세계 언어(language & logic). 알고리즘 궁리를 표현하는 언어와 논리. SW로 구현될 문제풀이법 다양한 계층의 프로그래밍 언어. 언어들 사이의 자동 기계적인 계산 방식으로 자동화되는 문제풀이법 예 번역. 알고리즘(algorithm & complexity) 소프트웨어 기술의 발전과정 추적. 두 자연수의 최대공약수? 숫자 리스트에서 최대수? 같은 계산을 하는 다양한 방법. 제일 효율적인 주소록에서 이름 찾기? 방법의 탐구. 지도위의 출발지/목적지를 잇는 가장 짧은 경로? 불가능한 계산문제의 존재. 가능하지만 계산 비용이 자연수를 소인수 분해하기? 너무 큰 문제. 카카오톡으로 가위바위보하기? 복잡성의 계층. 비밀문자를 주고받기? 알고리즘(algorithm & complexity) gcd(1892, ) max[9, 28,1, 2998, 21, 22, 189, 29, 882, 1829, 10101, 카카오톡으로 가위바위보 누구도 믿지않고 어떻게? 다음 사실을 이용: 229, 8, 101, 22, 399, ] factorize( ) shortest-path(종로5가, 종합운동장) 소인수분해는 매우 어렵다 솟수인지 아닌지 판별은 쉽다

11 알고리즘 성격 의분류 알고리즘 성격 의분류 A 결정된과정으로, 무작위없이 (deterministic) 결정된과정으로, 무작위없이 (deterministic) 무작위를동원하거나통계적으로 (stochastic) 새로운방식이계속고안되고있다 순차적으로재귀 (recursion) 혹은반복 (iteration) 같은일을작은부분에서반복 부분으로나누어 (divide & conquer) 부분으로나누고각부분에서해결 알고리즘 성격 의분류 B 알고리즘비용의분류 : 계산복잡 무작위를동원하거나통계적으로 (stochastic) 기계학습으로 (machine learning) 많은수 (statistical) 의입력과해답을가지고함수를추정 (machine learning) 알고리즘실행비용의증가정도 (order of growth) 계산비용 = 시간과메모리 추정한함수로새로운입력에대해서답하기 증가정도 = 입력크기에대한함수로, 단 유전자같은방법으로 (genetic algorithm) 관심 : 입력이커지면결국어떻게될지 (asymptotic 진화과정 ( 무작위, 교배, 돌연변이, 적자생존 ) 을 complexity) 모사하면서최적해찾기 무작위방법으로 (randomized algorithm) 계산복잡도 (complexity, order of growth) 가 O(f(n)) 무작위샘플을통해서전체를예측 이다 (n은입력의크기 ), 만일그계산비용이 f(n) 를 예 ) 도화지에서복잡한도형이차지하는넓이계산 넘지못하면 : 사람을동원해서 (human computation) k f(n) 컴퓨터로는어렵고사람은쉽게하는문제 예 ) 사람들이재미있게하는게임, 실은문제풀이 (k는 n과무관한양의상수 ) 의도가숨은게임 SNU c Kwangkeun n 2, Yi n 2, 3 n n은모두 O(n 2 ) 도 (complexity)

12 계산복잡도 (complexity) 계산복잡도 (complexity) (pictures from Google search) 계산 n!: O(n) 로구현가능 계산 b n : O(n) 로구현가능 O(log n) 로구현가능 계산복잡도 (complexity) 계산복잡도 (complexity) 순서대로정렬하기 (sorting) O(n 2 ) 로구현가능 (e.g. bubble sort) T n = (n 1) + (n 2) 대게 O(n log n) 이되게구현가능 (e.g. quick sort) T n = 2 T n/2 + (n 1) 알고리즘의복잡도 : 최악 / 평균 / 최선의경우따지기 주어진자연수를소인수분해하라 : 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 ) 로구현가능? 누구도모름

13 문제모델링 (modeling) 문제줄이기 (reduction) 까다로운배우들과스태프들캐스팅하기 (satisfiability) 부울식 (boolean formula) e.g. XY Z + XY Z + XY Z ( X 와 Y 가같이있을때 Z 가없으면 안되고... ) 주어진지하철노선도의모든역을지하철로방문하는최단경로는?(traveling salesman problem) 점과연결선 (graph) ( 연결선마다거리를표시 ) 샘많은조카들새해선물준비하기 (fixpoint) 집합연립방정식 (set equations) A문제를 B문제로줄이다 ( Problem A is reducible to problem B. ) A를푸는데 B의해법으로가능하면 B의문제로모델링해서풀고, 그결과를 A의결과로재해석 A-빨리풀기문제를 B-빨리풀기문제로줄이다 : A를푸는현실적인비용 (O(poly(n))) 의알고리즘? B를푸는현실적인비용 (O(poly(n))) 의알고리즘으로가능하면. 복잡도계층 복잡도계층 : P 클라스 컴퓨터로계산할수있는문제중에서, 대표적으로 P 클라스 NP 클라스 Polynomial-time algorithms 현실적인비용 (polynomial-time) 으로답을낼수있으면 이런 : O(logn), O(n), O(n 2 ), O(n 3 ) 등등 아닌 : O(2 n ), O(n n ) 등등

14 복잡도계층 : 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 클라스에속하는지는모르는.) P = NP? 이질문의의미 운좋아야 현실적인비용 (polynomial-time) 으로끝낼수있는일들이 운 에기대지않고도현실적으로가능한가? 좋은작품 ( 시, 소설, 그림, 음악, 영화 ) 을만들어내는것이현실적인비용 (polynomial-time) 으로 (& 자동으로 ) 가능한가? 작가가쉬운가비평가가쉬운가? ( 좋은작품을만드는것과, 좋은작품인지판단하는것, 똑같이어려운가?) 답? 아직아무도모름. 아마도 P NP. 양자컴퓨팅 Quantum Computing

15 다음 년의축적 2 그도구의실현 3 SW, 그궁리의세계 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 III Prof. Kwangkeun Yi School of Computer Science & Engineering 차례 1 400 년의축적 2 그도구의실현 3 SW, 그궁리의세계 4 응용 : 인간지능 / 본능 / 현실의확장 이전 1 400 년의축적 2 그도구의실현