{"id":33848,"date":"2019-04-11T00:38:44","date_gmt":"2019-04-10T16:38:44","guid":{"rendered":"https:\/\/case.ntu.edu.tw\/blog\/?p=33848"},"modified":"2019-04-22T11:49:44","modified_gmt":"2019-04-22T03:49:44","slug":"%e8%ae%93%e4%bd%a0%e4%b8%8d%e8%bf%b7%e8%b7%af%e7%9a%84%e8%90%ac%e8%83%bd%e5%9c%b0%e5%9c%96","status":"publish","type":"post","link":"https:\/\/case.ntu.edu.tw\/blog\/?p=33848","title":{"rendered":"\u8b93\u4f60\u4e0d\u8ff7\u8def\u7684\u842c\u80fd\u5730\u5716"},"content":{"rendered":"<p><strong>\u64b0\u6587\uff5c\u8cf4\u52a0\u7fcc<\/strong><\/p>\n<p>\u6211\u60f3\u5927\u5bb6\u90fd\u6709\u9019\u6a23\u7684\u7d93\u9a57\uff1a\u548c\u670b\u53cb\u7d04\u5728\u4e00\u500b\u5730\u9ede\u898b\u9762\uff0c\u4f46\u4ed6\u537b\u5728\u9644\u8fd1\u8ff7\u4e86\u8def\uff0c\u6700\u5f8c\u53ea\u597d\u6253\u96fb\u8a71\u7d66\u4f60\uff0c\u544a\u8a34\u4f60\u7576\u4e0b\u7684\u4f4d\u7f6e\u8acb\u4f60\u6307\u8def\u3002\u4f46\u662f\u5982\u679c\u4eba\u5728\u570b\u5916\u5c31\u6bd4\u8f03\u9ebb\u7169\u4e86\uff0c\u4ed6\u53ef\u80fd\u770b\u4e0d\u61c2\u8def\u6a19\u548c\u5e97\u540d\u3002<\/p>\n<p>\u9019\u6642\u5019\uff0c\u5982\u679c\u7576\u5730\u7684\u8857\u9053\u90fd\u88ab\u67d3\u6210\u7279\u5b9a\u7684\u984f\u8272\uff0c\u4ed6\u53ea\u8981\u6309\u8457\u56fa\u5b9a\u7684\u6a21\u5f0f\u8d70\u5c31\u80fd\u5230\u76ee\u7684\u5730\uff0c\u90a3\u4e0d\u662f\u65b9\u4fbf\u55ce\uff1f\u4f60\u53ef\u4ee5\u5728\u96fb\u8a71\u88e1\u8ddf\u4ed6\u8aaa\uff1a\u300c\u6cbf\u8457\u85cd\u8272\u90a3\u689d\u8def\u8d70\u5230\u4ea4\u53c9\u53e3\u4e4b\u5f8c\uff0c\u63db\u8d70\u7d05\u8272\u90a3\u689d\uff0c\u518d\u8d70\u5230\u4e0b\u4e00\u500b\u4ea4\u53c9\u53e3\u6642\uff0c\u7e7c\u7e8c\u8d70\u7d05\u8272\u90a3\u689d\u3002\u7d05\u8272\u8d70\u5b8c\u63a5\u85cd\u8272\uff0c\u85cd\u8272\u4e00\u76f4\u8d70\u5230\u4ea4\u53c9\u53e3\u63db\u7d05\u8272\uff0c\u7d05\u8272\u8d70\u5230\u4e00\u500b\u4ea4\u53c9\u53e3\u7e7c\u7e8c\u8d70\u7d05\u8272\uff0c\u9019\u6a23\u5c31\u53ef\u4ee5\u5230\u4e86\u3002\u300d\u8b1b\u767d\u4e00\u9ede\u5c31\u662f\u8aaa\uff0c\u4ed6\u53ea\u8981\u4e0d\u65b7\u7167\u8457\u300c\u85cd\u2014\u7d05\u2014\u7d05\u300d\u7684\u6a21\u5f0f\u8d70\u4e0b\u53bb\uff0c\u5c31\u7b97\u4ed6\u4e0d\u6e05\u695a\u81ea\u5df1\u73fe\u5728\u54ea\u88cf\uff0c\u6700\u5f8c\u9084\u662f\u80fd\u5230\u6307\u5b9a\u5730\u9ede\u3002<\/p>\n<p>\u6216\u8a31\u55ae\u7d14\u7528\u8aaa\u7684\u5f88\u96e3\u60f3\u50cf\uff0c\u4e0d\u5982\u76f4\u63a5\u770b\u4e0b\u5716\u3002\u6309\u7167\u300c\u85cd\u2014\u7d05\u2014\u7d05\u300d\u7684\u6a21\u5f0f\u91cd\u8907\u4e09\u6b21\uff0c\u4e0d\u7ba1\u4f60\u4eba\u5728\u54ea\u88cf\uff0c\u90fd\u80fd\u5230\u9ec3\u8272\u7684\u9ede\uff1b\u800c\u6309\u7167\u300c\u85cd\u2014\u85cd\u2014\u7d05\u300d\uff0c\u7684\u6a21\u5f0f\u91cd\u8907\u4e09\u6b21\uff0c\u5247\u4e00\u5b9a\u6703\u5230\u7da0\u9ede\u3002<\/p>\n<figure id=\"attachment_33856\" aria-describedby=\"caption-attachment-33856\" style=\"width: 400px\" class=\"wp-caption aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"wp-image-33856\" src=\"http:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2019\/03\/19f1.png\" alt=\"\" width=\"400\" height=\"399\" srcset=\"https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2019\/03\/19f1.png 902w, https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2019\/03\/19f1-150x150.png 150w, https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2019\/03\/19f1-300x300.png 300w, https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2019\/03\/19f1-768x765.png 768w, https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2019\/03\/19f1-250x250.png 250w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption id=\"caption-attachment-33856\" class=\"wp-caption-text\">\u5716\u7247\u51fa\u8655\uff1a wikipedia<\/figcaption><\/figure>\n<p>\u9053\u8def\u8457\u8272\u7684\u554f\u984c\uff0c\u662f\u5716\u8ad6\u4e2d\u975e\u5e38\u6709\u540d\u7684\u554f\u984c\u4e4b\u4e00\u3002\u7531\u7bc0\u9ede\u548c\u9023\u63a5\u7bc0\u9ede\u7684\u908a\u6240\u69cb\u6210\u7684\u5716\u5f62\uff0c\u53ef\u4ee5\u884d\u4f38\u6210\u73fe\u5be6\u4e16\u754c\u4e2d\u9047\u5230\u7684\u7cfb\u7d71\u3002\u6bd4\u5982\u8857\u9053\u7684\u4ea4\u53c9\u53e3\u53ef\u4ee5\u770b\u505a\u662f\u7bc0\u9ede\uff0c\u800c\u8857\u9053\u770b\u6210\u662f\u908a\u3002\u7db2\u969b\u7db2\u8def\u7684\u4e16\u754c\u88e1\uff0c\u7bc0\u9ede\u5c31\u662f\u8def\u7531\u5668\uff0c\u908a\u662f\u8def\u7531\u5668\u4e4b\u9593\u7684\u9023\u7d50\u3002\u4ee5\u822a\u7a7a\u7db2\u8def\u4f86\u8aaa\uff0c\u7bc0\u9ede\u5c31\u662f\u6a5f\u5834\uff0c\u800c\u908a\u662f\u6a5f\u5834\u5230\u6a5f\u5834\u4e4b\u9593\u7684\u822a\u7a0b\u3002<\/p>\n<p>\u4ee4\u4eba\u597d\u5947\u7684\u662f\uff0c\u6bcf\u500b\u9ede\u548c\u908a\u69cb\u6210\u7684\u5716\u5f62\u90fd\u5b58\u5728\u50cf\u9019\u6a23\u7406\u60f3\u7684\u300c\u842c\u80fd\u5730\u5716\u300d\u55ce\uff1f\u53ea\u8981\u5c07\u908a\u4e0a\u8272\uff0c\u5c31\u53ef\u4ee5\u7167\u8457\u7c21\u55ae\u91cd\u8907\u7684\u6307\u4ee4\u5230\u9054\u76ee\u7684\u5730\uff1f1970\u5e74\u73ed\u5091\u660e\uff0e\u61f7\u65af\u548c\u7f85\u4f0a\uff0e\u963f\u5fb7\u52d2\u6700\u65e9\u63d0\u51fa\u9019\u500b\u554f\u984c\uff0c\u672c\u4f86\u53ea\u662f\u8981\u627e\u5730\u5716\uff0c\u9806\u4fbf\u60f3\u5230\u8981\u8a2d\u8a08\u4e00\u500b\u96fb\u8166\u7684\u81ea\u52d5\u9664\u932f\u7a0b\u5f0f\u3002\u60f3\u4e0d\u5230\u81ea\u5df1\u63d0\u51fa\u7684\u554f\u984c\uff0c\u82b1\u4e86\u597d\u5e7e\u5e74\u9084\u6c92\u8fa6\u6cd5\u8b49\u660e\u3002\u56e0\u70ba\u9019\u500b\u60f3\u6cd5\u76f8\u7576\u6709\u8da3\uff0c\u5f15\u8d77\u4e00\u4e9b\u6578\u5b78\u5bb6\u7684\u95dc\u6ce8\uff0c\u524d\u524d\u5f8c\u5f8c\u51fa\u4e86\u5e7e\u7bc7\u76f8\u95dc\u8ad6\u6587\u3002<\/p>\n<p>\u96d6\u7136\u554f\u984c\u7684\u6558\u8ff0\u770b\u4f3c\u55ae\u7d14\uff0c\u537b\u5728\u6578\u5b78\u754c\u61f8\u800c\u4e0d\u89e3\u5c07\u8fd140\u5e74\uff0c\u76f4\u5230\u963f\u592b\u62c9\u7f55\uff0e\u5854\u514b\u7279\u66fc\u51fa\u73fe\uff0c\u4ed6\u8b49\u660e\u4efb\u4e00\u500b\u9ede\u548c\u7de8\u69cb\u6210\u7684\u5716\u5f62\u53ea\u8981\u5b8c\u6210\u67d0\u4e9b\u7279\u5b9a\u689d\u4ef6\uff0c\u90fd\u80fd\u4ee5\u300c\u842c\u80fd\u5730\u5716\u300d\u822c\u7684\u65b9\u5f0f\u8457\u8272\u3002\u9019\u500b\u8b49\u660e\u4e0d\u53ea\u662f\u6578\u5b78\u4e0a\u7684\u6210\u5c31\uff0c\u5728\u8a08\u7b97\u6a5f\u9818\u57df\u4e5f\u6709\u7279\u5225\u610f\u7fa9\u3002\u7b49\u65bc\u662f\u8aaa\u660e\u4e86\u67d0\u4e9b\u60c5\u6cc1\u4e0b\uff0c\u932f\u8aa4\u6578\u64da\u548c\u5e72\u64fe\u4e0d\u5f71\u97ff\u7d50\u679c\uff0c\u5c31\u50cf\u8ff7\u8def\u7684\u670b\u53cb\u5c31\u7b97\u4e0d\u77e5\u9053\u81ea\u5df1\u4f4d\u7f6e\uff0c\u53ea\u8981\u4f9d\u64da\u91cd\u8907\u6307\u4ee4\uff0c\u90fd\u80fd\u5230\u9054\u76ee\u7684\u5730\u3002<\/p>\n<p>&nbsp;<\/p>\n<p><strong>\u53c3\u8003\u8cc7\u6599\uff1a<\/strong><strong>&nbsp;<\/strong><\/p>\n<ol>\n<li><a href=\"https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022000016300447\">Vojt\u011bch Vorel, &amp;Adam Roman. Complexity of road coloring with prescribed reset words. <\/a><a href=\"https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022000016300447\"><em>Journal of Computer and System Sciences<\/em><\/a><a href=\"https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022000016300447\">. 2016<\/a><\/li>\n<li><a href=\"https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0890540115000462\">A.Roman, &amp;M. Drewienkowski. A complete solution to the complexity of Synchronizing Road Coloring for non-binary alphabets. <\/a><a href=\"https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0890540115000462\"><em>Information and Computation. 242<\/em><\/a><a href=\"https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0890540115000462\">, 383-393. 2015<\/a><\/li>\n<\/ol>\n<p><strong> <a href=\"https:\/\/line.me\/R\/ti\/p\/%40fcx6182w\" target=\"_blank\" rel=\"noopener noreferrer\"><img decoding=\"async\" class=\"alignnone\" src=\"https:\/\/scdn.line-apps.com\/n\/line_add_friends\/btn\/zh-Hant.png\" alt=\"\u52a0\u5165\u597d\u53cb\" width=\"212\" height=\"36\" border=\"0\"><\/a><\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9053\u8def\u8457\u8272\u7684\u554f\u984c\uff0c\u662f\u5716\u8ad6\u4e2d\u975e\u5e38\u6709\u540d\u7684\u554f\u984c\u4e4b\u4e00\u3002\u7531\u7bc0\u9ede\u548c\u9023\u63a5\u7bc0\u9ede\u7684\u908a\u6240\u69cb\u6210\u7684\u5716\u5f62\uff0c\u53ef\u4ee5\u884d\u4f38\u6210\u73fe\u5be6\u4e16\u754c\u4e2d\u9047\u5230\u7684\u7cfb\u7d71\u3002\u6bd4\u5982\u8857\u9053\u7684\u4ea4\u53c9\u53e3\u53ef\u4ee5\u770b\u505a\u662f\u7bc0\u9ede\uff0c\u800c\u8857\u9053\u770b\u6210\u662f\u908a\u3002\u7db2\u969b\u7db2\u8def\u7684\u4e16\u754c\u88e1\uff0c\u7bc0\u9ede\u5c31\u662f\u8def\u7531\u5668\uff0c\u908a\u662f\u8def\u7531\u5668\u4e4b\u9593\u7684\u9023\u7d50\u3002\u4ee5\u822a\u7a7a\u7db2\u8def\u4f86\u8aaa\uff0c\u7bc0\u9ede\u5c31\u662f\u6a5f\u5834\uff0c\u800c\u908a\u662f\u6a5f\u5834\u5230\u6a5f\u5834\u4e4b\u9593\u7684\u822a\u7a0b\u3002\u4ee4\u4eba\u597d\u5947\u7684\u662f\uff0c\u6bcf\u500b\u9ede\u548c\u908a\u69cb\u6210\u7684\u5716\u5f62\u90fd\u5b58\u5728\u50cf\u9019\u6a23\u7406\u60f3\u7684\u300c\u842c\u80fd\u5730\u5716\u300d\u55ce\uff1f<\/p>\n","protected":false},"author":20,"featured_media":33858,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3293,148,2977],"tags":[4226,4228,4227],"aioseo_notices":[],"jetpack_featured_media_url":"https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2019\/03\/78645345.jpg","_links":{"self":[{"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/posts\/33848"}],"collection":[{"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/users\/20"}],"replies":[{"embeddable":true,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=33848"}],"version-history":[{"count":1,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/posts\/33848\/revisions"}],"predecessor-version":[{"id":33857,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/posts\/33848\/revisions\/33857"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/media\/33858"}],"wp:attachment":[{"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=33848"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=33848"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=33848"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}