Giới thiệu về thuật toán trong tin học
Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một dãy các thao tác trên những đối tượng, sao cho sau một số hữu hạn bước thực hiện các thao tác ta đạt được mục tiêu định trước.
Thuật toán trong Tin học là gì
Download
Xem online
Tóm tắt nội dung tài liệu
- Giới thiệu về thuật toán trong tin học 1. Khái niệm thuật toán Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một dãy các thao tác trên những đối tượng, sao cho sau một số hữu hạn bước thực hiện các thao tác ta đạt được mục tiêu định trước. Để giải các bài toán bằng máy tính chúng ta thường phải có một quan niệm rộng rãi hơn về thuật toán cụ thể là lưu ý đến các đặc điểm sau: a] Không cần xác định toàn bộ lời giải, các thao tác theo từng bước một cách chính xác, đơn vị và rõ ràng.Thay vào đó chỉ cần chỉ ra một cách chuyển từ một bước giải i tới bước giải kế tiếp i+1, và tìm cách cắt nhỏ bài toán thành các bài toán con, đó chính là thuật toán đệ quy rất quan trọng để giải các bài toán tổng quát. b] Có nhiều bài toán không có cách giải đúng, hoặc cách giải đúng không thể chấp nhận được do hạn chế về thời gian chạy và kích thước bộ nhớ. Nhưng nếu ta chấp nhận kết quả gần đúng thì có thể tồn tại nhiều cách giải đỡ phức tạp và có hiệu quả hơn, đó chính là các thuật toán Heuristic để giải các bài toán gần đúng. 2. Khái niệm bài toán: Trong phạm vi tin học ta có thể quan niệm bài toán là một việc nào đó ta muốn máy tính thực hiện. Các bài toán được cấu tạo bởi 2 thành phần cơ bản Input và Output. Thuật toán cũng có thể được hiểu là một dãy các thao tác được sắp xếp theo trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán ta nhận được Output cần tìm. 3. Một số ví dụ: Bài toán 1:Tìm giá trị lớn nhất của một dãy số nguyên Xác định bài toán Input: Số nguyên dương N và dãy N số nguyên a1,a2,...,aN Output: Giá trị lớn nhất Max của dãy số. Ý tưởng: Chọn Max=a1
- Lần lượt với i từ 2 đến N, so sánh ai với a1, nếu ai>a1 thì gán Max=ai Thuật toán giải được mô tả như sau: Nhập N>0 và dãy a1,a2,…,aN. Max a1, i 2; Nếu i > N thì đưa giá trị Max rồi kết thúc; Nếu ai > Max thì Max ai i i + 1 rồi quay lại bước 3. Bài toán 2: Tìm UCLN của hai số nguyên dương m,n. Xác định bài toán: Input : 2 số nguyên dương m,n. Output : UCLN của 2 số. Ý tưởng 01: UCLN[m,n]=UCLN[m,m-n] [Giả sử m>n] Thuật toán giải được mô tả như sau: Nhập 2 số m,n > 0. Nếu m=n thì đưa ra UCLN[m,n]=m; Nếu m > n thì m m-n rồi quay lại bước 2. Nếu n>m thì n n-m rồi quay lại bước 2. Đưa ra kết quả UCLN khi một trong m hoặc n=0 [Nếu m=0 thì UCLN[m,n]=n còn nếu m≠0 thì UCLN[m,n]=m] Ý tưởng 02: UCLN[m,n] = UCLN[n,m mod n] Thuật toán giải 02 : dành cho bạn đọc. Bài toán 3: Cho dãy A gồm N số nguyên a1,a2,…,aN. Sắp xếp các số hạng để dãy A là trở thành dãy không giảm [tức là số hạng sau luôn lớn hơn hoặc bằng số hạng trước] Xác định bài toán: Input: Dãy A gồm N số nguyên a1,a2,…,aN. Output: Dãy A đã được sắp xếp trở thành dãy không giảm Ý tưởng 01: Với mỗi cặp số hạng đứng liền kề nhau trong dãy, nếu số đứng trước lớn hơn số đứng sau thì ta đổi chỗ hai số cho nhau. Quá trình lặp lại cho đến khi không còn sự đổi chỗ xảy ra. Thuật toán giải được mô tả như sau: Nhập N>0 và dãy a1,a2,…,aN. MN Nếu M < 2 thì đưa ra dãy A được sắp xếp rồi kết thúc. Nếu M ≥ 2 thì M M-1, i 0
- i i+1 Nếu i > M thì quay lại bước 3. Nếu ai > ai+1 thì tráo đổi vị trí ai và ai+1 Quay lại bước 5. Ý tưởng 02 : Chia dãy cần sắp xếp thành 2 phần, lấy thành phần giữa X làm chuẩn để so sánh. • Tìm một phần tử A ở dãy trên có giá trị lớn hơn X • Tìm một phần tử B ở dãy dưới có giá trị nhỏ hơn X • Hoán vị A và B. • Tiếp tục như vậy cho đến khi ta đạt được dãy trên chỉ gồm các phần tử nhỏ hơn X, dãy dưới chỉ gồm các phần tử lớn hơn X. • Áp dụng thuật toán trên vào dãy trên và dãy dưới [đệ quy] cho đến khi không chia được nữa. Thuật toán giải 02: bạn thử mô tả xem sao, đây coi như là một bài tập nhỏ cho các bạn yêu thích lập trình. Bài toán 4: Cho dãy A gồm N số nguyên a1,a2,…,aN và một số X. Hãy xác định xem giá trị của X có nằm trong dãy A không? Nếu có thì nằm ở đâu ? Xác định bài toán: Input: dãy A gồm N số nguyên a1,a2,…,aN và số X. Output: X có thuộc A không? Nếu có thì nằm ở vị trí nào? Ý tưởng: So sánh từng phần tử của dãy với X. Nếu có phần tử ai = X thì đưa ra thứ tự của phần tử thứ i thỏa ai = X. Thuật toán giải được mô tả như sau : Nhập N>0 ,dãy a1,a2,…,aN ,và số X i 1. Nếu i > N thì kết thúc và đưa kết quả Nếu i < N thì tiếp tục. Nếu ai = X thì kết thúc và đưa ra thứ tự của X là i . Nếu ai ≠ X thì i i + 1 và quay lại bước 5. Vòng lặp kết thúc khi i > N 4.[nói thêm] Phương pháp tinh chế từng bước trong lập trình:1 1 Trích từ cuốn “Phương pháp giải các bài toán trong tin học” của Thạc sĩ Trần Đức Huyên [NXBGD 2001]
- Ban đầu chương trình được viết bằng những lời tự nhiên [tiếng Việt chẳng hạn] thể hiện sự phân tích tổng thể của người lập trình. Ở từng bước sau, mỗi câu lời được phân tích ra chi tiết hơn bằng nhiều câu lời khác tương ứng với sự phân tích một công việc thành những công việc nhỏ hơn. Mỗi câu lời đó là một sự đặc tả công việc. Ta nói ở mỗi bước ta đã tinh chế những câu lời đó. Sự tinh chế được hướng về phía ngôn ngữ lập trình mà ta sẽ dùng. Nghĩa là, càng ở những bước sau, các câu lời tự nhiên càng được thay nhiều bằng các câu lời của ngôn ngữ lập trình. Một câu lời tự nhiên nếu đơn giản thì ta có thể thay bằng một vài phát biểu, nếu phức tạp thì ta coi nó như một thủ tục và tiếp tục tinh chế nó. Trong qua trình tinh chế đó, ta cần đưa ra những biểu diến dữ liệu, vì dữ liệu là nguyên liệu của máy tính. Như vậy cùng với sự tinh chế các công việc, dữ liệu cũng được tinh chế, phân rã, hay cấu trúc hóa. Điều này có nghĩa là sự tinh chế các dặc tả chương trình và dữ liệu là song song. Phương pháp tinh chế từng bước là một thể hiện của tư duy giải quyết vấn đề từ trên xuống, trong đó sự phát triển của các bước là hướng về phía ngôn ngữ lập trình được dùng. Đáy của sự đi xuống trong hoạt động phân tích là các phát triển và các mô tả dữ liệu viết bằng ngôn ngữ lập trình. Hiểu được phương pháp tinh chế từng bước sẽ giúp người lập trình có được môt định hướng thể hiện sự ngăn nắp trên tờ giấy nháp của mình, tránh khỏi việc phải mò mẫm, thử đi thử lại nhiều lần các chương trình mang tính trực giác.
Khái niệm bài toán và thuật toán qua ví dụ cụ thể
Tìm hiểu khái niệm bài toán
Bài toán trong tin học được hiểu là một việc gì đó mà ta muốn máy tính thực hiện nhằm cho ra kết quả.
Ví dụ như là tính diện tích hình chữ nhật, tìm ước chung lớn nhất của hai số nguyên dương, giải phương trình bậc nhất, quản lý nhân sự, quản lý tiền lương của nhân viên…
Muốn giải một bài toán nào đó trên máy tính, trước tiên ta cần xác định được hai yếu tố cơ bản:
- Đầu vào [Input]: đưa vào máy thông tin gì [ các thông tin đã có ]
- Đầu ra [Output]: cần lấy ra thông tin gì [các thông tin cần tìm ]
Hay ta có thể hiểu một cách đơn giản những thông tin mà chúng ta đã biết thì gọi là input, còn những thông tin chúng ta cần tìm là output.
Ví dụ 1: Biết chiều rộng và chiều dài của hình chữ nhật. Tính diện tích hình chữ nhật
- Input: chiều rộng, chiều dài
- Output: diện tích
Ví dụ 2: Giải phương trình bậc nhất ax+b = 0
- Input: Hệ số a, b [a khác 0]
- Output: Nghiệm của phương trình
Ví dụ 3: Tìm ước chung lớn nhất của hai số nguyên dương
- Input: a, b nguyên dương
- Output: UCLN của a,b
Ví dụ 4: Xếp loại kết quả học tập của học sinh
- Input: Bảng điểm của học sinh trong lớp
- Output: Bảng xếp loại học lực
Như vậy, khi muốn giải quết một bài toán thì điều đầu tiên chúng ta cần phải xác định được đầu vào [input] và đầu ra [output] của bài toán. Ta gọi chung việc xác định bài toán là xác định input và xác định output.
Tìm hiểu khái niệm và tính chất của thuật toán
Một câu hỏi được đặt ra là làm sao khi ta đưa thông tin vào máy tính, ta có thể xác định được output của bài toán. Việc chỉ ra tường minh một cách tìm output của bài toán được gọi là thuật toán. Vậy thuật toán là gì chúng ta cùng nhau tìm hiểu khái niệm sau:
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 đó, từ Input của bài toán, ta nhận được Output cần tìm.
Từ định nghĩa ở trên, với thuật toán ta cần quan tâm đếm 3 điểm chính sau:
+ Dãy hữu hạn các thao tác
+ Sắp xếp có thứ tự
+Từ input cho ra output
Để trình bày thuật toán, ta sẽ có nhiều cách khác nhau như: Dùng ngôn ngữ tự nhiên, mã giải, sơ đồ khối, ngôn ngữ lập trình, các bảng điều khiển.
Các cách viết thuật toán:
Sau đây chúng tôi sẽ trình bày cho các bạn 2 cách biểu diễn thuật toán gồm có các cách như sau:
Cách 1: Dùng phương pháp liệt kê
Ta sẽ liệt kê ra các thao tác cần tiến hành một cách tuần tự
Xác định bài toán
- Input: Các số thực a, b, c [a khác 0]
- Output: Số thực x thỏa : ax2 + bx + c = 0
Trình bày thuật toán
Bước 1: Nhập hệ số a, b, c [a khác 0]
Bước 2: Tính ∆ = b2 – 4ac
Bước 3: Nếu ∆ < 0 thì kết luận phương trình vô nghiệm rồi kết thúc
Bước 4: Nếu ∆ = 0 thì phương trình có nghiệm kép x1 = x2 = rồi kết thúc thuật toán, nếu khác 0 thì chuyển sao bước tiếp theo
Bước 5: Nếu ∆ > 0 thì phương trình có 2 nghiệm là
x1 = ; x2=rồi kết thúc
Ví dụ 2: Thuật toán tìm số lớn nhất trong dãy
Xác định bài toán:
- Input: Số nguyên dương N, dãy N số nguyên a1,…,aN
- Output: Giá trị lớn nhất của dãy số
Ý tưởng của thuật toán:
- Khởi tạo giá trị lớn nhất Max = a1.
- Lần lượt xét i từ 2 đến N, ta so sánh giá trị số hạng ai với giá trị Max, nếu ai > Max thì Max là giá trị ai.
Thuật toán được mô tả như như sau [mô tả liệt kê]
- Bước 1: Nhập N và cá số a1,a2,…,an
- Bước 2: Max := a1, i := 2;
- Bước 3: Nếu i > N thì chuyển đến bước 6
- Bước 4: Nếu ai > Max thì Max := ai;
- Bước 5: i := i + 1 rồi quay lại bước 3;
- Bước 6: Thông báo giá trị Max rồi kết thúc.
Quy ước vẽ hình:
Thế hiện thao tác nhập, xuất dữ liệu: hình ô van
Thể hiện thao tác so sánh: hình thoi
Thể hiện các phép toán: hình chữ nhật
Quy định trình tự các thao tác thực hiện: các mũi tên
Các tính chất của thuật toán:
- Tính chính xác: nhằm giúp kết quả tính toán hay các thao tác mà máy tính thực hiện đưa ra kết quả chính xác.
- Tính rõ ràng: Thuật toán thực hiện bằng câu lệnh minh bạch, rõ ràng.
- Tính khách quan: thuật toán dù nhiều người thực hiện trên máy tính cho kết quả giống nhau.
- Tính phổ dụng: Thuật toán không phải dùng cho các bài toán nhất định mà có thể áp dụng cho một lớp các bài toán với điều kiện đầu vào giống nhau.
- Tính kết thúc: Thuật toán là các số hữu hạn các bước tính toán.
Xem thêm: Các công thức toán học 12
Qua bài viết này, các bạn đã hiểu được thế nào là bài toán và thuật toán, không có gì quá khó hiểu phải không nào. Các bạn hãy đọc kĩ các ví dụ để có thể dễ hiểu hơn, cảm ơn các bạn đã theo dõi bài viết của chúng tôi, nếu có thắc mắc các bạn hãy để lại comment, chúng tôi sẽ giúp bạn giải đáp nhé.
Tham khảo thêm:
- 7 hằng đẳng thức đáng nhớ cơ bản và mở rộng
- Ảnh hưởng của ánh sáng lên đời sống sinh vật
- Ảnh hưởng của môi trường lên sự biểu hiện của gen
- Ảnh hưởng của nhiệt độ và độ ẩm lên đời sống sinh vật
- Ảnh hưởng của thuốc hóa học bảo vệ thực vật đến quần thể sinh vật và môi trường
Bạn có thể quan tâm:
Mục lục
- 1 Định nghĩa không chính thức
- 2 Hình thức hóa
- 2.1 Diễn đạt thuật toán
- 3 Thiết kế
- 4 Thực hiện
- 5 Thuật toán máy tính
- 6 Ví dụ
- 6.1 Ví dụ thuật toán
- 6.2 Thuật toán Euclid
- 6.3 Ngôn ngữ máy tính cho thuật toán Euclid
- 6.4 Một chương trình đơn giản cho thuật toán Euclid
- 6.5 Một chương trình đơn giản cho thuật toán Euclid
- 6.6 Kiểm tra các thuật toán Euclid
- 6.7 Đo lường và cải thiện các thuật toán Euclid
- 7 Đọc thêm
- 8 Tham khảo
Định nghĩa không chính thứcSửa đổi
Một định nghĩa không chính thức có thể là "một tập hợp các quy tắc xác định chính xác một chuỗi hoạt động",[17] mà sẽ bao gồm tất cả các chương trình máy tính [bao gồm cả các chương trình không thực hiện phép tính số] và [ví dụ] bất kỳ thủ tục hành chính quy định nào [18] hoặc công thức nấu ăn.[19]
Nói chung, một chương trình chỉ là một thuật toán nếu cuối cùng nó dừng lại [20] - mặc dù các vòng lặp vô hạn đôi khi có thể chấp nhận được.
Một ví dụ nguyên mẫu của một thuật toán là thuật toán Euclid, được sử dụng để xác định ước chung lớn nhất của hai số nguyên; một ví dụ được mô tả bằng lưu đồ ở trên và là ví dụ trong phần sau.
Boolos, Jeffrey & 1974, 1999Lỗi harv: không có mục tiêu: CITEREFBoolosJeffrey1999 [trợ giúp] đưa ra một định nghĩa không chính thức cho thuật toán như sau:
- Không một con người nào có thể viết đủ nhanh, đủ dài, hoặc đủ nhỏ † [† "nhỏ hơn và nhỏ hơn mà không có giới hạn... bạn đang cố viết trên phân tử, trên nguyên tử, trên electron"] để liệt kê tất cả các thành viên của vô số thiết lập bằng cách viết ra tên của họ, cái khác, trong một số ký hiệu. Nhưng con người có thể làm điều gì đó hữu ích không kém, trong trường hợp có nhiều tập hợp vô hạn nhất định: Họ có thể đưa ra các chỉ dẫn rõ ràng để xác định phần tử thứ n của tập hợp, cho n hữu hạn tùy ý. Những hướng dẫn như vậy phải được đưa ra khá rõ ràng, dưới hình thức mà chúng có thể được tuân theo bởi một máy tính toán hoặc bởi một con người chỉ có khả năng thực hiện các thao tác rất cơ bản trên các ký hiệu. [21]
"Tập hợp vô hạn liệt kê được" là tập hợp mà các phần tử của nó có thể được song ánh tương ứng 1-1 với các số nguyên. Vì vậy, Boolos và Jeffrey đang nói rằng một thuật toán ngụ ý hướng dẫn cho một quá trình "tạo" các số nguyên đầu ra từ một số nguyên "đầu vào" tùy ý hoặc các số nguyên, theo lý thuyết, có thể lớn tùy ý. Ví dụ: một thuật toán có thể là một phương trình đại số chẳng hạn như y = m + n [tức là hai "biến đầu vào" tùy ý m và n tạo ra đầu ra y], nhưng các nỗ lực của các tác giả khác nhau để xác định khái niệm cho thấy rằng từ đó ngụ ý nhiều hơn thế này, một cái gì đó theo thứ tự của [cho ví dụ bổ sung]:
- Các hướng dẫn chính xác [bằng ngôn ngữ mà "máy tính" hiểu được] [22] để có một quy trình "tốt" [23] nhanh, hiệu quả, chỉ định các "động thái" của "máy tính" [máy hoặc con người, được trang bị bên trong thông tin và khả năng] [24] để tìm, giải mã và sau đó xử lý các số nguyên / ký hiệu đầu vào tùy ý m và n, ký hiệu + và = … và "hiệu quả" [25]
sản xuất ra, trong một thời gian "hợp lý",[26] đầu ra-số nguyên y tại một nơi được chỉ định và với định dạng được chỉ định.
Khái niệm thuật toán cũng được sử dụng để định nghĩa khái niệm về khả năng giải mã — một khái niệm trung tâm để giải thích cách các hệ thống hình thức ra đời bắt đầu từ một tập hợp nhỏ các tiên đề và quy tắc. Về mặt logic, thời gian mà một thuật toán yêu cầu để hoàn thành không thể đo được, vì nó dường như không liên quan đến kích thước vật lý thông thường. Từ sự không chắc chắn như vậy, đặc trưng cho công việc đang diễn ra, dẫn đến việc không có định nghĩa thuật toán phù hợp với cả cách sử dụng thuật ngữ này một cách cụ thể [theo một nghĩa nào đó]
Bài 4. Bài toán và thuật toán
1. Khái niệm bài toán
a, Khái niệm
- Bài toán là một việc nào đó mà con người muốn máy tính thực hiện
- Các yếu tố của một bài toán:
+ Input: Thông tin đã biết, thông tin đưa vào máy tính
+ Output: Thông tin cần tìm, thông tin lấy ra từ máy tính
b. Ví dụ
+ Tìm USCLN của 2 số nguyên dương
+ Tìm số lớn nhất trong 3 số nguyên dương a,b,c
+ Tìm nghiệm của phương trình bậc nhất: ax + b = 0 [a≠0]
+ ...
2. Khái niệm thuật toán
a. Khái niệm
Thuật toán để giải một bài toán là:
+ Một dãy hữu hạn các thao tác [tính dừng]
+ Các thao tác được tiến hành theo một trình tự xác định [tính xác định]
+ Sau khi thực hiện xong dãy các thao tác đó ta nhận được Output của bài toán [tính đúng đắn]
b. Cách biểu diễn thuật toán
Có 2 cách để biểu diễn thuật toán:
- Cách dùng phương pháp liệt kê: Nêu ra tuần tự các thao tác cần tiến hành
+ Ví dụ:Cho bài toán Tìm nghiệm của phương trình bậc 2: ax2 + bx + c = 0 [a≠0]?
+ Xác định bài toán
Input: Các số thực a, b, c
Output: Các số thực x thỏa mãn ax2 + bx + c = 0 [a≠0]
+ Thuật toán:
Bước 1: Nhập a, b, c [a≠0]
Bước 2: Tính Δ = b2 – 4ac
Bước 3: Nếu Δ>0 thì phương trình có 2 nghiệm là
Bước 4: Nếu Δ = 0 thì phương trình có nghiệm kép
rồi kết thúc thuật toán. Nếu không chuyển sang bước tiếp theo
Bước 5: Kết luận phương trình vô nghiệm rồi kết thúc
- Cách dùng sơ đồ khối
+ Hình thoi: thể hiện thao tác so sánh;
+ Hình chữ nhật: thể hiện các phép tính toán;
+ Hình ô van: thể hiện thao tác nhập, xuất dữ liệu;
+ Các mũi tên: qui định trình tự thực hiện các thao tác.
3. Một số ví dụ về thuật toán
Bài toán 1: Kiểm tra tính nguyên tố
1. Xác định bài toán
- Input: N là một số nguyên dương
- Output:
+ N là số nguyên tố hoặc
+ N không là số nguyên tố
- Định nghĩa: "Một số nguyên dương N là số nguyên tố nếu nó chỉ có đúng hai ước là 1 và N"
- Tính chất:
+ Nếu N = 1 thì N không là số nguyên tố
+ Nếu 1 < N < 4 thì N là số nguyên tố
2. Ý tưởng
- N 1 của N
+ Nếu i < N thì N không là số nguyên tố [vì N có ít nhất 3 ước 1, i, N]
+ Nếu i = N thì N là số nguyên tố
3. Xây dựng thuật toán
a] Cách liệt kê
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 là số nguyên tố", kết thúc;
Bước 3: Nếu N số sau ta đổi chỗ chúng cho nhau.[Các số lớn sẽ được đẩy dần về vị trí xác định cuối dãy]
- Việc này lặp lại nhiều lượt, mỗi lượt tiến hành nhiều lần so sánh cho đến khi không có sự đổi chỗ nào xảy ra nữa
3. Xây dựng thuật toán
- Bước 1. Nhập N, các số hạng a1, a2,…,an;
- Bước 2. Đầu tiên gọi M là số số hạng cần so sánh, vậy M sẽ chứa giá trị của N:
- Bước 3. Nếu số số hạng cần so sánh < 2 thì dãy đã được sắp xếp. Kết thúc;
- Bước 4. M chứa giá trị mới là số phép so sánh cần thực hiện trong lượt: . Gọi i là số thứ tự của mỗi lần so sánh, đầu tiên i 0;
- Bước 5. Để thực hiện lần so sánh mới, i tăng lên 1[lần so sánh thứ i]
- Bước 6. Nếu lần so sánh thứ i> số phép so sánh M: đã hoàn tất M số phép so sánh của lượt này. Lặp lại bước 3, bắt đầu lượt kế [với số số hạng cần so sánh mới chính là M đã giảm 1 ở bước 4];
- Bước 7. So sánh 2 phần tử ở lần thứ i là ai và ai+1. Nếu ai > ai+1 thì tráo đổi 2 phần tử này;
- Bước 8. Quay lại bước 5
a] Đối chiếu, hình thành các bước liệt kê
b] Sơ đồ khối
Hình 2. Sơ đồ khối thuật toán sắp xếp bằng cách tráo đổi
Bài toán 3: Tìm kiếm tuần tự
1. Xác định bài toán
- Input : Dãy A gồm N số nguyên khác nhau a1, a2,…,an và một số nguyên k [khóa]
Ví dụ : Dãy A gồm các số nguyên: 5 7 1 4 2 9 8 11 25 51 . Và k = 2 [k = 6]
- Output: Vị trí i mà ai = k hoặc thông báo không tìm thấy k trong dãy. Vị trí của 2 trong dãy là 5[không tìm thấy 6]
2. Ý tưởng
Tìm kiếm tuần tự được thực hiện một cách tự nhiên: Lần lượt đi từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khóa cho đến khi gặp một số hạng bằng khóa hoặc dãy đã được xét hết mà không tìm thấy giá trị của khóa trên dãy.
3. Xây dựng thuật toán
a] Cách liệt kê
Bước 1: Nhập N, các số hạng a1, a2,…, aN và giá trị khoá k;
Bước 2: i ← 1;
Bước 3: Nếu ai = k thì thông báo chỉ số i, rồi kết thúc;
Bước 4: i ← i+1
Bước 5: Nếu i > N thì thông báo dãy A không có số hạng nào có giá trị bằng k, rồi kết thúc;
Bước 6: Quay lại bước 3;
b] Sơ đồ khối
Hình 3. Sơ đồ khối thuật toán tìm kiếm tuần tự
Bài toán 4: Tìm kiếm nhị phân
1. Xác định bài toán
- Input: Dãy A là dãy tăng gồm N số nguyên khác nhau a1, a2,…,an và một số nguyên k.
Ví dụ: Dãy A gồm các số nguyên: 2 4 5 6 9 21 22 30 31 33. Và k = 21 [k = 25]
- Output : Vị trí i mà ai = k hoặc thông báo không tìm thấy k trong dãy. Vị trí của 21 trong dãy là 6 [không tìm thấy 25]
2. Ý tưởng
- Sử dụng tính chất dãy A đã sắp xếp tăng, ta tìm cách thu hẹp nhanh vùng tìm kiếm bằng cách so sánh k với số hạng ở giữa phạm vi tìm kiếm [agiữa], khi đó chỉ xảy ra một trong ba trường hợp:
+ Nếu agiữa= k thì tìm được chỉ số, kết thúc;
+ Nếu agiữa > k thì việc tìm kiếm thu hẹp chỉ xét từ ađầu [phạm vi] → agiữa - 1;
+ Nếu agiữa < k việc tìm kiếm thu hẹp chỉ xét từ agiữa + 1 → acuối [phạm vi].
- Quá trình trên được lặp lại cho đến khi tìm thấy khóa k trên dãy A hoặc phạm vi tìm kiếm bằng rỗng.
3. Xây dựng thuật toán
a] Cách liệt kê
b] Sơ đồ khối
Hình 4. Sơ đồ khối thuật toán tìm kiếm tuần tự
1. Khái niệm bài toán
- Bài toán là một việc nào đó ta muốn máy tính thực hiện. Ví dụ: Giải phương trìnhbậc 2, quản lý nhân viên…
- Các bài toán được cấu tạo bởi 2 thành phần cơ bản:
- Input: các thông tin đã có.
- Output: Các thông tin cần tìm từ Output.
Một số thuật toán chọn lọc và ứng dụng trong tin học phổ thông
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây [1.12 MB, 78 trang ]
1
MỞ ĐẦU
Thuật toán là một trong những khái niệm quan trọng nhất trong tin học.
Thuật toán xuất phát từ nhà khoa học Arập Abu Ja’far Mohammed ibn Musa al
Khowarizmi. Chúng ta có thể xem thuật toán là một công cụ dùng để giải bài toán
được xác định trước. 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. 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 thao tác được sắp xếp theo một trình tự nhất định sao cho sau
khi thực hiện dãy thao tác ấy, từ input của bài toán, ta nhận được output cần tìm.
Ở Việt Nam môn Tin học được đưa vào giảng dạy chính thức ở trường phổ
thông từ năm học 2006 - 2007 tuy nhiên trong thực tế môn Tin học đã được đưa
vào tham gia thi học sinh giỏi cấp tỉnh, cấp quốc gia từ rất lâu: Hội thi Tin học trẻ
không chuyên toàn quốc được tổ chức lần đầu vào năm 1995, kỳ thi học sinh giỏi
Tin học quốc gia được tổ chức vào năm 1995 và đặc biệt kỳ thi Olympic Tin
học quốc tế [IOI] tổ chức lần đầu vào năm 1989. Từ đó đến nay các kỳ thi học
sinh giỏi, Olympic Tin học ngày một nhiều và đòi hỏi kiến thức rất cao.
Chúng ta biết rằng để có kết quả cao trong kỳ thi chọn học sinh giỏi môn Tin
học nói chung thì học sinh phải có vốn kiến thức về thuật toán để giải được các bài
toán khó [đặc biệt là các thuật toán nâng cao], sau đó học sinh sẽ sử dụng ngôn ngữ
lập trình nào đó để lập trình dựa vào thuật toán đã tìm được và giải bài toán theo
yêu cầu. Chương trình giảng dạy ở sách giáo khoa của môn Tin học hiện hành trong
trường phổ thông có lượng kiến thức rất hạn chế và đơn giản, không đủ cơ sở để
học sinh có thể dựa vào vốn kiến thức đó để tham gia một kỳ thi học sinh giỏi cấp
thành phố hay cấp cao hơn. Câu hỏi đặt ra: “Làm thế nào để học sinh có thể đạt
kết quả cao trong các kỳ thi học sinh giỏi môn Tin học trong trường phổ thông?”
yêu cầu đặt ra là các giáo viên giảng dạy môn Tin học trong trường phổ thông phải
suy nghĩ, tìm tòi tài liệu về một số thuật toán như: Thuật toán đệ quy, thuật toán
2
tham lam, thuật toán xấp xỉ và một số thuật toán trên đồ thị ... là những thuật toán
sử dụng hiệu quả để giải nhiều bài toán Tin học.
Xuất phát từ thực tế đó, đề tài luận văn: “MỘT SỐ THUẬT TOÁN CHỌN
LỌC VÀ ỨNG DỤNG TRONG TIN HỌC PHỔ THÔNG” với mục đích tìm
hiểu, nghiên cứu một số thuật toán và cách ứng dụng vào giảng dạy, bồi dưỡng đội
tuyển học sinh giỏi môn Tin học ở trường phổ thông.
Nội dung chính của luận văn gồm 3 chương, phần phụ lục với các nội dung
chính như sau:
Chương 1: Luận văn trình bày tổng quan về các khái niệm cơ bản về thuật
toán và độ phức tạp của thuật toán, vấn đề phân lớp các bài toán trên cơ sở đánh
giá độ phức tạp của thuật toán. Các kiến thức này sẽ là nền tảng về mặt lý thuyết
tính toán để nghiên cứu các chương tiếp sau của luận văn.
Chương 2: Trong chương này luận văn trình bày tổng quan về thuật toán đệ
quy, thuật toán tham lam, thuật toán xấp xỉ và một số thuật toán trên mô hình đồ
thị.
Chương 3: Dựa vào cơ sở lý thuyết của thuật toán được trình bày ở chương
2, trong chương này luận văn sẽ cài đặt chương trình cho một số bài toán cụ thể.
Phần phụ lục:
Toàn bộ các kết quả thực nghiệm giải các bài toán được cài đặt bằng ngôn
ngữ Pascal version 7.0 trên máy tính PC.
3
Chương 1
CÁC KHÁI NIỆM VỀ THUẬT TOÁN
VÀ ĐỘ PHỨC TẠP CỦA THUẬT TOÁN
1.1 Khái niệm cơ bản về thuật toán
1.1.1 Khái niệm bài toán Tin học
Trong phạm vi tin học, người ta quan niệm bài toán là một công việc nào
đó muốn máy tính thực hiện [2].
Khi dùng máy tính để giải bài toán, ta cần quan tâm tới 2 vấn đề: Dữ liệu
cần được đưa vào máy tính [Input] là gì? và cần lấy ra [Output] thông tin gì? nói
một cách khác, cho một bài toán là việc mô tả rõ input và output của bài toán.
Vấn đề còn lại là: Làm thế nào để từ input ta có được output?
1.1.2 Khái niệm thuật toán
Khác với toán học [các yêu cầu của bài toán thường là chứng minh sự tồn tại
đáp án chứ không yêu cầu tìm một cách chi tiết để tìm ra đáp số đó], giải một bài
toán Tin học là việc đi tìm một lời giải cụ thể, tường minh để đưa ra output của bài
toán dựa trên input đã cho. Việc chỉ ra một cách tìm output của bài toán gọi là một
thuật toán. Có nhiều cách phát biểu khái niệm về thuật toán. Dưới đây là cách phát
biểu được chọn để đưa vào sách giáo khoa Tin học phổ thông.
Khái niệm về thuật toán: Thuật 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ự nhất định để sau khi thực hiện dãy các thao tác đó, từ
input ta có output cần tìm [2].
Trong lĩnh vực khoa học máy tính, cụm từ “thuật toán” đôi khi còn được gọi
là: “giải thuật”.
Ví dụ 1: Thuật toán tô màu đồ thị
- Input: đồ thị G = [V, E].
- Output: đồ thị G = [V, E] có các đỉnh đã được gán màu.
Thuật toán: Có nhiều cách để mô tả thuật toán khác nhau. Dưới đây là cách
mô tả thuật toán dạng liệt kê các bước:
4
Bước 1: Lập danh sách các đỉnh của đồ thị E’:= [v1, v2, …,vn] được sắp xếp
theo thứ tự bậc giảm dần: d[v1] d[v2] … d[vn]
Đặt i := 1;
Bước 2: Tô màu i cho đỉnh đầu tiên trong danh sách. Duyệt lần lượt các đỉnh
tiếp theo và tô màu i cho đỉnh không kề đỉnh đã được tô màu i.
Bước 3: Nếu tất cả các đỉnh đã được tô màu thì kết thúc, đồ thị được tô bằng
i màu. Ngược lại, chuyển sang bước 4;
Bước 4: Loại khỏi E’ các đỉnh đã tô màu. Sắp xếp lại các đỉnh trong E’ theo
thứ tự bậc giảm dần.
Đặt i := i +1 và quay lại bước 2.
1.2 Yêu cầu của thuật toán
Thuật toán phải đảm bảo được các yêu cầu sau đây [2], [4].
1. Tính xác định: Các bước của thuật toán phải được trình bày rõ ràng, mạch
lạc, đảm bảo cho người đọc chỉ hiểu theo một nghĩa duy nhất.
2. Tính khả thi: Thuật toán phải thực hiện được, nghĩa là ta có thể sử dụng
máy tính kết hợp giữa các ngôn ngữ lập trình để thể hiện thuật toán hay có thể kiểm
tra thuật toán chỉ bằng giấy và bút [còn gọi là Test].
3. Tính dừng: Nếu dữ liệu vào thỏa mãn điều kiện đầu vào thì thuật toán phải
kết thúc và cho ra kết quả sau một số hữu hạn bước.
4. Tính chính xác [tính đúng đắn]: Thuật toán phải cho kết quả chính xác và
thể hiện đúng đắn trên cơ sở toán học.
5. Tính tối ưu: Thuật toán phải có chi phí về không gian bộ nhớ ít nhất và
chạy trong thời gian nhanh nhất.
1.3. Thể hiện thuật toán
Thuật toán được thể hiện bằng một trong các cách sau
Sử dụng liệt kê các bước.
Sử dụng lưu đồ [sơ đồ khối].
Sử dụng ngôn ngữ lập trình.
5
1.4 Độ phức tạp của thuật toán
1.4.1 Chi phí phải trả cho một quá trình tính toán
Chi phí phải trả cho một quá trình tính toán bao gồm chi phí về không gian
[bộ nhớ - số ô nhớ cần sử dụng trong quá trình tính toán] và chi phí về thời gian
[thời gian cần sử dụng cho một quá trình tính toán].
Nếu cho một thuật toán A. Thuật toán này thực hiện trên bộ dữ liệu e.
Thuật toán này phải trả 2 giá: giá về không gian là LA[e], giá về thời gian là
TA[e], e là bộ dữ liệu vào.
Ví dụ 2: Xét thuật toán A, “Tìm số lớn nhất trong một dãy số”.
Begin
Max := x1;
For i := 2 to n do
If max < xi then max := xi ;
End.
Thực hiện A trên hai bộ dữ liệu khác nhau:
+ Bộ dữ liệu e1 = {0, 4, 9, 5, 7, 6}:
Khi đó LA[e1] = 7 [dữ liệu vào] + 2 [biến trung gian] = 9.
TA[e1] = 8 [thời gian để thực hiện tất cả các phép tính cơ bản].
+ Bộ dữ liệu e2 = {3, 4, 6, 7, 9, 10, 12, 15}:
LA[e2] = 11.
TA[e2] = 15.
Khi đó ta có các khái niệm về chi phí phải trả trong các trường hợp như sau:
Chi phí phải trả trong trường hợp xấu nhất:
- Chi phí xấu nhất về bộ nhớ: LA[n] = Max {LA[e] | e ≤ n}
- Chi phí xấu nhất về thời gian: TA[n] = Max {TA[e] | e ≤ n}
Chi phí phải trả trung bình:
6
Là tổng số các chi phí khác nhau ứng với các bộ số liệu chia cho tổng số số
bộ số liệu.
Chi phí phải trả tiệm cận:
Đó là biểu thức biểu diễn tốc độ tăng của chi phí thực tế phải trả. Nó có gía trị
tiệm cận với chi phí thực tế.
Nhận xét: Ngày nay do sự phát triển không ngừng của khoa học công nghệ
kỹ thuật điện tử nên chi phí về bộ nhớ không còn là vấn đề cần thiết phải bàn tới mà
ta chỉ quan tâm tới chi phí phải trả về thời gian thực hiện giải thuật. Từ đây ta chỉ
xét đến thời gian thực hiện giải thuật T[n], hay đó chính là độ phức tạp của thuật
toán.
Sau đây là việc phân tích thời gian thực hiện giải thuật, một trong các tiêu
chuẩn quan trọng để đánh giá hiệu lực của giải thuật vốn hay được đề cập tới.
1.4.2. Phân tích thời gian thực hiện giải thuật
Với một bài toán, không chỉ có một giải thuật. Chọn một giải thuật đưa tới
kết quả nhanh là một đòi hỏi thực tế. Nhưng căn cứ vào đâu để có thể nói được giải
thuật này nhanh hơn giải thuật kia?
Có thể thấy ngay: thời gian thực hiện một giải thuật, [hay chương trình thể
hiện một giải thuật đó] phụ thuộc vào rất nhiều yếu tố. Một yếu tố cần chú ý trước
tiên đó là kích thước của dữ liệu đưa vào. Chẳng hạn thời gian sắp xếp một dãy số
phải chịu ảnh hưởng của số lượng các số thuộc dãy số đó. Nếu gọi n là số lượng
này [kích thước của dữ liệu vào] thì thời gian thực hiện T của một giải thuật phải
được biểu diễn như một hàm của n: T[n].
Các kiểu lệnh và tốc độ xử lý của máy tính, ngôn ngữ viết chương trình và
chương trình dịch ngôn ngữ ấy đều ảnh hưởng tới thời gian thực hiện; nhưng những
yếu tố này không đồng đều với mọi loại máy trên đó cài đặt giải thuật, vì vậy không
thể đưa chúng vào khi xác lập T[n]. Điều đó có nghĩa là T[n] không thể được biểu
diễn thành đơn vị thời gian bằng giây, bằng phút được. Tuy nhiên, không phải vì thế
mà không thể so sánh được các giải thuật về mặt tốc độ. Nếu như thời gian thực
hiện của một giải thuật là T1[n] = c.n2 và thời gian thực hiện một giải thuật khác là
7
T2[n] = k.n [với c và k là một hằng số nào đó], thì khi n khá lớn, thời gian thực hiện
giải thuật T2 rõ ràng ít hơn so với thời gian thực hiện giải thuật T1. Như vậy, nếu nói
thời gian thực hiện giải thuật bằng T[n] tỉ lệ với n2 hay tỉ lệ với n cũng cho ta ý
niệm về tốc độ thực hiện giải thuật đó khi n khá lớn [với n nhỏ thì việc xét T[n]
không có ý nghĩa]. Cách đánh giá thời gian thực hiện giải thuật độc lập với máy tính
và các yếu tố liên quan với máy như vậy sẽ dẫn tới khái niệm về cấp độ lớn của thời
gian thực hiện giải thuật hay còn gọi là độ phức tạp tính toán của giải thuật.
1.4.3 Độ phức tạp của thuật toán
Nếu thời gian thực hiện một giải thuật là T[n] = c.n2 [với c là hằng số] thì ta
nói: Độ phức tạp tính toán của giải thuật này có cấp là n2 [hay cấp độ lớn – tốc độ
tăng – của thời gian thực hiện giải thuật là n2] và ký hiệu là:
T[n] = O[n2] [kí hiệu chữ O lớn]. Một cách tổng quát có thể định nghĩa:
Một hàm f[n] được xác định là O[g[n]]
f[n] = O[g[n]] và được gọi là có cấp g[n] nếu tồn tại các hằng số c và n0 sao
cho f[n] ≤ c.g[n] khi n ≥ n0 nghĩa là f[n] bị chặn trên bởi một hằng số nhân với g[n],
với mọi giá trị của n từ một điểm nào đó. Thông thường các hàm thể hiện độ phức
tạp tính toán của giải thuật có dạng: O[log2n], O[n], O[nlog2n], O[n2], O[n3], O[2n],
O[n!], O[nn].
O[g[n]] còn gọi là độ phức tạp tiệm cận của hàm f[n].
Dưới đây là một số hàm số hay dùng để ký hiệu độ phức tạp tính toán và
bảng giá trị của chúng để tiện theo dõi sự tăng của hàm theo đối số n.
log2n
n
n2
nlog2n
n3
2n
0
1
0
1
1
2
1
2
2
4
8
4
2
4
8
16
64
16
3
8
24
64
512
256
4
16
64
256
4096
65536
5
32
160
1024
32768
2.147.483.648
8
Các hàm như 2n, nn được gọi là hàm loại mũ, ngoài ra còn có hàm n! và một
số hàm khác có độ phức tạp lớn hơn các hàm mũ. Một giải thuật mà thời gian thực
hiện của nó có cấp là các hàm loại mũ thì tốc độ rất chậm. Các như n3, n2, nlog2n,
log2n được gọi là các hàm loại đa thức. Giải thuật với thời gian thực hiện có cấp
hàm đa thức thì thường hiệu quả và chấp nhận được.
Ví dụ 3: Tính giá trị đa thức P[x] = anxn+an-1xn-1+...+a1x+a0 với a0, a1, ...,an, x nhập
từ bàn phím.
Thuật toán 1:
1. Input n, ao, a1, a2, ..., an, x;
2. S := ao;
3. for i := 1 to n do
begin
p := 1;
for j := 1 to i do p := p*x;
S:= S + ai*p;
end;
4. Output s;
Với mỗi giá trị i của vòng lặp 3, vòng lặp 3.2 thực hiện i vòng lặp nên khi
n = i nó thực hiện đủ n vòng lặp. Vậy vòng lặp 3 thực hiện
n[n 1]
lần câu lệnh sau
2
do nên thời gian tính toán tỉ lệ thuận với n2.
Vậy độ phức tạp tính toán của thuật toán trên là O[n2].
Thuật toán 2: Vì xn = x*xn-1 nên có thể tận dụng kết quả của lần tính trước cho lần
tính sau:
1. Input n, ao, a1, a2, ..., an, x;
2. S := ao; p:=1;
3. for i := 1 to n do
begin
p := p* x;
9
S := s + p;
end;
4. Output S;
Hai lệnh 2 và 4 đều có độ phức tạp tính toán là O[1]. Vòng lặp 3 cần thực hiện
n lần hai thao tác tính s và p. Vậy số lần thực hiện lệnh 3 là 2n. Do vậy, độ phức tạp
tính toán của thuật toán trên là O[n].
1.4.4. Các qui tắc xác định độ phức tạp tính toán của giải thuật
Xác định độ phức tạp tính toán của một giải thuật bất kì có thể dẫn tới những
bài toán phức tạp. Tuy nhiên, trong thực tế, đối với một số giải thuật ta cũng có thể
phân tích được bằng một số quy tắc đơn giản như [2], [4]:
- Quy tắc tổng
Giả sử T1[n] và T2[n] là thời gian thực hiện của 2 đoạn chương trình P1 và P2
mà T1[n] = O[f[n]]; T2[n] = O[g[n]] thì thời gian thực hiện P1 rồi P2 tiếp theo sẽ là:
T1[n] + T2[n] = O[max[f[n], g[n]]].
Ví dụ, trong một chương trình có 3 bước thực hiện mà thời gian thực hiện
từng bước lần lượt là O[n2], O[n3] và O[log2n] thì thời gian thực hiện 2 bước đầu là
O[max[n2, n3]] = O[n3].
Một ứng dụng khác của quy tắc này là nếu g[n] ≤ f[n] với mọi n ≥ no thì
O[f[n] + g[n]] cũng là O[f[n]]. Chẳng hạn: O[n4+n2] = O[n4] và O[n+log2n] = O[n].
- Quy tắc nhân
Nếu tương ứng với P1 và P2 là T1[n] = O[f[n]]; T2[n] = O[g[n]] thì thời gian
thực hiện P1 và P2 lồng nhau sẽ là: T1[n].T2[n] = O[f[n].g[n]].
Ví dụ, câu lệnh gán: x := x+1 có thời gian thực hiện bằng c [hằng số] nên
được đánh giá là O[1].
Câu lệnh: for i := 1 to n do x := x+1; có thời gian thực hiện O[n.1]=O[n].
Câu lệnh: for i := 1 to n do
for j := 1 to n do x := x+1;
có thời gian thực hiện được đánh giá là: O[n.n] = O[n2]. Có thể suy ra
O[c.f[n]] = O[f[n]] chẳng hạn O[n2/2] = O[n2].
10
* Chú ý: Phép toán tích cực [active operation] đó là phép toán thuộc giải
thuật mà thời gian thực hiện nó không ít hơn thời gian thực hiện các phép khác [tất
nhiên các phép toán tích cực không phải là duy nhất] hay nói một cách khác: số lần
thực hiện nó không kém gì các phép khác. Thông thường đó là các phép toán cộng,
trừ, nhân, chia và các phép so sánh.
- Quy tắc tổng quát
1. Thời gian thực hiện mỗi câu lệnh Gán, Read, Write là O[1].
2. Thời gian thực hiện mỗi chuỗi tuần tự các câu lệnh được tính theo quy tắc
cộng.
3. Thời gian thực hiện cấu trúc if [điều kiện] then ... được tính bằng thời gian
thực hiện câu lệnh sau then hoặc sau else. Còn câu lệnh điều kiện thường là O[1].
4. Thời gian thực hiện vòng lặp được tính là tổng trên tất cả số lần lặp thời
gian thực hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp là hằng số thì
thời gian thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng
lặp.
Ví dụ 4: Giải thuật toán tính giá trị của ex:
x
1!
ex 1 +
x2
xn
với x và n cho trước.
...
2!
n!
Program EXP1;
{tính từng số hạng rồi cộng lại}
1. Read[x]; S :=1;
2. for i:=1 to n do
Begin
P:=1;
for j:=1 to i do p:=
p* x
;
j
S:=s+p;
End;
3. End.
Phép toán tích cực ở đây là phép p :=
p* x
.
j
11
Ta thấy nó được thực hiện
n * [n 1]
lần.
2
Vậy thời gian thực hiện giải thuật này được đánh giá là T[n] = O[n2].
1.5. Phân lớp các bài toán dựa trên độ phức tạp của thuật toán
Khi cho một bài toán, có hai khả năng xảy ra là: bài toán không giải được
hoặc bài toán giải được. Trong thực tế có rất nhiều các bài toán không thể giải trong
thời gian đa thức. Ví dụ bài toán treo [Halting Problem] nổi tiếng của Turing không
thể giải bất kỳ máy tính nào, bất kể cung cấp bao nhiêu thời gian. Cũng có các bài
toán có thể giải được, nhưng không phải trong thời gian đa thức O[nk] với một hằng
k. Nói chung, ta xem các bài toán có thể giải được bằng các thuật toán thời gian đa
thức là “dễ trị”, và các bài toán yêu cầu thời gian siêu đa thức là “khó trị”.
Vì độ phức tạp giải thuật đối với mỗi bài toán là khác nhau thông qua thời
gian đa thức và siêu đa thức, trên cơ sở đó các bài toán cũng được phân chia thành
các lớp thông qua độ phức tạp thuật toán [đa thức hay hàm mũ]. Đó là các lớp P,
NP, NPC được định nghĩa như sau [1], [11].
1.5.1. Lớp P
Lớp P [Polynomial time – thời gian đa thức] là lớp các bài toán dễ, có thể
giải được bằng thuật toán đơn định đa thức.
1.5.2. Lớp NP
Lớp NP [Nondeterministic Polynomial – thời gian đa thức không tất định] là
lớp các bài toán có thể giải được bằng các thuật toán không đơn định đa thức.
Nhiều giả thiết đặt ra rằng liệu lớp P và lớp NP có đồng nhất với nhau hay
không? Điều đó đang còn là vấn đề mở chưa được làm sáng tỏ. Bởi trong NP vẫn
tồn tại lớp các bài toán không giải được bằng các thuật toán đa thức, đó chính là sự
có mặt của lớp NPC. Như vậy, chúng ta đang chấp nhận P NP.
1.5.3. Lớp NPC
Để định nghĩa lớp NPC, dựa vào các khái niệm sau:
12
- Khái niệm dẫn về được: Bài toán B được gọi là dẫn về được bài toán A một
cách đa thức nếu có một thuật toán đơn định đa thức để giải bài toán A thì cũng có
một thuật toán đơn định đa thức để giải bài toán B. ký hiệu B A.
Khi đó bài toán A khó hơn bài toán B hay còn gọi B dễ hơn A hay B là
trường hợp riêng của A.
Quan hệ có tính bắc cầu: B C, C A B A.
- Khái niệm khó tương đương: Bài toán A được gọi là khó tương đương bài
toán B nếu như A B và B A. Ký hiệu A ~ B.
Bài toán NP – khó [NP hard]:
Bài toán A được gọi là NP – khó nếu có bài toán L A với L NP.
Bài toán NP đầy đủ
Bài toán A được goi là NP đầy đủ [NP-Complate] nếu:
A
là NP - khó
A
NP
Lớp NPC
Lớp NPC là lớp các bài toán NP đầy đủ, có độ phức tạp hàm mũ. Qua đó cho
thấy: P NPC = Ø.
Hình 1.1 minh họa các lớp P, NP, NPC dưới dạng tập hợp.
NP
NPC
P
Hình 1.1: Các lớp P, NP và NPC
KẾT LUẬN CHƯƠNG 1
Chương này luận văn trình bày những khái niệm cơ bản về bài toán - thuật
toán trong tin học, khái niệm về độ phức tạp của thuật toán và các nguyên tắc đánh
giá độ phức tạp. Trên cơ sở đó đưa ra nguyên tắc phân lớp các bài toán để tiến hành
lựa chọn giải thuật tốt nhất giải các lớp bài toán trong thực tế. Các kiến thức này đã
được tham khảo trong các tài liệu [2], [3], [4], [7].
13
Chương 2
MỘT SỐ THUẬT TOÁN CHỌN LỌC VÀ ỨNG DỤNG
2.1 Thuật toán đệ quy
2.1.1 Khái niệm đệ quy
Đệ quy [trong Tiếng Anh là recursion] là phương pháp dùng trong các chương
trình máy tính trong đó có một hàm tự gọi chính nó [2], [7]
Một khái niệm X được định nghĩa theo đệ quy nếu trong định nghĩa X có sử
dụng ngay chính khái niệm X.
Ví dụ 5: Để định nghĩa về số nguyên, người ta định nghĩa như sau
-
Số 1 là số nguyên
-
Nếu n >1 là số nguyên thì [n+1] cũng là số nguyên
Ví dụ 6: Để định nghĩa về số n!, người ta định nghĩa
-
Nếu n = 0 thì n! = 1
-
Nếu n > 0 thì n! = n*[n-1]!
Ví dụ 7: Để định nghĩa về cây, người ta định nghĩa
- R là gốc cây
- Cây là hợp của các tập hợp T1,T2,..,Tn trong đó các Ti cũng là cây
Trong các định nghĩa trên đều yêu cầu 2 vấn đề quan trọng
1. Luôn luôn tồn tại 1 trường hợp đặc biệt không định nghĩa được phải công
nhận [1 là số nguyên, 0!=1 hay R là gốc]
2. Luôn dùng khái niệm cấp thấp hơn để định nghĩa ra khái niệm cấp cao
hơn
+ Thuật toán đệ quy là một thuật toán mà khi thiết kế nó, ta dùng chính nó để
thiết kế ra nó, khi thực hiện nó thì sẽ tồn tại lời gọi đến chính nó.
Ví dụ 8: Xuất phát từ định nghĩa n! Ta có thể thiết kế 1 thuật toán đệ quy như sau:
Function giaithua[n:integer];
Begin
If n = 0 then giaithua = 1
else
14
giaithua = n*giaithua[n-1];
End.
Như vậy đặc điểm của thuật toán đệ quy đòi hỏi
1. Phải có định nghĩa đệ quy
2. Điểm dừng của thuật toán chính là trường hợp đặc biệt không định nghĩa
được.
3. Tồn tại lời gọi tới chính bản thân nó theo đúng định nghĩa.
Ví dụ 9: Định nghĩa dãy Fibonaci
B[n] = 1 nếu n = 1 hoặc n= 2 - Đây là trường hợp đặc biệt phải công nhận
B[n] = B[n-1] + B[n-2]
- Đây là định nghĩa theo đệ quy
Khi đó ta sẽ có thuật toán
Function B[n:integer];
Begin
if [n=1] or [n=2] then B=1
else B=B[n-1]+B[n-2];
End.
2.1.2 Giải thuật đệ quy và thủ tục đệ quy:
Một thủ tục gọi là đệ quy nếu trong quá trình thực hiện nó phải gọi đến chính
nó nhưng với kích thước nhỏ hơn của tham số.
- Cách xây dựng hàm, thủ tục đệ quy thường được viết theo thuật toán sau:
IF trường hợp suy biến THEN
Begin
trình bày cách giải bài toán
End
else
Begin
gọi đệ quy tới hàm, thủ tục đang xây dựng với bộ tham số mới
End;
15
Ví dụ 10: Để lập hàm tính giai thừa của một số nguyên không âm ta có thể làm theo
2 cách như sau:
Cách 1: Hàm tính n giai thừa dùng theo đệ quy
Function Giaithua [ n:longint ] : longint;
begin
if n = 0 then giaithua :=1
else giaithua := n * giaithua [ n-1];
end;
Cách 2: Hàm tính n giai thừa bằng cách dùng vòng lặp for:
Function Giaithua[ n: longint] : longint;
Var
i, GT : longint;
Begin
GT := 1;
If n > 0 then
For i:= 1 to n do GT := GT * i;
Giaithua := GT;
End;
Ví dụ 11: Xét bài toán tính tổng:
f[a,n]= a[1] + a[2] + …+ a[n]
+ Trường hợp suy biến là trường hợp n = 1, khi đó: f[a,n] = a[1]
+ Trường hợp tổng quát n>1, bài toán quy về việc tính tổng của [n-1] phần tử
như sau:
f[a,n] = [a[1] + … +a[n-1]] + a[n] = f[a, n-1] + a[n]
Hàm đệ quy tính tổng được viết như sau:
Type DS = Array [1..100] of Real;
Function TongDS [a: DS; n: Integer] : Real;
Begin
If n = 1 then
TongDS := a[1]
16
Else
TongDS := TongDS [a, n-1] + a[n];
End;
2.1.3 Cấu trúc và đặc điểm của đệ quy.
- Cấu trúc: Gồm 2 phần
+ Phần cơ sở: chứa các tác động của hàm hoặc thủ tục với một số giá trị cụ
thể ban đầu của tham số.
+ Phần đệ quy: định nghĩa tác động cần được thực hiện cho giá trị hiện thời
của các tham số bằng các tác động đã được định nghĩa trước đây với kích thước
tham số nhỏ hơn.
- Đặc điểm:
+ Trong thủ tục đệ quy có lời gọi đến chính nó.
+ Mỗi lần có lời gọi lại thủ tục thì kích thước của bài toán thu nhỏ hơn trước.
+ Sử dụng đệ quy là một phương pháp làm cho chương trình ngắn gọn, dễ
hiểu nhưng nó sẽ làm tốn bộ nhớ và thời gian nếu như cấu trúc hàm đệ quy “phức
tạp”.
2.1.4 Một số bài toán thường gặp trong đệ quy:
Thực tế có rất nhiều bài toán có sử dụng giải thuật đệ quy như bài toán tính
giai thừa của n! hay bài toán tính giá trị của dãy Fibonacci … Trong luận văn chỉ đi
sâu vào một vài bài toán điển hình nhất trong đó đã đưa ra được bản chất nổi bật
nhất của đệ quy.
Ví dụ 12: Bài toán Tháp Hà Nội.
Bài toán: Có 3 cái cọc , đánh dấu A, B, C và N cái đĩa. Mỗi đĩa đều có một lỗ
chính giữa để đặt xuyên qua cọc, các đĩa đều có kích thước khác nhau. Ban đầu tất
cả các đĩa đều được đặt ở cọc thứ nhất theo thứ tự đĩa nhỏ hơn ở trên.
Yêu cầu của bài toán là chuyển tất cả các đĩa từ cọc A qua cọc C với 3 ràng
buộc như sau:
1. Mỗi lần chỉ chuyển được một đĩa.
2. Trong quá trình chuyển đĩa có thể dùng cọc còn lại [B] để làm cọc trung
17
gian.
3. Chỉ cho phép đặt đĩa có bán kính nhỏ hơn lên đĩa có bán kính lớn hơn.
Phân tích bài toán:
Trong bài toán trên hình dung một lời giải tổng quát cho trường hợp tổng
quát N là không dễ dàng.
Hãy bắt đầu với các trường hợp đơn giản sau:
- Với N = 1: Chỉ cần chuyển đĩa này từ cọc A qua cọc C là xong.
- Với N = 2: Để đảm bảo ràng buộc thứ hai ta bắt buộc chuyển đĩa trên cùng
từ cọc A qua cọc B. Chuyển tiếp đĩa còn lại từ cọc A qua cọc C. Chuyển tiếp đĩa
đang ở cọc B sang cọc C.
- Với N = 3: ta phải thực hiện 7 bước như sau:
Hình 2.1 Mô tả bước chuyển của đĩa
Nhận xét:
Ở kết quả của bước thứ ba. Đây là một kết quả quan trọng vì nó cho ta thấy
từ trường hợp N = 3 bài toán đã được phân chia thành hai bài toán với kích thước
nhỏ hơn. Đó là bài toán chuyển 1 đĩa từ cọc A qua cọc C lấy cọc B làm trung gian
và bài toán chuyển 2 đĩa [dời] từ cọc B sang cọc C lấy cọc A làm trung gian. Hai
bài toán con này đã biết cách giải [trường hợp N = 1 và trường hợp N = 2].
18
+ Nhận xét đó cho ta gợi ý trong trường hợp tổng quát:
Bước 1: Dời [N-1] đĩa trên cùng từ cọc A sang cọc B lấy cọc C làm trung
gian.
Bước 2: Chuyển 1 đĩa dưới cùng từ cọc C.
Bước 3: Dời [N-1] đĩa đang ở cọc B sang cọc C lấy cọc A làm trung gian.
Như vậy, bài toán đối với N đĩa ở trên được “đệ quy” về hai bài toán [N-1]
đĩa và bài toán 1 đĩa. Quá trình đệ qui sẽ dừng lại khi N = 0 [không còn đĩa để dời
hoặc chuyển].
- Giải thuật đệ quy cho bài toán tháp Hà Nội:
Procedure dich_chuyen[n, A, B, C];
1. if n = 1 then chuyển đĩa từ A sang C
2.
else
begin
dich_chuyen[n-1, A, C, B];
dich_chuyen[1, A, B, C];
dich_chuyen[n-1, B, A, C]
end
3. return
2.2 Thuật toán tham lam
2.2.1 Tổng quan về thuật toán tham lam
2.2.1.1 Thuật toán tham lam là gì?
Thuật toán tham lam [Tiếng Anh: Greedy algorithms] là một thuật toán giải
quyết một số bài toán theo kiểu metaheuristic để tìm kiếm lựa chọn tối ưu địa
phương ở mỗi bước đi với hy vọng tìm được tối ưu toàn cục [1], [3].
2.2.1.2 Đặc điểm của thuật toán tham lam
Mục đích của thuật toán tham lam là xây dựng bài toán giải nhiều lớp bài
toán khác nhau, đưa ra quyết định dựa ngay vào thuật toán đang có, và trong tương
lai sẽ không xem xét lại quyết định trong quá khứ.
19
Ưu điểm của thuật toán tham lam
- Dễ đề xuất.
- Thời gian tính nhanh.
Đặc điểm
Lời giải bài toán là một tập hữu hạn S các phần tử thỏa mãn điều kiện nào đó,
ta phải giải quyết bài toán một cách tối ưu. Nói cách khác nghiệm S phải được xây
dựng sao cho hàm mục tiêu f[S] có giá trị tốt nhất [lớn nhất, nhỏ nhất] có thể.
Các bước giải bài toán như sau
- Có một tập các ứng cử viên C để chọn cho các thành phần của nghiệm tại
mỗi bước.
- Xuất phát từ lời giải rỗng S, tại mỗi bước của thuật toán, ta sẽ lựa chọn một
ứng cử viên trong C để bổ sung vào lời giải S hiện có.
- Xây dựng được hàm Seclect[C] tại mỗi bước chọn để lựa chọn một ứng cử
viên có triển vọng nhất để đưa vào lời giải S.
- Xây dựng được hàm Feasible[Sx] để kiểm tra tính chấp nhận được ứng
cử viên x khi đưa vào tập nghiệm S.
- Cuối cùng khi có được tập S, xây dựng hàm Soluition[S] để kiểm tra tính
chấp nhận được của lời giải S.
2.2.1.3 Điều kiện để một bài toán áp dụng được giải thuật tham lam
Các dạng bài toán tìm phương án tối ưu như bài toán người du lịch, bài toán
cái túi … Chúng thuộc lớp các bài toán tối ưu tổ hợp là một trường hợp riêng của
bài toán tối ưu.
Các bài toán tối ưu tổ hợp có rất nhiều ứng dụng trong thực tiễn và việc ứng
dụng trở nên tốt hơn rất nhiều khi người ta nghiên cứu các thuật toán tối ưu và cài
đặt trên máy tính.
Một trong những thuật toán để giải quyết các bài toán trên là thuật toán
tham lam.
Thuật toán tham lam [Greedy Algorithms] được dùng để giải quyết các bài
toán mà chúng ta có thể quyết định đâu là lựa chọn tốt nhất.
20
Nếu có thể chứng minh rằng một thuật toán tham lam cho ra kết quả tối ưu
toàn cục cho một lớp bài toán nào đó, thì thuật toán thường sẽ trở thành phương
pháp được chọn lựa, vì nó chạy nhanh hơn các phương pháp tối ưu hóa khác như
quy hoạch động. Tuy nhiên trong một số trường hợp thuật toán tham lam chỉ cho
nghiệm gần đúng với nghiệm tối ưu.
2.2.1.4 Những dạng bài toán thường dùng thuật toán tham lam để giải
- Các thuật toán tham lam chủ yếu để giải quyết các bài toán tối ưu.
- Các bài toán tối ưu là các bài toán có dạng tổng quát như sau
1. Hàm f[x] được gọi là hàm mục tiêu, xác định trên một tập hữu hạn các phần
tử D.
2. Mỗi phần tử X thuộc D có dạng X=[x1, x2,….,xn] được gọi là một phương
án.
3. Tìm một phương án X0 thuộc D sao cho f[x] đạt giá trị lớn nhất hoặc đạt giá
trị nhỏ nhất trên D. Thì X0 được gọi là phương án tối ưu.
4. Tập D được gọi là tập các phương án của bài toán.
Ví dụ như các dạng bài toán sau
- Một tập các đối tượng
- Một dãy các đối tượng đã lựa chọn
- Một hàm để xem một tập các đối tượng có lập thành một giải pháp hay
không [không nhất thiết tối ưu]
- Một hàm để xem một tập đối tượng có là tiềm năng hay không
- Một hàm để lựa chọn ứng viên có triển vọng nhất
- Một hàm đích cho một giá trị của một giải pháp [để tối ưu hóa]
2.2.2 Vấn đề thiết kế thuật toán
2.2.2.1 Các thành phần của thuật toán tham lam
Xét bài toán chọn hoạt động, ta định nghĩa bài toán con Sij với i j, nếu luôn
thực hiện lựa chọn tham lam ta có thể giới hạn các bài toán con được thành lập bởi
Si,n+1
21
Như một sự lựa chọn, ta có thể tạo nên cấu trúc con tối ưu với một lựa chọn
tham lam có nghĩa. Điều đó có nghĩa là, có thể bỏ qua chỉ số dưới thứ hai và định
nghĩa các bài toán con của công thức si {a k S fi sk } . Sau đó, chứng minh rằng
một lựa chọn tham lam [hoạt động đầu tiên am để kết thúc si] kết hợp với một giải
pháp tối ưu để đi đến tập còn lại Sm của các hoạt động tương thích, mang lại một
giải pháp tối ưu đối với Si. Một cách tổng quát, thuật toán tham lam được thiết kế
theo các bước:
1. Tìm lựa chọn sao cho bước tiếp theo chỉ giải quyết một bài toán con.
2. Chứng minh với sự lựa chọn tham lam tại mỗi bước ta luôn tìm được một
giải pháp tối ưu của bài toán ban đầu.
3. Chỉ ra rằng với sự lựa chọn tham lam tại mỗi bước, giải pháp tối ưu của
bài toán con còn lại kết hợp với sự lựa chọn tham lam này sẽ đi đến một giải pháp
tối ưu cho bài toán ban đầu.
Không có cách tổng quát cho một thuật toán tham lam giải quyết một bài
toán tối ưu, nhưng chiến lược lựa chọn tham lam và cấu trúc con tối ưu là hai thành
phần then chốt, thực tế đã chứng minh rằng các bài toán có 2 thuộc tính này là rất
thuận lợi cho việc xây dựng một thuật toán tham lam giải quyết nó.
Nói chung, giải thuật tham lam thường có 5 thành phần
1. Một tập hợp các ứng cử viên [tập giá trị đề cử] để từ đó tạo ra lời giải.
2. Một hàm lựa chọn [select] để theo đó lựa chọn ứng cử viên tốt nhất để bổ
sung vào lời giải.
3. Một hàm khả thi, dùng để quyết định nếu một ứng cử viên có thể được dùng
để xây dựng lời giải.
4. Một hàm mục tiêu, ấn định giá trị của lời giải hoặc một lời giải chưa hoàn
chỉnh.
5. Một hàm đánh giá, chỉ ra khi nào tìm được một lời giải hoàn chỉnh
Trong 5 thành phần trên có 2 yếu tố quyết định tới tính tham lam của thuật toán:
+ Tính lựa chọn tham lam: Đây là thành phần then chốt đầu tiên, một giải
pháp tối ưu toàn cục có thể đạt được bằng cách lựa chọn tối ưu cục bộ [tham lam].
22
Như vậy, khi có nhiều sự lựa chọn thì ta lựa chọn phương án nào tốt nhất ở
hiện tại trong bài toán đang xét mà không cần quan tâm đến kết quả của các bài toán
con của nó.
+ Cấu trúc con tối ưu: Một bài toán có cấu trúc con tối ưu nếu giải pháp tối
ưu cho bài toán này chứa trong nó các giải pháp tối ưu cho các bài toán con. Thuộc
tính này là điểm quyết định để có thể giải bài toán bằng phương pháp quy hoạch
động cũng như tham lam được hay không?
Thuật toán tham lam có được một giải pháp tối ưu cho một bài toán bằng
cách thực hiện một chuỗi các lựa chọn. Đối với mỗi quyết định chỉ ra trong thuật
toán sự lựa chọn này thường là tốt nhất tại thời điểm được chọn.
Chứng minh:
- Theo tính chất lựa chọn tham lam, tồn tại giải pháp tối ưu S chứa một lựa
chọn tham lam a1. Theo tính chất cấu trúc con tối ưu, X-{a1} là giải pháp tối ưu của
bài toán con không chứa a1.
- Áp dụng cho bài toán con không chứa a1, theo tính chất lựa chọn tham lam,
X-{a1} là giải pháp tối ưu chứa lựa chọn tham lam a2. Theo tính chất cấu trúc con tối
ưu, X-{a1,a2} là giải pháp tối ưu cho bài toán con không chứa a1 và a2.
- Tiếp tục như thế, cuối cùng ta có:
X- {a1,a2,…,an} = .
Vậy giải pháp tối ưu X của bài toán ban đầu là một dãy các sự lựu chọn tham
lam thực hiện bởi thuật toán tham lam.
2.2.2.2 Sơ đồ chung để giải các bài toán bằng giải thuật tham lam
Tư tưởng của phương pháp tham lam
Ta xây dựng tập S dần từng bước, bắt đầu từ tập rỗng. Tại mỗi bước ta sẽ
chọn một phần tử “tốt nhất” trong các phần tử còn lại của A để đưa vào S. Việc lựa
chọn một phần tử như thế ở mỗi bước được hướng dẫn bởi hàm chọn. Phần tử được
chọn sẽ bị loại khỏi tập A. Nếu khi thêm phần tử được chọn vào tập S mà S vẫn còn
thỏa mãn các điều kiện của bài toán thì ta mở rộng S bằng cách thêm vào phần thử
được chọn.
23
Mô hình:
Chọn S từ tập A.
Tính chất tham lam của thuật toán định hướng bởi hàm Chọn
- Khởi động S = ;
- Trong khi A ≠ ;
Chọn phần tử tốt nhất của A gán vào x : x = Chọn [A];
Cập nhật các đối tượng để chọn A : A = A - x;
Nếu S x thỏa mãn yêu cầu bài toán thì:
Cập nhật lời giải: S = S x
- Thủ tục thuật toán tham lam
+ Input A// Tập các đối tượng cho trước
+ Output X //Lời giải, xây dựng phương án X từ A
Greedy_Method[A,X];
Begin
X:= [];
While [ A ] Do
Begin
X = Select[A];// Hàm chọn x tốt nhất trong A
A = A-{x}// Loại x ra khỏi A
If [ X U {x} chấp nhận được] then X = X U {x};
Return X;
End;
End;
Trong thủ tục tổng quát trên, Select là hàm chọn, cho phép chọn từ tập A một
phàn tử được xem là tốt nhất, nhiều hứa hẹn nhất là thành viên của tập nghiệm.
2.2.3 Một số bài toán áp dụng thuật toán tham lam
Bài toán xếp lịch cho các hoạt động
1. Mô tả bài toán
24
- Xét S = {a1,a2,..,an} là tập các hoạt động muốn sử dụng tài nguyên [vd: hội
trường]
- Mỗi hoạt động ai sẽ có thời điểm bắt đầu là Si và thời điểm kết thúc là fi,
với điều kiện 0 ≤ Si < fi < ∞. Nếu hoạt động ai được chọn, thì nó sẽ độc chiếm tài
nguyên trong khoảng thời gian [Si,fi]. Hoạt động ai và aj được gọi là tương thích lẫn
nhau nếu như khoảng thời gian [Si,fi] và [Sj,fj] là không giao nhau
2. Yêu cầu: Mỗi thời điểm chỉ có 1 hoạt động sử dụng tài nguyên chung.
3. Mục tiêu: Chọn được một tập lớn nhất các hoạt động tương thích với nhau
[khoảng thời gian thực hiện không giao nhau] => Tận dụng tối đa tài nguyên.
Ví dụ ai và aj là tương thích nếu Si ≥ fj hoặc Sj ≥ fi
4. Ý tưởng giải quyết bài toán
Xét một bài toán con khác rỗng Sij, và nếu am là một hoạt động trong Sij có
thời điểm kết thúc sớm nhất: fm = min{f k: ak Sij}. Thì:
• Hoạt động am được sử dụng trong một tập con lớn nhất nào đó của các hoạt
động tương thích lẫn nhau của Sij.
• Bài toán con Sim là rỗng, do đó nếu chọn am thì chỉ còn duy nhất bài toán
con khác rỗng Smj.
Mục tiêu :
Giảm số các bài toán con và số cách chọn:
Chỉ duy nhất một bài toán con được sử dụng trong giải pháp tối ưu [một bài
toán con khác rỗng]
Chỉ cần 1 chọn lựa cho bài toán con: chọn hoạt động nào có thời gian kết thúc
sớm nhất trong Sij [dễ dàng].
Có thể giải mỗi bài toán con theo phương pháp top down [thay vì bottom up
trong lập trình động].
Vì khi chọn am chắc chắn lời giải Smj sẽ được dùng trong lời giải tối ưu của
Sij không cần giải Smj trước khi giải Sij
Tóm lại: Để giải bài toán con Sij, đầu tiên chọn hoạt động am trong Sij có thời
gian kết thúc sớm nhất rồi mới tìm lời giải cho bài toán con Smj
25
5. Chương trình minh họa cho thuật toán
- Input:
Mảng S và f biểu diễn thời điểm bắt đầu và kết thúc của các hoạt động
Giả sử N hoạt động đã xếp theo thứ tự tăng dần của thời điểm kết thúc.
f 0 ≤ f1 ≤ f2 ≤ ... ≤ fn ≤ fn+1
- Output:
Trả về một tập lớn nhất của các hoạt động tương thích với nhau trong Si, n+1
Chương trình:
RECURSIVE-ACTIVITY-SELECTOR [s ,f ,i, n]
M i+1
While m < n and sm< fi {Tìm hoạt động đầu tiên trong Si, n+1}
Do mi+1
If m < n Then
Return {am} U RECURSIVE-ACTIVITY-SELECTOR[s ,f ,m ,n]
Else Return Ø
2.3 Thuật toán xấp xỉ [Heuristic]
2.3.1 Các khái niệm
Thuật toán xấp xỉ là các thuật toán tìm lời giải xấp xỉ cho các bài toán tối ưu
hóa. Thuật toán xấp xỉ thường được sử dụng cho các bài toán NP - khó, hoặc các
bài toán có thuật toán đa thức nhưng quá chậm cho dữ liệu lớn [1].
Người ta cho rằng ngày nay máy tính với tốc độ rất lớn, không cần quan tâm
nhiều tới thuật toán nhanh nhưng với sự kiểm chứng sau đây: Bài toán xử lý với n
đối tượng, có 3 thuật toán với 3 mức phức tạp khác nhau, sau 1 giờ xử lý sẽ chịu 3
hậu quả khác nhau.
Thuật toán Độ phức tạp
Xử lý/1 giờ
A
O[n]
3,6 triệu đối tượng
B
O[nlog2n]
0,2 triệu đối tượng
C
O[2n]
21 đối tượng