ĐẠ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ử xS 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 (n0). 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 n3.
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 n3 :
Đế 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! (n0).
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 n2 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 -
Chi phí hỗ trợ lưu trữ và tải về cho tài liệu này là đ. Bạn có muốn hỗ trợ không?
|