Tài liệu Giao trinh ctdl va gt_2010

môc lôc môc lôc............................................................................................................ 1 Ch¬ng 1: më ®Çu..........................................................................................4 1.1. Gi¶i thuËt....................................................................................................4 1.1.1 Kh¸i niÖm gi¶i thuËt.............................................................................4 1.1.2. C¸c ®Æc trng cña gi¶i thuËt..................................................................4 1.2. CÊu tróc d÷ liÖu vµ c¸c vÊn ®Ò liªn quan.....................................................5 1.2.1. CÊu tróc d÷ liÖu vµ gi¶i thuËt...............................................................5 1.2.2. CÊu tróc d÷ liÖu vµ ng«n ng÷ lËp tr×nh.................................................5 1.3. Ng«n ng÷ diÔn ®¹t gi¶i thuËt......................................................................6 1.3.1. §Æt vÊn ®Ò............................................................................................6 1.3.2. Quy c¸ch vÒ cÊu tróc ch¬ng tr×nh........................................................6 1.3.3. Ký tù vµ biÓu thøc................................................................................7 1.3.4. C¸c c©u lÖnh........................................................................................7 Ch¬ng 2 : ThiÕt kÕ vµ ph©n tÝch gi¶i thuËt.............................11 2.1. Tõ bµi to¸n ®Õn ch¬ng tr×nh......................................................................11 2.1.1 M« - ®un ho¸ vµ viÖc gi¶i quyÕt bµi to¸n............................................11 2.1.2. Ph¬ng ph¸p tinh chØnh tõng bíc........................................................13 2.2. Ph©n tÝch gi¶i thuËt...................................................................................24 2.2.1. §Æt vÊn ®Ò..........................................................................................24 2.2.2. Ph©n tÝch thêi gian thùc hiÖn gi¶i thuËt..............................................25 2.3. Bµi tËp......................................................................................................32 Ch¬ng 3 : §Ö quy vµ gi¶i thuËt ®Ö quy........................................36 3.1. Kh¸i niÖm vÒ ®Ö quy.................................................................................36 3.2. Gi¶i thuËt ®Ö quy vµ ch¬ng tr×nh con ®Ö quy............................................36 3.3. ThiÕt kÕ gi¶i thuËt ®Ö quy.........................................................................38 3.3.1. Hµm N !.............................................................................................38 3.3.2. Bµi to¸n Th¸p Hµ Néi........................................................................39 3.3.3. Bµi to¸n 8 qu©n hËu vµ gi¶i thuËt quay lui.........................................41 3.4. HiÖu lùc cña ®Ö quy..................................................................................45 3.5. §Ö quy vµ quy n¹p to¸n häc.....................................................................46 3.6. Bµi tËp......................................................................................................49 Ch¬ng 4: m¶ng vµ danh s¸ch............................................................51 4.1. C¸c kh¸i niÖm...........................................................................................51 4.2. CÊu tróc lu tr÷ cña m¶ng..........................................................................52 4.3. Lu tr÷ kÕ tiÕp cña danh s¸ch tuyÕn tÝnh....................................................55 4.4. Ng¨n xÕp (Stack)......................................................................................56 4.4.1. §Þnh nghÜa.........................................................................................56 4.4.2. Lu tr÷ Stack kÕ tiÕp............................................................................56 4.4.3. C¸c gi¶i thuËt PUSH, POP.................................................................57 4.4.4. øng dông cña Stack...........................................................................59 4.4.5. Stack vµ viÖc cµi ®Æt thñ tôc ®Ö quy...................................................64 4.5. Hµng ®îi (Queue).....................................................................................67 4.5.1. §Þnh nghÜa.........................................................................................67 4.5.2. Lu tr÷ Queue kÕ tiÕp..........................................................................67 4.5.3. C¸c gi¶i thuËt chÌn (INSERT), xo¸ (DELETE).................................68 4.6. Bµi tËp......................................................................................................70 Ch¬ng 5: danh s¸ch mãc nèi..............................................................75 5.1. Danh s¸ch nèi ®¬n....................................................................................75 5.1.1. Nguyªn t¾c.........................................................................................75 5.1.2. Mét sè gi¶i thuËt................................................................................76 5.2. Danh s¸ch nèi vßng..................................................................................79 5.2.1. Nguyªn t¾c.........................................................................................79 5.2.2. Mét sè gi¶i thuËt................................................................................80 5.3. Danh s¸ch nèi kÐp....................................................................................81 5.3.1. Nguyªn t¾c.........................................................................................81 5.3.2. Mét sè gi¶i thuËt................................................................................81 5.4. VÝ dô ¸p dông...........................................................................................83 5.4.1. BiÓu diÔn ®a thøc...............................................................................83 5.4.2. Gi¶i thuËt céng hai ®a thøc................................................................84 5.4.3. BiÓu diÔn tËp hîp...............................................................................86 5.4.3. C¸c phÐp to¸n....................................................................................87 5.5. Ng¨n xÕp vµ Hµng ®îi mãc nèi................................................................91 5.6. CÊu tróc ®a danh s¸ch...............................................................................93 5.6.1. BiÓu diÔn ma trËn tha.........................................................................93 5.6.2. Mét sè gi¶i thuËt................................................................................95 5.7. Danh s¸ch tæng qu¸t.................................................................................99 5.7.1. §Þnh nghÜa.........................................................................................99 5.7.2. BiÓu diÔn danh s¸ch tæng qu¸t...........................................................99 5.7.3. Mét sè gi¶i thuËt xö lý danh s¸ch tæng qu¸t....................................100 5.8. Bµi tËp.....................................................................................................104 5.9. KiÓm tra..................................................................................................105 Ch¬ng 6 : c©y.............................................................................................106 6.1. §Þnh nghÜa vµ kh¸i niÖm.........................................................................106 6.2. C©y nhÞ ph©n...........................................................................................109 6.2.1. §Þnh nghÜa vµ tÝnh chÊt....................................................................109 6.2.2. BiÓu diÔn c©y nhÞ ph©n.....................................................................111 6.2.3. PhÐp duyÖt c©y nhÞ ph©n..................................................................113 6.3. C©y nhÞ ph©n nèi vßng............................................................................118 6.3.1. Kh¸i niÖm vµ lu tr÷..........................................................................118 6.3.2. C¸c gi¶i thuËt...................................................................................120 6.4. C©y tæng qu¸t.........................................................................................123 6.4.1. BiÓu diÔn c©y tæng qu¸t...................................................................123 6.4.2. Gi¶i thuËt duyÖt c©y tæng qu¸t.........................................................126 6.4.3. ¸p dông...........................................................................................127 6.5. Bµi tËp.....................................................................................................131 6.6. KiÓm tra..................................................................................................134 Ch¬ng 7 : s¾p xÕp.....................................................................................135 7.1. §Æt vÊn ®Ò...............................................................................................135 7.2. Mét sè ph¬ng ph¸p s¾p xÕp....................................................................137 7.2.1. S¾p xÕp lùa chän (selection - Sort)...................................................137 7.2.2. S¾p xÕp thªm dÇn (Insert - Sort).......................................................138 7.2.3. S¾p xÕp næi bät (Bubble - Sort)........................................................139 7.2.4. S¾p xÕp nhanh (Quick- Sort)............................................................140 7.2.5. S¾p xÕp vun ®èng (Heap –Sort)......................................................142 7.2.6. S¾p xÕp hoµ nhËp (Merge – Sort)...................................................147 7.3. Ph©n tÝch ®¸nh gi¸ c¸c thuËt to¸n...........................................................149 7.4. Bµi tËp.....................................................................................................151 Ch¬ng 8: T×m kiÕm..................................................................................153 8.1. Bµi to¸n t×m kiÕm...................................................................................153 8.2. T×m kiÕm tuÇn tù....................................................................................153 8.3. T×m kiÕm nhÞ ph©n..................................................................................154 8.4. C©y nhÞ ph©n t×m kiÕm............................................................................156 8.4.1. §Þnh nghÜa.......................................................................................156 8.4.2. C¸c gi¶i thuËt...................................................................................157 8.5. Bµi tËp – Tæng kÕt vµ «n tËp.................................................................161 tµi liÖu tham kh¶o..............................................................................187 Ch¬ng 1: më ®Çu 1.1. Gi¶i thuËt 1.1.1 Kh¸i niÖm gi¶i thuËt Gi¶i thuËt (Algorithms): lµ mét d·y c¸c c©u lÖnh (statements) chÆt chÏ vµ râ rµng x¸c ®Þnh mét tr×nh tù c¸c thao t¸c trªn mét sè ®èi tîng nµo ®ã sao cho sau mét sè h÷u h¹n bíc thùc hiÖn ta ®¹t ®îc kÕt qu¶ mong muèn. §Ó minh ho¹ cho kh¸i niÖm gi¶i thuËt ta xÐt gi¶i thuËt gi¶i bµi to¸n t×m phÇn tö lín nhÊt trong mét d·y h÷u h¹n c¸c sè nguyªn. Gi¶i thuËt gåm c¸c bíc sau: Bíc 1. §Æt gi¸ trÞ cùc ®¹i t¹m thêi b»ng sè nguyªn ®Çu tiªn trong d·y. Bíc 2. So s¸nh sè nguyªn tiÕp sau víi gi¸ trÞ cùc ®¹i t¹m thêi, nÕu nã lín h¬n gi¸ trÞ cùc ®¹i t¹m thêi, th× ®Æt cùc ®¹i t¹m thêi b»ng sè nguyªn ®ã. Bíc 3. LÆp l¹i bíc 2 nÕu cßn c¸c sè nguyªn trong d·y Bíc 4. Cùc ®¹i t¹m thêi thu ®îc ë bíc nµy chÝnh lµ sè nguyªn lín nhÊt cña d·y. 1.1.2. C¸c ®Æc trng cña gi¶i thuËt Gi¶i thuËt cã c¸c ®Æc trng sau:  §Çu vµo (Input): Gi¶i thuËt nhËn d÷ liÖu ®Çu vµo tõ mét tËp nµo ®ã.  §Çu ra (Output): Víi mçi tËp c¸c d÷ liÖu ®Çu vµo, gi¶i thuËt ®a ra c¸c d÷ liÖu t¬ng øng víi lêi gi¶i cña bµi to¸n.  TÝnh chÝnh x¸c: C¸c bíc cña mét gi¶i thuËt ph¶i ®îc x¸c ®Þnh mét c¸ch chÝnh x¸c.  TÝnh h÷u h¹n: Mét gi¶i thuËt cÇn ph¶i t¹o ra c¸c gi¸ trÞ ®Çu ra mong muèn sau mét sè h÷u h¹n ( nhng cã thÓ rÊt lín) c¸c bíc ®èi víi mäi tËp ®Çu vµo.  TÝnh hiÖu qu¶: Mçi bíc cña gi¶i thuËt cÇn ph¶i thùc hiÖn ®îc mét c¸ch chÝnh x¸c vµ trong mét kho¶ng thêi gian h÷u h¹n.  TÝnh tæng qu¸t: Thñ tôc cÇn ph¶i ¸p dông ®îc cho mäi bµi to¸n cã d¹ng mong muèn, chø kh«ng ph¶i chØ cho mét tËp ®Æc biÖt c¸c gi¸ trÞ ®Çu vµo. VÝ dô 1.1: Cho 3 sè nguyªn a, b, c. M« t¶ gi¶i thuËt t×m sè lín nhÊt trong 3 sè ®· cho. Gi¶i: Tuy r»ng bµi to¸n ®Æt ra lµ rÊt ®¬n gi¶n, nhng môc ®Ých cña chóng ta lµ dïng nã ®Ó gi¶i thÝch kh¸i niÖm gi¶i thuËt. Gi¶i thuËt gåm c¸c bíc sau: Bíc 1: §Æt x := a; Bíc 2: NÕu b > x th× ®Æt x := b; Bíc 3: NÕu c > x th× ®Æt x := c; T tëng cña gi¶i thuËt lµ duyÖt lÇn lît gi¸ trÞ cña tõng sè vµ gi÷ l¹i gi¸ trÞ lín nhÊt vµo biÕn x. KÕt thóc gi¶i thuËt x cho sè nguyªn lín nhÊt trong 3 sè ®· cho. 1.2. CÊu tróc d÷ liÖu vµ c¸c vÊn ®Ò liªn quan 1.2.1. CÊu tróc d÷ liÖu vµ gi¶i thuËt Cã thÓ cã lóc khi nãi ®Õn viÖc gi¶i quyÕt bµi to¸n trªn m¸y tÝnh ngêi ta chØ chó ý ®Õn gi¶i thuËt, tuy nhiªn gi¶i thuËt chØ ph¶n ¸nh c¸c phÐp xö lý, cßn ®èi tîng ®Ó xö lý trªn m¸y tÝnh ®iÖn tö chÝnh lµ d÷ liÖu (data), chóng biÓu diÔn c¸c th«ng tin cÇn thiÕt cho bµi to¸n: C¸c d÷ kiÖn ®a vµo (input), c¸c kÕt qu¶ trung gian,...B¶n th©n c¸c phÇn tö cña d÷ liÖu thêng cã mèi quan hÖ víi nhau: Víi mét m« t¶ kiÓu d÷ liÖu trõu tîng cã thÓ cã nhiÒu c¸ch cµi ®Æt kh¸c nhau ®Ó h×nh thµnh nhiÒu cÊu tróc d÷ liÖu kh¸c nhau. Ngoµi ra, nÕu l¹i biÕt “tæ chøc” theo cÊu tróc thÝch hîp th× viÖc thùc hiÖn c¸c phÐp xö lý trªn c¸c d÷ liÖu sÏ cµng thuËn lîi h¬n, ®¹t hiÖu qu¶ cao h¬n. Víi mét cÊu tróc d÷ liÖu ®· chän ta sÏ cã gi¶i thuËt xö lý t¬ng øng. CÊu tróc d÷ liÖu thay ®æi, gi¶i thuËt còng thay ®æi theo. Nh vËy, gi÷a cÊu tróc d÷ liÖu vµ gi¶i thuËt cã mèi quan hÖ mËt thiÕt: Kh«ng thÓ nãi tíi gi¶i thuËt mµ kh«ng nghÜ tíi gi¶i thuËt ®ã ®îc t¸c ®éng trªn cÊu tróc d÷ liÖu nµo, cßn khi xÐt tíi cÊu tróc d÷ liÖu th× còng ph¶i xÐt ®Õn d÷ liÖu ®ã cÇn ®îc t¸c ®éng gi¶i thuËt g× ®Ó ®a l¹i kÕt qu¶ mong muèn. 1.2.2. CÊu tróc d÷ liÖu vµ ng«n ng÷ lËp tr×nh C¸c ng«n ng÷ lËp tr×nh ngoµi viÖc cung cÊp c¸c kiÓu d÷ liÖu c¬ b¶n, nã cßn cung cÊp c¬ chÕ hiÖu qu¶ vµ dÔ sö dông cho phÐp chóng ta ®Þnh nghÜa c¸c kiÓu d÷ liÖu míi (kiÓu d÷ liÖu trõu tîng) theo yªu cÇu. ViÖc chän mét ng«n ng÷ lËp tr×nh tøc lµ chÊp nhËn c¸c cÊu tróc tiÒn ®Þnh cña ng«n ng÷ Êy vµ ph¶i biÕt linh ho¹t vËn dông chóng ®Ó m« pháng c¸c cÊu tróc d÷ liÖu ®· cho cho bµi to¸n cÇn gi¶i quyÕt. Tuy nhiªn, trong thùc tÕ viÖc lùa chän mét ng«n ng÷ kh«ng ph¶i chØ xuÊt ph¸t tõ yªu cÇu cña bµi to¸n mµ cßn phô thuéc vµo rÊt nhiÒu yÕu tè kh¸ch quan còng nh chñ quan cña ngêi lËp tr×nh n÷a. Tho¹t ®Çu, khi øng dông cña m¸y tÝnh ®iÖn tö chØ míi cã trong ph¹m vi c¸c bµi to¸n khoa häc kü thuËt th× ta chØ gÆp c¸c cÊu tróc d÷ liÖu ®¬n gi¶n nh biÕn, vÐct¬, ma trËn,...nhng khi c¸c øng dông ®ã ®· ®îc më réng sang c¸c lÜnh vùc kh¸c mµ ta thêng gäi lµ bµi to¸n phi sè (non-numerical proplems), víi ®Æc ®iÓm thÓ hiÖn ë chç: khèi lîng d÷ liÖu lín, ®a d¹ng, biÕn ®éng; phÐp xö lý thêng kh«ng chØ lµ c¸c phÐp sè häc..th× c¸c cÊu tróc d÷ liÖu tiÒn ®Þnh do c¸c ng«n ng÷ lËp tr×nh cung cÊp thêng kh«ng ®ñ ®Æc trng cho c¸c mèi quan hÖ míi cña d÷ liÖu míi. V× vËy, viÖc ®i s©u nghiªn cøu c¸c cÊu tróc d÷ liÖu phøc t¹p h¬n chÝnh lµ sù quan t©m cña chóng ta trong gi¸o tr×nh nµy. Bµi bµi to¸n phi sè ®i ®«i víi c¸c cÊu tróc d÷ liªu míi còng xuÊt hiÖn c¸c phÐp to¸n míi t¸c ®éng trªn c¸c cÊu tróc d÷ liÖu nµy, c¸c phÐp to¸n ®ã sÏ cã nh÷ng t¸c dông kh¸c nhau ®èi víi tõng cÊu tróc d÷ liÖu. Cã phÐp h÷u hiÖu ®èi víi cÊu tróc nµy nhng l¹i tá ra kh«ng h÷u hiÖu trªn cÊu tróc kh¸c. C¸ch biÓu diÔn mét cÊu tróc d÷ liÖu trong bé nhí ®îc gäi lµ cÊu tróc lu tr÷. §ã chÝnh lµ c¸ch cµi ®Æt cÊu tróc Êy trªn m¸y tÝnh ®iÖn tö vµ trªn c¬ së c¸c cÊu tróc lu tr÷ nµy mµ ta thùc hiÖn c¸c phÐp xö lý. Cã thÓ cã nhiÒu cÊu tróc lu tr÷ kh¸c nhau cho cïng mét cÊu tróc d÷ liÖu; còng nh cã nh÷ng cÊu tróc d÷ liÖu kh¸c nhau mµ ®îc thÓ hiÖn trong bé nhí bëi cïng mét kiÓu cÊu tróc lu tr÷. Khi ®Ò cËp ®Õn cÊu tróc lu tr÷ ta còng cÇn ph©n biÖt cÊu tróc lu tr÷ t¬ng øng víi bé nhí trong- lu tr÷ trong, hay øng víi bé nhí ngoµi- lu tr÷ ngoµi. 1.3. Ng«n ng÷ diÔn ®¹t gi¶i thuËt 1.3.1. §Æt vÊn ®Ò §Ó diÔn ®¹t c¸c gi¶i thuËt mµ ta sÏ tr×nh bµy trong gi¸o tr×nh, ta cÇn mét ng«n ng÷ diÔn ®¹t. Ta cã thÓ lùa chän mét ng«n ng÷ lËp tr×nh nµo ®ã nh C, Pascal, v.v... , nhng nh vËy ta sÏ gÆp mÊy h¹n chÕ sau: - Ph¶i lu«n lu«n tu©n thñ c¸c quy t¾c chÆt chÏ vÒ có ph¸p cña ng«n ng÷ ®ã, khiÕn cho viÖc tr×nh bµy vÒ gi¶i thuËt vµ cÊu tróc d÷ liÖu cã thiªn híng nÆng nÒ, gß bã. - Ph¶i phô thuéc vµo cÊu tróc d÷ liÖu tiÒn ®Þnh cña ng«n ng÷, nªn cã lóc kh«ng thÓ hiÖn ®îc ®Çy ®ñ c¸c ý nghÜa vÒ cÊu tróc mµ ta muèn biÓu ®¹t. - Ng«n ng÷ nµo ®îc chän còng kh«ng h¼n ®· ®îc mäi ngêi a thÝch vµ muèn sö dông. V× vËy, ë ®©y ta sÏ dïng mét ng«n ng÷ “th« h¬n”, cã ®ñ kh¶ n¨ng diÔn ®¹t ®îc gi¶i thuËt trªn c¸c cÊu tróc ®Ò cËp ®Õn (mµ ta giíi thiÖu b»ng tiÕng ViÖt), víi mét møc ®é linh ho¹t nhÊt ®Þnh, kh«ng qu¸ gß bã, kh«ng c©u nÖ nhiÒu vÒ có ph¸p nhng còng gÇn gòi víi c¸c ng«n ng÷ chuÈn, ®Ó khi cÇn thiÕt dÔ dµng chuyÓn ®æi. Ta t¹m gäi nã b»ng c¸i tªn: “ng«n ng÷ tùa PASCAL”. 1.3.2. Quy c¸ch vÒ cÊu tróc ch¬ng tr×nh Mçi ch¬ng tr×nh ®Òu ®îc g¾n mét tªn ®Ó ph©n biÖt, tªn nµy ®îc viÕt b»ng ch÷ in hoa, cã thÓ cã thªm dÊu g¹ch nèi vµ b¾t ®Çu b»ng tõ kho¸ Program. VÝ dô 1.2: Program NHAN_MA_TRAN §é dµi cña tªn kh«ng h¹n chÕ. Sau tªn cã thÓ kÌm theo lêi thuyÕt minh (ë ®©y ta quy íc dïng tiÕng ViÖt) ®Ó giíi thiÖu tãm t¾t nhiÖm vô cña gi¶i thuËt hoÆc mét sè chi tiÕt cÇn thiÕt. PhÇn thuyÕt minh ®îc ®Æt gi÷a hai dÊu { …….. }. Ch¬ng tr×nh bao gåm nhiÒu ®o¹n (bíc), mçi ®o¹n ®îc ph©n biÖt bëi sè thø tù, cã thÓ kÌm theo nh÷ng lêi thuyÕt minh. 1.3.3. Ký tù vµ biÓu thøc Ký tù dïng ë ®©y còng gièng nh trong c¸c ng«n ng÷ chuÈn, nghÜa lµ gåm: - 26 ch÷ c¸i latinh in hoa hoÆc in thêng. - 10 ch÷ sè thËp ph©n. - C¸c dÊu phÐp to¸n sè häc +, -, *, /,  (luü thõa) - C¸c dÊu phÐp to¸n quan hÖ <, =, >, ≤, ≥, ≠ - Gi¸ trÞ logic: true, false - DÊu phÐp to¸n logic: and, or, not - Tªn biÕn: d·y ch÷ c¸i vµ ch÷ sè, b¾t ®Çu b»ng ch÷ c¸i. - BiÕn chØ sè cã d¹ng: A[i], B[i, j], v.v... Cßn biÓu thøc còng nh thø tù u tiªn cña c¸c phÐp to¸n trong biÓu thøc còng theo quy t¾c nh trong PASCAL hay c¸c ng«n ng÷ chuÈn kh¸c. 1.3.4. C¸c c©u lÖnh C¸c c©u lÖnh trong ch¬ng tr×nh ®îc viÕt c¸ch nhau bëi dÊu ; chóng bao gåm: 1- C©u lÖnh g¸n Cã d¹ng V := E; Víi V chØ tªn biÕn, tªn hµm; E chØ biÓu thøc. ë ®©y cho phÐp dïng phÐp g¸n chung. VÝ dô: A :=B := 0.1; 2- C©u lÖnh ghÐp Cã d¹ng: begin S1; S2; …; Sn; end; Víi Si (i = 1, .., n) lµ c¸c c©u lÖnh. Nã cho phÐp ghÐp nhiÒu c©u lÖnh l¹i ®Ó ®îc coi nh mét c©u lÖnh. 3- C©u lÖnh ®iÒu kiÖn Cã d¹ng: if B then S; Víi B lµ biÓu thøc logic, S lµ mét c©u lÖnh kh¸c. Cã thÓ diÔn t¶ bëi s¬ ®å B true S hoÆc then false if B else S2; B true S1 false S2 S1 4- C©u lÖnh tuyÓn Cã d¹ng: Case B1: S1; …. Bn: Sn; Else: Sn+1; End case; Víi Bi (i = 1, 2, .., n) lµ c¸c ®iÒu kiÖn, S i (i = 1, 2, .., n) lµ c¸c c©u lÖnh. C©u lÖnh nµy cho phÐp ph©n biÖt c¸c t×nh huèng xö lý kh¸c nhau trong c¸c ®iÒu kiÖn kh¸c nhau mµ kh«ng ph¶i dïng tíi c¸c c©u lÖnh if- then- else lång nhau. Cã thÓ biÓu diÔn bëi s¬ ®å: B1 false true B2 true S1 false… Bn false Sn+1 true S2 S2  Vµi ®iÓm linh ®éng Else cã thÓ kh«ng cã mÆt. S i (i = 1, 2, .., n) cã thÓ ®îc thay b»ng mét d·y c¸c c©u lÖnh thÓ hiÖn mét d·y xö lý khi cã ®iÒu kiÖn B i mµ kh«ng cÇn ph¶i ®Æt gi÷a begin vµ end. 5- C©u lÖnh lÆp  Víi sè lÇn lÆp biÕt tríc. For i := m to n do S; Nh»m thùc hiÖn c©u lÖnh S víi i lÊy gi¸ trÞ nguyªn tõ m tíi n ( n >= m) víi bíc nh¶y t¨ng b»ng 1; HoÆc: For i:= n downto m do S; T¬ng tù nh c©u lÖnh trªn víi bíc nh¶y gi¶m b»ng 1.  Víi sè lÇn lÆp kh«ng biÕt tríc While B do S; true B S false Chõng nµo mµ B cã gi¸ trÞ b»ng true th× thùc hiÖn S HoÆc: Repeat S until B; LÆp l¹i S cho tíi khi B cã gi¸ trÞ true (S cã thÓ lµ mét d·y lÖnh) S B true false 6- C©u lÖnh chuyÓn Goto n; (n lµ sè hiÖu cña mét bíc trong ch¬ng tr×nh) Thêng ngêi ta h¹n chÕ viÖc sö dông goto. Tuy nhiªn, víi môc ®Ých diÔn ®¹t cho tù nhiªn, trong mét chõng mùc nµo ®ã ta vÉn sö dông. 7- C©u lÖnh vµo, ra Cã d¹ng: Read (); Write (); C¸c biÕn trong danh s¸ch c¸ch nhau bëi dÊu phÈy. Dßng ký tù lµ mét d·y c¸c ký tù ®Æt gi÷a hai dÊu nh¸y ‘ vµ ‘. 8- C©u lÖnh kÕt thóc ch¬ng tr×nh. End. 1.3.4 Ch¬ng tr×nh con.  Ch¬ng tr×nh con hµm Cã d¹ng: Function () S1; S2; … ; Sn; Return ; C©u lÖnh kÕt thóc ch¬ng tr×nh con ë ®©y lµ return thay cho end.  Ch¬ng tr×nh con thñ tôc Procedure () S1; S2; … ; Sn; Return ; Lêi gäi ch¬ng tr×nh con hµm thÓ hiÖn b»ng tªn hµm cïng danh s¸ch tham sè thùc sù, n»m trong biÓu thøc. Cßn víi ch¬ng tr×nh con thñ tôc lêi gäi ®îc thÓ hiÖn b»ng c©u lÖnh call cã d¹ng: Call () Chó ý: Trong c¸c ch¬ng tr×nh diÔn ®¹t mét sè gi¶i thuËt ë ®©y phÇn khai b¸o d÷ liÖu ®îc bá qua. Nã ®îc thay bëi phÇn m« t¶ cÊu tróc d÷ liÖu b»ng ng«n ng÷ tù nhiªn, mµ ta sÏ nªu ra tríc khi bíc vµo gi¶i thuËt. Nh vËy, nghÜa lµ c¸c ch¬ng tr×nh ®îc nªu ra chØ lµ ®o¹n thÓ hiÖn c¸c phÐp xö lý theo gi¶i thuËt ®· ®Þnh, trªn c¸c cÊu tróc d÷ liÖu ®îc m« t¶ tríc ®ã, b»ng ng«n ng÷ tù nhiªn. Ch¬ng 2 : ThiÕt kÕ vµ ph©n tÝch gi¶i thuËt 2.1. Tõ bµi to¸n ®Õn ch¬ng tr×nh 2.1.1 M« - ®un ho¸ vµ viÖc gi¶i quyÕt bµi to¸n C¸c bµi to¸n ®îc gi¶i trªn m¸y tÝnh ®iÖn tö ngµy cµng ®a d¹ng vµ phøc t¹p. C¸c gi¶i thuËt vµ ch¬ng tr×nh ®Ó gi¶i chóng còng ngµy cµng cã quy m« lín vµ cµng khã khi thiÕt lËp còng nh khi muèn t×m hiÓu. Tuy nhiªn, ta còng thÊy r»ng mäi viÖc sÏ ®¬n gi¶n h¬n nÕu nh cã thÓ ph©n chia bµi to¸n lín cña ta thµnh c¸c bµi to¸n nhá. §iÒu ®ã còng cã nghÜa lµ nÕu coi bµi to¸n cña ta nh mét m«-®un chÝnh th× cÇn chia nã thµnh c¸c m«-®un con, vµ dÜ nhiªn, víi tinh thÇn nh thÕ, ®Õn lît nã, mçi m«-®un nµy l¹i ®îc ph©n chia tiÕp cho tíi nh÷ng m«-®un øng víi c¸c phÇn viÖc c¬ b¶n mµ ta ®· biÕt c¸ch gi¶i quyÕt. Nh vËy, viÖc tæ chøc lêi gi¶i cña bµi to¸n sÏ ®îc thÓ hiÖn theo mét cÊu tróc ph©n cÊp, cã d¹ng nh h×nh sau: A B E F C G D H I H×nh 2.1 ChiÕn thuËt gi¶i quyÕt bµi to¸n theo tinh thÇn nh vËy chÝnh lµ chiÕn thuËt “chia ®Ó trÞ” (divide and conquer). §Ó thÓ hiÖn chiÕn thuËt ®ã, ngêi ta dïng c¸ch thiÕt kÕ “®Ønh- xuèng” (top-down design). §ã lµ c¸ch ph©n tÝch tæng qu¸t toµn bé vÊn ®Ò, xuÊt ph¸t tõ d÷ kiÖn vµ c¸c môc tiªu ®Æt ra, ®Ó ®Ò cËp ®Õn nh÷ng c«ng viÖc chñ yÕu, råi sau ®ã míi ®i dÇn vµo gi¶i quyÕt c¸c phÇn cô thÓ mét c¸ch chi tiÕt h¬n (còng v× vËy mµ ngêi ta gäi lµ c¸ch thiÕt kÕ tõ kh¸i qu¸t ®Õn chi tiÕt). VÝ dô ta nhËn ®îc tõ chñ tÞch héi ®ång xÐt cÊp häc bæng cña trêng mét yªu cÇu lµ: “Dïng m¸y tÝnh ®iÖn tö ®Ó qu¶n lý vµ b¶o tr× hå s¬ vÒ häc bæng cña c¸c sinh viªn ë diÖn ®îc tµi trî, ®ång thêi thêng kú ph¶i lËp c¸c b¸o c¸o tæng kÕt ®Ó ®Ö tr×nh lªn bé” Nh vËy, tríc hÕt ta ph¶i h×nh dung ®îc cô thÓ h¬n ®Çu vµo vµ ®Çu ra cña bµi to¸n. Cã thÓ coi nh ta ®· cã mét tËp hå s¬ (mµ ta gäi lµ tÖp file) bao gåm c¸c b¶n ghi (records) vÒ c¸c th«ng tin liªn quan tíi häc bæng cña sinh viªn, Ch¼ng h¹n: sè hiÖu sinh viªn, ®iÓm trung b×nh (theo häc kú), ®iÓm ®¹o ®øc, kho¶n tiÒn tµi trî. Vµ ch¬ng tr×nh lËp ra ph¶i t¹o ®iÒu kiÖn cho ngêi sö dông gi¶i quyÕt ®îc c¸c yªu cÇu sau: 1. T×m l¹i vµ hiÓn thÞ ®îc b¶n ghi cña bÊt kú sinh viªn nµo t¹i thiÕt bÞ cuèi (terminal) cña ngêi dïng. 2. CËp nhËp (update) ®îc b¶n ghi cña mét sinh viªn cho tríc b»ng c¸ch thay ®æi ®iÓm trung b×nh, ®iÓm ®¹o ®øc, kho¶n tiÒn tµi trî, nÕu cÇn. 3. In b¶n tæng kÕt chøa nh÷ng th«ng tin hiÖn thêi ( ®· ®îc cËp nhËp mçi khi cã thay ®æi) gåm sè liÖu, ®iÓm trung b×nh, ®iÓm ®¹o ®øc, kho¶n tiÒn tµi trî. XuÊt ph¸t tõ nh÷ng nhËn ®Þnh nªu trªn, gi¶i thuËt xö lý sÏ ph¶i gi¶i quyÕt ba nhiÖm vô chÝnh nh sau: 1. Nh÷ng th«ng tin vÒ sinh viªn ®îc häc bæng, lu tr÷ trªn ®Üa ph¶i ®îc ®äc vµo bé nhí trong ®Ó cã thÓ xö lý ( ta gäi lµ nhiÖm vô “®äc tÖp”). 2. Xö lý c¸c th«ng tin nµy ®Ó t¹o ra kÕt qu¶ mong muèn (nhiÖm vô ”xö lý tÖp”). 3. Sao chÐp nh÷ng th«ng tin ®· ®îc cËp nhËp vµo tÖp trªn ®Üa ®Ó lu tr÷ cho viÖc xö lý sau nµy (nhiÖm vô ”ghi tÖp”) Cã thÓ h×nh dung, c¸ch thiÕt kÕ nµy theo s¬ ®å cÊu tróc ë h×nh 2.2. HÖ hç trî qu¶n lý häc bæng §äc tÖp Xö lý tÖp Ghi tÖp H×nh 2.2 C¸c nhiÖm vô ë møc ®Çu nµy thêng t¬ng ®èi phøc t¹p, cÇn ph¶i chia thµnh c¸c nhiÖm vô con. Ch¼ng h¹n nhiÖm vô “xö lý tÖp” sÏ ®îc ph©n thµnh ba, t¬ng øng víi viÖc gi¶i quyÕt ba yªu cÇu chÝnh ®· ®îc nªu ë trªn: 1) T×m l¹i b¶n ghi cña mét sinh viªn cho tríc 2) CËp nhËp th«ng tin trong b¶n ghi sinh viªn 3) In b¶n tæng kÕt nh÷ng th«ng tin vÒ c¸c sinh viªn ®îc häc bæng. Nh÷ng nhiÖm vô con nµy còng cã thÓ ®îc chia thµnh nh÷ng nhiÖm vô nhá h¬n. Cã thÓ h×nh dung theo s¬ ®å cÊu tróc nh sau: Xö lý tÖp T×m b¶n ghi T×m kiÕm HiÓn thÞ b¶n ghi CËp nhËt b¶n ghi T×m kiÕm In b¶n tæng CËp nhËt H×nh 2.3 C¸ch thiÕt kÕ gi¶i thuËt theo kiÓu top-down nh trªn gióp cho viÖc gi¶i quyÕt bµi to¸n ®îc ®Þnh híng râ rµng, tr¸nh sa ®µ ngay vµo c¸c chi tiÕt phô. Nã còng lµ nÒn t¶ng cho viÖc lËp tr×nh cã cÊu tróc. Th«ng thêng ®èi víi c¸c bµi to¸n lín, viÖc gi¶i quyÕt nã ph¶i do nhiÒu ngêi cïng lµm. ChÝnh ph¬ng ph¸p m«-®un hãa sÏ cho phÐp t¸ch bµi to¸n ra thµnh c¸c phÇn ®éc lËp t¹o ®iÒu kiÖn cho c¸c nhãm gi¶i quyÕt phÇn viÖc cña m×nh mµ kh«ng lµm ¶nh hëng g× ®Õn nhãm kh¸c. Víi ch¬ng tr×nh ®îc x©y dùng trªn c¬ së cña c¸c gi¶i thuËt ®îc thiÕt kÕ theo c¸ch nµy th× viÖc t×m hiÓu còng nh söa ch÷a, chØnh lý sÏ dÔ dµng h¬n. ViÖc ph©n bµi to¸n thµnh c¸c bµi to¸n con nh thÕ kh«ng ph¶i lµ mét viÖc lµm dÔ dµng. ChÝnh v× vËy mµ cã nh÷ng bµi to¸n nhiÖm vô ph©n tÝch vµ thiÕt kÕ gi¶i thuËt gi¶i bµi to¸n ®ã cßn mÊt nhiÒu thêi gian vµ c«ng søc h¬n c¶ nhiÖm vô lËp tr×nh. 2.1.2. Ph¬ng ph¸p tinh chØnh tõng bíc 1) Ph¬ng ph¸p Tinh chØnh tõng bíc lµ ph¬ng ph¸p thiÕt kÕ gi¶i thuËt g¾n liÒn víi lËp tr×nh. Nã ph¶n ¸nh tinh thÇn cña qu¸ tr×nh m«-®un ho¸ bµi to¸n thiÕt kÕ kiÓu top-down. Tho¹t ®Çu ch¬ng tr×nh thÓ hiÖn gi¶i thuËt ®îc tr×nh bµy b»ng ng«n ng÷ tù nhiªn ph¶n ¸nh ý chÝnh cña c«ng viÖc cÇn lµm. Tõ c¸c bíc sau nh÷ng lêi, nh÷ng ý ®ã sÏ ®îc chi tiÕt ho¸ dÇn dÇn t¬ng øng víi nh÷ng c«ng viÖc nhá h¬n. Ta gäi ®ã lµ c¸c bíc tinh chØnh, sù tinh chØnh nµy sÏ ®îc híng vÒ phÝa ng«n ng÷ lËp tr×nh mµ ta ®· chän. Cµng ë c¸c bíc sau c¸c lêi lÏ ®Æc t¶ c«ng viÖc xö lý sÏ ®îc thay thÕ dÇn bëi c¸c c©u lÖnh híng tíi c©u lÖnh cña ng«n ng÷ lËp tr×nh. Muèn vËy, ë c¸c giai ®o¹n trung gian ngêi ta thêng dïng pha t¹p c¶ ng«n ng÷ tù nhiªn lÉn ng«n ng÷ lËp tr×nh, mµ ngêi ta gäi lµ gi¶ ng«n ng÷ (pseudo-language) hay gi¶ m· (pseudo code). Nh vËy, nghÜa lµ qu¸ tr×nh thiÕt kÕ gi¶i thuËt vµ ph¸t triÓn ch¬ng tr×nh sÏ ®îc thÓ hiÖn dÇn dÇn tõ d¹ng ng«n ng÷ tù nhiªn, qua gi¶ ng«n ng÷ råi ®Õn ng«n ng÷ lËp tr×nh vµ ®i tõ møc “lµ c¸i g×” ®Õn møc “lµm thÕ nµo”, ngµy cµng s¸t víi c¸c chøc n¨ng øng víi c¸c c©u lÖnh cña ng«n ng÷ lËp tr×nh ®· chän. Trong qu¸ tr×nh nµy d÷ liÖu còng ®îc “tinh chÕ” tõ d¹ng cÊu tróc ®Õn d¹ng lu tr÷ cµi ®Æt cô thÓ. 2) Bµi to¸n s¾p xÕp Gi¶ sö ta muèn lËp mét ch¬ng tr×nh s¾p xÕp mét d·y n sè nguyªn kh¸c nhau theo thø tù t¨ng dÇn. Cã thÓ ph¸c th¶o gi¶i thuËt nh sau: “Tõ d·y c¸c sè nguyªn cha ®îc s¾p xÕp chän ra sè nhá nhÊt, ®Æt nã vµo cuèi d·y ®· ®îc s¾p xÕp. Cø lÆp l¹i quy tr×nh ®ã cho tíi khi d·y cha ®îc s¾p xÕp chØ cßn mét sè”. Ta thÊy ph¸c ho¹ trªn cßn ®ang rÊt th«, nã chØ thÓ hiÖn nh÷ng ý c¬ b¶n. H×nh dung cô thÓ h¬n mét chót ta thÊy, tho¹t ®Çu d·y sè cha ®îc s¾p xÕp chÝnh lµ d·y sè ®· cho. D·y sè ®· ®îc s¾p xÕp cßn rçng, cha cã phÇn tö nµo. VËy th× nÕu chän ®îc sè nhá nhÊt ®Çu tiªn vµ ®Æt vµo cuèi d·y ®· ®îc s¾p th× còng chÝnh lµ ®Æt vµo vÞ trÝ ®Çu tiªn cña d·y nµy. Nhng d·y nµy ®Æt ë ®©u? ThÕ th× ph¶i hiÓu d·y sè mµ ta sÏ s¾p xÕp ®îc ®Æt t¹i chç cò hay ®Æt ë chç kh¸c? §iÒu ®ã ®ßi hái ph¶i chi tiÕt h¬n vÒ cÊu tróc d÷ liÖu vµ cÊu tróc lu tr÷ cña d·y sè cho. Tríc hÕt ta Ên ®Þnh: d·y sè cho ë ®©y ®îc coi nh d·y c¸c phÇn tö cña mét vect¬ (sau nµy ta nãi: nã cã cÊu tróc cña m¶ng mét chiÒu) vµ d·y nµy ®îc lu tr÷ bëi mét vect¬ lu tr÷ gåm n tõ m¸y kÕ tiÕp ë bé nhí trong (a 1, a2, .., an) mçi tõ m¸y ai lu tr÷ phÇn tö thø i (1 ≤ i ≤ n) cña d·y sè. Ta còng qui íc: d·y sè ®îc s¾p xÕp råi vÉn ®Ó t¹i chç cò nh d·y ®· cho. VËy th× viÖc ®Æt “sè nhá nhÊt” võa ®îc chän, ë mét lît nµo ®ã, vµo cuèi d·y ®· ®îc s¾p xÕp ph¶i thùc hiÖn b»ng c¸ch ®æi chç cho sè hiÖn ®ang ë vÞ trÝ ®ã (nÕu nh nã kh¸c sè nµy). Gi¶ sö ta ®ang ®Þnh híng ch¬ng tr×nh cña ta vµo vµo ng«n ng÷ tùa PASCAL, nªu ë ch¬ng 1, th× bíc tinh chØnh ®Çu tiªn sÏ nh sau: For i :=1 to n-1 do begin - XÐt tõ ai ®Õn an ®Ó t×m sè nhá nhÊt aj - §æi chç gi÷a ai vµ aj nÕu ai kh¸c aj end Tíi ®©y ta thÊy cã hai nhiÖm vô con, cÇn lµm râ thªm. 1. T×m sè nguyªn nhá nhÊt aj trong c¸c sè tõ ai ®Õn an 2. §æi chç gi÷a aj víi ai nÕu ai kh¸c aj NhiÖm vô ®Çu cã thÓ thùc hiÖn b»ng c¸ch: “Tho¹t tiªn coi ai lµ “sè nhá nhÊt” t¹m thêi; lÇn lît so s¸nh ai víi ai+1, ai+2, v.v… Khi thÊy sè nµo nhá h¬n th× l¹i coi ®ã lµ “sè nhá nhÊt” míi. Khi ®· so s¸nh víi a n råi th× sè nhá nhÊt sÏ ®îc x¸c ®Þnh” Nhng x¸c ®Þnh b»ng c¸ch nµo? Cã thÓ b»ng c¸ch chØ ra chç cña nã, nghÜa lµ n¾m ®îc chØ sè cña phÇn tö Êy. Ta cã bíc tinh chØnh 2.1: j := i; For k :=j +1 to n do If ak < aj then j := k; Víi nhiÖm vô thø hai th× cã thÓ gi¶i quyÕt b»ng c¸ch t¬ng tù nh khi ta muèn chuyÓn hai thø rîu trong hai ly, tõ ly nä sang ly kia: ta sÏ ph¶i dïng mét ly thø ba (kh«ng ®ùng g×) ®Ó lµm ly trung chuyÓn. Ta cã bíc tinh chØnh 2.2: B := ai ; ai := aj ; aj := B; Sau khi ®· chØnh l¹i c¸ch viÕt biÕn chØ sè cho ®óng víi quy íc ta cã ch¬ng tr×nh s¾p xÕp díi d¹ng thñ tôc nh sau: Procedure SORT (A, n) 1. for i := 1 to n-1 do begin 2. j := i;{chän sè nhá nhÊt} for k :=j +1 to n do if A[k] < A[j] then j := k; 3. if A[i] ≠ A[j] then begin B := A[i]; A[i] := A[j]; A[j] := B; {§æi chç} end; end; 4. Return; 3) Bµi to¸n hiÓn thÞ c¸c ®êng chÐo cña ma trËn Ph¸t biÓu bµi to¸n: Cho mét ma trËn vu«ng n x n c¸c sè nguyªn. H·y in ra c¸c phÇn tö thuéc ®êng chÐo song song víi ®êng chÐo chÝnh. VÝ dô: Cho ma trËn vu«ng víi n = 3 3 5 11 4 7 9 2 0 8 Gi¶ sö ta chän c¸ch in tõ ph¶i sang tr¸i, th× cã kÕt qu¶: 11 5 0 3 7 4 2 8 9 Ta sÏ híng viÖc thÓ hiÖn gi¶i thuËt vÒ mét ch¬ng tr×nh PASCAL. Gi¶i thuËt cã thÓ ph¸c ho¹ nh sau: 1- NhËp n 2- NhËp c¸c phÇn tö cña ma trËn 3- In c¸c ®êng chÐo song song víi ®êng chÐo chÝnh Hai nhiÖm vô 1 vµ 2 cã thÓ diÔn ®¹t dÔ dµng b»ng PASCAL: 1. readln (n); 2. for i := 1 to n do for j := 1 to n do readln(a[i, j]); NhiÖm vô 3 cÇn ph©n tÝch kü h¬n. Ta thÊy vÒ ®êng chÐo, cã thÓ ph©n lµm hai lo¹i: - §êng chÐo øng víi cét tõ n ®Õn 1 - §êng chÐo øng víi hµng tõ 2 ®Õn n V× vËy, ta t¸ch thµnh hai nhiÖm vô con: 3.1. for j := n down to 1 do { in ®êng chÐo øng víi cét j } 3.2. for i := 2 to n do { in ®êng chÐo øng víi hµng i } Tíi ®©y ta l¹i ph¶i chi tiÕt h¬n c«ng viÖc: “in ®êng chÐo øng cét j” Víi j = n th× in mét phÇn tö hµng 1 cét j j = n - 1 th× in 2 phÇn tö hµng 1 cét j vµ hµng 2 cét j + 1 j = n - 2 th× in 3 phÇn tö hµng 1 cét j, hµng 2 cét j + 1 vµ hµng 3 cét j + 2 Ta thÊy sè lîng c¸c phÇn tö ®îc in chÝnh lµ (n- j + 1), cßn phÇn tö ®îc in chÝnh lµ A[i, j + i-1], víi i lÊy gi¸ trÞ tõ 1 tíi (n- j + 1) VËy 3.1 cã thÓ tinh chØnh tiÕp t¸c vô “in ®êng chÐo øng víi cét j” thµnh: for i := 1 to (n-j +1) do Write (a[i, j + i - 1] : 8); Writeln; ë ®©y, ta tËn dông kh¶ n¨ng cña PASCAL ®Ó in mçi phÇn tö trong mét qu·ng 8 vµ mçi ®êng chÐo sÏ ®îc in trªn mét dßng, sau ®ã ®Ó c¸ch mét dßng trèng. Víi 3.2 còng t¬ng tù for j := 1 to n- i + 1 do Write (a[i + j - 1, j)]:8); Writeln; §Ó cã mét ch¬ng tr×nh Pascal hoµn chØnh tÊt nhiªn ta ph¶i tu©n thñ mäi quy ®Þnh cña PASCAL: ch¼ng h¹n tríc khi bíc vµo phÇn c©u lÖnh thÓ hiÖn phÇn xö lý, ph¶i cã phÇn khai b¸o d÷ liÖu. Ngoµi ra cã thÓ thªm vµo phÇn thuyÕt minh cho c¸c bíc (víi mét ngo¹i lÖ lµ ta viÕt b»ng tiÕng ViÖt). Sau ®©y lµ ch¬ng tr×nh hoµn chØnh: Program INCHEO; Const max = 30; Type matran = array [1…max, 1…max] of integer; Var a: matran; n, i, j:integer; Begin Repeat Write (‘nhËp kÝch thíc n cña ma trËn’); Readln (n); Until (0 < n) and (n <= max); Writeln (‘NhËp phÇn tö ma trËn’); For i := 1 to n do For j := 1 to n do readln (a[i, j]); Writeln (‘In c¸c ®êng chÐo’) For j := n downto 1 do Begin For i := 1 to n- j + 1 do Write (a[i, j + i - 1] : Writeln; End; For i := 2 to n do Begin For j := 1 to n- i + 1 do Write(a[i + j - 1, j] : 8); Writeln; End; End. 4) Bµi to¸n thiÕt lËp quy tr×nh ®iÒu khiÓn ®Ìn giao th«ng Ph¸t biÓu bµi to¸n: Gi¶ sö ta cÇn thiÕt lËp mét quy tr×nh ®Ìn giao th«ng ë mét chèt giao th«ng phøc t¹p, cã nhiÒu giao lé. Nh vËy nghÜa lµ ®iÒu khiÓn ®Ìn b¸o sao cho trong mét kho¶ng thêi gian Ên ®Þnh mét sè tuyÕn ®êng ®îc th«ng, trong khi mét sè tuyÕn kh¸c bÞ cÊm, tr¸nh x¶y ra ®ông ®é. §èi víi bµi to¸n nµy ta thÊy: Ta nhËn ë ®Çu vµo mét sè tuyÕn ®êng cho phÐp (t¹i chèt giao th«ng ®ã) vµ ph¶i ph©n ho¹ch tËp nµy thµnh mét sè Ýt nhÊt c¸c nhãm, sao cho mäi tuyÕn trong mét nhãm ®Òu cã thÓ cho th«ng ®ång thêi mµ kh«ng x¶y ra ®ông ®é. Ta sÏ g¾n mçi pha cña viÖc ®iÒu khiÓn ®Ìn giao th«ng víi mét nhãm trong ph©n ho¹ch nµy vµ viÖc t×m mét ph©n ho¹ch víi sè pha Ýt nhÊt. §iÒu ®ã cã nghÜa lµ thêi gian chê ®îi tèi ®a ®Ó ®îc th«ng còng Ýt nhÊt. VÝ dô nh ë D ®Çu mèi sau E C B A H×nh 2.4 ë ®©y C vµ E lµ ®êng mét chiÒu (1 tuyÕn) cßn c¸c ®êng kh¸c ®Òu hai chiÒu (2 tuyÕn). Nh vËy, sÏ cã 13 tuyÕn cã thÓ thùc hiÖn qua ®Çu mèi nµy. Nh÷ng tuyÕn nh AB (tõ A tíi B), EC cã thÓ th«ng ®ång thêi. Nh÷ng tuyÕn nh AD vµ EB th× kh«ng thÓ th«ng ®ång thêi ®îc v× chóng giao nhau, cã thÓ g©y ra ®ông ®é ( ta sÏ gäi lµ c¸c tuyÕn xung kh¾c). Nh vËy ®Ìn tÝn hiÖu ph¶i b¸o sao cho AD vµ EB kh«ng thÓ ®îc th«ng cïng mét lóc, trong khi ®ã l¹i ph¶i cho phÐp AB vµ EC ch¼ng h¹n ®îc th«ng ®ång thêi. Ta cã thÓ m« h×nh ho¸ bµi to¸n cña ta dùa vµo mét kh¸i niÖm, vèn ®· ®îc ®Ò cËp tíi trong to¸n häc, ®ã lµ ®å thÞ (graph). §å thÞ bao gåm mét tËp c¸c ®iÓm gäi lµ ®Ønh (vetices) vµ c¸c ®êng nèi c¸c ®Ønh gäi lµ cung (edges). Nh vËy ®èi víi bµi to¸n “®iÒu khiÓn híng ®Ìn giao th«ng”cña ta th× cã thÓ h×nh dung mét ®å thÞ mµ c¸c ®Ønh biÓu thÞ cho c¸c tuyÕn ®êng, cßn cung lµ mét cÆp ®Ønh øng víi hai tuyÕn ®êng xung kh¾c. Víi mét ®Çu mèi giao th«ng nh ë h×nh 2.4 ®å thÞ biÓu diÔn nã sÏ nh sau: AB AC A D BA BC BD D A DB DC EA EB ED EC H×nh 2.5 B©y giê ta sÏ t×m lêi gi¶i cho bµi to¸n cña ta dùa trªn m« h×nh ®å thÞ ®· nªu. Ta sÏ thªm vµo kh¸i niÖm “t« mµu cho ®å thÞ”. §ã lµ viÖc g¸n mµu cho mçi ®Ønh cña ®å thÞ sao cho kh«ng cã hai ®Ønh nµo nèi víi nhau bëi mét cung l¹i t« mét mµu. Víi kh¸i niÖm nµy, nÕu ta h×nh dung mçi mµu ®¹i diÖn cho mét pha ®iÒu khiÓn ®Ìn b¸o (cho th«ng mét sè tuyÕn vµ cÊm mét sè tuyÕn kh¸c) th× bµi to¸n ®ang ®Æt ra chÝnh lµ bµi to¸n: t« mµu cho ®å thÞ øng víi c¸c tuyÕn ®êng ë mét ®Çu mèi, nh ®· quy íc ë trªn ( xem h×nh 2.5) sao cho ph¶i dïng Ýt mÇu nhÊt. Bµi to¸n t« mµu cho ®å thÞ ®îc nghiªn cøu tõ nhiÒu thËp kû nay. Tuy nhiªn, bµi to¸n t« mµu cho mét ®å thÞ bÊt kú, víi sè mµu Ýt nhÊt l¹i thuéc vµo mét líp kh¸ réng c¸c bµi to¸n, ®îc gäi lµ “Bµi to¸n N-P ®Çy ®ñ”, mµ ®èi víi chóng th× nh÷ng bµi gi¶i hiÖn cã chñ yÕu thuéc lo¹i “cè hÕt mäi kh¶ n¨ng”. Trong trêng hîp bµi to¸n t« mµu cña ta th× “cè hÕt mäi kh¶ n¨ng” nghÜa lµ cè g¸n mµu cho c¸c ®Ønh, tríc hÕt b»ng mét mµu ®·, kh«ng thÓ ®îc n÷a th× míi dïng mµu thø hai, thø ba v.v… Cho tíi khi ®¹t ®îc môc ®Ých, nghe ra th× cã vÎ tÇm thêng, nhng ®èi víi bµi to¸n lo¹i nµy, ®©y l¹i chÝnh lµ mét gi¶i thuËt cã hiÖu lùc thùc tÕ. VÊn ®Ò gay cÊn nhÊt ë ®©y vÉn lµ kh¶ n¨ng t×m ®îc lêi gi¶i tèi u cho bµi to¸n. NÕu ®å thÞ nhá, ta cã thÓ cè g¾ng theo mäi ph¬ng ¸n, ®Ó cã thÓ ®i tíi mét lêi gi¶i tèi u. Nhng víi ®å thÞ lín th× c¸ch lµm nµy sÏ tæn phÝ rÊt nhiÒu thêi gian, trªn thùc tÕ khã chÊp nhËn ®îc. Còng cã thÓ cã trêng hîp do dùa vµo mét sè th«ng tin phô cña bµi to¸n mµ viÖc t×m lêi gi¶i tèi u kh«ng cÇn ph¶i thö tíi mäi kh¶ n¨ng. Nhng ®ã chØ lµ “nh÷ng dÞp may hiÕm cã”. Cßn mét c¸ch kh¸c n÷a lµ thay ®æi c¸ch nh×n nhËn vÒ lêi gi¶i cña bµi to¸n ®i ®«i chót: Thay v× ®i t×m lêi gi¶i tèi u, ta