Thiết kế và đánh giá thuật toán

Lời nói đầu

Xây dựng một thuật toán tốt để giải bài bài toán đã cho là bước quan trọng nhất trong việc giải bài toán đó trên máy tính điện tử. Để có được một thuật một thuật toán tốt cần phải nắm vững các kỹ thuật thiết kế, phân tích, đánh giá thuật toán cùng các thuật toán cơ bản cho một số lớp bài bài toán điển hình.

Tài liệu Thiết kế và đánh giá thuật toán được biên soạn nhằm phục vụ công việc giảng dạy và học tập môn học Thiết kế và đánh giá thuật toán của ngành học Khoa học máy tính thuộc khoa Công nghệ thông tin trường Đại học sư phạm kỹ thuật Nam Định. Tài liệu cũng rất cần thiết cho tất cả các ngành học thuộc khoa Công nghệ thông tin.

Nội dung của tài liệu trình bày các kỹ thuật thiết kế thuật toán thông dụng và cơ sở phân tích, đánh giá độ phức tạp của thuật toán. Tài liệu gồm 6 chương:

Chương 1: Tổng quan về thiết kế và đánh giá thuật toán Chương 2: Kỹ thuật chia để trị

Chương 3: Kỹ thuật tham lam Chương 4: Kỹ thuật quay lui

Chương 5: Kỹ thuật nhánh và cận Chương 6: Kỹ thuật quy hoạch động

Trong từng chương các vấn đề đưa ra đều được minh họa bằng các ví dụ. Cuối mỗi chương đều có một hệ thống các bài tập nhằm giúp người học củng cố các kiến thức đã được học đồng thời rèn luyện khả năng vận dụng các kiến thức để giải quyết một số bài toán trong thực tế. Với các bài tập khó tài liệu đã đưa ra hướng dẫn giải để giúp người học thuận lợi trong qua trình nghiên cứu và giải quyết các bài tập. Cuối tài liệu là phần cài đặt một số thuật toán đã được thiết kế nhằm giúp người học thuận lợi hơn trong việc nắm bắt và vận dụng các kỹ thuật thiết kế thuật toán.

Tài liệu được biên soạn theo chương trình môn học Thiết kế và đánh giá thuật toán của ngành học Khoa học máy tính thuộc khoa Công nghệ thông tin trường Đại học sư phạm kỹ thuật Nam Định. Nội dung tài liệu được biên soạn dựa trên cơ sở nội dung các bài giảng của tác giả trong một số năm qua tại khoa Công nghệ thông tin trường Đại học sư phạm kỹ thuật Nam Định.

Trong quá trình biên soạn, tác giả đã nhận được nhiều ý kiến đóng góp cùng với sự động viên, khích lệ của bạn bè đồng nghiệp trong khoa và trong trường. Tác giả xin được tỏ lòng cảm ơn với những ý kiến đóng góp và động viên khích lệ này.

Có thể bạn quan tâm!

Xem toàn bộ 205 trang tài liệu này.

Với lần biên soạn đầu tiên, mặc dù đã hết sức cố gắng song chắc chắn tài liệu không thể tránh khỏi những thiếu sót. Rất mong nhận được các ý kiến đóng góp để tài liệu ngày càng hoàn thiện hơn.

Phạm Cao Hào

MỤC LỤC

Chương 1. Tổng quan về thiết kế và đánh giá thuật toán 1

1.1. Thuật toán 1

1.1.1. Khái niệm thuật toán 1

1.1.2. Các đặc trưng cơ bản của thuật toán 1

1.2. Sự cần thiết của thiết kế và đánh giá thuât toán 2

1.3. Diễn tả thuật toán 3

1.4. Thiết kế thuật toán 7

1.4.1. Modul hoá và thiết kế từ trên xuống 7

1.4.2. Phương pháp là mịn dần (tinh chỉnh từng bước) 7

1.4.3. Một số kỹ thuật thiết kế 8

1.5. Phân tích thuật toán 9

1.5.1. Thời gian thực hiên thuật toán 9

1.5.2. Độ phức tạp tính toán của thuật toán 10

1.5.3. Ðộ phức tạp của chương trình có gọi chương trình con không đệ qui 16

1.5.4. Phân tích các thuật toán đệ quy 17

1) Thành lập phương trình truy hồi 18

2) Giải phương trình truy hồi 19

Bài tập chương 1. 31

Chương 2. Kỹ thuật chia để trị 37

2.1 Nội dung kỹ thuật 37

2.2. Các ví dụ áp dụng 37

2.2.1. Tìm min và max 37

2.2.2. Một số thuật toán sắp xếp 40

1) Sắp xếp nhanh 40

2) Sắp xếp trộn 44

2.2.3. Tìm kiếm nhị phân 51

2.2.4. Nhân các số nguyên lớn 53

Bài tập chương 2. 57

Chương 3. Kỹ thuật tham lam 62

3.1. Nội dung kỹ thuật 62

3.1.1. Bài toán tối ưu tổ hợp 62

3.1.2. Nội dung kỹ thuật tham lam 62

3.2. Các ví dụ áp dụng 62

3.2.1. Bài toán người giao hàng 62

3.2.2. Bài toán chiếc ba lô 65

3.2.3. Bài toán tô màu bản đồ 70

3.2.4. Tìm cây khung nhỏ nhất 74

3.2.5. Tìm đường đi ngắn nhất 77

3.2.6. Bài toán phân công công việc 79

Bài tập chương 3. 84

Chương 4. Kỹ thuật quay lui 86

4.1. Nội dung kỹ thuật 86

4.2. Các ví dụ áp dụng 87

4.2.1. Đưa ra các dãy nhị phân độ dài n 87

4.2.2. Đưa ra các hoán vị của n số nguyên 88

4.2.3. Đưa ra các tập con của tập gồm n số nguyên 90

4.2.4. Bài toán xếp hậu 92

4.2.5. Tìm đường đi trên đồ thị 94

4.2.6. Bài toán ngựa đi tuần 99

Bài tập chương 4 104

Chương 5. Kỹ thuật nhánh và cận 111

5.1. Nội dung kỹ thuật 111

5.2. Các ví dụ áp dụng 114

5.2.1. Bài toán người du lịch 114

5.2.2. Bài toán chiếc ba lô 128

Bài tập chương 5. 133

Chương 6. Kỹ thuật quy hoạch động 137

6.1. Nội dung kỹ thuật 137

6.2. Các ví dụ áp dụng 140

6.2.1. Tính số tổ hợp 140

6.2.2. Bài toán nhân nhiều ma trận 143

6.2.3. Bài toán chiếc ba lô 149

6.2.4. Xâu con chung dài nhất 154

Bài tập chương 6. 164

Phụ lục 171

Tài liệu tham khảo 195

Chương 1

TỔNG QUAN VỀ THIẾT KẾ VÀ ĐÁNH GIÁ THUẬT TOÁN

1.1. Thuật toán

1.1.1. Khái niệm thuật toán

Thuật toán (Algorithm) đã được biết đến từ rất lâu. Đầu tiên thuật toán được hiểu như là các qui tắc thực hiện các phép tính số học với các con số được viết trong hệ thập phân. Cùng với sự phát triển của máy tính, khái niệm thuật toán được hiểu theo nghĩa rộng hơn. Khái niệm thuật toán được định nghĩa một cách hình thức chính xác thông qua máy Turing. ở đây chúng ta sẽ xem xét khái niệm thuật toán một cách trực quan.

Thuật toán (hay giải thuật, thuật giải) là một khái niệm cơ sở của tin học.

Mỗi bài toán trong thực tế bao gồm hai phần:

- Input: Các đại lượng cho trước (đại lượng vào)

- Output: Các đại lượng cần tìm (đại lượng ra)

Như vậy việc giải bài toán là việc xác định tường minh output theo input bằng một quá trình có thể thực hiện một cách hiệu quả. Đó chính là nội dung cơ bản của lý thuyết tính toán. Khi cho bài toán, ta cần tìm ra 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 theo đó, từ input ta sẽ tìm ra được output theo yêu cầu.

Một cách trực quan thuật toán giải một bài toán là một dãy hữu hạn các chỉ dẫn (quy tắc, thao tác hay phép toán) hết sức rò ràng và chính xác được sắp xếp theo một trình tự xác định để sao cho sau một số hữu hạn lần thực hiên các chỉ dẫn đó thì biến đổi được input thành output.

1.1.2. Các đặc trưng cơ bản của thuật toán

1) Dữ liệu vào

Mỗi thuật toán có thể có một hoặc nhiều đại lượng vào mà ta thường gọi là dữ liệu vào

2) Dữ liệu ra

Sau khi thực hiên xong thuật toán, tuỳ theo chức năng mà thuật toán đảm nhiệm ta có thể thu được một số đại luợng ra mà ta gọi là dữ liệu ra.

3) Tính xác định

Tính xác định của thuật toán đòi hỏi ở chỗ ở mỗi bước các thao tác phải hết sức rò ràng, không thể gây nên sự nhập nhằng, lẫn lộn, tuỳ tiện. Nói cách khác trong cùng một điều kiện hai bộ xử lý (người hoặc máy) thực hiện cùng một bước của thuật toán thì phải cho cùng một kết quả.

4) Tính dừng

Thuật toán phải dừng và cho kết quả sau một số hữu hạn bước thực hiện.

5) Tính hiệu quả

Yêu cầu của tính hiệu quả là trong số các thuật toán thực hiện cùng một chức năng ta cần chọn thuật toán tốt nhất. Tiêu chuẩn tốt ở đây được hiểu là: thuật toán thực hiện nhanh, tốn ít thời gian nhất, dùng ít giấy hoặc từ nhớ để lưu trữ các kết quả trung gian.

6) Tính phổ dụng

Một thuật toán được xem là có tính phổ dụng cao nếu nó có thể dùng để giải bất cứ bài toán nào trong một lớp các bài toán chứ không phải là một bài toán cụ thể.

1.2. Sự cần thiết của thiết kế và đánh giá thuật toán

Xây dựng một thuật toán tốt để giải bài toán đã cho là bước quan trọng nhất trong việc giải bài toán đó trên máy tính điện tử. Để có được một thuật toán tốt cần phải nắm vững các kỹ thuật thiết kế, phân tích, đánh giá thuật toán cùng các thuật toán cơ bản cho một số lớp bài toán điển hình.

Trong khi giải một bài toán chúng ta có thể có một số thuật toán khác nhau, vấn đề là cần phải đánh giá các thuật toán đó để lựa chọn một thuật toán tốt (nhất). Thông thường thì ta sẽ căn cứ vào các tiêu chuẩn sau:

(1) Thuật toán đúng đắn.

(2) Thuật toán đơn giản.

(3) Thuật toán thực hiện nhanh.

Với yêu cầu (1), để kiểm tra tính đúng đắn của thuật toán chúng ta có thể cài đặt thuật toán đó và cho thực hiện trên máy với một số bộ dữ liệu mẫu rồi lấy kết quả thu được so sánh với kết quả đã biết. Thực ra thì cách làm này không chắc chắn bởi vì có thể thuật toán đúng với tất cả các bộ dữ liệu chúng ta đã thử nhưng lại sai với một bộ dữ liệu nào đó. Vả lại cách làm này chỉ phát hiện ra thuật toán sai chứ chưa chứng minh được là nó đúng. Tính đúng đắn của thuật toán cần phải được chứng minh bằng toán học. Điều này không đơn giản và do vậy chúng ta sẽ không đề cập đến ở đây.

Khi chúng ta viết một chương trình để sử dụng một vài lần thì yêu cầu (2) là quan trọng nhất. Chúng ta cần một giải thuật dễ viết chương trình để nhanh chóng có được kết quả , thời gian thực hiện chương trình không được đề cao vì dù sao thì chương trình đó cũng chỉ sử dụng một vài lần mà thôi. Tuy nhiên khi một chương trình được sử dụng nhiều lần thì thì yêu cầu tiết kiệm thời gian thực hiện chương

trình lại rất quan trọng đặc biệt đối với những chương trình mà khi thực hiện cần dữ liệu nhập lớn do đó yêu cầu (3) sẽ được xem xét một cách kĩ càng. Ta gọi nó là hiệu quả thời gian thực hiện của thuật toán.

1.3. Diễn tả thuật toán

Có nhiều cách diễn tả thuật toán. Người ta thường diễn tả thuật toán bằng một trong các cách sau:

1) Liệt kê từng buớc

Thuật toán có thể trình bày dưới dạng ngôn ngữ tự nhiện theo trình tự các bước thực hiện trong thuật toán

2) Sơ đồ khối (Lưu đồ)

Dùng các hình vẽ (có qui ước) để diễn tả thuật toán. Lưu đồ cho hình ảnh trực quan và tổng thể của thuật toán nên thường được sử dụng.

3) Ngôn ngữ lập trình

Dùng cấu trúc lệnh, dữ liệu của một ngôn ngữ lập trình nào đó để mô tả.

4) Dạng giả mã

Thuật toán trình bày dưới dạng văn bản bằng ngôn ngữ tự nhiên tuy dễ hiểu nhưng khó cài đặt. Dùng một ngôn ngữ lập trình nào đó để diễn tả thì phức tạp, khó hiểu. Thông thường thuật toán cũng được trình bày dưới dạng văn bản và không ràng buộc nhiều vào cú pháp qui định của ngôn ngữ lập trình, nhưng cũng tuân theo một số qui ước ban đầu- Ta gọi dạng này là dạng giả mã. Tuỳ theo việc định hướng cài đặt thuật toán theo ngôn ngữ lập trình nào mà tả fiễn đạt thuật toán gần với ngôn ngữ ấy. Trong tài liệu naứy ta trình bày các thuật toán dưới dạng giả mã của ngôn ngữ lập trình C. Dưới đây là một số quy ước của ngôn ngữ lập trình C:

* Các ký tự

- Bộ chữ cái: 26 chữ cái

- 10 chữ số thập phân.

- Các dấu phép toán số học.

- Các dấu phép toán quan hệ.

. . .

* Các phép toán số học và logic

Các từ sau xem như là các từ khoá : if, else, case, for, while , do while

...

* Các phép toán số học và logic

- Các phép toán số học : +, -, *, /, %.

- Các phép toán Logic : &&, ||, !

* Lệnh gán: biến=biểu thức;

* Khối lệnh:

{

A1;

A2;

...

An;

}

* Cấu trúc rẽ nhánh if

Toán tử if cho phép lựa chọn chạy theo một trong hai nhánh tuỳ thuộc vào sự bằng không và khác không của biểu thức. Nó có hai cách viết sau :

if (biểu thức) khối lệnh 1

/* Dạng một */

Sự lồng nhau của các toán tử if :

if (biểu thức) khối lệnh 1 else

khối lệnh 2

/* Dạng hai */

C cho phép sử dụng các toán tử if lồng nhau có nghĩa là trong các khối lệnh (1 và 2) ở trên có thể chứa các toán tử if - else khác. Trong trường hợp này, nếu không sử dụng các dấu đóng mở ngoặc cho các khối thì sẽ có thể nhầm lẫn giữa các if-else. Chú ý là máy sẽ gắn toán tử else với toán tử if không có else gần nhất.

* Cấu trúc rẽ nhánh - toán tử switch: switch (biểu thức nguyên)

{

case n1

khối lệnh 1 case n2