tailieunhanh - 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. | 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 T rướ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 . Vài khái niệm cơ bản . 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 s là quan hệ hai ngôi thoả mãn bốn tính chất Với V a b c e s Tính phổ biến Universality Hoặc là a b hoặc b