SKKN phương pháp quy hoạch động và ứng dụng vào giải một số bài toán bồi dưỡng học sinh giỏi, thi chuyên bằng ngôn ngữ lập trình Pascal và C++

Phần I.  Đặt vấn đề 

1.  Lí do chọn đề tài  

Tự học tập, nghiên cứu là một nhiệm vụ quan trọng của mỗi giáo viên để nâng cao trình độ chuyên môn, phục vụ cho công tác giảng dạy và đặc biệt là trong bồi dưỡng đội tuyển học sinh giỏi. 

Trong những năm gần đây, trong các đề thi học sinh giỏi tỉnh, quốc gia cũng như các bài tập trên các trang giải bài trực tuyến vn.spoj.com, vnoi.info, … có nhiều bài tập nếu chúng ta sử dụng những kiến thức cơ bản như đệ quy, duyệt, chia để trị, … có thể giải quyết được nhưng gặp nhiều khó khăn về mặt tốc độ cũng như giới hạn dữ liệu. Trong khi đó nếu chúng ta sử dụng phương pháp quy hoạch động hoặc các phương pháp trên có kết hợp với quy hoạch động thì cho một hiệu quả cao.  

Quy hoạch động là một phương pháp rất hiệu quả để giải lớp bài toán trong Tin học. Đặc biệt là những bài toán tối ưu, khi sử dụng phương pháp quy hoạch động chương trình chạy nhanh, cách viết chương trình rõ ràng. Nhưng không phải bài toán nào cũng có thể áp dụng được bằng phương pháp quy hoạch động. Vậy thường những bài toán như thế nào thì áp dụng được phương pháp quy hoạch động và cách giải một bài toán quy hoạch động như thế nào là một vấn đề?   

Mặt khác hiện nay khi bồi dưỡng thi học sinh giỏi giáo viên có thể lựa chọn 1 trong 3 ngôn ngữ lập trình là Pascal, C++ hoặc là Python. Pascal là ngôn ngữ lập trình đã cũ, câu lệnh dài và không được hỗ trợ nhiều. Python là ngôn ngữ lập trình mới nhất, câu lệnh ngắn gọn, hỗ trợ nhiều trong khi viết chương trình. Tuy nhiên một số bài toán khi chạy chương trình còn hạn chế về mặt thời gian. Chính vì vậy hiện nay thi học sinh giỏi thì ngôn ngữ lập trình C++ được lựa chọn nhiều nhất. Cho nên trong đề tài này tôi sử dụng ngôn ngữ lập trình C++ để viết chương trình cũng như minh hoạ thuật toán. Ngoài ra tôi còn minh hoạ chương trình bằng ngôn ngữ lập trình Pascal (Link code minh hoạ bằng ngôn ngữ lập trình pascal để ở phần phụ lục của đề tài) cho một số bạn đọc dễ hiểu và nắm bắt tốt hơn khi chưa tiếp cận nhiều với ngôn ngữ lập trình C++.  

Vì những lý do trên, với những kinh nghiệm và tìm hiểu của bản thân, tôi đưa ra đề tài “phương pháp quy hoạch động và ứng dụng vào giải một số bài toán bồi dưỡng  học sinh giỏi, thi chuyên bằng ngôn ngữ lập trình Pascal và C++” . 

2.  Mục đích nghiên cứu, đóng góp mới của đề tài 

• Đề tài nêu ra các định hướng giúp học sinh có thể tiếp cận phương pháp Quy hoạch động để giải một số bài toán tối ưu phù hợp với dữ liệu bài toán.  
• Giúp người đọc tiếp cận ngôn ngữ lập trình C++ tốt hơn trong khi lập trình.  – Từ đó bồi dưỡng học sinh năng lực giải quyết vấn đề trong giải toán Tin học,  đồng thời rèn luyện và nâng cao kĩ năng lập trình cho các em. Đặc biệt là học sinh  tham gia dự thi học sinh giỏi cấp tỉnh THCS, THPT, thi Olimpic Tin học trẻ hoặc thi vào các trường chuyên.  

3. Đối tượng nghiên cứu  

• Đối tượng nghiên cứu là học sinh giỏi tin, giáo viên giảng dạy, bồi dưỡng học sinh giỏi môn Tin trong trường THCS và THPT.  
• Phương pháp quy hoạch động và các bài toán tối ưu.  

4.  Phương pháp nghiên cứu  

Để hoàn thành nhiệm vụ, tôi đã nghiên cứu rất nhiều sách và các chuyên đề Tin học dành cho học sinh Chuyên tin, những vấn đề cơ bản nhất về cấu trúc dữ liệu, thuật toán và cài đặt chương trình.  

Cùng nhau trao đổi, thảo luận, rút kinh nghiệm cùng các đồng nghiệp trong và ngoài trường nhằm nâng cao chất lượng cho đề tài. 

Lựa chọn một số bài toán giải bằng phương pháp Quy hoạch động trong các đề thi và chương trình tin học chuyên THPT.  

5.  Phạm vi nghiên cứu 

Lí thuyết về Quy hoạch động và một số bài tập ứng dụng kĩ thuật xử lí Quy hoạch động hiệu quả trong các đề thi học sinh giỏi, các bài tập trên các trang trực tuyến như:  vn.spoj.com, vnoi.info, laptrinh.ntu.edu.vn, chuyentin.pro… 

6. Cấu trúc của đề tài  

Ngoài phần mở đầu, kết luận và kiến nghị, phần nội dung đề tài gồm có 2 nội dung: 

1. Cơ sở lý luận  

Giới thiệu về phương pháp Quy hoạch động, các bước tiếp cận với phương pháp Quy hoạch động, cách nhận diện xem bài toán tối ưu nào có thể giải bằng phương pháp Quy hoạch động và nếu giải thì cách giải như thế nào? Trình bày các dạng, phân tích và cài đặt chương trình cụ thể để bạn đọc dễ hiểu nhất. Qua đó có thể vận dụng để giải quyết  các bài toán về sau.  

2. Cơ sở thực tiễn  

Nêu ra thực trạng vấn đề, những hạn chế, khó khăn của học sinh cũng như giáo viên trong việc giải quyết các bài toán lớn, các bài toán ôn thi học sinh giỏi hiện nay. Qua đó giải quyết vấn đề và đưa ra các bài toán điển hình để so sánh sử dụng phương pháp Quy hoạch động và một số phương pháp khác. Sử dụng phương pháp Quy hoạch động có  thể vận dụng lập trình giải các bài toán trong các đề thi hay khi ôn luyện. Trang bị kiến thức cho học sinh và giáo viên để giải quyết tốt khi gặp các bài toán có liên  quan đến sử dụng phương pháp Quy hoạch động một cách hiệu quả nhất.  

Phần II. Nội dung: 

1. Cơ sở lý luận  

Giới thiệu về phương pháp Quy hoạch động, các bước tiếp cận với phương pháp Quy hoạch động, cách nhận diện xem bài toán tối ưu nào có thể giải bằng phương pháp quy hoạch động và nếu giải thì cách giải như thế nào? Trình bày các dạng, phân tích và cài đặt chương trình cụ thể để bạn đọc dễ hiểu nhất. Qua đó có thể vận dụng để giải quyết  các bài toán về sau.  

1. 1. Giới thiệu  

Phương pháp quy hoạch động do nhà toán học người Mỹ Richard Bellman (1920 – 1984) phát minh năm 1953.  

Phương pháp quy hoạch động (dynamic programming) là một kỹ thuật được áp dụng để giải nhiều lớp bài toán, đặc biệt là bài toán tối ưu.  

Vậy bài toán tối ưu là gì?. Đó chính là bài toán có nhiều nghiệm chấp nhận được mỗi nghiệm có một giá trị đánh giá. Mục tiêu đặt ra là tìm nghiệm tối ưu, đó là nghiệm có giá trị đánh giá nhỏ nhất hoặc lớn nhất (tối ưu).  

Khi tiến hành giải một bài toán phức tạp (bài toán lớn) ban đầu người ta thường đi chia bài toán đó thành các bài toán con độc lập đơn giản để giải, khi tiến hành giải xong các bài toán con ta tổng hợp lời của các bài toán con và đó chính là bài toán lớn cần giải. Đây chính là phương pháp chia để trị được sử dụng rất thông dụng trong quá trình lập trình giải các bài toán trong Tin học. Nhưng đối với những bài toán phức tạp nếu chúng ta sử dụng phương pháp này thì sẽ mất test ở những dữ liệu lớn. Vì chưa tối ưu về mặt thời gian. Chính vì vậy phương pháp Quy hoạch động ra đời nhằm cải tiến về vấn đề này. 

1. 2. Phương pháp quy hoạch động  

1.2.1.  Khái niệm  

Phương pháp quy hoạch động là một kỹ thuật nhằm đơn giản hóa việc tính toán các công thức truy hồi bằng cách lưu toàn bộ hay một phần kết quả tính toán của mỗi bước trước đó với mục đích sử dụng lạ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 các bước sau thường dựa vào kết quả của các bước trước đó. Kết quả của bước cuối cùng chính là kết quả bài toán cần tìm).