Michael O. Rabin
(¹Ì±¹ ÄÄÇ»ÅͰúÇÐÀÚ, 1931~)
.......... Rabin Àº ÄÄÇ»ÅÍ¾Ë°í¸®ÁòÀÇ À̷аú ÀÀ¿ëÀ» ¿¬±¸ÇÏ¿© ¿Ô´Ù. ±×ÀÇ ÁÖ¿ä °ü½É»ç´Â computer security ¿Í randomization in computations ÀÇ ÀÀ¿ëÀÌ´Ù. Dana Scott ¿Í Rabin Àº ±×µéÀÇ Àú¼ "Finite Automata and Their Decision Problem," ¿¡¼ ±²ÀåÈ÷ Áß¿äÇÑ °³³äÀ¸·Î ÆÇ¸íµÈ nondeterministic machines À» ¼Ò°³Çß´Ù. Áï ±×°ÍÀº computational complexity theory ¿¡¼ ÇÙ½É °³³äÀÌ µÇ¾úÀ¸¸ç ƯÈ÷ °¡Àå À¯¸íÇÑ ¿¹·Î¼ complexity classes P and NP ¸¦ ¹¦»çÇÏ¿´´Ù. Dana Scott ¿Í ÇÔ²² ÇÑ ±×ÀÇ Ãʱ⠿¬±¸ Ȱµ¿Àº ÄÄÇ»ÅÍ ¾ð¾î ÇÁ·Î¼¼½ÌÀÇ ±âÃʰ¡ µÇ¾ú´Ù. ÈĹݿ¡´Â ¹«ÀÛÀ§È (randomized) ¾Ë°í¸®Áò (¿À·ù ¹ß»ý È®·üÀº ±ØÈ÷ ÀÛÀ¸¸é¼µµ ¾ÆÁÖ È¿À²ÀûÀÎ ¾Ë°í¸®Áò) ¿¡ ´ëÇÑ ¿¬±¸·Î ¾ÏÈ£Çаú ³×Æ®¿öÅ© ÄÄÇ»ÆÃ ºÐ¾ß¿¡ ¾öû³ ¹ßÀüÀ» °¡Á®¿Ô´Ù. ±×´Â ¹«ÀÛÀ§È ¾Ë°í¸®ÁòÀÇ ±â¹ýÀ» ÀÌ·¸°Ô ¿ä¾àÇÑ´Ù. "µ¿ÀüÀ» ´øÁ® ±×°ÍÀ» Çö¸íÇÏ°Ô »ç¿ëÇϽÿÀ" ............... ±×´Â 1976 ³â Turing Award ¸¦ ¼ö»óÇß´Ù..........
Michael O. Rabin Àº ÇöÀç ÇϹöµåÀÇ Thomas J. Watson, Sr. Professor of Computer Science ÀÌÀÚ ¿¹·ç»ì·½¿¡ ÀÖ´Â È÷ºê·ç ´ëÇп¡¼ ¼öÇаú ÄÄÇ»ÅÍ °úÇÐÀ» ´ã´çÇÏ´Â ¾Ë¹öÆ® ¾ÆÀνºÅ¸ÀÎ ±³¼ö·Î ÀÖ´Ù. ±×´Â ½Ã°£À» Âɰ³¾î µÎ ´ëÇÐÀ» ¿À°¡¸ç ÇÑ ÇØ¸¦ º¸³»Áö¸¸ °¡Á·µéÀº ±×´ë·Î ¿¹·ç»ì·½¿¡ ¸Ó¹°°í ÀÖ´Ù. .........
º¹ÀâÇÑ ÀÛ¾÷µé¿¡ °üÇØ À̾߱⸦ ³ª´ ¶§¸é, ³ª´Â ¿ì¸®°¡ ÇöÀç·Î¼± ÀÌÇØ¸¦ ¿ÏÀüÈ÷ °á¿©Çϰí ÀÖ´Ù´Â »ý°¢À» ÇÕ´Ï´Ù. ¿¹¸¦ µé¸é, Àΰ£ÀÇ ±â¾ïÀÌ ¾î¶»°Ô ÀÛ¿ëÇÏ´ÂÁö¿¡ °üÇÑ ÀÌÇØ¸¦ °®°í ÀÖÁö ¸øÇÑ °ÍÀÔ´Ï´Ù. ³»°¡ ¸¸ÀÏ º£Å亥À» ¾ð±ÞÇÏ¸é °ð¹Ù·Î ±×°ÍÀÌ ÇÑ ÀÛ°î°¡¿¡ ´ëÇØ ¸»Çϰí ÀÖ´Â °ÍÀÓÀ» ¾Ë ¼ö ÀÖ½À´Ï´Ù. ´©±º°¡°¡ ¸Þ¸ð¸® ±¸¼º ¹æ¹ý°ú ÄÄÇ»ÅÍ ÇÁ·Î±×·¥À» ±¸¼ºÇÒ ¼ö ÀÖ´Ù¸é ±×°ÍÀ¸·Î ¾î¶² ÇÑÁ¤µÈ ºÐ¾ß¿¡¼ À̸§µéÀ» ºÐ·ùÇÒ °Ô µÉ °ÍÀÔ´Ï´Ù.
ÇÏÁö¸¸ ¿ì¸®ÀÇ ±â¾ïÀº ÈξÀ ´õ º¹ÀâÇÕ´Ï´Ù. °Å¸®¸¦ °È´Ù°¡ ´Ù¼Ò ÁöÀúºÐÇÑ ¸ô°ñÀ» ÇÑ »ç¶÷À» º¸°í´Â °©Àڱ⠰íµîÇб³ ½ÃÀý Á¦´ë·Î ¾ÄÁö ¾Ê¾Æ ±âºÐÀ» °Å½½¸®°Ô ¸¸µé´ø ¿·ÀÚ¸®ÀÇ ´©±º°¡¸¦ ¶°¿Ã¸± ¼öµµ ÀÖ½À´Ï´Ù. ±× ¿ª½Ã ´Ü¼øÇÑ ¿¹ÀÔ´Ï´Ù. ¿ì¸®´Â »ç¹°À» ±× ±¸Á¶·Î ±â¾ïÇÕ´Ï´Ù. ½ºÆ®·¹½º¸¦ ¹Þ°í ÀÖ´Â ¾î¶² »ç¶÷À» º¸¸é¼ ¿ÏÀüÈ÷ ´Ù¸¥ ¼º°ÝÀÇ ¾î¶² ³ó´ãÀ» ¶°¿Ã¸± ¼öµµ ÀÖÁö¿ä. ¿ì¸®´Â ´Ã»ó ÀÌ·¯ÇÑ ºñ¾àÀ» ÇÏ¸é¼ »ì°í ÀÖ½À´Ï´Ù.
¿ì¸®´Â ¾î¶² ¹æÇâÀ¸·Î °É¾î°¡°í ÀÖ´Â »ç¶÷À» µÚ¿¡¼ º¸°í´Â Á¦¸®µµ ¹Ù·Î Àú·¨¾ú´Ù°í ¸»ÇÕ´Ï´Ù. Á»Ã³·³ ½Ç¼ö¸¦ ÇÏ´Â ¹ýÀÌ ¾øÁö¿ä. ÃÖ¼ÒÇÑ ³» °æ¿ì¿£ °ÅÀÇ ÇÑ ¹øµµ ½Ç¼ö¸¦ ÇÏ´Â ÀûÀÌ ¾ø½À´Ï´Ù. µû¶ó¼, ½ÇÁ¦·Î ¿ì¸®¿¡°Ô ÇÊ¿äÇÑ °ÍÀº ¾ÆÁÖ ¾ÆÁÖ Àû´Ù°í ÇÒ ¼ö ÀÖ½À´Ï´Ù. ´Ù¸¸ ±×°ÍÀÌ ¿ì¸®¿¡°Ô ÇÊ¿äÇÑ °ÍÀº ¾ÆÁÖ ¾ÆÁÖ Àû´Ù°í ÇÒ ¼ö ÀÖ½À´Ï´Ù. ´Ù¸¸ ±×°ÍÀÌ ¾î¶»°Ô ÀÌ·ç¾îÁö´ÂÁö¸¦ ¿ì¸®°¡ ¾ËÁö ¸øÇÏ´Â °Í»ÓÀÌÁö¿ä. ³ª´Â À̰ÍÀÌ ÀǽÄÀÇ Èû°ú ÄÄÇ»ÅÍÀÇ Èû »çÀÌ¿¡ Á¸ÀçÇÏ´Â Â÷À̸¦ ¼³¸íÇØ¾ß ÇÑ´Ù°í´Â »ý°¢ÇÏÁö ¾Ê½À´Ï´Ù. ±× ¹®Á¦´Â ´ÜÁö ¿ì¸®°¡ ±×°ÍÀ» ½ÇÇàÇÒ ¼ö ÀÖ´Â ÄÄÇ»ÅÍ ÇÁ·Î±×·¥À» ÀÛ¼ºÇÏ´Â ¹æ¹ýÀ» ¸ð¸£°í ÀÖ´Â °Í»ÓÀÔ´Ï´Ù. ........... (Dennis Shasha 1995)
term :
¾Ë°í¸®Áò (Algorithm) °è»ê (Computation) °è»êº¹Àâµµ ÀÌ·Ð (Computational Complexity Theory) ºñ°áÁ¤ ¿ÏÀü (NP-complete) Michael Rabin A.M. Turing Award
site :
Homepage at Harvard Division of Engineering and Applied Science
Short Description in a Information Science Hall of Fame at University of Pittsburgh
Michael O. Rabin : ÄÄÇ»Å͸¦ ¸¸µç 15 ÀÎÀÇ °úÇÐÀÚ : Dennis Shasha. Cathy Lazere