Giáo trình Nhập môn trí tuệ nhân tạo: Phần 2 - GS.TSKH. Hoàng Kiếm, ThS. Đinh Nguyễn Anh Dũng

Chia sẻ: Hoa La Hoa | Ngày: | Loại File: PDF | Số trang:99

Thêm vào BST

Báo xấu

285
lượt xem 106
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phần 2 Giáo trình Nhập môn trí tuệ nhân tạo tiếp tục giới thiệu đến bạn đọc nội dung chương 2 và chương 3. Chương 2 giới thiệu về biểu diễn tri thức, cụ thể về: Tổng quan về trí tuệ nhân tạo, các phương pháp biểu diễn tri thức trên máy tính. Chương 3 giới thiệu về mở đầu về máy học, cụ thể là các phương pháp giúp máy tính chủ động rút ra được tri thức bằng cách quan sát các dữ liệu con người cung cấp. Sau mỗi chương đều có bài tập thực hành giúp cho bạn đọc và các bạn sinh viên dễ dàng trong việc nghiên cứu và học tập.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Nhập môn trí tuệ nhân tạo: Phần 2 - GS.TSKH. Hoàng Kiếm, ThS. Đinh Nguyễn Anh Dũng

Chöông 2 BIEÅU DIEÃN TRI THÖÙC A. TOÅNG QUAN TRÍ TUEÄ NHAÂN TAÏO I. MÔÛ ÑAÀU Cheá taïo ñöôïc nhöõng coã maùy thoâng minh nhö con ngöôøi (thaäm chí thoâng minh hôn con ngöôøi) laø moät öôùc mô chaùy boûng cuûa loaøi ngöôøi töø haøng ngaøn naêm nay. Haún baïn ñoïc coøn nhôù ñeán nhaø khoa hoïc Alan Turing cuøng nhöõng ñoùng goùp to lôùn cuûa oâng trong lónh vöïc trí tueä nhaân taïo. Naêng löïc maùy tính ngaøy caøng maïnh meõ laø moät ñieàu kieän heát söùc thuaän lôïi cho trí tueä nhaân taïo. Ñieàu naøy cho pheùp nhöõng chöông trình maùy tính aùp duïng caùc thuaät giaûi trí tueä nhaân taïo coù khaû naêng phaûn öùng nhanh vaø hieäu quaû hôn tröôùc. Söï kieän maùy tính Deep Blue ñaùnh baïi ñaïi kieän töôùng côø vua theá giôùi Casparov laø moät minh chöùng huøng hoàn cho moät böôùc tieán daøi trong coâng cuoäc nghieân cöùu veà trí tueä nhaân taïo. Tuy coù theå ñaùnh baïi ñöôïc Casparov nhöng Deep Blue laø moät coã maùy chæ bieát ñaùnh côø ! Noù thaäm chí khoâng coù ñöôïc trí thoâng minh sô ñaúng cuûa moät ñöùa beù bieát leân ba nhö nhaän dieän ñöôïc nhöõng ngöôøi thaân, khaû naêng quan saùt - - 75
nhaän bieát theá giôùi, tình caûm thöông, gheùt ... Ngaønh trí tueä nhaân taïo ñaõ coù nhöõng böôùc tieán ñaùng keå, nhöng moät trí tueä nhaân taïo thöïc söï vaãn chæ coù trong nhöõng boä phim khoa hoïc giaû töôûng cuûa Hollywood. Vaäy thì taïi sao chuùng ta vaãn nghieân cöùu veà trí tueä nhaân taïo? Ñieàu naøy cuõng töông töï nhö öôùc mô cheá taïo vaøng cuûa caùc nhaø giaû kim thuaät thôøi Trung coå, tuy chöa thaønh coâng nhöng chính quaù trình nghieân cöùu ñaõ laøm saùng toû nhieàu vaán ñeà. Maëc duø muïc tieâu toái thöôïng cuûa ngaønh TTNT laø xaây döïng moät chieác maùy coù naêng löïc tö duy töông töï nhö con ngöôøi nhöng khaû naêng hieän taïi cuûa taát caû caùc saûn phaåm TTNT vaãn coøn raát khieâm toán so vôùi muïc tieâu ñaõ ñeà ra. Tuy vaäy, ngaønh khoa hoïc môùi meû naøy vaãn ñang tieán boä moãi ngaøy vaø ñang toû ra ngaøy caøng höõu duïng trong moät soá coâng vieäc ñoøi hoûi trí thoâng minh cuûa con ngöôøi. Hình aûnh sau seõ giuùp baïn hình dung ñöôïc tình hình cuûa ngaønh trí tueä nhaân taïo. Caùc maïch ñieän töû Maùy tính trí tueä luaän lyù ñôn giaûn nhaâ n taïo ngaøy nay Thaáp Cao Baät/Taét caùc Maùy tính tieâu Maùy tính trí Con coâng taéc chuaån tueä nhaân taïo ngöôøi Hình 2.1 trong töông lai 76 - -
Tröôùc khi böôùc vaøo tìm hieåu veà trí tueä nhaân taïo, chuùng ta haõy nhaéc laïi moät ñònh nghóa ñöôïc nhieàu nhaø khoa hoïc chaáp nhaän. Muïc tieâu cuûa ngaønh khoa hoïc trí tueä nhaân taïo ? Taïo ra nhöõng chieác maùy tính coù khaû naêng nhaän thöùc, suy luaän vaø phaûn öùng. Nhaän thöùc ñöôïc hieåu laø khaû naêng quan saùt, hoïc hoûi, hieåu bieát cuõng nhö nhöõng kinh nghieäm veà theá giôùi xung quanh. Quaù trình nhaän thöùc giuùp con ngöôøi coù tri thöùc. Suy luaän laø khaû naêng vaän duïng nhöõng tri thöùc saün coù ñeå phaûn öùng vôùi nhöõng tình huoáng hay nhöõng vaán ñeà - baøi toaùn gaëp phaûi trong cuoäc soáng. Nhaän thöùc vaø suy luaän ñeå töø ñoù ñöa ra nhöõng phaûn öùng thích hôïp laø ba haønh vi coù theå noùi laø ñaëc tröng cho trí tueä cuûa con ngöôøi. (Dó nhieân coøn moät yeáu toá nöõa laø tình caûm. Nhöng chuùng ta seõ khoâng ñeà caäp ñeán ôû ñaây!). Do ñoù, cuõng khoâng coù gì ngaïc nhieân khi muoán taïo ra moät chieác maùy tính thoâng minh, ta caàn phaûi trang bò cho noù nhöõng khaû naêng naøy. Caû ba khaû naêng naøy ñeàu caàn ñeán moät yeáu toá cô baûn laø tri thöùc. Döôùi goùc nhìn cuûa taäp saùch naøy, xaây döïng trí tueä nhaân taïo laø tìm caùch bieåu dieãn tri thöùc, tìm caùch vaän duïng tri thöùc ñeå giaûi quyeát vaán ñeà vaø tìm caùch boå sung tri - - 77
thöùc baèng caùch “phaùt hieän” tri thöùc töø caùc thoâng tin saün coù (maùy hoïc). II. THOÂNG TIN, DÖÕ LIEÄU VAØ TRI THÖÙC Tri thöùc laø moät khaùi nieäm raát tröøu töôïng. Do ñoù, chuùng ta seõ khoâng coá gaéng ñöa ra moät ñònh nghóa hình thöùc chính xaùc ôû ñaây. Thay vaøo ñoù, chuùng ta haõy cuøng nhau caûm nhaän khaùi nieäm “tri thöùc” baèng caùch so saùnh noù vôùi hai khaùi nieäm khaùc laø thoâng tin vaø döõ lieäu. Nhaø baùc hoïc noåi tieáng Karan Sing ñaõ töøng noùi raèng “Chuùng ta ñang ngaäp chìm trong bieån thoâng tin nhöng laïi ñang khaùt tri thöùc”. Caâu noùi naøy laøm noåi baät söï khaùc bieät veà löôïng laãn veà chaát giöõa hai khaùi nieäm thoâng tin vaø tri thöùc. Trong ngöõ caûnh cuûa ngaønh khoa hoïc maùy tính, ngöôøi ta quan nieäm raèng döõ lieäu laø caùc con soá, chöõ caùi, hình aûnh, aâm thanh... maø maùy tính coù theå tieáp nhaän vaø xöû lyù. Baûn thaân döõ lieäu thöôøng khoâng coù yù nghóa ñoái vôùi con ngöôøi. Coøn thoâng tin laø taát caû nhöõng gì maø con ngöôøi coù theå caûm nhaän ñöôïc moät caùch tröïc tieáp thoâng qua caùc giaùc quan cuûa mình (khöùu giaùc, vò giaùc, thính giaùc, xuùc giaùc, thò giaùc vaø giaùc quan thöù 6) hoaëc giaùn tieáp thoâng qua caùc phöông tieän kyõ thuaät nhö tivi, radio, cassette,... Thoâng tin ñoái vôùi con ngöôøi luoân coù moät yù nghóa nhaát ñònh naøo ñoù. Vôùi phöông tieän maùy tính (maø cuï theå laø caùc thieát bò ñaàu ra), con ngöôøi 78 - -
seõ tieáp thu ñöôïc moät phaàn döõ lieäu coù yù nghóa ñoái vôùi mình. Neáu so veà löôïng, döõ lieäu thöôøng nhieàu hôn thoâng tin. TRI THÖÙC Möùc ñoä tröøu töôïng THOÂNG TIN DÖÕ LIEÄU Soá löôïng Hình 2.2 Cuõng coù theå quan nieäm thoâng tin laø quan heä giöõa caùc döõ lieäu. Caùc döõ lieäu ñöôïc saép xeáp theo moät thöù töï hoaëc ñöôïc taäp hôïp laïi theo moät quan heä naøo ñoù seõ chöùa ñöïng thoâng tin. Neáu nhöõng quan heä naøy ñöôïc chæ ra moät caùch roõ raøng thì ñoù laø caùc tri thöùc. Chaúng haïn : Trong toaùn hoïc : Baûn thaân töøng con soá rieâng leû nhö 1, 1, 3, 5, 2, 7, 11... laø caùc döõ lieäu. Tuy nhieân, khi ñaët chuùng laïi vôùi nhau theo traät töï nhö döôùi ñaây thì giöõa chuùng ñaõ baét ñaàu coù moät moái lieân heä Döõ lieäu : 1, 1, 2, 3, 5, 8, 13, 21, 34... - - 79
Moái lieân heä naøy coù theå ñöôïc bieåu dieãn baèng coâng thöùc sau : Un = Un-1 + Un-2. Coâng thöùc neâu treân chính laø tri thöùc. Trong vaät lyù : Baûn sau ñaây cho chuùng ta bieát soá ño veà ñieän trôû (R), ñieän theá (U) vaø cöôøng ñoä doøng ñieän (I) trong moät maïch ñieän. I U R 5 10 2 2.5 20 8 4 12 3 7.3 14.6 2 Baûn thaân nhöõng con soá trong caùc coät cuûa baûn treân khoâng coù maáy yù nghóa neáu ta taùch rôøi chuùng ta. Nhöng khi ñaët keá nhau, chuùng ñaõ cho thaáy coù moät söï lieân heä naøo ñoù. Vaø moái lieân heä naøy coù theå ñöôïc dieãn taû baèng coâng thöùc ñôn giaûn sau : U I R Coâng thöùc naøy laø tri thöùc. 80 - -
Trong cuoäc soáng haøng ngaøy : Haèng ngaøy, ngöôøi noâng daân vaãn quan saùt thaáy caùc hieän töôïng naéng, möa, raâm vaø chuoàn chuoàn bay. Raát nhieàu laàn quan saùt, hoï ñaõ coù nhaän xeùt nhö sau : Chuoàn chuoàn bay thaáp thì möa, Bay cao thì naéng, bay vöøa thì raâm. Lôøi nhaän xeùt treân laø tri thöùc. Coù quan ñieåm treân cho raèng chæ nhöõng moái lieân heä töôøng minh (coù theå chöùng minh ñöôïc) giöõa caùc döõ lieäu môùi ñöôïc xem laø tri thöùc. Coøn nhöõng moái quan heä khoâng töôøng minh thì khoâng ñöôïc coâng nhaän. ÔÛ ñaây, ta cuõng coù theå quan nieäm raèng, moïi moái lieân heä giöõa caùc döõ lieäu ñeàu coù theå ñöôïc xem laø tri thöùc, bôûi vì, nhöõng moái lieân heä naøy thöïc söï toàn taïi. Ñieåm khaùc bieät laø chuùng ta chöa phaùt hieän ra noù maø thoâi. Roõ raøng raèng “duø sao thì traùi ñaát cuõng vaãn xoay quanh maët trôøi” duø tri thöùc naøy coù ñöôïc Galileâ phaùt hieän ra hay khoâng! Nhö vaäy, so vôùi döõ lieäu thì tri thöùc coù soá löôïng ít hôn raát nhieàu. Thuaät ngöõ ít ôû ñaây khoâng chæ ñôn giaûn laø moät daáu nhoû hôn bình thöôøng maø laø söï keát tinh hoaëc coâ ñoïng laïi. Baïn haõy hình dung döõ lieäu nhö laø nhöõng ñieåm treân maët phaúng coøn tri thöùc chính laø phöông trình cuûa ñöôøng cong noái taát caû nhöõng ñieåm naøy laïi. Chæ caàn moät phöông trình ñöôøng cong ta coù theå bieåu dieãn ñöôïc voâ soá ñieåm! Cuõng vaäy, chuùng ta caàn coù nhöõng kinh nghieäm, nhaän xeùt töø haøng ñoáng soá lieäu thoáng keâ, neáu khoâng, chuùng ta seõ - - 81
ngaäp chìm trong bieån thoâng tin nhö nhaø baùc hoïc Karan Sing ñaõ caûnh baùo! Ngöôøi ta thöôøng phaân loaïi tri thöùc ra laøm caùc daïng nhö sau. Tri thöùc söï kieän : laø caùc khaúng ñònh veà moät söï kieän, khaùi nieäm naøo ñoù (trong moät phaïm vi xaùc ñònh). Caùc ñònh luaät vaät lyù, toaùn hoïc ... thöôøng ñöôïc xeáp vaøo loaïi naøy. (Chaúng haïn : maët trôøi moïc ôû ñaèng ñoâng, tam giaùc ñeàu coù ba goùc 600...) Tri thöùc thuû tuïc : thöôøng duøng ñeå dieãn taû phöông phaùp, caùc böôùc caàn tieán haønh, trình töø hay ngaén goïn laø caùch giaûi quyeát moät vaán ñeà. Thuaät toaùn, thuaät giaûi laø moät daïng cuûa tri thöùc thuû tuïc. Tri thöùc moâ taû : cho bieát moät ñoái töôïng, söï kieän, vaán ñeà, khaùi nieäm ... ñöôïc thaáy, caûm nhaän, caáu taïo nhö theá naøo (moät caùi baøn thöôøng coù boán chaân, con ngöôøi coù hai tay, hai maét...) Tri thöùc heuristic : laø moät daïng tri thöùc caûm tính. Caùc tri thöùc thuoäc loaïi naøy thöôøng coù daïng öôùc löôïng, phoûng ñoaùn, vaø thöôøng ñöôïc hình thaønh thoâng qua kinh nghieäm. 82 - -
Treân thöïc teá, raát hieám coù moät trí tueä maø khoâng caàn ñeán tri thöùc (lieäu coù theå coù moät ñaïi kieän töôùng côø vua maø khoâng bieát ñaùnh côø hoaëc khoâng bieát caùc theá côø quan troïng khoâng?). Tuy tri thöùc khoâng quyeát ñònh söï thoâng minh (ngöôøi bieát nhieàu ñònh lyù toaùn hôn chöa chaéc ñaõ giaûi toaùn gioûi hôn!) nhöng noù laø moät yeáu toá cô baûn caáu thaønh trí thoâng minh. Chính vì vaäy, muoán xaây döïng moät trí thoâng minh nhaân taïo, ta caàn phaûi coù yeáu toá cô baûn naøy. Töø ñaây ñaët ra vaán ñeà ñaàu tieân laø … Caùc phöông phaùp ñöa tri thöùc vaøo maùy tính ñöôïc goïi laø bieåu dieãn tri thöùc. III. THUAÄT TOAÙN – MOÄT PHÖÔNG PHAÙP BIEÅU DIEÃN TRI THÖÙC? Tröôùc khi traû lôøi caâu hoûi treân, baïn haõy thöû nghó xem, lieäu moät chöông trình giaûi phöông trình baäc hai coù theå ñöôïc xem laø moät chöông trình coù tri thöùc hay khoâng? ... Coù chöù ! Vaäy thì tri thöùc naèm ôû ñaâu? Tri thöùc veà giaûi phöông trình baäc hai thöïc chaát ñaõ ñöôïc maõ hoùa döôùi daïng caùc caâu leänh if..then..else trong chöông trình. Moät caùch toång quaùt, coù theå khaúng ñònh laø taát caû caùc chöông trình maùy tính ít nhieàu ñeàu ñaõ coù tri thöùc. Ñoù chính laø tri thöùc cuûa laäp trình vieân ñöôïc chuyeån thaønh caùc caâu leänh cuûa chöông trình. Baïn seõ thaéc maéc “nhö vaäy taïi sao ñöa tri thöùc vaøo maùy tính laïi laø moät vaán ñeà ? (vì töø tröôùc tôùi giôø chuùng ta ñaõ, ñang vaø seõ tieáp tuïc laøm nhö theá maø?)”. Ñuùng nhö theá thaät, nhöng vaán ñeà naèm ôû choã, caùc tri thöùc trong nhöõng chöông - - 83
trình truyeàn thoáng laø nhöõng tri thöùc “cöùng”, nghóa laø noù khoâng theå ñöôïc theâm vaøo hay ñieàu chænh moät khi chöông trình ñaõ ñöôïc bieân dòch. Muoán ñieàu chænh thì chuùng ta phaûi tieán haønh söûa laïi maõ nguoàn cuûa chöông trình (roài sau ñoù bieân dòch laïi). Maø thao taùc söûa chöông trình thì chæ coù nhöõng laäp trình vieân môùi coù theå laøm ñöôïc. Ñieàu naøy seõ laøm giaûm khaû naêng öùng duïng chöông trình (vì ña soá ngöôøi duøng bình thöôøng ñeàu khoâng bieát laäp trình). Baïn thöû nghó xem, vôùi moät chöông trình hoã trôï ra quyeát ñònh (nhö ñaàu tö coå phieáu, ñaàu tö baát ñoäng saûn chaúng haïn), lieäu ngöôøi duøng coù caûm thaáy thoaûi maùi khoâng khi muoán ñöa vaøo chöông trình nhöõng kieán thöùc cuûa mình thì anh ta phaûi choïn moät trong hai caùch laø (1) töï söûa laïi maõ chöông trình!? (2) tìm taùc giaû cuûa chöông trình ñeå nhôø ngöôøi naøy söûa laïi!?. Caû hai thao taùc treân ñeàu khoâng theå chaáp nhaän ñöôïc ñoái vôùi baát kyø ngöôøi duøng bình thöôøng naøo. Hoï caàn coù moät caùch naøo ñoù ñeå chính hoï coù theå ñöa tri thöùc vaøo maùy tính moät caùch deã daøng, thuaän tieän gioáng nhö hoï ñang ñoái thoaïi vôùi moät con ngöôøi. Ñeå laøm ñöôïc ñieàu naøy, chuùng ta caàn phaûi “meàm” hoùa caùc tri thöùc ñöôïc bieåu dieãn trong maùy tính. Xeùt cho cuøng, moïi chöông trình maùy tính ñeàu goàm hai thaønh phaàn laø caùc maõ leänh vaø döõ lieäu. Maõ leänh ñöôïc ví nhö laø phaàn cöùng cuûa chöông trình coøn döõ lieäu ñöôïc xem laø phaàn meàm (vì noù coù theå ñöôïc thay ñoåi bôûi ngöôøi duøng). Do ñoù, “meàm” hoùa tri 84 - -
thöùc cuõng ñoàng nghóa vôùi vieäc tìm caùc phöông phaùp ñeå coù theå bieåu dieãn caùc loaïi tri thöùc cuûa con ngöôøi baèng caùc caáu truùc döõ lieäu maø maùy tính coù theå xöû lyù ñöôïc. Ñaây cuõng chính laø yù nghóa cuûa thuaät ngöõ “bieåu dieãn tri thöùc”. Baïn caàn phaûi bieát raèng, ít ra laø cho ñeán thôøi ñieåm baïn ñang ñoïc cuoán saùch naøy, con ngöôøi vaãn chöa theå tìm ra moät kieåu bieåu dieãn toång quaùt cho moïi loaïi tri thöùc! Ñeåå laøm vaán ñeà maø chuùng ta ñang baøn luaän trôû neân saùng toû hôn. Chuùng ta haõy xem xeùt moät soá baøi toaùn trong phaàn tieáp theo. IV. LAØ M QUEN VÔÙ I CAÙ C H GIAÛ I QUYEÁ T VAÁ N ÑEÀ BAÈ N G CAÙ C H CHUYEÅ N GIAO TRI THÖÙ C CHO MAÙ Y TÍNH Baøi toaùn 1 : Cho hai bình roãng X vaø Y coù theå tích laàn löôït laø VX vaø VY, haõy duøng hai bình naøy ñeå ñong ra z lít nöôùc (z
Hai baøi toaùn ñaàu laø hai baøi toaùn khaù tieâu bieåu, thöôøng ñöôïc duøng ñeå minh hoïa cho neùt ñeïp cuûa phöông phaùp giaûi quyeát vaán ñeà baøi toaùn baèng caùch chuyeån giao tri thöùc cho maùy tính. Neáu söû duïng thuaät toaùn thoâng thöôøng, chuùng ta thöôøng chæ giaûi ñöôïc moät soá tröôøng hôïp cuï theå cuûa caùc baøi toaùn naøy. Thaäm chí, nhieàu ngöôøi khi môùi tieáp caän vôùi hai baøi toaùn naøy coøn khoâng tin laø noù coù theå hoaøn toaøn ñöôïc giaûi moät caùch toång quaùt bôûi maùy tính! Baøi toaùn soá 3 laø moät minh hoïa ñeïp maét cho kyõ thuaät giaûi quyeát vaán ñeà “vó moâ”, nghóa laø ta chæ caàn moâ taû caùc böôùc giaûi quyeát ôû möùc toång quaùt cho maùy tính maø khoâng caàn ñi vaøo caøi ñaët cuï theå. Baøi toaùn 1 seõ ñöôïc giaûi quyeát baèng caùch söû duïng caùc luaät daãn xuaát (luaät sinh). Baøi toaùn 2 seõ ñöôïc giaûi quyeát baèng maïng ngöõ nghóa vaø baøi toaùn 3 seõ giaûi quyeát baèng coâng cuï frame. ÔÛ ñaây chuùng ta cuøng nhau tìm hieåu caùch giaûi baøi toaùn ñaàu tieân. Hai baøi toaùn keá tieáp seõ ñöôïc giaûi quyeát laàn löôït ôû caùc muïc sau. Vôùi moät tröôøng hôïp cuï theå cuûa baøi toaùn 1, nhö VX = 5 vaø VY = 7 vaø z = 4. Sau moät thôøi gian tính toaùn, baïn coù theå seõ ñöa ra moät quy trình ñoå nöôùc ñaïi loaïi nhö : - Muùc ñaày bình 7 - Truùt heát qua bình 5 cho ñeán khi 5 ñaày. - Ñoå heát nöôùc trong bình 5 - Ñoå heát nöôùc coøn laïi töø bình 7 sang bình 5 86 - -
- Muùc ñaày bình 7 - Truùt heát qua bình 5 cho ñeán khi bình 5 ñaày. - Phaàn coøn laïi chính laø soá nöôùc caàn ñong. Tuy nhieân, vôùi nhöõng soá lieäu khaùc, baïn phaûi “maøy moø” laïi töø ñaàu ñeå tìm ra quy trình ñoå nöôùc. Cöù theá, moãi moät tröôøng hôïp seõ coù moät caùch ñoå nöôùc hoaøn toaøn khaùc nhau. Nhö vaäy, neáu coù moät ai ñoù yeâu caàu baïn ñöa ra moät caùch laøm toång quaùt thì chính baïn cuõng seõ luùng tuùng (dó nhieân, ngoaïi tröø tröôøng hôïp baïn ñaõ bieát tröôùc caùch giaûi theo tri thöùc maø chuùng ta saép söûa tìm hieåu ôû ñaây!). Ñeán ñaây, baïn haõy bình taâm kieåm laïi caùch thöùc baïn tìm kieám lôøi giaûi cho moät tröôøng hôïp cuï theå. Vì chöa tìm ra moät quy taéc cuï theå naøo, baïn seõ thöïc hieän moät loaït caùc thao taùc “caûm tính” nhö ñong ñaày moät bình, truùt moät bình naøy sang bình kia, ñoå heát nöôùc trong moät bình ra... vöøa laøm vöøa nhaåm tính xem caùch laøm naøy coù theå ñi ñeán keát quaû hay khoâng. Sau nhieàu laàn thí nghieäm, raát coù theå baïn seõ ruùt ra ñöôïc moät soá kinh nghieäm nhö “khi bình 7 ñaày nöôùc maø bình 5 chöa ñaày thì haõy ñoå noù sang bình 5 cho ñeán khi bình 5 ñaày”... Vaäy thì taïi sao baïn laïi khoâng thöû “truyeàn” nhöõng kinh nghieäm naøy cho maùy tính vaø ñeå cho maùy tính “maøy moø” tìm caùc thao taùc cho chuùng ta? Ñieàu naøy hoaøn toaøn coù lôïi, vì maùy tính coù khaû naêng “maøy moø” hôn haún chuùng ta! Neáu nhöõng “kinh nghieäm” maø chuùng ta cung caáp cho maùy tính khoâng giuùp chuùng ta tìm ñöôïc lôøi giaûi, chuùng - - 87
ta seõ thay theá noù baèng nhöõng kinh nghieäm khaùc vaø laïi tieáp tuïc ñeå maùy tính tìm kieám lôøi giaûi! Chuùng ta haõy phaùt bieåu laïi baøi toaùn moät caùch hình thöùc hôn. Khoâng laøm maát tính toång quaùt, ta luoân coù theå giaû söû raèng VX < VY. Goïi löôïng nöôùc chöùa trong bình X laø x (0
(L1) Neáu bình X ñaày thì ñoå heát nöôùc trong bình X ñi. (L2) Neáu bình Y roãng thì ñoå ñaày nöôùc vaøo bình Y. (L3) Neáu bình X khoâng ñaày vaø bình Y khoâng roãng thì haõy truùt nöôùc từ bình Y sang bình X (cho ñeán khi bình X ñaày hoaëc bình Y heát nöôùc). Treân thöïc teá, luùc ñaàu ñeå giaûi tröôøng hôïp toång quaùt cuûa baøi toaùn naøy, ngöôøi ta ñaõ duøng ñeán hôn 15 luaät (kinh nghieäm) khaùc nhau. Tuy nhieân, sau naøy, ngöôøi ta ñaõ ruùt goïn laïi chæ coøn ba luaät nhö treân. Baïn coù theå deã daøng chuyeån ñoåi caùch giaûi naøy thaønh chöông trình nhö sau : ... x := 0; y := 0; WHILE ( (x z) AND (yz) ) DO BEGIN IF (x = Vx) THEN x := 0; IF (y = 0) THEN (y:= Vy); IF (y > 0) THEN BEGIN k:= min(Vx - x, y); x := x + k; y := y - k; END; END; ... Thöû “chaïy” chöông trình treân vôùi soá lieäu cuï theå laø : VX = 3, VY = 4 vaø z = 2 Ban ñaàu : x = 0, y = 0 Luaät (L2) -> x = 0, y = 4 Luaät (L3) -> x = 3, y = 1 - - 89
Luaät (L1) -> x = 0, y = 1 Luaät (L3) -> x = 1, y = 0 Luaät (L2) -> x = 1, y = 4 Luaät (L3) -> x = 3, y = 2 Ba luaät maø chuùng ta ñaõ caøi ñaët trong chöông trình ôû treân ñöôïc goïi laø cô sôû tri thöùc. Coøn caùch thöùc tìm kieám lôøi giaûi baèng caùch duyeät tuaàn töï töøng luaät vaø aùp duïng noù ñöôïc goïi laø ñoäng cô suy dieãn. Chuùng ta seõ ñònh nghóa chính xaùc hai thuaät ngöõ naøy ôû cuoái muïc. Ngöôøi ta ñaõ chöùng minh ñöôïc raèng, baøi toaùn ñong nöôùc chæ coù lôøi giaûi khi soá nöôùc caàn ñong laø moät boäi soá cuûa öôùc soá chung lôùn nhaát cuûa theå tích hai bình. z = n  USCLN(VX, VY) (vôùi n nguyeân döông) Caùch giaûi quyeát vaán ñeà theo kieåu naøy khaùc so vôùi caùch giaûi baèng thuaät toaùn thoâng thöôøng laø chuùng ta khoâng ñöa ra moät trình töï giaûi quyeát vaán ñeà cuï theå maø chæ ñöa ra caùc quy taéc chung chung (döôùi daïng caùc luaät), maùy tính seõ döïa vaøo ñoù (aùp duïng caùc luaät) ñeå töï xaây döïng moät quy trình giaûi quyeát vaán ñeà. Ñieàu naøy cuõng gioáng nhö vieäc chuùng ta giaûi toaùn baèng caùch ñöa ra caùc ñònh lyù, quy taéc lieân quan ñeán baøi toaùn maø khoâng caàn phaûi chæ ra caùch giaûi cuï theå. Vaäy thì ñieåm thuù vò naèm ôû ñieåm naøo? Baïn seõ coù theå caûm thaáy raèng chuùng ta vaãn ñang duøng tri thöùc “cöùng” ! (vì caùc tri thöùc vaãn laø caùc caâu leänh IF ñöôïc caøi saün trong chöông trình). Thöïc ra thì chöông trình cuûa chuùng ta ñaõ 90 - -
“meàm” hôn moät tí roài ñaáy. Neáu khoâng tin, caùc baïn haõy quan saùt phieân baûn keá tieáp cuûa chöông trình naøy. FUNCTION DK(L INTEGER):BOOLEAN; BEGIN CASE L OF 1 : DK := (x = Vx); 2 : DK := (y = 0); 3 : DK := (y>0); END; END; PROCEDURE ThiHanh(L INTEGER):BOOLEAN; BEGIN CASE L OF 1 : x := 0; 2: y := Vy; 3 : BEGIN k := min(Vx-x,y); x := x+k; y := y-k; END; END; END; CONST SO_LUAT = 3; BEGIN WHILE (xz) AND (yz) DO BEGIN FOR i:=1 TO SO_LUAT DO IF DK(L) THEN ThiHanh(L); END; END. Ñoaïn chöông trình chính cuõng thi haønh baèng caùch laàn löôït xeùt qua ba leänh IF nhö chöông trình ñaàu tieân. Tuy nhieân, ôû ñaây, bieåu thöùc ñieàu kieän ñöôïc thay theá baèng haøm DK vaø caùc haønh ñoäng öùng vôùi ñieàu kieän ñaõ ñöôïc thay theá - - 91
baèng thuû tuïc ThiHanh. Tính chaát “meàm” hôn cuûa chöông trình naøy theå hieän ôû choã, neáu muoán boå sung “tri thöùc”, ta chæ phaûi ñieàu chænh laïi caùc haøm DK vaø ThiHanh maø khoâng caàn phaûi söûa laïi chöông trình chính. Baây giôø haõy giaû söû raèng ta ñaõ coù haøm vaø thuû tuïc ñaëc bieät sau : FUNCTION GiaTriBool(DK : String) : BOOLEAN; PROCEDURE ThucHien(ThaoTac : String) ; Haøm GiaTriBool nhaän vaøo moät chuoãi ñieàu kieän, noù seõ phaân tích chuoãi, tính toaùn roài traû ra giaù trò BOOLEAN cuûa bieåu thöùc naøy. Ví duï : GiaTriBoolean(‘6
DSLuat ARRAY [1..SO_LUAT] OF Luat; VAR CacLuat DSLuat; PROCEDURE KhoiDong; BEGIN CacLuat[1].DK := ‘x = Vx’; CacLuat[2].DK := ‘y = 0’; CacLuat[3].DK := ‘y>0’; CacLuat[1].ThaoTac := ‘x:=0’; CacLuat[2].ThaoTac:= ‘y:=Vy’; CacLuat[3].ThaoTac:= ‘k:=min(Vx-x,y), x:=x+k, y:=y-k’; END; BEGIN WHILE (xz) AND (yz) DO BEGIN FOR i:=1 TO SO_LUAT DO IF GiaTriBoolean(CacLuat[i].DK) THEN ThucHien(CacLuat[i].ThaoTac); END; END. Chuùng ta taïm cho raèng trong quaù trình chöông trình thi haønh, ta coù theå deã daøng thay ñoåi soá phaàn töû maûng CacLuat (caùc ngoân ngöõ laäp trình sau naøy nhö Visual C++, Delphi ñeàu cho pheùp ñieàu naøy). Vôùi chöông trình naøy, khi muoán söûa ñoåi “tri thöùc”, baïn chæ caàn thay ñoåi giaù trò maûng Luat laø xong. Tuy nhieân, ngöôøi duøng vaãn gaëp khoù khaên khi muoán boå sung hoaëc hieäu chænh tri thöùc. Hoï caàn phaûi nhaäp caùc chuoãi ñaïi loaïi nhö ‘x=0’ hoaëc ‘k:=min(Vx-x,y)’ ...Caùc chuoãi naøy, - - 93
tuy coù yù nghóa ñoái vôùi chöông trình nhöng vaãn coøn khaù xa laï ñoái vôùi ngöôøi duøng bình thöôøng. Chuùng ta caàn giaûm bôùt “khoaûng caùch” naøy laïi baèng caùch ñöa ra nhöõng chuoãi ñieàu kieän hoaëc thao taùc coù yù nghóa tröïc tieáp ñoái vôùi ngöôøi duøng. Chöông trình seõ coù chuyeån ñoåi laïi caùc ñieàu kieän vaø thao taùc naøy sang daïng phuø hôïp vôùi chöông trình. Ñeå laøm ñöôïc ñieàu treân. Chuùng ta caàn phaûi lieät keâ ñöôïc caùc traïng thaùi vaø thao taùc cô baûn cuûa baøi toaùn naøy. Sau ñaây laø moät soá traïng thaùi vaø thao taùc cô baûn. Traïng thaùi cô baûn Bình X ñaày, Bình X roãng, Bình X khoâng roãng, Bình X coù n lít nöôùc. Thao taùc Ñoå heát nöôùc trong bình, Ñoå ñaày nöôùc trong bình, Ñoå nöôùc töø bình A sang bình B cho ñeán khi B ñaày hoaëc A roãng. Löu yù raèng ta khoâng theå coù thao taùc “Ñoå n lít nöôùc töø A sang B” vì baøi toaùn ñaõ giaû ñònh raèng caùc bình ñeàu khoâng coù vaïch chia, hôn nöõa neáu ta bieát caùch ñoå n lít nöôùc töø A sang B thì lôøi giaûi baøi toaùn trôû thaønh quaù ñôn giaûn. “Muùc ñaày X” “Ñoå z lít nöôùc töø X sang Y” 94 - -