Thuật toán và giải thuật - Hoàng Kiếm Part 7

Chia sẻ: Mr Yukogaru | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

75
lượt xem 17
download

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

Tri thức là một khai niệm rất trừu tượng. Do đó , chúng ta sẽ cố gắng không đưa ra một định nghĩa hình thức chính xác ở đây . thay vào đó chúng ta sẽ cùng nhau cảm nhận khía niêm tri thức bằng cách so sánh hai khía niệm là thông tin và dữ liệu

Chủ đề:

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

Lưu

Nội dung Text: Thuật toán và giải thuật - Hoàng Kiếm Part 7

II. THÔNG TIN, D LI U VÀ TRI TH C Tri th c là m t khái ni m r t tr u tư ng. Do ó, chúng ta s không c g ng ưa ra m t nh nghĩa hình th c chính xác ây. Thay vào ó, chúng ta hãy cùng nhau c m nh n khái ni m "tri th c" b ng cách so sánh nó v i hai khái ni m khác là thông tin và d li u. Nhà bác h c n i ti ng Karan Sing ã t ng nói r ng "Chúng ta ang ng p chìm trong bi n thông tin nhưng l i ang khát tri th c". Câu nói này làm n i b t s khác bi t v lư ng l n v ch t gi a hai khái ni m thông tin và tri th c. Trong ng c nh c a ngành khoa h c máy tính, ngư i ta quan ni m r ng d li u là các con s , ch cái, hình nh, âm thanh... mà máy tính có th ti p nh n và x lý. B n thân d li u thư ng không có ý nghĩa i v i con ngư i. Còn thông tin là t t c nh ng gì mà con ngư i có th c m nh n ư c m t cách tr c ti p thông qua các giác quan c a mình (kh u giác, v giác, thính giác, xúc giác, th giác và giác quan th 6) ho c gián ti p thông qua các phương ti n k thu t như tivi, radio, cassette,... Thông tin i v i con ngư i luôn có m t ý nghĩa nh t nh nào ó. V i phương ti n máy tính (mà c th là các thi t b u ra), con ngư i s ti p thu ư c m t ph n d li u có ý nghĩa i v i mình. N u so v lư ng, d li u thư ng nhi u hơn thông tin. Cũng có th quan ni m thông tin là quan h gi a các d li u. Các d li u ư c s p x p theo m t th t ho c ư c t p h p l i theo m t quan h nào ó s ch a ng thông tin. N u nh ng quan h này ư c ch ra m t cách rõ ràng thì ó là các tri th c. Ch ng h n : Trong toán h c : B n thân t ng con s riêng l như 1, 1, 3, 5, 2, 7, 11, ... là các d li u. Tuy nhiên, khi t chúng l i v i nhau theo tr t t như dư i ây thì gi a chúng ã b t u có m t m i liên h D li u : 1, 1, 2, 3, 5, 8, 13, 21, 34, .... M i liên h này có th ư c bi u di n b ng công th c sau : Un = Un-1 + Un-2. Công th c nêu trên chính là tri th c. Trong v t lý : B n sau ây cho chúng ta bi t s ov i n tr (R), i n th (U) và cư ng dòng i n (I) trong m t m ch i n. I U R 5 10 2 2.5 20 8 43 Sưu t m b i: www.daihoc.com.vn
4 12 3 7.3 14.6 2 B n thân nh ng con s trong các c t c a b n trên không có m y ý nghĩa n u ta tách r i chúng ta. Nhưng khi t k nhau, chúng ã cho th y có m t s liên h nào ó. Và m i liên h này có th ư c di n t b ng công th c ơn gi n sau : Công th c này là tri th c. Trong cu c s ng hàng ngày : H ng ngày, ngư i nông dân v n quan sát th y các hi n tư ng n ng, mưa, râm và chu n chu n bay. R t nhi u l n quan sát, h ã có nh n xét như sau : Chu n chu n bay th p thì mưa, bay cao thì n ng, bay v a thì râm. L i nh n xét trên là tri th c. Có quan i m trên cho r ng ch nh ng m i liên h tư ng minh (có th ch ng minh ư c) gi a các d li u m i ư c xem là tri th c. Còn nh ng m i quan h không tư ng minh thì không ư c công nh n. ây, ta cũng có th quan ni m r ng, m i m i liên h gi a các d li u u có th ư c xem là tri th c, b i vì, nh ng m i liên h này th c s t n t i. i m khác bi t là chúng ta chưa phát hi n ra nó mà thôi. Rõ ràng r ng "dù sao thì trái t cũng v n xoay quanh m t tr i" dù tri th c này có ư c Galilê phát hi n ra hay không! Như v y, so v i d li u thì tri th c có s lư ng ít hơn r t nhi u. Thu t ng ít ây không ch ơn gi n là m t d u nh hơn bình thư ng mà là s k t tinh ho c cô ng l i. B n hãy hình dung d li u như là nh ng i m trên m t ph ng còn tri th c chính là phương trình c a ư ng cong n i t t c nh ng i m này l i. Ch c n m t phương trình ư ng cong ta có th bi u di n ư c vô s i m!. Cũng v y, chúng ta c n có nh ng kinh nghi m, nh n xét t hàng ng s li u th ng kê, n u không, chúng ta s ng p chìm trong bi n thông tin như nhà bác h c Karan Sing ã c nh báo!. Ngư i ta thư ng phân lo i tri th c ra làm các d ng như sau : Tri th c s ki n : là các kh ng nh v m t s ki n, khái ni m nào ó (trong m t ph m vi xác nh). Các nh lu t v t lý, toán h c, ... thư ng ư c x p vào lo i này. (Ch ng h n : m t tr i m c ng ông, tam giác u có 3 góc 600, ...) Tri th c th t c : thư ng dùng di n t phương pháp, các bư c c n ti n hành, trình t hay ng n g n là cách gi i quy t m t v n . Thu t toán, thu t gi i là m t d ng c a tri th c th t c. 44 Sưu t m b i: www.daihoc.com.vn
Tri th c mô t : cho bi t m t i tư ng, s ki n, v n , khái ni m, ... ư c th y, c m nh n, c u t o như th nào (m t cái bàn thư ng có 4 chân, con ngư i có 2 tay, 2 m t,...) Tri th c Heuristic : là m t d ng tri th c c m tính. Các tri th c thu c lo i này thư ng có d ng ư c lư ng, ph ng oán, và thư ng ư c hình thành thông qua kinh nghi m. Trên th c t , r t hi m có m t trí tu mà không c n n tri th c (li u có th có m t i ki n tư ng c vua mà không bi t ánh c ho c không bi t các th c quan tr ng không?). Tuy tri th c không quy t nh s thông minh (ngư i bi t nhi u nh lý toán hơn chưa ch c ã gi i toán gi i hơn!) nhưng nó là m t y u t cơ b n c u thành trí thông minh. Chính vì v y, mu n xây d ng m t trí thông minh nhân t o, ta c n ph i có y u t cơ b n này. T ây t ra v n u tiên là … Các phương pháp ưa tri th c vào máy tính ư c g i là bi u di n tri th c. III. THU T TOÁN – M T PHƯƠNG PHÁP BI U DI N TRI TH C? Trư c khi tr l i câu h i trên, b n hãy th nghĩ xem, li u m t chương trình gi i phương trình b c 2 có th ư c xem là m t chương trình có tri th c hay không? ... Có ch ! V y thì tri th c n m âu? Tri th c v gi i phương trình b c hai th c ch t ã ư c mã hóa dư i d ng các câu l nh if..then..else trong chương trình. M t cách t ng quát, có th kh ng nh là t t c các chương trình máy tính ít nhi u u ã có tri th c. ó chính là tri th c c a l p trình viên ư c chuy n thành các câu l nh c a chương trình. B n s th c m c "như v y t i sao ưa tri th c vào máy tính l i là m t v n ? (vì t trư c t i gi chúng ta ã, ang và s ti p t c làm như th mà?)". úng như th th t, nhưng v n n m ch , các tri th c trong nh ng chương trình truy n th ng là nh ng tri th c "c ng", nghĩa là nó không th ư c thêm vào hay i u ch nh m t khi chương trình ã ư c biên d ch. Mu n i u ch nh thì chúng ta ph i ti n hành s a l i mã ngu n c a chương trình (r i sau ó biên d ch l i). Mà thao tác s a chương trình thì ch có nh ng l p trình viên m i có th làm ư c. i u này s làm gi m kh năng ng d ng chương trình (vì a s ngư i dùng bình thư ng u không bi t l p trình). B n th nghĩ xem, v i m t chương trình h tr ra quy t nh (như u tư c phi u, u tư b t ng s n ch ng h n), li u ngư i dùng có c m th y tho i mái không khi mu n ưa vào chương trình nh ng ki n th c c a mình thì anh ta ph i ch n m t trong hai cách là (1) t s a l i mã chương trình!? (2) tìm tác gi c a chương trình nh ngư i này s a l i!?. C hai thao tác trên u không th ch p nh n ư c iv i b t kỳ ngư i dùng bình thư ng nào. H c n có m t cách nào ó chính h có th ưa tri th c vào máy tính m t cách d dàng, thu n ti n gi ng như h ang i tho i v i m t con ngư i. làm ư c i u này, chúng ta c n ph i "m m" hóa các tri th c ư c bi u di n trong máy tính. Xét cho cùng, m i chương trình máy tính u g m hai thành ph n là các mã l nh và d li u. Mã l nh ư c ví như là ph n c ng c a chương trình còn d li u ư c xem là ph n m m (vì nó có th ư c thay i b i ngư i dùng). Do ó, "m m" hóa tri th c cũng ng nghĩa v i vi c tìm các phương pháp có th bi u di n các lo i tri th c c a con ngư i b ng các c u trúc d li u mà máy tính có th x lý ư c. ây cũng chính là ý nghĩa c a thu t ng "bi u di n tri th c". 45 Sưu t m b i: www.daihoc.com.vn
B n c n ph i bi t r ng, ít ra là cho n th i i m b n ang c cu n sách này, con ngư i v n chưa th tìm ra m t ki u bi u di n t ng quát cho m i lo i tri th c! làm v n mà chúng ta ang bàn lu n tr nên sáng t hơn. Chúng ta hãy xem xét m t s bài toán trong ph n ti p theo. IV. LÀM QUEN V I CÁCH GI I QUY T V N B NG CÁCH CHUY N GIAO TRI TH C CHO MÁY TÍNH Bài toán 1 : Cho hai bình r ng X và Y có th tích l n lư t là VX và VY, hãy dùng hai bình này ong ra z lít nư c (z
Như v y, n u có m t ai ó yêu c u b n ưa ra m t cách làm t ng quát thì chính b n cũng s lúng túng (dĩ nhiên, ngo i tr trư ng h p b n ã bi t trư c cách gi i theo tri th c mà chúng ta s p s a tìm hi u ây!). n ây, b n hãy bình tâm ki m l i cách th c b n tìm ki m l i gi i cho m t trư ng h p c th . Vì chưa tìm ra m t quy t c c th nào, b n s th c hi n m t lo t các thao tác "c m tính" như ong y m t bình, trút m t bình này sang bình kia, h t nư c trong m t bình ra... v a làm v a nh m tính xem cách làm này có th i n k t qu hay không. Sau nhi u l n thí nghi m, r t có th b n s rút ra ư c m t s kinh nghi m như "khi bình 7 y nư c mà bình 5 chưa y thì hãy nó sang bình 5 cho n khi bình 5 y"... V y thì t i sao b n l i không th "truy n" nh ng kinh nghi m này cho máy tính và cho máy tính "mày mò" tìm các thao tác cho chúng ta? i u này hoàn toàn có l i, vì máy tính có kh năng "mày mò" hơn h n chúng ta! N u nh ng "kinh nghi m" mà chúng ta cung c p cho máy tính không giúp chúng ta tìm ư c l i gi i, chúng ta s thay th nó b ng nh ng kinh nghi m khác và l i ti p t c máy tính tìm ki m l i gi i! Chúng ta hãy phát bi u l i bài toán m t cách hình th c hơn. Không làm m t tính t ng quát, ta luôn có th gi s r ng VX
... 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 "ch y" chương trình trên v i s li u c th là : Vx = 3, Vy = 4 và z = 2 Ban u : x = 0, y = 0 Lu t (L2) -> x = 0, y = 4 Lu t (L3) -> x = 3, y = 1 Lu t (L1) -> x = 0, y = 1 Lu t (L3) -> x = 1, y = 0 Lu t (L2) -> x = 1, y = 4 Lu t (L3) -> x = 3, y = 2 3 lu t mà chúng ta ã cài t trong chương trình trên ư c g i là cơ s tri th c. Còn cách th c tìm ki m l i gi i b ng cách duy t tu n t t ng lu t và áp d ng nó ư c g i là ng cơ suy di n. Chúng ta s nh nghĩa chính xác hai thu t ng này cu i m c. Ngư i ta ã ch ng minh ư c r ng, bài toán ong nư c ch có l i gi i khi s nư c c n ong là m t b i s c a ư c s chung l n nh t c a th tích hai bình. 48 Sưu t m b i: www.daihoc.com.vn
z = n  USCLN(VX, VY) (v i n nguyên dương) Cách gi i quy t v n theo ki u này khác so v i cách gi i b ng thu t toán thông thư ng là chúng ta không ưa ra m t trình t gi i quy t v n c th mà ch ưa ra các quy t c chung chung (dư i d ng các lu t), máy tính s d a vào ó (áp d ng các lu t) t xây d ng m t quy trình gi i quy t v n . i u này cũng gi ng như vi c chúng ta gi i toán b ng cách ưa ra các nh lý, quy t c liên quan n bài toán mà không c n ph i ch ra cách gi i c th . V y thì i m thú v n m i m nào? B n s có th c m th y r ng chúng ta v n ang dùng tri th c "c ng" ! (vì các tri th c v n là các câu l nh IF ư c cài s n trong chương trình). Th c ra thì chương trình c a chúng ta ã "m m" hơn m t tí r i y. N u không tin, các b n hãy quan sát phiên b n k ti p c a chương trình nà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; 49 Sưu t m b i: www.daihoc.com.vn