THUẬT TOÁN – ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

Chia sẻ: Nguyễn Văn Toàn | Ngày: | Loại File: DOC | Số trang:29

Thêm vào BST

Báo xấu

153
lượt xem 31
download

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

Từ thuật toán (Algorithm) xuất phát từ tên một nhà toán học người Trung Á là Abu Abd - Allah ibn Musa al’Khwarizmi, thường gọi là al’Khwarizmi. Ông là tác giả một cuốn sách về số học, trong đó ông đã dùng phương pháp mô tả rất rõ ràng, mạch lạc cách giải những bài toán. Sau này, phương pháp mô tả cách giải toán của ông đã được xem là một chuẩn mực và được nhiều nhà toán học khác tuân theo. Từ algorithm ra đời dựa theo cách phiên âm tên của ông. Việc nghiên cứu về thuật toán có vai trò...

Chủ đề:

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

Lưu

Nội dung Text: THUẬT TOÁN – ĐỘ PHỨC TẠP CỦA THUẬT TOÁN

THUẬT TOÁN – ĐỘ PHỨC TẠP CỦA THUẬT TOÁN Mục lục THUẬT TOÁN – ĐỘ PHỨC TẠP CỦA THUẬT TOÁN....................................................................1 Mục lục..................................................................................................................................................1 1. THUẬT TOÁN...................................................................................................................................2 2. CÁC PHƯƠNG PHÁP BIỂU DIỄN THUẬT TOÁN...................................................................... 7 3. ĐỘ PHỨC TẠP CỦA THUẬT TOÁN............................................................................................12 4. PHÂN LOẠI VẤN ĐỀ - BÀI TOÁN...............................................................................................15 5. THUẬT TOÁN ĐỆ QUY.................................................................................................................17 6.THUẬT GIẢI.................................................................................................................................... 21 7. CÂU HỎI......................................................................................................................................... 27 8.Bài viết khác: SỰ PHÂN LỚP VẤN ĐỀ - BÀI TOÁN.................................................................. 28
1. THUẬT TOÁN Thuật toán là một khái niệm cơ sở của Toán học và Tin học. Hi ểu m ột cách đ ơn gi ản, thuật toán là một tập các hướng dẫn nhằm thực hiện một công vi ệc nào đó. Ð ối v ới vi ệc gi ải quyết một vấn đề - bài toán thì thuật toán có thể hi ểu là m ột t ập hữu hạn các hướng dẫn rõ ràng để người giải toán có thể theo đó mà giải quyết được vấn đề. Như vậy, thuật toán là m ột phương pháp thể hiện lời giải của vấn đề - bài toán. Tại sao lại là "Thuật toán" ? Từ thuật toán (Algorithm) xuất phát từ tên một nhà toán học người Trung Á là Abu Abd - Allah ibn Musa al’Khwarizmi, thường gọi là al’Khwarizmi. Ông là tác giả một cuốn sách về số học, trong đó ông đã dùng phương pháp mô tả rất rõ ràng, mạch lạc cách giải những bài toán. Sau này, phương pháp mô tả cách giải toán của ông đã được xem là một chuẩn mực và được nhiều nhà toán học khác tuân theo. Từ algorithm ra đời dựa theo cách phiên âm tên của ông. Việc nghiên cứu về thuật toán có vai trò rất quan trọng trong khoa học máy tính vì máy tính chỉ giải quyết được vấn đề khi đã có hướng dẫn giải rõ ràng và đúng. N ếu h ướng d ẫn gi ải sai hoặc không rõ ràng thì máy tính không thể giải đúng đ ược bài toán. Trong khoa h ọc máy tính, thuật toán được định nghĩa là một dãy hữu hạn các bước không mập mờ và có thể thực thi được, quá trình hành động theo các bước này phải dừng và cho được kết quả như mong muốn. Số bước hữu hạn của thuật toán và tính chất dừng của nó được gọi chung là tính h ữu hạn. Số bước hữu hạn của thuật toán là một tính chất khá hiển nhiên. Ta có thể tìm ở đâu một lời giải vấn đề - bài toán có vô số bước giải ? Tính "không mập mờ" và "có thể thực thi được" gọi chung là tính xác định. Giả sử khi nhận một lớp học mới, Ban Giám hiệu yêu cầu giáo viên ch ủ nhi ệm ch ọn l ớp trưởng mới theo các bước sau : 1. Lập danh sách tất các học sinh trong lớp. 2. Sắp thứ tự danh sách học sinh. 3. Chọn học sinh đứng đầu danh sách để làm lớp trưởng. Khi nhận được thông báo này, giáo viên chắc chắn sẽ rất b ối r ối vì không hi ểu là trong danh sách học sinh cần có những thông tin gì? Danh sách ch ỉ c ần h ọ tên, hay c ần thêm ngày tháng năm sinh? Có cần thêm điểm trung bình không? Yêu cầu 2 lại càng gây nhi ều th ắc m ắc. C ần ph ải sắp xếp danh sách theo chiều tăng dần ho ặc giảm dần ? Sắp theo ch ỉ tiêu gì ? Theo tên, theo ngày tháng năm sinh hay theo điểm trung bình chung, ...Gi ả sử sắp theo điểm trung bình thì n ếu có hai học sinh cùng điểm trung bình thì học sinh nào sẽ sắp trước, học sinh nào sẽ sắp sau ? ... Hướng dẫn ở trên vi phạm tính chất "không mập mờ" của thuật toán. Nghĩa là, có quá nhiều thông tin còn thiếu để làm cho các bước 1,2 được hiểu đúng và hiểu theo một nghĩa duy nhất. Nếu sửa lại một chút ít thì hướng dẫn trên sẽ trở nên rõ ràng hơn rất nhi ều và có th ể gọi là m ột thuật toán chọn lớp trưởng ! 1. Lập danh sách tất các học sinh trong lớp theo hai thông tin: Họ và Tên; Ðiểm trung bình cuối năm.
2. Sắp hạng học sinh theo điểm trung bình theo thứ tự giảm dần (từ điểm cao đến điểm thấp). Hai h ọc sinh có cùng điểm trung bình sẽ có cùng hạng. 3. Nếu chỉ có một học sinh có hạng nhất thì chọn học sinh đó làm lớp trưởng. Trường hợp có nhiều học sinh đồng hạng nhất thì chọn học sinh có điểm môn Toán cao nhất làm lớp trưởng. Nếu vẫn còn nhiều hơn một học sinh đồng hạng nhất và có cùng điểm môn Toán cao nhất thì tiến hành bốc thăm. Ở đây chúng ta cần phân biệt mập mờ và sự chọn lựa có quyết định . Mập mờ là thiếu thông tin hoặc có nhiều chọn lựa nhưng không đủ điều kiện để quyết định . Còn chọn lựa có quyết định là hoàn toàn xác định duy nhất trong đi ều ki ện cụ thể c ủa v ấn đề. Ch ẳng h ạn trong vấn đề chọn lớp trưởng ở trên, bước 3 thể hiện một sự lựa chọn có quyết đ ịnh. T ất nhiên, khi chưa lập danh sách, chưa xếp hạng theo điểm trung bình thì giáo viên không th ể bi ết đ ược s ẽ chọn lớp trưởng theo cách nào. Nhưng khi đã sắp xong danh sách thì ch ỉ có m ột ph ương án ch ọn duy nhất. Tính "thực thi được" cũng là một tính chất khá hiển nhiên. Rõ ràng nếu trong "thuật toán" tồn tại một bước không thể thực thi được thì làm sao ta có được kết quả đúng như ý mu ốn? Tuy nhiên, cần phải hiểu là "thực thi được" xét trong điều kiện hiện tại của bài toán. Chẳng hạn, khi nói "lấy căn bậc hai của một số âm" là không thể thực thi được nếu miền xác đ ịnh c ủa bài toán là số thực, nhưng trong miền số phức thì thao tác "lấy căn bậc hai của một số âm" là hoàn toàn thực thi được. Tương tự, nếu ta chỉ đường cho một người đi xe máy đ ến m ột b ưu đi ện nh ưng con đường ta chỉ là đường cụt, đường cấm hoặc đường ngược chiều thì người đi không th ể đi đ ến bưu điện được. Tính "dừng" là tính chất dễ bị vi phạm nhất, thường là do sai sót khi trình bày thu ật toán. Dĩ nhiên, mọi thuật toán đều nhằm thực hiện một công việc nào đó nên sau m ột thời gian thi hành hữu hạn thì thuật toán phải cho chúng ta kết quả mong muốn. Khi không thỏa tính chất này, ta nói rằng "thuật toán" bị lặp vô tận hoặc bị quẩn. Ðể tính tổng các số nguyên dương lẻ trong khoảng từ 1 đến n ta có thuật toán sau : B1. Hỏi giá trị của n. B2. S = 0 B3. i = 1 B4. Nếu i = n+1 thì sang bước B8, ngược lại sang bước B5 B5. Cộng thêm i vào S B6. Cộng thêm 2 vào i B7. Quay lại bước B4. B8. Tổng cần tìm chính là S. Ta chú ý đến bước B4. Ở đây ta muốn kết thúc thuật toán khi giá trị của i v ượt quá n. Thay vì viết là "nếu i lớn hơn n" thì ta thay bằng điều ki ện "n ếu i b ằng n+1" vì theo toán h ọc "i = n+1" thì suy ra "i lớn hơn n". Nhưng điều ki ện "i=n+1" không phải lúc nào cũng đ ạt đ ược. Vì ban
đầu i = 1 là số lẻ, sau mỗi bước, i được tăng thêm 2 nên i luôn là số l ẻ. N ếu n là s ố ch ẵn thì n+1 là một số lẻ nên sau một số bước nhất định, i sẽ bằng n+1. Tuy nhiên, n ếu n là m ột s ố l ẻ thì n+1 là một số chẵn, do i là số lẻ nên dù có qua bao nhiêu b ước đi chăng n ữa, i v ẫn khác n+1. Trong trường hợp đó, thuật toán trên sẽ bị quẩn. Tính "đúng" là một tính chất khá hiển nhiên nhưng là tính chất khó đạt tới nh ất. Th ực vậy, khi giải quyết một vấn đề-bài toán, ta luôn luôn mong muốn lời giải của mình s ẽ cho k ết quả đúng nhưng không phải lúc nào cũng đạt được. Mọi học sinh khi làm bài ki ểm tra đ ều mu ốn bài làm của mình có đáp số đúng nhưng trên thực tế, trong l ớp h ọc ch ỉ có m ột s ố h ọc sinh nh ất định là có khả năng đưa ra lời giải đúng! Thuật toán thì cứng nhắc ! Các tính chất của thuật toán rất chặt chẽ và cứng nhắc. Nhưng điều đó cũng có nghĩa là khả năng giải quyết vấn đề theo kiểu thuật toán cũng bị giới hạn. Sau này, người ta đã "làm mềm" đi hai tính chất quan trọng của thuật toán là tính xác định và tính đúng để giải quyết những vấn đề phức tạp hơn mà với các tính chất chặt chẽ của thuật toán thì không thể giải quyết được. Ðó là các thuật toán đệ quy và thuật giải. Ta sẽ tìm hiểu về đi ều này ngay trong các mục 4 và 5 của chương này. Các đặc trưng khác của thuật toán Bên cạnh 3 đặc trưng chính là xác định, hữu hạn và đúng, thu ật toán còn có thêm 3 đ ặc trưng phụ khác. 1. Ðầu vào và đầu ra (input/output) : mọi thuật toán, dù có đơn giản đến mấy cũng phải nhận dữ liệu đầu vào, xử lý nó và cho ra kết quả cuối cùng. 2. Tính hiệu quả (effectiveness) : tính hiệu quả của thuật toán được đánh giá dựa trên một số tiêu chuẩn như khối lượng tính toán, không gian và th ời gian khi thu ật toán đ ược thi hành. Tính hiệu quả của thuật toán là một yếu tố quyết định đ ể đánh giá, ch ọn l ựa cách gi ải quy ết v ấn đề-bài toán trên thực tế. Có rất nhiều phương pháp để đánh giá tính hi ệu qu ả c ủa thu ật toán. Trong mục 3 của chương , ta sẽ tìm hiểu một tiêu chuẩn được dùng rộng rãi là đ ộ ph ức t ạp c ủa thuật toán. 3. Tính tổng quát (generalliness) : thuật toán có tính tổng quát là thuật toán phải áp dụng được cho mọi trường hợp của bài toán chứ không phải chỉ áp dụng được cho m ột số tr ường hợp riêng lẻ nào đó. Chẳng hạn giải phương trình bậc hai sau đây bằng Delta đ ảm b ảo đ ược tính chất này vì nó luôn giải được với mọi giá trị số thực a,b,c bất kỳ. Tuy nhiên, không phải thu ật toán nào cũng đảm bảo được tính tổng quát. Trong thực tế, có lúc người ta ch ỉ xây d ựng thu ật toán cho một dạng đặc trưng của bài toán mà thôi. Thuật toán giải phương trình bậc hai ax2+bx+c=0 (a?0) 1. Yêu cầu cho biết giá trị của 3 hệ số a, b, c 2. Nếu a=0 thì 2.1. Yêu cầu đầu vào không đảm bảo.
2.2. Kết thúc thuật toán. 3. Trường hợp a khác 0 thì 3.1. Tính giá trị D = b2-4ac 3.2. Nếu D > 0 thì 3.2.1. Phương trình có hai nghiệm phân biệt x1 và x2 3.2.2. Giá trị của hai nghiệm được tính theo công thức sau 3.2.3. Kết thúc thuật toán. 3.3. Nếu D = 0 thì 3.3.1. Phương trình có nghiệm kép x0 3.3.2. Giá trị của nghiệm kép là 3.3.3. Kết thúc thuật toán 3.4. Nếu D < 0 thì 3.4.1. Phương trình vô nghiệm. 3.4.2. Kết thúc thuật toán. Thuật toán tìm hộp có trọng lượng nặng nhất Vấn đề : Có n hộp có khối lượng khác nhau và một cái cân dĩa. Hãy chỉ ra cách cân để tìm được hộp có trọng lượng nặng nhất. Vấn đề này là thể hi ện c ủa m ột bài toán t ổng quát : Cho một tập hợp A hữu hạn và một thứ tự toàn phần trên A. Hãy xây dựng thu ật toán tìm ph ần t ử lớn nhất của A. Bài toán trong toán học có vẻ rất phức tạp nhưng m ột th ể hi ện trên th ực t ế l ại rất dễ hiểu, và cách giải quyết cũng đơn giản. Từ đó ta có thể dễ dàng suy ra cách gi ải bài toán tổng quát. 1. Nếu chỉ có 1 hộp (n=1) thì 1.1. Hộp đó chính là hộp nặng nhất. 1.2. Kết thúc thuật toán. 2. Ngược lại nếu có từ hai hộp trở lên (n>1)
2.1. Chọn hai hộp bất kỳ và đặt lên bàn cân. 2.2. Giữ lại hộp nặng hơn, cất hộp nhẹ hơn sang chỗ khác. 3. Nếu còn hộp chưa được cân thực hiện các bước sau, nếu không còn hộp nào n ữa, sang bước 5. 3.1. Chọn một hộp bất kỳ và để lên dĩa cân còn trống. 3.2. Giữ lại hộp nặng hơn, cất hộp nhẹ hơn sang chỗ khác. 4. Trở lại bước 3. 5. Hộp còn lại trên cân chính là hộp nặng nhất. Kết thúc. Thuật toán Euclid tìm ước số chung lớn nhất Bài toán : Cho hai số nguyên dương a và b. Tìm ước số chung lớn nhất của a và b. 1. Yêu cầu cho biết giá trị của a, b. 2. a0 = a 3. b0 = b 4. i = 0 5. Nếu ai khác bi thì thực hiện các thao tác sau, ngược lại qua bước 7. 5.1 Tăng i lên 1. 5.2. Nếu ai-1 > bi-1 thì ai = ai-1 - bi-1 bi = bi-1 5.3. Ngược lại bi = bi-1 - ai-1 ai = ai-1 6. Trở lại bước 5. 7. Ước số chung lớn nhất của a, b là ai .
2. CÁC PHƯƠNG PHÁP BIỂU DIỄN THUẬT TOÁN Khi chứng minh hoặc giải một bài toán trong toán học, ta th ường dùng nh ững ngôn t ừ toán học như : "ta có", "điều phải chứng minh", "giả thuyết", ... và sử dụng nh ững phép suy lu ận toán học như phép suy ra, tương đương, ...Thuật toán là một phương pháp thể hi ện lời giải bài toán nên cũng phải tuân theo một số quy tắc nhất định. Ðể có thể truyền đạt thuật toán cho người khác hay chuyển thuật toán thành chương trình máy tính, ta phải có phương pháp biểu diễn thu ật toán. Có 3 phương pháp biểu diễn thuật toán : 1. Dùng ngôn ngữ tự nhiên. 2. Dùng lưu đồ-sơ đồ khối (flowchart). 3. Dùng mã giả (pseudocode). 2.1. Ngôn ngữ tự nhiên Trong cách biểu diễn thuật toán theo ngôn ngữ tự nhiên, người ta sử d ụng ngôn ng ữ thường ngày để liệt kê các bước của thuật toán (Các ví dụ v ề thu ật toán trong m ục 1 c ủa ch ương sử dụng ngôn ngữ tự nhiên). Phương pháp biểu di ễn này không yêu cầu người viết thuật toán cũng như người đọc thuật toán phải nắm các quy tắc. Tuy vậy, cách biểu di ễn này th ường dài dòng, không thể hiện rõ cấu trúc của thuật toán, đôi lúc gây hi ểu l ầm ho ặc khó hi ểu cho ng ười đọc. Gần như không có một quy tắc cố định nào trong việc th ể hi ện thu ật toán b ằng ngôn ng ữ t ự nhiên. Tuy vậy, để dễ đọc, ta nên viết các bước con lùi vào bên ph ải và đánh s ố b ước theo quy tắc phân cấp như 1, 1.1, 1.1.1, ... Bạn có thể tham khảo lại ba ví dụ trong m ục 1 c ủa chương đ ể hiểu cách biểu diễn thuật toán theo ngôn ngữ tự nhiên. 2.2. Lưu đồ - sơ đồ khối Lưu đồ hay sơ đồ khối là một công cụ trực quan để di ễn đạt các thu ật toán. Bi ểu di ễn thuật toán bằng lưu đồ sẽ giúp người đọc theo dõi được sự phân c ấp các tr ường h ợp và quá trình xử lý của thuật toán. Phương pháp lưu đồ thường được dùng trong nh ững thu ật toán có tính r ắc rối, khó theo dõi được quá trình xử lý. Ðể biểu diễn thuật toán theo sơ đồ khối, ta phải phân biệt hai lo ại thao tác. M ột thao tác là thao tác chọn lựa dựa theo một điều kiện nào đó. Chẳng hạn : thao tác "nếu a = b thì thực hiện thao tác B2, ngược lại thực hiện B4" là thao tác chọn lựa. Các thao tác còn lại không thuộc lo ại chọn lựa được xếp vào loại hành động. Chẳng hạn, "Chọn một hộp bất kỳ và để lên dĩa cân còn trống." là một thao tác thuộc loại hành động. 2.2.1. Thao tác chọn lựa (decision) Thao tác chọn lựa được biểu diễn bằng một hình thoi, bên trong ch ứa bi ểu th ức đi ều kiện.
2.2.2. Thao tác xử lý (process) Thao tác xử lý được biểu diễn bằng một hình chữ nhật, bên trong chứa nội dung xử lý. 2.2.3.Ðường đi (route) Khi dùng ngôn ngữ tự nhiên, ta mặc định hiểu rằng quá trình th ực hi ện sẽ lần l ượt đi t ừ bước trước đến bước sau (trừ khi có yêu cầu nhảy sang bước khác). Trong ngôn ng ữ l ưu đ ồ, do thể hiện các bước bằng hình vẽ và có thể đặt các hình vẽ này ở vị trí bất kỳ nên ta phải có phương pháp để thể hiện trình tự thực hiện các thao tác. Hai bước kế tiếp nhau được nối bằng một cung, trên cung có mũi tên để chỉ hướng thực hiện. Chẳng hạn trong hình dưới, trình tự thực hiện sẽ là B1, B2, B3. Từ thao tác chọn lựa có thể có đến hai hướng đi, m ột hướng ứng v ới đi ều ki ện th ỏa và một hướng ứng với điều kiện không thỏa. Do vậy, ta dùng hai cung xuất phát t ừ các đ ỉnh hình thoi, trên mỗi cung có ký hiệu Ð/Ðúng/Y/Yes để chỉ hướng đi ứng v ới đi ều ki ện th ỏa và ký hi ệu S/Sai/N/No để chỉ hướng đi ứng với điều kiện không thỏa.
2.2.4. Ðiểm cuối (terminator) Ðiểm cuối là điểm khởi đầu và kết thúc của thuật toán, được bi ểu di ễn bằng hình ovan, bên trong có ghi chữ bắt đầu/start/begin hoặc kết thúc/end. Ði ểm cu ối ch ỉ có cung đi ra (đi ểm khởi đầu) hoặc cung đi vào (điểm kết thúc). Xem lưu đồ thu ật toán gi ải ph ương trình b ậc hai ở trên để thấy cách sử dụng của điểm cuối. 2.2.5. Ðiểm nối (connector) Ðiểm nối được dùng để nối các phần khác nhau của một lưu đồ lại với nhau. Bên trong điểm nối, ta đặt một ký hiệu để biết sự liên hệ giữa các điểm nối.
2.2.6. Ðiểm nối sang trang (off-page connector) Tương tự như điểm nối, nhưng điểm nối sang trang được dùng khi lưu đồ quá lớn, ph ải vẽ trên nhiều trang. Bên trong điểm nối sang trang ta cũng đặt m ột ký hi ệu đ ể bi ết đ ược s ự liên hệ giữa điểm nối của các trang. Ở trên chỉ là các ký hiệu cơ bản và thường được dùng nhất. Trong thực tế, lưu đồ còn có nhiều ký hiệu khác nhưng thường chỉ dùng trong những lưu đồ lớn và phức tạp. Ðối với các thuật toán trong cuốn sách này, ta chỉ cần sử dụng các ký hiệu trên là đủ. 2.3. Mã giả Tuy sơ đồ khối thể hiện rõ quá trình xử lý và sự phân cấp các trường h ợp c ủa thuật toán nhưng lại cồng kềnh. Ðể mô tả một thuật toán nhỏ ta phải dùng m ột không gian r ất l ớn. H ơn nữa, lưu đồ chỉ phân biệt hai thao tác là rẽ nhánh (chọn lựa có điều ki ện) và xử lý mà trong th ực tế, các thuật toán còn có thêm các thao tác lặp (Chúng ta sẽ tìm hi ểu về thao tác lặp trong các bài sau). Khi thể hiện thuật toán bằng mã giả, ta sẽ vay mượn các cú pháp của một ngôn ngữ lập trình nào đó để thể hiện thuật toán. Tất nhiên, m ọi ngôn ngữ l ập trình đ ều có nh ững thao tác c ơ bản là xử lý, rẽ nhánh và lặp. Dùng mã gi ả vừa tận d ụng đ ược các khái ni ệm trong ngôn ng ữ l ập trình, vừa giúp người cài đặt dễ dàng n ắm bắt nội dung thuật toán. T ất nhiên là trong mã gi ả ta vẫn dùng một phần ngôn ngữ tự nhiên. Một khi đã vay mượn cú pháp và khái ni ệm c ủa ngôn ng ữ lập trình thì chắc chắn mã giả sẽ bị phụ thuộc vào ngôn ngữ l ập trình đó. Chính vì lý do này,
chúng ta chưa vội tìm hiểu về mã giả trong bài này (vì chúng ta ch ưa bi ết gì v ề ngôn ng ữ l ập trình!). Sau khi tìm hiểu xong bài về thủ tục - hàm bạn sẽ hiểu mã giả là gì ! Một đoạn mã giả của thuật toán giải phương trình bậc hai if Delta > 0 then begin x1=(-b-sqrt(delta))/(2*a) x2=(-b+sqrt(delta))/(2*a) xuất kết quả : phương trình có hai nghiệm là x1 và x2 end else if delta = 0 then xuất kết quả : phương trình có nghiệm kép là -b/(2*a) else {trường hợp delta < 0 } xuất kết quả : phương trình vô nghiệm * Các từ in đậm là các từ khóa của ngôn ngữ Pascal
3. ĐỘ PHỨC TẠP CỦA THUẬT TOÁN Một chương trình máy tính thường được cài đặt dựa trên m ột thuật toán đúng đ ể gi ải quyết bài toán hay vấn đề. Tuy nhiên, ngay cả khi thuật toán đúng, chương trình vẫn có thể không sử dụng được đối với một dữ liệu đầu vào nào đó vì thời gian để cho ra kết qu ả là quá lâu ho ặc sử dụng quá nhiều bộ nhớ (vượt quá khả năng đáp ứng của máy tính). Khi tiến hành phân tích thuật toán nghĩa là chúng ta tìm ra một đánh giá về thời gian và "không gian" cần thiết để thực hiện thuật toán. Không gian ở đây đ ược hi ểu là các yêu c ầu v ề b ộ nhớ, thiết bị lưu trữ, ... của máy tính để thuật toán có thể làm vi ệc. Vi ệc xem xét v ề không gian của thuật toán phụ thuộc phần lớn vào cách tổ chức dữ liệu c ủa thuật toán. Trong phần này, khi nói đến độ phức tạp của thuật toán, chúng ta chỉ đ ề c ập đến nh ững đánh giá v ề m ặt th ời gian mà thôi. Phân tích thuật toán là một công việc rất khó khăn, đòi hỏi phải có những hi ểu biết sâu sắc về thuật toán và nhiều kiến thức toán học khác. Ðây là công vi ệc mà không ph ải b ất c ứ người nào cũng làm được. Rất may mắn là các nhà toán học đã phân tích cho chúng ta độ phức tạp của hầu hết các thuật toán cơ sở (sắp xếp, tìm kiếm, các thuật toán số h ọc, ...). Chính vì v ậy, nhiệm vụ còn lại của chúng ta là hiểu được các khái ni ệm liên quan đ ến đ ộ ph ức t ạp c ủa thu ật toán. Ðánh giá về thời gian của thuật toán không phải là xác định thời gian tuyệt đối (chạy thuật toán mất bao nhiêu giây, bao nhiêu phút,...) để thực hiện thuật toán mà là xác đ ịnh mối liên quan giữa dữ liệu đầu vào (input) của thuật toán và chi phí (số thao tác, số phép tính c ộng,tr ừ, nhân, chia, rút căn,...) để thực hiện thuật toán. Sở dĩ người ta không quan tâm đ ến th ời gian tuy ệt đối của thuật toán vì yếu tố này phụ thuộc vào tốc độ của máy tính, mà các máy tính khác nhau thì có tốc độ rất khác nhau. Một cách tổng quát, chi phí thực hiện thuật toán là một hàm số phụ thuộc vào dữ liệu đầu vào : T = f(input) Tuy vậy, khi phân tích thuật toán, người ta thường chỉ chú ý đến mối liên quan giữa độ lớn của dữ liệu đầu vào và chi phí. Trong các thuật toán, độ lớn của dữ li ệu đầu vào thường được thể hiện bằng một con số nguyên n. Chẳng hạn : sắp xếp n con số nguyên, tìm con số lớn nhất trong n số, tính điểm trung bình của n học sinh, ... Lúc này, người ta thể hiện chi phí thực hiện thuật toán bằng một hàm số phụ thuộc vào n : T = f(n) Việc xây dựng một hàm T tổng quát như trên trong m ọi tr ường h ợp c ủa thu ật toán là một việc rất khó khăn, nhiều lúc không thể thực hiện được. Chính vì vậy mà người ta ch ỉ xây dựng hàm T cho một số trường hợp đáng chú ý nhất của thu ật toán, th ường là tr ường h ợp tốt nhất và xấu nhất. Chúng ta trở lại ví dụ về thuật toán tìm hộp nặng nhất trong n h ộp cho tr ước, nh ưng lần này ta làm việc trên một thể hiện khác của vấn đề. Ðây là m ột thu ật toán t ương đ ối đ ơn gi ản nên chúng ta có thể tiến hành phân tích được độ phức tạp. Trước khi phân tích độ ph ức t ạp, ta nhắc lại đôi điều về thuật toán này.
Tìm số lớn nhất trong một dãy số Bài toán : Cho một dãy số a có n phần tử a 1, a2, ...an. Hãy xây dựng thuật toán để tìm con số lớn nhất trong dãy a. Nhận xét 1. Nếu dãy chỉ có 1 phần tử thì phần tử đó là số lớn nhất. 2. Giả sử dãy có n phần tử và ta đã xác định được phần tử lớn nhất là amax . Nếu bổ sung thêm phần tử thứ an+1 vào dãy mà an+1 > amax thì an+1 chính là phần tử lớn nhất của dãy có n+1 phần tử. Trường hợp ngược lại, nghĩa là an+1 £ amax thì amax vẫn là phần tử lớn nhất của dãy có n+1 phần tử. Thuật toán 1. Ghi nhớ amax = a1. 2. i = 2. 3. Nếu (i £ n) thì thực hiện các bước sau, ngược lại sang bước 5. 3.1. Nếu (ai > amax ) thì 3.1.1. Ghi nhớ amax = ai . 3.2. Tăng i lên 1. 4. Trở lại bước 3. 5. Phần tử lớn nhất dãy a chính là amax .Kết thúc. Trong thuật toán trên, để đơn giản, ta chỉ xem chi phí là số l ần so sánh ở b ước 3.1 và số lần "ghi nhớ" trong bước 3.1.1. Trường hợp tốt nhất của thuật toán này xảy ra khi con s ố l ớn nhất nằm đầu dãy (amax= a1); trường hợp xấu nhất xảy ra khi con số lớn nh ất n ằm ở cu ối dãy (amax=an) và dãy được sắp xếp theo thứ tự tăng dần.
Dựa theo sơ đồ khối của thuật toán, ta nhận thấy rằng, trong m ọi tr ường h ợp c ủa bài toán, phép "ghi nhớ" ở bước 3.1 luôn được thực hi ện và số lần th ực hi ện là n-1 ( ứng v ới vi ệc xét từ phần tử a2 đến an). Ta gọi đây là chi phí cố định hoặc bất biến của thuật toán. Trường hợp tốt nhất : do amax = a1 suy ra, với mọi i ³ 2, a i< amax. Do đó, điều kiện ai>amax ở bước 3.1 luôn không thỏa nên bước 3.1.1 không bao giờ được thực hiện. Như vậy, chi phí chung cho trường hợp này chính là chi phí cố định của bài toán. T = f(n) = n-1 Trường hợp xấu nhất : Ta có : với mọi i>1, a i-1< ai (do định nghĩa dãy được sắp xếp tăng dần) nên đi ều ki ện ai>amax ở bước 3.1 luôn thỏa, bước 3.1.1 luôn được thực hiện. Như vậy, ngoài chi phí chung là n-1 phép so sánh, ta cần phải dùng thêm n-1 phép "ghi nhớ" ở bước 3.1.1. Nh ư vậy, t ổng chi phí c ủa trường hợp này là T = f(n) = 2(n-1)=2n-2
Ðịnh nghĩa Cho hai hàm f và g có miền xác định trong tập số tự nhiên . Ta viết f(n) = O(g(n)) và nói f(n) có cấp cao nhất là g(n) khi tồn tại hằng số C và k sao cho | f(n) | £ C.g(n) với mọi n > k Tuy chi phí của thuật toán trong trường hợp tốt nhất và xấu nhất có th ể nói lên nhi ều điều nhưng vẫn chưa đưa ra được một hình dung tốt nhất về độ phức tạp của thu ật toán. Ð ể có thể hình dung chính xác về độ phức tạp của thuật toán, ta xét đến một yếu tố khác là độ tăng của chi phí khi độ lớn n của dữ liệu đầu vào tăng. Theo định nghĩa ở trên, ta nhận thấy chi phí thấp nhất và l ớn nh ất c ủa thu ật toán tìm số lớn nhất đều bị chặn bởi O(n) (tồn tại hằng số C=10, k=1 để 2n-2 < 10n với mọi n>1). Một cách tổng quát, nếu hàm chi phí của thuật toán (xét trong m ột trường h ợp nào đó) bị chặn bởi O(f(n)) thì ta nói rằng thuật toán có độ phức tạp là O(f(n)) trong trường hợp đó. Như vậy, thuật toán tìm số lớn nhất có độ phức tạp trong trường hợp tốt nhất và xấu nhất đều là O(n). Người ta gọi các thuật toán có đ ộ ph ức t ạp O(n) là các thu ật toán có đ ộ ph ức tạp tuyến tính. Sau đây là một số "thước đo" độ phức tạp của thuật toán được sử dụng rộng rãi. Các độ phức tạp được sắp xếp theo thứ tự tăng dần. Nghĩa là m ột bài toán có đ ộ ph ức t ạp O(n k) sẽ phức tạp hơn bài toán có độ phức tạp O(n) hoặc O(logan). 4. PHÂN LOẠI VẤN ĐỀ - BÀI TOÁN Ðộ phức tạp của thuật toán chính là yếu tố cơ sở để phân lo ại vấn đề-bài toán. M ột cách tổng quát, mọi bài toán đều có thể chia làm 2 lớp l ớn là : gi ải đ ược và không gi ải đ ược. L ớp giải được chia làm 2 lớp con. Lớp con đầu tiên là các bài toán có độ phức tạp đa thức : nghĩa là bài toán có thể giải được bằng thuật toán có độ phức tạp đa thức (hay nói ng ắn g ọn : l ớp đa
thức) được xem là có lời giải thực tế. Lớp con thứ hai là những bài toán có độ phức tạp không phải là đa thức mà lời giải của nó được xem là thực tế chỉ cho những số liệu đầu vào có ch ọn l ựa cẩn thận và tương đối nhỏ. Cuối cùng là những bài toán thu ộc lo ại NP ch ưa th ể phân lo ại m ột cách chính xác là thuộc lớp bài toán có độ phức tạp đa thức hay có độ phức tạp không đa thức. 4.1. Lớp bài toán có độ phức tạp đa thức Các bài toán thuộc lớp này có độ phức tạp là O(n k) hoặc nhỏ hơn O(nk). Chẳng hạn như các bài toán có độ phức tạp là O(nlog2n) được xem là các bài toán thuộc lớp đa thức vì nlog 2n bị chặn bởi n2 ( nlog2n £ n2 với mọi n>0). Như vậy các bài toán có độ phức tạp hằng O(1), phức tạp tuyến tính O(n) và logarith O(nlogan) đều là các bài toán thuộc lớp đa thức. Còn các bài toán có độ phức tạp lũy thừa O(an) hoặc giai thừa O(n!) là không thuộc lớp đa thức. Tuy độ phức tạp chỉ là số đo về độ tăng của chi phí ứng với đ ộ tăng c ủa d ữ li ệu đ ầu vào nhưng nó cũng cho chúng ta có một đánh giá tương đối về th ời gian thi hành thu ật toán. Các thu ật toán thuộc lớp đa thức được xem là các bài toán có lời giải th ực t ế. Lời giải thực tế được hiểu rằng là chi phí về mặt thời gian và không gian cho vi ệc gi ải bài toán là chấp nh ận đ ược trong điều kiện hiện tại. Bất kỳ một bài toán nào không thuộc lớp này thì đều có chi phí rất lớn. Có thể giải được hay không? Người ta đã ước tính thời gian cần thiết để giải một mật mã được mã hóa bằng khóa 128-bit là trên 1 tri ệu năm với điều kiện làm việc trên các siêu máy tính mạnh nhất hiện nay! Chính vì lý do này, một bài toán được xem là có thể giải được trên thực tế hay không ph ụ thuộc vào độ phức tạp của bài toán đó có phải là đa thức hay không. 4.2. Lớp bài toán có độ phức tạp không đa thức Thật không may mắn, nhiều bài toán thực sự có lời giải lại không thu ộc l ớp c ủa bài toán đa thức. Ví dụ : cho một tập hợp có n phần tử, hãy liệt kê tất cả các tập con khác tr ống c ủa tập hợp này. Bằng toán học, người ta đã chứng minh được rằng số tập con c ủa m ột t ập h ợp có n phần tử là 2n-1. Lời giải tuy đã có nhưng khi thể hiện lời gi ải này bằng b ất kỳ thu ật toán nào thì phải tốn ít nhất 2n-1 bước. Dễ thấy rằng độ phức tạp của bài toán này cũng cỡ O(2 n). Như vậy bài toán này không thuộc lớp của bài toán đa thức. Với n vào kho ảng 16, s ố b ước c ần thi ết ch ỉ khoảng vài chục ngàn là hoàn toàn giải được trên các máy tính hi ện nay. Nh ưng khi s ố ph ần t ử lên đến 32 thì ta đã tốn một số bước lên đến 4 tỷ, chỉ thêm m ột phần tử n ữa thôi, chúng ta đã t ốn 8 tỷ bước! Với số lượng bước như vậy, dù chạy trên m ột siêu máy tính cũng ph ải t ốn m ột th ời gian đáng kể! Các bài toán không thuộc lớp đa thức ch ỉ gi ải đ ược v ới m ột đ ộ l ớn d ữ li ệu đ ầu vào nhất định. 4.3. Lớp bài toán NP Chúng ta đều biết rằng tính xác định là một trong ba đ ặc tính quan tr ọng c ủa thu ật toán. Nghĩa là mỗi bước của thuật toán phải được xác định duy nhất và có thể thực thi được. Nếu có sự phân chia trường hợp tại một bước thì thông tin tại bước đó ph ải đầy đ ủ đ ể thu ật toán có thể tự quyết định chọn lựa trường hợp nào. Trong mục 4.3 này, ta tạm gọi các thuật toán th ỏa mãn tính xác định là các thuật toán tự quyết.
Vậy thì điều gì sẽ xảy ra nếu ta đưa ra một "thuật toán" có tính không tự quyết? Nghĩa là tại một bước của "thuật toán", ta đưa ra một số trường hợp chọn lựa nh ưng không cung c ấp đầy đủ thông tin để "thuật toán" tự quyết định? Thật ra, trong cuộc sống, những "thu ật toán" thuộc loại này rất hay được áp dụng. Chẳng hạn ta có m ột lời ch ỉ dẫn khi đi du l ịch : "Khi đi hết khu vườn này, bạn hãy chọn một con đường mà bạn cảm thấy thích. Tất cả đ ều dẫn đ ến b ảo tàng lịch sử.". Nếu là khách du lịch, bạn sẽ cảm thấy bình thường. Nhưng máy tính thì không! Nó không thể thực thi những hướng dẫn không rõ ràng như vậy! Ðến đây, lập tức sẽ có một câu hỏi rằng "Tại sao lại đề cập đến những thuật toán có tính không tự quyết dù máy tính không thể thực hiện một thuật toán như vậy?". Câu tr ả l ời là, khi nghiên cứu về thuật toán không tự quyết, dù không dùng để gi ải bài toán nào đi n ữa, chúng ta s ẽ có những hiểu biết về hạn chế của những thuật toán tự quyết thông thường. Ðến đây, ta hãy xem sự khác biệt về độ phức tạp của một thuật toán tự quyết và không tự quyết để giải quyết cho cùng một vấn đề. Bài toán người bán hàng Một nhân viên phân phối hàng cho một công ty được giao nhiệm vụ phải giao hàng cho các đ ại lý c ủa công ty, sau đó trở về công ty. Vấn đề của người nhân viên là làm sao đi giao hàng cho t ất c ả đ ại lý mà không tiêu quá s ố tiền đổ xăng mà công ty cấp cho mỗi ngày. Nói một cách khác, làm sao đừng đi quá một số lượng cây số nào đó. Một lời giải cổ điển cho bài toán này là liệt kê một cách có hệ thống từng con đ ường có thể đi, so sánh chiều dài mỗi con đường tìm được với chi ều dài gi ới h ạn cho đ ến lúc tìm đ ược một con đường phù hợp hoặc đã xét hết tất cả các con đ ường có th ể đi. Tuy nhiên, cách gi ải quyết này có độ phức tạp không phải đa thức. Bằng toán h ọc, ng ười ta đã ch ứng minh đ ược r ằng độ phức tạp của thuật toán này là O(n!). Như vậy, với số đại lý lớn thì thuật toán trên đ ược xem là không thực tế. Bây giờ, chúng ta xem qua một thuật toán không tự quyết. 1. Chọn một con đường có thể và tính chiều dài của nó. 2. Nếu chiều dài này không lớn hơn giới hạn thì báo là thành công, ngược lại báo chọn lựa sai. Quan điểm của ta trong cách giải quyết này là nếu chọn sai thì là do lỗi c ủa người ch ọn chứ không phải lỗi của thuật toán !. Theo thuật toán này thì chi phí để tính chiều dài của con đ ường đ ược ch ọn s ẽ t ỷ l ệ v ới số đại lý; chi phí để so sánh chiều dài quãng đường với giới hạn cho phép thì không liên quan đến số thành phố. Như vậy, chi phí của thuật toán này là m ột hàm có dạng T = an+b v ới n là s ố đ ại lý và a,b là các hằng số. Ta kết luận rằng, độ phức tạp của thuật toán này là O(n) hay đ ộ ph ức t ạp thuộc lớp đa thức. Như vậy, nếu dùng thuật toán tự quyết thì bài toán người bán hàng sẽ có đ ộ ph ức t ạp không thuộc lớp đa thức, còn nếu dùng thuật toán không tự quyết thì bài toán s ẽ có đ ộ ph ức t ạp đa thức. 5. THUẬT TOÁN ĐỆ QUY
Thuật toán đệ quy là một trong những sự mở rộng cơ bản nhất của khái niệm thuật toán. Như đã biết, một thuật toán cần phải thỏa mãn 3 tính chất : – Tính hữu hạn. – Tính xác định – Tính đúng đắn Tuy nhiên, có những bài toán mà việc xây dựng m ột thu ật toán v ới đ ầy đ ủ ba tính ch ất trên rất khó khăn. Trong khi đó, nếu ta xây dựng m ột thuật toán vi ph ạm m ột vài tính ch ất trên thì cách giải lại trở nên đơn giản hơn nhiều và có thể chấp nhận được. Một trong những trường h ợp đó là thuật toán đệ quy. Tư tưởng giải bài toán bằng thuật toán đệ quy là đưa bài toán hi ện t ại v ề m ột bài toán cùng loại, cùng tính chất (hay nói một cách nôm na là đồng dạng) nhưng ở cấp độ thấp hơn (chẳng hạn : độ lớn dữ liệu nhập nhỏ hơn, giá trị cần tính toán nhỏ hơn, ....), và quá trình này ti ếp tục cho đến lúc bài toán được đưa về một cấp độ mà tại đó có thể gi ải được. Từ k ết qu ả ở c ấp độ này, ta sẽ lần ngược để giải được bài toán ở cấp độ cao hơn cho đến lúc gi ải được bài toán ở cấp độ ban đầu. Trong toán học ta cũng thường gặp những định nghĩa v ề nh ững đ ối t ượng, nh ững khái niệm dựa trên chính những đối tượng, khái niệm đó. Ðịnh nghĩa giai thừa Giai thừa của một số tự nhiên n, ký hiệu n! được định nghĩa là : 0! = 1 n! = (n-1)!n với mọi n>0 Ðịnh nghĩa dãy số Fibonacci f0 = 1 f1 = 1 fn = fn-1 + fn-2 với mọi n>1 Theo toán học, những khái niệm được định nghĩa nh ư vậy gọi là đ ịnh nghĩa theo ki ểu quy nạp. Chính vì vậy, đệ quy có sự liên hệ rất chặt chẽ với quy nạp toán học. Ðệ quy mạnh ở điểm nó có thể định nghĩa một tập vô hạn các đ ối t ượng ch ỉ b ằng m ột số hữu hạn các mệnh đề. Tuy nhiên, đặc tính này của đệ quy l ại vi ph ạm tính xác đ ịnh c ủa thu ật toán. Về nguyên tắc, một bước trong thuật toán phải đ ược xác đ ịnh ngay t ại th ời đi ểm b ước đó được thi hành, nhưng với thuật toán đệ quy, bước thứ n không được xác định ngay trong ngữ cảnh của nó mà phải xác định thông qua một bước thấp hơn. Chẳng hạn, để tính đ ược giá tr ị ph ần t ử thứ 5 của dãy Fibonacci theo định nghĩa ở trên, ta phải tính f 3+f4, nhưng ta chưa biết giá trị f3 và f4
tại thời điểm này. Ðến đây, ta phải lùi lại để tính f 3 và f4. Ðể tính f3 ta lại phải lùi về để tính f2,...Tất nhiên, là quá trình tính lùi này phải dừng sau m ột số h ữu h ạn b ước. Trong tr ường h ợp này, điểm dừng chính là giá trị f1 và f0. Ưu thế của thuật toán đệ quy là ta chỉ cần giải bài toán tại m ột số trường h ợp đ ặc bi ệt nào đó, còn gọi là trường hợp dừng. Sau đó, các tr ường h ợp khác c ủa bài toán s ẽ đ ược xác đ ịnh thông qua trường hợp đặc biệt này. Ðối với việc tính dãy Fibonacci, tr ường h ợp d ừng chính là giá trị của f0 và f1. Nói một cách chính xác, mọi thuật toán đệ quy đều gồm hai phần: Phần cơ sở Là các trường hợp không cần thực hiện lại thuật toán (hay không có yêu c ầu gọi đệ quy). Nếu thuật toán đệ quy không có phần này thì sẽ dẫn đến bị lặp vô hạn và sinh lỗi khi thi hành. Vì lý do này mà người ta đôi lúc còn gọi phần cơ sở là trường hợp dừng. Phần đệ quy Là phần trong thuật toán có yêu cầu gọi đệ quy, tức là yêu c ầu th ực hi ện l ại thu ật toán nhưng với một cấp độ dữ liệu thấp hơn.