LỜI CAM ĐOAN
Tôi xin cam đoan: Luận văn thạc sĩ Công nghệ thông tin "Phương pháp sinh
toà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ân
tôi, không trùng với bất kỳ luận văn nào khác. Luận văn hoàn thành là kết quả nghiên
cứu của cá nhân tôi dưới sự hướng dẫn tận tình của Tiến sĩ Đỗ Phan Thuận.
Hà Nội, tháng 09 năm 2012
Tác giả
Nguyễn Thị Hảo
1
LỜI CẢM ƠN
Đề hoàn thành chương trình học, tôi xin chân thành cảm ơn quý thầy cô
trong Viện Công nghệ thông tin và truyền thông - Trường Đại học Bách Khoa Hà nội
đã tận tình dạy bảo tôi trong thời gian qua.
Tôi xin gửi lời biết ơn sâu sắc tới Tiến sĩ Đỗ Phan Thuận đã dành nhiều thời
gian, tận tình hướng dẫn tôi hoàn thành luận văn này.
Nhân đây, cho tôi gửi lời cảm ơn đến ban lãnh đạo trường Đại học Hùng
Vương đã tạo điều kiện thuận lợi cho lớp học thạc sĩ Công nghệ thông tin năm 2010
học tập tại trường.
Trong quá trình làm luận văn, mặc dù tôi đã cố gắng nghiên cứu song không
thể tránh các thiếu xót. Vì vậy, tôi rất mong nhận được ý kiến đóng góp quý báu của
quí thầy cô và các bạn.
Hà Nội, tháng 09 năm 2012
Tác giả
Nguyễn Thị Hảo
2
Mục lục
Lời cam đoan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Chương 1. Giới thiệu và định nghĩa 9
1.1. Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2. Một số đối tượng tổ hợp quan trọng . . . . . . . . . . . . . . . . . . . . 10
1.2.1. Từ Dyck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.2. Từ Motzkin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.3. Từ Sch¨oder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3. Bài toán liệt kê và một số phương pháp sinh cơ bản . . . . . . . . . . . 15
1.3.1. Bài toán liệt kê . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3.2. Một số phương pháp sinh cơ bản . . . . . . . . . . . . . . . . . 16
1.4. Độ phức tạp của thuật toán sinh . . . . . . . . . . . . . . . . . . . . . 20
1.5. Phương pháp ECO và luật kế tiếp . . . . . . . . . . . . . . . . . . . . . 21
1.5.1. Phương pháp ECO đơn tầng . . . . . . . . . . . . . . . . . . . . 22
1.5.2. Phương pháp ECO đa tầng . . . . . . . . . . . . . . . . . . . . 22
1.5.3. Luật kế tiếp và cây sinh . . . . . . . . . . . . . . . . . . . . . . 23
Chương 2. Họ các từ Dyck mở rộng và một số từ liên quan 26
2.1. Các từ Grand Dyck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2. Các từ Grand Motzkin . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3. Các từ Grand Schr¨oder . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4. Các từ mở rộng khác của từ Dyck . . . . . . . . . . . . . . . . . . . . . 28
2.4.1. Các từ Dyck k - phân . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.2. Các từ Dyck m - màu . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.3. Mối quan hệ giữa các từ Dyck m màu và các từ Grand Dyck . . 31
2.4.4. Các từ Dyck k - phân m - màu . . . . . . . . . . . . . . . . . . 32
Chương 3. Một số thuật toán sinh và luật kế tiếp đề xuất 35
3.1. Một số thuật toán sinh . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2. Phương pháp sinh theo luật đường chạy cuối cùng cho các lớp từ . . . . 35
3.2.1. Lớp từ Dyck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.2. Các từ Dyck m - màu . . . . . . . . . . . . . . . . . . . . . . . 38
3.2.3. Các từ Grand Dyck . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.4. Các từ Dyck k - phân . . . . . . . . . . . . . . . . . . . . . . . 40
3.2.5. Các từ Dyck k - phân m - màu . . . . . . . . . . . . . . . . . . 41
3.2.6. Các từ Motzkin . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3. Các từ Grand Motzkin . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.4. Các từ Schr¨oder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.5. Các từ Grand Schr¨oder . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.6. Các từ nhị phân mật độ cố định . . . . . . . . . . . . . . . . . . . . . . 48
Chương 4. Giả mã và phân tích độ phức tạp các thuật toán sinh 50
4.1. Giải thuật chung cho một số lớp từ tổ hợp . . . . . . . . . . . . . . . . 50
4.2. Giải thuật sinh cho các lớp từ . . . . . . . . . . . . . . . . . . . . . . . 51
4.2.1. Giải thuật sinh cho lớp từ Dyck . . . . . . . . . . . . . . . . . . 51
4.2.2. Giải thuật sinh cho lớp từ Grand Dyck . . . . . . . . . . . . . . 52
4.2.3. Giải thuật sinh cho lớp từ Dyck k - phân m - màu . . . . . . . . 53
4.2.4. Giải thuật sinh cho lớp từ Motzkin . . . . . . . . . . . . . . . . 54
4.2.5. Giải thuật sinh cho lớp từ Schr¨oder . . . . . . . . . . . . . . . . 56
4.3. Đánh giá độ phức tạp của các giải thuật . . . . . . . . . . . . . . . . . 57
Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Phụ lục: Một số hình ảnh trong chương trình sinh . . . . . . . . . . . 63
4
DANH MỤC CÁC BẢNG
Bảng Nội dung bảng Trang
2.1. Bảng tổng hợp một số lớp từ 33
4.1. Các kết quả thử nghiệm của thuật toán cho luật đường chạy cuối
cùng cho các số nhị phân mật độ cố định C(k, n)
58
4.2. Các kết quả thử nghiệm của thuật toán cho luật đường chạy cuối
cùng thứ nhất của các từ Motzkin
58
4.3 Các kết quả thử nghiệm của thuật toán với quy luật đường chạy
cuối cùng cho các từ Schr¨oder
59
4.4 Các kết quả thử nghiệm của thuật toán với quy luật đường chạy
cuối cùng cho các từ Grand Dyck
59
5
DANH MỤC CÁC HÌNH
Hình Nội dung hình Trang
1.1. Biểu diễn 5 từ có độ dài bằng 6 10
1.2. Biểu diễn các từ Dyck 11
1.3. Mã hóa cây nhị phân 12
1.4 Biểu diễn các từ Motzkin 14
1.5 Biểu diễn các từ Schr¨oder 15
2.1. Biểu diễn các từ Grand Dyck 27
2.2. Biểu diễn các từ Grand Motzkin 27
2.3 Biểu diễn các từ Grand Schr¨oder 28
2.4. Biểu diễn mối liên hệ giữa các lớp từ 29
2.5. Biểu diễn từ Dyck 3 - phân 30
2.6 Đường đi của các từ Dyck 2 - màu 31
2.7 Minh họa từ Dyck 3 - phân 2 màu 32
3.1. Bốn từ kế tiếp của từ Dyck 36
3.2. Bốn từ kế tiếp của từ Dyck 38
3.3. Ba từ kế tiếp của từ Dyck 2 - màu 39
3.4. Minh họa sinh các từ Grand Dyck 41
3.5 Bốn từ kế tiếp của từ Dyck 3 - phân 42
3.6. Bốn từ kế tiếp β của từ Dyck 3 - phân 2 -màu có độ dài 9 43
3.8. Bốn từ kế tiếp của từ Motzkin 45
3.10. Bốn từ kế tiếp của từ Schr¨oder 39
6
MỞ ĐẦU
Tổ hợp là một lĩnh vực quan trọng của toán học rời rạc đề cập tới nhiều vấn đề
khác nhau của toán học. Lý thuyết tổ hợp nghiên cứu việc phân bố các phần tử vào
các tập hợp. Thông thường các phần tử của tập hợp là hữu hạn và việc phân bố chúng
phải thoả mãn những điều kiện nhất định nào đó tuỳ theo yêu cầu của bài toán nghiên
cứu. 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ủa
toá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ài
toán không thể tách rời máy tính
Ngà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 nhau
từ 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. Trong
cá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ản
củ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úc
theo đị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 đếm
số 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ách
phâ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ính
phổ 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ủa
cá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ợp
là 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 đối
tượ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ệc
lấ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ác
danh 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ật
7
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ạn
như 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 đưa
ra 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ích
khá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ều
ngành như sinh học, y học, hóa học và khoa học máy tính. Một cách tiếp cận được biết
đến nhiều để sinh toàn bộ được đưa ra trong đề án mã Gray cho việc sinh các số nhị
phân n bit theo cách này trong các số liên tiếp khác nhau đúng một vị trí bit. Trong
luận văn này, tôi giới thiệu một thuật toán sinh toàn bộ, đó là thuật toán chung cho
các lớp của các luật kế tiếp. Thuật toán này hiệu quả trong một phân tích khấu trừ
(Constant Amortized Time viết tắt CAT); CAT sử dụng một số lượng hằng số phép
tính trên một đối tượng được sinh ra.
Đề tài luận văn dựa trên cơ sở thực tiễn và khoa học: Nghiên cứu các số tổ hợp
quan trọng luôn được quan tâm và ứng dụng rộng rãi trong lĩnh vực lý thuyết tổ hợp
nói riêng và lý thuyết cơ sở của ngành tin học nói chung; ngoài ra các số tổ hợp cũng
xuấ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ượng
tổ 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. Giới thiệu và định nghĩa.
- Chương 2. 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. Giả mã và phân tích độ phức tạp các thuật toán sinh.
8
Chương 1
Giới thiệu và định nghĩa
1.1. Giới thiệu
Từ Dyck được xem là đối tượng nổi tiếng trong lớp các đối tượng tổ hợp, chúng
thường xuất hiện trong một vài loại như cây, hoán vị,. . . Hơn nữa, phương pháp sinh
mộ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, b
1
,
c
n
là 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. Ví dụ,
α, β, δ
00
được ký hiệu là các từ, λ biểu thị là một từ rỗng có độ dài bằng 0. Nếu α là
một từ thì α(i) là kí tự thứ i của α, với quy ước đó kí tự đầu tiên của α là α(1).
- Nếu a là một kí tự thì a
n
là từ chứa n lần a. Ví dụ, a
3
= aaa; (ab)
2
= abab; 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 độ Z
2
với các bước là (1, −1), (1, 0), (m, m) với m ≥ 1. Một đường
lưới không bao giờ đi xuống phía dưới trục Ox sẽ được gọi là không âm. 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. Khi
biể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ục
Ox, bắt đầu và kết thúc ở trục Ox. Qui ước a tượng trưng cho bước (m, m), m ≥ 0;
b tượng trưng cho bước (1, −1); 0 tượng trưng cho (1, 0), khi đó mỗi từ tương ứng
vớ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, A
n
biể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 6
các từ có độ dài bất kì trên A; khi đó ta có A
∗
=
S
n≥0
A
n
.
- Độ 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 α. Nếu thêm điều kiện k 6= n thì tiền tố β được gọi là tiền tố
chặt (proper) của α.
- Với X là một tập các kí tự, một từ α ∈ ({a, b} ∪ X)
∗
có tính chất tiền tố nếu với
mỗ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ỏa
mãn vì |β|
b
≤ |β|
a
và 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ên
trục Ox.
- Cho α là một từ trên tập {a, b}. Từ β thu được từ α bằng cách thay đổi mỗi a
bởi b, và ngược lại thay b bởi a, khi đó β gọi là đảo của α.
Ví dụ, cho α = abab, theo cách xây dựng trên ta có β = baba gọi là đảo của α .
1.2. Một số đối tượng tổ hợp quan trọng
1.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ền
tố 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 đường
lưới ô vuông. Kí hiệu D
2n
là 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ây
nhị 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 C
n
, các từ Dyck có thể được sử dụng cho việc
mã 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ây
nhị phân:
Giải thuật mã hóa cho một cây nhị phân - Cho B
L
là cây con trái và B
R
là cây con
phải của cây nhị phân B. Qui ước: w01 có nghĩa là nối từ nhị phân w với 01, w00 có
nghĩa là nối từ nhị phân w với 00, w11 có nghĩa là nối từ nhị phân w với 11, w10 có
nghĩa là nối từ nhị phân w với 10.
- Giải thuật mã hóa cho cây nhị phân B như sau:
ENCODINGBT(B)
begin
11
if (B
L
6= ∅) and (B
R
= ∅) (*Trường hợp cây nhị phân chỉ có cây con
trái.*)
then w ← w01
ENCODINGBT(B
L
)
if (B
L
= ∅) and (B
R
6= ∅) (*Trường hợp cây nhị phân chỉ có cây con
phải.*)
then w ← w10
ENCODINGBT(B
R
)
if (B
L
6= ∅) and (B
R
6= ∅) (*Trường hợp cây nhị phân có cả cây con trái
và cây con phải*)
then w ← w00
ENCODINGBT(B
L
)
w ← w11
ENCODINGBT(B
R
)
return
End;
Hình 1.3 : Mã hóa cây nhị phân
Giả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. Khi một cạnh được vẽ, đỉnh
cuối trở thành đỉnh hiện tại.
- Giải thuật giải mã như sau:
12
DECODINGBT(w)
begin
Cho ab là hai chữ cái đầu tiên của w
Xóa ab từ w
if ab = 01
then vẽ một đỉnh trái từ đỉnh hiện tại
DECODINGBT(w)
if ab = 10
then vẽ một đỉnh phải từ đỉnh hiện tại
DECODINGBT(w)
if ab = 00
then đặt vào ngăn xếp vị trí của đỉnh hiện tại.
vẽ một đỉnh trái từ đỉnh hiện tại.
DECODINGBT(w)
if ab = 11
then đặt vào ngăn xếp vị trí của đỉnh hiện tại.
vẽ một đỉnh phải từ đỉnh hiện tại.
DECODINGBT(w)
return
End;
Với giải thuật trên, khi thực hiện ta làm như sau:
Xóa 0 ở vị trí đầu tiên, xóa 1 ở vị trí cuối cùng của từ nhị phân w.
Vẽ một đỉnh (gốc của cây) là đỉnh hiện tại.
DECODINGBT(w)
1.2.2. Từ Motzkin
Cá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ố. Một vài số Motzkin đầu tiên là: 1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798,
15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559,
400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209,
593742784829.
- Định nghĩa: Một từ α trên tập {a, b, 0} được gọi là từ Motzkin nếu nó có tính chất tiền
tố và số các kí tự b trên α bằng số các kí tự a trên α (|α|
b
= |α|
a
). Tập hợp các từ Motzkin
13
độ 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 (1, 1), (1, −1) và (1, 0). Số bước ngang của từ Motzkin lẻ thì độ dài lẻ và ngược
lại, số bước ngang chẵn thì độ dài của từ Motzkin chẵn. Như vậy, độ dài của các từ Motzkin
chẵ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 hai
từ 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, a0b0
1.2.3. Từ Sch¨oder
- Định nghĩa: Một từ α trên tập {a, b, 0} được gọi là từ Schr¨oder nếu nó là từ Motzkin
và nếu α
i
= α
i+1
= ... = α
j
= 0 và (i = 1 hoặc α
i−1
6= 0) và (j = n + 1 hoặc α
j+1
6= 0) thì
(j − i + 1) là số chẵn. 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 độ Z
2
, đường đi của các từ Schr¨oder gồm
các bước (1, 1), (1, −1), (1, 0) và yêu cầu cần ít nhất có hai đường ngang liên tiếp. Khi đó, có
thể quy hai bước ngang thành bước một bước (2, 0).
- 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ản
1.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ước
có 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ả đếm
cấu hình đơn giản. Bài toán đếm thường áp dụng một cách có hiệu quả vào những công việc
mang tính chất đánh giá như tính xác suất của một sự kiện, tính độ phức tạp của một thuật
toán, ...
- Trong lớp các bài toán đếm, có những bài toán còn yêu cầu chỉ rõ những cấu hình tìm
được thoả mãn điều kiện cho trước là những cấu hình nào. Bài toán yêu cầu đưa ra danh
sách các cấu hình có thể có gọi là bài toán liệt kê. Để 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 các phương pháp 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.
- 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ài
toá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ẫn
tớ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ìm
thấy lời giải. Bài toán này quan tâm đến tất cả các cấu hình có thể có được, vì thế lời giải
của nó cần được biểu diễn dưới dạng thuật toán "vét cạn" tất cả các cấu hình do đó chỉ nên
15
dùng phương pháp liệt kê khi không còn một phương pháp nào khác tìm ra lời giải.
1.3.2. Một số phương pháp sinh cơ bản
a) 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 = b
n−1
b
n−2
...b
0
, trong
đó b
i
∈ {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 = b
n−1
b
n−2
...b
0
được gọi là đi trước dãy a = a
n−1
a
n−2
...a
0
(hay a kế tiếp
b) nếu P (b) < P (a), kí hiệu là b < a. Cách xác định thứ tự như vậy gọi là thứ tự tự nhiên
hay 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 0 1 2 3 4 5 6 7
Dãy cụ thể 000 001 010 011 100 101 110 111
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, . . . , 2n − 1. Như vậy, dãy
đầu tiên gồm toàn số 0, dãy cuối cùng gồm toàn số 1. Nhận xét rằng nếu b = b
n−1
b
n−2
...b
0
là dãy đang có và không phải là dãy cuối cùng cần liệt kê thì dãy kế tiếp sẽ nhận được bằng
16
