SKKN Sử dụng Quy hoạch động để giải quyết một số bài toán trong bồi dưỡng học sinh giỏi môn Tin học

ĐẶT VẤN ĐỀ
I. Lý do chọn đề tài
1. Xuất phát từ xu hướng tuyển sinh của các trường Đại học có ngành học về Công nghệ thông tin. Hiện nay một số trường Đại học sử dụng kết quả kì thi học sinh giỏi tỉnh để làm một tiêu chí lựa chọn xét tuyển.
Tin học lập trình là một môn học khó đối với học sinh THPT. Làm thế nào để học sinh hiểu, học tốt, yêu thích và tham gia tốt các kỳ thi học sinh giỏi Tin học là điều mà nhiều giáo viên dạy tin học trăn trở.
Trong tin học, bài toán là một việc nào đó mà ta muốn máy tính thực hiện, để giải bài toán chúng ta cần có các thuật toán. Thuật toán là 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 từ input sau khi thực hiện dãy thao tác đó ta thu được output cần tìm của bài toán. Như vậy một bài toán có thể dùng rất nhiều thuật toán để giải quyết, vấn đề là chọn thuật toán nào hay phương pháp nào phù hợp với từng kiểu bài để đạt hiệu quả cao nhất.
Chương trình Tin học phổ thông đã có một số thuật toán để giải một lớp bài toán nhất định như: các thuật toán Sắp xếp, tìm kiếm …và một số phương pháp thiết kế thuật toán như: Chia để trị, tham lam, quy hoạch động…
2. Từ thực tế giảng dạy của bản thân chúng tôi nhận thấy việc nắm vững các thuật toán và áp dụng nó một cách linh hoạt trong các bài tập nhất định là không đơn giản. Khi nào thì chúng ta cần đến quy hoạch động? Đó là một câu hỏi rất khó trả lời. Không có một công thức nào cho các bài toán như vậy. Để có thể nhận dạng một bài toán có thể thực hiện với thuật toán này không phải dễ, ngoài ra để cài đặt được thuật toán hiệu quả nhất cũng đòi hỏi người lập trình nắm vững các phương pháp thiết kế thuật giải.
3. Trên cơ sở đó, chúng tôi trăn trở nghiên cứu đề tài “Sử dụng Quy hoạch động để giải quyết một số bài toán trong bồi dưỡng học sinh giỏi môn Tin học”.
II. Đối tượng nghiên cứu
Đề tài tập trung nghiên cứu, tìm hiểu, phân tích từ 30 bài tập cơ bản đến nâng cao và 10 bài toán luyện tập dạng bài tập về quy hoạch động, để tìm ra nhiều cách làm khác nhau, đánh giá độ phức tạp, đo thời gian thực hiện chương trình, để so sánh tìm ra chương trình tối ưu nhất và dễ hiểu nhất trong các chương trình đã đưa ra.
III. Phương pháp nghiên cứu
– Phương pháp nghiên cứu lí luận
– Phương pháp thống kê, xử lí số liệu
– Phương pháp đặt vấn đề – giải quyết vấn đề
– Phương pháp phân tích, tổng hợp
– Phương pháp Test
1
– Phương pháp thực nghiệm
– Phương pháp so sánh đối chiếu
IV. Cấu trúc của đề tài
Phần một: Đặt vấn đề Phần hai: Nội dung Phần ba: Kết luận
2

I. Cơ sở của đề tài
1. Cơ sở lí luận
1.1. Khái niệm
Khi nào nên áp dụng thuật toán quy hoạch động?
NỘI DUNG
Quy hoạch động (dynamic programming) là kỹ thuật trong lập trình giúp đơn giản hóa hiệu quả việc chia bài toán lớn thành các bài toán con chồng chéo và cấu trúc con tối ưu. Những bài toán này thường có nhiều nghiệm đúng và mỗi nghiệm có một giá trị đánh giá. Do đó, cần tính toán nhiều lần và sử dụng lời giải của các bài toán con để tìm ra đáp án cho bài toán ban đầu.
Khi muốn giải quyết một bài toán một cách nhanh nhất thì thuật toán này là một cách giải giúp tối ưu thời gian. Quy hoạch động này bao gồm bốn bước như sau:
 Bước 1: Đặc trưng hóa cấu trúc của lời giải tối ưu.
 Bước 2: Định nghĩa giá trị của lời giải tối ưu một cách đệ quy.
 Bước 3: Tính trị của lời giải tối ưu theo kiểu từ dưới lên hoặc trên xuống.
 Bước 4: Xây dựng lời giải tối ưu từ những thông tin đã được tính toán trên.
Thay vì gọi đệ quy, thuật toán sẽ tính toán lời giải của các bài toán con trước tiên và lưu vào mảng bộ nhớ. Tiếp theo, sẽ dùng lời giải của bài toán con trong mảng đã tính trước đó để giải bài toán lớn theo công thức truy hồi. Công thức truy hồi là công thức thể hiện quan hệ giữa các bước trong một bài toán và kết quả của bước sau nhờ vào kết quả của các bước trước đó.
Thuật toán này với ưu điểm chính là tiết kiệm thời gian tính toán thì cũng có một vài nhược điểm. Đầu tiên, việc tìm ra công thức truy hồi hay phân rã bài toán lớn yêu cầu phải suy nghĩ và phân tích thật kỹ càng. Điều này sẽ giúp bạn tránh được sự sai sót cũng như rủi ro phải tính lại từ đầu. Thứ hai là khó xử lý dữ liệu khi bảng lưu trữ yêu cầu mảng hai hoặc ba chiều. Cuối cùng, không phải bài toán tối ưu nào cũng có thể áp dụng giải bằng quy hoạch động.
Bên cạnh đó, một bài toán tối ưu cũng có một số đặc điểm cần lưu ý dưới đây:
 Cần phân tách bài toán lớn thành nhiều bài toán con và kết hợp lời giải của các bài toán con để giải của bài toán lớn.
 Bản chất của thuật toán là giải tất cả các bài toán con. Quy hoạch động không
thể tiến hành được nếu không gian lưu trữ không đủ để phối hợp.
Điểm quyết định trong khi giải thuật toán này là cần tìm ra được công thức truy hồi cho từng trường hợp bài toán. Đối với một số bài toán thì dễ dàng có nhiều cách giải và giải bằng quy hoạch động nhưng chưa hẳn là giải pháp tối ưu. Mỗi bài toán
3

là mỗi kiểu khó khác nhau, không có một công thức chung cho tất cả các bài toán đó được.
Vậy khi nào chúng ta nên áp dụng đến thuật toán này? Thường bài toán có hai tính chất này là bạn có thể sử dụng thuật toán quy hoạch động vào. Đó chính là bài toán con gối nhau và cấu trúc con tối ưu.
Sử dụng thuật toán quy hoạch động khi nào?
Bài toán con gối nhau
Bài toán con gối nhau là bài toán nhỏ hơn và được chia từ bài toán ban đầu ra. Việc sử dụng lặp lại nhiều lần này, thuật toán sẽ lưu kết quả mà không cần tính lại, giúp bạn tiết kiệm rất nhiều thời gian. Việc giải một bài toán con nhiều lần thì không thể tránh khỏi việc trùng lời giải của các bài toán con.
Khi các bài toán con không gối nhau thì việc áp dụng thuật toán này cũng bằng không. Quy hoạch động không thể tối ưu được với thuật toán tìm kiếm nhị phân. Lý do vì khi chia bài toán lớn thành các bài toán nhỏ và mỗi bài toán chỉ cần giải một lần mà không được gọi lại.
Bài toán tính Fibonacci là ví dụ rất điển hình của bài toán con gối nhau. Bằng cách cộng fibonacci thứ n-1 và n-2 sẽ tính được số fibonacci thứ n. Bài toán con của số fibonacci thứ n chính là bài toán tính fibonacci n-1 và n-2. Công thức tính toán số Fibonacci được tính như sau:
def fib(n): if n <= 1:
return n
return fib(n -1) + fib(n – 2)
Quy hoạch động chính là một trong số những giải pháp cực kỳ hiệu quả có thể tối ưu hóa quá trình tính toán này. Trước khi tiến hành tính những bài lớn thì mỗi
bài toán con sẽ được lưu lại. Nhờ đó, mà việc tính toán giảm đi đáng kể, mỗi bài toán con chỉ cần tính đúng một lần. Nhờ đó mà thuật toán này được sử dụng rất nhiều trong các cuộc thi lập trình giúp các thí sinh giảm đáng kể thời gian tính toán.
Cấu trúc con tối ưu
Bài toán có cấu trúc con tối ưu là gì? Cấu trúc con tối ưu chính là tập hợp các lời giải tối ưu từ các bài toán con để tìm ra lời giải bài toán lớn. Bài toán có cấu trúc
4

con tối ưu có thể dễ dàng tính toán hoặc có khi không cần phải tính toán nữa. Các bài toán con tối ưu có thể sử dụng công thức truy hồi đưa vào thuật toán để tìm ra đáp án cuối cùng cho bài toán.
Cấu trúc con tối ưu với quy trình ba bước mà bạn nên nắm rõ để có thể giải một bài toán nhanh chóng nhất:
 Bước 1: Từ bài toán lớn chia thành các bài toán con nhỏ hơn.
 Bước 2: Sử dụng phương pháp đệ quy để giải các bài toán con tối ưu.
 Bước 3: Lấy kết quả tối ưu đã tính để có thể dễ dàng tìm lời giải tối ưu cho bài toán lớn trên.
Bài toán có cấu trúc con tối ưu rất quan trọng, bởi nó cho phép bạn dựa vào các bài toán con đã giải để có lời giải cho bài toán lớn. Chúng ta sẽ không thể nào áp
dụng thuật toán quy hoạch động nếu bài toán không có tính chất này.
Các phương pháp trong quy hoạch động
Trong quy hoạch động, chúng ta có thể sử dụng một trong hai cách để lưu trữ dễ dàng các giá trị đã tính như sau:
Phương pháp từ trên xuống ( phương pháp ghi nhớ )
Phương pháp từ trên xuống trong quy hoạch động
Với phương pháp này, sẽ bắt đầu giải bài toán từ trên xuống. Bằng cách lặp đệ quy để giải bài toán lớn hơn, từ đó tìm ra lời giải cho các bài toán con. Các bài toán con này được giải và lưu kết quả vào bộ nhớ. Việc ghi nhớ câu trả lời này sẽ giúp giải quyết vấn đề con mà không tốn quá nhiều thời gian.
Phương pháp từ dưới lên ( phương pháp lập bảng )
Phương pháp từ dưới lên trong thuật toán quy hoạch động
5

Phương pháp lập bảng này trái ngược hoàn toàn với phương pháp ghi nhớ. Cách tiếp cận này sẽ không dùng đệ quy và giải quyết bài toán con liên quan từ dưới lên. Bạn trực tiếp giải tất cả bài toán nhỏ và điền vào bảng N chiều. Sau đó, dùng kết quả trong bảng để tìm ra dần lời giải cho bài toán ban đầu. Cách tiếp cận này hiệu quả và được sử dụng nhiều hơn phương pháp ghi nhớ bởi nó sẽ không làm tốn bộ nhớ và số lần gọi hàm.
1.2. Độ phức tạp của thuật toán
Giả sử ta có hai thuật toán P1 và P2 với thời gian thực hiện tương ứng là T1(n) = 100n2 (với tỷ suất tăng là n2) và T2(n) = 5n3 (với tỷ suất tăng là n3). Khi n > 20 thì T1 <T2.SởdĩnhưvậylàdotỷsuấttăngcủaT1 nhỏhơntỷsuấttăngcủaT2.Như vậy một cách hợp lý là ta xét tỷ suất tăng của hàm thời gian thực hiện chương trình thay vì xét chính bản thân thời gian thực hiện.Cho một hàm T(n), T(n) gọi là có độ phức tạp f(n) nếu tồn tại các hằng C, N0 sao cho T(n) ≤ Cf(n) với mọi n ≥ N0 (tức là T(n) có tỷ suất tăng là f(n)) và kí hiệu T(n) là O(f(n)) (đọc là “ô của f(n)”).
Các hàm thể hiện độ phức tạp có các dạng thường gặp sau: log2n, n, nlog2n, n2, n3, 2n, n!, nn. Trong cách viết, ta thường dùng logn thay thế cho log2n cho gọn.
Khi ta nói đến độ phức tạp của thuật toán là ta nói đến hiệu quả thời gian thực hiện chương trình nên có thể xem việc xác định thời gian thực hiện chương trình chính là xác định độ phức tạp của thuật toán.
1.3. Phương pháp lựa chọn và cài đặt chương trình tối ưu khi giải một số dạng bài tập về dãy con
Đối với mỗi dạng bài tập về dãy con, chúng tôi đưa ra một bài toán cơ bản, từ mỗi bài toán cơ bản chúng tôi trình bày từ 2 hoặc 3 cách giải (cả cách làm của học sinh và cách làm chúng tôi định hướng cho học sinh làm). Với phương châm“ mưa dầm thấm lâu”, chúng tôi không hướng dẫn học sinh cách làm tối ưu ngay mà khi phát vấn một dạng bài tập mới mà yêu cầu học sinh làm theo các trình tự sau:
Bước 1: Xác định bài toán
Bước 2: Suy nghĩ tìm ra thuật toán, viết chương trình, tính độ phức tạp (Có thể nhiều
cách).
Bước 3: Trao đổi cách làm của mình với bạn để tìm cái hay cái dở.
Bước 4: Sử dụng phần mềm Themis-chấm bài tự động để chấm cách làm của mình (với 10 bộ test hoặc nhiều hơn mà giáo viên đã xây dựng sẵn, mỗi bộ test cấu hình là 1 điểm, thời gian chạy không quá 1 giây).
Bước 5: Nhận xét sự tối ưu của thuật toán.
Bước 6: Giáo viên định hướng cách làm tối ưu hơn (nếu có).
Bước 7: Sử dụng phần mềm Themis để chấm tất cả các cách đã viết chương trình.
Bước 8: Dựa vào kết quả, lựa chọn chương trình có độ phức tạp nhỏ nhất, thời gian thực hiện mỗi test nhỏ nhất và chương trình ngắn gọn dễ hiểu nhất.
Bước 9: Lập trình giải các bài tập tương tương với cách đã lựa chọn.
6

2. Cơ sở thực tiễn
2.1. Thực trạng học tập của học sinh
a) Khảo sát thực trạng
Chúng tôi đã tiến hành khảo sát tìm hiểu thực trạng học tập của học sinh. Cụ thể, chúng tôi đã phát phiếu điều tra cho HS ở nhiều lớp khác nhau để các em phát biểu những cảm nhận và nêu ý kiến, nguyện vọng của mình về việc học môn Tin học. Nội dung khảo sát như sau :
Hãy trả lời câu hỏi dưới đây bằng cách đánh dấu x vào ô trống trong bảng có câu trả lời phù hợp với em.
Nội dung
Câu 1: Em có yêu thích môn Tin học không?
Câu 2: Em có yêu thích môn Tin học lập trình không? Câu 3: Em có biết về quy hoạch động không?
Có Không
Câu 3
Có Không
1/45 44/45 2.2% 97.8%
3/50 47/50 6% 94%
4/38 34/38 10.5% 89.5%
10/40 30/40 25% 75%
5/42 37/42 11.9% 88.1%
4/32 28/32 12.5% 87.5%
–
Kết quả thu được như sau:
TT
1 3 6 7 8 9
Lớp
10D1
10A
11A
11T
12T
12A1
Nội dung khảo sát Câu 2
Câu 1
Không Có
Có
45/45 100%
40/50 80%
35/38 92.1%
36/40 90%
34/42 81%
30/32 93.7%
0/45 15/45 0% 33.3%
10/50 30/50 20% 60%
3/38 25/38 7.9% 65.8%
4/40 23/40 10% 57.5%
8/42 22/42 19% 52.4%
2/32 15/32 6.3% 46.9%
Không
30/45 66.7%
20/50 40%
13/38 34.2%
17/40 42.5%
20/42 47.6%
17/32 53.1%
b) Phân tích, đánh giá thực trạng
Từ kết quả khảo sát đó, chúng tôi nhận thấy: Đa số học sinh đều yêu thích môn Tin học nhất là trong lĩnh vực ứng dụng như tìm hiểu Internet tham gia các trò chơi trí tuệ, hay tự mình làm ra các phần mềm nhỏ như các trò chơi ô chữ trong các giờ học, hay tạo ra những video hình ảnh có ích trong các môn học. Tuy nhiên trong các nội dung ở trường THPT thì phần lập trình là khó khăn nhất dẫn đến học sinh không có hứng thú, bài toán có sử dụng quy hoạch động là một bài toán khó rất ít các em HS biết và sử dụng.