
Èí¼þÕýÔÚͳÖÎÊÀ½ç¡£¶øÈí¼þµÄºËÐÄÔòÊÇËã·¨¡£Ë㷨ǧǧÍòÍò£¬ÓÖÓÐÄÄЩËã·¨ÊôÓÚ¡°»Ê¹ÚÉϵÄÕäÖ顱Ĩ£¿Marcos Otero¸ø³öÁËËûµÄ¿´·¨¡£
ʲôÊÇËã·¨£¿
ͨË×¶øÑÔ£¬Ëã·¨ÊÇÒ»¸ö¶¨ÒåÃ÷È·µÄ¼ÆËã¹ý³Ì£¬¿ÉÒÔһЩֵ»òÒ»×éÖµ×÷ΪÊäÈë²¢²úÉúһЩֵ»òÒ»×éÖµ×÷ΪÊä³ö¡£Òò´ËËã·¨¾ÍÊǽ«ÊäÈëתΪÊä³öµÄһϵÁмÆËã²½Öè¡£
¡ªThomas H. Cormen£¬Chales E. Leiserson£¬Ëã·¨ÈëÃŵÚÈý°æ
¼ò¶øÑÔÖ®£¬Ëã·¨¾ÍÊÇ¿ÉÍê³ÉÌØ¶¨ÈÎÎñµÄһϵÁв½Ö裬ËüÓ¦¸Ã¾ß±¸Èý´óÌØÕ÷£º
1¡¢ÓÐÏÞ
2¡¢Ö¸ÁîÃ÷È·
3¡¢ÓÐЧ
ÒÔÏÂÊÇMarcos OteroÍÆ¼öµÄÊ®´óËã·¨£º
1¡¢¹é²¢ÅÅÐò¡¢¿ìËÙÅÅÐò¼°¶Ñ»ýÅÅÐò

×îºÃµÄÅÅÐòËã·¨¸úÐèÇóÃÜÇÐÏà¹Ø£¬ºÜÄÑÆÀÅС£µ«ÊÇ´ÓʹÓÃÉÏ˵£¬ÕâÈýÖÖµÄʹÓÃÆµÂʸü¸ß¡£
¹é²¢ÅÅÐòÓÉ·ë?ŵÒÀÂüÓÚ1945Äê·¢Ã÷¡£ÕâÊÇÒ»ÖÖ»ùÓڱȽϵÄÅÅÐòËã·¨£¬²ÉÓ÷ֶøÖÎÖ®µÄ°ì·¨½â¾öÎÊÌ⣬Æä½×ÊÇO(n^2)¡£
¿ìËÙÅÅÐò¿É²ÉÓÃԵطָ·¨£¬Ò²¿É²ÉÓ÷ֶøÖÎÖ®Ëã·¨¡£Õâ²»ÊÇÒ»ÖÖÎȶ¨µÄÅÅÐòËã·¨£¬µ«¶ÔÓÚ»ùÓÚRAM£¨Äڴ棩µÄÊý×éÅÅÐòÀ´Ëµ·Ç³£ÓÐЧ¡£
¶ÑÅÅÐò²ÉÓÃÓÅÏȼ¶¶ÓÁÐÀ´¼õÉÙÊý¾ÝÖеÄËÑË÷ʱ¼ä¡£¸ÃËã·¨Ò²ÊÇÔµØËã·¨£¬²¢·ÇÎȶ¨ÅÅÐò¡£
ÕâЩÅÅÐòËã·¨Ïà¶ÔÓÚÒÔǰµÄðÅÝÅÅÐòËã·¨µÈÓÐÁ˾޴ó¸Ä½ø£¬Êµ¼ÊÉÏÎÒÃǽñÌìµÄÊý¾ÝÍÚ¾ò¡¢È˹¤ÖÇÄÜ¡¢Á´½Ó·ÖÎö¼°°üÀ¨webÔÚÄڵĴó¶àÊý¼ÆË㹤¾ß¶¼Òª¸ÐлËüÃÇ¡£
2¡¢¸µÀïÒ¶±ä»»Óë¿ìËÙ¸µÀïÒ¶±ä»»

ÎÒÃǵÄÕû¸öÊý×ÖÊÀ½ç¶¼Ê¹ÓÃÕâÁ½¸ö¼òµ¥µ«·Ç³£Ç¿´óµÄËã·¨£¬Æä×÷ÓÃÊǽ«ÐźŴÓʱÓòתΪƵÓò»òÕß·´Ö®¡£Êµ¼ÊÉÏ£¬Äã¿´µÃµ½ÕâÆªÎÄÕµøÐлÕâЩËã·¨¡£
»¥ÁªÍø¡¢ÄãµÄWiFi¡¢ÖÇÄÜÊÖ»ú¡¢µç»°¡¢¼ÆËã»ú¡¢Â·ÓÉÆ÷¡¢ÎÀÐÇ£¬¼¸ºõËùÓÐÄÚÖÃÓмÆËã»úµÄ¶«Î÷¶¼»áÒÔ¸÷ÖÖ·½Ê½Ê¹ÓÃÕâÁ½Ëã·¨¡£Èç¹û²»Ñо¿ÕâЩËã·¨£¬Äã¾ÍÄò»µ½µç×Ó¡¢¼ÆËã»òͨÐÅ·½ÃæµÄѧλ¡£
3¡¢µÏ½ÜË¹ÌØÀ£¨Dijkstra£©Ëã·¨

DijkstraÊÇÒ»ÖÖͼÆ×ËÑË÷Ëã·¨¡£Ðí¶àÎÊÌâ¶¼¿ÉÒÔ½¨Ä£ÎªÍ¼Æ×£¬È»ºóÀûÓÃDijkstraѰÕÒÁ½¸ö½ÚµãÖ®¼äµÄ×î¶Ì·¾¶¡£Èç¹ûûÓÐDijkstraËã·¨£¬»¥ÁªÍøµÄÔËӪЧÂʱؽ«´ó´ó½µµÍ¡£ËäÈ»½ñÌìÎÒÃÇÒѾÓÐÁ˸üºÃµÄѰÕÒ×î¶Ì·¾¶µÄ½â¾ö·½°¸£¬µ«³öÓÚÎȶ¨ÐÔµÄÒªÇó£¬DijkstraËã·¨ÈÔÈ»±»ºÜ¶àϵͳʹÓá£
4¡¢RSAËã·¨
Èç¹ûûÓÐÃÜÂëÊõºÍÍøÂ簲ȫ£¬»¥ÁªÍø¾Í²»»áÏñ½ñÌìÒ»ÑùÖØÒª£¬ÒòΪµç×ÓÉÌÎñºÍµç×Ó½»Ò×ÐèÒªÕâЩ¼¼ÊõÀ´È·±£½»Ò×°²È«¡£¶øRSAËã·¨ÊÇ×îÖØÒªµÄÃÜÂëѧËã·¨Ö®Ò»¡£¸ÃËã·¨ÓÉͬÃû¹«Ë¾µÄ´´Ê¼ÈË£¨Ron Rivest¡¢Adi ShamirºÍLeonard Adleman£©¿ª·¢£¬ËüÈÃÃÜÂëѧÆÕ¼°µ½ÁËǧ¼ÒÍò»§²¢µì¶¨ÁËÃÜÂëÊõµÄÓ¦Óûù´¡¡£RSAÒª½â¾öµÄÎÊÌâ¼È¼òµ¥ÓÖ¸´ÔÓ£ºÈçºÎÔÚ¶ÀÁ¢Æ½Ì¨Óë×îÖÕÓû§Ö®¼ä¹²Ïí¹«Ô¿¡£Æä½â¾ö·½°¸ÊǼÓÃÜ¡£RSA¼ÓÃܵĻù´¡ÊÇÒ»¸öÊ®·Ö¼òµ¥µÄÊýÂÛÊÂʵ£º½«Á½¸ö´óËØÊýÏà³ËÊ®·ÖÈÝÒ×£¬µ«ÊÇÏëÒª¶ÔÆä³Ë»ý½øÐÐÒòʽ·Ö½âÈ´¼«ÆäÀ§ÄÑ£¬Òò´Ë¿ÉÒÔ½«³Ë»ý¹«¿ª×÷Ϊ¼ÓÃÜÃÜÔ¿¡£µ«ÔÚ·Ö²¼Ê½¼ÆËãºÍÁ¿×Ó¼ÆËã»úÀíÂÛÈÕÇ÷³ÉÊìµÄ½ñÌ죬RSA¼ÓÃܰ²È«ÐÔÊܵ½ÁËÌôÕ½¡£
5¡¢°²È«¹þÏ£Ëã·¨£¨SHA£©
Õâ¸öʵ¼ÊÉϲ¢²»ËãÊÇËã·¨£¬¶øÊÇÓÉÃÀ¹ú¹ú¼Ò±ê×¼¼¼ÊõÑо¿Ëù¿ª·¢µÄһϵÁÐÃÜÂëÔÓ´Õº¯Êý¡£µ«ÊÇÕâϵÁк¯ÊýÊÇÈ«ÊÀ½çÔË×÷µÄ»ùʯ¡£Ó¦ÓÃÉ̵꣬µç×ÓÓʼþ¡¢·´²¡¶¾¡¢ä¯ÀÀÆ÷µÈÔÚʹÓÃSHAϵÁк¯Êý£¬SHAº¯Êý¿ÉÓÃÀ´È·¶¨ÏÂÔØµÄ¶«Î÷ÊÇ·ñ×Ô¼ºÏëÒªµÄ¶«Î÷£¬»¹ÊÇ˵ÔâÓöÁËÖмäÈ˹¥»÷»òµöÓã¹¥»÷¡£
6¡¢ÕûÊýÒò×Ó·Ö½â
ÕâÊÇÒ»¸öÔÚ¼ÆËãÁìÓòʹÓÃÆµ·±µÄÊýѧËã·¨¡£Èç¹ûûÓÐÕâÒ»Ëã·¨£¬ÃÜÂëÊõ¾Í»á±äµÃ²»°²È«µÃ¶à¡£ÕûÊýÒò×Ó·Ö½âÊÇÓÃÀ´½«Ò»¸öºÏÊý·Ö½â³ÉһϵÁÐËØÒò×ÓµÄһϵÁв½Öè¡£ÕûÊýÒò×Ó·Ö½â¿É±»ÊÓΪÊÇFNPÎÊÌ⣨FNPÊÇÄÑÒÔ½â¾öµÄµäÐÍNPÎÊÌâµÄÀ©Õ¹£©¡£
Ðí¶àÃÜÂëÐÒé¾ù»ùÓÚÄÑÒÔ·Ö½âµÄ´óÐͺÏÊý»òÏà¹ØÎÊÌâ¡£±È·½ËµÇ°ÃæÌáµ½µÄRSAÎÊÌâ¡£Èç¹ûÓÐËã·¨Äܹ»ÓÐЧ·Ö½âÈÎÒâÊý×Ö£¬ÄÇô¾Í»áʹµÃ»ùÓÚRSAµÄ¹«Ô¿ÃÜÂëϵͳÏÝÈë²»°²È«µÄ¾³µØ¡£
¶øÁ¿×Ó¼ÆËãµÄµ®ÉúÔòÁî´ËÎÊÌâµÄ½â¾ö±äµÃÈÝÒ×£¬´Ó¶øÒ²´ò¿ªÁËÒ»¸öȫеÄÁìÓò£¬¿ÉÀûÓÃÁ¿×ÓÊÀ½çµÄÊôÐÔÀ´Áîϵͳ¸ü¼Ó°²È«¡£
7¡¢Á´½Ó·ÖÎö

ÔÚ»¥ÁªÍøÊ±´ú£¬²»Í¬ÊµÌå¼ä¹ØÏµµÄ·ÖÎöÖÁ¹ØÖØÒª¡£´ÓËÑË÷ÒýÇæºÍÉç½»ÍøÂçµ½ÓªÏú·ÖÎö¹¤¾ß£¬Ã¿¸öÈ˶¼ÏëÕÒ³ö»¥ÁªÍøµÄÕæÕý½á¹¹¡£
Á´½Ó·ÖÎöÎÞÒÉÊǹ«ÖÚ¶ÔËã·¨µÄ×î´óÀ§»óÓëÃÔ˼֮һ¡£ÆäÎÊÌâÔÚÓÚ½øÐÐÁ´½Ó·ÖÎöÓв»Í¬µÄ·½Ê½£¬¶øÔö¼ÓÒ»Ð©ÌØÕ÷¾Í»áÁîÿһËã·¨ÂÔÓв»Í¬£¨´Ó¶øÊ¹µÃËã·¨Êܵ½×¨Àû±£»¤£©£¬µ«»ù±¾ÉÏÕâЩËã·¨¶¼ÊÇÀàËÆµÄ¡£
Á´½Ó·ÖÎöËã·¨Ê×ÏÈÓÉGabriel PinskiºÍFrancis NarinÔÚ1976Äê·¢Ã÷¡£Æä±³ºóµÄ˼·ºÜ¼òµ¥£¬¼´°ÑͼÆ×ÒÔ¾ØÕóµÄÐÎʽ±íʾ£¬´Ó¶ø×ªÎªÌØÕ÷ÖµÎÊÌ⣬¶øÌØÕ÷ÖµÓÐÖúÓÚÁ˽âͼÆ×½á¹¹¼°Ã¿¸ö½ÚµãµÄÏà¶ÔÖØÒªÐÔ¡£
GoogleµÄPageRank£¬FacebookչʾÐÂÎÅÔ´£¬Google+£¬FacebookÅóÓÑÍÆ¼ö£¬LinkedIn¹¤×÷¼°ÁªÏµÈËÍÆ¼ö£¬NetflixÓëHuluµÄµçÓ°ÍÆ¼ö£¬YouTubeÊÓÆµÍƼöµÈ¾ùʹÓÃÁËÁ´½Ó·ÖÎöËã·¨¡£ËäȻÿ¸ö¶¼Óв»Í¬µÄÄ¿±êºÍ²ÎÊý£¬µ«Æä±³ºóµÄÊýѧÊÇÒ»ÑùµÄ¡£
¾¡¹ÜGoogleËÆºõÊÇÀûÓôËÀàËã·¨µÄµÚÒ»¼Ò¹«Ë¾£¬µ«ÊÇʵ¼ÊÉϰٶȴ´Ê¼ÈËÀîÑåºêÔÚGoogleµ®Éú2Á½Äêǰ×öµÄËÑË÷ÒýÇæ¡°RankDex¡±ÒѾÀûÓÃÕâÖÖ˼·À´½øÐÐËÑË÷ÅÅÃûÁË¡£
8¡¢±ÈÀý»ý·Ö΢·ÖËã·¨
Èç¹ûÄãÓùý·É»ú¡¢Æû³µ¡¢Î¢ÐÍ·þÎñ»òÊÖ»úÍøÂ磬Èç¹ûÄãÔÚ¹¤³§´ô¹ý»òÕß¼û¹ý»úÆ÷ÈË£¬ÄÇôÄãÒѾ¼ûʶ¹ýÕâÒ»PIDËã·¨µÄ×÷ÓÃÁË¡£
¸ÃËã·¨ÀûÓÃÁË¿ØÖÆ»ØÂ·»úÖÆÀ´ÈÃÆÚÍûÊä³öÐźÅÓëʵ¼ÊÊä³öÐźÅÖ®¼äµÄ´íÎó½µµ½×îС¡£Ö»ÒªÐèÒªÐźŴ¦Àí»òÐèÒªµç×ÓϵͳÀ´¿ØÖÆ×Ô¶¯»¯µÄ»úе¡¢Ë®Á¦»òÈÈÁ¦ÏµÍ³¾ÍÒªÓõ½Ëü¡£
Òò´Ë¿ÉÒÔ˵Èç¹ûûÓÐÕâÒ»Ëã·¨£¬ÈËÀàµÄÏÖ´úÎÄÃ÷½«²»¸´´æÔÚ¡£
9¡¢Êý¾ÝѹËõËã·¨
Êý¾ÝѹËõËã·¨ÎÞÒÉÊǷdz£ÖØÒªµÄ£¬ÒòΪ¼¸ºõÔÚËùÓеĽṹÖж¼ÒªÓõ½¡£³ýÁË×îÃ÷ÏÔµÄѹËõÎĵµÒÔÍâ£¬ÍøÒ³ÏÂÔØÊ±Ò²»áѹËõ£¬ÊÓÆµÓÎÏ·¡¢ÊÓÆµ¡¢ÒôÀÖ¡¢Êý¾Ý´æ´¢¡¢ÔƼÆËã¡¢Êý¾Ý¿âµÈµÈÒ²¶¼ÒªÊ¹ÓÃѹËõËã·¨¡£¿ÉÒÔ˵¼¸ºõËùÓÐÓ¦Óö¼ÒªÊ¹ÓÃѹËõËã·¨¡£Ñ¹ËõËã·¨Áîϵͳ¸üÓÐЧ³É±¾¸üµÍ£¬µ«ÊÇÒªÏëÈ·¶¨ÄÄÒ»¸ö×îÖØÒªÈ´ºÜÀ§ÄÑ£¬ÒòΪӦÓò»Í¬£¬Ê¹ÓõÄѹËõËã·¨´Ózipµ½mp3¡¢JPEG»òMPEG-2¸÷Òì¡£
10¡¢Ëæ»úÊýÉú³ÉËã·¨
ºÜ¶àÓ¦Óö¼ÐèÒªËæ»úÊý¡£Ïñinterlink connection£¬ÃÜÂëϵͳ¡¢ÊÓÆµÓÎÏ·¡¢È˹¤ÖÇÄÜ¡¢ÓÅ»¯¡¢ÎÊÌâµÄ³õʼÌõ¼þ£¬½ðÈڵȶ¼ÐèÒªÉú³ÉËæ»úÊý¡£µ«Êµ¼ÊÉÏĿǰÎÒÃDz¢Ã»ÓС°ÕæÕý¡±µÄËæ»úÊýÉú³ÉÆ÷£¬¾¡¹ÜÓÐÒ»Ð©Î±Ëæ»úÊýÉú³ÉÆ÷Ò²ÊǷdz£ÓÐЧµÄ¡£
µ±È»£¬Ê®´óËã·¨Ò²¿ÉÄܸøÓдÕÊýÖ®ÏÓ£¬ÉóÊӵĽǶȲ»Í¬¶ÔËã·¨µÄÖØÒªÐÔ¿´·¨Ò²»áºÜ²»Ò»Ñù£¬Èç¹ûÄãÈÏΪÕâÒ»°ñµ¥Óдí©µÄµØ·½£¬²»·ÁÔÚÆÀÂÛÖй±Ï×ÄãµÄÒâ¼û¡£
|