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

59
lượt xem 16
download

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

Mô tả tài liệu

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

CÓ THỂ BẠN MUỐN DOWNLOAD