KỸ THUẬT THIẾT KẾ THUẬT TOÁN
➤ Gửi thông báo lỗi ⚠️ Báo cáo tài liệu vi phạmNội dung chi tiết: KỸ THUẬT THIẾT KẾ THUẬT TOÁN
KỸ THUẬT THIẾT KẾ THUẬT TOÁN
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 tha KỸ THUẬT THIẾT KẾ THUẬT TOÁN at is rhe most adaptable to change"Charles DarwinChương này giới thiệu một sổ kỳ thuật quan trong 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 đé tn (divide and conquer). Quy hoạch động (dynamic programmin KỸ THUẬT THIẾT KẾ THUẬT TOÁN g) 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ácKỸ THUẬT THIẾT KẾ THUẬT TOÁN
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á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 tha KỸ THUẬT THIẾT KẾ THUẬT TOÁN ào. Chúng ta chi có thé khao 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 khỉ 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 đố) tượng cho tnrớc có bao nhiêu KỸ THUẬT THIẾT KẾ THUẬT TOÁN đố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 điền cáKỸ THUẬT THIẾT KẾ THUẬT TOÁN
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à) 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 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 tha KỸ THUẬT THIẾT KẾ THUẬT TOÁN lại một cấu hình•Không đưực bò sót một cấu hìnhTrước khi nó) 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ản1.1.1.Thứ tự từ điểnNhá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 KỸ THUẬT THIẾT KẾ THUẬT TOÁN tính chất:Với V a, b, c 6 s•Tính phó biến (Universality): Hoặc là (1 < b , hoặc b < o;•Tính phàn xạ (Reflexivity): a < a•Tính phàn đối xứng (AntisymmeKỸ THUẬT THIẾT KẾ THUẬT TOÁN
try): Nếu a < b và b < a thi bất buộc a = b•Tính bắc cầu (Transitivity): Nếu có 0 < b và b < c thì (i < c.Các quan hệ >, >, < có thế tự suy ra từ quanChươ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 tha KỸ THUẬT THIẾT KẾ THUẬT TOÁN an hệ thứ tự toàn phàn Khi đỏ ÍĨỊ n < bỵ n nếu như :•Hoặc hai dày giống nhau: «i = bị, Ví: 1 < í < n•Hoặc tồn tại một số nguyên dương k < n đế ak < bk và Uị = bị,Vi: 1 < ị < kThứ tự đó gọi là thứ tự từ điển (lexicographic order) trên các dáy độ dài n.Khi hai dày a và b có số phàn từ khác nhau, người KỸ THUẬT THIẾT KẾ THUẬT TOÁN ta cùng xác định được thứ tự từ điển. Bằng cách thêm vào cuối dãy a hoặc dãy b những phần từ đặc biệt gọi là e để đô dài của a và b bằng nhau, và coiKỸ THUẬT THIẾT KẾ THUẬT TOÁN
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ụ:(L2.3.4) < (5,6)(a.b.c) < (aChươ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 tha KỸ THUẬT THIẾT KẾ THUẬT TOÁN u hạn gòm n phàn lừ vã k là một số lự nhiên. Gọi X là lập các số nguyên dương từ 1 tới k; X - {1,2,..., 7c}□ Chinh hợp lặpMỘI ánh xạ j'.x > s cho lircrng ứng mồi phần lử i F X mội và chỉ rnộl phàn lừ /ơ) F s, dược gọi là một chinh hợp lặp chập k của S’ KỸ THUẬT THIẾT KẾ THUẬT TOÁN 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 thaGọi ngay
Chat zalo
Facebook