Robert  E.  Tarjan

 

(¹Ì±¹ ÄÄÇ»ÅÍ°úÇÐÀÚ, 1948~)

.........¾Ë°í¸®Áò°ú ÀڷᱸÁ¶ÀÇ ¼³°è, ºÐ¼®¿¡ ¹ßÀü¿¡ °øÇå, 1986 Æ©¸µ»óÀ» ¼ö»ó ............

Robert E. Tarjan  Homepage : Princeton Univ., Computer Science

·Î¹öÆ® ¾Óµå·¹ ŸÀÜÀº 1948 ³â Ķ¸®Æ÷´Ï¾Æ ÁÖ Æ÷¸ð³ª¿¡¼­ ž´Ù. ¾î¸° ³ªÀ̺ÎÅÍ ±×´Â °úÇп¡ Èï¹Ì¸¦ ´À²¼´Ù. ¼Ò¾ÆÁ¤½Å°ú¿¡¼­ Á¤½Å Áöü ºÐ¾ß Àü¹®ÀÇ¿´´ø ŸÀÜÀÇ ¾Æ¹öÁö´Â ÁÖ¸³ º´¿øÀ» ¿î¿µÇÏ°í ÀÖ¾ú´Ù. ŸÀÜÀº ÁßÇб³ ½ÃÀý ±× °÷¿¡¼­ ÀÏÀÚ¸®¸¦ ¾ò¾î ±×°¡ '¿¹ºñ ÄÄÇ»ÅÍ (precomputer)' ¶ó ºÒ·¶´ø IBM õ°ø Ä«µå Á¶ÇÕ±âµé¿¡ ´ëÇÑ ÀÛ¾÷À» ÇÏ¿´´Ù. 1964 ³â ÁßÇÐ °úÁ¤¿¡ À̾îÁø ÇÏ°è°úÇÐ ÇÁ·Î±×·¥¿¡¼­ ŸÀÜÀº óÀ½À¸·Î ½ÇÁ¦ ÄÄÇ»Å͵éÀ» °¡Áö°í ÀÛ¾÷À» ÇÏ°Ô µÇ¾ú´Ù.

Ä®Å×Å©¿¡¼­ ŸÀÜÀº ¼öÇÐÀ» Àü°øÇÏ¿´Áö¸¸, ÄÄÇ»ÅÍ °úÇÐÂÊ¿¡¼­µµ ´ëÇпø»ýµé¿¡°Ô °³¼³µÈ °úÁ¤Àº ºüÁü¾øÀÌ ¼ö°­ÇÏ¿´´Ù. ½ºÅÄÆÛµå´Â µµ³Îµå Å©´©½º¿Í Á¸ ¸ÅÄ¿½Ã¸¦ Æ÷ÇÔÇØ ÄÄÇ»ÅÍ °úÇÐÀÇ ¼±±¸Àû Àι°µéÀ» ¹èÃâÇß´Ù´Â °ÍÀ» ÀÚ¶û½º·´°Ô ¿©±â°í ÀÖ¾ú´Ù.

¶Ç ÇѸíÀÇ °í¹«ÀûÀÎ Àι°Àº ÄÚ³Ú¿¡¼­ ¾È½Ä³âÀ» ¸Â¾Æ ½ºÅÄÆ۵忡 ¿Í ÀÖ¾ú´ø Á¸ È©Å©·ÎÇÁÆ®¿´´Ù. ±×´Â ŸÀÜÀÌ ´ëÇпø 2 Çг⠰úÁ¤À» ½ÃÀÛÇϱâ ÀüÀ̾ú´ø ¿©¸§¿¡ ±× °÷¿¡ µµÂøÇÏ¿© ±×ÀÇ ¿·¹æ¿¡ µé¾î¿Ô´Ù. ±× µÎ »ç¶÷Àº °ð °øµ¿ ¿¬±¸¸¦ ½ÃÀÛÇÏ¿© ¸¶Ä§³» 1986 ¿¡´Â Æ©¸µ»óÀ» ¼ö»óÇϱ⿡ À̸¥´Ù........

±×°¡ ½ºÅÄÆÛµå ´ëÇп¡¼­ Á¸ È©Å©·ÎÇÁÆ® (John Hopcroft) ¿Í ÇÔ²² ÇÑ ¹Ú»ç °úÁ¤ÀÇ ¿¬±¸´Â Æò¸é °Ë»ç (planarity testing) ¿Í ±× ¹ÛÀÇ ±×·¡ÇÁ ¾Ë°í¸®Áòµé¿¡ ´ëÇÑ °ÍÀ¸·Î¼­, º¸´Ù È¿À²ÀûÀΠĨ ·¹À̾ƿô¿¡¼­ º¸´Ù ³ªÀº µµÇü (map) ·¹À̾ƿô¿¡ À̸£±â±îÁö ´Ù¾çÇÑ ÀÀ¿ë ÇÁ·Î±×·¥À» ź»ý½ÃÄ×´Ù. ÀÌµé ¾Ë°í¸®ÁòÀº ¸ðµç ÇкλýµéÀÌ ¹è¿ì°Ô µÇ´Â '±íÀÌ ¿ì¼± °Ë»ö (depth-first search)' À̶ó´Â ÇÁ·Î±×·¡¹Ö ±â¼úÀÇ À§·ÂÀ» °­Á¶ÇÑ´Ù. ¶ÇÇÑ, ±íÀÌ ¿ì¼± °Ë»öÀº °ÔÀÓÀ̳ª ½ºÇÁ·¹µå ½ÃÆ®, ±×·¡ÇÈ ÇÁ·Î±×·¥ µîÀÇ ºÐ¾ß¿¡¼­µµ ÇÏ·ç¿¡ ¼ö½Ê¾ï Â÷·Ê¾¿ »ç¿ëµÇ°í ÀÖ´Ù. ÀÌÈÄ Å¸ÀÜÀÌ ´í ½½¸®ÅÍ (Dan Sleator), ¾Øµå·ù °ñµå¹ö±× (Andrew Goldberg) ¿Í ÇÔ²² ÁøÇàÇÏ¿´´ø È¿À²ÀûÀÎ ³×Æ®¿öÅ© È帧¿¡ ´ëÇÑ ¿¬±¸´Â ¼³°èÀÚµéÀÌ ¿¬¾ÈÀÇ ¼®À¯¿¡¼­ ÀüÈ­ ÅëÈ­¿¡ À̸£±â±îÁö ¸ðµç °ÍÀÇ È帧À» °³¼±Çϱâ À§Çؼ­´Â ³×Æ®¿öÅ©¿¡¼­ °¢°¢ÀÇ ¿¬°á¿¡ ¾ó¸¶³ª ¸¹Àº ¿ë·®À» ºÎ¿©ÇØ¾ß ÇÏ´ÂÁö¸¦ ¾Ë¾Æ³»´Â µ¥ µµ¿òÀ» ÁÖ¾ú´Ù. »Ó¸¸ ¾Æ´Ï¶ó, »óÇâ Æ®¸® (up-tree) ¿Í »ç¼± Æ®¸® (splay-tree) ¶ó°í ¾Ë·ÁÁ® ÀÖ´Â ÇÑ ½ÖÀÇ ´Ü¼øÇÑ ÀÚ·á ±¸Á¶¿¡ ´ëÇÑ ±×ÀÇ ¿¬±¸´Â ¾Ë°í¸®ÁòÀÇ È¿À²¼ºÀ» ÃøÁ¤ÇÏ´Â »õ·Î¿î ±â¹ýÀ» µµÀÔ½ÃÄ×´Ù.

´Ò »ç³ªÅ© (Neil Sarnak), ½½¸®ÅÍ, Á¦ÀÓ½º µå¸®½ºÄÝ (James Driscoll) µî°ú ÇÔ²² ÇÑ ¶Ç ´Ù¸¥ ¿¬±¸´Â ÇöÀç »Ó¸¸ ¾Æ´Ï¶ó °ú°Å¿¡ ´ëÇÑ Á¤º¸±îÁö º¸À¯ÇÒ ¼ö ÀÖ´Â ÀÚ·á ±¸Á¶¸¦ ¾ÆÁÖ È¿À²ÀûÀÎ ÇüÅ·ΠÁ¦½ÃÇÏ¿´´Ù. ±×ó·³ '¿µ¼ÓÀûÀÎ' ÀÚ·á ±¸Á¶´Â ¿À´Ã³¯ ·Îº¿ °øÇаú µ¥ÀÌÅÍ º£À̽º ½Ã½ºÅÛ ºÐ¾ß¿¡¼­ Á¡Á¡ ´õ »ç¿ëÀÌ ´Ã°í ÀÖ´Ù.

ŸÀÜÀº ¶ÇÇÑ ÄÄÇ»ÅÍ °úÇÐÀÇ ¿¬±¸¿¡ ¹®È­Àû º¯È­¸¦ °¡Á®¿Ô´Ù. ±×°ÍÀº ÀûÀýÇÑ 'Å« ¾ÆÀ̵ð¾î (big idea)' ¸¦ ¾òÀº ´ÙÀ½, ±×°ÍÀ» °¡Àå È¿À²ÀûÀ¸·Î Áö¿øÇÒ ÀÚ·á ±¸Á¶¸¦ ¸¸µé¾î ³»´Â ¹æ½ÄÀÌ´Ù. ±×¸¦ ºñ·ÔÇØ ¿©·¯ »ç¶÷ÀÌ ±×·¯ÇÑ Àü·«À¸·Î ´ÙÀÌÅ©½ºÆ®¶óÀÇ ÃÖ´Ü °æ·Î ¾Ë°í¸®Áò°ú ¶Ç ´Ù¸¥ ±âº» ¾Ë°í¸®Áòµé¿¡¼­ Áß´ëÇÑ °³¼±À» ¹Ð¾îºÙ¿´´Ù.

±×ÀÇ ¿¬±¸´Â ¹Ì´Ï¸Ö¸®Áò (minimalism), ¼¼·ÃµÊ, ±×¸®°í º¸Æí¼ºÀ» ÇâÇÑ ¹«¾ðÀÇ Ãß±¸ µîÀ¸·Î Ư¡ÁöÀ» ¼ö ÀÖ´Ù.

"ÁÁÀº ¾ÆÀ̵ð¾î´Â º¸´Ù ´Ü¼øÇØÁ® ¿ø·¡ ¸ñÇ¥Çß´ø °Í ÀÌ¿ÜÀÇ ¹®Á¦µé±îÁö ÇØ°áÇÒ ¼ö ÀÖ´Â ¹æ¹ýÀ» °¡Áö°í ÀÖ½À´Ï´Ù."

"³­ º¸´Ù ÀÀ¿ë·Â ÀÖ´Â À¯ÇüÀÇ ¼öÇÐÀ̶ó´Â ÀÌÀ¯ ¶§¹®¿¡ ÄÄÇ»ÅÍ °úÇÐÀ» ÇÏ°í ½Í¾ú½À´Ï´Ù. ´ëü·Î ³í¸®¿Í Á¤¸® Áõ¸íÀÇ Ãø¸é¿¡¼­ ÀΰøÁö´É¿¡ Èï¹Ì¸¦ ´À²¼Áö¿ä. ÇÏÁö¸¸ Á¤ÀÛ ½ºÅÄÆ۵忡 µé¾î°¡ AI °úÁ¤À» ½ÃÀÛÇÏ°Ô µÇ¾úÀ» ¶§¿¡´Â ±×°ÍÀÌ ¾ÆÁÖ ¸ðÈ£ÇÑ °ÍÀ̶ó´Â °á·ÐÀ» ³»·È½À´Ï´Ù."

"Å©´©½º´Â ¿ì¼± °í¹«ÀûÀ̾ú½À´Ï´Ù. ±×°¡ ¾ÆÁÖ ±¸Ã¼ÀûÀÎ ºÐ¼®¿¡ °ü½ÉÀÇ ÃÊÁ¡À» µÎ¾ú´Ù´Â Á¡¿¡¼­ °í¹«ÀûÀ̾úÁö¿ä. ±×´Â Ç×»ó Á¤È®ÇÑ °á°ú¸¦ ¾ò¾î³»´Â ¼öÇÐÀÇ ¾ö¹Ð¼º¿¡ Èï¹Ì¸¦ º¸ÀÌ°í ÀÖ¾ú½À´Ï´Ù."

"³­ ¸ÅÄ¿½ÃÀÇ ±âÈ£ ó¸® °úÁ¤À» ÅÃÇß½À´Ï´Ù. ±× °­ÀÇ´Â ´ëºÎºÐ ¸®½ºÇÁ¿¡ ´ëÇÑ ³»¿ëÀ̾úÁö¿ä. ±×´Â Çлýµé¿¡°Ô ±×·¡ÇÁ°¡ Æò¸éÀÎÁö ¾Æ´ÑÁö¸¦ ½Äº°ÇÏ´Â ÇÁ·Î±×·¥À» ¾²µµ·Ï Á¦¾ÈÇÏ¿´½À´Ï´Ù." ............ (Dennis Shasha 1995)

term :

¼öÇÐ (Mathematics)   ¾Ë°í¸®Áò (Algorithm)   ±×·¡ÇÁ (Graph)   ÀΰøÁö´É (Artificial Intelligence)   ±íÀÌ¿ì¼± Ž»ö (Depth First Search)   John Hopcroft   John McCarthy   Donald Knuth   A.M. Turing Award

site :

Robert E. Tarjan  Homepage

Wikipedia : Robert Tarjan

paper :