Tài liệu tham khảo môn học Cấu trúc dữ liệu

Chia sẻ: Benq Benq | Ngày: | Loại File: DOC | Số trang:385

Thêm vào BST

Báo xấu

1.356
lượt xem 415
download

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

Tài liệu tham khảo môn học Cấu trúc dữ liệu gồm 8 chương với mục tiêu giới thiệu cho học sinh về khái niệm về kiểu dữ liệu trừu tượng, kiểu dữ liệu trừu tượng, cấu trúc dữ liệu thông dụng, nâng cao và những thao tác trên các cấu trúc đó, một số thuật toán cơ bản và rèn luyện một số kĩ năng phân tích thuật toán.

Chủ đề:

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

Lưu

Nội dung Text: Tài liệu tham khảo môn học Cấu trúc dữ liệu

Tài liệu tham khảo môn học cấu trúc dữ liệu  -1-
LỜI NÓI ĐẦU Giáo trình này được viết cho sinh viên các trường Cao đẳng Đại học Để học tốt giáo trình này sinh viên cần có kiến thức về tin học cơ sở và đã biết một ngôn ngữ lập trình bậc cao như Pascal, Delphi, C hay C++... Giáo trình được viết nhằm những mục tiêu sau đây:  Giới thiệu cho học sinh về khái niệm về kiểu dữ liệu trừu tượng.  Cung cấp cho học sinh kiến thức cơ bản về những kiểu dữ liệu trừu tượng, cấu trúc dữ liệu thông dụng, nâng cao và những thao tác trên các cấu trúc đó.  Cung cấp một số thuật toán cơ bản và rèn luyện một số kĩ năng phân tích thuật toán cho học sinh.  Rèn luyện cho học sinh cách áp dụng các cấu trúc dữ liệu đã học và tư duy thuật toán để có thể thiết kế và cài đặt một số chương trình bằng một ngôn ngữ bậc cao. Để có thể học tốt các chương sau, sinh viên cần đọc kĩ chương 1 và chương 2. Chương 1 giới thiệu những khái niệm cơ bản về thuật giải. Chương 2 giới thiệu những khái niệm cơ bản về kiểu dữ liệu trừu tượng. Đây là khái niệm mới đối với học sinh. Một kiểu dữ liệu trừu tượng là một tập hợp các đối tượng và được xác định hoàn toàn bởi các phép toán có thể biểu diễn trên các đối tượng đó. Người sử dụng được phép tìm hiểu các đối tượng và thực hiện các thao tác trên các đối tượng của kiểu dữ liệu thông qua các phép toán đó mà không cần quan tâm đến việc đối tượng được cài như thế nào trong ngôn ngữ lập trình. Chúng tôi có đưa ra một vài ví dụ đơn giản về kiểu dữ liệu trừu tượng, cách đặc tả và xây dựng chúng để định hướng cho việc đặc tả và xây dựng những kiểu dữ liệu trừu tượng trong những chương sau. Trong khi trình bày mỗi kiểu dữ liệu trừu tượng ở mỗi chương sau, chúng tôi cố gắng khuyến khích sinh viên trước hết phải hiểu một cách khái quát về kiểu dữ đó trước khi quan tâm đến việc cài đặt chi tiết bên trong. Điều đó không có nghĩa là chúng tôi không coi trọng việc cài đặt. Việc tách riêng đặc tả bên ngoài và bên trong cho phép ta nhìn rõ trước hết vào bản chất của một kiểu dữ liệu trừu tượng là tập các thao tác trên -2-
các đối tượng của kiểu dữ liệu đó. Và chỉ khi đã hiểu rõ bản chất của các thao tác trên một kiểu dữ liệu trừu tượng chúng ta mới chuyển tới việc cài đặt những thao tác đó bằng một ngôn ngữ bậc cao nào đó. Công cụ cho phép ta bóc tách một cách khái niệm hình thức bên ngoài và chi tiết bên trong đó chính là kiểu dữ liệu trừu tượng. Từ chương 3 đến chương 6 dành cho việc nghiên cứu một số kiểu dữ liệu trừu tượng cơ bản tuyến tính và phi tuyến. Đó là các kiểu dữ liệu trừu tượng ngăn xếp, hàng đợi, cây, bảng tìm kiếm, tập hợp và đồ thị... Với mỗi kiểu dữ liệu trừu tượng đưa ra, chúng đều được đặc tả bởi các thao tác cơ bản và hướng dẫn cài đặt một số thao tác. Những thao tác đưa ra là những thao tác cơ bản nhất. Tuy nhiên, tuỳ theo điều kiện và hoàn cảnh, học sinh có thể bổ sung thêm một số những thao tác khác. Trong việc xây dựng các kiểu dữ liệu trừu tượng, chúng tôi rất nhấn mạnh việc quan tâm đầu tiên là đặc tả được các thao tác cần thiết (xây dựng mô đun ngoài), sau đó mới đến việc cài đặt các thao tác (xây dựng mô đun trong). Ngoài ra, chúng tôi cũng quan tâm đến việc hướng dẫn sử dụng các kiểu dữ liệu trừu tượng thông qua những ví dụ về những mô đun ứng dụng. Sinh viên ắt hẳn đã được giới thiệu một vài thuật toán sắp xếp đơn giản trên mảng từ phần Tin học đại cương. Tuy nhiên, bài toán sắp xếp và tìm kiếm là bài toán hết sức cơ bản đối với mỗi sinh viên Cao đẳng và Đại học nên chúng tôi dành riêng chương 7 để nói về một số giải thuật sắp xếp đơn giản cũng như một số giải thuật sắp xếp nâng cao, cần đến một chút kiến thức về kiểu dữ liệu trừu tượng vừa học trong các chương trước. Một số phép so sánh các giải thuật sắp xếp cũng được đề cập trong chương này. Để giúp học sinh có thêm một số kiến thức về thuật giải, trong chương 8, chúng tôi trình bày một số phương pháp thiết kế thuật giải như đệ qui, quay lui, chia dể trị, tham lam, qui hoạch động. Đây là những phương pháp rất cơ bản và thông dụng trong khoa học máy tính. Bạn đọc có thể tìm thấy nhiều ví dụ minh hoạ cho những phương pháp này. Các ví dụ đều được cài đặt cụ thể bằng ngôn ngữ lập trình Pascal. Cuối mỗi chương đều có hệ thống bài tập để học sinh làm và tự kiểm tra kiến thức của mình. Cuối cùng là phần phụ lục, trong đó chúng tôi có đưa ra một số bài tập lớn, để học sinh áp dụng những kiến thức đã học tập giải quyết những vấn đề phức tạp hơn so với bài -3-
tập sau mỗi chương. Với những bài tập lớn này, để nâng cao hiệu quả, yêu cầu học sinh cần đặc tả rõ bài toán, phân tích và thiết kế thuật giải, sau đó cài đặt trên một ngôn ngữ cụ thể. Tiếp theo học sinh cần phải kiểm thử phần mềm mình vừa cài đặt và có những nhận xét về độ phức tạp của thuật toán mình thiết kế, về các hướng cần mở rộng cho các bài tập này. Chỉ khi nào học sinh làm tốt các bài tập lớn đó mới có thể nói là họ đã thành công trong việc học tập môn học này. Chủ biên và hiệu đính toàn bộ nội dung bản thảo: Chương 1: Mở đầu chương 2: . Chương 3: . Chương 4, Chương 6: Chương 7: Chương 8: -4-
CHƯƠNG I: MỞ ĐẦU Chương này trình bày một số khái niệm cơ bản đầu tiên về bài toán theo quan điểm Tin học, thuật giải, cấu trúc dữ liệu, mối quan hệ giữa cấu trúc dữ liệu và thuật giải. Những khái niệm về độ phức tạp của thuật giải và phân tích thuật giải cũng được giới thiệu trong chương. 1.1. Khái niệm về cấu trúc dữ liệu và thuật giải 1.1.1. Khái niệm bài toán Trong phạm vi Tin học, ta có thể quan niệm bài toán là bất cứ việc gì ta muốn máy tính thực hiện. Như vậy những việc như viết một dòng chữ ra màn hình, giải phương trình bậc hai, giải hệ phương trình bậc nhất hai ẩn số, quản lý các cán bộ trong một cơ quan... đều là các ví dụ về bài toán. Khi dùng máy tính giải bài toán, ta chỉ cần quan tâm đến hai yếu tố: đưa vào máy thông tin gì (thông tin vào) và cần lấy ra thông tin gì (thông tin ra), Thông tin vào còn được gọi là Input, thông tin ra còn được gọi là Output. Như vậy để phát biểu một bài toán, ta chỉ cần đặc tả Input và Output của bài toán. Ví dụ 1. Bài toán tìm ước chung lớn nhất Input. Hai số nguyên dương M và N Output. Ước chung lớn nhất của M và N Ví dụ 2. Bài toán tìm nghiệm của đa thức một biến: Input: số nguyên dương n; các số thực a0, a1, . . ., an; Output: Trả lời câu hỏi có bao nhiêu số thực x khác nhau và giá trị của chúng (nếu có) sao cho a0 + a1 x +...+ anxn = 0 Ví dụ 3. Bài toán phân tích số: -5-
Input: Số nguyên dương N2; Output: Các số nguyên tố p1,..., pk; các số nguyên dương 1,...,k; sao cho n = p11...pkk; Ví dụ 4. Bài toán kiểm tra tính nguyên tố: Input: Số nguyên dương n; Output: Trả lời câu hỏi n là số nguyên tố hay không?. Ví dụ 5. Bài toán quản lý hồ sơ cán bộ: Input: Hồ sơ gốc của các cán bộ trong cơ quan; Output: Những biểu bảng thống kê, phân loại cán bộ, các quy trình lưu trữ, quản lý hồ sơ cán bộ. Ví dụ 6. Bài toán thứ 10 của Hilbert: Input: P là đa thức (nhiều ẩn) với hệ số nguyên; Output: Trả lời câu hỏi P có nghiệm nguyên hay không? Qua các ví dụ trên, ta thấy các bài toán được cấu tạo bởi hai thành phần cơ bản: - Thông tin vào (input): Cho ta biết những thông tin đã có (các giả thiết); - Thông tin ra (output): Các thông tin cần tìm từ input (kết luận); 1.1.2. Khái niệm thuật giải Như vậy trong giáo trình này, việc cho một bài toán có nghĩa là cho input và mô tả output cần tìm. Vấn đề đặt ra là thế nào là giải một bài toán? Trước hết cần lưu ý rằng trong toán học có một xu hướng nghiên cứu định tính các bài toán. Theo xu hướng này, khi xem xét các bài toán, người ta chỉ cần chứng tỏ sự tồn tại của output khi cho input và nếu có thể, xét xem có bao nhiêu "lời giải" và nghiên cứu dáng điệu của chúng. Trong các nghiên cứu như vậy, nhiều khi ta không cần tìm ra lời giải một cách tường minh nhưng bằng cách dùng các công cụ toán học khác nhau một cách thích hợp ta vẫn có thể chứng minh chặt chẽ các điều khẳng định liên -6-
quan đến lời giải. Mục tiêu của xu hướng nghiên cứu này là chỉ ra điều kiện tồn tại và nếu có thể, sự duy nhất của lời giải. Sự tồn tại lời giải theo nghĩa này không luôn cho ta cách thức thực tế để tìm ra lời giải. Trong khuôn khổ của Tin học, việc giải bài toán có nghĩa trao được cho máy tính cách giải. Để giao bài toán cho máy tính, ta cần hướng dẫn cho máy các thao tác mà về nguyên tắc máy có thể thực hiện được. Một cách giải bài toán như vậy được gọi là một thuật giải (còn gọi là thuật toán hay giải thuật). Nói một cách đầy đủ hơn, Thuật giải A để giải bài toán P là một dãy hữu hạn các thao tác đơn giản được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác đó, từ Input của bài toán, ta nhận được Output cần tìm. Chính quan niệm về việc giải bài toán như vậy là cốt lõi để ta có thể chuyển giao công việc đó cho máy tính. Như vậy, khác với quan niệm về việc giải một bài toán theo toán học truyền thống, việc giải bài toán theo quan niệm của Tin học là quá trình thực hiện một dãy hữu hạn các thao tác đơn giản để có thể từ Input dẫn ra Output một cách tường minh. Trong định nghĩa nêu trên, thao tác đơn giản được hiểu là thao tác mà máy tính có thể thực hiện được. Ví dụ các phép toán số học, các phép so sánh hai giá trị số là các thao tác đơn giản. 1.1.3. Mô tả thuật giải Ngay từ khi học môn Tin học cơ sở học sinh đã được làm quen với khái niệm thuật giải và được học cách mô tả hay diễn đạt những thuật giải đơn giản. Thuật giải cho những bài toán nhỏ hay thuật giải cho những bài toán lớn khi được thiết kế ở mức thô hay được mô tả bằng sơ đồ khối. Cách dùng sơ đồ khối để minh họa thuật giải có lợi thế là rất trực quan, dễ hiểu. Tuy nhiên, với những bài toán lớn, phức tạp, việc dùng sơ đồ khối để mô tả thuật giải có những hạn chế nhất định. Hạn chế này là có thể là do khuôn khổ giấy hay màn hình ta dùng để vẽ sơ đồ hay tầm bao quát, theo dõi của mắt -7-
ta trên sơ đồ. Hạn chế này cũng nảy sinh khi bài toán của ta phức tạp, có nhiều vòng lặp lồng nhau, khi đó việc trình bày sơ đồ có rất nhiều hạn chế. Ta cũng hay dùng phương pháp liệt kê các bước giải để mô tả thuật giải. Phương pháp này cũng rất dễ hiểu đối với các bài toán nhỏ. Tuy nhiên, đối với các bài toán lớn, việc liệt kê sẽ trở nên khó khăn và nếu được thì cũng gây khó khó theo dõi, nhất là đối với vòng lặp. Hơn thế nữa việc liệt kê các bước giải ta hay phải dùng ngôn ngữ tự nhiên để mô tả các thao tác nên việc diễn đạt nhiều khi rất khó chính xác. Phương pháp thứ ba hay được dùng để mô tả thuật giải là dùng giả mã hay ngôn ngữ phỏng trình. Việc dùng ngôn ngữ phỏng trình khắc phục được những nhiều nhược điểm của hai phương pháp trên, đặc biệt đối với những bài toán lớn, phức tạp. Cũng có ý kiến là ta nên chọn một ngôn ngữ lập trình thông dụng làm công cụ để diễn đạt thuật giải. Tuy nhiên, ai cũng biết là thuật giải cần phải độc lập với ngôn ngữ lập trình. Khi thuật giải được viết tốt nó có thể được cài đặt bằng bất cứ ngôn ngữ lập trình nào, tùy theo tính thích hợp của bài toán và ý muốn của người lập trình. Hơn thế nữa, thiết kế thuật giải là một trong những công việc quan trọng nhất của người lập trình. Nếu ta chọn một ngôn ngữ lập trình để mô tả thuật giải thì lúc nào ta cũng phải chú ý tuân thủ các tiểu tiết cú pháp của ngôn ngữ. Điều đó sẽ gây mất thì giờ và ảnh hưởng lớn đến sự tập trung vào công việc chính là thiết kế và mô tả thuật giải. Sau đây là ví dụ về mô tả thuật giải tìm ước chung lớn nhất của hai số nguyên m và n. Begin Cách 1: Dùng sơ đồ khối t m True m  n mod m nt m>0 False Write n -8- End
Hình 1.1: Sơ đồ khối diễn tả thuật giải tìm ước chung lớn nhất của hai số nguyên không âm -------------------------------------- Cách thứ hai: Dùng phương pháp liệt kê các bước giải, ta có thể viết như sau:. Bước 1. Khi m > 0 thực hiện tm m  n mod m n t Bước 2. Kiểm tra xem nếu m > 0, quay lại bước 1 Bước 3. In kết quả là n và kết thúc Cách thứ ba: Dùng ngôn ngữ phỏng trình. Function Ucln(m,n) var t Begin While m > 0 do t m m  n mod m n t Return n ----------------------------- Trong thực tế, tùy theo từng giai đoạn thiết kế thuật giải, tùy theo mức độ, và đối tượng trình bày mà người lập trình thường hay chọn phương pháp thích hợp nhất trong ba phương tiện nêu trên. -9-
Như vậy, việc diễn tả một thuật giải giải một bài toán nào đó có nghĩa là trình bày trình tự các thao tác cần thực hiện. Tuy nhiên, đó chỉ là cách diễn tả thuật giải giữa người với người. Ngay khi thuật giải đã được diễn tả như vậy, con người có thể dùng để giải bài toán với mỗi bộ dữ liệu vào. Tuy nhiên, theo cách diễn tả này, máy tính vẫn chưa thể thực hiện các thao tác trong thuật giải dù các thao tác đó rất đơn giản. Thuật giải cần được diễn tả thành một chương trình gồm những dòng lệnh. Mỗi lệnh là một việc nào đó mà ta đòi hỏi máy tính thực hiện. Ngôn ngữ dùng để viết chương trình được gọi là ngôn ngữ lập trình. Phần đọc thêm Khái niệm thuật giải trình bày ở trên đủ để ta có thể hình dung để có thể chuyển giao cho máy tính việc giải một bài toán ta cần diễn tả cách giải như thế nào và cũng là cách nhận biết thế nào là thuật giải đối với một bài toán nào đó. Trong quá trình nghiên cứu cách giải bài toán theo nghĩa nêu trên,trong toán học đã diễn ra một quá trình phát triển đầy kịch tính. Cho tới đầu thế kỷ 20, với lòng tin tiên nghiệm vào việc mọi bài toán được phát biểu đúng đắn đều có thuật giải giải, nhiều nhà toán học đầy tài năng và tâm huyết đã tiến công vào các bài toán đang tồn tại như những lời thách đố trí tuệ con người. Vấn đề then chốt nhất của lý thuyết tính toán phát sinh ở đây. Để chứng minh một bài toán nào đó có thuật giải giải nó, ta chỉ cần đề ra một thuật giải theo quan niệm trực giác của khái niệm này và kiểm định tính đúng đắn của nó đối với bài toán đã cho. Tuy nhiên, khi cần chứng minh việc không có thuật giải giải một bài toán nào đó, quan niệm trực quan về thuật giải không thể là cơ sở bảo đảm cho một chứng minh toán học chặt chẽ được. Do đó, muốn chứng minh những điều khẳng định "không có thuật giải giải một bài toán nào dó", ta cần có một định nghĩa toán học cho khái niệm thuật giải. Vào khoảng những năm 1930-1936, lần lượt các nhà toán học K.Gõdel, S. Kleene, A.Church, A.Turing đã đề ra một số định nghĩa khác nhau cho khái niệm thuật giải. Trong số các định nghĩa toán học khác nhau (nhưng tương đương) về thuật giải, các khái niệm Máy Turing (1936) và Hàm đệ quy (1931-1936) được sử dụng rộng rãi hơn vì có nhiều thuận tiện cho các nghiên cứu cả về lý thuyết lẫn thực hành. Ta có thể xem máy Turing là một mô hình toán học của máy tính. - 10 -
Chính nhờ có được định nghĩa toán học về thuật giải, người ta đã chứng minh được có những bài toán không có thuật giải giải. Chẳng hạn, bài toán thứ 10 của Hilbert (Ví dụ 5 nêu trên) không có thuật giải đểgiải. 1.1.4. Một số ví dụ về thuật giải Ví dụ 1. Một thuật giải tìm ước chung lớn nhất (viết tắt là UC) của hai số nguyên dương M và N.(Bạn đọc có thể thấy sự khác nhau chút ít giữa thuật toán này và thuật toán trình bày ở phần trên). Bước 1. Nếu M=N thì UC=M và kết thúc, nếu không thì chuyển đến bước 2. Bước 2. Nếu M
3.3. Tăng i một đơn vị và quay về bước 2. Rõ ràng số thao tác cần tiến hành không quá n. Ví dụ 3. Thuật giải để sắp xếp một dãy số cho trước thành một dãy đơn điệu không tăng. Ta xét bài toán sau: Input: Số nguyên dương n và dãy n số a1, . . ., an. Output: Dãy số trên được sắp xếp lại thành một dãy số không tăng tức là số hạng trước lớn hơn hay bằng số hạng sau. Một thuật giải giải bài toán này có thể nói vắn tắt như sau: với mỗi chỉ số i, 1in-1, xét các chỉ số j đứng sau i, i+1jn, nếu ai
thức nhất định thành những cấu trúc dữ liệu để thuật giải tác động lên đó được hiệu quả. Trong giáo trình Tin học cơ sở, ta đã làm quen với một số cấu trúc dữ liệu đơn giản như bản ghi, mảng...Trong giáo trình này ta sẽ lần lượt nghiên cứu những cấu trúc dữ liệu phức tạp hơn cả tuyến tính và phi tuyến tính. Khi lập chương trình cho máy tính, công việc tổ chức dữ liệu và thiết kế những thuật giải tương thích, hiệu quả là rất quan trọng. Chính vì thế cấu trúc dữ liệu và thuật giải là hai thành tố quan trọng của chương trình máy tính và đều là những đối tượng nghiên cứu quan trọng của khoa học máy tính. Hơn nữa, chúng có quan hệ mật thiết với nhau, ảnh hưởng và điều phối lẫn nhau để tạo ra lời giải cho bài toán. Trong phạm vi của giáo trình này, ta nghiên cứu những cấu trúc dữ liệu cơ bản và những thuật giải hay thao tác thường thực hiện trên các cấu trúc dữ liệu đó. 1.2. Khái niệm về độ phức tạp của thuật giải Mỗi thuật giải chỉ giải một bài toán nào đó nhưng có thể có nhiều thuật giải khác nhau giải cùng một bài toán. Ví dụ, để sắp xếp một dãy số bất kỳ thành một dãy đơn điệu, có rất nhiều thuật giải khác nhau. Cùng một bài toán, có thể có nhiều thuật giải khác nhau. Việc lựa chọn một thuật giải thích hợp nhất hay tốt nhất cho một bài toán luôn là mối quan tâm của người lập trình. Vậy làm thế nào để chọn được thuật giải thích hợp nhất trong những thuật giải của một bài toán? Nói cụ thể hơn, những tiêu chí nào là quan trọng để đánh giá một thuật giải? Thuật giải càng trong sáng, có cấu trúc tốt thì mã hóa càng nhanh, bảo trì chương trình càng dễ dàng và do đó giảm được giá thành của phần mềm. Tuy nhiên, có những thuật giải rất trong sáng, dễ hiểu nhưng lại không khả thi về mặt thời gian thực hiện hay không gian nhớ cần thiết khi thực hiện nó. Vậy làm thế nào để đánh giá được thời gian thực hiện và không gian nhớ dành cho một thuật giải? Cách đơn giản nhất là ta cài đặt thuật giải rồi cho máy chạy chưong trình với một tập dữ liệu vào nào đó và đo thời gian thực hiện chương trình cũng như tính không gian nhớ cần thiết cho nó và ta có kết quả về thời gian và không gian cần thiết cho thuật giải. Tuy nhiên, cách tính - 13 -
này chỉ mới áp dụng trên một tập dữ liệu đầu vào cụ thể. Sẽ là không thích hợp nếu ta dùng kết quả này để áp dụng chung cho các tập dữ liệu đầu vào khác. Nếu bài toán đơn giản và đầu vào chỉ gồm một số ít phần tử thì ta cũng chẳng cần quan tâm nhiều đến việc lựa chọn thuật giải làm gì. Ví dụ như bài toán sau: Ta cần chọn ra số lớn nhất trong 3 số nguyên hay thậm chí trong vài chục số nguyên đã cho. Bạn có thể dùng bất cứ thuật giải nào bạn nghĩ ra hay bạn thích, miễn là nó đúng, có lẽ thời gian thực hiện chúng cũng không khác nhau bao nhiêu. Một thuật toán tìm kiếm tuần tự để tìm một số điện thoại trong một danh sách điện thoại gồm 50 số thì có thể chấp nhận được nhưng nếu áp dụng thuật toán đó cho một danh sách gồm hàng chục ngàn số điện thoại trong một thành phố, hẳn là không thể chấp nhận được. Như vậy, vấn đề đặt ra rất tự nhiên là khi giải một bài toán, ta muốn chọn một thuật giải tốt. Chúng ta cần tìm ra một phương pháp nào đó để có thể cho phép ta đánh giá được thuật giải này tốt hơn thuật giải kia với một tập dữ liệu vào bất kì. Ví dụ, khi một danh bạ điện thoại gồm từ một trăm số điện thoại trở lên, cách tổ chức thành thư mục và việc tìm kiếm theo thư mục chắc chắn sẽ giúp ta tìm kiếm tốt hơn là việc tìm kiếm tuần tự. Nhưng thế nào là thuật giải tốt. Đây là nội dung nghiên cứu của lý thuyết độ phức tạp tính toán. Lý thuyết này có thể được xây dựng trên một nền tảng toán học chặt chẽ từ một hệ tiên đề. Tuy nhiên, trong phạm vi giáo trình này, chúng tôi chỉ giới thiệu một số vấn đề đơn giản . Khi dùng máy tính thực hiện một chương trình thể hiện một thuật giải nào đó, hệ điều hành cần cung cấp cho chương trình đó các tài nguyên như giờ CPU, bộ nhớ, . . . Độ phức tạp của một thuật giải được đo bằng số lượng các tài nguyên cần dùng để thực hiện chương trình đó. Khi so sánh hai thuật giải cùng giải một bài toán, một thuật giải này được xem là tốt hơn thuật giải kia nếu nó dùng ít tài nguyên hơn. Trong các tài nguyên cần dùng để chạy chương trình, hiện nay người ta quan tâm nhiều nhất đến thời gian vì đó là dạng tài nguyên không tái tạo được. Một thuật giải được xem là tốt nếu chương trình tương ứng chạy nhanh hay chính xác hơn, chạy - 14 -
trong thời gian chấp nhận được. Do đó, để đánh giá độ phức tạp của một thuật giải, ta thường ước tính số thao tác cơ bản cần dùng để thực hiện thuật giải. Thao tác cơ bản của một thuật giải là thao tác mà số lần thựchiện nó không ít hơn số lần thực hiện các thao tác khác. Ví dụ về thao tác cơ bản: Bài toán Thao tác cơ bản Tìm phần tử x trong một danh sách So sánh x với một phần tử của danh sách Nhân hai ma trận thực Phép nhân hai số thực, phép cộng hai số thực Sắp xếp một danh sách So sánh hai phần tử của danh sách Với mỗi bài toán, ta xét kích thước đầu vào hay gọi đơn giản là kích thước của bài toán. Kích thước đầu vào một bài toán được đo bằng số lượng dữ liệu vào cần xử lý. Ví dụ nếu dữ liệu vào là một dãy số có N số hạng thì kích thước bài toán dược xem bằng N, nếu dữ liệu vào là một đồ thị có N đỉnh, kích thước bài toán bằng N, nếu dữ liệu vào là một xâu ký tự độ dài L thì kích thước bài toán bằng L, nếu dữ liệu vào là một bảng có M dòng và N cột thì kích thước bài toán bằng MxN. . . Khi đó, số các thao tác cơ bản mà một thuật giải sẽ được biểu thị như một hàm f(K) của biến số K là kích thước của bài toán. Khi đánh giá hàm f(K) người ta thường dùng ký hiệu O hay chính xác hơn là khái niệm  của giải tích có nghĩa là cùng bậc. Ví dụ, giải thuật tìm Min-Max của một dãy số trong Mục 8.1 có độ phức tạp 2N, ta nói độ phức tạp đó cỡ (N) có nghĩa là cùng bậc với N khi N tiến đến vô cùng; tương tự, giải thuật sắp xếp dãy số có độ phức tạp cở (N2). - 15 -
Việc dùng ký hiệu  để thể hiện độ phức tạp của giải thuật cho ta một đánh giá tổng thể không bị sa vào những tính toán tỉ mỉ hơn nhưng không thật cần thiết. Ví dụ, cùng là hai phép toán cộng và nhân hai số, rõ ràng phép cộng thực hiện nhanh hơn nhiều so với phép nhân nhưng sự khác biệt đó chỉ thể hiện bằng việc thời gian tính toán sai khác một hằng số nhân. Do đó, nếu dùng ký hiệu , ta có thể bỏ qua sự khác biệt đó. Khi nói về độ phức tạp về thời gian, có một số bậc được sử dụng thường xuyên và người ta đã đặt tên cho chúng. Một cách vắn tắt, nếu một thuật toán có độ phức tạp là t và t < cn, với n > n0 và c là một hằng số dương, còn n là kích cỡ đầu vào thì người ta gọi thuật toán đó có độ phức tạp tuyến tính. Nếu t < cn2 thì t được gọi là có độ phức tạp bình phương. Tương tự t được gọi là có độ phức tạp lập phương, đa thức hay mũ nếu nó có bậc lần lượt của các hàm n 3, nk hay an , với k và a là những hằng số nào đó. Để dễ hình dung về sự tăng của một số hàm với n là kích thước của bài toán, dưới đây ta phác họa một số đồ thị của độ phức tạp loga, độ phức tạp tuyến tính, độ phức tạp bình phương, độ phức tạp lập phương và độ phức tạp mũ. O(an) O(n3) O(n2) O(n) O(log(n) - 16 -
Hình 2.1: Phác hoạ các đường biểu diễn độ phức tạp của một số thuật giải ----------------------------------------- 1.3. Phân tích thuật toán 1.3.1. Khái niệm về phân tích thuật toán Phân tích một giải thuật có nghĩa là đánh giá độ phức tạp của giải thuật đó. Thực ra không có một cẩm nang để phân tích thuật toán mà chủ yếu là ta sử dụng kiến thức toán học, sự trực quan, suy luận, và một số kĩ thuật cơ bản để tính độ phức tạp của một thuật giải. Có một số cấu trúc phổ biến trong các thuật giải: cấu trúc tuần tự, cấu trúc lặp và cấu trúc đệ quy. Với cấu trúc tuần tự: Nếu ta có hai đoạn trình thực hiện tuần tự là P1 và P2 , độ phức tạp của chúng lần lượt là t1 = O(f(n)), t2 = O(g(n)) thì độ phức tạp của cả hai đoạn P1 và P2 chính là O(max(f(n), g(n)). Ví dụ: Khi ta thực hiện tuần tự hai đoạn trình P1 và P2, P1 có độ phức tạp là O(n 2) và P2 có độ phức tạp là O(n3) thì hợp hai đoạn P1 và P2 sẽ có độ phức tạp là O(n3). Tương tự, nếu P1 có độ phức tạp là O(2 n) còn P2 có độ phức tạp là O(n 5) thì độ phức tạp của đoạn trình hợp là O(2 n). Để ý rằng, với n đủ lớn ta luôn có: n! > an > nk > logn. Cấu trúc lặp thường có một trong các dạng sau For i:=a to b do ; (1) While Do ; (2) Repeat Until ; (3) Số thao tác cần thực hiện trong một cấu trúc lặp có thể đễ dàng ước tính được sau khi đã tính được các thao tác cần thực hiện trong . Đối với cấu trúc lặp loại (1), nếu số thao tác trong là S thì số thao tác cần thực hiện tổng cộng không lớn hơn S(b-a). - 17 -
Ví dụ: trong phép nhân hai ma trận vuông A và B cấp n ta có: Procedure Nhanmatran(A,B) Var C; Begin for i  1 to n do for j  1 to n do Begin C[i,j]  0 for k  1 to n do C[i,j]  C[i,j] + a[i,k] * b[k,j] End; Return C; End Ta thấy ngay là vòng lặp trong cùng (k là biến chạy) có độ phức tạp O(n), vòng lặp trong tiếp theo (j là biến chạy) cũng có độ phức tạp O(n) và vòng lặp ngoài cùng (với i là biến chạy) với độ phức tạp O(n). Do đó toàn bộ chương trình của ta có độ phức tạp O(n 3). Đối với cấu trúc lặp loại (2) và (3), căn cứ vào điều kiện lô gic, ta có thể ước lượng được số lần lặp tối đa do đó có thể tính được số tối đa các thao tác cần thực hiện. Đối với các cấu trúc đệ quy, việc ước lượng số thao tác khó khăn hơn vì nói ta phải tiến hành tính số thao tác theo một công thức truy hồi. Sau đây ta sẽ xét một số ví dụ nữa. Ví dụ 1. Xét bài toán Input. Mảng một chiều A[1..N] gồm các số nguyên; Output. Giá trị nhỏ nhất Min và giá trị lớn nhất Max của các phần tử của mảng; Xét thuật giải có tên FindMin-Max(1,N) sau: Bước 1. Nếu N=1 thì nếu Min = Max = A[1] và kết thúc nếu không thì chuyển sang Bước 2. - 18 -
Bước 2. Nếu N=2 thì (A[1]A[2] thì Min = A[1] và Max = A[2] nếu không thì Min = A[2] và Max = A[1] và kết thúc nếu không thì chuyển sang Bước 3. Bước 3. Gọi FindMin1-Max1(1,N Div 2) và FindMin2-Max2(N div 2 +1,N); nếu Min1Min2 thì Min = Min1 nếu không thì Min=Min2 và nếu Max1Max2 thì Max = Max1 nếu không thì Max=Max2; kết thúc. Nếu dộ phức tạp tính theo số lần so sánh C(N) các số thì ta có C(2) = 1; C(2K) = 2C(K) +2 với K>1; C(2K+1) = C(K) + C(K+1) + 2; Từ đó ta có thể tính được C(N) = 3N/2 - 2. Ví dụ 2. Bài toán Tháp Hà Nội Ta sẽ diễn tả bài toán này bằng ngôn ngữ thông thường. Có N đĩa tròn đường kính khác nhau với lỗ thủng ở tâm và ba cọc 1, 2, 3. Ban đầu N đĩa đặt trên cọc 1, đĩa lớn hơn nằm dưới đĩa nhỏ hơn. Một di chuyển đĩa thực hiện bằng cách chuyển đĩa trên cùng ở cọc A (nếu có) đặt lên trên cùng một cọc B khác với điều kiện đĩa đó nhỏ hơn đĩa (nếu có) đang nằm trên cùng đĩa ở cọc B. Cần tiến hành một dãy các di chuyển đĩa sao cho cuối cùng, N đĩa được chuyển sang cọc 2. Bài toán này gắn với một giai thoại về sự thử thách của Thượng đế đối với lòng kiên trì của con người. Nếu số đĩa bằng 64, mỗi di chuyển đĩa thực hiện trong 1 giây và một người thực hiện một dãy các di chuyển đúng đắn thì người đó phải mất 500 tỷ năm mới di chuyển xong. Việc cần chuyển N đĩa từ cọc 1 sang cọc 2 một cách hợp lệ và tốt nhất có thể xem là trường hợp riêng của việc chuyển M đĩa nhỏ nhất từ cọc i sang cọc j ,1i3, 1j3, ij, một cách hợp lệ và tốt nhất có thể. Nếu ta thể hiện việc đó bằng một thủ tục Procedure Hanoi(m,i,j); Việc ta cần làm chính là Hanoi(N,1,2); Để làm việc đó, do quy định của một di chuyển đĩa, ta cần chuyển m-1 đĩa nhỏ nhất từ cọc i sang cọc thứ ba, đó là cọc k = 6-i-j, chuyển đĩa thứ M từ cọc i sang cọc j và sau đó chuyển M-1 đĩa từ cọc k sang cọc j. Nếu viết bằng Pascal, ta có - 19 -
Procedure Hanoi(M,i,j: Byte); Begin If m=0 then Exit; Hanoi(M-1,i,6-i-j); Writeln(i,’ – ‘,j); Hanoi(M-1,6-i-j,j); End; Nếu ký hiệu T(M) là số di chuyển cần thực hiện (xem như một thao tác cơ bản), ta có T(M) = 2.T(M-1) - 1 (*) Như vậy nếu xem N là kích thước của bài toán thì độ phức tạp tính toán của thuật giải trên là T(N). Từ hệ thức (*), ta có thể suy ra T(N) = 2N - 1. Hệ thức (*) là một hệ thức truy hồi. 1.3.2. Một số quan điểm phân tích thuật toán Cách phân tích thuật toán trong mục 8.2.2 còn được gọi là phân tích theo tình huống xấu nhất (Worst-Case Analysis). Với mỗi thuật giải đối với bài toán kích thước K, ta luôn đánh giá số tối đa các thao tác cơ bản cần tiến hành là bao nhiêu. Có nhiều cách khác để phân tích thuật giải như phân tích trung bình (Average Analysis), phân tích tiệm cận (Asymptotic Analysis). Ta sẽ giới thiệu cách phân tích trung bình. Câu chuyện bắt đầu từ việc xem xét thuật giải đơn hình đối với bài toán Quy hoạch tuyến tính. Bài toán này có thể phát biểu trong ngôn ngữ đại số tuyến tính như sau: I. Ma trận A gồm M dòng, N cột; Véc tơ cột B M chiều; véc tơ dòng C N chiều; O. Cần tìm véc tơ cột N chiều X sao cho AXB và CX đạt giá trị nhỏ nhất. Theo cách đánh giá xấu nhất, độ phức tạp của thuật toán đơn hình cỡ hàm mũ. Tuy nhiên, trải qua mấy chục năm dùng thuật giải này để giải rất nhiều bài toán phát sinh trong nhiều lĩnh vực khác nhau, các chương trình vẫn chạy trong thời gian chấp nhận được. Công trình nghiên cứu của nhà toán học S.. Smale cho kết quả độ phức tạp trung - 20 -