[Giáo trình Toán rời rạc] - Chương1 - Thuật Toán

Tài liệu " [Giáo trình Toán rời rạc] - Chương1 - Thuật Toán " mang tính chất tham khảo, giúp ích cho các bạn tự học, ôn thi, với phương pháp học hay, thú vị, rèn luyện kỹ năng giải đề, nâng cao vốn kiến thức cho các bạn trong các kỳ thi sắp tới. Tác giả hy vọng tài liệu này sẽ giúp ích cho các bạn.
Nội dung trích xuất từ tài liệu:
[Giáo trình Toán rời rạc] - Chương1 - Thuật Toán http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p CHƯƠNG I: THU T TOÁN1.1. KHÁI NI M THU T TOÁN.1.1.1. M ñ u: Có nhi u l p bài toán t ng quát xu t hi n trong toán h c r i r c. Ch ng h n, chom t dãy các s nguyên, tìm s l n nh t; cho m t t p h p, li t kê các t p con c a nó; chot p h p các s nguyên, x p chúng theo th t tăng d n; cho m t m ng, tìm ñư ng ñing n nh t gi a hai ñ nh c a nó. Khi ñư c giao cho m t bài toán như v y thì vi c ñ utiên ph i làm là xây d ng m t mô hình d ch bài toán ñó thành ng c nh toán h c. Cácc u trúc r i r c ñư c dùng trong các mô hình này là t p h p, dãy, hàm, hoán v , quan h ,cùng v i các c u trúc khác như ñ th , cây, m ng - nh ng khái ni m s ñư c nghiên c u các chương sau. L p ñư c m t mô hình toán h c thích h p ch là m t ph n c a quá trình gi i. ðhoàn t t quá trình gi i, còn c n ph i có m t phương pháp dùng mô hình ñ gi i bài toánt ng quát. Nói m t cách lý tư ng, cái ñư c ñòi h i là m t th t c, ñó là dãy các bư cd n t i ñáp s mong mu n. M t dãy các bư c như v y, ñư c g i là m t thu t toán. Khi thi t k và cài ñ t m t ph n m m tin h c cho m t v n ñ nào ñó, ta c n ph iñưa ra phương pháp gi i quy t mà th c ch t ñó là thu t toán gi i quy t v n ñ này. Rõràng r ng, n u không tìm ñư c m t phương pháp gi i quy t thì không th l p trìnhñư c. Chính vì th , thu t toán là khái ni m n n t ng c a h u h t các lĩnh v c c a tinh c.1.1.2. ð nh nghĩa: Thu t toán là m t b ng li t kê các ch d n (hay quy t c) c n th chi n theo t ng bư c xác ñ nh nh m gi i m t bài toán ñã cho. Thu t ng “Algorithm” (thu t toán) là xu t phát t tên nhà toán h c R p Al-Khowarizmi. Ban ñ u, t algorism ñư c dùng ñ ch các quy t c th c hi n các phép tínhs h c trên các s th p phân. Sau ñó, algorism chuy n thành algorithm vào th k 19.V i s quan tâm ngày càng tăng ñ i v i các máy tính, khái ni m thu t toán ñã ñư c chom t ý nghĩa chung hơn, bao hàm c các th t c xác ñ nh ñ gi i các bài toán, ch khôngph i ch là th t c ñ th c hi n các phép tính s h c. Có nhi u cách trình bày thu t toán: dùng ngôn ng t nhiên, ngôn ng lưu ñ (sơñ kh i), ngôn ng l p trình. Tuy nhiên, m t khi dùng ngôn ng l p trình thì ch nh ngl nh ñư c phép trong ngôn ng ñó m i có th dùng ñư c và ñi u này thư ng làm cho smô t các thu t toán tr nên r i r m và khó hi u. Hơn n a, vì nhi u ngôn ng l p trìnhñ u ñư c dùng r ng rãi, nên ch n m t ngôn ng ñ c bi t nào ñó là ñi u ngư i ta khôngmu n. Vì v y ñây các thu t toán ngoài vi c ñư c trình bày b ng ngôn ng t nhiêncùng v i nh ng ký hi u toán h c quen thu c còn dùng m t d ng gi mã ñ mô t thu t 4http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t ptoán. Gi mã t o ra bư c trung gian gi a s mô t m t thu t toán b ng ngôn ng thôngthư ng và s th c hi n thu t toán ñó trong ngôn ng l p trình. Các bư c c a thu t toánñư c ch rõ b ng cách dùng các l nh gi ng như trong các ngôn ng l p trình.Thí d 1: Mô t thu t toán tìm ph n t l n nh t trong m t dãy h u h n các s nguyên.a) Dùng ngôn ng t nhiên ñ mô t các bư c c n ph i th c hi n: 1. ð t giá tr c c ñ i t m th i b ng s nguyên ñ u tiên trong dãy. (C c ñ i t mth i s là s nguyên l n nh t ñã ñư c ki m tra m t giai ño n nào ñó c a th t c.) 2. So sánh s nguyên ti p sau v i giá tr c c ñ i t m th i, n u nó l n hơn giá trc c ñ i t m th i thì ñ t c c ñ i t m th i b ng s nguyên ñó. 3. L p l i bư c trư c n u còn các s nguyên trong dãy. 4. D ng khi không còn s nguyên nào n a trong dãy. C c ñ i t m th i ñi mnày chính là s nguyên l n nh t c a dãy.b) Dùng ño n gi mã:procedure max (a1, a2, ..., an: integers) max:= a1 for i:= 2 to n if max http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t pki m tra chính t c a các t , tìm ki m các t này trong m t cu n t ñi n, mà t ñi nch ng qua cũng là m t b ng li t kê s p th t c a các t . Các bài toán thu c lo i nàyñư c g i là các bài toán tìm ki m. Bài toán tìm ki m t ng quát ñư c mô t như sau: xác ñ nh v trí c a ph n t xtrong m t b ng li t kê các ph n t phân bi t a1, a2, ..., an ho c xác ñ nh r ng nó không cóm t trong b ng li t kê ñó. L i gi i c a bài toán trên là v trí c a s h ng c a b ng li t kêcó giá tr b ng x (t c là i s là nghi m n u x=ai và là 0 n u x không có m t trong b ngli t kê).1.2.2. Thu t toán tìm ki m tuy n tính: Tìm ki m tuy n tính hay tìm ki m tu n t làb t ñ u b ng vi c so sánh x v i a1; khi x=a1, nghi m là v trí a1, t c là 1; khi x≠a1, sosánh x v i a2. N u x=a2, nghi m là v trí c a a2, t c là 2. Khi x≠a2, so sánh x v i a3. Ti pt c quá trình này b ng cách tu n t so sánh x v i m i s h ng c a b ng li t kê cho t ikhi tìm ñư c s h ng b ng x, khi ñó nghi m là v trí c a s h ng ñó. N u toàn b ng li tkê ñã ñư c ki m tra mà không xác ñ nh ñư c v trí c a x, thì nghi m là 0. Gi mã ñ i ...