차례 SNU 027.013 컴퓨터과학이여는 세계 (Computational Civilization) Part IV 1 400 년의축적 2 그도구의실현 Prof. Kwangkeun Yi School of Computer Science & Engineering 3 SW, 그궁리의세계 4 응용 : 인간지능 / 본능 / 현실의확장 이전 1 400 년의축적 2 그도구의실현 3 SW, 그궁리의세계 4 응용 : 인간지능 / 본능 / 현실의확장
다음 1 400 년의축적 2 그도구의실현 3 SW, 그궁리의세계 4 응용 : 인간지능 / 본능 / 현실의확장
컴퓨터과학의응용 : Part I 컴퓨터과학은 머리로궁리하는것 (intelligence) 에대한연구 (science) 이고 그응용은인간지능의확장. 컴퓨터과학, 인간지능의확장 Computer Science is the science of intelligence and its application is extensions of human intelligence. 마치 computer science life science science of intelligence science of life extension of human intelligence extension of human life 생명과학이생명현상에대한연구이고 그응용이인간수명의연장이듯이.
computer science medical science science of intelligence science of human disease extension of human intelligence conquering cancers computer science physics science of intelligence science of nature extension of human intelligence discovering energy source computer science mathematics science of intelligence science of reasoning enhancing human intelligence enhancing human reasoning 자동화 초창기자동화 상하수도, 세탁기 증기기차 내연기관자동차 더지능있는자동화 전화교환원 철도운전 진공청소기운전 좀더지능있는자동화 지능로봇 (robot), 자동차 / 비행기운전 컴퓨터서양장기챔피언 (IBM s Deep Blue): 인간 챔피언을이기다 (1997.5.11) 컴퓨터 Jeopardy! 챔피언 (IBM s Watson): 인간 챔피언들을이기다 (2011.2.14) 구글 (Google) 시리 (Wolfram Alpha)
컴퓨터의응용 I, 우리지능의확장 컴퓨터없이는불가능했던우리지능 I 자동화를통해서 사람지능을기계로확장 사람의고유한지능을집중 / 확장할여지 예 ) 질문하는지능 : 중요한문제가무엇인가? 예 ) 합성하는창의 : 전혀다른분야의융합 또어떤? 초광대한지식의탐색. 예전에는? 부분적인지식의탐색 손가락끝에제공되는모든지식들 Google같은탐색기술의성과 지식모음 (collection): 이세상모든웹페이지, 책, 이미지 인덱싱 (indexing, tagging): 탐색준비 랭킹 (ranking): 탐색결과정리 컴퓨터없이는불가능했던우리지능 I Google s PageRank 알고리즘 랭킹 : 복수의탐색결과들중에서어느것이정답일까? 기준 : 제일많이보는자료 ( 웹페이지, 책페이지, 이미지등 ) 링크의양으로? Google 의 PageRank 알고리즘 안1) 링크양 : 많이연결되어진페이지우선 안2) 링크질 : 중요하게연결되어진페이지우선 어떻게질을알아내는가? 페이지가방문될확률계산 (random surfer trick) 수리모델 : Markov chain 의극한값 (steady state) 다른기준들도 : 예 ) 질의문단어들의폰트크기, 웹페이지 단어들과의연관도
Google s PageRank 알고리즘 Google s PageRank 알고리즘 링크의질로? 위의문제없이랭킹하는방법 : 사람들이페이지를방문하는확률을예측하기 Google s PageRank 알고리즘 수리모델 : 지식탐색시설 옛날스타일 : Markov matrix M xij : i- 페이지가 j- 페이지를링크하면 1/n i (n i = i- 페이지에서외부로나가는링크수 ) 목표 : S = lim i S i, 여기서 S k+1 = M(S k ) 요즘스타일 : Google Server Farm at Dalles, Oregon 실제 : S = lim i S i, 여기서 S k+1 = N (S k ) 이고 N = 0.85M + 0.15. 왜? Markov 행렬안의모두가양이면, 그 Markov chain의극한값은유일하게존재. (Perron-Frobenius 정리 )
컴퓨터없이는불가능했던우리지능 II 컴퓨터없이는불가능했던우리지능 II 생명체의대규모데이터를판독 / 비교 / 분석. Human Genome Project: 인간유전자염기서열규명 (2003년 4월완성 ) 과감한 컴퓨터기술을이용해서비용문제해결 Archon X Prize( 천만달러 ): 100개의인간유전자서열들을 10일이내에판독해낼수있으면. 인간유전자염기서열 (ACGT ) 크기 : 약 30억자 (3 10 9 ) 약 100 만페이지 = 1000 페이지책 1000 권 실험기자재로한번에판독할수있는양 : 100자이내 유전자실전체를그만큼씩판독 : 3 10 7 횟수필요. 비현실적인시간과비용. 구원투수 ( 컴퓨터능력의활용 ): Shotgun sequencing technology Shotgun sequencing technology Shotgun sequencing technology 1. 판독할인간유전자실을여러개복사한다 2. 그실들을임의로잘게토막낸다 토막들은서로어느정도겹치게된다 3. 각토막마다양끝의염기서열을판독해낸다 4. (key) 양끝의염기서열들이서로겹치는토막들을연결해서원래의유전자실을복원한다 양끝의염기서열들이서로겹치는토막들을연결해서원래의유전자실을복원하기 컴퓨터기술때문에가능 문제 : 문자열토막들 {s0, s 1,, s n } 이주어졌을때, 모두를품고있는하나의가장짧은문자열 S 찾기. 예 ) {ACT, CT A, T AC, CCT, CT G, T GC, T CC, GCT, CT C} 답 ) ACT CCT GCT AC 또는 ACT GCT CCT AC
Shotgun sequencing technology 문제모델 문자열토막들의끝이겹치는관계를그래프로표현하면, 그그래프에서찾기. 입력 : 할일 : 꼭지를한번씩만모두방문하는여정 찾기 (Hamiltonian path 찾기 ) NP-complete 문제 이론 : 운좋아야현실적인비용으로가능 현실 : 적절한 통밥 (heuristics) 을이용하면대개 현실적으로가능 컴퓨터의응용 II, 우리본능의확장 컴퓨터가응원하고확대시켜주는우리의본능 소통의본능 이메일, 카카오톡, 미니홈피, facebook, twitter, skype, google hangout 음악 / 동영상공유 torrent, bugs, naver music 살펴볼근간기술 통신의한계는? 정보이론 (information theory) 온전히전달하는효과적인방법? 코딩 (encoding + error-correcting) 기술 컴퓨터의응용 II, 우리본능의확장 컴퓨터가응원하고확대시켜주는우리의본능 놀고싶은본능 컴퓨터게임 : 컴퓨터와, 친구와, 불특정다수의 사람들과 MMORPG(massively multiplayer online role-playing game) 에버랜드 보다거대한가상세계들이컴퓨터안에가능성 / 순기능 Reality Is Broken: why games make us better and how they can change the world, Jane McGonigal 한국형디지털스토리텔링 : [ 리니지2] 바츠해방전쟁이야기, 이인화 ( 특히 4부 )
디지털소통의근간기술 : Information Theory 디지털소통의근간기술 : Information Theory 소통중에임의로에러 / 잡음 : 메세지손상 메세지를온전히보낼방법들? 예 ) 반복 : 밥먹자? vs 밥먹자? 밥먹자? Claude Shannon(1916 2001) Information Theory 창시자 A Mathematical Theory of Communication, Bell System Technical Journal 27(3):379-423, 1948, Bell Labs Margna Carta of information age 밥먹자? 효율적인다양한방법들가능 그런방법들의한계는? 더좋은방법이가능한가? Information Theory가답을함 디지털소통의근간기술 : Information Theory 메세지의정보량 H = p(x) log 2 p(x). x 다음이엄밀히유도됨 온전히소통할수있는정보의량은제한된다 소통채널의용량 : C bits/sec 보낼메세지의정보량 : H bits/sec H C이면, 온전히전달가능. 채널잡음이아무리 커도. H > C이면, 온전히전달불가능. 오류율을 H C이하로줄일수없다. 메세지전달하기 : 인코딩 (encoding) 오류수정장치 (error-correcting) 인코딩 (encoding) 예 ) 사용단어 : 가마, 꼭, 꽃, 타고 문장예 ) 가마가마꼭가마꽃가마타고가마, 꽃가마꼭타고가마가마꼭가마 크기고정코드 : 00( 가마 ), 01( 타고 ), 10( 꼭 ), 11( 꽃 ). 복구? 크기변동코드 : 단어빈도 ( 가마 > 타고 > 꼭 > 꽃 ) 이용 0( 가마 ), 11( 타고 ), 100( 꼭 ), 101( 꽃 ). 복구?
메세지전달하기 : 인코딩 (encoding) 오류수정 장치 (error-correcting) 메세지전달하기 : 인코딩 (encoding) 오류수정 장치 (error-correcting) 오류수정장치 (error-correcting) 오류수정장치 (error-correcting) 반복 (repetition): 밥먹자? 밥먹자? 밥먹자? 밥먹자? 복구 : 밥먹자? 밤먹자? 밥먹저? 밥먹자 여분 (redundancy): 027013 zero two seven zero one three 복구 : zeri dwo sevem zirp ome tjree 027013 검산치 (checksum): 4 6 7 4 6 7 7 복구 : 4 6 7 5 다시보내줘 ( 검산치에러 ) 족집게검산치 (pinpoint checksum): 4 6 7 2 3 8 8 2 6 4 6 7 7 2 3 8 3 8 2 6 6 4 1 1 컴퓨터의응용 III, 우리현실의확장 컴퓨터의응용 III, 우리현실의확장 컴퓨터가확장시켜주는일상현실 : 전세계누구와도시공 간공유 ( 예 ) 전세계누구와도가위바위보 이전 : 여기현재 있는사람들끼리만 컴퓨터한계를역이용 전세계불특정다수와상거래 이전 : 동네 사람들끼리만 전세계누구와도가위바위보 / 상거래를성사시키는기술 컴퓨터로간단한그러나그역은 불가능 한계산 이용 정수곱 ( ) vs 역 : 소인수분해, 현실적으로불가능 P 로나눈나머지 (mod P ) 역 : 현실적으로불가능 근간기술 암호기술 (cryptography)
전세계누구와도시공간공유 : 가위바위보 카카오톡, facebook, skype 에서가위바위보 시공간공유해야 : 동시에내고그자리에서확인할수 있어야 떨어져있는전세계친구들과는? 문제 : 속일수있는여지 늦게내기 : 온것보고보내기 심판을두기? 심판이거짓말하면? 전세계누구와도시공간공유 : 가위바위보 컴퓨터로해결하는방법 속일수없게 믿고맡기는심판도없이 컴퓨터 : 곱의쉬움 vs 그역 ( 소인수분해 ) 의어려움을이용 가위 / 바위 / 보마다 1/3/7로끝나는솟수를사용하기로하고각자낼것에해당하는솟수를인수로가지는수를보냄 (X, Y ) 서로받고나면소인수분해못함 ( 서로가낸것을못봄 ) 서로에게자기솟수를공개 ( 소인수 x, y) 서로받은숫자를받은솟수로나눠봄 (X/x, Y/y); 서로승패를확인 ( 세솟수를곱해서보내면? 나눈값 X/x가솟수인지 확인은쉽다 ) 암호기술 (cryptography) 암호기술 (cryptography) 두사람이미리비밀 키 (key) 를공유 메세지보내는사람과받는사람만알수있게 암호화 : 보내는사람은메세지글자들을비밀키로 더해서 보내기 복호화 : 받는사람은메세지글자들을비밀키로 빼서 암호를풀기 단순히 더하고빼기 는아니지만... 비밀키를공유해야하는문제점 미리서로정해놔야. 당사자를미리알아야. 불특정다수와거래하고싶은데? 비밀소통 ( 거래 ) 하려면비밀소통 ( 비밀키 ) 가미리필요. 닭 vs 달걀
공개키암호기술 (public key cryptography) 비밀키를공개적으로만들수있는방법? Diffie-Hellman key exchange 비유 : 양념섞기 ( 가정 : 섞는것은쉽고, 분리해내는것은불가능 ) 공개 : 고추장 C 비밀 : 공개된고추장 C에각자의비밀양념 (x, y) 을 섞어 A = C x B = C y 공개 : A와 B를공개 비밀 : 다른사람의공개된 A, B를가져와서자기양념 y, x를섞는다 : k = (C x) y k = (C y) x 공유되는비밀양념 : k 공개키암호기술 (public key cryptography) 두사람 a 와 b 공개 : 솟수 P 비공개 : 각자의비밀 x, y 다음과같이비밀로공유할키를공개적으로만든다 : 각자 A, B를계산해서공개 A = 2 x mod P B = 2 y mod P 각자상대방것가져와서비밀계산 : 공유되는비밀키 a는 k = B x mod P b는 k = A y mod P (2 y mod P ) x mod P = 2 y x mod P (2 x mod P ) y mod P = 2 x y mod P 공개키암호기술 (public key cryptography) https: 로열리는페이지에서주고받는정보들은이방식으로 예 ) amazon.com에서책을살때 : 신용카드정보 128-bit encryption : 비밀키의크기가 128 bits