Bài giảng Toán rời rạc - Phần 1: Lý thuyết tổ hợp - Mở đầu - Nguyễn Đức Nghĩa
Nội dung
1. Mở đầu
2. Bài toán đếm tổ hợp (Counting Problem)
3. Bài toán tồn tại tổ hợp (Existence Problem)
4. Bài toán liệt kê tổ hợp (Enumeration Problem)
5. Bài toán tối ưu tổ hợp (Combinatorial
Optimization Problem)
2
Toán rời rạc
0. Mở đầu
NỘI DUNG
0.1. Tổ hợp là gì?
0.2. Sơ lược về lịch sử phát triển của tổ hợp
0.3. Tập hợp và ánh xạ
3
Toán rời rạc
0.1 Tổ hợp là gì?
⚫ Đối tượng nghiên cứu
⚫ Nội dung nghiên cứu
4
Toán rời rạc
Đối tượng nghiên cứu của tổ hợp
⚫ Lý thuyết tổ hợp gắn liền với việc nghiên
cứu sự sắp xếp của các phần tử trong các tập
hữu hạn và sự phân bố của các phần tử vào
các tập hữu hạn. Mỗi cách sắp xếp hoặc phân
bố như thế được gọi là một cấu hình tổ hợp.
⚫ Có thể nói vắn tắt: Tổ hợp là lý thuyết về các
tập hữu hạn.
5
Toán rời rạc
Phân loại bài toán
⚫ Trong các tài liệu về tổ hợp, thường gặp các dạng
bài toán dưới đây:
1. Bài toán đếm tổ hợp (Counting Problem)
2. Bài toán tồn tại tổ hợp (Existence Problem)
3. Bài toán liệt kê tổ hợp (Enumeration Problem)
4. Bài toán tối ưu tổ hợp (Combinatorial
optimization Problem)
6
Toán rời rạc
Bài toán đếm – Counting Problem
⚫ Đây là các bài toán nhằm trả lời câu hỏi: “Có bao
nhiêu cấu hình thoả mãn các điều kiện cho
trước?".
⚫ 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ác cấu hình đơn
giản.
⚫ Bài toán đếm được á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, ...
7
Toán rời rạc
Bài toán tồn tại tổ hợp
(Existence Problem)
⚫ Khác với bài toán đếm, trong bài toán tồn tại tổ
hợp chúng ta cần trả lời câu hỏi: “Tồn tại hay
chăng cấu hình tổ hợp thoả mãn các tính chất đã
cho?”
⚫ Rõ ràng nếu có thể đếm được số lượng cấu hình
tổ hợp thoả mãn các tính chất đó cho thì ta cũng
giải quyết được bài toán tồn tại tương ứng!
⚫ Có thể coi bài toán tồn tại như trường hợp riêng
của bài toán đếm được không?
8
Toán rời rạc
Ví dụ
⚫ Bài toán phủ bàn cờ quốc tế bởi các quân
bài domino:
“Cho bàn cờ quốc tế kích thước 88 bị đục đi
2 ô ở hai góc đối diện và bộ bài domino, mỗi
quân bài phủ kín 2 ô của bàn cờ. Hỏi có thể
phủ kín bàn cờ đã cho bởi 31 quân bài
domino?”
9
Toán rời rạc
Bàn cờ quốc tế và quân bài domino
10
Toán rời rạc
Bàn cờ quốc tế và quân bài domino
11
Toán rời rạc
Có thể phủ bàn cờ như vậy
bởi 31 quân bài domino?
⚫ Bàn cờ còn 62 ô
⚫ 31 quân bài có thể
phủ kín được 62 ô
⚫ Về diện tích là có
thể phủ được
12
Toán rời rạc
Không tồn tại cách phủ bàn cờ như vậy
bởi 31 quân bài domino!
⚫ Chứng minh
⚫ Mỗi quân bài phủ kín 1 ô
trắng và một ô đen.
⚫ Suy ra số lượng ô trắng và
ô đen bị phủ bởi 31 quân
domino là bằng nhau.
⚫ Thế nhưng số lượng ô
trắng và ô đen trên phần
còn lại của bàn cờ là khác
nhau
⚫ Từ đó suy ra không tồn
tại cách phủ!
13
Toán rời rạc
Có bao nhiêu cách phủ bàn cờ
bởi 32 quân bài domino?
⚫ Sự tồn tại cách phủ là
hiển nhiên. Dễ dàng
có thể chỉ ra vài cách
phủ
⚫ Vấn đề “Có bao nhiêu
cách phủ?”
⚫ Không dễ dàng trả
lời!
14
Toán rời rạc
Có bao nhiêu cách phủ bàn cờ
bởi 32 quân bài domino?
⚫ Nếu chỉ phân biệt hai cấu hình bởi
dạng hình học của cách phủ thì có
tất cả
12 988 816
cách phủ.
Có 2 cách phủ bàn cờ
kích thước 22
15
Toán rời rạc
Phân biệt hai bài toán đếm và tồn tại
⚫ Trong bài toán đếm, sự tồn tại cấu hình là hiển nhiên và
vấn đề là cần đếm xem có bao nhiêu.
⚫ Trong bài toán tồn tại, bản thân sự tồn tại cấu hình là vấn
đề nghi vấn. Cần giải quyết vấn đề “có hay không có” cấu
hình như vậy.
• Việc chỉ ra được một cấu hình là đủ để khẳng định là
tồn tại
• Nhưng để chỉ ra sự không tồn tại cấu hình đòi hỏi phải
đưa ra những lập luận tin cậy
16
Toán rời rạc
Bài toán liệt kê tổ hợp
(Enumeration Problem)
⚫ Bµi to¸n nµy quan t©m ®Õn viÖc ®a ra tÊt c¶ cÊu h×nh
tho¶ m·n c¸c ®iÒu kiÖn cho trí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. Lêi gi¶i trong tõng trêng hîp
cô thÓ sÏ ®îc m¸y tÝnh ®iÖn tö gi¶i quyÕt theo thuËt to¸n ®·
nªu.
• Bµi to¸n liÖt kª ®îc lµm "nÒn" cho nhiÒu bµi to¸n kh¸c. HiÖn
nay, mét sè bµi to¸n ®Õm, tèi u, tån t¹i vÉn cha cã c¸ch nµo
gi¶i, ngoµi c¸ch gi¶i liÖt kª.
• NÕu tríc ®©y, c¸ch gi¶i liÖt kª cßn mang nÆng tÝnh lý thuyÕt,
th× b©y giê nã ngµy cµng kh¶ thi nhê sù ph¸t triÓn nhanh
chãng cña m¸y tÝnh ®iÖn tö.
17
Toán rời rạc
Bài toán tối ưu tổ hợp
(Combinatorial Problem)
⚫ Khác với bài bài toán liệt kê, bài toán tối ưu chỉ quan tâm
đến một cấu hình "tốt nhất" theo một nghĩa nào đấy.
⚫ Trong các bài toán tối ưu, mỗi cấu hình được gán cho một
giá trị số (là giá trị sử dụng hoặc chi phí xây dựng cấu
hình), và bài toán đặt ra là trong số những cấu hình thoả
mãn các điều kiện cho trước hãy tìm cấu hình với giá trị
số gán cho nó là lớn nhất hoặc nhỏ nhất.
⚫ Đây là bài toán có nhiều ứng dụng trong thực tiễn và lý
thuyết tổ hợp đã đóng góp một phần đáng kể trong việc
xây dựng được những thuật toán hữu hiệu.
18
Toán rời rạc
0. Mở đầu
NỘI DUNG
0.1. Tổ hợp là gì?
0.2. Sơ lược về lịch sử phát triển của tổ hợp
0.3. Tập hợp và ánh xạ
19
Toán rời rạc
0.2. Sơ lược về lịch sử phát triển
⚫ Có thể nói là tổ hợp là một trong những lĩnh
vực có lịch sử phát triển lâu đời nhất của
toán học
⚫ Nói về lịch sử phát triển của tổ hợp cũng
chính là nói về lịch sử phát triển của toán học
⚫ Vì vậy, chúng ta sẽ chỉ điểm qua vài nét về
lịch sử, thông qua một số bài toán nổi tiếng
trong lịch sử phát triển của tổ hợp
Fall 2008
20
Toán rời rạc
Tải về để xem bản đầy đủ
91 trang
26/04/2022
4580
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Phần 1: Lý thuyết tổ hợp - Mở đầu - Nguyễn Đức Nghĩa", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_phan_1_ly_thuyet_to_hop_nguyen_duc_ng.ppt
