Chương I - THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN

Thuật toán (algorithm) là một trong những khái niệm quan trọng nhất trong tin học. Thuật ngữ thuật toán xuất phát từ nhà toán học A rập Abu Jafar Mohammed ibn Musa al Khowarizmi (khoảng năm 825). Tuy nhiên lúc bấy giờ và trong nhiều thế kỷ sau, nó không mang nội dung như ngày nay chúng ta quan niệm. Thuật toán nổi tiếng nhất, có từ thời cổ Hy lạp là thuật toán Euclid, thuật toán tìm ước chung lớn nhất của hai số nguyên. Có thể mô tả thuật toán này như sau :...
Nội dung trích xuất từ tài liệu:
Chương I - THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN Ch¬ng I ThuËt to¸n vµ ph©n tÝch thuËt to¸n 1.1. ThuËt to¸n. 1.1.1. Kh¸i niÖm thuËt to¸n. ThuËt to¸n (algorithm) lµ mét trong nh÷ng kh¸i niÖm quan trängnhÊt trong tin häc. ThuËt ng÷ thuËt to¸n xuÊt ph¸t tõ nhµ to¸n häc A rËpAbu Jafar Mohammed ibn Musa al Khowarizmi (kho¶ng n¨m 825). Tuynhiªn lóc bÊy giê vµ trong nhiÒu thÕ kû sau, nã kh«ng mang néi dungnh ngµy nay chóng ta quan niÖm. ThuËt to¸n næi tiÕng nhÊt, cã tõ thêicæ Hy l¹p lµ thuËt to¸n Euclid, thuËt to¸n t×m íc chung lín nhÊt cña haisè nguyªn. Cã thÓ m« t¶ thuËt to¸n nµy nh sau : ThuËt to¸n Euclid. Input : m, n nguyªn d¬ng Output : g, íc chung lín nhÊt cña m vµ n Ph¬ng ph¸p : Bíc 1 : T×m r, phÇn d cña phÐp chia m cho n Bíc 2 : NÕu r = O, th× g ← n (g¸n gi¸ trÞ cña n cho g) vµ dõng l¹i.Trong trêng hîp ngîc l¹i (r ≠ 0), th× m ← n, n ← r vµ quay l¹i bíc 1. Chóng ta cã thÓ quan niÖm c¸c bíc cÇn thùc hiÖn ®Ó lµm métmãn ¨n, ®îc m« t¶ trong c¸c s¸ch d¹y chÕ biÕn mãn ¨n, lµ mét thuËt to¸n.Còng cã thÓ xem c¸c bíc cÇn tiÕn hµnh ®Ó gÊp ®å ch¬i b»ng giÊy, ®îctr×nh bÇy trong s¸ch d¹y gÊp ®å ch¬i b»ng giÊy, lµ thuËt to¸n. Ph¬ngph¸p thùc hiÖn phÐp céng, nh©n c¸c sè nguyªn, chóng ta ®· häc ë cÊp Icòng lµ c¸c thuËt to¸n. Trong s¸ch nµy chóng ta chØ cÇn ®Õn ®Þnh nghÜa kh«ng h×nhthøc vÒ thuËt to¸n : ThuËt to¸n lµ mét d·y h÷u h¹n c¸c bíc, mçi bíc m« t¶ chÝnh x¸c c¸cphÐp to¸n hoÆc hµnh ®éng cÇn thùc hiÖn, ®Ó gi¶i quyÕt mét sè vÊn®Ò. (Tõ ®iÓm Oxford Dictionary ®Þnh nghÜa, Algorithm: set of well -defined rules for solving a problem in a finite number of steps.) §Þnh nghÜa nµy, tÊt nhiªn, cßn chøa ®ùng nhiÒu ®iÒu cha rârµng. §Ó hiÓu ®Çy ®ñ ý nghÜa cña kh¸i niÖm thuËt to¸n, chóng ta nªura 5 ®Æc trng sau ®©y cña thuËt to¸n (Xem D.E. Knuth [1968]. The Artof Computer Programming, vol. I. Fundamental Algorithms). 5 1. Input. Mçi thuËt to¸n cÇn cã mét sè (cã thÓ b»ng kh«ng) d÷liÖu vµo (input). §ã lµ c¸c gi¸ trÞ cÇn ®a vµo khi thuËt to¸n b¾t ®Çulµm viÖc. C¸c d÷ liÖu nµy cÇn ®îc lÊy tõ c¸c tËp hîp gi¸ trÞ cô thÓ nµo®ã. Ch¼ng h¹n, trong thuËt to¸n Euclid trªn, m vµ n lµ c¸c d÷ liÖu vµolÊy tõ tËp c¸c sè nguyªn d¬ng. 2. Output. Mçi thuËt to¸n cÇn cã mét hoÆc nhiÒu d÷ liÖu ra(output). §ã lµ c¸c gi¸ trÞ cã quan hÖ hoµn toµn x¸c ®Þnh víi c¸c d÷ liÖuvµo vµ lµ kÕt qu¶ cña sù thùc hiÖn thuËt to¸n. Trong thuËt to¸n Euclidcã mét d÷ liÖu ra, ®ã lµ g, khi thùc hiÖn ®Õn bíc 2 vµ ph¶i dõng l¹i (tr-êng hîp r = 0), gi¸ trÞ cña g lµ íc chung lín nhÊt cña m vµ n. 3. TÝnh x¸c ®Þnh. Mçi bíc cña thuËt to¸n cÇn ph¶i ®îc m« t¶ métc¸ch chÝnh x¸c, chØ cã mét c¸ch hiÓu duy nhÊt. HiÓn nhiªn, ®©y lµ mét®ßi hái rÊt quan träng. Bëi v×, nÕu mét bíc cã thÓ hiÓu theo nhiÒu c¸chkh¸c nhau, th× cïng mét d÷ liÖu vµo, nh÷ng ngêi thùc hiÖn thuËt to¸nkh¸c nhau cã thÓ dÉn ®Õn c¸c kÕt qu¶ kh¸c nhau. NÕu ta m« t¶ thuËtto¸n b»ng ng«n ng÷ th«ng thêng, kh«ng cã g× ®¶m b¶o ngêi ®äc hiÓu®óng ý cña ngêi viÕt thuËt to¸n. §Ó ®¶m b¶o ®ßi hái nµy, thuËt to¸ncÇn ®îc m« t¶ trong c¸c ng«n ng÷ lËp tr×nh (ng«n ng÷ m¸y, hîp ng÷hoÆc ng«n ng÷ bËc cao nh Pascal, Fortran, C, ...). Trong c¸c ng«n ng÷nµy, c¸c mÖnh ®Ò ®îc t¹o thµnh theo c¸c qui t¾c có ph¸p nghiªm ngÆtvµ chØ cã mét ý nghÜa duy nhÊt. 4. TÝnh kh¶ thi. TÊt c¶ c¸c phÐp to¸n cã mÆt trong c¸c bíc cñathuËt to¸n ph¶i ®ñ ®¬n gi¶n. §iÒu ®ã cã nghÜa lµ, c¸c phÐp to¸n ph¶isao cho, Ýt nhÊt vÒ nguyªn t¾c cã thÓ thùc hiÖn ®îc bëi con ngêi chØb»ng giÊy tr¾ng vµ bót ch× trong mét kho¶ng thêi gian h÷u h¹n. Ch¼ngh¹n trong thuËt to¸n Euclid, ta chØ cÇn thùc hiÖn c¸c phÐp chia c¸c sènguyªn, c¸c phÐp g¸n vµ c¸c phÐp so s¸nh ®Ó biÕt r = 0 hay r ≠ 0. 5. TÝnh dõng. Víi mäi bé d÷ liÖu vµo tho¶ m·n c¸c ®iÒu kiÖn cñad÷ liÖu vµo (tøc lµ ®îc lÊy ra tõ c¸c tËp gi¸ trÞ cña c¸c d÷ liÖu vµo),thuËt to¸n ph¶i dõng l¹i sau mét sè h÷u h¹n bíc thùc hiÖn. Ch¼ng h¹n,thuËt to¸n Euclid tho¶ m·n ®iÒu kiÖn nµy. Bëi v× gi¸ trÞ cña r lu«n nháh¬n n (khi thùc hiÖn bíc 1), nÕu r ≠ 0 th× gi¸ trÞ cña n ë bíc 2 lµ gi¸ trÞcña r ë bíc tríc, ta cã n > r = n1 > r1 = n2 > r2 ... D·y sè nguyªn d¬ng gi¶mdÇn cÇn ph¶i kÕt thóc ë 0, do ®ã sau mét sè bíc nµo ®ã gi¸ trÞ cña rph¶i b»ng 0, thuËt to¸n dõng. Víi mét vÊn ®Ò ®Æt ra, cã thÓ cã mét hoÆc nhiÒu thuËt to¸ngi¶i. Mét vÊn ®Ò cã thuËt to¸n gi¶i gäi lµ vÊn ®Ò gi¶i ®îc (b»ng thuËtto¸n). Ch¼ng h¹n, vÊn ®Ò t×m nghiÖm cña hÖ ph¬ng tr×nh tuyÕn tÝnhlµ vÊn ®Ò gi¶i ®îc. Mét vÊn ®Ò kh«ng tån t¹i thuËt to¸n gi¶i gäi lµ vÊn®Ò kh«ng gi¶i ®îc (b»ng thuËt to¸n). Mét trong nh÷ng thµnh tùu xuÊt 6s¾c nhÊt cña to¸n häc thÕ kû 20 lµ ®· t×m ra nh÷ng vÊn ®Ò kh«ng gi¶i®îc b»ng thuËt to¸n. Trªn ®©y chóng ta ®· tr×nh bµy ®Þnh nghÜa kh«ng h×nh thøc vÒt ...