intTypePromotion=1

Luận văn Thạc sĩ Khoa học: Một số phương pháp chứng minh tính đúng của thuật toán và ứng dụng

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

0
132
lượt xem
15
download

Luận văn Thạc sĩ Khoa học: Một số phương pháp chứng minh tính đúng của thuật toán và ứng dụng

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

Để đá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.

Chủ đề:
Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học: Một số phương pháp chứng minh tính đúng của thuật toán và ứng dụng

  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 LUẬN VĂN THẠC SĨ KHOA HỌC 1
  2. Hà Nội – Năm 2015 2
  3. ĐẠ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
  4. Hà Nội – Năm 2015 4
  5. 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.
  6. 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)                                                                         .....................................................................       11  1.1.4. Chương trình (Program)                                                                                        ....................................................................................       11  1.2. Một số phương pháp thiết kế thuật toán                                                                    ................................................................       12  1.2.1. Kỹ thuật đệ quy                                                                                                    ................................................................................................       12  1.2.2. Phương pháp chia để trị (Divide and Conquer)                                                    ................................................       15  1.2.3. Phương pháp quay lui (Backtracking)                                                                   ...............................................................       16  1.2.4. Phương pháp nhánh cận                                                                                        ....................................................................................       19  1.2.5. Phương pháp quy hoạch động (Dynamic Programming )                                    ................................       21  1.2.6. Phương pháp tham lam (Greedy Method)                                                             .........................................................       22  1.3. Phân tích thuật toán                                                                                                      ..................................................................................................       24  1.3.1. Tính đúng đắn của thuật toán                                                                               ...........................................................................       24  1.3.2. Độ phức tạp thuật toán                                                                                         .....................................................................................       25  a) Độ phức tạp về mặt thời gian                                                                                ............................................................................       25  b) Độ phức tạp về mặt không gian                                                                            ........................................................................       25 CHƯƠNG 2. MỘT SỐ PHƯƠNG PHÁP CHỨNG MINH TÍNH ĐÚNG CỦA THUẬT    TOÁN                                                                                                                                       ...................................................................................................................................       27  2.1. Các chiến lược chứng minh tính đúng thuật toán                                                       ...................................................       27  2.2. Các phương pháp chứng minh tính đúng (Correctness proofs)                                   ...............................       28  2.2.1. Phương pháp quy nạp (induction)                                                                         .....................................................................       29  a) Phương pháp quy nạp toán học                                                                              .........................................................................       29  b) Chứng minh tính đúng của thuật toán bằng phương pháp quy nạp                      ..................       29  c) Một số ví dụ                                                                                                            ........................................................................................................       30  2.2.2. Phương pháp bất biến vòng lặp (loop invariant)                                                     .................................................       35  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          36 .....      b) Các đặc trưng của bất biến vòng lặp                                                                        ...................................................................       38
  7.  c) Một số ví dụ                                                                                                                ............................................................................................................       38 CHƯƠNG   3.   ỨNG   DỤNG   CHỨNG   MINH   TÍNH   ĐÚNG   CỦA   MỘT   SỐ   THUẬT   TOÁN                                                                                                                                       ...................................................................................................................................       48  3.1. Bài toán: Dãy con đơn điệu tăng dài nhất                                                               ...........................................................       48  3.2. Bài toán: Chia kẹo                                                                                                    ................................................................................................       57  3.3. Bài toán Cây bao trùm nhỏ nhất (Minimum spanning tree).                                   ...............................       59  KẾT LUẬN                                                                                                                              ..........................................................................................................................       66  TÀI LIỆU THAM KHẢO                                                                                                        ....................................................................................................       68 7
  8. 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   1
  9. 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 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  2
  10. 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 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
  11. 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. 4
  12. Output: Xác định N là số nguyên tố hoặc N không là số nguyên tố. 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ố . Output: Một hoán vị  
  13. 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.  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: 6
  14. 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; 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
  15. Nếu N 4 thì N là số nguyên tố nếu N không có ước số từ 2 đến phần  nguyên căn bậc 2 của N, kí hiệu: � � � N �. Do đó ta có thuật toán như sau: Thuật toán biểu diễn bằng ngôn ngữ tự nhiên: Bước 1. Nhập số nguyên dương N; Bước 2. Nếu N=1 thì thông báo N không nguyên tố rồi kết thúc; Bước 3. Nếu N [ 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: 8
  16. Nhập N  nguyên dương Đúng N = 1 ?  Sai N � �? Thông báo N N Đúng là số nguyên tố  � � Sai và kết thúc. Sai i = i + 1  N chia hết  cho  i ?   Đúng Thông báo N  không là số nguyên  tố rồi 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 9
  17. if (N
  18. 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 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ể. 11
  19. 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. 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.  12
  20. 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). Để 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). 13
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2