Đăng ký Đăng nhập
Trang chủ Một số phương pháp chứng minh tính đúng của thuật toán và ứng dụng...

Tài liệu Một số phương pháp chứng minh tính đúng của thuật toán và ứng dụng

.PDF
68
230
111

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ---------------------- Bế Thị Hƣơng MỘT SỐ PHƢƠNG PHÁP CHỨNG MINH TÍNH ĐÚNG CỦA THUẬT TOÁN VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội – Năm 2015 1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------------- Bế Thị Hƣơng MỘT SỐ PHƢƠNG PHÁP CHỨNG MINH TÍNH ĐÚNG CỦA THUẬT TOÁN VÀ ỨNG DỤNG Chuyên ngành: Cơ sở Toán học cho Tin học Mã số: 60460110 LUẬN VĂN THẠC SĨ KHOA HỌC NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. NGUYỄN THỊ HỒNG MINH Hà Nội – Năm 2015 LỜI CẢM ƠN Lời đầu tiên em xin chân thành cảm ơn các thầy giáo, cô giáo giảng dạy lớp cao học Cơ sở Toán học cho Tin học, Khoa Toán – Cơ – Tin học, Trƣờng Đại học Khoa học Tự nhiên – ĐHQGHN khóa 2012 – 2014. Các thầy cô đã rất nhiệt tình, tâm huyết trong giảng dạy cho em học tập, nghiên cứu bổ sung đƣợc thêm nhiều kiến thức mới quan trọng, hữu ích trong nghiên cứu và trong công tác giảng dạy ở trƣờng THPT chuyên. Đồng thời kịp nhận ra và sửa đổi, bổ sung những kiến thức mình còn hiểu chƣa thật chính xác giúp tăng cƣờng năng lực và phát triển tƣ duy trong nghiên cứu khoa học. Đặc biệt, em gửi lời cảm ơn chân thành và sâu sắc tới cô giáo TS.Nguyễn Thị Hồng Minh (Khoa Sau Đại học – ĐHQGHN). Cô đã giảng dạy cùng với hƣớng dẫn luận văn cho em một cách rất khoa học, tận tâm, chu đáo và chi tiết để em có thể hoàn thành luận văn một cách tốt nhất. Cảm ơn gia đình đã cho em một chỗ dựa vững chắc để hoàn thành khóa học cũng nhƣ hoàn thành luận văn này. Mặc dù đã có rất nhiều cố gắng trong việc nghiên cứu khoa học để hoàn thành luận văn tuy nhiên do hạn chế cá nhân về mặt thời gian nên em khó có thể tránh đƣợc những thiếu sót. Kính mong thầy cô và các bạn đóng góp ý kiến quý báu để hoàn chỉnh luận văn này hơn nữa. MỤC LỤC MỞ ĐẦU ............................................................................................................................... 1 CHƢƠNG 1. TỔNG QUAN VỀ PHÂN TÍCH THUẬT TOÁN .......................................... 4 1.1. Một số khái niệm cơ bản ............................................................................................. 4 1.1.1. Bài toán ................................................................................................................ 4 1.1.2. Thuật toán (Algorithm) ........................................................................................ 5 1.1.3. Cấu trúc dữ liệu (Data Structure) ....................................................................... 10 1.1.4. Chƣơng trình (Program) .................................................................................... 10 1.2. Một số phƣơng pháp thiết kế thuật toán ................................................................... 11 1.2.1. Kỹ thuật đệ quy .................................................................................................. 11 1.2.2. Phƣơng pháp chia để trị (Divide and Conquer) ................................................. 14 1.2.3. Phƣơng pháp quay lui (Backtracking) ............................................................... 15 1.2.4. Phƣơng pháp nhánh cận ..................................................................................... 17 1.2.5. Phƣơng pháp quy hoạch động (Dynamic Programming ) ................................. 19 1.2.6. Phƣơng pháp tham lam (Greedy Method) ......................................................... 21 1.3. Phân tích thuật toán................................................................................................... 22 1.3.1. Tính đúng đắn của thuật toán ............................................................................. 22 1.3.2. Độ phức tạp thuật toán ....................................................................................... 23 a) Độ phức tạp về mặt thời gian............................................................................... 23 b) Độ phức tạp về mặt không gian ........................................................................... 23 CHƢƠNG 2. MỘT SỐ PHƢƠNG PHÁP CHỨNG MINH TÍNH ĐÚNG CỦA THUẬT TOÁN .................................................................................................................................. 25 2.1. Các chiến lƣợc chứng minh tính đúng thuật toán ..................................................... 25 2.2. Các phƣơng pháp chứng minh tính đúng (Correctness proofs) ................................ 26 2.2.1. Phƣơng pháp quy nạp (induction)...................................................................... 26 a) Phƣơng pháp quy nạp toán học............................................................................ 26 b) Chứng minh tính đúng của thuật toán bằng phƣơng pháp quy nạp ..................... 27 c) Một số ví dụ ......................................................................................................... 27 2.2.2. Phƣơng pháp bất biến vòng lặp (loop invariant).................................................... 33 a) Chứng minh tính đúng của thuật toán bằng phƣơng pháp bất biến vòng lặp .......... 33 b) Các đặc trƣng của bất biến vòng lặp ....................................................................... 35 c) Một số ví dụ ............................................................................................................. 35 CHƢƠNG 3. ỨNG DỤNG CHỨNG MINH TÍNH ĐÚNG CỦA MỘT SỐ THUẬT TOÁN ............................................................................................................................................. 44 3.1. Bài toán: Dãy con đơn điệu tăng dài nhất ............................................................. 44 3.2. Bài toán: Chia kẹo................................................................................................. 53 3.3. Bài toán Cây bao trùm nhỏ nhất (Minimum spanning tree). ................................ 54 KẾT LUẬN.......................................................................................................................... 61 MỞ ĐẦU Thế kỷ XXI là thế kỷ của tri thức hiện đại, một nền tri thức không thể không kể đến công cụ hỗ trợ đắc lực của máy tính điện tử trong mọi lĩnh vực cuộc sống. Mặc dù công nghệ chế tạo ngày càng phát triển và phát triển với tốc độ nhanh nhƣng để sử dụng máy tính điện tử một cách hiệu quả cao thì thuật toán (Algorithm) là thành phần luôn luôn quan trọng và không thể thiếu đƣợc kể từ khi máy tính điện tử ra đời. Theo lịch sử toán học nguồn gốc của từ thuật toán “Algorithm” là bắt nguồn từ “Algorism” tên của một nhà bác học nổi tiếng ngƣời Arập là Abu Jafar Mohammed ibn Musâ al Khowârizmi. (Phiên âm của từ al Khowârizmi chính là Algorism). Ông là ngƣời đã viết hai quyển sách nổi tiếng là “Sơ lƣợc về các phép tính” và “Về hệ đếm ấn độ” vào khoảng năm 850. Đây là những quyển sách giáo khoa nổi tiếng về toán học. Lịch sử đã ghi nhận ngƣời đƣợc coi là nhà lập trình đầu tiên trên thế giới là nữ bá tƣớc Ada Lovelace (10/12/1815 - 27/11/1852), tên khai sinh là Augusta Ada Byron. Các nhà khoa học về sau cho rằng thuật toán (viết năm 1842) của Ada Lovelace là những thuật toán máy tính đầu tiên do con ngƣời lập ra, vì nó lần đầu tiên thể hiện rõ từng bƣớc phát triển logic, đặc trƣng hoạt động xác định dành riêng cho máy tính. Với lịch sử lâu đời của thuật toán đã đƣợc nghiên cứu và phát triển cho tới tận ngày nay và sẽ vẫn còn tiếp tục đƣợc nghiên cứu và phát triển hơn nữa. Khi lập trình câu hỏi luôn luôn đƣợc đặt ra là thuật toán đƣợc thiết kế hoặc thuật toán đƣợc sử dụng có đúng hay không? Điều này đảm bảo cho một chƣơng trình máy tính thực hiện có cho kết quả đúng hay không? (Chƣa kể đến các kỹ năng của ngƣời lập trình). Vì vậy việc xây dựng một thuật toán tốt để giải bài toán đã cho 1 là bƣớc quan trọng có thể nói là quan trọng nhất trong việc giải một bài toán trên máy tính điện tử. Để đánh giá một thuật toán là tốt có rất nhiều tiêu chí trong đó không thể bỏ qua tính đúng của thuật toán. Và đây cũng là nội dung chính của luận văn này theo đề tài nghiên cứu: “Một số phƣơng pháp chứng minh tính đúng của thuật toán và ứng dụng”. Luận văn nhằm tìm hiểu, nghiên cứu, tổng hợp phƣơng pháp chứng minh tính đúng của thuật toán. Cấu trúc luận văn gồm 3 chƣơng, nội dung chính nhƣ sau: Chương 1. Tổng quan về phân tích thuật toán. Chƣơng này nhằm tổng hợp lại một số kiến thức chung về bài toán, thuật toán, cấu trúc dữ liệu, chƣơng trình và kiến thức về phân tích thuật toán. Gồm các định nghĩa, khái niệm và các ví dụ để minh họa. Trong chƣơng này còn tổng hợp lại một số phƣơng pháp thiết kế thuật toán thƣờng sử dụng trong thực tế. Nhƣ kỹ thuật đệ quy, phƣơng pháp chia để trị, phƣơng pháp quay lui, phƣơng pháp nhánh cận, phƣơng pháp quy hoạch động và phƣơng pháp tham lam. Chương 2. Một số phương pháp chứng minh tính đúng của thuật toán. Nội dung chƣơng này gồm các chiến lƣợc chứng minh tính đúng của thuật toán; các phƣơng pháp cụ thể để chứng minh tính đúng của thuật toán nhƣ phƣơng pháp quy nạp và phƣơng pháp bất biến vòng lặp. Đây cũng chính là điểm mới của luận văn. Trong đó, phƣơng pháp quy nạp chứng minh cho các thuật toán đệ quy, phƣơng pháp bất biến vòng lặp chứng minh cho các thuật toán không đệ quy. Đối với mỗi phƣơng pháp trình bày về đặc điểm, phƣơng pháp chung đồng thời nêu một số ví dụ về thuật toán và chứng minh tính đúng của các thuật toán đó. Đối với những thuật toán phức tạp có chứa cả đệ quy và lặp thì cần kết hợp khéo 2 léo cả hai phƣơng pháp chứng minh tính đúng của thuật toán là quy nạp và bất biến vòng lặp. Chương 3. Ứng dụng chứng minh tính đúng của một số thuật toán. Nghiên cứu một số bài toán có sử dụng các thuật toán kinh điển, thƣờng sử dụng và vận dụng lý thuyết của chƣơng 2 để chứng minh tính đúng của các thuật toán đó. Nhƣ bài toán dãy con đơn điệu tăng dài nhất; Chia kẹo; Cây bao trùm nhỏ nhất. 3 CHƢƠNG 1. TỔNG QUAN VỀ PHÂN TÍCH THUẬT TOÁN Để khẳng định đƣợc một thuật toán là tốt là một điều không dễ dàng gì. Thật vậy, để đánh giá một thuật toán tốt ta cần rất nhiều kỹ thuật từ thiết kế, phân tích đến đánh giá một thuật toán. Ở chƣơng này đề cập tổng quát đến các vấn đề trong phân tích thuật toán và một số thuật toán cơ bản thƣờng dùng trong khoa học tính toán hiện đại. 1.1. Một số khái niệm cơ bản 1.1.1. Bài toán Khoa học máy tính ngày nay giải quyết rất nhiều vấn đề trong thực tế trong nhiều lĩnh vự khác nhau, những vấn đề đó ta thƣờng gọi là bài toán. Tuy nhiên bài toán ở đây không phải là một trƣờng hợp cụ thể mà là bài toán mang tính tổng quát bao gồm hầu nhƣ tất cả các khả năng có thể của thế giới thực trong vấn đề cần giải quyết. Nhƣ vậy, nói một cách dễ hiểu thì bài toán là việc nào đó ta muốn máy tính thực hiện. Có thể là một yêu cầu đơn giản nhƣ in ra một dòng chữ trên 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 hoặc kiểm tra một số là chẵn hay lẻ,... Nhƣng cũng có thể là giải quyết những vấn đề rất phức tạp nhƣ tìm đƣờng đi trong mê cung, tìm đƣờng đi ngắn nhất, tìm cây bao trùm,... Điểm quan trọng đầu tiên khi giải một bài toán trên máy tính đó là cần xác định rõ những gì đã biết input (dữ liệu vào) và kết quả cần thu đƣợc output (dữ liệu ra) và phân tích mối quan hệ giữa hai yếu tố đó. Sau đây là một số ví dụ về bài toán:  Bài toán 1.1: Kiểm tra tính nguyên tố của một số nguyên dƣơng cho trƣớc.  Input: Số nguyên dƣơng N.  Output: Xác định N là số nguyên tố hoặc N không là số nguyên tố. 4  Bài toán 1.2: Giải phƣơng trình bậc hai ax2+bx+c=0 (a≠0).  Input: Các số thực a, b, c (a≠0).  Output: Các nghiệm x thỏa mãn phƣơng trình đã cho hoặc thông báo không có nghiệm.  Bài toán 1.3: Tìm ƣớc số chung lớn nhất của hai số nguyên dƣơng a, b.  Input: Hai số nguyên dƣơng a, b.  Output: Ƣớc số chung lớn nhất của a và b.  Bài toán 1.4: Xác định vị trí của phần tử có giá trị bằng số nguyên x trong một dãy số nguyên a1, a2,..., an.  Input: Số n; dãy số nguyên a1, a2, ..., an và số nguyên x.  Output: Chỉ số i nếu x=ai và là 0 nếu x không có mặt trong dãy.  Bài toán 1.5. Cho đồ thị vô hƣớng G=(V, E). Tìm đƣờng đi ngắn nhất từ đỉnh u tới đỉnh v của đồ thị G.  Input: Đồ thị vô hƣớng G=(V, E) và hai đỉnh u,v.  Output: Xác định đƣờng đi có độ dài ngắn nhất d=(u=v1,v2,...,vn=v) (với đỉnh vi thuộc V, cung (vi, vi+1) thuộc E).  Bài toán 1.6. Sắp xếp một dãy các số cho trƣớc thành dãy không giảm.  Input: Số n và dãy gồm n số < a1, a2, …, an>.  Output: Một hoán vị < a'1, a'2, …, a'n > của chuỗi đầu vào thỏa mãn: a'1  a'2  … a'n. 1.1.2. Thuật toán (Algorithm) Để giải một bài toán trên máy tính sau khi đã xác định rõ ràng về bài toán việc quan trọng nhất là phải đƣa ra một thuật toán tốt, thuật toán này có thể là một thiết kế mới hoặc lựa chọn một thuật toán đã có. Thuật toán là để biểu diễn về cách giải một bài toán trên máy tính. 5 Một bài toán có thể có nhiều cách giải nhƣng một thuật toán chỉ giải một bài toán mà thôi. Đến hiện nay thì đã có nhiều định nghĩa về thuật toán và sau đây là một lựa chọn định nghĩa thuật toán: Định nghĩa: Thuật toán (Algorithm) để giải một bài toán là một dãy hữu hạn các thao tác đƣợ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 ấy, từ dữ liệu vào có thể là một giá trị hoặc một tập giá trị (input) của bài toán ta nhận đƣợc một giá trị hoặc một tập giá trị còn gọi là dữ liệu ra (output) của bài toán đó. Để thuật toán đƣợc rõ ràng, chính xác, dễ hiểu, dễ đọc hơn ngƣời ta đƣa ra các phƣơng pháp biểu diễn thuật toán. Gồm có ba phƣơng pháp biểu diễn thuật toán nhƣ sau:  Ngôn ngữ tự nhiên (Natural languages): Dùng ngôn ngữ tự nhiên để liệt kê từng bƣớc của thuật toán. Phƣơng pháp này không có các quy tắc chung do đó ngƣời viết và ngƣời đọc dễ dàng thực hiện đƣợc mà không cần phải nắm đƣợc những quy tắc. Nhƣng viết thuật toán theo cách này thƣờng dài dòng, không thể hiện đƣợc rõ cấu trúc thuật toán và đôi lúc có thể gây khó hiểu hoặc hiểu nhầm đối với ngƣời đọc.  Sơ đồ khối (Flowcharts): là công cụ trực quan để thể hiện thuật toán. Sơ đồ khối biểu diễn đƣợc sự phân cấp của thuật toán cũng nhƣ trình tự thực hiện thuật toán. Đặc biệt phù hợp với những thuật toán phức tạp, khó theo dõi quá trình xử lý. Tuy nhiên, phƣơng pháp biểu diễn này có nhƣợc điểm là cồng kềnh, cần không gian biểu diễn lớn hơn các phƣơng pháp khác. Trong sơ đồ khối thƣờng sử dụng một số khối và cung để biểu diễn thuật toán nhƣ sau:  Hình oval: Thể hiện thao tác nhập, xuất dữ liệu;  Hình thoi: Thể hiện thao tác so sánh, chỉ có hai nhánh logic là đúng hoặc sai;  Hình chữ nhật: Thể hiện các phép gán, các thao tác tính toán; 6  Cung có hƣớng: Thể hiện trình tự thực hiện các thao tác, thao tác này nối tiếp thao tác kia theo hƣớng mũi tên.  Nút nối: Để nối các phần khác nhau của sơ đồ khối lại với nhau. Thƣờng biểu diễn bằng hình tròn, bên trong có kí hiệu để biết là nút nối nào.  Nút nối trang: Với các sơ đồ khối lớn cần biểu diễn trên nhiều trang thì biểu diễn thêm bằng nút nối trang.  Giả mã (Pseudocode): Sử dụng cú pháp của một ngôn ngữ lập trình nào đó kết hợp với ngôn ngữ tự nhiên để thể hiện thuật toán. Với giả mã ngƣời lập trình tận dụng đƣợc các định nghĩa và cấu trúc của ngôn ngữ lập trình. Đây cũng là phƣơng pháp chính đƣợc chọn lựa để biểu diễn các thuật toán trong luận văn này. Sau đây là ví dụ về thuật toán và ba cách để biểu diễn thuật toán tƣơng ứng của bài toán 1 đã nêu ở mục 1.1.1 Phân tích bài toán: Theo định nghĩa số nguyên tố thì số nguyên dƣơng N là số nguyên tố nếu N chỉ có đúng 2 ƣớc số là 1 và chính nó. Nên ta có với N là số nguyên dƣơng thì:  Nếu N=1 thì N không là số nguyên tố;  Nếu 1 [ N ] thì thông báo N là nguyên tố rồi kết thúc; Bƣớc 6. Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc; Bƣớc 7. i = i+1 rồi quay lại bƣớc 5.  Thuật toán biểu diễn bằng sơ đồ khối: Nhập N nguyên dƣơng Đúng N=1? Sai N<4? Đúng Sai i=2 i>  N  ?   Sai Sai N chia hết cho i ? i=i+1 Đúng Thông báo N không là số nguyên tố rồi kết thúc. 8 Đúng Thông báo N là số nguyên tố và kết thúc.  Thuật toán biểu diễn bằng giả mã: Ngto(N):int  //Hàm kiểm tra số N có phải nguyên tố hay không if (N=1) return 0; else if (N<4) return 1 else for i=2 to [sqrt(N)] do if (N chia hết cho i) then return 0; return 1; End. Các tính chất của thuật toán: Khi viết thuật toán cần chú ý đến những tính chất quan trọng sau đây:  Tính tổng quát (Generality): Thuật toán áp dụng cho mọi trƣờng hợp của bài toán (nhiều bộ dữ liệu vào) chứ không phải chỉ cho một trƣờng hợp riêng lẻ (một bộ dữ liệu vào) nói một cách khác là áp dụng cho một lớp các bài toán cùng loại;  Tính dừng (Stationarity): Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác, mặc dù đối với các bài toán phức tạp số lần này có thể là rất lớn;  Tính xác định (Definiteness): Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để đƣợc thực hiện tiếp theo (do đó luôn thực hiện đƣợc). 9  Tính hiệu quả (Effectiveness): Đƣợc đánh giá dựa trên một số tiêu chuẩn nhƣ là sử dụng không gian bộ nhớ và thời gian thực hiện thuật toán. Đây cũng chính là tính chất quan trọng để đánh giá và lựa chọn thuật toán để giải quyết một bài toán trong thực tế.  Tính đúng đắn (Generalliness): Sau khi thuật toán kết thúc ta phải nhận đƣợc output cần tìm. Tính đúng là tính chất hiển nhiên khi giải một bài toán muốn đạt đƣợc nhất nhƣng cũng là tính chất khó đạt tới nhất. Vì không phải lúc nào cũng tìm đƣợc lời giải đúng cho bài toán đã đặt ra. 1.1.3. Cấu trúc dữ liệu (Data Structure) Cấu trúc dữ liệu là một cách lƣu trữ dữ liệu trong máy tính sao cho việc khai thác chúng đƣợc hiệu quả hơn. Trong thiết kế chƣơng trình việc lựa chọn cấu trúc dữ liệu rất quan trọng. Vì mỗi loại cấu trúc dữ liệu phù hợp với một số loại ứng dụng khác nhau. Một cấu trúc dữ liệu đƣợc thiết kế cho phép thực hiện nhiều phép toán, tiết kiệm tài nguyên, ít thời gian xử lý và sử dụng không gian bộ nhớ càng ít thì càng tốt. Các cấu trúc dữ liệu đƣợc triển khai bằng cách sử dụng các kiểu dữ liệu, các tham chiếu và các phép toán trên cấu trúc dữ liệu đó đƣợc cung cấp bởi một ngôn ngữ lập trình cụ thể. Sự liên hệ giữa cấu trúc dữ liệu và thuật toán rất chặt chẽ, thuật toán cần đƣợc thao tác trên các cấu trúc dữ liệu nào đó và các cấu trúc dữ liệu sẽ đƣợc xử lý bởi thuật toán nào đó. Và vì không có một cấu trúc duy nhất nào có thể tốt cho mọi mục đích hay phù hợp với mọi thuật toán do đó điều quan trọng khi nghiên cứu cấu trúc dữ liệu là cần phải biết sức mạnh cũng nhƣ giới hạn của cấu trúc dữ liệu đó để sử dụng cho phù hợp, hiệu quả. 1.1.4. Chƣơng trình (Program) Chƣơng trình = Thuật toán + Cấu trúc dữ liệu. Chƣơng trình là sự thể hiện bằng một ngôn ngữ lập trình cụ thể một thuật toán đã cho đƣợc thể hiện trên một cấu trúc dữ liệu xác định. Việc lựa chọn cấu trúc dữ liệu phù hợp với thuật toán 10 hoặc ngƣợc lại lựa chọn thuật toán phù hợp với cấu trúc dữ liệu cụ thể còn phụ thuộc vào mục đích của chƣơng trình, kỹ năng ngƣời lập trình và khả năng của ngôn ngữ lập trình cụ thể. 1.2. Một số phương pháp thiết kế thuật toán Ngày nay có nhiều phƣơng pháp thiết kế thuật toán đã đƣợc nghiên cứu và sử dụng trong công nghệ phần mềm. Có những bài toán có thể giải đƣợc bằng thuật toán nhƣng cũng những bài toán chƣa có thuật toán hoặc chỉ có thuật toán cho lời giải tƣơng đối chấp nhận đƣợc. Trong luận văn này nghiên cứu về các phƣơng pháp thiết kế thuật toán và ứng dụng cho các bài toán có thuật toán để giải. 1.2.1. Kỹ thuật đệ quy Đệ quy là một khái niệm cơ bản trong toán học và tin học. Ta nói một đối tƣợng là đệ quy nếu nó đƣợc định nghĩa qua chính nó hoặc một đối tƣợng cùng dạng với chính nó bằng quy nạp. Ý tƣởng của kỹ thuật đệ quy đó là chia bài toán cần giải quyết thành nhiều bài toán nhỏ hơn, việc chia này thực hiện cho đến khi bài toán con có lời giải và lời giải này thƣờng là tƣờng minh và tƣơng đối đơn giản. Ví dụ: Kí hiệu |S| là số các phần tử của tập hữu hạn S. Nếu S= thì |S|=0 Ngƣợc lại S≠ thì tất có một phần tử xS khi đó |S|=|S\{x}|+1. Khái niệm giải thuật đệ quy: Một bài toán T đƣợc thực hiện bằng giải thuật của một bài toán T’ có dạng giống nhƣ T thì giải thuật đó gọi là giải thuật đệ quy. Bài toán T’ tuy có dạng giống bài toán T nhƣng T’ theo một nghĩa nào đó phải là bài toán nhỏ hơn T. Bài toán T’ phải dễ giải hơn bài toán T và việc giải bài toán T’ không cần dùng đến T. 11 Do đó phƣơng pháp chung sử dụng kỹ thuật đệ quy để giải một bài toán là ta chia bài toán đó thành các bài toán con đơn giản hơn cùng loại. Phƣơng pháp này còn đƣợc gọi là kỹ thuật lập trình chia để trị. Chính nó là chìa khóa để thiết kế nhiều giải thuật quan trọng, là cơ sở của phƣơng pháp quy hoạch động. Sau đây là một số ví dụ về bài toán mang bản chất đệ quy:  Ví dụ 1: Bài toán tính n giai thừa. Cho n là một số tự nhiên (n0). Hãy tính giai thừa của n. Biết rằng 0!=1 và n!=(n-1)!n. Phân tích: Theo giả thiết, ta có : n! = (n-1)!n. Nhƣ vậy : Để tính n! ta cần phải tính (n-1)! Để tính (n-1)! ta phải tính (n-2)! ................................................... Cứ nhƣ vậy, cho tới khi gặp trƣờng hợp 0!.  Ví dụ 2: Dãy Fibonacci Dãy Fibonacci là dãy vô hạn các số tự nhiên. Số Fibonacci thứ n, ký hiệu F(n), đƣợc định nghĩa nhƣ sau: F(n) = 1, nếu n=1 hoặc n=2; F(n) = F(n-1) + F(n-2), nếu n3. Yêu cầu: Tính số fibonacci thứ n với n nguyên dƣơng cho trƣớc. Phân tích: Với n3 : Đế tính F(n) ta phải tính F(n-1) và F(n-2). 12 Để tính F(n-1) ta lại phải tính F(n-2) và F(n-3), và để tính F(n-2) ta phải tính F(n-3) và F(n-4). ......................................................... Cứ nhƣ vậy cho đến khi n=1 và n=2. Đặc trƣng của các bài toán có thể giải bằng đệ quy:  Các bài toán phụ thuộc tham số;  Ứng với các giá trị đặc biệt nào đó của tham số thì bài toán có lời giải (trƣờng hợp suy biến). Phần này quan trọng vì nó quyết định tính dừng của thuật toán;  Trong trƣờng hợp tổng quát bài toán có thể quy về dạng tƣơng tự với một bộ giá trị mới của tham số và sau hữu hạn lần sẽ dẫn tới trƣờng hợp suy biến. Phối hợp lời giải của các bài toán con để có đƣợc lời giải cho bài toán ban đầu cần giải quyết. Lƣợc đồ giải thuật đệ quy: Dequy(Tn) ; if (Tn=T0) //Trƣờng hợp suy biến ; else //Trƣờng hợp tổng quát Dequy(Tn-1); endif; End. Ví dụ: Sau đây là thuật toán Tính n! (n0). 13 S(n): int ; //Hàm đệ quy tính giá trị n giai thừa if (n=0) then else S=1 S=n*S(n-1); End. Giả sử tính 4!, thuật toán thực hiện nhƣ sau: 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 1! 1! = 1 * 0! 0! = 1 Kết quả 4! = (((1*1)*2)*3)*4 = 24. 1.2.2. Phƣơng pháp chia để trị (Divide and Conquer) Trong thực tế có nhiều thuật toán hữu ích đƣợc sử dụng có bản chất đệ quy, tức là trong thuật toán có lời gọi đến chính nó một hoặc nhiều lần để giải bài toán tƣơng tự nhƣng với kích thƣớc dữ liệu vào nhỏ hơn. Phƣơng pháp chia để trị có tƣ tƣởng là chia bài toán ban đầu thành các bài toán con tƣơng tự. Các bài toán con tiếp tục đƣợc chia nhỏ hơn, cứ chia liên tiếp nhƣ vậy cho tới khi gặp bài toán con đã có lời giải hoặc có thể dễ dàng đƣa ra lời giải. Sau đó lần lƣợt giải các bài toán con này và kết hợp các kết quả lại với nhau ta thu đƣợc kết quả cần tìm của bài toán ban đầu. Lƣợc đồ tổng quát thuật toán chia để trị với mô hình đệ quy nhƣ sau: Chia_tri(A, x) ; //Tìm nghiệm x của bài toán A if (A đủ nhỏ) then Giai(A) //Giải bài toán con đủ nhỏ else ; for i=1 to n do Chia_tri(Ai, xi); 14 ; endelse; End. Ví dụ Số Fibonacci: Bài toán Số Fibonacci đƣợc cho bởi công thức sau: F1 =1  F2 =1 F =F + F (n  3)  n n-1 n-2 Hãy tính số Fibonacci thứ n? Thuật toán chia để trị sau đây sử dụng hàm F(n) để tính số Fibonacci thứ n (n là số nguyên dƣơng) dựa vào F(n-1) và F(n-2): F(n):int ; //Hàm tính số Fibonacci thứ n. if n2 then else F=1 F=F(n-1)+F(n-2); End. 1.2.3. Phƣơng pháp quay lui (Backtracking) Tƣ tƣởng của thuật toán quay lui đó là tìm nghiệm của bài toán bằng cách xem xét tất cả các phƣơng án có thể. Ta có thể thử duyệt các phƣơng án cho đến khi tìm thấy phƣơng án đúng còn gọi là phƣơng pháp thử sai. Với tốc độ xử lí nhanh của máy vi tính thì phƣơng pháp này có thể giải quyết đƣợc nhiều bài toán tuy nhiên nếu kích thƣớc bài toán quá lớn thì nó trở nên không phù hợp. Bởi vì nếu kích thƣớc bài toán lớn thì kéo theo thời gian duyệt các phƣơng án và độ phức tạp về mặt không gian cũng lớn và có thể lớn đến mức nào đó không thể chấp nhận đƣợc. Do đó phƣơng pháp này thƣờng chỉ hữu dụng với các bài toán có kích thƣớc nhỏ. Không mất tổng quát, việc tìm nghiệm của nhiều bài toán có thể quy về việc tìm véc tơ hữu hạn X=  x1 , x 2 , ..., x n , ... độ dài véc tơ có thể xác định trƣớc 15
- Xem thêm -

Tài liệu liên quan