Giải bài toán có túi bằng phương pháp vét cạn

Tuần 1: 1. Khái niệm thuật toán - Định nghĩa. - Các tính chất. - Ví dụ minh họa: Tìm phần tử bé nhất trong dãy có n số cho trước. 1. Biểu diễn thuật toán - Sơ đồ khối. Ký hiệu. Ví dụ minh họa: Tìm phần tử bé nhất trong dãy có n số cho trước. - Giả mã. Yêu cầu. Ví dụ minh họa: Tìm phần tử có giá trị bằng b trong dãy có n số cho trước (làm rõ là tìm tất cả, phần tử đầu tiên, cuối cùng, hay phần tử bất kỳ). - Chất lượng biểu diễn thuật toán. 1. Tính đúng đắn và hiệu quả của thuật toán - Tính đúng đắn: Phương pháp lý thuyết, phương pháp thực nghiệm. - Tính hiệu quả: Phương pháp lý thuyết và phương pháp thực nghiệm. Bài tập: 1) Thuật toán sinh dãy nhị phân. 2) Viết chương trình cho bài toán ba lô dựa trên duyệt tất cả các phương án. 3) Tìm số m lớn nhất có tính chất ở cơ số 16 có tổng các chữ số bằng n cho trước. Thuật toán tốt và thuật toán kém. 4) Phân biệt chính xác input, output của bài toán và trong mô tả thuật toán. Thuật toán giải phương trình, hệ phương trình. Câu hỏi ôn tập và bài tập tự làm:

1. Chứng minh tính đúng đắn của các thuật toán trong các ví dụ 1, 1, 1.
2. Cho xâu kí tự S có độ dài n. Hãy xây dựng thuật toán để tìm một đoạn dài nhất trong S gồm các kí tự liên tiếp khác nhau.
3. Cho L là dãy có n số nguyên. Hãy tìm dãy con liên tiếp có tổng các phần tử đạt giá trị dương nhỏ nhất. Tuần 2:
   1. Độ tăng của hàm
      • Các định nghĩa.
      • Các tính chất.
      • Ví dụ minh họa: Tính giá trị đa thức và thuật toán Hoorner, tính C(k,n) = n!/(k!(n- k)!).
      • Thuật toán Euclid tìm ước số chung lớn nhất của hai số nguyên dương a và b. Định lý Lamé.
   2. Độ phức tạp của thuật toán
      • Khái niệm
      • Lớp P và NP
      • Một số bài toán tối ưu rời rạc.
   3. Đánh giá hiệu quả bằng thực nghiệm.
4. Chuẩn bị số liệu thực nghiệm.
5. Lựa chọn thông số đánh giá.
6. Ví dụ minh họa: o Đánh giá thời gian tính: Bài toán ba lô, bài toán tô màu, o Đánh giá về số vòng lặp thực tế so với số vòng lặp lý thuyết: tìm ước số chung lớn nhất của hai số nguyên dương. Bài tập:
7. Đánh giá một số thuật toán thông thường.
8. Đánh giá về thời gian thực cho bài toán ba lô dựa trên duyệt mọi khả năng.
9. Sử dụng phương pháp vét cạn để giải bài toán tô màu với số màu bằng 2, 3. Đồ thị được cho bởi danh sách cạnh. Câu hỏi ôn tập và bài tập tự làm:
10. Cho xâu kí tự S có độ dài n. Xây dựng thuật toán thuộc O( n ) để tìm một đoạn dài nhất trong S gồm các kí tự liên tiếp khác nhau.
11. Cho L là dãy có n số nguyên. Xây dựng thuật toán thuộc O( n ) tìm dãy con liên tiếp có tổng các phần tử đạt giá trị dương nhỏ nhất.
12. Đánh giá thời gian thực thuật toán tô màu bằng phương pháp vét cạn.
13. Xây dựng kỹ thuật chỉ ra mọi phương án có thể của các bài toán tối ưu rời rạc (chủ yếu là không bỏ sót lời giải của bài toán - phục vụ cho kỹ thuật giải quyết bài toán bằng phương pháp duyệt mọi phương án có thể có).

Chương 2. Một số kỹ thuật thiết kế thuật toán (tuần 3 - 7)

Tuần 3: 2. Kỹ thuật thiết kế tuần tự - Ý tưởng - Ví dụ: nhân một số nguyên lớn với số có một chữ số, tìm xâu con dài nhất các ký tự liên tiếp khác nhau, thao tác với xâu kí tự. 2. Kỹ thuật thiết kế theo cấu trúc - Ý tưởng. - Ví dụ: Tính tích của hai số nguyên lớn. Bài tập:

1. Sửa lỗi soạn thảo cho xâu kí tự.
2. Thuật toán không đệ quy tìm nghiệm của phương trình f (x) = 0.
3. Tìm giá trị gần đúng của a, a>0. Câu hỏi ôn tập và bài tập tự làm:
   1. Từ là một dãy liên tiếp các chữ cái Latin. Cho xâu kí tự S gồm các từ. Xây dựng thuật toán tìm từ dài nhất trong S. Đánh giá độ phức tạp của thuật toán xây dựng được.
   2. Một xâu gọi là xâu đối xứng nếu đem đảo ngược xâu đó ta lại nhận được xâu ban đầu. Cho xâu S, hãy tìm số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng.
   3. Cho hai xâu A và B. Xâu S được gọi là bao A và B nếu A và B là các xâu con liên tiếp của S. Tìm xâu bao ngắn nhất của A và B.
   4. Mỗi đoạn thẳng trên trục O x được mô tả bới hai giá trị [ a , b ]. Kí hiệu S là tập hợp n đoạn thẳng S = { [ ai , bi ], i = 1,2,..., n }. Xây dựng thuật toán tìm tập S* có nhiều phần tử nhất thuộc S sao cho các đoạn thẳng trong S* đôi một không có điểm chung.

Tuần 6: 2. Kỹ thuật chia để trị - Ý tưởng - Ví dụ minh họa: 1. Tìm min, max của dãy số 2. Hòa nhập đơn giản. Định lý về chi phí tính toán. 3. Sắp xếp phân đoạn. 4. Tìm hai phần tử trong dãy số cho trước có tổng bằng K cho trước. Bài tập:

1. Cho một tập gồm 200 bài thi, mỗi bài được trình bày trên giấy A4, có ghi đầy đủ họ tên. Được phép sử dụng 2 bàn làm việc rộng 120cm70cm. Hãy chỉ ra cách sắp xếp cái bài thi theo tên dựa trên thứ tự từ điển tiếng Việt. Tính số theo tác phải thực hiện.
2. Cho hai số nguyên a và b có không quá 10 100 chữ số. Tính tích c = ab.

Câu hỏi ôn tập và bài tập tự làm:

1. Sử dụng ý tưởng chia để trị xây dựng thuật toán tìm phần tử bé nhất, lớn nhất trong một dãy số. Đánh giá số phép toán so sánh phải thực hiện. Đối chiếu với thuật toán tìm kiếm tuần tự.
2. Cho dãy A có n phần tử là các số nguyên. Tìm dãy con liên tiếp có tổng lớn nhất của A. Kiểm tra giữa kỳ lần 1. Tuần 7:
3. Kỹ thuật liệt kê
4. Cơ sở thuật toán
5. Ví dụ minh họa: liệt kê các dãy nhị phân, liệt kê các hoán vị.
6. Lựa chọn cấu trúc dữ liệu thích hợp
7. Ý tưởng.
8. Ví dụ:
9. Xác định tên theo âm lịch của một năm;
10. Tìm dãy con liên tiếp có tổng không âm nhỏ nhất trong một dãy cho trước. Bài tập:
11. Liệt kê phân hoạch một tập hợp.
12. Liệt kê phân hoạch một số nguyên. Câu hỏi ôn tập và bài tập tự làm:
13. Xây dựng thuật toán liệt kê dãy nhị phân độ dài n theo từ điển ngược.
14. Liệt kê mọi phương án có thể để tô màu đồ thị G = {V, E}, với các đỉnh được đánh số từ 1 đến n và các cạnh được cho bởi danh sách cạnh.
15. Cho tập S chứa các phần tử là các số nguyên dương a 1 , ..., an và số nguyên dương T, trong đó ai ≤ T, với  i = 1, 2, .., n. Liệt kê mọi phương án xếp các đồ vật vào các túi có sức chứa T.
16. Giả thiết có balô với dung lượng T và n đồ vật với trọng lượng a 1 , a 2 , ..., an và giá trị tương ứng c 1 , c 2 , ..., cn. Liệt kê mọi phương án xếp các đồ vật vào ba lô có sức chứa T.
17. Có n thành phố và giữa các thành phố xác định một thông số là chi phí đi lại. Một hành trình là một cách đi xuất phát từ một thành phố, qua tất cả các thành phố còn lại và quay lại vị trí xuất phát. Liệt kê mọi hành trình có thể.

Chương 3. Sắp xếp và tìm kiếm (tuần 8-10)

Tuần 8:

1. Bài toán sắp xếp
   • Phát biểu bài toán
   • Đánh giá tốt nhất
2. Các thuật toán sắp xếp chọn, chèn, nổi bọt
   • Ý tưởng.
   • Thuật toán.
   • Ví dụ minh họa.
   • Đánh giá số phép so sánh, số lần đổi chỗ các phần tử. Câu hỏi ôn tập và bài tập tự làm:
3. Cho A là ma trận m  n , có mỗi phần tử là một số nguyên. Sắp xếp ma trận A sao cho các phần tử trên cùng một hàng thì không giảm từ trái qua phải và các phần tử trên cùng một cột thì không giảm từ trên xuống dưới.
4. Mỗi đoạn thẳng trên trục O x được mô tả bới hai giá trị [ a , b ]. Kí hiệu S là tập hợp n đoạn thẳng S = { [ ai , bi ], i = 1,2,..., n }. Xây dựng thuật toán tìm tập S* có nhiều phần tử nhất thuộc S sao cho các đoạn thẳng trong S* đôi một không có điểm chung. Sắp xếp không giảm theo ai, i=1,..,n hoặc theo bi, i=1,..,n, và sau đó dùng kỹ thuật tham lam để giải bài toán. So sánh hiệu quả của hai cách sắp xếp.

Tuần 9:

1. Thuật toán sắp xếp vun đống
   • Ý tưởng. Thuật toán.
   • Ví dụ minh họa. Đánh giá. Bài tập:
   • Thực hiện bằng số trên một mảng. Đánh giá các trường hợp xấu nhất, tốt nhất, trung bình;
   • Cách áp dụng giải quyết bài toán thực tế. Nêu một ví dụ thực tế: xếp bài thi trong một túi. Câu hỏi ôn tập và bài tập tự làm:
2. So sánh thực nghiệm 6 thuật toán: sắp xếp chọn, sắp xếp chèn, sắp xếp nổi bọt, sắp xếp phân đoạn, sắp xếp hòa nhập và sắp xếp vun đống.
3. Cho dãy n bản ghi X={X 1 , X 2 , .., Xn}, mỗi bản ghi có một trường dữ liệu K. K nhận một trong các giá trị {1, 2, 3}. Xây dựng thuật toán có độ phức tạp O( n ) để sắp xếp X không giảm theo K.

Tuần 10:

1. Thuật toán tìm kiếm tuần tự
   • Ý tưởng. Thuật toán.
   • Ví dụ minh họa. Đánh giá.
2. Thuật toán tìm kiếm nhị phân
3. Ví dụ minh họa 1: T = 10, a = (5, 4, 6), c = (4, 10, 3)
4. Chi tiết thuật toán
5. Tính đúng đắn của thuật toán quy hoạch động giả bài toán ba lô Bài tập :
6. Phân tích ví dụ đầu tư, ví dụ khai thác mỏ của Belman.
7. Xây dựng chiến lược tối ưu cho: a. Bài toán chia đôi đồ vật; b. Bài toán cực đại gá trị biểu thức số học (có các phép toán cộng, trừ), đại số.

Câu hỏi ôn tập và bài tập tự làm:

1. Xây dựng thuật toán giải bài toán cực đại gá trị biểu thức số học (có các phép toán cộng, trừ), đại số.
2. Có các đồng xu với mệnh giá là các số nguyên c 1 , c 2 , ..., cn. Chọn số đồng xu ít nhất để đạt tổng T. Đánh giá độ phức tạp của các thuật toán xây dựng được.

Tuần 12:

Bài toán ba lô (knapsack) 0-1. 4. Đánh giá thuật toán 1. So sánh lý thuyết các thuật toán: vét cạn, gần đúng và quy hoạch động 2. Ví dụ minh họa 2: T = 12, a = (2, 7, 1, 5, 4), c = (2, 5, 2, 4, 10) 3. Cài đặt chương trình 4. So sánh thực nghiệm các thuật toán: vét cạn, gần đúng và quy hoạch động 4. Bài toán dãy con chung dài nhất 1. Phát biểu bài toán 2. Trạng thái khởi tạo, quyết định ban đầu 3. Chiến lược tối ưu 4. Chi tiết thuật toán 5. Tính đúng đắn của thuật toán Bài tập :

1. Cài đặt cho thuật toán tìm dãy con chung dài nhất của hai dãy.

Câu hỏi ôn tập và bài tập tự làm:

1. Dãy con chung dài nhất của 3 dãy X, Y, Z.
2. Một xâu gọi là xâu đối xứng nếu đem đảo ngược xâu đó ta lại nhận được xâu ban đầu. Cho xâu S, hãy tìm số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứngả thiết các thao tác chèn kí tự tốn kém thời gian không đáng kể.
3. Cho hai xâu A và B. Xâu S được gọi là bao A và B nếu A và B là các xâu con liên tiếp của S. Tìm xâu bao ngắn nhất của A và B. Kiểm tra giữa kỳ lần 2.

Tuần 13:

1. Bài toán dãy con đơn điệu dài nhất (Longest Monotone Subsequence - LMS)
   1. Phát biểu bài toán
   2. Trạng thái khởi tạo, quyết định ban đầu
   3. Chiến lược tối ưu
   4. Chi tiết thuật toán
2. Tính đúng đắn của thuật toán

Xét một số bài toán ứng dụng: Sắp xếp nhiều cuộc họp vào một phòng họp, sắp xếp các cuộc họp sao cho tốn ít phòng nhất (kết hợp quy hoạch động và tham lam để giải gần đúng).