Bài giảng Thiết kế và đánh giá thuật toán: Phần 1 - ĐH Sư Phạm Kỹ Thuật Nam Định

Chia sẻ: Mucnang222 Mucnang222 | Ngày: | Loại File: PDF | Số trang:91

Thêm vào BST

Báo xấu

51
lượt xem 8
download

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

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. Mời các bạn cùng tham khảo phần 1 bài giảng Thiết kế và đánh giá thuật toán dưới đây.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Thiết kế và đánh giá thuật toán: Phần 1 - ĐH Sư Phạm Kỹ Thuật Nam Định

BỘ LAO ĐỘNG - THƯƠNG BINH VÀ XÃ HỘI TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT NAM ĐỊNH tËp bµi gi¶ng thiÕt kÕ vµ ®¸nh gi¸ thuËt to¸n MÃ SỐ TB2012-02-06 BIÊN SOẠN: PHẠM CAO HÀO NAM ĐỊNH 2012
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. i
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 ii
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 iii
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 iv
v
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ả. 1
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 2
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 ... 3
* 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) if (biểu thức) khối lệnh 1 khối lệnh 1 /* Dạng một */ else khối lệnh 2 /* Dạng hai */ Sự lồng nhau của các toán tử if : 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 4
khối lệnh 2 ....... case nk khối lệnh k [ default khối lệnh k+1] } Với ni là các số nguyên, hằng ký tự hoặc biểu thức hằng. Các ni cần có giá trị khác nhau. Đoạn chương trình nằm giữa các dấu { } gọi là thân của toán tử switch. default là một thành phần không bắt buộc phải có trong thân của switch. * Cấu trúc lặp với toán tử while : Toán tử while dùng để xây dựng chu trình lặp dạng : while (biểu thức) Lệnh hoặc khối lệnh; Như vậy toán tử while gồm một biểu thức và thân chu trình. Thân chu trình có thể là một lệnh hoặc một khối lệnh. Hoạt động của chu trình như sau : Máy xác định giá trị của biểu thức, tuỳ thuộc giá trị của nó máy sẽ chọn cách thực hiện như sau : Nếu biểu thức có giá trị 0 (biểu thức sai), máy sẽ ra khỏi chu trình và chuyển tới thực hiện câu lệnh tiếp sau chu trình trong chương trình. Nếu biểu thức có giá trị khác không (biểu thức đúng), máy sẽ thực hiện lệnh hoặc khối lệnh trong thân của while. Khi máy thực hiện xong khối lệnh này nó lại thực hiện xác định lại giá trị biểu thức rồi làm tiếp các bước như trên. * Cấu trúc lặp với toán tử for : Toán tử for dùng để xây dựng cấu trúc lặp có dạng sau : for (biểu thức 1; biểu thức 2; biểu thức 3) Lệnh hoặc khối lệnh ; Toán tử for gồm ba biểu thức và thân for. Thân for là một câu lệnh hoặc một khối lệnh viết sau từ khoá for. Bất kỳ biểu thức nào trong ba biểu thức trên có thể 5
vắng mặt nhưng phải giữ dấu ; Thông thường biểu thức 1 là toán tử gán để tạo giá trị ban đầu cho biến điều khiển, biểu thức 2 là một quan hệ logic biểu thị điều kiện để tiếp tục chu trình, biểu thức ba là một toán tử gán dùng để thay đổi giá trị biến điều khiển. Hoạt động của toán tử for : Toán tử for hoạt động theo các bước sau : Xác định biểu thức 1 Xác định biểu thức 2 Tuỳ thuộc vào tính đúng sai của biểu thức 2 để máy lựa chọn một trong hai nhánh : Nếu biểu thức 2 có giá trị 0 (sai), máy sẽ ra khỏi for và chuyển tới câu lệnh sau thân for. Nếu biểu thức 2 có giá trị khác 0 (đúng), máy sẽ thực hiện các câu lệnh trong thân for. Tính biểu thức 3, sau đó quay lại bước 2 để bắt đầu một vòng mới của chu trình. * Cấu trúc do-while Khác với các toán tử while và for, việc kiểm tra điều kiện kết thúc đặt ở đầu chu trình, trong chu trình do while việc kiểm tra điều kiện kết thúc đặt cuối chu trình. Như vậy thân của chu trình bao giờ cũng được thực hiện ít nhất một lần. do Lệnh hoặc khối lệnh; while (biểu thức) ; Hoạt động của chu trình như sau : Máy thực hiện các lệnh trong thân chu trình. Khi thực hiện xong tất cả các lệnh trong thân của chu trình, máy sẽ xác định giá trị của biểu thức sau từ khoá while rồi quyết định thực hiện như sau : Nếu biểu thức đúng (khác 0) máy sẽ thực hiện lặp lại khối lệnh của chu trình lần thứ hai rồi thực hiện kiểm tra lại biểu thức như trên. Nếu biểu thức sai (bằng 0) máy sẽ kết thúc chu trình và chuyển tới thực hiện lệnh đứng sau toán tử while. 6
Những điều lưu ý với toán tử while ở trên hoàn toàn đúng với do while. * Câu lệnh break Câu lệnh break cho phép ra khỏi các chu trình với các toán tử for, while, do while và switch. Khi có nhiều chu trình lồng nhau, câu lệnh break sẽ đưa máy ra khỏi chu trình bên trong nhất chứa nó không cần điều kiện gì. * Câu lệnh continue : Trái với câu lệnh break, lệnh continue dùng để bắt đầu một vòng mới của chu trình chứa nó. Trong while và do while, lệnh continue chuyển điều khiển về thực hiện ngay phần kiểm tra, còn trong for điều khiển được chuyển về bước khởi đầu lại (tức là bước : tính biểu thức 3, sau đó quay lại bước 2 để bắt đầu một vòng mới của chu trình). Lệnh continue chỉ áp dụng cho chu trình chứ không áp dụng cho switch. 1.4. Thiết kế thuật toán 1.4.1. Modul hoá và thiết kế từ trên xuống Các bài toán giải được trên máy tính ngày càng phức tạp và đa dạng. Các thuật toán giải chúng ngày càng có quy mô lớn đòi hỏi nhiều thời gian và công sức của nhiều người. Tuy nhiên công việc sẽ đơn giản hơn nếu như ta chia bài toán ra thành các bài toán nhỏ. Điều đó cũng có nghĩa là nếu coi bài toán là modul chính thì cần chia thành các modul con. Đến lượt mình các modul con lại phân rã thành các modul con thích hợp... Như vậy việc tổ chức lời giải thể hiện theo một cấu trúc phân cấp. Chiến thuật giải bài toán như vậy là “chia để trị”, thể hiện chiến thuật đó ta dùng thiết kế từ trên xuống. Đó là cách nhìn nhận vấn đề một cách tổng quát, đề cập đến các công việc chính, sau đó mới bổ sung dần các chi tiết. 1.4.2. Phƣơng pháp làm mịn dần (tinh chỉnh từng bƣớc) Đầu tiên thuật toán được trình bày dưới dạng ngôn ngữ tự nhiên thể hiện ý chính công việc. Các bước sau sẽ chi tiết hóa dần tương ứng với các công việc nhỏ hơn. Đó là các bước làm mịn dần đặc tả thuật toán và hướng về ngôn ngữ lập trình mà ta dự định cài đặt. Quá trình thiết kế và phát triển thuật toán sẽ thể hiện dần từ ngôn ngữ tự nhiên, sang ngôn ngữ mã giả rồi đến ngôn ngữ lập trình, và đi từ mức “làm cái gì“đến “làm như thế nào”. 7
1.4.3. Một số kỹ thuật thiết kế Trên cơ sở lý thuyết máy Turing, người ta chia được các bài toán thành 2 lớp không giao nhau : Lớp giải được bằng thuật toán, và lớp không giải được bằng thuật toán. Đối với lớp các bài toán giải được bằng thuật toán, dựa vào các đặc trưng của quá trình thiết kế của thuật toán, ta có thể chỉ ra một số các kỹ thuật thiết kế thuật toán cơ bản sau đây : 1) Kỹ thuật chia để trị Chia bài toán thành các bài toán đủ nhỏ, giải các bài toán nhỏ rồi tổng hợp kết quả lại . 2) Kỹ thuật quay lui Tìm kiếm theo ưu tiên. Đối với mỗi bước thuật toán, ưu tiên theo độ rộng hay chiều sâu để tìm kiếm. Chẳng hạn thuật toán giải bài toán 8 hậu. 3) Kỹ thuật tham lam Ý tưởng là : Xác định trật tự xử lý để có lợi nhất, Sắp xếp dữ liệu theo trật tự đó, rồi xử lý dữ liệu theo trật tự đã nêu. Công sức bỏ ra là tìm ra trật tự đó. Chẳng hạn thuật toán tìm cây khung nhỏ nhất. 4) Kỹ thuật nhánh và cận Trong quá trình tìm kiếm lời giải, ta phân hoạch tập các phương án của bài toán ra thành hai hay nhiều tập con được biểu diễn như là các nút của cây tìm kiếm và cố gắng bằng phép đánh giá cận cho các nút, tìm cách loại bỏ các nhánh của cây mà ta biết chắc không chứa phương án tối ưu. 5) Kỹ thuật Quy hoạch động Kỹ thuật quy hoạch động dựa vào một nguyên lý, gọi là nguyên lý tối ưu của Bellman : “ Nếu lời giải của bài toán là tối ưu thì lời giải của các bài toán con cũng tối ưu ”. Kỹ thuật này tổ chức tìm kiếm lời giải theo kiểu từ dưới lên. Xuất phát từ các bài toán con nhỏ và đơn giản nhất, tổ hợp các lời giải của chúng để có lời giải của bài toán con lớn hơn...và cứ như thế cuối cùng được lời giải của bài toán ban đầu. 8
1.5. Phân tích thuËt toán 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: - Thuật toán đơn giản - Thuật toán thực hiện nhanh 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 thuật toán đơn giản là quan trọng. 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ì 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 thuật toán thực hiện nhanh 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. Hơn nữa khối lượng dữ liệu lớn mà dung lượng bộ nhớ lại có giới hạn thì không thể bỏ qua yêu cầu về tiết kiệm bộ nhớ được. Tuy nhiên cân đối giữa yêu cầu về thời gian và không gian không mấy khi có được một giải phấp trọn vẹn. Sau đây ta sẽ chỉ chú ý đến việc phân tích thời gian thực hiện thuật toán. 1.5.1. Thêi gian thùc hiÖn thuËt toán Một phương pháp để xác định hiệu quả thời gian thực hiện của một thuật toán là lập trình nó và đo lường thời gian thực hiện của hoạt động trên một máy tính xác định đối với tập hợp được chọn lọc các dữ liệu vào. Thời gian thực hiện không chỉ phụ thuộc vào thuật toán mà còn phụ thuộc vào tập các chỉ thị của máy tính, chất lượng của máy tính và kĩ xảo của người lập trình. Sự thi hành cũng có thể điều chỉnh để thực hiện tốt trên tập đặc biệt các dữ liệu vào được chọn. Ðể vượt qua các trở ngại này, các nhà khoa học máy tính đã chấp nhận tính phức tạp của thời gian được tiếp cận như một sự đo lường cơ bản sự thực thi của thuật toán. Thuật ngữ tính hiệu quả sẽ đề cập đến sự đo lường này và đặc biệt đối với sự phức tạp thời gian trong trường hợp xấu nhất. Nói chung thì thời gian thực hiện thuật toán không chỉ phụ thuộc vào kích thước mà còn phụ thuộc vào tính chất của dữ liệu vào. Nghĩa là dữ liệu vào có cùng kích thước nhưng thời gian thực hiện giải thuật có thể khác nhau. Chẳng hạn chương trình sắp xếp dãy số nguyên tăng dần, khi ta cho vào dãy có thứ tự thì thời gian thực hiện khác với khi ta cho vào dãy chưa có thứ tự, hoặc khi ta cho vào một 9
dãy đã có thứ tự tăng thì thời gian thực hiện cũng khác so với khi ta cho vào một dãy đã có thứ tự giảm. Vì vậy thường ta coi T(n) là thời gian thực hiện chương trình trong trường hợp xấu nhất trên dữ liệu vào có kích thước n, tức là: T(n) là thời gian lớn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n. Để đánh giá thời gian thực hiện thuật toán người ta tìm cách đánh giá độc lập với các yếu tố bên ngoài như máy tính hay các yếu tố liên quan đến máy tính. Cách đánh giá như vậy dẫn tới khái niệm về cấp độ lớn của thời gian thực hiện thuật toán hay độ phức tạp tính toán của thuật toán. 1.5.2. Độ phức tạp tính toán của thuật toán Nếu thời gian thực hiện một thuật toán là T(n) =cn2 (với c là hằng số, n là kích thước dữ liệu đầu vào) thì ta nói: Độ phức tạp tính toán của thuật toán này có cấp là n2 (hay cấp độ lớn của thời gian thực hiện thuật toán là n2) và ta ký hiệu: T(n) = O(n2) (ký hiệu chữ O lớn) Một cách tổng quát có thể định nghĩa: Một hàm f(n) được xác định là O(g(n)) và viết là f(n) =O(g(n)) và được gọi là cấp g(n) nếu tồn tại các hằng số c và n0 sao cho: f(n) ≤ cg(n) khi n ≥ n0 nghĩa là f(n) bị chặn trên bởi một hằng số nhân với g(n), với mọi giá trị của n tăng từ một điểm nào đó. Thông thường các hàm thể hiện độ phức tạp tính toán của thuật toán có dạng : log2n, n, nlog2, n2, n3, 2n, n!, nn Sau đây là bảng giá trị của một số hàm đó Log2n n nlog2n n2 n3 2n 0 1 0 1 1 2 1 2 2 4 8 4 2 4 8 16 64 16 3 8 24 64 512 256 4 16 64 256 40963 65536 5 32 160 1024 32768 2.147.483.648 Hình 1.1. Bảng giá trị của một số hàm số Các hàm như 2n , n!, nn được gọi là hàm loại mũ. Một thuật toán mà thời gian 10
thực hiện của nó có cấp là các hàm loại mũ thì tốc độ rất chậm. Các hàm như n3 , n2, nlog2n, n, log2n được gọi là các hàm loại đa thức. Một thuật toán mà thời gian thực hiện có độ phức tạp là một hàm đa thức thì chấp nhận được tức là có thể cài đặt để thực hiện, còn các thuật toán có độ phức tạp hàm mũ thì phải tìm cách cải tiến thuật toán. Các quy tắc xác định độ phức tạp của thuật toán: Xác định độ phức tạp tính toán của một thuật toán bất kỳ có thể dẫn tới những bài toán phức tạp. Tuy nhiên, trong thực tế, đối với một số thuật toán ta cũng có thể phân tích được bằng một số quy tắc đơn giản. * Quy tắc tổng: Giả sử T1(n) và T2(n) là độ phức tạp tính toán của hai đoạn chương trình P1 và P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)) thì độ phức tạp tính toán khi thực hiện P1 và tiếp theo là P2 sẽ là: T1(n) + T2(n) = O(max (f(n),g(n)) Chứng minh: Vì T1(n) = O(f(n)); T2(n) = O(g(n)) nên theo định nghĩa tồn tại các hằng số dương c1 , n1 và c2 , n2 sao cho: T1(n) ≤ c1  f(n), với mọi n > n1 T2(n) ≤ c2  g(n) với mọi n > n2. Chọn c = c1 + c2; n0 = max {n1, n2}. Khi đó: T1(n) + T2(n)  c1  f(n) + c2  g(n)  c  max(f(n), g(n)) , với mọi n > n0 . Do vậy: O(f(n)) + O(g(n)) = O(max(f(n), g(n))). Ví dụ 1.1. Trong một chương trình có 3 bước thực hiện mà độ phức tạp tính toán từng bước lần lượt là O(n2), O(n3) và O(nlog2n) thì độ phức tạp tính toán hai bước đầu là O(max (n2, n3) = O(n3). Độ phức tạp tính toán của chương trình sẽ là: O(max(n3, nlog2n)) = O(n3). Nhận xét: Từ quy tắc này có thể nhận thấy rằng: nếu g(n) ≤ f(n) với mọi n ≥ n0 thì: O(f(n)+g(n)) = O(f(n)). Chẳng hạn: O(n4+n2) = O(n4) O(n + log2n) = O(n). 11
* Quy tắc nhân: Giả sử T1(n) và T2(n) là độ phức tạp tính toán của hai đoạn chương trình P1 và P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)) thì độ phức tạp tính toán khi P1 và P2 lồng nhau sẽ là: T1(n).T2(n) = O(f(n).g(n)) Chứng minh: Ta có: T1(n) = O(f(n)), T2(n) = O(g(n) theo định nghĩa tồn tại các hằng số dương c1 , n1và c2 , n2 sao cho: T1(n) ≤ c1  f(n), với mọi n > n1 T2(n) ≤ c2  g(n) với mọi n > n2. Chọn c = c1 * c2; n0 = max {n1, n2}. Khi đó: T1(n).T2(n)  c1  f(n)  c2  g(n) = c  (f(n) g(n)). Do vậy: T1(n).T2(n) = O(f(n).g(n)). Ví dụ 1.2. Câu lệnh gán : x = x+1 có thời gian thực hiện bằng c (hằng số) nên được đánh giá là O(1). Câu lệnh: for ( i=1; i
Ví dụ 1.3. Giải thuật tính giá trị của ex theo công thức gần đúng: ex = 1 + x/1! +x2/2! + …+ xn/n! với x và n cho trước EXP1(); { scanf(x) ; S =1; for (i=1;i
Bây giờ độ phức tạp tính toán lại là: T(n) = O(n). Vì phép gán p=p*x/i chỉ thực hiện n lần. Ví dụ 1.4. Thuật toán sắp xếp kiểu nổi bọt void Bubble(a) { for(i=1;i=i+1; j--) if (a[j-1]>a[j]) { tg:= a[j-1]; a[j-1] := a[j]; a[j]:= tg; } } Trong thuật toán ta coi phép so sánh (a[j-1]>a[j]) là phép toán tích cực. Phép toán này nằm trong vòng lặp for(j=n; j>=i+1; j--) nên nó được thực hiện (n-i) lần. Vòng lặp for(j=n; j>=i+1; j--) nằm trong vòng lặp for(i=1;ia[j]) sẽ là: n 1 n( n  1 ) ( n  i )  i 1 2 Nên độ phức tạp tính toán của thuật toán là O(n2). Chú ý: Ta biết rằng thời gian thực hiện thuật toán không phải chỉ phụ thuộc vào kích thước dữ liệu mà còn phụ thuộc vào tình trạng dữ liệu nhập nữa. Chẳng hạn, khi xếp tăng dần một dãy các số nguyên mà dãy các so nguyên đĩ đã có sẵn thứ tự tăng dần, hoặc ngược lại, hoặc ngẫu nhiên. Lúc đó khi phân tích thời gian thực hiện thuật toán ta sẽ phải xét tới: đối với mọi dữ liệu vào có kích thước n thì T(n) trong trường hợp tốt nhất, xấu nhất là như thế nào? T(n) trung bình? Việc xác định T(n) trung bình thường khó và phức tạp đòi hỏi những công cụ toán học đặc biệt, hơn nữa việc tính trung bình có thể có nhiều cách quan niệm khác nhau. Trong trường hợp T(n) khó xác định người ta thường đánh giá thuật toán qua giá trị xấu nhất của T(n) 14