Project Problems SNU 4910.210, Fall 2012 Kwangkeun Yi due: 12/21(Fri), 24:00 Problem 1 (7%) 먼지폭풍 지구에서보낸화성표면탐사로봇은 2032년현재 100개이상이고, 그갯수가빠르게증가하고있다. 지구에는없는귀중한금속자원이화성표면에서속속발견되고있기때문이다. 화성궤도에는모선이돌고있어서, 화성표면에서임무를수행하는수많은로봇들과수시로데이타와명령을주고받도록되어있다. 이모선이하는일중하나는, 화성대기에먼지폭풍이예상되면표면탐사로봇들을재빨리대피소로대피시키는것이다. 모선에서는화성표면의로봇들에게대피해야할대피소를지정해주고대피명령을내리는것이다. 하나의대피소에는하나의로봇만수용할수있고, 대피명령을받은로봇은직 1
선경로로대피소를향해전속력으로이동하게되어있다. 문제는로봇이대피소로이동중에다른로봇과충돌할수있다는점이다. 충돌할일이없도록각각의로봇들에게대피소를할당해줘야한다. 이일을하는프로그램 shelterassign을아래의모듈타입에맞게작성하라. module type DUSTSTORM = sig type robot = string (* robot s name *) type shelter = int (* shelta s id number *) type location = int * int (* 화성에서의위도와경도 *) type robot_locs = (robot * location) list type shelter_locs = (shelter * location) list val shelterassign: robot_locs -> shelter_locs -> (robot * shelter) list end 화성은 2차원평면이라고하자. 원구나도넛모양으로끝들이연결되지않는다. 위도와경도는왼쪽위를 (0,0) 으로오른쪽아래는 (100,100) 으로한다. 그리고, 왜이프로그램이항상올바른답을유한시간내에내는지를프로그램에코멘트로설명하라. 올바른답 : 로봇과대피소의짝이주어지면절대로봇끼리직선경로이동중에충돌의가능성이없어야한다. 유한시간내 : 항상끝나야한다. 힌트 : 처음에는무작위로로봇과대피소를짝짖는다. 그리고다음을반복한다. 직선이동중충돌할수있는짝을찾아 하기. Problem 2 (5%) 랭킹추측 구글의페이지랭크 (PageRank) 기술은전세계모든웹페이지들의 중요도 순위를예측하는기술이다. 구글서치엔진은사용자가입력한문구를가진웹페이지들을추린후, 이기술을이용해서웹페이지들을 중요도 순서대로보여주려는것이다. 이중요도순서가사용자가읽고싶은페이지순서와일치하길바라면서. 그럼어떻게이 중요도 를계산해야할까? 구글창업자인 Page와 Brin의아이디어는이렇다 : 2
가정 : 사람들이자주방문하는페이지가 중요한 페이지이다. 그렇다면, 페이지를방문하는빈도를알아내면될텐데, 어떻게알아낼 것인가? 아이디어 : 불특정다수의사람이인터넷서핑을하는과정을모사 (simulation) 해서예측해보자. 사람들은한페이지에서시작해서링크를따라이런저런페이지를방문할것이고, 종종새로운페이지에서부터다시서핑을시작하곤할것이다. 이런경우를모사해서각페이지가방문되는상대적인비율을계산하면, 그비율이그페이지의 중요도 가아닐까. 그렇다면, 어떻게그런시뮬레이션을할것인가? 답 : 사람들이방문하는과정을 Markov chain으로모델링하면안성맞춤이다. Example 1 Markov chain으로모델링하는예. 다음과같은경우를생각해보자. 서울시와세종시사이에는매년인구이동이있다. 서울에서는매년인구의 5% 가세종시로이주하고, 반대로세종시에서는인구의 15% 가서울시로이주한다고하자. n-번째해의서울시의인구 S n 과세종시의인구 J n 은다음의관계를만족할것이다 : S n = 0.95 S n 1 + 0.15 J n 1 J n = 0.05 S n 1 + 0.85 J n 1 즉, ( Sn J n ) = ( ) ( ) 0.95 0.15 Sn 1 0.05 0.85 J n 1 3
그러면, 초기인구를각각 S 0, J 0 으로놓고, 위의점화식을연쇄적으로계산해가면서울시와세종시의인구가최종적으로어떻게될지를알수있을것이다. 위의행렬과같이, 각렬 (column) 의합이모두 1인행렬을 Markov행렬이라고하는데, Markov행렬로표현되는점화식이연쇄적으로만드는값들을 Markov chain이라고한다. 이제다시페이지랭킹문제로돌아오면, 수많은사람들이웹페이지를방문하면서형성되는각페이지별방문비율은다음과같이 Markov chain으로모델링될수있을것이다 : 전세계웹페이지가 3개있고 A, B, C라고하자. 각페이지에는다른페이지로향하는링크가매달려있을것이고, 사람들은이링크를따라방문을한다. 매번페이지 A가방문될비율은 A, B, C에서 A로가는링크의갯수에비례한다고하자. 예를들어, 페이지 B에링크가 3개인데, 그중하나가 A로오는것이면 B를방문한사용자는 1/3의비율로 A를방문한다고할수있다. 다른페이지들에대해서도서로이런관계로방문비율의변화를표현할수있을것이다. 예를들어다음과같이 : ( 페이지마다링크의목적지는각각다르다고가정하고, 페이지 A에는링크가두개있고, B에는세개, C에는하나가있다고가정 ): A n = 1 2 A n 1 + 1 3 B n 1 + 0 1 C n 1 B n = 1 2 A n 1 + 1 3 B n 1 + 1 1 C n 1 C n = 0 2 A n 1 + 1 3 B n 1 + 0 1 C n 1 즉, A n B n C n 1/2 1/3 0 = 1/2 1/3 1 0 1/3 0 A n 1 B n 1 C n 1 일반적으로총웹페이지수가 N개라면다음과같은 N N Markov 행렬 M이만들어진다. x ij M: i-페이지가 j-페이지를링크하면 1/r i (r i = i-페이지에있는링크수 ) 아니면 0. 그러면, 시간이지나면서페이지들이방문되는비율의변화는다음의점화식으로표현된다 : S n = MS n 1 4
목표 : 궁극적으로어떻게될지를계산하고싶다. 즉, 극한 S S = lim i S i 를계산하려는것이다. 초기벡터 S 0 는모든엔트리를 1/N 으로하 면될것이다 ( 모든페이지가방문을시작하는페이지일비율이동일 하다는가정 ). 문제 : 항상그런 Markov chain 의극한이유일하게존재하는가? 그 래서프로그램으로단순하게연쇄과정을반복하는작업을짜면항 상그프로그램은유한시간내에끝나게될까? 힌트 : Perron-Frobenius 정리 위의답을찾고, 주어진행렬이 Markov 행렬이고그극한이유일하게존재하 도록변환시킨후그극한을계산하는함수 markov_limit 를작성하라. 아래 의모듈타입을만족하도록한다. ( 함수들 row, column, add_row, add_column, size, ij 등은매트릭스를만들고사용하는함수들이다.) module type MARKOV = sig type matrix val row: float list -> matrix val column: float list -> matrix val add_row: float list -> matrix -> matrix val add_column: float list -> matrix -> matrix val size: matrix -> int * int (* numbers of columns and rows *) val ij: matrix -> int -> int -> float (* Given a Markov matrix and an initial column, markov_limit returns the limit of the Markov chain. *) val markov_limit: matrix -> matrix -> matrix end 5
Problem 3 (10%) 트랜스포머 한세계의물건을다른세계의물건으로변환시키는 트랜스포머 를만들 어보자. 우리변환의대상물과결과물은정수를다루는프로그램들이다. 변환대상은다음의규칙으로만들어지는정수식프로그램이다 : E n 정수 E+E 덧셈식 -E 부호변경식 read 정수입력식 if E E E 조건식 repeat E E 반복식 입력식 read는외부에서입력받은정수를뜻한다. 입력은 -100과 100사 이의정수라고가정한다. 조건식 if E 1 E 2 E 3 의결과는 E 1 의값에따라결정된다 : E 1 의값이 0 이아니면 E 2 의값이되 고 0 이면 E 3 의값이된다. 반복식 repeat E 1 E 2 은 E 1 의값이음수가아닐때만정의되는데, 결과는 E 2 의값을 E 1 의값만큼반복해서더한결과이다. 즉, (E 1 의값 ) (E 2 의값 ) 이다. 따라서 E 1 이 0이면결과는 0이다. 6
변환결과물은다음의규칙으로만들어지는명령문프로그램이다 : C x has n 변수 x가정수 n을가진다 x has x 다른변수의값을가진다 x has x+x 다른변수의덧셈결과를가진다 x has x-x 다른변수의뺄셈결과를가진다 x has read 입력된정수를가진다 say x 변수를출력한다 goto l on x 변수에따라점프 l: C 태그가붙은명령문 C ; C 순서대로실행되는명령문들 보다시피변수가중심이다. 모든값을항상변수에넣고변수를가지고 계산이진행된다. 따라서변수를사용전에는항상그변수에어떤값이 들어가있어야한다. 명령문 x has read 는외부에서정수입력을받아변수 x에넣는다. 입력은 -100과 100사이의정수라고가정한다. 명령문 goto l on x 은변수 x의값이 0이면일없이마치고, 0이아니면태그 l이붙은명령문으로점프한다. 예를들어다음의프로그램은외부에 1을출력한다 : x has 1 ; y has 2 ; x has x+y ; goto L on x ; x has 0 ; L: z has x-y ; say z 다음의프로그램은실행될수없는프로그램이다. 변수 z가값을가지지 7
도않았는데사용되기때문이다 : x has 1 ; y has x+x ; z has y+z ; say z 변환기는변환대상정수식과 같은일을하는 명령문프로그램을내놓는다. 이명령문프로그램은원래정수식이계산하는값과같은값을출력해야한다. 변환전확인사항 : 변환해서는안되는 의미없는 정수식이있다. 변환기는의미없는정수식이입력으로들어오면변환을거부해야한다. 의미없는정수식은한가지경우밖에없다. 반복식 repeat E 1 E 2 에서 E 1 의값이음수인경우다. 이런정수식은그계산이정의되어있지않다. 변환기는번역대상물인정수식에이런의미없는반복식이있는지확인해야한다. 번역하기전에 E 1 의값을예측해서음수여부를첵크해야한다. 변환후확인사항 : 변환결과로만들어지는 C프로그램이제대로동작하는지를확인해야한다. 이확인은궁극적으로변환대상과변환결과가같은일을하는지를체크해야하지만, 여기서는다음의두가지경우를확인하도록한다. 변수가사용되기전에항상값이넣어졌는지. 점프하는대상명령문이제대로정의되어있는지. 즉, 점프할태그가붙은명령문이딱하나있는지. 변환기 transform과검사기들 check_exp와 check_cmd는아래의모듈타입을만족하도록한다 : module type TRANS = sig type exp = Num of int Add of exp * exp 8
Minus of exp Read If of exp * exp * exp Repeat of exp * exp type var = string type tag = string type cmd = HasNum of var * int HasVar of var * var HasSum of var * var * var HasSub of var * var * var HasRead of var Say of var Goto of tag * var Tag of tag * cmd Seq of cmd * cmd val transform: exp -> cmd val check_exp: exp -> bool val check_cmd: cmd -> bool end Problem 4 (8%) 진품코드 가방제조업체부비통에서는제품의진품여부를추후에확인할수있도록, 출시되는백의배경에비밀스런패턴코드를심어놓는다. 이패턴코드는다음과같이여러개가자동생성되고, 제품마다무작위로심어지게된다. 패턴코드생성기는세가지로구성된다. 패턴코드에사용되는심볼들의집합, 시작심볼, 유한개의규칙들이다. 규칙들은두종류가있다. 생성규칙과소멸규칙. 생성규칙은심볼하나가어떤다른심볼들의문자열로변환되는지를정한규칙이다. 소멸규칙은소멸되는심볼들의문자열들이모여있다. 예를들어, 심볼집합이 {A, B}, 9
이고, 시작심볼은 A 이며, 생성규칙들은 A AB B A 이고, 소멸규칙은 AA 라고하자. 그러면, A에서시작해서매스텝마다 모든생성 ( ) 후모든소멸 ( ) 을적용하면서 ( 생성규칙을모두적용하고그결과에소멸규칙을모두적용하면서 ) 다음과같은패턴코드들이계속생성된다 : A AB AB ABA ABA ABAAB ABB ABAA AB 즉, A에서시작해서네번째생성-후-소멸결과의패턴코드는 ABB가된다. 소멸규칙은주어진문자열에서최대로소멸시킬수있을만큼소멸시키게된다. 없앨수있는부분문자열이겹치더라도모두적용된다. 예를들어현재문자열이 AAABA 라면소멸될수있는부분문자열 (AA) 가두개앞쪽에겹쳐있지만 (AAA) 모두적용되어소멸되고뒤에오는 BA만생성규칙에의해 AAB가된다. 아래의모듈타입을만족하는모듈을정의하라. 함수 valid는주어진룰에서심볼리스트가만들어질수있는패턴코드인지를판별한다. pprint n(n 0) 은생성-후-소멸을 n번취한후의패턴코드를출력한다. module type BOUVITON = sig type symbol = A B C D type start = symbol type genrule = (symbol * symbol list) list type delrule = (symbol list) list type rule = genrule * delrule val pprint: int -> unit val valid: rule * symbol list -> bool end 10
[ 참고 ] 다음의것들이, 심볼들마다붓움직임을대입하면우리가아는그림 을그리는패턴들이다. 생성규칙만있는. name symbols start rules algae A, B A A AB, B A tree 0, 1, [,] 0 1 11, 0 1[0]0 cantor dust A, B A A ABA, B BBB koch curve F, +, F F F+F F F+F sierpinski tri A, B, +, A A B A B, B A+B+A dragon curve X, Y, F, +, FX X X+YF, Y FX Y fractal plan X, F, +,, [,] X X F [[X]+X]+F[+FX] X, F FF 11