Giáo trình Toán rời rạc - Chương 4: Thuật toán

100 trang Đức Chiến 03/01/2024 580

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Chương 4: Thuật toán", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_toan_roi_rac_chuong_4_thuat_toan.pdf

Nội dung text: Giáo trình Toán rời rạc - Chương 4: Thuật toán

Chöông 4: THUAÄT TOAÙN I. Thuaät toaùn vaø caùch bieåu dieãn thuaät toaùn 1.1 Khaùi nieäm thuaät toaùn Thuaät toaùn laø moät khaùi nieäm cô baûn cuûa Toaùn hoïc vaø Tin hoïc. Khi vieát moät chöông trình maùy tính, ngöôøi ta thöôøng caøi ñaët moät phöông phaùp ñaõ ñöôïc nghó ra tröôùc ñoù ñeå giaûi quyeát moät vaán ñeà. Töø “thuaät toaùn” ñöôïc duøng trong khoa hoïc maùy tính ñeå ñeå chæ söï moâ taû moät phöông phaùp giaûi baøi toaùn thích hôïp cho vieäc caøi ñaët thaønh caùc chöông trình nhôø caùc ngoân ngöõ laäp trình. Moät thuaät toaùn thöôøng ñöôïc theå hieän bôûi moät thuû tuïc goàm moät daõy höõu haïn böôùc maø theo ñoù ta seõ ñaït ñeán lôøi giaûi cho baøi toaùn. Ngöôøi ta coù theå trình baøy thuaät toaùn baèng caùch lieät keâ ra caùc böôùc cuûa thuaät toaùn söû duïng ngoân ngöõ töï nhieân hay moät ngoân ngöõ qui öôùc naøo ñoù chaúng haïn söû duïng moät ngoân ngöõ laäp trình naøo ñoù gaàn vôùi ngoân ngöõ töï nhieân. Ví duï 1: thuaät toaùn tìm phaàn töû lôùn nhaát trong moät daõy höõu haïn caùc soá nguyeân. Baøi toaùn tìm phaàn töû lôùn nhaát trong moät daõy höõu haïn töông ñoái taàm thöôøng. Tuy nhieân ñaây laø moät trong nhöõng ví duï khaù toát ñeå minh hoïa cho khaùi nieäm veà thuaät toaùn. Coù nhieàu vaán ñeà maø trong ñoù ñoøi hoûi phaûi tìm soá nguyeân lôùn nhaát trong moät daõy soá. Chaúng haïn nhö vieäc tìm ra moät hoïc sinh coù ñieåm cao nhaát trong moät kyø thi, hay tìm ra moät nhaân vieân coù naêng suaát cao nhaát trong moät xí nghieäp, v.v -120-
Chuùng ta coù nhieàu caùch ñeå giaûi baøi toaùn naày. Moät trong nhöõng phöông phaùp ñeå tìm phaàn töû lôùn nhaát trong moät daõy soá nguyeân laø thöïc hieän moät thuû tuïc theo caùc böôùc sau ñaây: 1. Tröôùc heát ta ñaët cho giaù trò lôùn nhaát taïm thôøi baèng soá nguyeân ñaàu tieân. (Giaù trò lôùn nhaát taïm thôøi naøy chính laø giaù trò lôùn nhaát ôû moãi giai ñoaïn cuûa thuû tuïc.) 2. So saùnh soá nguyeân keá tieáp trong daõy vôùi giaù trò lôùn nhaát taïm thôøi, vaø neáu noù lôùn hôn giaù trò lôùn nhaát taïm thôøi thì ñaët cho giaù trò lôùn nhaát taïm thôøi baèng soá nguyeân naày. 3. Laëp laïi böôùc 2 neáu coøn soá nguyeân trong daõy chöa ñöôïc xeùt tôùi. 4. Döøng neáu khoâng coøn soá nguyeân naøo trong daõy chöa ñöôïc xeùt. Giaù trò lôùn nhaát taïm thôøi luùc naày chính laø giaù trò lôùn nhaát trong daõy soá. Ví duï 2: Thuaät toaùn tính nghieäm cuûa phöông trình baäc hai: ax2 + bx + c = 0 khi bieát 3 heä soá a, b, c (a 0). Böôùc 1: Tính giaù trò theo coâng thöùc = b2 - 4ac Böôùc 2: Xeùt daáu , ta coù keát quaû tuøy thuoäc moät trong 3 tröôøng hôïp sau ñaây: - Tröôøng hôïp > 0: Phöông trình coù 2 nghieäm ñöôïc tính theo coâng thöùc - b x = 2a - Tröôøng hôïp = 0: Phöông trình coù nghieäm keùp ñöôïc tính theo coâng thöùc - b x = 2a -121-
- Tröôøng hôïp < 0: Phöông trình voâ nghieäm. 1.2 Bieåu dieãn thuaät toaùn Ñeå trình baøy moät thuaät toaùn hay bieåu dieãn moät thuaät toaùn, ta coù theå söû duïng caùc phöông phaùp bieåu dieãn thuaät toaùn sau ñaây: 1. Duøng ngoân ngöõ töï nhieân. 2. Duøng löu ñoà hay sô ñoà khoái. 3. Duøng maõ giaû. - Löu ñoà: Ngoân ngöõ löu ñoà hay sô ñoà khoái laø moät coâng cuï raát tröïc quan ñeå dieãn ñaït caùc thuaät toaùn. Bieåu dieãn baèng löu ñoà seõ giuùp ta coù ñöôïc moät caùi nhìn toång quan veà toaøn caûnh cuûa quaù trình xöû lyù theo thuaät toaùn. Löu ñoà laø moät heä thoáng caùc nuùt coù hình daïng khaùc nhau, theå hieän caùc chöùc naêng khaùc nhau vaø ñöôïc noái vôùi nhau bôûi caùc cung. Löu ñoà ñöôïc taïo thaønh bôûi 4 thaønh phaàn chuû yeáu sau ñaây: 1/ Nuùt giôùi haïn: ñöôïc bieåu dieãn bôûi hình oâvan coù ghi chöõ beân trong nhö : BAÉT ÑAÀU KEÁT THUÙC Caùc nuùt treân coøn ñöôïc goïi laø nuùt ñaàu vaø nuùt cuoái cuûa löu ñoà. -122-
2/ Nuùt thao taùc: laø moät hình chöõ nhaät coù ghi caùc leänh caàn thöïc hieän. Ví duï: taêng k 3/ Nuùt ñieàu kieän: thöôøng laø moät hình thoi coù ghi ñieàu kieän caàn kieåm tra. Trong caùc cung noái vôùi nuùt naày coù 2 cung ra chæ höôùng ñi theo 2 tröôøng hôïp: ñieàu kieän ñuùng vaø ñieàu kieän sai. Ví duï: 4/ Cung: laø caùc ñöôøng noái töø nuùt naày ñeán nuùt khaùc cuûa löu ñoà. Hoaït ñoäng cuûa thuaät toaùn theo löu ñoà ñöôïc baét ñaàu töø nuùt ñaàu tieân. Sau khi thöïc hieän caùc thao taùc hoaëc kieåm tra ñieàu kieän ôû moãi nuùt thì boä xöû lyù seõ theo moät cung ñeå ñeán nuùt khaùc. Quaù trình thöïc hieän thuaät toaùn döøng khi gaëp nuùt keát thuùc hay nuùt cuoái. Trong giaùo trình naày chuùng ta chuû yeáu laø söû duïng ngoân ngöõ töï nhieân vaø maõ giaû ñeå trình baøy thuaät toaùn. Trong caùch söû duïng ngoân ngöõ töï nhieân ta seõ lieät keâ caùc böôùc thöïc hieän caùc thao taùc hay coâng vieäc naøo ñoù cuûa thuaät toaùn baèng ngoân ngöõ maø con ngöôøi söû duïng moät caùch phoå thoâng haøng ngaøy. Caùc thuaät toaùn ñöôïc trình baøy trong hai ví duï treân -123-
chính laø caùch bieåu dieãn thuaät toaùn duøng ngoân ngöõ töï nhieân. Maëc duø caùch bieåu dieãn naày khaù töï nhieân vaø khoâng ñoøi hoûi ngöôøi vieát thuaät toaùn phaûi bieát nhieàu quy öôùc khaùc, nhöng noù khoâng theå hieän roõ tính caáu truùc cuûa thuaät toaùn neân khoâng thuaän lôïi cho vieäc thieát keá vaø caøi ñaët nhöõng thuaät toaùn phöùc taïp. Hôn nöõa trong nhieàu tröôøng hôïp vieäc bieåu dieãn thuaät toaùn baèng ngoân ngöõ töï nhieân toû ra daøi doøng vaø deõ gaây ra söï nhaàm laãn ñoái vôùi ngöôøi ñoïc. Coøn vieäc söû duïng löu ñoà seõ raát coàng keành ñoái vôùi caùc thuaät toaùn phöùc taïp. - Maõ giaû: Ñeå bieåu dieãn thuaät toaùn moät caùch hieäu quaû, ngöôøi ta thöôøng duøng maõ giaû (pseudocode). Theo caùch naày, ta seõ söû duïng moät soá qui öôùc cuûa moät ngoân ngöõ laäp trình, chaúng haïn laø ngoâng ngöõ laäp trình PASCAL, nhaát laø caùc caáu truùc ñieàu khieån cuûa ngoân ngöõ laäp trình nhö caùc caáu truùc choïn, caùc caáu truùc laëp. Trong maõ giaû ta coøn söû duïng caû caùc kyù hieäu toaùn hoïc, caùc bieán, vaø ñoâi khi caû caáu truùc kieåu thuû tuïc. Caáu truùc thuaät toaùn kieåu thuû tuïc thöôøng ñöôïc söû duïng ñeå trình baõy caùc thuaät toaùn ñeä qui hay caùc thuaät toaùn quaù phöùc taïp caàn phaûi ñöôïc trình baøy thaønh nhieàu caáp ñoä. Cuøng vôùi vieäc söû duïng caùc bieán, trong thuaät toaùn raát thöôøng gaëp moät phaùt bieåu haønh ñoäng ñaët (hay gaùn) moät giaù trò cho moät bieán. Ví du:ï haønh ñoäng taêng bieát i leân 1 coù theå ñöôïc vieát nhö sau: i := i + 1 hay i  i + 1 -124-
Caùc caáu thöôøng ñöôïc söû duïng trong maõ giaû döïa theo ngoân ngöõ laäp trình PASCAL goàm: 1/ Caáu truùc choïn: if (ñieàu kieän) then (haønh ñoäng) if (ñieàu kieän) then (haønh ñoäng) else (haønh ñoäng) 2/ Caáu truùc laëp: while (ñieàu kieän) do (haønh ñoäng) Repeat (haønh ñoäng) Until (ñieàu kieän) for (bieán) := (giaù trò ñaàu) to (giaù trò cuoái) do (haønh ñoäng) for (bieán) := (giaù trò ñaàu) downto (giaù trò cuoái) do (haønh ñoäng) 3/ Caáu truùc nhaûy goto. Ngoaøi ra ngöôøi ta coøn söû duïng leänh ngaét voøng laëp break. Döôùi ñaây laø caùc thuaät toaùn ñöôïc bieåu dieãn baèng maõ giaû (söû duïng caùc caáu truùc ñieàu khieån cuûa ngoân ngöõ laäp trình PASCAL). Tröôùc khi vieát -125-
caùc böôùc thöïc hieän thuaät toaùn ta thöôøng ghi roõ nhöõng gì ñöôïc cho tröôùc (phaàn nhaäp) vaø keát quaû caàn ñaït ñöôïc (phaàn xuaát). - Thuaät toaùn tìm phaàn töû lôùn nhaát trong moät daõy höõu haïn caùc soá nguyeân: Nhaäp: daõy soá a1, a2, . . ., an Xuaát: max laø giaù trò lôùn nhaát trong daõy soá ñaõ cho trong input. Thuaät toaùn: 1. max := a1 2. for i := 2 to n do if max 0 then begin x1 := (-b - sqrt(delta)) / (2*a); x2 := (-b+sqrt(delta)) / (2*a); Xuaát keát quaû: phöông trình coù hai nghieäm laø x1 vaø x2; end 3. esle if delta = 0 then Xuaát keát quaû: phöông trình coù nghieäm keùp laø -b / (2*a) 4. else tröôøng hôïp delta < 0 -126-
Xuaát keát quaû: phöông trình voâ nghieäm; (Trong thuaät toaùn naày, kyù hieäu sqrt(delta) duøng ñeå chæ caên baäc hai döông cuûa delta) 1.3 Caùc tính chaát cuûa thuaät toaùn Thuaät toaùn coù vai troø raát quan troïng trong khoa hoïc maùy tính. Ñeå coù theå laäp trình giaûi baøi toaùn treân maùy tính, ta caàn coù moät thuaät toaùn baûo ñaûm nhöõng tính chaát nhaát ñònh. Khi moâ taû moät thuaät toaùn chuùng ta caàn chuù yù ñeán caùc tính chaát sau ñaây: Nhaäp (input): Caùc thuaät giaûi coù caùc giaù trò nhaäp (input values) töø moät taäp hôïp nhaát ñònh naøo ñoù. Xuaát (output): Töø moãi taäp hôïp caùc giaù trò ñöôïc nhaäp moät thuaät toaùn thöôøng taïo ra nhöõng giaù trò xuaát (output values) thuoäc moät taäp hôïp nhaát ñònh naøo ñoù theå hieän lôøi giaûi cho baøi toaùn. Tính xaùc ñònh (definiteness): Caùc böôùc trong thuaät toaùn phaûi chính xaùc roõ raøng. Tính höõu haïn (finiteness): Thuaät toaùn phaûi cho ra lôøi giaûi (hay keát quaû) sau moät soá höõu haïn böôùc. Tính hieäu quaû (veà thôøi gian): Thuaät toaùn caàn phaûi ñöôïc thöïc hieän moät caùch chính xaùc vaø trong moät khoaûng thôøi gian cho pheùp. Tính toång quaùt. Thuaät toaùn phaûi aùp duïng ñöôïc cho taát caû caùc baøi toaùn coù daïng nhö mong muoán, chöù khoâng phaûi chæ aùp duïng ñöôïc cho moät soá tröôøng hôïp ñaëc bieät naøo ñoù. Tình ñuùng: Thuaät toaùn phaûi cho keát quaû nhö mong muoán. -127-
Trong caùc tính chaát treân, 3 tính chaát cô baûn cuûa thuaät toaùn ñoøi hoûi phaûi ñöôïc thoûa maõn laø tính xaùc ñònh, tính höõu haïn vaø tính ñuùng. Caùc thuaät toaùn trong hai ví duï 1 vaø 2 ñöôïc trình baøy ôû treân ñeàu thoûa maõn caùc tính chaát neâu treân. Döôùi ñaây chuùng ta xeùt theâm moät soá ví duï veà caùc thuaät toaùn. Ví duï 3: Thuaät toaùn tìm kieám tuyeán tính (Linear Search) Baøi toaùn ñöôïc ñaët ra laø xaùc ñònh xem moät phaàn töû x coù trong moät daõy a1, a2, . . ., an hay khoâng? Lôøi giaûi cuûa baøi toaùn naày laø giaù trò chæ vò trí (hay chæ soá) cuûa moät phaàn töû trong daõy baèng phaàn töû x, hoaëc laø 0 neáu x khoâng coù trong daõy. Moät thuaät toaùn ñôn giaûn ñeå giaûi baøi toaùn naày laø thuaät toaùn tìm kieám tuyeán tính (hay coøn goïi laø tìm kieám tuaàn töï). Thuaät toaùn baét ñaàu baèng vieäc so saùnh x vôùi a1, vaø neáu x = a1 thì lôøi giaûi laø vò trí cuûa a1(töùc laø 1). Khi x a1, ta tieáp tuïc so saùnh x vôùi a2. Neáu x = a2, thì lôøi giaûi laø vò trí cuûa a2(töùc laø 2). Khi x a2, ta tieáp tuïc so saùnh x vôùi a3. Cöù tieáp tuïc quaù trình naày: laàn löôït so saùnh x vôùi töøng phaàn töû cuûa daõy cho tôùi khi gaëp moät phaàn töû baèng x hoaëc laø cho tôùi khi ñaït ñeán cuoái daõy. Lôøi giaûi laø vò trí cuûa phaàn töû trong daõy baèng x; hoaëc laø 0 neáu khoâng coù phaàn töû naøo trong daõy baèng x. Thuaät toaùn naày coù theå ñöôïc vieát döôùi daïng maõ giaû nhö döôùi ñaây. Thuaät toaùn: Tìm kieám tuyeán tính (hay tuaàn töï) Nhaäp : daõy a1, a2, . . ., an, vaø phaàn töû x. Xuaát : vò trí cuûa x trong daõy (chæ soá cuûa phaàn töû trong daõy baèng vôùi x), hoaëc 0 -128-
Thuaät toaùn: 1. i := 1 2. while ( i n and x ai ) do i := i + 1; 3. if i n then location := i else location := 0 4. location laø moät lôøi giaûi (ví trí caàn tìm). Trong thuaät toaùn naày töø "location" laø moät bieán nguyeân. Ghi chuù : Trong tröôøng hôïp daõy a1, a2, . . ., an coù thöù töï thì ta coù theå tìm kieám theo thuaät toaùn tìm kieám nhò phaân (binary search). Ta coù theå tham khaûo thuaät toaùn naày trong caùc saùch veà "caáu truùc döõ lieäu vaø thuaät toaùn". Ví duï 4: thuaät toaùn kieåm tra tính ñoái xöùng cuûa moät ma traän. Nhaäp : ma traän M caáp n. Xuaát : Yes neáu ma traän M laø ma traän ñoái xöùng. No neáu M khoâng ñoái xöùng. Thuaät toaùn: 1. for i := 1 to n-1 do 2. for j := i + 1 to n do 3. if Mij Mij then Keát xuaát “No”, vaø döøng thuaät toaùn. 4. Keát xuaát “Yes”. -129-
II. Ñoä phöùc taïp cuûa thuaät toaùn 2.1 Khaùi nieäm ñoä phöùc taïp cuûa thuaät toaùn Moät chöông trình maùy tính thöôøng ñöôïc caøi ñaët döïa treân moät thuaät toaùn ñeå giaûi baøi toaùn hay vaán ñeà ñaët ra. Moät ñoøi hoûi ñöông nhieân laø thuaät toaùn phaûi ñuùng. Tuy nhieân, ngay caû khi thuaät toaùn ñuùng, chöông trình vaãn coù theå laø khoâng söû duïng ñöôïc ñoái vôùi moät soá döõ lieäu nhaäp naøo ñoù bôûi vì thôøi gian caàn thieát ñeå chaïy chöông trình hay vuøng nhôù caàn thieát ñeå löu tröõ döõ lieäu (nhö caùc bieán trong chöông trình, caùc file löu tröõ, ) quaù lôùn. Thuaät ngöõ phaân tích thuaät toaùn ñeà caäp ñeán moät quaù trình tìm ra moät ñaùnh giaù veà thôøi gian vaø khoâng gian caàn thieát ñeå thöïc hieän thuaät toaùn. Ñoä phöùc taïp cuûa thuaät toaùn ñöôïc theå hieän qua khoái löôïng thôøi gian vaø khoâng gian ñeå thöïc hieän thuaät toaùn. Khoâng gian ôû ñaây ñöôïc hieåu laø caùc yeâu caàu veà boä nhôù, thieát bò löu tröõ, cuûa maùy tính ñeå thuaät toaùn coù theå laøm vieäc ñöôïc. Vieäc xem xeùt ñoä phöùc taïp veà khoâng gian cuûa thuaät toaùn phuï thuoäc phaàn lôùn vaøo caáu truùc döõ lieäu ñöôïc söû duïng trong caøi ñaët thuaät toaùn. Trong phaàn naày chuùng ta chæ ñeà caäp ñeán ñoä phöùc taïp veà thôøi gian cuûa thuaät toaùn. Chuùng ta cuõng coù theå ñaït ñöôïc nhöõng thoâng tin raát höõu ích khi phaân tích ñoä phöùc taïp thôøi gian cuûa thuaät toaùn cô sôû cuûa moät chöông trình maùy tính. Ñaùnh giaù moät caùch chính xaùc thôøi gian thöïc hieän moät chöông trình phuï thuoäc vaøo raát nhieàu yeáu toá vaø laø moät coâng vieäc raát khoù khaên. Tuy nhieân caùc nhaø toaùn hoïc ñaõ phaân tích cho chuùng ta haàu ñoä phöùc taïp cuûa haàu heát caùc thuaät toaùn thöôøng ñöôïc söû duïng nhö caùc thuaät toaùn saép xeáp, caùc thuaät toaùn tìm kieám, caùc thuaät toaùn soá hoïc, v.v -130-
Ñoä phöùc taïp thôøi gian cuûa thuaät toaùn thöôøng ñöôïc ñaùnh giaù döïa vaøo soá löôïng thao taùc ñöôïc söû duïng trong thuaät toaùn vaø soá löôïng thao taùc naày phuï thuoäc vaøo côû (size) cuûa döõ lieäu nhaäp. Ta coøn goïi ñoä phöùc taïp thôøi gian cuûa thuaät toaùn laø ñoä phöùc taïp tính toaùn. Caùc thao taùc ñöôïc söû duïng ñeå ño ñoä phöùc taïp cuûa thuaät toaùn coù theå laø pheùp so saùnh 2 soá nguyeân, coäng 2 soá nguyeân, nhaân 2 soá nguyeân, chia 2 soá nguyeân, hay baát kyø thao taùc cô baûn naøo khaùc. Nhö theá ta coù theå xem thôøi gian thöïc hieän thuaät toaùn laø moät haøm phuï thuoäc vaøo döõ lieäu nhaäp (thöôøng laø côû cuûa döõ lieäu nhaäp). Neáu goïi côû döõ lieäu nhaäp laø n thì ñoä phöùc taïp coù theå ñöôïc xem laø moät haøm theo n. Chuùng ta coù theå ñaët ra caâu hoûi veà thôøi gian thöïc hieän thuaät toaùn nhoû nhaát ñoái vôùi caùc döõ lieäu nhaäp coù côû n. Ta coù theå neâu leân moät soá baøi toaùn coù döõ lieäu nhaäp coù côû n nhö: saép xeáp daõy n soá nguyeân, tìm soá nhoû nhaát trong daõy n soá nguyeân, v.v Thôøi gian nhoû nhaát naày ñöôïc goïi laø thôøi gian thöïc hieän thuaät toaùn trong tröôøng hôïp toát nhaát ñoái vôùi döõ lieäu nhaäp coù côû n. Töông töï ta cuõng thöôøng ñeà caäp ñeán thôøi gian thöïc hieän thuaät toaùn lôùn nhaát ñoái vôùi caùc döõ lieäu nhaäp coù côû n, vaø goïi laø thôøi gian thöïc hieän thuaät toaùn trong tröôøng hôïp xaáu nhaát ñoái vôùi döõ lieäu nhaäp coù côû n. Ngoaøi ra, ñoái vôùi thuaät toaùn coù döõ lieäu nhaäp coù côû n trong moät taäp höõu haïn naøo ñoù, ta coøn muoán tính ra thôøi gian trung bình ñeå thöïc hieän thuaät toaùn. Ví duï 1: Thuaät toaùn tìm giaù trò lôùn nhaát trong daõy goàm n soá nguyeân (xem ví duï 1, muïc I). Trong thuaät toaùn naày neáu ta xem thôøi gian thöïc hieän thuaät toaùn laø soá laàn thöïc hieän pheùp so saùnh hay pheùp gaùn thì thôøi gian thöïc hieän thuaät toaùn trong tröôøng hôïp xaáu nhaát laø: t(n) = 1 + 2*(n-1) = 2n+1 vaø thôøi gian thöïc hieän thuaät toaùn trong tröôøng hôïp toát nhaát laø: T(n) = 1 + (n-1) = n. -131-
2.2 Kyù hieäu O Vieäc tính toaùn ñoä phöùc taïp (veà thôøi gian hay veà tính toaùn) cuûa thuaät toaùn seõ giuùp ta coù theå ñaùnh giaù vaø so saùnh caùc thuaät toaùn. Tuy nhieân coù nhöõng tröôøng hôïp maø 2 thuaät toaùn khaùc nhau ñeå giaûi quyeát cuøng moät baøi toaùn coù soá löôïng thao taùc cô baûn laø f(n) vaø g(n), vôùi n laø côû döõ lieäu nhaäp, raát khoù so saùnh ñaùnh giaù hôn keùm theo söï so saùnh lôùn beù thoâng thöôøng. Hôn nöõa trong haàu heát caùc thuaät toaùn nhö thuaät toaùn saép xeáp, thuaät toaùn tìm kieám, ta khoâng theå tính ra ñöôïc soá löôïng thao taùc f(n) theo n. Thoâng thöôøng ta ít chuù yù tôùi con soá chính xaùc veà thôøi gian thöïc hieän thuaät toaùn trong tröôøng hôïp xaáu nhaát vaø trong tröôøng hôïp toát nhaát. Ñieàu maø chuùng ta thöôøng quan taâm hôn khi ñaùnh giaù ñoä phöùc taïp thôøi gian cuûa thuaät toaùn laø möùc ñoä taêng leân cuûa thôøi gian thöïc hieän thuaät toaùn khi côû cuûa döõ lieäu nhaäp taêng leân. Chaúng haïn, moät thuaät toaùn ñang ñöôïc xem xeùt naøo ñoù coù thôøi gian thöïc hieän trong tröôøng hôïp xaáu nhaát vaø trong tröôøng hôïp toát nhaát laàn löôït laø: t(n) = 20n2 + 5n + 1, T(n) = n2 + 10n + 1. Nhö theá, neáu nhö n raát lôùn thì ta coù theå xaáp xæ t(n) vaø T(n) vôùi 20n2 vaø n2. Coù theå noùi raèng t(n) vaø T(n) taêng gioáng nhö n2 khi n taêng. Ñeå dieãn ñaït ñieàu naày, ngöôøi ta ñònh nghóa vaø söû duïng kyù hieäu O ñöôïc ñònh nghóa nhö döôùi ñaây. - Ñònh nghóa: Cho 2 haøm thöïc f vaø g coù mieàn xaùc ñònh trong taäp soá töï nhieân N. Ta vieát: f(n) O(g(n)) -132-
vaø noùi laø f(n) coù caáp cao nhaát laø g(n), hay f(n) thuoäc lôùp O(g(n)), khi coù moät haèng soá döông C sao cho: f(n) C . | g(n) |, vôùi “haàu heát” n thuoäc mieàn xaùc ñònh cuûa caùc haøm f vaø g. Töø “haàu heát” ôû ñaây yù noùi laø “vôùi moïi chæ tröø moät soá höõu haïn”, hay noùi moät caùch chính xaùc laø  C > 0,  k N,  n N, n k f(n) C . | g(n) | Ví duï: 1. Vôùi t(n) = 20n2 + 5n + 1 vaø T(n) = n2 + 10n + 1. Ta coù theå chöùng minh ñöôïc raèng noùi t(n) vaø T(n) coù caáp cao nhaát laø n2, töùc laø t(n) O(n2) vaø T(n) O(n2). 2. Xeùt f(n) = log (n!). Ta coù n! = 1.2. . .n n.n. . .n nn log(n!) log (nn) = n.log(n) Suy ra log(n!) O(n log n) - Ñònh lyù: Neáu f(n) laø moät ña thöùc baäc k theo n, töùc laø f(n) coù daïng k k-1 f(n) = akn + ak-1n + . . . + a1n + a0, vôùi ak 0, thì ta coù f(n) thuoäc lôùp O(nk). - Ngoaøi ra ta coøn coù caùc tính chaát sau ñaây: Giaû söû raèng f1(n) O(g1(n)) vaø f2(n) O(g2(n)). Khi aáy ta coù f1(n) + f2(n) O ( max(g1(n), g2(n)) ) -133-
Heä quaû laø neáu f1(n) vaø f2(n) ñeàu thuoäc O(g(n)) thì ta cuõng coù f1(n) + f2(n) O(g(n)) Giaû söû raèng f1(n) O(g1(n)) vaø f2(n) O(g2(n)). Khi aáy ta coù f1(n).f2(n) O ( g1(n).g2(n) ) Ví duï 2: Ñaùnh giaù ñoä phöùc taïp (thôøi gian) cuûa thuaät toaùn tìm kieám tuyeán tính (xem ví duï 3 ôû muïc I) Ñoái vôùi thuaät toaùn naày, trong tröôøng hôïp toát nhaát (phaàn töû caàn tìm naèm ngay taïi vò trí ñaàu tieân cuûa daõy) thôøi gian thöïc hieän thuaät toaùn laø 1. Ta vieát thôøi gian thöïc hieän thuaät toaùn trong tröôøng hôïp toát nhaát laø: O(1). Ta cuõng coù theå tính toaùn ra ñöôïc thôøi gian thöïc hieän thuaät toaùn trong tröôøng hôïp xaáu nhaát vaø thôøi gian thöïc hieän thuaät toaùn trung bình ñeàu laø O(n). 2.3 Moät soá lôùp ñoä phöùc taïp Lieân quan ñeán ñoä phöùc taïp cuûa thuaät toaùn ta coù moät soá thuaät ngöõ thöôøng duøng trong söï phaân lôùp caùc ñoä phöùc taïp cuûa thuaät toaùn ñöôïc lieät keâ döôùi ñaây: - ñoä phöùc taïp haèng: O(1). - ñoä phöùc taïp logarith: O(log n). - ñoä phöùc taïp tuyeán tính: O(n). - ñoä phöùc taïp n log n: O(n log n). -134-
- ñoä phöùc taïp ña thöùc: O(nb). - ñoä phöùc taïp luõy thöøa: O(bn), trong ñoù b > 1. - ñoä phöùc taïp giai thöøa: O(n!). III. Thuaät toaùn ñeä quy 3.1 Khaùi nieäm ñeä quy Thuaät toaùn ñeä qui laø moät trong nhöõng söï môû roäng cuûa khaùi nieäm thuaät toaùn. Nhö ñaõ bieát, moät thuaät toaùn ñöôïc ñoøi hoûi phaûi thoûa maõn caùc tính chaát: - Tính xaùc ñònh. - Tính höõu haïn hay tính döøng. - Tính ñuùng. Tuy nhieân coù nhöõng tröôøng hôïp vieäc tìm ra moät thuaät toaùn vôùi nhöõng tính chaát ñoøi hoûi nhö treân raát khoù khaên nhöng coù caùch giaûi coù theå vi phaïm caùc tính chaát cuûa thuaät toaùn nhöng laïi khaù ñôn giaûn vaø ñöôïc chaáp nhaän. Ví duï nhöõng tröôøng hôïp baøi toaùn coù theå ñöôïc phaân tích vaø ñöa tôùi vieäc giaûi moät baøi toaùn cuøng loaïi nhöng caáp ñoä thaáp hôn, chaúng haïn côû döõ lieäu nhaäp nhoû hôn, giaù trò caàn tính toaùn nhoû hôn, v.v Ta cuõng thöôøng thaáy nhöõng ñònh nghóa veà nhöõng ñoái töôïng, nhöõng khaùi nieäm döïa treân chính nhöõng ñoái töôïng, nhöõng khaùi nieäm ñoù nhö nhöõng ví duï döôùi ñaây. Ví duï 1: Ñònh nghóa giai thöøa. Giai thöøa cuûa moät soá töï nhieân n, kyù hieäu laø n!, ñöôïc ñònh nghóa baèng caùch qui naïp nhö sau: -135-
0! = 1, n! = (n-1)!*n, vôùi moïi n > 0. Ví duï 2: Ñònh nghóa daõy soá Fibonacci f1, f2, . . ., fn,  : f0 = 1, f1 = 1, fn = fn-1 + fn-2 , vôù moïi n > 1. Thuaät toaùn ñeå giaûi caùc baøi toaùn trong nhöõng tröôøng hôïp nhö treân thöôøng ñöôïc vieát döïa treân chính noù, töùc laø trong caùc böôùc cuûa thuaät toaùn coù theå coù tröôøng hôïp thöïc hieän laïi chính thuaät toaùn ñoù (nhöng thöôøng laø vôùi döõ lieäu nhaäp coù côû thaáp hôn, hay coù caáp ñoä thaáp hôn). Nhöõng thuaät toaùn loaïi naày ñöôïc goïi laø nhöõng thuaät toaùn ñeä quy. Döôùi ñaây laø caùc thuaät toaùn ñeä quy tính giai thöøa cuûa moät soá töï nhieân n vaø tính soá haïng thöù n cuûa daõy soá Fibonacci. Thuaät toaùn ñeä quy tính giai thöøa cuûa moät soá töï nhieân. Input : soá töï nhieân n. Output : F (n) baèng n!. Thuaät toaùn : 1. F := 1 2. if n > 0 then F := F(n-1) * n; Tính (n-1)! roài nhaân vôùi n seõ ñöôïc giaù trò F 3. Output F. Thuaät toaùn ñeä quy tính soá haïng thöù n cuûa daõy soá Fibonacci. Input : soá nguyeân döông n. Output : F (n) baèng soá haïng thöù n cuûa daõy Fibonacci. -136-
Thuaät toaùn : 1. if n=0 or n=1 then F := 1; 2. if n > 1 then F := F(n-1) + F(n-2) töùc laø tính F(n-1) vaø F(n-2) roài tính toång soá cuûa caùc giaù trò naày ñeå gaùn cho F 3. Output F. Trong thuaät toaùn tính giai thöøa n ôû treân, coù moät böôùc maø ta tính (n-1)! ñeå töø ñoù tính ra keát quaû. Ñoù laø böôùc 2 trong tröôøng hôïp n > 0. Chính böôùc tính (n-1)! naày trong thuaät toaùn laøm cho thuaät toaùn trôû thaønh thuaät toaùn ñeä quy. Ta coøn goïi böôùc naày laø böôùc thöïc hieän ñeä quy. Trong thuaät toaùn tính soá haïng thöù n, kyù hieäu F(n), cuûa daõy soá Fibonacci ôû treân ta phaûi tính F(n-1) vaø F(n-2) neáu n > 1 trong böôùc 2. Böôùc tính F(n-1) vaø F(n-2) naày chính laø böôùc ñeä quy cuûa thuaät toaùn. Thuaät toaùn ñeä quy ñaõ vi phaïm tính xaùc ñònh vaø roõ raøng cuûa thuaät toaùn vì ôû caùc böôùc ñeä quy cuûa noù. Tuy nhieân ta vaãn chaáp nhaän caùc thuaät toaùn ñeä quy vì noù tieän lôïi trong nhieàu tröôøng hôïp chaúng haïn nhö vieäc caøi ñaët caùc ñònh nghóa ñeä quy hay trong nhöõng tröôøng hôïp baøi toaùn coù theå ñöôïc ñöa veà baøi toaùn cuøng loaïi ôû möùc ñoä thaáp hôn. Hôn nöõa caùc ngoân ngöõ laäp trình ñeàu cho pheùp ta vieát caùc chöông trình con (thuû tuïc hay haøm) döôùi daïng ñeä quy. Öu theá cuûa thuaät toaùn ñeä quy laø khi suy nghó veà phöông phaùp giaûi baøi toaùn baèng caùch phaân chia tröôøng hôïp maø trong ñoù coù nhöõng tröôøng hôïp baøi toaùn ñöôïc thu goïn veà baøi toaùn cuøng loaïi vôùi caáp ñoä thaáp hôn, vaø nhöõng tröôøng hôïp naày chính laø nhöõng tröôøng hôïp maø ta phaûi thöïc hieän böôùc ñeä quy. Coøn nhöõng tröôøng hôïp khaùc thì ta coù theå giaûi quyeát tröïc tieáp moät caùch deã daøng, vaø ta goïi nhöõng tröôøng hôïp naày laø nhöõng -137-
tröôøng hôïp döøng ñeä quy. Ví duï nhö trong vieäc tính soá haïng F(n) öùng vôùi chæ soá n cuûa daõy Fibonacci thì tröôøng hôïp n = 0 vaø tröôøng hôïp n = 1 laø caùc tröôøng hôïp döøng ñeä quy, coøn tröôøng hôïp n > 1 laø tröôøng hôïp maø ta phaûi thöïc hieän caùc böôùc ñeä quy: tính caùc soá haïng F(n-1) vaø F(n- 2) ñeå suy ra soá haïng F(n). 3.2 Caáu truùc cuûa thuaät toaùn ñeä quy - Trong thuaät giaûi ñeä qui thöôøng goàm 2 phaàn: phaàn cô sôû vaø phaàn ñeä quy. Phaàn cô sôû goàm caùc tröôøng hôïp khoâng caàn thöïc hieän laïi thuaät toaùn, töùc laø caùc tröôøng hôïp döøng maø ta coù theå tröïc tieáp giaûi quyeát ñöôïc baøi toaùn (hay khoâng coù yeâu caàu goïi ñeä qui). Trong thuaät toaùn tìm soá haïng thöù n cuûa daõy Fibonacci ôû treân, böôùc 1 trong thuaät toaùn laø phaàn cô sôû cuûa thuaät giaûi ñeä qui. Phaàn ñeä quy laø phaàn trong thuaät toaùn coù yeâu caàu goïi ñeä quy, töùc laø yeâu caàu thöïc hieän laïi thuaät toaùn ôû caáp ñoä thaáp hôn. Trong thuaät toaùn tìm soá haïng thöù n cuûa daõy Fibonacci ôû treân, böôùc 2 trong thuaät toaùn laø phaàn ñeä quy. Trong phaàn ñeä quy, yeâu caàu goïi ñeä qui thöôøng ñöôïc ñaët trong moät ñieàu kieän kieåm tra vieäc goïi ñeä quy. Caàn löu yù raèng phaàn cô sôû luoân luoân phaûi coù hay noùi caùch khaùc laø phaàn ñeä quy luoân luoân phaûi naèm trong ñieàu kieän kieåm soaùt döøng ñeä quy, vì neáu khoâng thì thuaät toaùn seõ bò laëp voâ haïn do vieäc goïi ñeä quy luoân ñöôïc thöïc hieän. - Veà maët caøi ñaët, neáu nhö coù söû duïng bieán cuïc boä trong thuû tuïc hay haøm ñeä quy thì caùc bieán naày ñöôïc taïo ra vaø ñöôïc ñaët trong vuøng nhôù “STACK”. Do ñoù quaù trình goïi ñeä quy deã gaây ra tình traïng traøn stack (stack overflow). Trong nhieàu tröôøng hôïp coù theå ñöôïc -138-
ngöôøi ta tìm caùch vieát laïi thuaät toaùn ñeä quy döôùi daïng laëp. Thuaät toaùn ñeä qui ñeå tìm soá haïng thöù n cuûa daõy soá Fibonacci vaø thuaät toaùn tính n! coù theå ñöôïc vieát laïi döôùi daïng laëp nhö sau: Thuaät toaùn laëp tính soá haïng thöù n cuûa daõy soá Fibonacci. Input : soá nguyeân döông n. Output : F (n) baèng soá haïng thöù n cuûa daõy Fibonacci. Thuaät toaùn : 1. a := 1 2. F := 1 3. for i:=3 to n do begin temp := a + F; a := F; F := temp; end; 4. Output F. Thuaät toaùn laëp tính giai thöøa cuûa moät soá töï nhieân. Input : soá töï nhieân n. Output : F (n) baèng n!. Thuaät toaùn : 1. F := 1 2. for i := 2 to n do F := F * i 3. Output F. -139-
3.3 Trình baøy (hay vieát) thuaät toaùn ñeä quy Ñeå tieän trình baøy thuaät toaùn ñeä quy, nhaát laø ôû caùc böôùc goïi ñeä quy (hay thöïc hieän ñeä quy), ta thöôøng ñaët teân cho thuaät toaùn coù ñi keøm caùc tham bieán chính lieân quan ñeán baøi toaùn cuõng gioáng nhö ta khai baùo thuû tuïc hay haøm trong caùc chöông trình maùy tính. Döôùi ñaây ta xeùt 2 ví duï khaùc veà caùc baøi toaùn maø ta coù theå giaûi baèng phöông phaùp ñeä quy. Ví duï 1: Tính toå hôïp n choïn k, kyù hieäu laø C(n,k). Nhaéc laïi moät soá tính chaát cuûa C(n,k): C(n,0) = C(n,n) = 1, vaø C(n,k) = C(n-1,k) + C(n-1,k-1) neáu 0 < k < n. Caùc tính chaát treân cuûa pheùp tính toå hôïp cho ta moät caùch tính toå hôïp theo phöông phaùp ñeä quy. Ñaët teân cho thuaät toaùn tính toå hôïp n choïn k laø Tohop(n,k) ta coù thuaät toaùn ñeä quy ñeå tính toå hôïp sau ñaây: Thuaät toaùn tính toå hôïp n choïn k: Tohop(n,k) If (k = 0) or (k = n) then Tohop := 1; If (0 < k) and (k < n) then Tohop := Tohop(n-1, k) + Tohop(n-1, k-1); Ví duï 2: Tính öôùc soá chung lôùn nhaát cuûa 2 soá töï nhieân a vaø b, kyù hieäu laø USCLN(a,b). -140-
Töø caùc tính chaát döôùi ñaây (cho caùc soá nguyeân tuøy yù) cuûa pheùp tính öôùc soá chung lôùn nhaát: USCLN(a, 0) = USCLN(0, a) = a, USCLN(a, b) = USCLN(a-b, b), vaø USCLN(a, b) = USCLN(a, b-a) Ta coù ngay moät caùch tính USCLN theo phöông phaùp ñeä quy. Ñaët teân cho thuaät toaùn tính USCLN cuûa 2 soá töï nhieân a vaø b laø USCLN(a, b) ta coù thuaät toaùn ñeä quy sau ñaây: Thuaät toaùn tính USCLN cuûa a vaø b: USCLN(a,b) If (a = 0) or (b = 0) then USCLN := a+b; Else If (a > b) then USCLN := USCLN(a-b, b); Else USCLN := USCLN(a, b -a); Ghi chuù: Moät ví duï khaù toát ñeå minh hoïa cho thuaät toaùn ñeä quy cuõng thöôøng ñöôïc ñeà caäp tôùi laø baøi toaùn "Thaùp Haø Noäi". Chuùng ta coù theå tham khaûo veà baøi toaùn naày trong [5] trang 227. IV. Moät soá thuaät toaùn soá hoïc Trong phaàn naày chuùng ta seõ giôùi thieäu moät soá thuaät toaùn ñôn giaûn veà soá hoïc. Vieäc giôùi thieäu naày nhaèm giuùp cho hoïc vieân cuõng coá theâm nhöõng kieán thöùc veà thuaät toaùn ñaõ ñöôïc trình baøy ôû caùc phaàn treân vaø cuõng laø nhöõng chaát lieäu caàn thieát veà toaùn laøm nhöõng baøi taäp cô baûn cho vieäc hoïc laäp trình. -141-
- Thuaät toaùn kieåm tra soá nguyeân toá. Vaán ñeà ñaët ra laø : cho moät soá nguyeân döông p. Laøm theá naøo ñeå bieát ñöôïc p coù phaûi laø soá nguyeân toá hay khoâng? Caùch ñôn giaûn nhaát ñeå bieát p coù nguyeân toá hay khoâng laø döïa vaøo ñònh nghóa cuûa soá nguyeân toá. Tröôùc heát ta xem xeùt ñieàu kieän p 1. Neáu p = 1 thì p khoâng nguyeân toá. Neáu ñuùng laø p 1 thì tieáp tuïc kieåm tra xem trong caùc soá töø 2 ñeán p-1 coù öôùc soá cuûa p hay khoâng? Neáu coù thì p khoâng nguyeân toá; ngöôïc laïi thì p nguyeân toá. Thuaät toaùn kieåm tra soá nguyeân toá theo caùch naày coù theå ñöôïc vieát nhö sau: Thuaät toaùn 1: Kieåm tra tính nguyeân toá cuûa moät soá nguyeân döông Nhaäp: p nguyeân döông Xuaát : keát luaän veà tính nguyeân toá cuûa p. Thuaät toaùn : 1. if p = 1 then begin keát luaän : p khoâng nguyeân toá; Döøng thuaät toaùn; end 2. flag := TRUE (gaùn cho côø hieäu “flag” giaù trò RUE) 3. for k := 2 to p-1 do if (k laø öôùc soá cuûa p) then begin flag := FALSE; break; (ngaét voøng laëp for) end -142-
4. if flag = TRUE then keát luaän: p laø soá nguyeân toá else keát luaän: p khoâng laø soá nguyeân toá Nhôø vaøo meänh ñeà döôùi ñaây, thuaät toaùn treân coøn coù theå ñöôïc caûi tieán ñeå giaûm bôùt thao taùc trong quaù trình thöïc hieän thuaät toaùn. Khoâng laøm maát tính toång quaùt, ta chæ caàn vieát thuaät toaùn kieåm tra tính nguyeân toá cuûa moät soá nguyeân döông n trong tröôøng hôïp n > 1. Meänh ñeà. Neáu soá nguyeân n > 1 khoâng phaûi laø moät soá nguyeân toá thì n coù moät öôùc soá nguyeân toá (döông) n . Thuaät toaùn 2. Thuaät toaùn kieåm tra soá nguyeân toá Nhaäp: n nguyeân döông Ñieàu kieän : n > 1 Xuaát : keát luaän veà tính nguyeân toá cuûa n. Thuaät toaùn : 1. p := 2 (p seõ ñöôïc kieåm tra xem coù phaûi laø moät öôùc soá cuûa n hay khoâng) 2. flag := TRUE 3. while p n and flag do if (p laø öôùc soá cuûa n) then flag := FALSE else p := p+1 4. if flag = TRUE then keát luaän: p laø soá nguyeân toá else keát luaän: p khoâng laø soá nguyeân toá -143-
- Thuaät toaùn tính öôùc soá chung lôùn nhaát cuûa 2 soá nguyeân. Trong muïc naày chuùng ta phaùt bieåu moät soá tính chaát lieân quan ñeán öôùc soá chung lôùn nhaát cuûa hai soá nguyeân. Töø ñoù ruùt ra moät thuaät toaùn ñeå tìm öôùc soá chung lôùn nhaát cuûa hai soá nguyeân. Meänh ñeà. (1) Neáu a laø moät öôùc soá cuûa b thì (a,b) = a. (2) (a,b) = (a, a b). (3) Giaû söû a laø moät soá nguyeân tuøy yù, b laø moät soá nguyeân khaùc 0. Goïi r laø soá dö khi chia a cho b. Khi ñoù ta coù : (a,b) = (b, r). Töùc laø öôùc soá chung lôùn nhaát cuûa a vaø b baèng öôùc soá chung lôùn nhaát cuûa b vaø r. Töø caùc tính chaát treân ta coù moät caùch ñeå tìm öôùc soá chung lôùn nhaát cuûa hai soá nguyeân a vaø b (khoâng ñoàng thôøi baèng 0) nhö sau: Thuaät toaùn 3. Tìm öôùc soá chung lôùn nhaát cuûa hai soá nguyeân. Nhaäp : m, n laø 2 soá nguyeân. Ñieàu kieän : m vaø n khoâng ñoàng thôøi baèng 0. Xuaát : d laø öôùc soá chung lôùn nhaát cuûa m vaø n. Thuaät toaùn : 1. if n = 0 then begin d := m; Döøng thuaät toaùn end 2. a := m; b := n 3. r := a mod b (gaùn cho r dö soá trong pheùp chia a cho b) 4. while r 0 do -144-
begin a := b (gaùn cho a giaù trò cuûa b) b := r (gaùn cho b giaù trò cuûa r) r := a mod b (gaùn cho r dö soá trong pheùp chia a cho b) end 5. d := b V. Söï phaân lôùp vaán ñeà - baøi toaùn Ñoä phöùc taïp cuûa thuaät toaùn chính laø yeáu toá cô sôû ñeå phaân loaïi vaán ñeà - baøi toaùn. Moät caùch toång quaùt, ngöôøi ta phaân chia caùc baøi toaùn thaønh 2 lôùp: lôùp caùc baøi toaùn giaûi ñöôïc vaø lôùp caùc baøi toaùn khoâng giaûi ñöôïc. Lôùp giaûi ñöôïc chia laøm 2 lôùp con: lôùp caùc baøi toaùn coù ñoä phöùc taïp ña thöùc vaø lôùp caùc baøi toaùn coù ñoä phöùc taïp khoâng phaûi laø ña thöùc. Ngoaøi ra ta coøn coù nhöõng baøi toaùn thuoäc loaïi NP, ñoù laø nhöõng baøi toaùn chöa theå phaân loaïi moät caùch chính xaùc laø thuoäc lôùp coù ñoä phöùc taïp ña thöùc hay coù ñoä phöùc taïp khoâng ña thöùc. 5.1 Lôùp baøi toaùn coù ñoä phöùc taïp ña thöùc Caùc baøi toaùn thuoäc lôùp naày coù ñoä phöùc taïp thuoäc loaïi O(nk). Caùc baøi toaùn coù ñoä phöùc taïp thuoäc loaïi O(n log n) cuõng laø caùc baøi toaùn coù ñoä phöùc taïp ña thöùc vì lôùp O(n log n) bao haøm trong lôùp O(n2). Töông töï, caùc baøi toaùn coù ñoä phöùc taïp haèng O(1), coù ñoä phöùc taïp tuyeán tính O(n) cuõng thuoäc lôùp caùc baøi toaùn coù ñoä phöùc taïp ña thöùc. Caùc baøi toaùn coù ñoä phöùc taïp tæ leä vôùi haøm muõ theo n hay tæ leä vôùi n! thì khoâng thuoäc lôùp baøi toaùn coù ñoä phöùc taïp ña thöùc. -145-
Ñoä phöùc taïp tính toaùn cuûa thuaät toaùn cho chuùng ta moät söï ñaùnh giaù töông ñoái veà thôøi gian thöïc hieän cuûa thuaät toaùn. Caùc baøi toaùn thuoäc lôùp ña thöùc, töùc laø coù ñoä phöùc taïp ña thöùc, ñöôïc xem laø caùc baøi toaùn coù lôøi giaûi thöïc teá. Lôøi giaûi thöïc teá ñöôïc hieåu laø chi phí veà maët thôøi gian vaø khoâng gian cho vieäc giaûi baøi toaùn laø chaáp nhaän ñöôïc trong ñieàu kieän hieän taïi. Chuùng ta ñaõ thaáy baøi toaùn saép xeáp daõy, baøi toaùn tìm kieám treân daõy ñeàu coù ñoä phöùc taïp ña thöùc. Baát kyø baøi toaùn naøo khoâng thuoäc lôùp caùc baøi toaùn coù ñoä phöùc taïp ña thöùc ñeàu coù chi phí lôùn. Vì vaäy ñoái vôùi baát kyø baøi toaùn naøo, ngöôøi ta cuõng mong muoán tìm ra nhöõng thuaät toaùn giaûi quyeát noù moät caùch hieäu quaû coù ñoä phöùc taïp ña thöùc. Tuy nhieân ñieàu naày khoâng phaûi luùc naøo cuõng laøm ñöôïc vaø coù nhöõng tröôøng hôïp khoâng theå laø ñöôïc. Ñoù laø tröôøng hôïp baøi toaùn coù ñoä phöùc taïp khoâng ña thöùc. 5.2 Lôùp baøi toaùn coù ñoä phöùc taïp khoâng ña thöùc Nhö ñaõ ñeà caäp trong muïc treân, ngöôøi ta luoân mong muoán tìm ra thuaät toaùn coù ñoä phöùc taïp ña thöùc ñeå giaûi caùc baøi toaùn. Nhöng coù nhieàu baøi toaùn khoâng theå coù thuaät toaùn thuoäc lôùp ñoä phöùc taïp ña thöùc ñeå giaûi noù, maëc duø noù coù lôøi giaûi. Baøi toaùn lieät keâ taát caû caùc taäp hôïp con cuûa moät taäp hôïp X höõu haïn coù n phaàn töû laø moät ví duï cho loaïi baøi toaùn giaûi ñöôïc nhöng coù ñoä phöùc taïp khoâng ña thöùc. Veà maët toaùn hoïc, ta coù theå chöùng minh ñöôïc raèng taäp hôïp X (coù n phaàn töû) seõ coù taát caû laø 2n taäp hôïp con. Nhö vaäy, baát kyø thuaät toaùn naøo ñeå lieät keâ taát caû caùc taäp hôïp con cuûa X ñeàu phaûi thöïc hieän ít nhaát 2n böôùc. Ngoaøi ra ta coù theå neâu leân moät thuaät toaùn lieät keâ caùc taäp hôïp con cuûa X vôùi ñoä phöùc taïp thuoäc loaïi O(2n). Ñieàu naày ñaõ chöùng toû raèng baøi toaùn khoâng thuoäc lôùp ña thöùc. Vôùi n chæ côû 32 thì soá böôùc thao taùc ñeå giaûi baøi toaùn ñaõ treân 4 tyû, vaø vôùi n = 33 thì soá thao taùc cuûa thuaät toaùn seõ hôn 8 tyû! Vôùi -146-
soá löôïng thao taùc nhö vaäy, ngay caû ñoái vôùi moät sieâu maùy tính thì cuõng phaûi toán moät thôøi gian ñaùng keå. Moät ví duï khaùc veà baøi toaùn khoâng thuoäc lôùp caùc baøi toaùn coù ñoä phöùc taïp ña thöùc laø baøi toaùn Thaùp Haø noäi vì soá laàn chuyeån ñóa cho baøi toaùn vôùi n ñóa ít nhaát laø 2n-1. 5.3 Lôùp baøi toaùn NP Nhö ñaõ trình baøy trong phaàn treân, ñoái vôùi caùc baøi toaùn ngöôøi ta mong muoán tìm ra moät thuaät toaùn coù ñoä phöùc taïp ña thöùc ñeå giaûi nhöng raát khoâng may laø coù nhöõng baøi toaùn coù ñoä phöùc taïp khoâng ña thöùc, töùc laø khoâng toàn taïi thuaät toaùn coù ñoä phöùc taïp ña thöùc ñeå giaûi baøi toaùn. Chaúng haïn nhö baøi toaùn lieät keâ caùc taäp hôïp con cuûa moät taäp hôïp, baøi toaùn Thaùp Haø Noäi. Ngoaøi ra, ta coøn coù theå gaëp phaûi nhöõng baøi toaùn maø ta coù thuaät toaùn vôùi ñoä phöùc taïp khoâng ña thöùc ñeå giaûi noù nhöng laïi chöa tìm ra ñöôïc thuaät toaùn ña thöùc ñeå giaûi baøi toaùn vaø cuõng chöa chöùng minh ñöôïc raèng khoâng theå coù moät thuaät toaùn ña thöùc ñeå giaûi baøi toaùn. Noùi moät caùch khaùc, ta chöa phaân loaïi ñöôïc baøi toaùn laø loaïi coù ñoä phöùc taïp ña thöùc hay coù ñoä phöùc taïp khoâng ña thöùc. Ta goïi nhöõng baøi toaùn naày laø nhöõng baøi toaùn NP. Ví duï: Baøi toaùn ngöôøi baùn haøng. Moät nhaân vieân phaân phoái haøng cho moät coâng ty ñöôïc giao nhieäm vuï phaûi giao haøng cho caùc ñaïi lyù cuûa coâng ty, sau ñoù trôû veà coâng ty. Vaán ñeà cuûa ngöôøi nhaân vieân laø laøm sao ñi giao haøng cho taát caû caùc ñaïi lyù vôùi chi phí ñöôøng ñi thaáp nhaát. ÔÛ ñaây ta xem chi -147-
phí ñöôøng ñi laø ñoä daøi ñöôøng ñi maø ngöôøi nhaân vieân ñaõ ñi ñeå giao haøng vaø trôû veà nôi xuaát phaùt (coâng ty). Moät caùch giaûi coå ñieån cho baøi toaùn ngöôøi baøn haøng laø lieät keâ taát caû caùc caùch ñi coù theå coù vaø so saùnh ñoä daøi cuûa ñöôøng ñi cuûa chuùng ñeå tìm ra caùch ñi coù ñoä daøi ñöôøng ñi ngaén nhaát. Theo caùch naày thì khi soá ñaïi lyù nhieàu thì phaûi toán raát nhieàu thôøi gian cho vieäc lieät keâ, tính toaùn vaø so saùnh. Ñeå giaûm thieåu thôøi gian tính toaùn ta coù theå giaûm nheï yeâu caàu baøi toaùn baèng caùch tìm ra moät caùch ñi vôùi ñoä daøi ñöôøng ñi chaáp nhaän ñöôïc (theo nghóa laø ñoä daøi ñöôøng ñi nhoû hôn hoaëc baèng moät soá ño cho tröôùc). Vôùi yeâu caàu giaûm nheï naày thì ta co theå thöïc hieän moät söï lieät keâ coù heä thoáng hôn theo moät kieåu naøo ñoù ñeå hy voïng raèng khoâng phaûi xeùt taát caû caùc tröôøng hôïp maø chæ ñeán moät böôùc naøo ñoù trong quaù trình lieät keâ laø ta ñaõ tìm thaáy moät caùch ñi giao haøng vôùi ñöôøng ñi chaáp nhaän ñöôïc. Tuy nhieân caùch giaûi quyeát naày vaãn coù ñoä phöùc taïp khoâng phaûi ña thöùc. Ngöôøi ta ñaõ chöùng minh ñöôïc raèng ñoä phöùc taïp cuûa thuaät toaùn naày laø O(n!). Nhö vaäy neáu soá löôïng ñaïi lyù laø lôùn thì thuaät toaùn treân laø khoâng thöïc teá. Cho ñeán nay ngöôøi ta chöa chöùng minh ñöôïc raèng toàn taïi hay khoâng toàn taïi moät thuaät toaùn coù ñoä phöùc taïp ña thöùc ñeå giaûi baøi toaùn ngöôøi baùn haøng. Nhö theá baøi toaùn naày chöù theå xeáp vaøo loaïi baøi toaùn coù ñoä phöùc taïp ña thöùc hay khoâng ña thöùc, vaø do ñoù ñaây laø baøi toaùn NP. Löu yù raèng ta coù theå giaûi baøi toaùn naày baèng caùch söû duïng thuaät giaûi heuristic. Khaùi nieäm thuaät giaûi heuristic ñöôïc ñeà caäp ñeán trong phaàn keá tieáp, ñaây laø moät söï môû roäng khaùi nieäm thuaät toaùn ñeå ta coù theå giaûi quyeát ñöôïc caùc baøi toaùn phöùc taïp vôùi moät chi phí thoûa ñaùng vaø thöôøng cho ta lôøi giaûi hay keát quaû chaáp nhaän ñöôïc. -148-
VI. Thuaät giaûi 6.1 Môû roäng khaùi nieäm thuaät toaùn: thuaät giaûi Nhö chuùng ta ñaõ bieát, caùch giaûi ñeä quy khoâng ñaùp öùng ñaày ñuû caùc yeâu caàu ñoái vôùi moät thuaät toaùn. Ñoù laø moät söï môû roäng khaùi nieäm thuaät toaùn. Trong quaù trình nghieân cöùu giaûi quyeát caùc baøi toaùn, caùc vaán ñeà ñaët ra ngöôøi ta nhaän thaáy coù nhöõng tình huoáng nhö sau: - Coù nhöõng baøi toaùn cho ñeán nay vaãn chöa coù moät caùch giaûi theo kieåu thuaät toaùn ñöôïc tìm ra vaø cuõng khoâng bieát coù toàn taïi thuaät toaùn hay khoâng. - Coù nhöõng baøi toaùn ñaõ coù thuaät toaùn ñeå giaûi nhöng khoâng chaáp nhaän ñöôïc vì thôøi gian giaûi theo thuaät toaùn ñoù quaù daøi hoaëc caùc ñieàu kieän cho thuaät toaùn khoù ñaùp öùng. - Coù nhöõng baøi toaùn ñöôïc giaûi theo nhöõng caùch giaûi vi phaïm thuaät toaùn nhöng vaãn ñöôïc chaáp nhaän. Töø nhöõng nhaän ñònh treân, ngöôøi ta thaáy raèng caàn phaûi coù nhöõng ñoåi môùi cho khaùi nieäm thuaät toaùn. Moät soá tieâu chuaån cuûa thuaät toaùn ñöôïc môû roäng: tính xaùc ñònh, tính ñuùng ñaén. Vieäc môû roäng tính xaùc ñònh ñoái vôùi thuaät toaùn ñöôïc theå hieän roõ qua caùc thuaät toaùn ñeä quy vaø caùc thuaät giaûi ngaãu nhieân. Tính ñuùng cuûa thuaät toaùn baây giôø khoâng coøn baét buoäc ñoái vôùi moät soá caùch giaûi cho caùc baøi toaùn, nhaát laø caùc caùch giaûi gaàn ñuùng. Trong thöïc tieãn coù nhieàu tröôøng hôïp ngöôøi ta chaáp nhaän caùc caùch giaûi chæ cho keát quaû gaàn ñuùng nhöng ít phöùc taïp vaø hieäu quaû. Moät trong nhöõng môû roäng ñoái vôùi thuaät toaùn thöôøng ñöôïc ñeà caäp ñeán vaø söû duïng trong khoa hoïc trí tueä nhaân taïo laø caùc caùch giaûi theo -149-
kieåu heuristic. Chuùng thöôøng khaù ñôn giaûn, töï nhieân nhöng cho keát quaû ñuùng hoaëc gaàn ñuùng trong phaïm vi cho pheùp. Caùc caùch giaûi chaáp nhaän ñöôïc nhöng khoâng hoaøn toaøn ñaùp öùng ñaày ñuû caùc tieâu chuaån cuûa thuaät toaùn thöôøng ñöôïc goïi laø caùc thuaät giaûi. Khaùi nieäm môû roäng naày cuûa thuaät toaùn ñaõ môû roäng cöûa cho chuùng ta trong vieäc tìm kieám phöông phaùp ñeå giaûi quyeát caùc baøi toaùn ñöôïc ñaët ra treân maùy tính. 6.2 Thuaät giaûi heuristic - Thuaät giaûi heuristic laø moät söï môû roäng khaùi nieäm thuaät toaùn. Noù theå hieän moät caùch giaûi baøi toaùn vôùi caùc ñaëc tính nhö sau: Thuaät giaûi thöôøng tìm ñöôïc lôøi giaûi toát (nhöng khoâng chaéc laø lôøi giaûi toát nhaát). Thöïc hieän caùch giaûi theo thuaät giaûi heuristic thöôøng deã daøng vaø nhanh choùng hôn so vôùi giaûi thuaät toái öu. Thuaät giaûi heuristic thöôøng theå hieän moät caùch haønh ñoäng khaù töï nhieân, gaàn guõi vôùi caùch suy nghó vaø caùch haønh ñoäng cuûa con ngöôøi. - Coù nhieàu caùch tieáp caän cho vieäc thieát keá moät thuaät giaûi heuristic. Trong ñoù ta coù theå döïa vaøo moät soá nguyeân lyù cô sôû sau ñaây: Nguyeân lyù veùt caïn thoâng minh: Trong moät baøi toaùn tìm kieám naøo ñoù, khi khoâng gian tìm kieám lôùn ta thöôøng tìm caùch ñeå giôùi haïn laïi khoâng gian tìm kieám hoaëc thöïc hieän moät kieåu doø tìm ñaëc bieät döïa vaøo ñaëc thuø cuûa baøi toaùn ñeå nhanh choùng tìm ra muïc tieâu. -150-
Nguyeân lyù tham lam: Laáy tieâu chuaån toái öu (treân phaïm vi toaøn boä) cuûa baøi toaùn ñeå laøm tieâu chuaån choïn löïa haønh ñoäng cho phaïm vi cuïc boä cuûa töøng böôùc (hay töøng giai ñoaïn) trong quaù trình tìm kieám lôøi giaûi. Nguyeân lyù thöù töï: thöïc hieän haønh ñoäng döïa treân moät caáu truùc thöù töï hôïp lyù cuûa khoâng gian khaûo saùt nhaèm nhanh choùng ñaït ñöôïc moät lôøi giaûi toát. Ngoaøi ra, trong vieäc thieát keá thuaät giaûi heuristic ngöôøi ta cuõng thöôøng ñöa ra caùc haøm heuristic. Ñoù laø caùc haøm maø giaù trò cuûa noù phuï thuoäc vaøo caùc traïng thaùi hay caùc tình huoáng trong quaù trình thöïc hieän thuaät giaûi. Nhôø vieäc so saùnh giaù trò haøm heuristic ta coù theå choïn ñöôïc caùch haønh ñoäng töông ñoái hôïp lyù trong töøng böôùc cuûa thuaät giaûi. Döôùi ñaây chuùng ta seõ xeùt 2 ví duï cuï theå minh hoïa cho caùc thuaät giaûi heuristic. Trong ví duï 1 ta ñöa ra moät caùch giaûi theo nguyeân lyù tham lam cho baøi toaùn haønh trình ngöôøi baùn haøng. Ví duï 2 laø baøi toaùn phaân coâng vieäc ñôn giaûn ñöôïc giaûi baèng moät caùch döïa treân nguyeân lyù thöù töï. Taát nhieân caùc caùch giaûi neâu trong caùc ví duï khoâng luoân luoân cho ta lôøi giaûi toát nhaát vaø caùc thuaät giaûi coù theå ñöôïc caûi tieán cho toát hôn. Ví duï 1: Treân moät ñoà thò (lieân thoâng) ñôn giaûn goàm n ñænh, moãi cung noái 2 ñænh coù moät giaù trò chi phí. Haõy xaây döïng moät lòch trình baét ñaàu töø moät ñænh xuaát phaùt A, ñi qua taát caû caùc ñænh treân ñoà thò vaø trôû veà nôi xuaát phaùt sao cho chi phí laø thaáp nhaát. Ta coù theå tieán haønh tìm lòch trình theo moät caùch raát ñôn giaûn nhö sau: -151-
Böôùc 1: Khôûi ñaàu. - Ñaët lòch trình TOUR laø roãng. - Ñaët chi phí COST laø 0. - Ñaët vò trí hieän taïi S laø A. Böôùc 2: Ñi qua caùc ñænh. for k := 1 to n-1 do begin - Choïn ñænh X chöa tôùi sao cho c(S,X) nhoû nhaát. ÔÛ ñaây c(S,X) laø chi phí cung (S,X). - Ñaët TOUR := TOUR + (S,X). - Ñaët COST := COST + c(S,X). - Ñaët S := X. end Buôùc 3: Trôû veà nôi xuaát phaùt vaø hoaøn thaønh chuyeán ñi. - Ñaët TOUR := TOUR + (S,A). - Ñaët COST := COST + c(S,A). Aùp duïng thuaät giaûi treân cho ñoà thò: -152-
chuùng ta tìm ñöôïc lòch trình A B C E D A vôùi chi phí laø 10. Ví duï 2: Baøi toaùn phaân vieäc: Giaû söû coù m maùy nhö nhau ñöôïc kyù hieäu bôûi P1,P2, ,Pm. Coù n coâng vieäc J1,J2, , Jn caàn ñöôïc thöïc hieän. Caùc coâng vieäc coù theå ñöôïc hieän ñoàng thôøi vaø baát kyø coâng vieäc naøo cuõng coù theå chaïy treân moät maùy naøo ñoù. Moãi laàn maùy ñöôïc cho thöïc hieän moät coâng vieäc noù seõ laøm cho tôùi khi hoaøn thaønh. Coâng vieäc Ji coù thôøi gian thöïc hieän treân moät maùy laø ti (i=1, ,n). Muïc ñích cuûa chuùng ta laø toå chöùc phaân coâng caùc coâng vieäc cho caùc maùy sao cho toaøn boä caùc coâng vieäc ñöôïc hoaøn thaønh trong thôøi gian ngaén nhaát. Kinh nghieäm cho thaáy moät trong nhöõng caùch raát ñôn giaûn (nhöng laïi thöôøng cho ta moät phöông aùn toát) ñeå xaây döïng moät baûng phaân coâng nhö sau: Böôùc 1: Choïn moät coâng vieäc J chöa ñöôïc phaân coâng vaø coù thôøi gain thöïc hieän lôùn nhaát. Böôùc 2: Choïn moät maùy P coù thôøi gian thöïc hieän caùc coâng vieäc (ñaõ phaân coâng cho maùy) laø thaáp nhaát. Böôùc 3: Phaân vieäc J cho maùy P. Böôùc 4: Quay laïi Böôùc 1 neáu coøn coâng vieäc chöa ñöôïc choïn ñeå phaân coâng. Ñoái vôùi maãu baøi toaùn cuï theå coù: m = 3, n = 8, t1 = 2, t2 = 5, t3 = 8, t4 = 6, t5 = 1, t6 = 4, t7 = 2, t8 = 1, -153-
thuaät giaûi treân seõ cho baûng phaân coâng caùc coâng vieäc cho caùc maùy nhö sau: Maùy P1: J3(8) J7(2) thôøi gian laøm vieäc = 10. Maùy P2: J4(6) J1(2) J5(1) thôøi gian laøm vieäc = 9. Maùy P3: J2(5) J6(4) J8(1) thôøi gian laøm vieäc = 10. BAØI TAÄP Caâu 1: Thuaät toaùn laø gì? Neâu leân caùc tính chaát cô baûn cuûa thuaät toaùn. Caâu 2: Cho moät ví duï veà caùch bieåu dieãn thuaät toaùn döôùi daïng maõ giaû. Caâu 3: Cho caùc ví duï veà caùc thuaät toaùn coù ñoä phöùc taïp O(n) vaø O(n2). Caâu 3: Moät thuaät toaùn ñôn giaûn ñeå tính öôùc soá chung lôùn nhaát (USCLN)cuûa hai soá töï nhieân a vaø b coù theå ñöôïc trình baøy theo ngoân ngöõ töï nhieân nhö sau: Ta thöïc hieän laëp ñi laëp laïi thao taùc tröø soá lôùn (hôn hoaëc baèng) cho soá nhoû trong hai soá a, b cho tôùi khi moät trong hai soá baèng 0; khi aáy soá kia chính laø USCLN. Haõy vieát thuaät toaùn tính USCLN naày döôùi daïng maõ giaû. Caâu 4: Vieát thuaät toaùn kieåm tra moät soá nguyeân coù phaûi laø soá nguyeân toá hay khoâng. -154-
Caâu 5: (a) Vieát thuaät toaùn tính toång S cuûa moät daõy soá a1, a2, . . ., an. (b) Cho moät daõy soá a1, a2, . . ., an, vaø moät phaàn töû x. Haõy vieát thuaät toaùn ñeám soá laàn xuaát hieän cuûa x trong daõy soá ñaõ cho. (c) Thuaät toaùn tìm ra daõy goàm caùc phaàn töû khaùc nhau töøng ñoâi moät trong moät daõy (höõu haïn) caùc soá nguyeân cho tröôùc. Caâu 6: Vieát thuaät toaùn keâ ra caùc giaù trò khaùc nhau cuûa moät daõy soá cho tröôùc, öùng vôùi moãi giaù trò cuõng cho bieát soá laàn xuaát hieän cuûa giaù trò ñoù trong daõy. Ví duï: neáu daõy soá cho tröôùc laø daõy sau ñaây: 2 4 5 7 8 9 2 2 5 5 7 9 4 9 9 9, thì caùc giaù trò khaùc nhau trong daõy vaø soá laàn xuaát hieän cuûa giaù trò töông öùng trong daõy ñöôïc keâ ra nhö sau: Gíaù trò soá laàn xuaát hieän 2 3 4 2 5 3 7 2 8 1 9 5 Caâu 7: Cho n vaø p laø caùc soá nguyeân döông, Vieát thuaät toaùn tìm soá nguyeân k lôùn nhaát thoûa maõn ñieàu kieän sau ñaây: pk < n Caâu 8: Moät thuaät toaùn khaù toát duøng ñeå tính toaùn giaù trò cuûa ña thöùc: n n-1 an.x + an-1.x + . . . + a1.x + a0 taïi x = c ñöôïc trình baøy döôùi daïng maõ giaû nhö sau -155-
power := 1 y := a0 for i:= 1 to n do begin power := power * c y := y + ai*power end; n n-1 y = an.c + an-1.c + . . . + a1.c + a0 trong thuaät toaùn treân, giaù trò cuoái cuøng cuûa y laø giaù trò cuûa ña thöùc taïi x=c. a/ Haõy tính toaùn giaù trò cuûa ña thöùc 3x2 + 2x + 1 taïi x=2 baèng caùch thöïc hieän theo töøng böôùc trong thuaät toaùn treân. b/ Haõy tính xem trong thuaät toaùn tính giaù trò cuûa moät ña thöùc baäc n taïi x=c nhö treân coù bao nhieâu pheùp nhaân vaø pheùp coäng ñöôïc söû duïng. Caâu 9: Moät thuaät toaùn khaùc raát toát ñeå tính giaù trò cuûa moät ña thöùc, thuaät toaùn naày ñöôïc goïi laø phöông phaùp Horner. Thuaät toaùn theo n n-1 phöông phaùp Horner ñeå tính giaù trò cuûa ña thöùc an.x + an-1.x + . . . + a1.x + a0 taïi x = c ñöôïc vieát nhö sau: 1. y := an 2. for i := 1 to n do y := y * c + an-i n n-1 y = an.c + an-1.c + . . . + a1.c + a0  a/ Haõy tính toaùn giaù trò cuûa ña thöùc 3x3 + 2x + 1 taïi x=2 baèng caùch thöïc hieän theo töøng böôùc trong thuaät toaùn treân. -156-
b/ Haõy tính xem trong thuaät toaùn tính giaù trò cuûa moät ña thöùc baäc n taïi x=c nhö treân coù bao nhieâu pheùp nhaân vaø pheùp coäng ñöôïc söû duïng. Caâu 10: Baøi toaùn “8-haäu”: treân moät baøn côø goàm 64 oâ (8 doøng vaø 8 coät), ta tìm caùch ñaët 8 quaân haäu sao cho khoâng coù quaân haäu naøo naèm trong phaïm vi taán coâng cuûa quaân haäu khaùc. (a) Haõy vieát thuaät giaûi tìm moät phöông aùn ñaët 8 haäu treân baøn côø. (b) Haõy vieát thuaät giaûi tìm taát caû caùc phöông aùn ñaët 8 haäu treân baøn côø. Caâu 11: Theá naøo laø thuaät toaùn ñeä quy? Cho ví duï. Caâu 12: Caáu truùc cuûa thuaät toaùn ñeä quy. Caâu 13: (a) Haõy dieãn giaûi quaù trình tính n! cho tröôøng hôïp n = 4 theo thuaät toaùn ñeä quy. (b) Haõy dieãn giaûi quaù trình tính F(n), soá haïng thöù n cuûa daõy soá Fibonacci, cho tröôøng hôïp n = 4 theo thuaät toaùn ñeä quy. Caâu 14: Vieát thuaät toaùn tìm kieám nhò phaân döôùi daïng ñeä quy. Caâu 15: Vieát moät thuaät toaùn ñeä quy ñeå tìm gia trò lôùn nhaát cuûa moät daõy soá (goàm höõu haïn phaàn töû). Caâu 16: Vieát thuaät toaùn lieät keâ taát caû caùc taäp hôïp con cuûa moät taäp höõu haïn (coù n phaàn töû) theo phöông phaùp ñeä quy. -157-
Caâu 17: Vieát thuaät toaùn lieät keâ taát caû caùc hoaùn vò cuûa moät taäp hôïp höõu haïn. Caâu 18: Cho 2 daõy soá ann 0 vaø bnn 0 ñöôïc ñònh nghóa nhö sau: a0 = 0, b0 = 1, an = 2an-1 - bn-1 + 2 vôùi n > 0, vaø bn = - an-1 + 2bn-1 - 1 vôùi n > 0. Vieát thuaät toaùn tính soá haïng an vaø thuaät toaùn tính soá haïng bn. Caâu 20: Trình baøy khaùi nieäm thuaät giaûi heuristic vaø cho moät ví duï. Caâu 21: Baøi toaùn “Maõ ñi tuaàn”: treân moät baøn coà goàm 64 oâ (8 doøng vaø 8 coät) coù moät quaân maõ ñang ôû moät moät oâ naøo ñoù ñöôïc xem laø vò trí xuaát phaùt. Chuùng ta muoán tìm ra moät phöông aùn ñi cho quaân maõ sao cho noù ñi qua heát taát caû caùc oâ treân baøn côø. Haõy vieát moät thuaät giaûi tìm ra nöôùc ñi cho quaân maõ. Caâu 22: Cho moät daõy soá a1, a2, . . ., an. Vieát moät thuaät giaûi phaân daõy soá thaønh 2 daõy con sao cho söï sai bieät giöõa caùc toång soá cuûa 2 daõy con laø nhoû nhaát. -158-
CHÖÔNG 5. QUAN HEÄ I. QUAN HEÄ 2 NGOÂI 1.1 Ñònh nghóa vaø ví duï - Giöõa caùc phaàn töû trong moät taäp hôïp naøo ñoù maø chuùng ta ñang quan taâm thöôøng coù nhöõng moái lieân heä hay nhöõng quan heä. Ví duï: quan heä lôùn hôn giöõa caùc soá thöïc, quan heä “anh em” giöõa ngöôøi vôùi ngöôøi, quan heä ñoàng daïng giöõa caùc tam giaùc, v.v Moãi quan heä trong moät taäp hôïp ñöôïc ñaëc tröng baèng moät hay moät soá tieâu chuaån naøo ñoù theå hieän ngöõ nghóa cuûa quan heä. ÔÛ ñaây chuùng ta chæ ñeà caäp ñeán nhöõng quan heä, ñöôïc goïi laø nhöõng quan heä 2 ngoâi, noùi leân söï lieân heä giöõa moãi phaàn töû vôùi caùc phaàn töû khaùc trong taäp hôïp. Khi ta ñang xem xeùt moät quan heä nhö theá, thì vôùi hai phaàn töû x, y tuøy yù trong taäp hôïp chuùng seõ coù : hoaëc laø x coù quan heä vôùi y, hoaëc laø x khoâng coù quan heä vôùi y. Noùi nhö vaäy cuõng coù nghóa laø taäp hôïp caùc caëp (x, y) goàm 2 phaàn töû coù quan heä coù theå xaùc ñònh ñöôïc quan heä ñang xeùt treân taäp hôïp. Veà maët toaùn hoïc, moät quan heä 2 ngoâi ñöôïc ñònh nghóa nhö sau: Ñònh nghóa : Cho moät taäp hôïp X khaùc roãng. Moät quan heä 2 ngoâi treân X laø moät taäp hôïp con R cuûa X2. Cho 2 phaàn töû x vaø y cuûa X, ta noùi x coù quan heä R vôùi y khi vaø chæ khi (x,y) R, vaø vieát laø x R y. Nhö vaäy: x R y (x,y) R Khi x khoâng coù quan heä R vôùi y, ta vieát: x R y. -159-
Ví duï: 1. Treân taäp hôïp X = 1,2,3,4, xeùt quan heä 2 ngoâi R ñöôïc ñònh nghóa bôûi: R = (1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (4,2), (4,4) Vôùi quan heä naày ta coù: 2 R 4, nhöng 2 R 3. 2. Treân taäp hôïp caùc soá nguyeân Z ta ñònh nghóa moät quan heä 2 ngoâi R nhö sau: x R y neáu vaø chæ neáu x-y laø soá chaún. hay noùi caùch khaùc: R = (x,y) Z2  x-y = 2k vôùi k Z  Quan heä R naày chính laø quan heä ñoàng dö modulo 2. 3. Cho n laø moät soá nguyeân döông. Nhaéc laïi raèng quan heä ñoàng dö modulo n treân taäp hôïp caùc soá nguyeân Z, kyù hieäu bôûi  (mod n), ñöôïc ñònh nghóa nhö sau: a  b (mod n)  k Z : (a - b) = k.n Quan heä naày laø moät quan heä 2 ngoâi treân Z. 4. Quan heä treân taäp hôïp caùc soá thöïc R cuõng laø moät quan heä 2 ngoâi. 5. Cho E laø moät taäp hôïp, ñaët X = P(E). Moãi phaàn töû thuoäc X laø moät taäp hôïp con cuûa E. Treân E coù caùc quan heä quen thuoäc sau ñaây: - quan heä bao haøm, kyù hieäu bôûi  - quan heä chöùa, kyù hieäu bôûi  - quan heä baèng nhau, kyù hieäu bôûi = -160-
Ghi chuù : Ngöôøi ta coøn ñònh nghóa moät quan heä (2 ngoâi) giöõa moät taäp hôïp A vaø moät taäp hôïp B laø moät taäp hôïp con cuûa AxB. Ví duï: A = 1, 2, 3, 4, 5, B = 0, 1. Ta coù R = (1,1), (2,0), (3,1), (4,0), (5,0) laø moät quan heä giöõa A vaø B. Toång quaùt hôn, ta coù theå ñònh nghóa moät quan heä giöõa caùc taäp hôïp A1,A2, . . ., An laø moät taäp hôïp con cuûa A1 x A2 x x An (tích Descartes cuûa caùc taäp hôïp A1,A2, . . ., An). Nhö vaäy, khi R laø moät quan heä giöõa caùc taäp A1,A2, . . ., An thì moãi phaàn töû cuûa R laø oät boä n (a1, a2, . . ., an) vôùi ai Ai (i=1, , n). - Caùch xaùc ñònh moät quan heä: Döïa vaøo caùc phöông phaùp xaùc ñònh moät taäp hôïp, ta coù theå xaùc ñònh moät quan heä baèng caùc phöông phaùp sau ñaây: Lieät keâ: lieät keâ taát caû caùc caëp hay boä phaàn töû coù quan heä R (töùc laø thuoäc R). Trong ví duï 1 ôû treân, quan heä R ñöôïc cho theo caùch lieät keâ. Neâu tính chaát ñaëc tröng cho quan heä R, töùc laø tính chaát hay tieâu chuaån ñeå xaùc ñònh caùc phaàn töû thuoäc R hay khoâng. Trong caùc ví duï 2 vaø 3 ôû treân, quan heä R ñöôïc cho baèng caùch neâu leân tính chaát xaùc ñònh quan heä. 1.2 Caùc tính chaát cuûa quan heä 2 ngoâi Moät quan heä 2 ngoâi treân moät taäp hôïp coù theå coù moät soá tính chaát naøo ñoù laøm cho taäp hôïp coù moät caáu truùc nhaát ñònh. Döôùi ñaây laø ñònh nghóa moät soá tính chaát thöôøng ñöôïc xeùt ñoái vôùi moät quan heä 2 ngoâi. -161-
Ñònh nghóa : Giaû söû R laø moät quan heä 2 ngoâi treân moät taäp hôïp X. (a) Ta noùi quan heä R coù tính phaûn xaï (reflexive) neáu vaø chæ neáu x R x vôùi moïi x X. (b) Ta noùi quan heä R coù tính ñoái xöùng (symmetric) neáu vaø chæ neáu x R y y R x vôùi moïi x,y X. (c) Ta noùi quan heä R coù tính phaûn xöùng (antisymmetric) neáu vaø chæ neáu (x R y vaø y R x) x = y vôùi moïi x,y X. (d) Ta noùi quan heä R coù tính truyeàn hay baéc caàu (transitive) neáu vaø chæ neáu (x R y vaø y R z) x R z vôùi moïi x,y,z X. Ví duï: Trong ví duï naày chuùng ta ñeà caäp ñeán moät soá quan heä ñaõ ñöôïc neâu leân trong caùc ví duï cuûa muïc 1.1 ôû treân, vaø phaùt bieåu caùc tính chaát cuûa chuùng. Vieäc kieåm chöùng caùc tính chaát naày khaù deã daøng. 1. Quan heä ñoàng dö modulo n treân Z coù 3 tính chaát: phaûn xaï, ñoái xöùng, truyeàn. 2. Quan heä treân taäp hôïp caùc soá thöïc coù 3 tính chaát: phaûn xaï, phaûn xöùng, truyeàn. 3. Cho E laø moät taäp hôïp. Quan heä  treân P(E) coù 3 tính chaát: phaûn xaï, phaûn xöùng, truyeàn. -162-
1.3 Bieåu dieãn quan heä 2 ngoâi döôùi daïng ma traän Ngoaøi phöông phaùp bieåu dieãn moät quan heä 2 ngoâi döôùi daïng taäp hôïp caùc caëp phaàn töû ngöôøi ta coøn coù theå söû duïng ma traän ñeå bieåu dieãn cho quan heä trong tröôøng hôïp caùc taäp hôïp laø höõu haïn. Khaùi nieäm ma traän seõ ñöôïc ñònh nghóa vaø khaûo saùt chi tieát hôn trong phaàn "Ñaïi soá Tuyeán tính". ÔÛ ñaây chuùng ta chæ caàn hieåu ma traän moät caùch ñôn giaûn laø moät baûng lieät keâ caùc phaàn töû thaønh caùc doøng vaø caùc coät. Ví duï, baûng lieät keâ 6 soá nguyeân thaønh 2 doøng vaø 3 coät sau ñaây laø moät ma traän: 1 1 2 3 0 1 0 0 1 Moät ma traän M goàm m doøng, n coät seõ ñöôïc goïi laø moät ma traän coù caáp mxn. Neáu m = n thì ta noùi M laø moät ma traän vuoâng caáp n. Giaû söû R laø moät quan heä 2 ngoâi giöõa moät taäp hôïp höõu haïn A = a1, a2, , am vaø moät taäp höõu haïn B = b1, b2, , bm. Quan heä R coù theå ñöôïc bieåu dieãn bôûi ma traän MR = [mij] goàm m doøng vaø n coät (töùc laø ma traän caáp mxn), trong ñoù mij = 1 neáu (ai , bj) R mij = 0 neáu (ai , bj) R Ta goïi ma traän MR laø ma traän bieåu dieãn cuûa quan heä R. Ví duï: Vôùi A = 1,2,3 vaø B = a, b, c, thì caùc quan heä sau ñaây: (a) R = (1,a), (1,b), (1,c) (b) S = (1,a), (1,b), (1,c), (2,b), (2,c), (3,c) -163-
coù caùc ma traän bieåu dieãn laø 1 1 1 MR = 0 0 0 0 0 0 1 1 1 MS = 1 1 0 0 0 1 Trong tröôøng hôïp R laø moät quan heä 2 ngoâi treân moät taäp X höõu haïn vaø coù n phaàn töû thì ma traän bieåu dieãn cuûa R laø moät ma traän coù n doøng vaø n coät (töùc laø ma traän vuoâng caáp n). Ghi chuù: Ngoaøi caùch bieåu dieãn quan heä döôùi daïng ma traän ta coøn bieåu ñoà (daïng ñoà thò) ñeå bieåu dieãn quan heä. Caùch bieåu dieãn naày seõ ñöôïc xeùt ñeán trong phaàn sau, khi noùi veà bieåu ñoà Hasse cuûa moät caáu truùc thöù töï. II. QUAN HEÄ TÖÔNG ÑÖÔNG 2.1 Khaùi nieäm - Ñònh nghóa: Moät quan heä 2 ngoâi R treân moät taäp hôïp X ñöôïc goïi laø moät quan heä töông ñöông neáu vaø chæ neáu noù thoûa 3 tính chaát: phaûn xaï, ñoái xöùng, truyeàn. -164-
Ví duï: 1. Moät ví duï quan troïng veà quan heä töông ñöông laø quan heä ñoàng dö modulo n treân Z. Ta ñaõ bieát quan heä naày coù 3 tính chaát phaûn xaï, ñoái xöùng, truyeàn. 2. Quan heä treân Z khoâng phaûi laø moät quan heä töông ñöông vì noù khoâng coù tính chaát ñoái xöùng. 2.2 Lôùp töông ñöông vaø taäp hôïp thöông - Ñònh nghóa: Vôùi moãi phaàn töû x X, ta ñònh nghóa lôùp töông ñöông chöùa x, kyù hieäu x, laø taäp hôïp taát caû nhöõng phaàn töû (thuoäc x) coù quan heä R vôùi x: x = y X : y R x  Nhö vaäy moãi lôùp töông ñöông laø moät taäp hôïp con cuûa X. Ngöôøi ta ñaõ chöùng minh raèng taäp hôïp caùc lôùp töông ñöông cuûa quan heä töông ñöông R treân X taïo thaønh moät “phaân hoaïch” cuûa taäp hôïp X, töùc laø söu taäp caùc lôùp töông ñöông khaùc nhau cho ta moät hoï caùc taäp con cuûa X rôøi nhau ñoâi moät vaø coù phaàn hoäi baèng X. Taäp hôïp caùc lôùp töông ñöông cuûa quan heä töông ñöông R treân Xnaày (laø moät taäp con cuûa P(X)) ñöôïc goïi laø taäp hôïp thöông (cuûa quan heä töông ñöông R treân X). Quan heä ñoàng dö modulo n treân Z coù taäp hôïp thöông töông öùng, ñöôïc kyù hieäu laø Zn, goàm n phaàn töû : Zn = 0, 1, . . ., n - 1 trong ñoù k (k Z) laø taäp hôïp taát caû nhöõng soá nguyeân ñoàng dö vôùi k modulo n. -165-
Ngöôøi ta coøn chöùng minh ñöôïc raèng vieäc xaùc ñònh moät quan heä töông ñöông treân moät taäp hôïp X töông ñöông vôùi vieäc xaùc ñònh moät phaân hoaïch cuûa taäp hôïp X, töùc laø coù moät song aùnh giöõa taäp hôïp taát caû caùc quan heä töông ñöông treân X vaø taäp hôïp taát caû caùc phaân hoaïch cuûa taäp X. III. QUAN HEÄ THÖÙ TÖÏ 3.1 Caùc ñònh nghóa - Ñinh nghóa 1: Moät quan heä 2 ngoâi R treân moät taäp hôïp X (khaùc roãng) ñöôïc goïi laø moät quan heä thöù töï (hay vaén taét, laø moät thöù töï) neáu vaø chæ neáu noù coù 3 tính chaát: phaûn xaï, phaûn xöùng, truyeàn. Khi ñoù ta cuõng noùi taäp hôïp X laø moät taäp coù thöù töï. Neáu coù theâm tính chaát: vôùi moïi x, y X ta coù xRy hay yRx thì ta noùi R laø moät quan heä thöù töï toaøn phaàn treân X. Ghi chuù : Trong tröôøng hôïp treân X coù nhieàu quan heä thöù töï thì khi xeùt ñeán thöù töï treân X ta phaûi noùi roõ thöù töï naøo, vaø ta thöôøng vieát taäp hôïp X coù thöù töï döôùi daïng moät caëp (X,R); trong ñoù R laø quan heä thöù töï ñang xeùt treân X. Vôùi 2 taäp hôïp coù thöù töï X vaø Y ta coù theå ñònh ra moät thöù töï treân tích Descartes XxY döïa vaøo caùc thöù töï treân X vaø treân Y. Töø ñoù ta XxY trôû thaønh moät taäp hôïp thöù töï (xem phaàn baøi taäp). Ví duï: 1. Quan heä treân taäp hôïp caùc soá thöïc R laø moät quan heä thöù töï toaøn phaàn. -166-
2. Cho E laø moät taäp hôïp. Quan heä  treân P(E) laø moät quan heä thöù töï. Neáu E coù nhieàu hôn 2 phaàn töû thì thöù töï naày khoâng phaûi laø thöù töï toaøn phaàn. Vieäc kieåm chöùng ñieàu naày ñöôïc daønh cho ngöôøi ñoïc. 3. Treân taäp hôïp caùc soá nguyeân Z, xeùt qna heä “chia heát” hay “öôùc soá cuûa”, kyù hieäu laø , ñöôïc ñònh nghóa nhö sau: ab  k Z : a = k.b Deã daøng kieåm chöùng raèng quan heä  coù 3 tính chaát: phaûn xaï, phaûn xöùng, truyeàn. Töø ñoù ta coù (Z,) laø moät taäp hôïp coù thöù töï. Ta coù 2 soá nguyeân 2 vaø 3, khoâng coù quan heä vôùi nhau theo quan heä . Do ñoù  khoâng phaûi laø thöù töï toaøn phaàn treân Z. Nhaän xeùt: Neáu (X,R) laø moät taäp hôïp coù thöù töï vaø A  X thì quan heä thöù R thu heïp treân taäp A, cuõng ñöôïc kyù hieäu laø R (neáu khoâng gaây ra nhaàm laãn), laø moät quan heä thöù töï treân A. Noùi moät caùch khaùc, ta coù: (X,R) thöù töï vaø A  X (A,R) thöù töï Ñoái vôùi moät taäp hôïp coù thöù töï thì vieäc ñeà caäp ñeán caùc khaùi nieäm nhö “phaàn töû nhoû nhaát”, “phaàn töû lôùn nhaát”, laø ñieàu raát töï nhieân. Döôùi ñaây, chuùng ta seõ giôùi thieäu moät soá khaùi nieäm quan troïng khi xeùt moät taäp hôïp coù thöù töï. -167-
- Ñònh nghóa 2: Cho (X, ) laø moät taäp hôïp coù thöù töï, vaø A  X. Ta goïi moät phaàn töû a A laø moät phaàn töû nhoû nhaát cuûa taäp hôïp A neáu vaø chæ neáu vôùi moïi x A ta coù : a x. Ta goïi moät phaàn töû a A laø moät phaàn töû lôùn nhaát cuûa taäp hôïp A neáu vaø chæ neáu vôùi moïi x A ta coù : x a. Ta goïi moät phaàn töû a A laø moät phaàn töû toái tieåu cuûa taäp hôïp A neáu vaø chæ neáu khoâng toàn taïi x A sao cho x a vaø x a. Ta goïi moät phaàn töû a A laø moät phaàn töû toái ñaïi cuûa taäp hôïp A neáu vaø chæ neáu khoâng toàn taïi x A sao cho x a vaø a x. Nhaän xeùt: (1) Phaàn töû nhoû nhaát (lôùn nhaát) cuûa moät taäp hôïp, neáu coù, laø duy nhaát.Ta kyù hieäu phaàn töû nhoû nhaát cuûa moät taäp hôïp A laø min A hay min (A), vaø kyù hieäu phaàn töû lôùn nhaát cuûa A laø max A hay max (A). (2) Phaàn töû toái tieåu (toái ñaïi) cuûa moät taäp hôïp coù thöù töï khoâng nhaát thieát laø duy nhaát. Ví duï: xeùt taäp hôïp X = 1,2,3 vôùi quan heä 2 ngoâi ñöôïc cho bôûi = (1,1), (2,2), (3,3), (1,2), (3,2). Chuùng ta coù theå kieåm chöùng raèng (X, ) laø moät taäp hôïp coù thöù töï. Vôùi thöù töï naày, X coù 2 phaàn töû toái tieåu laø 1 vaø 3. (3) Phaàn töû lôùn nhaát (nhoû nhaát) cuûa moät taäp hôïp, neáu coù, laø phaàn töû toái ñaïi (toái tieåu) duy nhaát cuûa taäp hôïp ñoù. Ví duï: 1. Trong taäp hôïp coù thöù töï (Z, ), taäp hôïp A = m Zm2 < 100 coù phaàn töû nhoû nhaát laø -9, vaø phaàn töû lôùn nhaát laø 9. Ta coù theå vieát: min(A) = -9; max(A) = 9. -168-
2. Trong taäp hôïp coù thöù töï (R, ), taäp hôïp A = x Rx2 < 100 khoâng coù phaàn töû nhoû nhaát vaø cuõng khoâng coù phaàn töû lôùn nhaát. 3. Cho E laø moät taäp hôïp. Ta ñaõ bieát (P(E), ) laø moät taäp hôïp coù thöù töï. Vôùi thöù töï naày P(E) coù phaàn töû nhoû nhaát laø , phaàn töû lôùn nhaát laø E. - Ñònh nghóa 3: Cho (X, ) laø moät taäp hôïp coù thöù töï, vaø A  X. Ta goïi moät phaàn töû x X laø moät chaän döôùi cuûa taäp hôïp A neáu vaø chæ neáu vôùi moïi a A ta coù : x a. Chaän döôùi lôùn nhaát (neáu coù), töùc laø phaàn töû lôùn nhaát trong taäp hôïp taát caû nhöõng chaän döôùi cuûa A ñöôïc kyù hieäu laø inf (A). Ta goïi moät phaàn töû x X laø moät chaän treân cuûa taäp hôïp A neáu vaø chæ neáu vôùi moïi a A ta coù : a x. Chaän treân nhoû nhaát (neáu coù), töùc laø phaàn töû nhoû nhaát trong taäp hôïp taát caû nhöõng chaän treân, cuûa A ñöôïc kyù hieäu laø sup (A). Ví du: Trong (R, ), A = x Rx2 < 100. Ta coù sup(A) = 10 vaø inf(A) = -10. Nhaän xeùt : Neáu trong moät taäp hôïp A toàn taïi phaàn töû max(A) thì ñoù cuõng chính laø sup(A). Töông töï, neáu trong moät taäp hôïp A toàn taïi phaàn töû min(A) thì ñoù cuõng chính laø inf(A). - Ñònh nghóa 4: (Thöù töï toát) Moät taäp hôïp coù thöù töï ñöôïc goïi laø coù thöù töï toát (hay ñöôïc saép toát) neáu vaø chæ neáu moïi taäp con khaùc roãng ñeàu coù phaàn töû nhoû nhaát. -169-
Ví du: 1. Taäp hôïp coù thöù töï (N, ) laø moät taäp hôïp ñöôïc saép toát. 2. Taäp hôïp coù thöù töï (Z, ) khoâng phaûi laø moät taäp hôïp ñöôïc saép toát vì Z khoâng coù phaàn töû nhoû nhaát. 3.2 Bieåu ñoà Hasse. Moät trong nhöõng phöông phaùp bieåu dieãn cho moät quan heä laø duøng caùc ñoà thò ñònh höôùng (directed graph). Moät ñoà thò ñònh höôùng goàm moät taäp hôïp caùc ñænh cuøng vôùi moät taäp hôïp caùc caëp ñænh ñöôïc goïi laø caùc caïnh (hay caùc cung). Ñoà thò bieåu dieãn cho moät quan heä 2 ngoâi R treân moät taäp hôïp X coù taäp hôïp caùc ñænh chính laø X, vaø taäp hôïp caùc cung chính laø R. Neáu (a,b) R thì treân bieåu ñoà ta veõ moät cung höôùng töø ñænh a ñeán ñænh b. Ñoà thò ñònh höôùng töông öùng cuûa moät quan heä hai ngoâi treân moät taäp hôïp seõ cung caáp cho ta nhöõng thoâng tin veà quan heä moät caùch raát tröïc quan. Do ñoù ngöôøi ta thöôøng söû duïng caùc ñoà thò ñònh höôùng ñeå nghieân cöùu caùc quan heä vaø caùc tính chaát cuûa chuùng. Ví duï: X = a,b,c,d, R = (a,d), (b,b), (b,d), (c,a), (c,b), (d,b). Ñoà thò ñònh höôùng (X,R) coù theå ñöôïc veõ ra nhö sau: Caïnh (b,b) ñöôïc veõ treân bieåu ñoà bôûi cung xuaát phaùt töø ñænh b vaø quay trôû laïi chính ñænh b. Caïnh naày ñöôïc goïi laø moät “voøng” taïi b. -170-
Chuùng ta coù theå thaáy raèng moät quan heä 2 ngoâi treân moät taäp hôïp laø ñoái xöùng khi vaø chæ khi treân ñoà thò bieåu dieãn töông öùng moãi caëp ñænh ñeàu coù 2 cung noái theo 2 höôùng ngöôïc nhau. Nhö vaäy ñoà thò cuûa quan heä trong ví duï treân ta keát luaän quan heä naày khoâng coù tính ñoái xöùng. Ñoái vôùi moät taäp hôïp X (höõu haïn) coù thöù töï thì treân ñoà thò ñònh höôùng töông öùng coù nhieàu caïnh khoâng nhaát thieát phaûi veõ ra bôûi vì chuùng ñöôïc hieåu ngaàm. Noùi moät caùch khaùc, caùc tính chaát cuûa quan heä thöù töï giuùp ta bieát ñöôïc coù nhöõng caïnh ñöông nhieân coù treân ñoà thò cuûa quan heä; vaø nhöõng caïnh ñoù seõ khoâng ñöôïc veõ ra treân ñoà thò. Tröôùc heát ta thaáy raèng taïi moãi ñænh cuûa ñoà thò phaûi coù moät voøng do tính phaûn xaï cuûa quan heä thöù töï, neân caùc voøng naày seõ khoâng ñöôïc veõ ra treân ñoà thò. Ngoaøi ra quan heä thöù töï coøn coù tính truyeàn, neân ta seõ khoâng caàn veõ ra caïnh (a,c) neáu treân ñoà thò coù caùc caïnh (a,b) vaø (b,c) vôùi b laø moät ñænh naøo ñoù. Hôn nöõa, neáu (a,b), (b,c), vaø (c,d) laø caùc caïnh thì ta cuõng loaïi ra caïnh (a,d). Chuùng ta cuõng khoâng ghi muõi teân ñònh höôùng treân caùc caïnh vôùi qui öôùc raèng : caùc ñænh cuûa ñoà thò ñöôïc boá trí treân hình veõ sao cho höôùng muõi teân cuûa caùc caïnh laø “höôùng leân”. Nhö vaäy ñoà thò ñònh höôùng (daïng bieåu ñoà) töông öùng cuûa taäp hôïp coù thöù töï (X, ) coù theå ñöôïc ruùt goïn laïi thaønh moät bieåu ñoà ñôn giaûn hôn nhöng vaãn haøm chöùa ñaày ñuû nhöõng thoâng tin cuûa thöù töï treân taäp hôïp X, baèng caùch laø ta chæ veõ cung noái töø ñænh x ñeán ñænh x' (x' khaùc x) khi ta coù x x', vaø khoâng toàn taïi y khaùc x vaø x' sao cho x y vaø y x'. Bieåu ñoà ôû daïng ruùt goïn naày ñöôïc goïi laø bieåu ñoà Hasse cuûa taäp hôïp coù thöù töï (X, ). Theo söï trình baøy ôû treân ta coù theå xaây döïng moät thuaät toaùn ñeå tìm bieåu ñoà Hasse cuûa moät taäp hôïp (höõu haïn) coù thöù töï. -171-
Ví duï: 1. Xeùt thöù töï thoâng thöôøng treân taäp hôïp X = 1,2,3,4. Ñoà thò ñaày ñuû cuûa (X, ) coù daïng trong hình (a) döôùi ñaây. Hình (b) laø daïng ruùt goïn cuûa ñoà thò, töùc laø bieåu ñoà Hasse cuûa thöù töï treân X. 2. Veõ bieåu ñoà Hasse bieåu dieãn thöù töï “chia heát”, ñöôïc kyù hieäu laø , treân taäp hôïp 1,2,3,4,6,8,12. Baét ñaàu töø ñoà thò ñònh höôùng cuûa thöù töï naày, ta loaïi boû caùc voøng taïi caùc ñænh. Sau ñoù loaïi boû caùc caïnh coù theå ñöôïc suy ra bôûi tính chaát truyeàn cuûa thöù töï : (1,4), (1,6), (1,8), (1,12), (2,8), (2,12) vaø (3,12). Cuoái cuøng ta ñöôïc bieåu ñoà Hasse goàm caùc caïnh (1,2), (1,3), (2,4), (2,6), (3,6), (4,8), (4,12), vaø (6,12) : -172-
3. Veõ bieåu ñoà Hasse cho thöù töï  treân taäp hôïp P(E), trong ñoù E = a,b,c. Cuõng laøm töông töï nhö trong ví duï tröôùc ta loaïi boû caùc caïnh sau ñaây töø ñoà thò bieåu dieãn cho thöù töï: (, a,b), (, a,c), (, b,c), (, a,b,c), ( a, a,b,c), ( b, a,b,c), vaø ( c, a,b,c). Töø ñoù ta coù bieåu ñoà Hasse ñöôïc veõ nhö sau : -173-
Ghi chuù : Chuùng ta coøn coù moät caùch khaùc ñeå neâu leân khaùi nieäm bieåu ñoà Hasse cho moät caáu truùc thöù töï (X, ) baèng caùch ñöa ra moät khaùi nieäm troäi tröïc tieáp: Cho x X, moät phaàn töû y X ñöôïc goïi laø moät troäi tröïc tieáp cuûa x neáu vaø chæ neáu ta coù 2 ñieàu kieän sau ñaây : (1) x y (y laø moät chaän treân cuûa x), (2) Vôùi moïi z, neáu x z vaø z y thì z = x hay z = y. Bieåu ñoà Hasse cho caáu truùc thöù töï (X, ) laø moät ñoà thò ñònh höôùng coù taäp hôïp ñænh laø X vaø taäp hôïp caùc caïnh laø moät phaàn cuûa goàm caùc caïnh (a,b) sao cho b laø moät troäi tröïc tieáp cuûa a. 3.3 Taäp hôïp höõu haïn coù thöù töï. Trong muïc naày chuùng ta seõ trình baøy moät soá keát quaû lieân quan ñeán caùc taäp hôïp höõu haïn coù thöù töï (hay caùc caáu truùc thöù töï höõu haïn). Bieåu ñoà Hasse laø moät coâng cuï höõu hieäu ñöôïc duøng trong vieäc khaûo saùt caùc thöù töï treân caùc taäp hôïp höõu haïn. Ñònh lyù 1. Cho (X, ) laø moät caáu truùc thöù töï höõu haïn. Ta coù : 1. Trong X coù ít nhaát moät phaàn töû toái tieåu. 2. Neáu X coù moät phaàn töû toái tieåu duy nhaát thì phaàn töû ñoù chính laø phaàn töû nhoû nhaát cuûa X. Chöùng minh: Cho (X, ) laø moät caáu truùc thöù töï höõu haïn (nghóa laø X höõu haïn vaø laø moät thöù töï treân X). Choïn moät phaàn töû a0 X. Neáu a0 khoâng phaûi laø moät phaàn töû toái tieåu thì theo ñònh nghóa cuûa phaàn töû toái tieåu ta coù moät phaàn töû a1 sao cho a1 a0 vaø a1 a0. -174-
Neáu a1 khoâng phaûi laø moät phaàn töû toái tieåu thì ta laïi coù moät phaàn töû a2 sao cho a2 a1 vaø a2 a1. Cöù tieáp tuïc quaù trình naày ñeå cho neáu an khoâng toái tieåu thì seõ coù moät phaàn töû an+1 sao cho an+1 an vaø an+1 an. Do X chæ coù moät soá höõu haïn phaàn töû, neân quaù trình treân phaûi döøng ñoái vôùi moät phaàn töû toái tieåu an. Nhö vaäy trong X coù ít nhaát moät phaàn töû toái tieåu. Giaû söû X coù moät phaàn töû toái tieåu duy nhaát laø m. Cho x laø moät phaàn töû tuøy yù thuoäc X. Theo laäp luaän treân, toàn taïi moät phaàn töû toái tieåu an sao cho an x. Vì phaàn töû toái tieåu laø duy nhaát neân an = m. Suy ra m x. Ñieàu naày chöùng toû m laø phaàn töû nhoû nhaát cuûa X. Theo doõi chöùng minh cuûa ñònh lyù treân ta ruùt ra moät thuaät toaùn ñeå tìm moät phaàn töû toái tieåu cuûa moät caáu truùc höõu haïn. Thuaät toaùn 1. Tìm phaàn töû toái tieåu trong moät caáu truùc thöù töï höõu haïn. Nhaäp : X laø moät taäp hôïp höõu haïn (khaùc roãng), laø moät thöù töï treân X. Xuaát : m laø moät phaàn töû toái tieåu trong X. Thuaät toaùn : 1. Choïn moät phaàn töû m X 2. for x X do if x m and x m then m  x (gaùn phaàn töû x cho bieán m), vaø trôû laïi böôùc 1. 3. m laø moät phaàn töû toái tieåu trong X. -175-
Nhaän xeùt : 1. Qua chöùng minh treân ta thaáy raèng vôùi moãi phaàn töû x X luoân toàn taïi moät phaàn töû toái tieåu m sao cho m x (ôû ñaây laø moät thöù töï treân X). 2. Ñònh lyù treân seõ khoâng coøn ñuùng neáu boû ñi ñieàu kieän höõu haïn cuûa taäp hôïp X. Vieäc tìm ra moät ví duï cho nhaän xeùt naày ñöôïc daønh cho phaàn baøi taäp. Ví du: Tìm phaàn töû toái tieåu cuûa taäp hôïp coù thöù töï ( 2,4,1,5,12,20, ). Aùp duïng thuaät toaùn treân chuùng ta seõ tìm ñöôïc phaàn töû toái tieåu cuûa caáu truùc thöù töï ñaõ cho laø 1. Töông töï nhö treân, ñoái vôùi caùc phaàn töû toái ñaïi ta cuõng coù ñònh lyù sau ñaây: Ñònh lyù 2. (1) Moïi taäp hôïp höõ haïn coù thöù töï (X, ) ñeàu coù moät phaàn töû toái ñaïi. Hôn nöõa, vôùi moïi x X luoân toàn taïi moät phaàn töû toái ñaïi M sao cho x M. (2) Neáu X coù moät phaàn töû toái ñaïi duy nhaát thì phaàn töû ñoù chính laø phaàn töû lôùn nhaát cuûa X. Vieäc chöùng minh ñònh lyù treân vaø xaây ñöïng thuaät toaùn ñeå tìm phaàn töû toái ñaïi ñöôïc daønh cho phaàn baøi taäp. 3.4 Saép xeáp topo (topological sorting) Saép xeáp topo laø moät vaán ñeà quan troïng trong vieäc khaûo saùt caùc caáu truùc thöù töï höõu haïn vaø phöông phaùp saép xeáp topo thöôøng ñöôïc söû -176-
duïng ñeå giaûi nhieàu baøi toaùn thöïc teá. Chuùng ta thöû xem baøi toaùn ñaët ra nhö sau: Giaû söû coù moät ñeà taøi goàm 20 coâng vieäc khaùc nhau. Moät soá coâng vieäc chæ coù theå ñöôïc thöïc hieän sau khi moät soá coâng vieäc khaùc ñöôïc thöïc hieän hoaøn taát. Chuùng ta phaûi thöïc hieän caùc coâng vieäc theo thöù töï naøo? Ñeå moâ hình cho vaán ñeà, chuùng ta ñaët X laø taäp hôïp 20 coâng vieäc cuûa ñeà taøi; treân X ta xeùt moät thöù töï (hay quan heä thöù töï) sao cho a b neáu vaø chæ neáu a vaø b laø 2 coâng vieäc trong ñoù coâng vieäc b chæ coù theå ñöôïc baét ñaàu khi coâng vieäc a ñaõ ñöôïc hoaøn thaønh. Muoán coù moät keá hoaïch thöïc hieän caùc coâng vieäc cho ñeà taøi chuùng ta phaûi tìm ra moät thöù töï cho taát caû 20 coâng vieäc “töông thích” vôùi thöù töï neâu treân. Tröôùc heát chuùng ta neâu ra ñònh nghóa khaùi nieäm “töông thích” nhö sau: Ñònh nghóa: Cho (X, ) laø moät taäp hôïp coù thöù töï. Moät thöù töï toaøn phaàn treân X ñöôïc goïi laø töông thích vôùi thöù töï neáu vaø chæ neáu a b a b, vôùi moïi a,b X. Vieäc xaây döïng thöù töï toaøn phaàn töông thích vôùi moät thöù töï cho tröôùc ñöôïc goïi laø saép xeáp topo (topological sorting). Thuaät toaùn saép xeáp topo cho moät taäp hôïp höõu haïn coù thöù töï döïa vaøo keát quaû neâu trong caùc ñònh lyù treân. Ñeå ñònh nghóa moät thöù töï toaøn phaàn treân (X, ), tröôùc heát ta choïn ra moät phaàn töû toái tieåu a1 cuûa X; phaàn töû naày toàn taïi do ñònh lyù 1. Keá ñoù, chuù yù raèng Neáu taäp hôïp X - a1  thì (X - a1, ) cuõng laø moät taäp hôïp höõu haïn (khaùc roãng) coù -177-
thöù töï. Ta laïi choïn ra phaàn töû toái tieåu a2 trong X - a1, roài loaïi a2 khoûi vieäc xem xeùt ôû böôùc tieáp theo ñeå choïn phaàn töû toái tieåu trong X - a1, a2 neáu taäp hôïp X - a1, a2 khaùc roãng. Tieáp tuïc quaù trình naày baèng caùch choïn phaàn töû toái tieåu ak+1 trong X - a1, a2, , ak khi taäp hôïp coøn phaàn töû. Vì X laø moät taäp hôïp höõu haïn neân quaù trình choïn treân phaûi döøng. Cuoái cuøng ta ñaõ saép caùc phaàn töû cuûa taäp hôïp X thaønh moät daõy a1, a2, , an thoûa ñieàu kieän : vôùi moïi i, j sao cho i < j ta coù ai aj hoaëc ai vaø aj khoâng coù quan heä trong thöù töï . Nhö vaäy choïn thöù töï toaøn phaàn treân X ñöôïc xaùc ñònh bôûi daây chuyeàn a1 a2 an thì ta ñöôïc moät thöù töï toaøn phaàn treân X töông thích vôùi thöù töï . Thuaät toaùn saép xeáp topo coù theå ñöôïc vieát döôùi daïng maõ giaû nhö sau: Thuaät toaùn 2. Saép xeáp topo (topological sorting) Nhaäp : (X, ) laø moät caáu truùc thöù töï höõu haïn. Xuaát : Daõy S = a1, a2, , an laø moät söï saép xeáp topo cuûa (X, ). Thuaät toaùn : 1. k := 1 2. S :=  3. while X  do begin ak := moät phaàn töû toái tieåu cuûa X (xem ñònh lyù 1 vaø thuaät toaùn 1) S := S  ak  X := X - ak  -178-
k := k +1 end 4. Xuaát S Ví duï: 1. Tìm moät thöù töï toaøn phaàn töông thích vôùi taäp hôïp coù thöù töï ( 1,5,2,4,12,20, ). Ñaàu tieân ta choïn moät phaàn töû toái tieåu. Phaàn töû naày phaûi laø 1 vì ñoù laø phaàn töû toái tieåu duy nhaát (hay phaàn töû nhoû nhaát). Keá ñoù ta choïn phaàn töû toái tieåu cuûa ( 5,2,4,20,12, ). Coù 2 phaàn töû toái tieåu trong taäp hôïp coù thöù töï naày laø 2 vaø 5. Ta choïn 5. Nhöõng phaàn töû coøn laïi laø 2,4,20,12. Trong taäp hôïp naày ta choïn moät phaàn töû toái tieåu, ví duï laø 2. Tieáp tuïc quaù trình naày ta laàn löôït choïn ra ñöôïc caùc phaàn töû 4, 20, vaø 12. Cuoái cuøng ta ñöôïc moät thöù töï toaøn phaàn cho bôûi: 1 5 2 4 20 12. 2. Giaû söû coù moät ñeà taøi ôû moät coâng ty maùy tính ñoøi hoûi phaûi hoaøn thaønh 7 coâng vieäc A, B, C, D, E, F, G. Moät soá coâng vieäc chæ coù theå baét ñaàu sau khi ñaõ hoaøn thaønh moät soá coâng vieäc khaùc. Noùi moät c aùch khaùc, coù moät thöù töï ñöôïc ñònh ra treân taäp hôïp caùc coâng vieäc nhö sau : (coâng vieäc X) (coâng vieäc Y) neáu vaø chæ neáu coâng vieäc Y chæ coù theå baét ñaàu khi coâng vieäc X ñaõ ñöôïc thöïc hieän hoaøn taát. Bieåu ñoà Hasse cho 7 coâng vieäc öùng vôùi thöù töï naày laø : -179-
Haõy tìm moät thöù töï thöïc hieän cho 7 coâng vieäc ñeå coù theå hoaøn thaønh ñeà taøi. Giaûi: Aùp duïng phöông phaùp saép xeáp topo ta ñaït ñöôïc moät thöù töï coù theå thöïc hieän cho caùc coâng vieäc laø : A C B D E F G. IV. DAØN (Lattice) - Ñònh nghóa 4.1: Cho (L, ) laø moät taäp hôïp coù thöù töï. Ta noùi (L, ) laø moät daøn neáu vaø chæ neáu vôùi moïi a, b L, taäp hôïp a,b coù chaän döôùi lôùn nhaát vaø coù chaän treân nhoû nhaát; töùc laø toàn taïi sup(a,b) vaø inf(a,b). Ta seõ duøng kyù hieäu aVb vaø ab ñeå chæ sup(a,b) vaø inf(a,b) : a V b = sup(a,b) a  b = inf(a,b) -180-
Nhaän xeùt: 1. Taäp hôïp coù thöù töï toaøn phaàn laø moät daøn, vôùi a V b = max(a,b) vaø a  b = min(a,b). 2. Trong daøn (L, ), phaàn töû sup(a,b) = aVb ñöôïc ñaëc tröng bôûi 2 tính chaát sau: (1) a aVb vaø b aVb, (2)  c L : (a c vaø b c) (aVb c) 3. Trong daøn (L, ), phaàn töû inf(a,b) = a  b ñöôïc ñaëc tröng bôûi 2 tính chaát sau: (1) ab a vaø ab b, (2)  c L : (c a vaø c b) (c ab) Ví duï 4.1. Cho E laø moät taäp hôïp; Taäp hôïp (P(E), ) laø moät daøn. Vôùi moïi A, B P(E), ta thaáy AB vaø AB laàn löôït chính laø chaän treân nhoû nhaát vaø chaän döôùi lôùn nhaát theo thöù töï . Noùi caùch khaùc, ta coù : A V B = A  B A  B = A  B Ví duï 4.2. Ta ñaõ bieát raèng (N,) laø moät taäp hôïp coù thöù töï. Theo thöù töï , thöù töï “chia heát”, vôùi 2 soá töï nhieân a vaø b ta coù chaän treân nhoû nhaát chính laø boäi soá chung nhoû nhaát cuûa chuùng, chaän döôùi lôùn nhaát chính laø öôùc soá chung lôùn nhaát cuûa chuùng. Vaäy (N,) laø moät daøn, vaø ta coù : a V b = [a, b] (boäi soá chung nhoû nhaát cuûa a vaø b) a  b = (a, b) (öôùc soá chung lôùn nhaát cuûa a vaø b) Ví duï 4.3. Cho n laø moät soá töï nhieân. Ñaët Dn laø taäp hôïp taát caû caùc öôùc soá khoâng aâm cuûa n. Ta coù (Dn, ) laø moät taäp hôïp coù thöù -181-
töï. Cho a vaø b laø 2 öôùc soá khoâng aâm cuûa n, ta coù n laø moät boäi soá chung cuûa a vaø b. Do ñoù boäi soá chung nhoû nhaát [a,b] cuûa a vaø b cuõng laø moät öôùc soá cuûa n. Vaäy [a,b] chính laø chaän treân nhoû nhaát cuûa a vaø b trong Dn. Öôùc soá chung lôùn nhaát (a,b) cuûa a vaø b cuõng laø moät öôùc soá cuûa n, neân ta coù (a,b) chính laø chaän döôùi lôùn nhaát cuûa a vaø b trong Dn. Toùm laïi, ta coù theå keát luaän raèng (Dn, ) laø moät daøn. Ví duï 4.4. Caùc taäp hôïp coù thöù töï ñöôïc bieåu dieãn bôûi caùc bieåu ñoà Hasse trong hình döôùi ñaây coù phaûi laø daøn hay khoâng? Caùc taäp hôïp coù thöù töï ñöôïc bieåu dieãn bôûi (a) vaø (b) laø caùc daøn. Taäp hôïp coù thöù töï ñöôïc bieåu dieãn bôûi (c) khoâng phaûi laø moät daøn vì 56 khoâng toàn taïi. Taäp hôïp coù thöù töï ñöôïc bieåu dieãn bôûi (d) khoâng phaûi laø moät daøn vì 4V5 khoâng toàn taïi. Ghi chuù : Vôùi 2 daøn X vaø Y ta coù theå ñònh ra moät thöù töï treân tích Descartes XxY döïa vaøo caùc thöù töï treân X vaø treân Y ñeå XxY trôû thaønh moät daøn (xem phaàn baøi taäp). -182-
Sau ñaây chuùng ta seõ giôùi thieäu tieáp khaùi nieäm “daøn con” vaø “ñoàng caáu daøn”. - Ñònh nghóa 4.2. Cho (L, ) laø moät daøn vaø B laø moät taäp hôïp con cuûa L. Ta noùi B laø moät daøn con cuûa L khi vaø chæ khi vôùi moïi a,b B ta coù aVb B vaø ab B. Ví duï 4.5. Cho moät soá töï nhieân n, ta coù Dn laø moät daøn con cuûa daøn (N,). Ví duï 4.6. Xem daøn L coù bieåu ñoà Hasse nhö sau: Trong caáu truùc thöù töï coù caùc bieåu ñoà Hasse nhö döôùi ñaây, caáu truùc naøo laø moät daøn con cuûa daøn L? -183-
Taäp hôïp coù thöù töï (a) khoâng phaûi laø moät daøn con cuûa L vì 2V3 khoâng thuoäc taäp hôïp ñoù. Taäp hôïp coù thöù töï (c) cuõng khoâng phaûi laø moät daøn con cuûa L vì 23 khoâng thuoäc taäp hôïp ñoù. Caùc taäp hôïp coù thöù töï (b) vaø (d) ñuùng laø caùc daøn con cuûa L. Ví duï 4.7. Cho (L, ) laø moät daøn vaø a, b laø caùc phaàn töû thuoäc L. Ñaët [a,b] = x L  a x vaø x b  -184-
Chöùng minh raèng [a,b] laø moät daøn con cuûa L vôùi moïi a, b thoûa a b. Vieäc chöùng minh tính chaát naày khaù ñôn giaûn vaø ñöôïc daønh cho phaàn baøi taäp. - Ñònh nghóa 4.3. Cho (L, ) vaø (M, ) laø caùc daøn. Moät aùnh xaï f : L M ñöôïc goïi laø moät ñoàng caáu daøn neáu vaø chæ neáu  x,y L : x y f(x) f(y) Tröôøng hôïp f coù theâm tính chaát song aùnh thì ta noùi f laø moät ñaúng caáu daøn. Ghi chuù: Ta coù theå chöùng minh ñöôïc raèng neáu f : L M laø moät ñaúng caáu daøn thì vôùi moïi x, y L ta coù: f (x  y) = f(x)  f(y) f (x  y) = f(x)  f(y) Ví duï 4.8. Xem hai daøn L vaø M coù bieåu ñoá Hasse nhö döôùi ñaây: -185-
Aùnh xaï f : L M ñöôïc ñònh nghóa bôûi : f(1) = b, f(2) = e, f(3) = c, f(4) = v laø moät ñoàng caáu daøn. Aùnh xaï g : L M ñöôïc ñònh nghóa bôûi : g(1) = a, g(2) = b, g(3) = d, g(4) = v khoâng phaûi laø moät ñoàng caáu daøn vì g(2) V g(3) = b V d = c, nhöng g(2V3) = g(4) = v c. Ví duï 4.9. Cho E = a,b. Hai daøn (P(E), ) vaø (D10,) ñaúng caáu vôùi nhau. Thaät vaäy, xeùt aùnh xaï f : P(E) D10 ñöôïc ñònh nghóa bôûi : f() = 1, f( a) = 2, f( b) = 5, f( a,b) = 10 ta coù theå kieåm tra deã daøng f laø moät ñaúng caáu daøn. Ñieàu naày coù theå thaáy roõ khi ta quan saùt caùc bieåu ñoà Hasse cuûa 2 daøn treân. Baây giôø chuùng ta seõ phaùt bieåu moät soá tính chaát cuûa daøn. Vieäc chöùng minh caùc tính chaát naày ñöôïc xem nhö baøi taäp. Ñònh lyù 4.1. Vôùi moïi phaàn töû x, y, z thuoäc daøn (L, ) ta coù : 1. x V x = x , x  x = x (tính luõy ñaúng) 2. x V y = y V x , x  y = y  x (tính giao hoaùn) 3. xV(yVz)=(xV y) V z (tính keát hôïp) x  (y  z) = (x  y)  z 4. (x y) (xVy = y) (x  y = x) 5. x  (x V y) = x = x V (x  y) -186-
Ñònh lyù 4.2. Vôùi moïi phaàn töû a, b, c, d thuoäc daøn (L, ) ta coù : 1. (a b) (aVc bVc vaø ac bc) 2. (a b vaø c d) (aVc bVd vaø ac bd) Ñònh lyù 4.3. Vôùi moïi phaàn töû x, y, z thuoäc daøn (L, ) ta coù : 1. x  (y V z) (xy) V (xz) x V (y  z) (xVy)  (xVz) 2. (x z) (xV(y  z) (xVy)  z) -187-
BAØI TAÄP Caâu 1: 1. Vôùi X = 1,2,3, haõy tìm ma traän bieåu dieõn cuûa caùc quan heä sau ñaây: (a) (1,1), (1,2), (1,3) (b) (1,1), (1,2), (1,3), (2,2), (2,3), (3,3) 2. Haõy lieät keâ quan heä R treân taäp hôïp 1,2,3 bieát caùc ma traän bieåu dieãn nhö sau: 1 0 1 0 1 0 1 1 1 (a) 0 1 0 (b) 0 1 0 (c) 1 0 1 1 0 1 0 1 0 1 1 1 Caâu 2: Cho moät quan heä 2 ngoâi R treân moät taäp hôïp X coù ma traän bieåu dieãn laø MR. Tìm ñieàu kieän (caàn vaø ñuû) treân ma traän MR ñeå quan heä R coù tính chaát: (a) phaûn xaï (b) ñoái xöùng (c) phaûn xöùng (d) truyeàn Caâu 3: Cho R laø moät quan heä 2 ngoâi treân moät taäp hôïp höõu haïn X. Tìm thuaät toaùn ñeå thöïc hieän caùc yeâu caàu sau ñaây: 1. Xaùc ñònh xem quan heä R coù phaûi laø moät quan heä töông ñöông hay khoâng? 2. Xaùc ñònh xem quan heä R coù phaûi laø moät quan heä thöù töï hay khoâng? -188-
Caâu 4: Döôùi ñaây laø caùc ma traän bieåu dieãn cuûa caùc quan heä; haõy xaùc ñònh xem quan heä naøo laø quan heä töông ñöông. 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 0 (a) 0 1 1 (b) (c) 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 0 0 1 Caâu 5: Coù bao nhieâu quan heä töông ñöông treân moät taäp hôïp coù 4 phaàn töû ? Haõy trình baøy thuaät toaùn lieät keâ ra taát caû caùc quan heä töông ñöông ñoù. Caâu 6: Veõ bieåu ñoà Hasse cuûa daøn (D105, ) (xem ví duï 3.3) Caâu 7: 1. Cho 2 taäp hôïp coù thöù töï (X, ) vaø (Y,). Treân taäp hôïp tích XxY ta ñònh nghóa moät quan heä 2 ngoâi nhö sau: (a,b) (c,d) ((a c) vaø (b  d)) Chöùng minh raèng laø moät thöù töï treân XxY. 2. Haõy môû roäng ñònh nghóa treân cho tích cuûa nhieàu taäp hôïp coù thöù töï. Caâu 8: 1. Vôùi 2 taäp hôïp coù thöù töï (X, ) vaø (Y,) chuùng ta coøn coù moät thöù töï treân XxY ñöôïc goïi laø thöù töï töï ñieån. Quan heä (thöù töï) naày ñöôïc ñònh nghóa bôûi : (a,b) (c,d) ((a b vaø a b) hay (a=b vaø c  d)) Haõy chöùng minh quan heä ñuùng laø moät quan heä thöù töï tr6en taäp hôïp tích XxY. -189-
2. Môû roäng: ñònh nghóa chöùng minh cho thöù töï töï ñieån treân tích cuûa höõu haïn taäp hôïp coù thöù töï. Caâu 9: Cho (X, ) laø moät caáu truùc thöù töï höõu haïn. Haõy trình baøy moät thuaät toaùn xaùc ñònh bieåu ñoá Hasse cho caáu truùc thöù töï treân. Caâu 10: Cho (X, ) laø moät caáu truùc thöù töï höõu haïn. Haõy trình baøy caùc thuaät toaùn thöïc hieän caùc yeâu caàu sau ñaây: 1. Tìm moät phaàn töû toái ñaïi cuûa X. 2. Tìm phaàn töû nhoû nhaát (neáu coù) cuûa X. 3. Tìm phaàn töû lôùn nhaát (neáu coù) cuûa X. Caâu 11: Cho (X, ) laø moät caáu truùc thöù töï höõu haïn. Ta goïi moät daây chuyeàn trong X laø moät taäp hôïp con A cuûa X sao cho thöù töï khi xeùt thu heïp treân A laø moät thöù töï toaùn phaàn. 1. Chöùng minh raèng moïi phaàn töû x X ñeàu naèm trong moät daây chuyeàn. 2. Trình baøy moät thuaät toaùn tìm moät daây chuyeàn chöùa moät phaàn töû x cho tröôùc. Caâu 12: Trong ñònh lyù 2.1. ta khoâng theå boû ñi ñieàu kieän “höõu haïn” cuûa taäp hôïp X. Haõy tìm moät ví duï cho söï khaúng ñònh naày. Caâu 13: 1. Tìm moät caáu truùc thöù töï goàm 6 phaàn töû, trong ñoù coù 2 phaàn töû toái ñaïi vaø 3 phaàn töû toái tieåu. 2. Coù bao nhieâu thöù töï treân moät taäp hôïp 6 phaàn töû thoûa ñieàu kieän neâu trong caâu 1. -190-
Caâu 14: Treân taäp hôïp caùc soá töï nhieân N ta xeùt moät quan heä R ñöôïc ñònh nghóa nhö sau: x R y neáu vaø chæ neáu moät trong 3 ñieàu kieän sau ñaây ñuùng: (1) (x 2N) vaø (y 2N) vaø (x y) (2) (x 2N) vaø (y 2N) vaø (x y) (3) (x 2N) vaø (y 2N) trong ñoù 2N laø taäp hôïp taát caû caùc boäi soá cuûa 2 (hay caùc soá chaún). Chöùng minh raèng R laø moät quan heä thöù töï treân N. Caâu 15: Cho A = 1,2,3,4,5. Cho R vaø S laø hai quan heä (2 ngoâi) treân A coù ma traän bieåu dieãn laàn löôït laø 1 0 0 0 0 1 0 1 1 0 1 1 0 1 0 0 1 1 1 0 MR = 1 1 1 1 1 MS = 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 1 Chöùng minh raèng R vaø S laø nhöõng quan heä thöù töï treân A. Veõ caùc bieåu ñoà Hasse cho (A,R) vaø (A,S). Caâu 16: 1. Cho X laø moät taäp hôïp coù thöù töï vôùi bieåu ñoà Hasse ñöôïc cho tröôùc laø H. Cho x, y laø hai phaàn töû thuoâc X. Tìm moät thuaät toaùn xaùc ñònh xem x vaø y quan heä vôùi nhau theo thöù töï ñang xeùt hay khoâng. 2. Haõy trình baøy thuaät toaùn xaùc ñònh moät quan heä thöù töï treân moät taäp hôïp höõu haïn töø bieåu ñoà Hasse ñaõ bieát tröôùc. -191-
Caâu 17: 1. Cho (X, ) laø moät caáu truùc thöù töï höõu haïn vaø A laø moät taäp con khaùc roãng cuûa X. Trình baøy caùc thuaät toaùn tìm sup (A) vaø inf(A). 2. Haõy cho moät ví duï cuï theå veà X vaø A, vaø vieát ra töøng böôùc thöïc hieän thuaät toaùn cho ví duï naày. Caâu 18: Cho (L, ) laø moät daøn vaø a, b laø caùc phaàn töû thuoäc L sao cho a b. Chöùng minh raèng [a,b] laø moät daøn con cuûa L (xem ví duï 3.7). Caâu 19: Cho (L, ) vaø (M, ) laø hai daøn. Treân taäp hôïp tích LxM haõy ñònh nghóa moät thöù töï ñeå ñöôïc moät daøn thoûa 2 ñieàu kieän sau ñaây: (1) (a,b) V (c,d) = (aVc, bVd) (2) (a,b)  (c,d) = (ac, bd) Caâu 20: 1. Chöùng minh raèng neáu f : L M laø moät ñoàng caáu daøn thì f baûo toaøn thöù töï, töùc laø f(x) f(y) vôùi moïi x,y sao cho x y. 2. Chæ ra raèng ñieàu ngöôïc laïi trong phaùt bieåu treân laø khoâng ñuùng. Noùi caùch khaùc, moät aùnh xaï L M baûo toaøn thöù töï khoâng nhaát thieát laø moät ñoàng caáu daøn. Caâu 21: Veõ ra caùc bieåu ñoà Hasse cho caùc daøn goàm 2 phaàn töû, 3 phaàn töû, 4 phaàn töû, 5 phaàn töû, 6 phaàn töû. Caâu 22: Chöùng minh raèng daøn D30 ñaúng caáu vôùi daøn (P( a,b,c), ). -192-
CHÖÔNG 6. ÑAÏI SOÁ BOOL VAØ HAØM BOOL I. CAÙC PHEÙP TOAÙN 1.1 Caùc ñònh nghóa. Raát nhieàu taäp hôïp quen thuoäc ñeàu coù nhöõng pheùp toaùn treân ñoù. Treân taäp hôïp caùc soá nguyeân coù pheùp toaùn coäng, pheùp toaùn nhaân. Treân taäp hôïp caùc soá thöïc khaùc khoâng coù pheùp toaùn nhaân vaø coøn coù caû pheùp laáy nghòch ñaûo. Moãi pheùp toaùn treân moät taäp hôïp cho ta moät qui taéc nhaèm taïo ra moät phaàn töû töø moät hay nhieàu phaàn töû naøo ñoù. Pheùp coäng thöïc hieän treân 2 soá 5 vaø 7 cho ra soá 12; pheùp laáy nghòch ñaûo cuûa soá 2 cho keát quaû laø soá 0.5. Khi pheùp toaùn thöïc hieän treân 2 phaàn töû ta noùi laø pheùp toaùn 2 ngoâi, pheùp toaùn thöïc hieän treân moät phaàn töû thì ñöôïc goïi laø pheùp toaùn moät ngoâi. Döôùi ñaây ta seõ neâu leân ñònh nghóa toaùn hoïc cuûa caùc pheùp toaùn. Ñònh nghóa 1. (pheùp toaùn 2 ngoâi) Cho X laø moät taäp hôïp khaùc roãng. Moät pheùp toaùn hai ngoâi treân taäp hôïp X laø moät aùnh xaï T ñi töø XxX vaøo X. Kyù hieäu cuûa aùnh xaï ñöôïc goïi laø kyù hieäu cuûa pheùp toaùn hay laø moät toaùn töû. aûnh cuûa caëp (a,b) qua aùnh xaï T ñöôïc goïi laø keát quaû thöïc hieän pheùp toaùn T treân 2 phaàn töû a vaø b, vaø thöôøng ñöôïc vieát laø a T b. Nhö vaäy, neáu T laø moät pheùp toaùn 2 ngoâi treân X thì ta coù aùnh xaï: T:XxX X (a,b) T(a,b) = a T b -193-
Ñònh nghóa 2. (pheùp toaùn 1 ngoâi) Cho X laø moät taäp hôïp khaùc roãng. Moät pheùp toaùn 1 ngoâi treân taäp hôïp X laø moät aùnh xaï T ñi töø X vaøo X. Kyù hieäu cuûa aùnh xaï ñöôïc goïi laø kyù hieäu cuûa pheùp toaùn hay laø moät toaùn töû. aûnh cuûa a qua aùnh xaï T ñöôïc goïi laø keát quaû thöïc hieän pheùp toaùn T treân phaàn töû a. Ví duï: 1. Treân caùc taäp hôïp soá N, Z, Q, R, C coù caùc pheùp toaùn + (coäng) vaø * (nhaân). 2. Treân taäp hôïp caùc ma traän soá thöïc vuoâng caáp n coù caùc pheùp toaùn: + (coäng matraän) vaø * (nhaân ma traän). 3. Cho E laø moät taäp hôïp. ñaët X = P(E). Treân X coù caùc pheùp toaùn taäp hôïp thoâng thöôøng : - pheùp giao hai taäp hôïp, ñöôïc kyù hieäu laø . - pheùp hoäi hai taäp hôïp, ñöôïc kyù hieäu laø . - pheùp laáy buø cuûa moät taäp hôïp, ñöôïc kyù hieäu laø c. Theo kyù hieäu naày, phaàn buø cuûa taäp A  X laø Ac. Pheùp toaùn  vaø  laø caùc pheùp toaùn 2 ngoâi, pheùp toaùn c laø pheùp toaùn 1 ngoâi. 4. Cho E laø moät taäp hôïp khaùc roãng. ñaët X laø taäp hôïp caùc aùnh xaï ñi töø E vaøo E. Treân X coù moät pheùp toaùn aùnh xaï thoâng thöôøng; ñoù laø pheùp hôïp noái aùnh xaï. Pheùp toaùn naày ñöôïc kyù hieäu laø o. Ñaây laø moät pheùp toaùn 2 ngoâi treân X. 5. Ñaët X laø taäp hôïp taát caû caùc chuoãi kyù töï. Pheùp noái 2 chuoãi pyù töï laø moät pheùp toaùn 2 ngoâi treân X. 6. Taäp hôïp B = 0,1 goàm 2 phaàn töû ñaïi dieän cho 2 chaân trò “sai” vaø “ñuùng”. Ta ñaõ bieát treân taäp hôïp B coù caùc pheùp toaùn logic:  (hay),  (vaø),  (phuû ñònh), (keùo theo). Trong caùc pheùp toaùn treân chæ coù pheùp toaùn  (phuû ñònh) laø -194-
pheùp toaùn 1 ngoâi, coøn caùc pheùp toaùn khaùc ñeàu laø caùc pheùp toaùn 2 ngoâi. 7. Cho (L, ) laø moät daøn. Khi ñoù vôùi moãi caëp (a,b) goàm caùc phaàn töû cuûa L ta coù hai phaàn töû töông öùng laø inf(a,b) vaø sup(a,b), ñöôïc kyù hieäu laàn löôït laø ab vaø ab. Nhö vaäy treân moãi daøn ta coù hai pheùp toaùn 2 ngoâi laø  vaø . Pheùp toaùn  thöïc hieän treân caùc phaàn töû a, b seõ cho keát quaû laø chaän treân nhoû nhaát cuûa a vaø b. Pheùp toaùn  thöïc hieän treân caùc phaàn töû a, b seõ cho keát quaû laø chaän döôùi lôùn nhaát cuûa a vaø b. Ghi chuù : 1. Moät caùch toång quaùt, ta coù theå ñònh nghóa pheùp toaùn n-ngoâi treân moät taäp hôïp X laø moät aùnh xaï ñi töø Xn vaøo X. Öùng vôùi moãi boä n phaàn töû (a1, , an) pheùp toaùn seõ cho ta moät phaàn töû keát quaû thuoäc X. 2. Trong tröôøng hôïp taäp hôïp X laø höõu haïn thì ngöôøi ta coù theå ñònh nghóa hay xaùc ñònh pheùp toaùn baèng caùch lieät keâ keát quaû thöïc hieän pheùp toaùn cho moïi tröôøng hôïp coù theå coù. Ví duï X = a1, , an  goàm n phaàn töû. Giaû söû * laø moät pheùp toaùn 2 ngoâi treân X. Khi ñoù, pheùp toaùn * coù theå ñöôïc xaùc ñònh bôûi baûng sau ñaây: * a1  aj  an a1    ai   ai* aj  an -195-
Baûng treân ñöôïc goïi laø baûng Cayley cuûa pheùp toaùn 2 ngoâi. Nhö vaäy öùng vôùi moãi pheùp toaùn 2 ngoâi treân X ta coù moät ma traän coù caáp n vôùi phaàn töû ôû doøng i coät j baèng ai* aj. Veà sau, nhieàu tính chaát cuûa pheùp toaùn seõ ñöôïc xem xeùt thoâng qua ma traän naày. Chuùng ta ñaõ töøng thaáy nhöõng pheùp toaùn 2 ngoâi ñöôïc ñònh nghóa baèng baûng nhö theá; ñoù laø caùc pheùp toaùn logic  (hay),  (vaø), (keùo theo). Ví duï: Cho n laø moät soá nguyeân lôùn hôn 1. Treân taäp hôïp Zn = 0, 1, . . ., n - 1, taäp hôïp thöông theo quan heä ñoàng dö modulo n treân taäp hôïp caùc soá nguyeân Z, ta ñònh nghóa 2 pheùp toaùn + vaø * nhö sau: a + b = a + b ,  a,b Z a * b = a * b ,  a,b Z Ñònh nghóa treân döïa vaøo phaàn töû ñaïi dieän cuûa lôùp töông ñöông. Tuy nhieân ta coù theå kieåm chöùng deã daøng raèng ñònh nghóa treân laø hôïp leä. Tröôøng hôïp n = 3, pheùp + treân Z3 coù baûng Cayley nhö sau : + 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1 trong ñoù ta vieát a thay cho a vôùi moïi a = 0, 1, 2. -196-
1.2 Caùc tính chaát ñaïi soá cuûa pheùp toaùn 2 ngoâi. Trong muïc naày chuùng ta neâu leân moät soá tính chaát ñaïi soá thöôøng ñöôïc xem xeùt ñoái vôùi caùc pheùp toaùn 2 ngoâi. Ñònh nghóa 3. 1. Ta noùi moät pheùp toaùn 2 ngoâi T treân moät taäp hôïp X coù tính giao hoaùn neáu  x,y X : x T y = y T x 2. Ta noùi moät pheùp toaùn 2 ngoâi T treân moät taäp hôïp X coù tính keát hôïp neáu  x,y,z X: xT(yTz) = (xTy)Tz Ví duï: 1. Caùc pheùp toaùn + vaø * treân caùc taäp hôïp soá ñeàu coù tính chaát keát hôïp vaø giao hoaùn. 2. Pheùp toaùn + (coäng) treân taäp hôïp caùc ma traän thöïc vuoâng caáp n, kyù hieäu Mn(R), coù tính chaát giao hoaùn vaø keát hôïp. Nhöng pheùp toaùn * (nhaân ma traän) coù tính keát hôïp nhöng khoâng coù tính giao hoaùn. Pheùp nhaân treân Mn(R) chæ coù tính giao hoaùn khi n = 1. (Ñònh nghóa cuûa caùc pheùp toaùn ma traän coù theå ñöôïc tham khaûo ôû phaàn ñaïi soá tuyeán tính) 3. Pheùp chia treân taäp hôïp caùc soá höõu tæ khaùc 0 khoâng coù tính keát hôïp vaø cuõng khoâng coù tính giao hoaùn. Bôûi vì 1 / 2 2 / 1, vaø (8/4) / 2 = 1 4 = 8/(4/2). 4. Ñaët X laø taäp hôïp taát caû caùc aùnh xaï ñi töø moät taät hôïp E vaøo chính noù. Pheùp toaùn o (hôïp noái aùnh xaï) treân X coù tính keát hôïp. Bôûi vì vôùi 3 aùnh xaï f, g, h töø E vaøo E, theo tính chaát veà aùnh xaï hôïp, ta coù fo(goh) = (fog)oh. -197-
Noùi chung pheùp toaùn o khoâng coù tính giao hoaùn; pheùp toaùn chæ coù tính giao hoaùn trong tröôøng hôïp E coù moät phaàn töû. Thaät vaäy, neáu E coù nhieàu hôn 1 phaàn töû thì ta coù theå choïn ra 2 phaàn töû khaùc nhau a, b trong E. Xeùt 2 aùnh xaï f vaø g nhö sau: f(x) = a vôùi moïi x E, vaø g(x) = b vôùi moïi x E. Ta coù fog(x) = a vôùi moïi x E, vaø gof(x) = b vôùi moïi x E; neân fog gof. 5. Treân moät daøn L, caùc pheùp toaùn 2 ngoâi  vaø  coù tính chaát giao hoaùn vaø keát hôïp Cho * laø moät pheùp toaùn 2 ngoâi treân moät taäp hôïp X = a1, , an. Baây giôø chuùng ta seõ xem xeùt caùc tính chaát giao hoaùn vaø keát hôïp cuûa pheùp toaùn * coù lieân quan nhö theá naøo ñeán caùc tính chaát cuûa ma traän M = (mij) Mn(X) lieân keát vôùi pheùp toaùn. Nhaéc laïi laø mij = ai* aj. Pheùp toaùn * giao hoaùn khi vaø chæ khi ai* aj = aj* ai vôùi moïi i, j. Ñieàu naày töông ñöông vôùi ñieàu kieän : mij = mj i vôùi moïi i, j. Vaäy pheùp toaùn giao hoaùn khi vaø chæ khi ma traän lieân keát vôùi pheùp toaùn laø ñoái xöùng. Ñoái vôùi tính chaát keát hôïp chuùng ta coù theå giaû söû raèng X = 1, 2, , n,vaø ta seõ xaây döïng moät haøm laáy giaù trò Bool ASSOC vôùi ñoái laø moät ma traän M coù caáp n thuoäc Mn(X) sao cho ASSOC(M) = 1 (True) pheùp toaùn 2 ngoâi ñöôïc lieân keát vôùi ma traän M coù tính keát hôïp Nhaän xeùt raèng vôùi M Mn(X), M[i,j] X = 1, 2, , n, haøm ASSOC coù theå ñöôïc vieát döôùi daïng maõ giaû nhö sau: -198-
Function ASSOC (M) : Boole begin T  1 for i=1 to n do for j=1 to n do for k=1 to n do if M[M[i,k],j] M[i, M[k,j]] then begin T  0 goto OUT end OUT: return T end Ñònh nghóa 4. Cho X laø moät taäp hôïp khaùc roãng, * laø moät pheùp toaùn 2 ngoâi treân X. 1. pheùp toaùn * ñöôïc goïi laø luõy ñaúng khi vaø chæ khi x * x = x , vôùi moïi x X 2. Moät phaàn töû e X ñöôïc goïi laø phaàn töû trung hoøa cuûa pheùp toaùn * treân X khi vaø chæ khi x * e = e * x = x , vôùi moïi x X 3. Giaû söû pheùp toaùn * coù phaàn töû trung hoøa laø e. Ta noùi moät phaàn töû x X laø khaû nghòch (hay coù nghòch ñaûo) khi vaø chæ khi  x’ X : x * x’ = e = x’ * x -199-
Nhaän xeùt : 1. Neáu pheùp toaùn coù tính keát hôïp thì phaàn töû trung hoøa (neáu coù) laø duy nhaát, vaø trong tröôøng hôïp toång quaùt ngöôøi ta coøn goïi laø “phaàn töû ñôn vò”. 2. Khi pheùp toaùn coù tính keát hôïp vaø coù phaàn töû trung hoøa, vôùi moãi phaàn töû x khaû nghòch, phaàn töû x’ trong ñònh nghóa treân laø duy nhaát. Ta goïi x’ laø phaàn töû nghòch ñaûo cuûa x, vaø kyù hieäu laø x-1. Ghi chuù : 1. Trong tröôøng hôïp pheùp toaùn ñöôïc kyù hieäu laø ‘.’ (daáu nhaân) thì phaàn töû trung hoøa cuûa pheùp toaùn thöôøng ñöôïc kyù hieäu 1, vaø ñöôïc goïi laø “ñôn vò”. 2. Khi pheùp toaùn ñöôïc kyù hieäu laø ‘+’ (daáu coäng) thì phaàn töû trung hoøa cuûa pheùp toaùn thöôøng ñöôïc kyù hieäu 0, vaø ñöôïc goïi laø “zero”. Trong tröôøng hôïp naày, moãi phaàn töû x thoûa ñieàu kieän khaû nghòch seõ ñöôïc goïi laø “coù ñoái”, vaø phaàn töû x’ trong ñònh nghóa ñöôïc goïi laø phaàn töû ñoái cuûa x. Ta kyù hieäu phaàn töû ñoái cuûa x laø -x. Ví duï: 1. Treân taäp B = 0,1 (goàm 2 giaù trò Boole), coù caùc pheùp toaùn  vaø . Pheùp toaùn V coù caùc tính chaát : giao hoaùn, keát hôïp, coù trung hoøa laø 0, luõy ñaúng. Phaàn töû 1 khoâng khaû nghòch ñoái vôùi pheùp  vì 1  x = 1 0 vôùi moïi x B. Pheùp toaùn  coù caùc tính chaát : giao hoaùn, keát hôïp, coù trung hoøa laø 1, luõy ñaúng. Phaàn töû 0 khoâng khaû nghòch ñoái vôùi pheùp  vì 0  x = 0 1 vôùi moïi x B. 2. Pheùp toaùn + (coäng) treân caùc taäp hôïp soá N, Z, Q, R, C coù caùc tính chaát : giao hoaùn, keát hôïp, coù trung hoøa (hay phaàn -200-