Báo Cáo Quy hoạch động Bài toán Xâu con chung lớn nhất

Trước khi viết một chương trình cho máy tính, cho dù đơn giản nhất, bất cứ ai, dù ở trình độ nào, cũng đều phải tư duy ít nhiều về thuật toán. Trong tổng thể kiến thức về tin học, các thuật toán cùng các cấu trúc dữ liệu được xem là những tri thức quan trọng hàng đầu và không thể thiếu cho cho bất kỳ người lập trình ứng dụng hay hệ thống nào muốn đạt được mục đích với hiệu quả cao nhất. Chính vì vậy tư duy về thuật toán; cách phân tích, đánh giá và thiết kế thuật toán là điều kiện cần thiết, cốt lõi, tiên quyết cho những nhà lập trình.

Tuy nhiên, thuật toán là một vấn đề hết sức đa dạng, phong phú và phức tạp. Cùng một bài toán đặt ra có thể có nhiều cách giải quyết; và do đó cũng có nhiều thuật toán và hướng tiếp cận tốt xấu khác nhau. Có những hướng tiếp cận đúng đắn về mặt lý thuyết nhưng không hiệu quả về mặt thực tiễn; hay có thể không giải quyết được vấn đề. Ứng với một lớp bài toán nhất định sẽ có một lớp thuật toán thích hợp với nó. Vấn đề quy hoạch động là một trong những vấn đề hay dùng trong việc giải quyết lớp các bài toán tối ưu và một số các loại bài toán khác mang tính hiệu quả cao. Trong bản thuyết trình này sẽ đề cập đến việc giải bài toán tìm xâu con chung dài nhất sử dụng phương pháp quy hoạch động.

Phần I: Tóm tắt nội dung:


A. Vấn đề quy hoạch động:


I. Một số vấn đề khái niệm cơ bản;


Phần này trình bày một số khái niệm về thuật toán, phân tích thuật toán, và việc thiết kế thuật toán.

II. Quy hoạch động;


Trong phần này đề cập đến phương pháp quy hoạch động để giải quyết lớp các bài toán tối ưu. Đặc điểm, tính chất, cách nhận biết và trình tự để giải một bài toán dùng phương pháp quy hoạch động.

B. Bài toán xâu con chung dài nhất:


Ở đây sẽ trình bày phương pháp quy hoạch động để giải bài toán tìm xâu con chung dài nhất của hai xâu cho ban đầu bao gồm ý tưởng và cài đặt thuật toán chi tiết bằng giả mã.

Phần II: Nội dung trình bày:


A. Vấn đề quy hoạch động.


I. Một số khái niệm cơ bản.


1. Thuật toán:


Hiểu một cách nôm na thuật toán là một cách thức để tính toán, thực hiện được định nghĩa theo một số bước xác định mà qua đó ta có thể sử dụng một giá trị hoặc một tập hợp giá trị nào đó làm đầu vào; kết quả sẽ cho ra một giá trị hoặc một tập giá trị nào đó. Như vậy có thể coi một thuật toán là một trình tự các bước tính toán, thực hiện biến đổi dữ liệu đầu vào để cho một kết quả là dữ liệu đầu ra.

Ta cũng có thể xem một thuật toán như một công cụ để giải quyết một bài toán cụ thể. Việc định nghĩa bài toán sẽ xác định mối quan hệ tổng quát của dữ liệu đầu vào và dữ liệu đầu ra.

Có thể định nghĩa thuật toán theo nhiều cách khác nhau, ở đây ta có thể hiểu khái niệm thuật toán theo một cách thông thường nhất là một quy tắc để từ những dữ liệu ban đầu đã cho, tìm được lời giải sau một khoảng thời gian hữu hạn.

Tóm lại ta có thể coi: Thuật toán là một bảng liệt kê các chỉ dẫn, quy tắc mà theo đó thực hiện từng bước có thể giải quyết bài toán đặt ra theo thời gian hữu hạn.

Như vậy đối với một thuật toán phải thoả mãn tính hữu hạn về mặt thực tế, tính đúng đắn cũng như tính xác định. Ngoài ra một thuật toán luôn luôn phải có dữ liệu đầu vào, dữ liệu đầu ra và mang tính phổ quát cho một lớp bài toán nhất định.

1.1. Tính hữu hạn.

Thuật toán cần phải kết thúc sau một số bước hữu hạn. Khi thuật toán dừng ta phải thu được kết quả ứng với bài toán đặt ra.

1.2. Tính xác định.

Ở mỗi bước, thuật toán phải đảm bảo tính xác định, nghĩa là chỉ rõ bước thực hiện, công việc cần làm.

1.3. Tính đúng đắn.

Khi thuật toán kết thúc, ứng với một dữ liệu đầu vào ta phải thu được kết quả đúng đắn.

*) Ngoài những yếu tố kể trên, ta còn phải xét đến tính hiệu quả của thuật toán. Có rất nhiều thuật toán về mặt lý thuyết là kết thúc sau hữu hạn bước, tuy nhiên thời gian “hữu hạn” đó vượt qua khả năng làm việc thực tế. Do vậy những thuật toán này chỉ có ý nghĩa về mặt lý thuyết chứ không có ý nghĩa về mặt thực tế. Khi xét đến thuật toán ta cũng cần phải chú ý đến độ phức tạp của thuật toán, độ phức tạp của thuật toán có thể đo bằng không gian, tức là dung lược bộ nhớ của máy tính cần thiết để thực hiện thuật toán; và bằng thời gian, tức là thời gian máy tính làm việc.