Giáo trình Toán rời rạc: Phần 2 - TS. Đỗ Văn Nhơn (biên soạn)

Phần 2 Giáo trình Toán rời rạc tiếp tục giới thiệu đến bạn đọc nội dung từ chương 4 đến chương 6 về thuật toán, quan hệ, đại số bool và hàm số bool. Giáo trình được trình bày dưới dạng lý thuyết với các ví dụ minh họa và bài tập, đồng thời sau mỗi chương đều có các bài tập giúp cho bạn đọc cũng như các bạn sinh viên thuận tiện trong việc nghiên cứu, củng cố kiến thức và áp dụng giải bài tập.
Nội dung trích xuất từ tài liệu:
Giáo trình Toán rời rạc: Phần 2 - TS. Đỗ Văn Nhơn (biên soạn)Chöông 4: THUAÄT TOAÙNI. Thuaät toaùn vaø caùch bieåu dieãn thuaät toaùn1.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ätphöô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ùcchöông trình nhôø caùc ngoân ngöõ laäp trình. Moät thuaät toaùn thöôøng ñöôïctheå 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ùnbaè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ânngöõ 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áitaàm thöôøng. Tuy nhieân ñaây laø moät trong nhöõng ví duï khaù toát ñeå minhhoïa cho khaùi nieäm veà thuaät toaùn. Coù nhieàu vaán ñeà maø trong ñoù ñoøihoû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ìmra 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öõngphöô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ätcaù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äncaù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ântrong 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öïchieä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ànkieåm tra. Trong caùc cung noái vôùi nuùt naày coù 2 cung ra chæ höôùng ñitheo 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àutieân. Sau khi thöïc hieän caùc thao taùc hoaëc kieåm tra ñieàu kieän ôû moãinuùt thì boä xöû lyù seõ theo moät cung ñeå ñeán nuùt khaùc. Quaù trình thöïchieän thuaät toaùn döøng ...