(¥»¥Ã¥·¥ç¥óɽ¤Ø)

Ê¿À®27ǯÅÙ (Âè66²ó) Åŵ¤¡¦¾ðÊó´ØÏ¢³Ø²ñÃæ¹ñ»ÙÉôÏ¢¹çÂç²ñ

ÉôÌç: ¥»¥Ã¥·¥ç¥ó 1201  18. ¾ðÊó¿ôÍý-(1)
Æü»þ: 2015ǯ10·î17Æü(ÅÚ) 9:00 - 10:05
Éô²°: E21 (¢ªÃÏ¿Þ)
ºÂĹ: ²¦ Ìö (»³¸ýÂç³Ø)

18-1 (»þ´Ö: 9:00 - 9:13)
Âê̾¥Ó¥ë¥Ç¥£¥ó¥°¥Ñ¥º¥ë¤Î·×»»Ê£»¨¤µ
Ãø¼Ô*¾¾°æ ͦÂÀ, ´äËÜ Ãè¤ (¹­ÅçÂç³ØÂç³Ø±¡¹©³Ø¸¦µæ²Ê¾ðÊ󹩳ØÀ칶)
¥­¡¼¥ï¡¼¥É¥Ó¥ë¥Ç¥£¥ó¥°¥Ñ¥º¥ë, ¥Ú¥ó¥·¥ë¥Ñ¥º¥ë, NP´°Á´
¥¢¥Ö¥¹¥È¥é¥¯¥È¥Ó¥ë¥Ç¥£¥ó¥°¥Ñ¥º¥ë¤ÏÌð°õ¤ÎÊý¸þ¤«¤é¿ô»ú¤Î¿ô¤À¤±¥Ó¥ë¤¬¸«¤¨¤ë¤è¤¦¤Ë¹â¤µ¤Î°ã¤¦¥Ó¥ë¤òʤ٤ë¥Ñ¥º¥ë¤Ç¤¢¤ë. ¹â¤¤¥Ó¥ë¤¬¼êÁ°¤Ë¤¯¤ë¤ÈÄ㤤¥Ó¥ë¤Ï¸«¤¨¤Ê¤¯¤Ê¤ë.N*N¥µ¥¤¥º¤ÎÈ×Ì̤ǰìÈÖÂ礭¤¤¿ô»ú¡Ê°ìÈֹ⤤¥Ó¥ë¡Ë¤ÏN¤Ç¤¢¤ë¡£¹Ô¤ÈÎó¤Ë¤Ï¥Þ¥¹¤Î¿ô¤À¤±°ã¤¦¹â¤µ¤Î¥Ó¥ë¤¬Â¸ºß¤¹¤ë¤Î¤Ç¡¢¹Ô¤ÈÎó¤Ç³Æ¿ô»ú¤Ï¤½¤ì¤¾¤ì°ìÅÙ¤º¤Ä»È¤ï¤ì¤ë. °Ê¾å¤Î¥ë¡¼¥ë¤òÍѤ¤¤Æ,Í¿¤¨¤é¤ì¤¿ÌäÂ꤫¤é²ò¤òƳ¤­½Ð¤¹¤³¤È¤¬¤³¤Î¥²¡¼¥à¤ÎÌÜŪ¤Ç¤¢¤ë. ËܹƤǤϥӥë¥Ç¥£¥ó¥°¥Ñ¥º¥ë¤ÎNP´°Á´À­¤ò¼¨¤¹.

18-2 (»þ´Ö: 9:13 - 9:26)
Âê̾GLL¹½Ê¸²òÀÏË¡»ë³Ð²½¥Ä¡¼¥ë¤Î³«È¯
Ãø¼Ô*²Ï¸ý ͺÂç, °ËÆ£ ¶Ç (»³¸ýÂç³ØÂç³Ø±¡Íý¹©³Ø¸¦µæ²Ê)
¥­¡¼¥ï¡¼¥É¹½Ê¸²òÀÏ
¥¢¥Ö¥¹¥È¥é¥¯¥ÈGLL ¹½Ê¸²òÀÏË¡¤È¤Ï¡¤Ê¸Ë¡¤ÎÈó·èÄêŪ¤ÊÉôʬ¤ËÂФ·¤ÆÊ£¿ô¤Î¥×¥í¥»¥¹¤òÊÂÎóŪ¤ËºîÆ°¤µ¤»¡¤²òÀϤËɬÍפʥǡ¼¥¿¤ò°ì¤Ä¤Î¥°¥é¥Õ¾õ¥¹¥¿¥Ã¥¯¤Ë³ÊǼ¤·¤Ê¤¬¤é²òÀϤò¹Ô¤¦¹½Ê¸²òÀÏË¡¤Ç¤¢¤ë[1]¡¥Ëܸ¦µæ¤Ç¤Ï, ʸˡÁ«°Ü¿Þ, ¤½¤ÎʸˡÁ«°Ü¿Þ¾å¤Ë¤ª¤±¤ëGLL ¹½Ê¸²òÀÏË¡¤ÎÁ´Æ°ºîÅÀ¤ÎÁ«°Üµ°À׿ޡ¤¥°¥é¥Õ¾õ¥¹¥¿¥Ã¥¯¿Þ¤Î£³ÅÀ¤òÍѤ¤¤ÆGLL ¹½Ê¸²òÀÏË¡¤òľ´¶Åª¤Ë¤ï¤«¤ê¤ä¤¹¤¯¤¹¤ë¤¿¤á¤Î»ë³Ð²½¤òÄó°Æ¤·¡¤¤½¤ì¤é¤Î»ë³Ð²½¤µ¤ì¤¿GLL ¹½Ê¸²òÀÏ´ï¤ò¼ÂÁõ¤¹¤ë.

18-3 (»þ´Ö: 9:26 - 9:39)
Âê̾¥³¥Ô¡¼²ó¿ô¸ÂÄê¥Ñ¥¿¡¼¥óʸ̮¼«Í³Ê¸Ë¡
Ãø¼Ô*²ÏÌî ÍÛÂÀ, ¶ÌÌÚ ½¨Ëá (»³¸ýÂç³Ø¹©³ØÉô), °ËÆ£ ¶Ç (»³¸ýÂç³ØÂç³Ø±¡Íý¹©³Ø¸¦µæ²Ê)
¥­¡¼¥ï¡¼¥Éʸ̮¼«Í³Ê¸Ë¡, ³ÈÄ¥Àµµ¬É½¸½
¥¢¥Ö¥¹¥È¥é¥¯¥È¥Ñ¥¿¡¼¥óɽ¸½(pattern expression) ¤Ïregex Åù¤Ë¤ª¤±¤ë¸åÊý »²¾È(back reference) ¤Îµ¡Ç½¤ò·Á¼°²½¤¹¤ë¤¿¤á¤ËƳÆþ¤µ¤ì¤¿ ³ÈÄ¥Àµµ¬É½¸½¤Ç¤¢¤ë[1, 2]¡¥¥Ñ¥¿¡¼¥óʸ̮¼«Í³Ê¸Ë¡(pattern context-free grammar) ¤Ï¥Ñ¥¿¡¼¥óɽ¸½¤Î¹Í¤¨Êý¤òʸ̮¼«Í³ ʸˡ¤ËÂФ·¤ÆƳÆþ¤·¤¿¤â¤Î¤Ç¤¢¤ë[3]¡¥ Ëܸ¦µæ¤Ç¤Ï¡¤¤Þ¤ºÀþ·Áʸˡ¤ÈÀµµ¬Ê¸Ë¡¤Ë¥³¥Ô¡¼µ¡Ç½¤ò»ý ¤¿¤»¤¿¾ì¹ç¤Ë¤Ï¡¤¸À¸ìÀ¸À®Ç½ÎϤϸþ¾å¤·¤Ê¤¤¤³¤È¤ò¼¨¤¹¡¥ ¤Þ¤¿¡¤¥Ñ¥¿¡¼¥óɽ¸½¤ò¤½¤ì¤ÈÅù²Á¤Ê¥Ñ¥¿¡¼¥óCFG ¤ËÊÑ´¹¤¹ ¤ë¼êË¡¤ò¼¨¤¹¡¥ºÇ¸å¤Ë¡¤¥Ñ¥¿¡¼¥óɽ¸½¸À¸ì¤ËÂФ¹¤ëÈ¿ÉüÊä Âê¤ò¾Ò²ð¤·¡¤¤½¤ÎŬ±þÎã¤òµó¤²¤¿¸å¤Ë¡¤¥³¥Ô¡¼²ó¿ô¤¬1 ²ó ¤Ç¤¢¤ë¤è¤¦¤Ê¥Ñ¥¿¡¼¥óʸ̮¼«Í³Ê¸Ë¡¤ËÂФ¹¤ëÈ¿ÉüÊäÂê¤ò¾Ú ÌÀ¤¹¤ë¡¥

18-4 (»þ´Ö: 9:39 - 9:52)
Âê̾3¼¡¸µLarger than Life ¥»¥ë¥ª¡¼¥È¥Þ¥È¥ó¤Ë¤ª¤±¤ë¥Ð¥°¤Îõº÷
Ãø¼Ô*µ×ÊÝÅÄ ÃÒÂç (¹­ÅçÂç³ØÂç³Ø±¡¹©³Ø¸¦µæ²Ê¾ðÊ󹩳ØÀ칶), º£°æ ¹îĪ (¹­ÅçÂç³ØÂç³Ø±¡¹©³Ø¸¦µæ±¡)
¥­¡¼¥ï¡¼¥É¥»¥ë¥ª¡¼¥È¥Þ¥È¥ó, ¥é¥¤¥Õ¥²¡¼¥à
¥¢¥Ö¥¹¥È¥é¥¯¥È¥»¥ë¥ª¡¼¥È¥Þ¥È¥ó¤È¤Ï¡¤¶õ´Ö¾å¤Ë°ìÍͤËʤó¤À¥»¥ë¤È´Êñ¤Êµ¬Â§¤Ë¤è¤ë¡¢Î¥»¶Åª·×»»¥â¥Ç¥ë¤Ç¤¢¤ë¡£2¼¡¸µ¥»¥ë¥ª¡¼¥È¥Þ¥È¥ó¤Î¥ë¡¼¥ë¤Î°ì¤Ä¤Ç¤¢¤ëLarger than Life(LtL)¤Ï5¤Ä¤Î¥Ñ¥é¥á¡¼¥¿¤Çɽ¤µ¤ì¡¢¤½¤ÎÃͤˤè¤êÈó¾ï¤Ë¿Íͤʥѥ¿¡¼¥ó¤ò»ý¤Ä¡£LtL¤Ë¤Ï¥Ð¥°¤È¸Æ¤Ð¤ì¤ëÆÃÊ̤ʰÜÆ°¥Ñ¥¿¡¼¥ó¤¬Â¸ºß¤¹¤ë¡£Ëܸ¦µæ¤Ï3¼¡¸µ¤Ë³ÈÄ¥¤·¤¿LtL¤Ë¤ª¤¤¤Æ¡¢¥Ð¥°¤¬À¸À®¤µ¤ì¤ë¾ò·ï¤òËþ¤¿¤¹¥Ñ¥é¥á¡¼¥¿¤ÎÈϰϤòõº÷¤·¡¢¿·¤¿¤Ê¥Ð¥°¤òȯ¸«¤·¤¿¡£

18-5 (»þ´Ö: 9:52 - 10:05)
Âê̾Á´¾Î¾õÂ֤ΤߤÎ1Êý¸þ¸òÂåÀ­¥Þ¥ë¥Á¥×¥í¥»¥Ã¥µÍ­¸Â¥ª¡¼¥È¥Þ¥È¥ó
Ãø¼Ô*µ×ËÜ ½ã¼ù (ÆÁ»³¹©¶È¹âÅùÀìÌç³Ø¹»¾ðÊóÅŻҹ©³ØÀ칶), µÁ±Ê ¾ï¹¨ (ÆÁ»³¹©¶È¹âÅùÀìÌç³Ø¹»¾ðÊóÅŻҹ©³Ø²Ê), ºäËÜ âÃ¿Í (µÜºêÂç³Ø¹©³ØÉô)
¥­¡¼¥ï¡¼¥É¥Þ¥ë¥Á¥×¥í¥»¥Ã¥µÍ­¸Â¥ª¡¼¥È¥Þ¥È¥ó, ¸òÂåÀ­·×»», 1Êý¸þ·×»», Á´¾Î¾õÂÖ
¥¢¥Ö¥¹¥È¥é¥¯¥È¥Þ¥ë¥Á¥×¥í¥»¥Ã¥µÍ­¸Â¥ª¡¼¥È¥Þ¥È¥ó(MPFA)¤Ï, Ê£¿ô¤ÎÍ­¸Â¥ª¡¼¥È¥Þ¥È¥ó¤È¥¹¥¤¥Ã¥Á¥ó¥°´Ø¿ô¤Ë¤è¤ê¹½À®¤µ¤ì¤Æ¤ª¤ê, ºÇ¤âñ½ã¤ÊÊÂÎó·×»»¥â¥Ç¥ë¤Î1¤Ä¤È¹Í¤¨¤ë¤³¤È¤¬¤Ç¤­¤ë.¤³¤ì¤Þ¤Ç¤ËMPFA¤Ë¤ª¤±¤ë·èÄêÀ­¤ª¤è¤ÓÈó·èÄêÀ­·×»»¤Ë¤Ä¤¤¤Æ¤Î¸¦µæ¤¬¤Ê¤µ¤ì¤Æ¤¤¤ë¤¬, ¸òÂåÀ­·×»»¤Ë¤Ä¤¤¤Æ¤Ï¤Û¤È¤ó¤É¹Í»¡¤µ¤ì¤Æ¤¤¤Ê¤¤. Ëܸ¦µæ¤Ç¤ÏÁ´¾Î¾õÂÖ¤À¤±¤ËÀ©¸Â¤µ¤ì¤¿1Êý¸þ¸òÂåÀ­MPFA¤Î´ðËÜŪ¤ÊÀ­¼Á¤Ë¤Ä¤¤¤Æ¹Í»¡¤·, ­¡¥×¥í¥»¥Ã¥µ¿ô¤Ë´ð¤Å¤¯¼õÍýǽÎϤγ¬ÁØÀ­¤¬Â¸ºß¤¹¤ë¤³¤È, ­¢Á´¾Î¾õÂ֤ΤߤθòÂåÀ­¤Ï·èÄêÀ­¤è¤ê¤â¿¿¤Ë¼õÍýǽÎϤ¬¹â¤¤¤³¤È, ­£Èó·èÄêÀ­¤ÈÁ´¾Î¾õÂ֤ΤߤθòÂåÀ­¤Î¼õÍýǽÎϤÏÈæ³ÓÉÔǽ¤Ç¤¢¤ë¤³¤È¤ò¼¨¤·¤Æ¤¤¤ë. ¤Þ¤¿, ´ØÏ¢¤¹¤ë̤²ò·èÌäÂê¤òÄ󼨤·¤Æ¤¤¤ë.