Phương pháp sinh toàn bộ một số đối tượng tổ hợp

- LỜI CAM ĐOANTôi xin cam đoan: Luận văn thạc sĩ Công nghệ thông tin "Phương pháp sinhtoàn bộ một số đối tượng tổ hợp" là công trình nghiên cứu thực sự của cá nhântôi, không trùng với bất kỳ luận văn nào khác.
- Một số đối tượng tổ hợp quan trọng.
- Từ Dyck.
- Bài toán liệt kê và một số phương pháp sinh cơ bản.
- Bài toán liệt kê.
- Một số phương pháp sinh cơ bản.
- Phương pháp ECO và luật kế tiếp.
- Phương pháp ECO đơn tầng.
- Phương pháp ECO đa tầng.
- Họ các từ Dyck mở rộng và một số từ liên quan 262.1.
- Các từ Grand Dyck.
- Các từ Grand Motzkin.
- Các từ Grand Schr¨oder.
- Các từ mở rộng khác của từ Dyck.
- Các từ Dyck k - phân.
- Các từ Dyck m - màu.
- Mối quan hệ giữa các từ Dyck m màu và các từ Grand Dyck.
- Các từ Dyck k - phân m - màu.
- Một số thuật toán sinh và luật kế tiếp đề xuất 353.1.
- Một số thuật toán sinh.
- Phương pháp sinh theo luật đường chạy cuối cùng cho các lớp từ.
- Lớp từ Dyck.
- Các từ Motzkin.
- Các từ Schr¨oder.
- Các từ nhị phân mật độ cố định.
- Giải thuật chung cho một số lớp từ tổ hợp.
- Giải thuật sinh cho lớp từ Dyck.
- Giải thuật sinh cho lớp từ Dyck k - phân m - màu.
- 61Phụ lục: Một số hình ảnh trong chương trình sinh.
- Bảng tổng hợp một số lớp từ 334.1.
- Các kết quả thử nghiệm của thuật toán cho luật đường chạy cuốicùng cho các số nhị phân mật độ cố định C(k, n)584.2.
- Các kết quả thử nghiệm của thuật toán cho luật đường chạy cuốicùng thứ nhất của các từ Motzkin584.3 Các kết quả thử nghiệm của thuật toán với quy luật đường chạycuối cùng cho các từ Schr¨oder594.4 Các kết quả thử nghiệm của thuật toán với quy luật đường chạycuối cùng cho các từ Grand Dyck595 DANH MỤC CÁC HÌNHHình Nội dung hình Trang1.1.
- Biểu diễn 5 từ có độ dài bằng 6 101.2.
- Biểu diễn các từ Dyck 111.3.
- Mã hóa cây nhị phân 121.4 Biểu diễn các từ Motzkin 141.5 Biểu diễn các từ Schr¨oder 152.1.
- Biểu diễn các từ Grand Dyck 272.2.
- Biểu diễn các từ Grand Motzkin 272.3 Biểu diễn các từ Grand Schr¨oder 282.4.
- Biểu diễn mối liên hệ giữa các lớp từ 292.5.
- Biểu diễn từ Dyck 3 - phân 302.6 Đường đi của các từ Dyck 2 - màu 312.7 Minh họa từ Dyck 3 - phân 2 màu 323.1.
- Bốn từ kế tiếp của từ Dyck 363.2.
- Bốn từ kế tiếp của từ Dyck 383.3.
- Ba từ kế tiếp của từ Dyck 2 - màu 393.4.
- Minh họa sinh các từ Grand Dyck 413.5 Bốn từ kế tiếp của từ Dyck 3 - phân 423.6.
- Bốn từ kế tiếp β của từ Dyck 3 - phân 2 -màu có độ dài 9 433.8.
- Lý thuyết tổ hợp nghiên cứu việc phân bố các phần tử vàocác tập hợp.
- Mỗi cách phân bố được coi là một “cấu hình của tổ hợp”.
- Nguyên lý chung đểgiải quyết bài toán tổ hợp được dựa trên những nguyên lý cơ sở đó là nguyên lý cộng,nguyên lý nhân và một số nguyên lý khác, nhưng một đặc thù không thể tách rời củatoán học tổ hợp đó là việc chứng minh và kiểm chứng các phương pháp giải quyết bàitoán không thể tách rời máy tínhNgày nay, tổ hợp là một lĩnh vực tích cực với các ứng dụng và tác động khác nhautừ những phân tích của các thuật toán tới ngành vật lý thống kê và sinh học.
- Trongcác tổ hợp, tổ hợp liệt kê và tổ hợp ánh xạ xử lý đặc biệt với những vấn đề cơ bảncủa các cấu trúc tính toán trong các lớp tổ hợp và giải thích sự xuất hiện của cấu trúctheo định kỳ.Tổ hợp liệt kê là một trong các phần chính của tổ hợp và có liên quan tới việc đếmsố lượng các phần tử của một lớp hữu hạn một cách chính xác hoặc gần đúng.
- Cónhiều vấn đề phát sinh từ các lĩnh vực khác nhau có thể được giải quyết bằng cáchphân tích chúng từ một quan điểm tổ hợp.
- Thông thường, những vấn đề này có tínhphổ biến được đại diện bởi các đối tượng đơn giản phù hợp với các kỹ thuật liệt kê củacác tổ hợp.Những dạng bài toán quan trọng mà lý thuyết tổ hợp đề cập đó là bài toán đếm,bài toán liệt kê, bài toán tồn tại và bài toán tối ưu.Một trong những vấn đề đầu tiên giải quyết trong phần của các thuật toán tổ hợplà tạo ra các kết quả sinh hiệu quả trong lớp tổ hợp đặc biệt theo cách này mỗi đốitượng được sinh ra chỉ một lần.
- Trong thực tế, nhiều câu hỏi thực tế cần thiết cho việclấy mẫu của một đối tượng ngẫu nhiên từ một lớp tổ hợp hay việc tìm kiếm toàn bộcác đối tượng trong một lớp.
- Do đó, có nhiều lý do để phát triển các thuật toán cho cácdanh sách sản xuất của các đối tượng tổ hợp cơ bản.
- Trên thực tế, những giải thuật7 này rất hữu ích và tìm thấy nhiều ứng dụng trong các lĩnh vực khác nhau, chẳng hạnnhư kiểm thử phần cứng, phần mềm và hóa học tổng hợp.Có nhiều vấn đề trong lý thuyết tổ hợp đặc biệt các giải pháp của tổ hợp được đưara nhờ những con số Catalan.
- Cuốn sách “tổ hợp liệt kê” (Enumerative Combinatorics)của Richard P.
- Stanley đưa ra một danh sách các bài tập trong đó mô tả 66 giải thíchkhác nhau của các con số Catalan.Vấn đề sinh toàn bộ các đối tượng tổ hợp hiện nay được áp dụng nhiều trong nhiềungành như sinh học, y học, hóa học và khoa học máy tính.
- ngoài ra các số tổ hợp cũngxuất hiện rất nhiều trong ngành tin học ứng dụng.Mục đích chính của đề tài: Tìm ra các phương pháp sinh toàn bộ một số đối tượngtổ hợp quan trọng.Ứng dụng của đề tài: Nghiên cứu tính chất của các dãy số, sinh toàn bộ các số vớiđộ dài n và cách biểu diễn các dãy số.Bố cục của đề tài chia thành các chương như sau:- Chương 1.
- Họ các từ Dyck mở rộng và một số từ liên quan.- Chương 3.
- Một số thuật toán sinh và luật kế tiếp đề xuất.- Chương 4.
- Hơn nữa, phương pháp sinhmột số các đối tượng tổ hợp là mối quan tâm lớn trong các thập kỷ trước.
- Trước khiđi vào tìm hiểu một số khái niệm các đối tượng tổ hợp, ta có một số qui ước như sau:- Một chữ cái La tinh in thường biểu diễn một kí tự của bảng chữ cái.
- Ví dụ, a, b1,cnlà các kí tự.- Các chữ cái Hy Lạp in thường biểu diễn các từ trên một bảng chữ cái.
- nếuα = bc thì α4= (bc)4= bcbcbcbcbc.- Các từ có thể được biểu diễn bởi các đường đi trên lưới ô vuông (latticepath)trên hệ trục tọa độ Z2với các bước là m, m) với m ≥ 1.
- Xem ví dụsau, với 5 đường đi biểu diễn năm từ trên lưới ô vuông, mỗi từ có độ dài là 6.
- Khibiểu diễn các từ bằng các đường đi trên lưới ô vuông, các đường đi luôn nằm trên trụcOx, bắt đầu và kết thúc ở trục Ox.
- 0 tượng trưng cho (1, 0), khi đó mỗi từ tương ứngvới mỗi đường đi trên lưới ô được mã hóa với một từ ở trên bảng chữ cái a, b, 0.Ví dụ, 5 đường đi trên lưới ô vuông có độ dài là 6 ở trên được mã hóa bởi các từ:ababab, abaabb, aa0b0b, ababbb, aabbbb.- Cho một bảng chữ cái A, Anbiểu diễn tập các từ độ dài n trên A và A∗là tập Hình 1.1 : Biểu diễn 5 từ có độ dài bằng 6các từ có độ dài bất kì trên A.
- khi đó ta có A∗=Sn≥0An.- Độ dài của α ∈ A∗được ký hiệu là |α| và số lần xuất hiện của kí tự x trong α,với x ∈ A được ký hiệu là |α|x.- Cho các từ α, β như sau: α = α(1)α(2)...α(n), β = α(1)α(2)...α(k), k ≤ n khi đó,β được gọi là tiền tố của α.
- X)∗có tính chất tiền tố nếu vớimỗi tiền tố β của α, |β|b≤ |β|a, một tập các từ Y ⊂ ({a, b.
- X)∗có tính chất tiền tốnếu mỗi α ∈ Y có tính chất tiền tố.Ví dụ, X = 0, α = ab0ab có tính chất tiền tố nếu với β = ab0a là tiền tố của α thỏamãn vì |β|b≤ |β|avà tập các từ Y ⊂ (a, b, 0)∗nếu mỗi α ∈ Y có tính chất tiền tố.Như vậy, tính chất tiền tố đảm bảo các đường đi trên lưới ô vuông luôn nằm trêntrục Ox.- Cho α là một từ trên tập {a, b}.
- Một số đối tượng tổ hợp quan trọng1.2.1.
- Từ Dyck- Định nghĩa: Một từ α trên tập {a, b} được gọi là từ Dyck nếu nó có tính chất tiềntố và |α|b= |α|a.10 - Một từ Dyck là một từ nhị phân cùng với số lượng như nhau của bit 1, bit 0 vàthỏa mãn các đặc tính hậu tố: Hậu tố bất kì có ít nhất bit 0 cũng như bit 1.
- Các từDyck mã hóa một loạt các đối tượng tổ hợp bao gồm các cây nhị phân hoặc các đườnglưới ô vuông.
- Kí hiệu D2nlà tập các từ Dyck có độ dài 2n.- Khi biểu diễn các từ Dyck trên lưới ô vuông, đường đi của các từ Dyck luôn bắtđầu và kết thúc ở Ox.
- các từ Dyck khi biểu diễn chỉ gồm hai bước (1, 1) và (1, −1),khi đó m = 1.
- Tập hợp các từ Dyck độ dài n được kí hiệu là D(n) và n luôn luôn là sốchẵn để đảm bảo cho đường đi của chúng bắt đầu và kết thúc tại trục Ox.- Ví dụ, D(6) bao gồm các từ ababab, abaabb, aabbab, aababb, aaabbb.
- Biểu diễn từDyck có độ dài là 6 trên hệ tọa độ như sau:Hình 1.2 : Biểu diễn các từ Dyck: ababab, abaabb, aabbab, aababb, aaabbb ∈ D(6)Các từ Dyck mã hóa các cây nhị phân hoàn chỉnh.
- Cây nhị phân hoàn chỉnh là câynhị phân mà các nút trừ nút lá đều có hai con.Ứng dụng của các từ Dyck:Nếu O là tập các đối tượng tổ hợp Cn, các từ Dyck có thể được sử dụng cho việcmã hóa các đối tượng của O.
- Dưới đây là các giải thuật mã hóa và giải mã cho các câynhị phân:Giải thuật mã hóa cho một cây nhị phân - Cho BLlà cây con trái và BRlà cây conphải của cây nhị phân B.
- (*Trường hợp cây nhị phân chỉ có cây contrái.*)then w ← w01ENCODINGBT(BL)if (BL.
- (*Trường hợp cây nhị phân chỉ có cây conphải.*)then w ← w10ENCODINGBT(BR)if (BL6.
- (*Trường hợp cây nhị phân có cả cây con tráivà cây con phải*)then w ← w00ENCODINGBT(BL)w ← w11ENCODINGBT(BR)returnEnd;Hình 1.3 : Mã hóa cây nhị phânGiải thuật giải mã một từ Dyck trên cây nhị phân- Ban đầu, gốc của cây được tạo ra từ đỉnh hiện tại.
- Từ MotzkinCác từ Motzkin có rất nhiều ứng dụng đa dạng trong hình học, tổ hợp và trong lýthuyết số.
- Tập hợp các từ Motzkin13 độ dài n được ký hiệu M(n.
- Đường đi của một từ Motzkin có độ dài n là một đường lưới trong hệ lưới ô vuông (Z)với các bước và (1, 0).
- Như vậy, độ dài của các từ Motzkinchẵn hay lẻ phụ thuộc vào số bước ngang (1, 0) chẵn hay lẻ.- Các từ Motzkin khi biểu diễn trên đường lưới ô vuông thì đường đi của chúng luôn bắtđầu và kết thúc tại Ox hay bắt đầu tại điểm (0, 0) và kết thúc tại điểm (n, 0.
- Ví dụ, tập M(4) gồm các từ abab, aabb, ab00, a00b, 00ab, 0000, a0b0, 0a0b .
- Biểu diễn haitừ Motzkin abab, aabb thuộc tập M (4) như sau:Hình 1.4 : Biểu diễn các từ Motzkin abab, aabb, a00b, a0b01.2.3.
- Tập các từ Schr¨oder có độ dài n được ký hiệu là S(n) và n luôn là sốchẵn.- Khi biểu diễn từ Schr¨oder trên hệ trục tọa độ Z2, đường đi của các từ Schr¨oder gồmcác bước và yêu cầu cần ít nhất có hai đường ngang liên tiếp.
- Các từ Schr¨oder bắt đầu tại điểm (0, 0) và kết thúc tại điểm (n, 0.
- Ví dụ, các từ Schr¨oder có độ dài bằng 4 kí hiệu là S(4) gồm các từ ab00, a00b, 00ab, 0000,biểu diễn các từ này trên lưới ô vuông như sau:14 Hình 1.5 : Biểu diễn các từ Schr¨oder ab00, a00b, 00ab, 0000 ∈ S(4)1.3.
- Bài toán liệt kê và một số phương pháp sinh cơ bản1.3.1.
- Bài toán 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ướccó bao nhiêu đối tượng thoả mãn những điều kiện nhất định.
- Bài toán đó gọi là bài toánđếm.- Phương pháp đếm thường dựa vào một số nguyên lý cơ bản và một số kết quả đếmcấu hình đơn giản.
- Có nhiều phương pháp liệt kê nhưng các phương pháp cần phải đáp ứng được hai yêucầ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.- Có thể thấy rằng, phương pháp liệt kê là phương kế cuối cùng để giải được một số bàitoán tổ hợp hiện nay.
- Khó khăn chính của phương pháp này chính là sự bùng nổ tổ hợp dẫntới sự đòi hỏi lớn về không gian và thời gian thực hiện chương trình.
- Tuy nhiên cùng với sựphát triển của máy tính điện tử, bằng phương pháp liệt kê, nhiều bài toán tổ hợp đã tìmthấy lời giải.
- Một số phương pháp sinh cơ bảna) Phương pháp sinh kế tiếp- Phương pháp sinh kế tiếp có thể áp dụng để giải bài toán liệt kê tổ hợp đặt ra nếu nhưhai điều kiện sau thoả mãn:+ Có thể xác định được một thứ tự trên tập các cấu hình tổ hợp cần liệt kê.
- Từđó có thể biết được cấu hình đầu tiên và cấu hình cuối cùng trong thứ tự đó.+ Xây dựng được thuật toán từ một cấu hình chưa phải cấu hình cuối, sinh rađược cấu hình kế tiếp nó.Phương pháp sinh kế tiếp có thể mô tả như sau:(Xây dựng cấu hình đầu tiên);repeat(Đưa ra cấu hình đang có)(Từ cấu hình đang có sinh ra cấu hình kế tiếp nếu còn)until(Hết cấu hình)- Ví dụ, liệt kê các dãy nhị phân có độ dài n.
- Mỗi dãy nhị phân b = bn−1bn−2...b0, trongđó bi∈ {0, 1} có thể xem là biểu diễn nhị phân của một số nguyên P (b) nào đó nằm trongđoạn [0, 2n − 1].
- Vậy có thể lấy thứ tự tăng của số nguyên để xác định thứ tự các dãy nhịphân.Dãy nhị phân b = bn−1bn−2...b0được gọi là đi trước dãy a = an−1an−2...a0(hay a kế tiếpb) nếu P (b.
- Cách xác định thứ tự như vậy gọi là thứ tự tự nhiênhay còn gọi là thứ tự từ điển.Chẳng hạn với n = 3 ta có thứ tự từ điển của các dãy như sau:Thứ tự của dãy Dãy cụ thể Ta sẽ lập chương trình liệt kê các dãy nhị phân theo thứ tự từ điển có nghĩa là sẽ liệt kêlần lượt các dãy nhị phân biểu diễn các số nguyên theo thứ tự 0, 1

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt