KỸ THUẬT THIẾT KẾ THUẬT TOÁN - Le Minh Hoang

Có một số bài toán trên thực tế yêu cầu chỉ rõ: trong một tập các đối tượng cho trước có bao nhiêu đối tượng thoả mãn những điều kiện nhất định và đó là những đối tượng nào. Bài toán này gọi là bài toán liệt kê hay bài toán duyệt. Nếu ta biểu diễn các đối tượng cần tìm dưới dạng một cấu hình các biến số thì để giải bài toán liệt kê, cần phải xác định được một thuật toán để có thể theo đó lần lượt xây dựng được tất cả các cấu hình đang quan...
Nội dung trích xuất từ tài liệu:
KỸ THUẬT THIẾT KẾ THUẬT TOÁN - Le Minh Hoang Chương I. KỸ THUẬT THIẾT KẾ THUẬT TOÁN “It is not the strongest of the species that survives, nor the most intelligent that survives. It is the one that is the most adaptable to change” Charles Darwin Chương này giới thiệu một số kỹ thuật quan trọng trong việc tiếp cận bài toán và tìm thuật toán. Các lớp thuật toán sẽ được thảo luận trong chương này là: Vét cạn (exhaustive search), Chia để trị (divide and conquer), Quy hoạch động (dynamic programming) và Tham lam (greedy). Các bài toán trên thực thế có muôn hình muôn vẻ, không thể đưa ra một cách thức chung để tìm giải thuật cho mọi bài toán. Các phương pháp này cũng chỉ là những “chiến lược” kinh điển. Khác với những thuật toán cụ thể mà chúng ta đã biết như QuickSort, tìm kiếm nhị phân,…, các vấn đề trong chương này không thể học theo kiểu “thuộc và cài đặt”, cũng như không thể tìm thấy các thuật toán này trong bất cứ thư viện lập trình nào. Chúng ta chỉ có thể khảo sát một vài bài toán cụ thể và học cách nghĩ, cách tiếp cận vấn đề, cách thiết kế giải thuật. Từ đó rèn luyện kỹ năng linh hoạt khi giải các bài toán thực tế. Bài 1. Liệt kê Có một số bài toán trên thực tế yêu cầu chỉ rõ: trong một tập các đối tượng cho trước có bao nhiêu đối tượng thoả mãn những điều kiện nhất định và đó là những đối tượng nào. Bài toán này gọi là bài toán liệt kê hay bài toán duyệt. Nếu ta biểu diễn các đối tượng cần tìm dưới dạng một cấu hình các biến số thì để giải bài toán liệt kê, cần phải xác định được một thuật toán để có thể theo đó lần lượt xây dựng được tất cả các cấu hình đang quan tâm. Có nhiều phương pháp liệt kê, nhưng chúng cần phải đáp ứng được hai yêu cầu dưới đây:  Không được lặp lại một cấu hình  Không được bỏ sót một cấu hình Trước khi nói về các thuật toán liệt kê, chúng ta giới thiệu một số khái niệm cơ bản: 1.1. Vài khái niệm cơ bản 1.1.1. Thứ tự từ điển Nhắc lại rằng quan hệ thứ tự toàn phần “nhỏ hơn hoặc bằng” ký hiệu “” trên một tập hợp , là quan hệ hai ngôi thoả mãn bốn tính chất: Với  Tính phổ biến (Universality): Hoặc là , hoặc ;  Tính phản xạ (Reflexivity):  Tính phản đối xứng (Antisymmetry) : Nếu và thì bắt buộc  Tính bắc cầu (Transitivity): Nếu có và thì . Các quan hệ có thể tự suy ra từ quan hệ này. Trên các dãy hữu hạn, người ta cũng xác định một quan hệ thứ tự: Xét và là hai dãy độ dài , trên các phần tử của và đã có quan hệ thứ tự toàn phần “”. Khi đó nếu như :  Hoặc hai dãy giống nhau:  Hoặc tồn tại một số nguyên dương để và Thứ tự đó gọi là thứ tự từ điển (lexicographic order) trên các dãy độ dài . Khi hai dãy và có số phần tử khác nhau, người ta cũng xác định được thứ tự từ điển. Bằng cách thêm vào cuối dãy hoặc dãy những phần tử đặc biệt gọi là để độ dài của và bằng nhau, và coi những phần tử này nhỏ hơn tất cả các phần tử khác, ta lại đưa về xác định thứ tự từ điển của hai dãy cùng độ dài. Ví dụ: ( ) ( ) ( ) ( ) calculato computer Thứ tự từ điển cũng là một quan hệ thứ tự toàn phần trên các dãy. 1.1.2. Chỉnh hợp, tổ hợp, hoán vị. Cho là một tập hữu hạn gồm phần tử và là một số tự nhiên. Gọi là tập các số nguyên dương từ 1 tới :  Chỉnh hợp lặp Một ánh xạ cho tương ứng mỗi phần tử một và chỉ một phần tử ( ) , được gọi là một chỉnh hợp lặp chập của Do là tập hữu hạn ( phần tử) nên ánh xạ có thể xác định qua bảng các giá trị ( ( ) ( ) ( )), vì vậy ta có thể đồng nhất với dãy giá trị ( ( ) ( ) ( )) và coi dãy giá trị này cũng là một chỉnh hợp lặp chập của . Ví dụ . Một ánh xạ cho bởi: 1 2 3 () tương ứng với tập ảnh ( ) là một chỉnh hợp lặp của Số chỉnh hợp lặp chập của tập phần tử là  Chỉnh hợp không lặp Mỗi đơn ánh được gọi là một chỉnh hợp không lặp chập của . Nói cách khác, một chỉnh hợp không lặp là một chỉnh hợp lặp có các phần tử khác nhau đôi một. Ví dụ một chỉnh hợp không lặp chập 3 ( ) của tập 1 2 3 () Số chỉnh hợp không lặp chập của tập phần tử là ( )  Hoán vị Khi mỗi song ánh được gọi là một hoán vị của . Nói cách khác một hoán vị của là một chỉnh hợp không lặp chập của . Ví dụ: ( ) là một hoán vị của 1 2 3 4 5 6 () Số hoán vị của tập phần tử là  Tổ hợp Mỗi tập con gồm phần tử của được gọi là một tổ hợp chập của . Lấy một tổ hợp chập của , xét tất cả hoán vị của nó, mỗi hoán vị sẽ là một chỉnh hợp không lặp chập của . Điều đó tức là khi liệt kê tất cả các chỉnh hợp không lặp chập thì mỗi tổ hợp chập sẽ được tính lần. Như vậy nếu xét về mặt số lượng: Số tổ hợp chập của tập phần tử là ( ) ( ) Ta có công thức khai triển nhị thức: ( ) ∑( ) Vì vậy ...