Phương pháp quy hoạch động và vận dụng kết hợp giải các bài toán chuyên tin bậc THPT

Abstract

Quy hoạch động là một chuyên đề rất hay và mạnh của tin học, đã vậy thực hiện quy hoạch động trên dãy bit lại còn cho kết quả khả quan hơn nữa. Như chúng ta đã biết, phép xử lí bit có thời gian thực hiện rất nhỏ, nhỏ hơn phép số học toán thông thường. Vì vậy, trong luận văn này, phạm vi dữ liệu mà tôi muốn đề cập đến là bit và quy hoạch động trên dãy bit. Bên cạnh đó luận văn cũng trình bày một số cách quy hoạch trên dãy đã được sắp xếp cùng với một số bài toán điển hình dùng để minh họa cho quy hoạch động. Các bài toán được phân tích, thiết kế và cài đặt theo phương pháp quy hoạch động và phương pháp khác nhằm để so sánh và thấy được ưu điểm của phương pháp quy hoạch động (chủ yếu là về mặt thời gian chạy của thuật toán). Luận văn cũng đã cho thấy có sự cùng dạng của một lớp các bài toán có thể chuyển về xử lý bằng cách mô tả các trạng thái của bài toán bằng dãy bit và từ đó thực hiện quy hoạch động trên dãy bit đó để đạt được kết quả tối ưu.