Chương 1: Giải thuật Chương 2: Danh sách Chương 3: Mô hình cây và đồ thị Chương 4: Các giải thuật sắp xếp và tìm kiếm Mặc dù có nhiều cố gắng, nhưng trong quá trình biên soạn, biên tập và in ấn khó tránh khỏi những thiếu sót. Chúng tôi rất mong nhận được sự đóng góp ý kiến từ phía các thầy cô và bạn đọc để hoàn thiện giáo trình hơn! Xin trân trọng cảm ơn! Hà Nội, ngày……tháng……năm……… Tham gia biên so¿n Trần Thá M¢ - Chủ biên v Tên môn hác: CÄU TRÚC Dþ LIàU VÀ GIÀI THU¾T Mã môn hác: MH13 Thßi gian thāc hián môn hác: 60 giß; (Lý thuyÁt: 30 giß; Thāc hành, thí nghiệm, thÁo luÁn, bài tÁp: 27giß; Kiểm tra:3 giß) I. Vß trí, tính chÃt của môn hác: - Vá trí: Môn Cấu trúc dÿ liệu và giÁi thuÁt là môn học bÃt buác thuác nhóm các môn học, mô đun đào t¿o ngành Công nghệ thông tin. - Tính chất: Môn Cấu trúc dÿ liệu đ°ợc ứng dụng ráng rãi trong các lĩnh vāc tin học, góp phần nâng cao chất l°ợng đào t¿o nghề và phát triển nguán nhân lāc trong giai đo¿n mới.
Mÿc tiêu môn hác: - Về kiÁn thức: Các khái niệm c¢ bÁn về giÁi thuÁt, đánh giá đá phức t¿p của giÁi thuÁt. Các kiểu cấu trúc dÿ liệu thông dụng và mát sß giÁi thuÁt trên các kiểu cấu trúc dÿ liệu đó. - Về kỹ năng: ThiÁt kÁ đ°ợc mát sß giÁi thuÁt sÃp xÁp , tìm kiÁm. VÁn dụng các kiểu cấu trúc dÿ liệu thông dụng và các giÁi thuÁt để giÁi mát sß bài toán thāc tiễn.
- Về năng lāc tā chủ và trách nhiệm: Tích cāc nghiên cứu nhÿng kiÁn thức về cấu trúc dÿ liệu, giÁi thuÁt. Rèn luyện ý thức chấp hành kỷ luÁt lao đáng, phát huy tinh thần chủ đáng nghiên cứu, học hỏi, sáng t¿o trong học tÁp và làm việc. vi CH¯¡NG 1: GIÀI THU¾T Mÿc tiêu bài hác 1. Cung cấp cho ng°ßi học các kiÁn thức c¢ bÁn về c¢ bÁn về giÁi thuÁt: các đặc tr°ng giÁi thuÁt, ngôn ngÿ diễn đ¿t giÁi thuÁt, ph°¢ng pháp thiÁt kÁ giÁi thuÁt, đánh giá đá phức t¿p của giÁi thuÁt trong mát sß bài toán cụ thể.
CH¯¡NG 1: GIÀI THU¾T 1. GiÁi thu¿t Khái niệm giÁi thuÁt hay thuÁt giÁi mà nhiều khi còn đ°ợc gọi là thuÁt toán dùng để chß ph°¢ng pháp hay cách thức (method) để giÁi quyÁt vần đề. GiÁi thuÁt có thể đ°ợc minh họa b¿ng ngôn ngÿ tā nhiên (natural language), b¿ng s¢ đá (flow chart) hoặc b¿ng mã giÁ (pseudo code). Trong thāc tÁ, giÁi thuÁt th°ßng đ°ợc minh họa hay thể hiện b¿ng mã giÁ tāa trên mát hay mát sß ngôn ngÿ lÁp trình nào đó (th°ßng là ngôn ngÿ mà ng°ßi lÁp trình chọn để cài đặt thuÁt toán), chÁng h¿n nh° C, Pascal, ? Khi đã xác đánh đ°ợc cấu trúc dÿ liệu thích hợp, ng°ßi lÁp trình s¿ bÃt đầu tiÁn hành xây dāng thuÁt giÁi t°¢ng ứng theo yêu cầu của bài toán đặt ra trên c¢ sá của cấu trúc dÿ liệu đã đ°ợc chọn.
Để giÁi quyÁt mát vấn đề có thể có nhiều ph°¢ng pháp, do vÁy sā lāa chọn ph°¢ng pháp phù hợp là mát việc mà ng°ßi lÁp trình phÁi cân nhÃc và tính toán. Sā lāa chọn này cũng có thể góp phần đáng kể trong việc giÁm bớt công việc của ng°ßi lÁp trình trong phần cài đặt thuÁt toán trên mát ngôn ngÿ cụ thể. CÃu trúc dÿ liáu Mßi quan hệ giÿa cấu trúc dÿ liệu và GiÁi thuÁt có thể minh họa b¿ng đÁng thức: Cấu trúc dÿ liệu + GiÁi thuÁt = Ch°¢ng trình. Nh° vÁy, khi đã có cấu trúc dÿ liệu tßt, nÃm vÿng giÁi thuÁt thāc hiện thì việc thể hiện ch°¢ng trình b¿ng mát ngôn ngÿ cụ thể chß là vấn đề thßi gian.
Khi có cấu trúc dÿ liệu mà ch°a tìm ra thuÁt giÁi thì không thể có ch°¢ng trình và ng°ợc l¿i không thể có ThuÁt giÁi khi ch°a có cấu trúc dÿ liệu. Mát ch°¢ng trình máy tính chß có thể đ°ợc hoàn thiện khi có đầy đủ cÁ Cấu trúc dÿ liệu để l°u trÿ dÿ liệu và GiÁi thuÁt xử lý dÿ liệu theo yêu cầu của bài toán đặt ra. Để đánh giá mát cấu trúc dÿ liệu chúng ta th°ßng dāa vào mát sß tiêu chí sau: - Cấu trúc dÿ liệu phÁi tiÁt kiệm tài nguyên (bá nhớ trong) - Cấu trúc dÿ liệu phÁi phÁn Ánh đúng thāc tÁ của bài toán - Cấu trúc dÿ liệu phÁi dễ dàng trong việc thao tác dÿ liệu. Các đặc tr°ng của giÁi thu¿t - Tính xác định: Mßi b°ớc của thuÁt giÁi cần phÁi đ°ợc mô tÁ mát cách chính xác, chß có mát cách hiểu duy nhất.
Bái vì, nÁu mát b°ớc có thể hiểu theo nhiều cách khác nhau, thì cùng mát dÿ liệu vào, nhÿng ng°ßi thāc hiện thuÁt giÁi khác nhau có thể cho ra kÁt quÁ khác nhau. NÁu ta mô tÁ thuÁt giÁi b¿ng ngôn ngÿ tā nhiên, không có gì đÁm bÁo ng°ßi đọc hiểu đúng ý của ng°ßi viÁt thuÁt giÁi, bái ngôn ngÿ tā nhiên th°ßng là đa nghĩa. Để đÁm bÁo đòi hỏi này, thuÁt giÁi cần đ°ợc mô tÁ trong mát ngôn ngÿ lÁp trình, chÁng h¿n mát ngôn ngÿ lÁp trình (Pascal, C. trong các ngôn ngÿ này, các mệnh đề đ°ợc t¿o thành theo các qui tÃc cú pháp nghiêm nghặt và chß có mát ý nghĩa duy nhất.
- Tính khả thi: Tất cÁ các phép giÁi có mặt trong các b°ớc của thuÁt giÁi phÁi đủ đ¢n giÁn. Điều đó có nghĩa là các phép giÁi phÁi sao cho, ít nhất về nguyên tÃc có thể 2 thāc hiện đ°ợc bái con ng°ßi trong mát khoÁng thßi gian hÿu h¿n. ChÁng h¿n trong thuÁt giÁi Euclid, ta chß cần thāc hiện các phép chia các sß nguyên, các phép gán và các phép so sánh. - Tính dừng: Với mọi bá dÿ liệu vào thoÁ mãn điều kiện qui đánh, thuÁt giÁi phÁi dừng l¿i sau mát sß hÿu h¿n b°ớc thāc hiện.
ChÁng h¿n đßi với thuÁt giÁi Euclid là thuÁt giÁi thoÁ mãn điều kiện này. Bái vì sß d° r luôn nhỏ h¢n n, nÁu r0 thì giá trá của n á b°ớc sau là giá trá của r á b°ớc tr°ớc, ta có n>r=n1>r1=n2>r2.Dãy sß nguyên d°¢ng giÁm dần cần phÁi kÁt thúc á 0, do đó sau mát sß b°ớc giá trá của r=0 thuÁt giÁi dừng. Dÿ liáu vào - Input: Mßi thuÁt giÁi cần có mát sß (có thể b¿ng không) dÿ liệu vào. Đó là giá trá cần đ°a vào khi thuÁt giÁi bÃt đầu làm việc.
Dÿ liáu ra - Output: Mßi thuÁt giÁi cần có mát hoặc nhiều dÿ liệu ra. Đó là các giá trá có quan hệ xác đánh với giá trá vào và là kÁt quÁ của sā thāc hiện thuÁt giÁi. Tính hiáu quÁ Mát giÁi thuÁt nên là có thể thi hành đ°ợc với các nguán có sẵn, tức là có khÁ năng giÁi quyÁt hiệu quÁ vấn đề trong điều kiện thßi gian và tài nguyên cho phép. Tính chính xác GiÁi thuÁt nên rõ ràng và không m¢ há.
Mßi mát giai đo¿n (hay mßi b°ớc) nên rõ ràng và chß mang mát mục đích nhất đánh. Tính ứng dụng Mát giÁi thuÁt có tính phổ biÁn nÁu giÁi thuÁt này có thể giÁi quyÁt đ°ợc mát lớp các vấn đề t°¢ng tā. Tính hÿu h¿n Các giÁi thuÁt phÁi kÁt thúc sau mát sß hÿu h¿n các b°ớc. Ngôn ngÿ dißn đ¿t 1.
Ngôn ngÿ thông thường Trong cách biểu diễn thuÁt giÁi theo ngôn ngÿ tā nhiên, ng°ßi ta sử dụng ngôn ngÿ th°ßng ngày để liệt kê các b°ớc của thuÁt giÁi (Các ví dụ về thuÁt giÁi trong mục 1 của ch°¢ng sử dụng ngôn ngÿ tā nhiên). Ph°¢ng pháp biểu diễn này không yêu cầu ng°ßi viÁt thuÁt giÁi cũng nh° ng°ßi đọc thuÁt giÁi phÁi nÃm các quy tÃc. Tuy vÁy, cách biểu diễn này th°ßng dài dòng, không thể hiện rõ cấu trúc của thuÁt giÁi, đôi lúc gây hiểu lầm hoặc khó hiểu cho ng°ßi đọc. Gần nh° không có mát quy tÃc cß đánh nào trong việc thể hiện thuÁt giÁi b¿ng ngôn ngÿ tā nhiên 1.
Lưu đồ L°u đá hay s¢ đá khßi là mát công cụ trāc quan để diễn đ¿t các thuÁt giÁi. Biểu diễn thuÁt giÁi b¿ng l°u đá s¿ giúp ng°ßi đọc theo dõi đ°ợc sā phân cấp các tr°ßng hợp và quá trình xử lý của thuÁt giÁi. Ph°¢ng pháp l°u đá th°ßng đ°ợc dùng trong nhÿng thuÁt giÁi có tính rÃc rßi, khó theo dõi đ°ợc quá trình xử lý. 3 Các nút biểu diễn giải thuật bằng sơ đồ khối: Nút thao tác Nút điều khiển: trong đó ghi điều kiện cần kiểm tra trong quá trình tính toán.
Nút khái đầu, kÁt thúc Cung V¿ l°u đá hoặc s¢ đá khßi, mßi khßi mô tÁ mát b°ớc. Sử dụng mũi tên nßi khßi này với khßi kia để chß trình tā thāc hiện các b°ớc. Để dễ dàng nhÁn biÁt chức năng của từng khßi, mßi khßi đ°ợc thể hiện á mát d¿ng nh° sau: Ví dụ: Tìm nghiệm thāc của ph°¢ng trình bÁc hai ax2+bx+c=0. ThuÁt toán gám các b°ớc sau: + NhÁp dÿ liệu a, b, c.
+ Tính biệt sß = b2-4ac. + So sánh với 0. B°ớc tiÁp theo s¿ phụ thuác vào giá trá của . + NÁu <0, đáp sß của bài toán là <Vô nghiệm=.
+ NÁu =0, tính và ghi đáp sß trá của nghiệm kép. + NÁu >0, tính và ghi đáp sß trá của hai nghiệm phân biệt:. L°u đá biểu diễn thuÁt toán này đ°ợc thể hiện nh° sau: 4 1. Ngôn ngÿ l¿p trình Tuy s¢ đá khßi thể hiện rõ quá trình xử lý và sā phân cấp các tr°ßng hợp của thuÁt toán nh°ng l¿i cáng kềnh.
Để mô tÁ mát thuÁt toán nhỏ ta phÁi dùng mát không gian rất lớn. Đôi khi, ta có thể thể hiện thuÁt toán b¿ng ngôn ngÿ lÁp trình nào đó. Mọi ngôn ngÿ lÁp trình đều có nhÿng thao tác c¢ bÁn là xử lý, r¿ nhánh và lặp. Nh° vÁy, có thể tÁn dụng đ°ợc các khái niệm trong ngôn ngÿ lÁp trình, vừa giúp ng°ßi cài đặt dễ dàng hiểu chính xác thuÁt toán.
Mát khi đã vay m°ợn cú pháp và khái niệm của ngôn ngÿ lÁp trình thì chÃc chÃn mã giÁ s¿ bá phụ thuác vào ngôn ngÿ lÁp trình đó. Mát đo¿n mã giÁ của thuÁt toán giÁi ph°¢ng trình bÁc hai: if Delta > 0 then begin end else if delta = 0 then xuất kết quả : phương trình có nghiệm kép là -b/(2*a) else {trường hợp delta < 0 } xuất kết quả : phương trình vô nghiệm x1=(-b+sqrt(delta))/(2*a) x2=(-b-sqrt(delta))/(2*a) 5 xuất kết quả : phương trình có hai nghiệm là x1 và x2 1. Ph°¢ng pháp thi¿t k¿ giÁi thu¿t 1. Mô-đun hóa và viác giÁi quyết bài toán Các bài toán giÁi trên máy tính càng ngày càng đa d¿ng và phong phú d¿n tới quy mô ch°¢ng trình ngày càng lớn.
Quy mô càng lớn d¿n tới việc lÁp và kiểm soát ch°¢ng tình càng gặp nhiều khó khăn h¢n.