68 trang 5 lượt tải

Bài Giảng Toán Rời Rạc: Tổ Hợp và Thuật Toán Liệt Kê Môn Toán giải tích | Trường Học Viện nông nghiệp Việt Nam

9

TOÁN RỜI RẠCSơ lược về tổ hợp1. BÀI TOÁN ĐẾM2. BÀI TOÁN LIỆT KÊNỘI DUNG2.1. Giới thiệu bài toán2.2. Thuật toán và độ phức tạp tính toán2.3. Phương pháp sinh2.4. Thuật toán quay lui. Tài liệu gồm 68 trang, giúp các bạn tham khảo, ôn tập và đạt kết quả cao. Mình bạn đọc đón xem!

Môn: Toán giải tích (HVNN) 6 tài liệu

Trường: Học viện Nông nghiệp Việt Nam 2.2 K tài liệu

Tác giả:

Profile

Hân Hân

1 tuần trước
Danh sách Quiz
/68
BÀI GIÁNG TOÁN RàI RẠC
PHẦN 1: LÝ THUYẾT TỔ HỢP
TOÁN RỜI RẠC
2
N⑥I
DUNG
•
Sơ lược về tỗ hợp.
•
Bài toán đếm
•
Bài toán liệt kê
TOÁN RỜI RẠC
3
2.
BÀI TOÁN LIST KÊ
N⑥I
DUNG
2.1.
Giái thi»u bài toán
2.2.
Thuªt toán và độ phùc tạp tính toán
2.3.
Phuơng pháp sinh
2.4.
Thuªt toán quay lui
TOÁN RỜI RẠC
4
Ví dụ 2.1.1: Cho các số a
1
, a
2
, . . . , a
n
và số M. Hãy tìm tất cǎ các tªp con
gồm k phần tû được lấy tø n số đã cho sao cho tỗng các phần tû trong mői
tªp con này đúng bằng M.
2.1. Giái thi»u bài toán
TOÁN RỜI RẠC
5
n
n
Phân tích:
De dàng thấy rằng số các tªp con gồm k phần tû lấy tø {a
1
, a
2
, . . . , a
n
} là C
k
.
Như vªy, ta cần duyệt trong số
C
k
tªp con
k
phần tû để lấy ra các tªp có
tỗng các phần tû đúng bằng
M.
Tuy nhiên, ta sẽ g°p rất nhiều khó khăn để xác định có bao nhiêu tªp con
gồm
k
phần tû lấy tø
n
mà tỗng các phần tû cǔa tªp con này đúng bằng
M
.
Do vªy, một phương pháp thích hợp cho bài toán này là xây dụng các bước
phù hợp để liệt kê được hết tất cǎ các tªp con thǒa mãn. Đây là bài toán
thuộc nhóm
bài toán li»t kê.
TOÁN RỜI RẠC
6
D Bài toán đưa ra danh sách tất cǎ các cấu hình tỗ hợp có thể có được được
gọi là bài toán li»t kê.
D Phuơng pháp chung để giái bài toán: Xác định một thuªt toán để theo
đó có thể xây dụng được lần lượt tất cǎ các cấu hình cần quan tâm.
D Phuơng pháp li»t kê phái đám báo hai nguyên tắc:
•
Không được l°p lại bất kỳ một cấu hình nào.
•
Không được bǒ sót bất kỳ một cấu hình nào.
TOÁN RỜI RẠC
7
D Các buác tiến hành giái bài toán trên máy tính:
•
Hiểu yêu cầu cǔa bài toán.
•
Chọn cấu trúc dú liệu biểu dien phương án cần duyệt.
•
Chọn thuªt toán phù hợp với cấu trúc dú liệu.
•
Cài đ°t thuªt toán và thû nghiệm chương trình.
•
Tối ưu hóa chương trình.
TOÁN RỜI RẠC
8
2.2.1.
Thuªt toán
D Định nghĩa: Dãy húu hạn các thao tác sơ cấp F = F
1
F
2
· · ·
F
n
: Input →
Output
được gọi là một thuªt toán trên tªp thông tin vào Input để có
được kết quǎ ra Output. Dãy các thao tác sơ cấp được hiểu là các phép toán
số học, các phép toán logic, các phép toán so sánh.
D Các đ°c trung cơ bán cúa thuªt toán:
•
Đầu vào (Input):
Thuªt toán nhªn dú liệu vào tø một tªp nào đó.
•
Đầu ra (Output):
Với mői tªp các dú liệu đầu vào, thuªt toán đưa ra các
dú liệu tương ùng với lời giǎi cǔa bài toán.
2.2. Thuªt toán và độ phùc tạp tính toán
TOÁN RỜI RẠC
9
•
Chính xác (Precision):
Các bước cǔa thuªt toán được mô tǎ chính xác.
•
Húu hạn (Finiteness): Thuªt toán cần phǎi đưa được đầu ra sau một số
húu hạn (có thể rất lớn) bước với mọi đầu vào.
•
Đơn trị (Uniqueness): Các kết quǎ trung gian cǔa tøng bước thục hiện
thuªt toán được xác định một cách đơn trị và chǐ phụ thuộc vào đầu vào
và các kết quǎ cǔa các bước trước.
•
Tổng quát (Generality): Thuªt toán có thể áp dụng để giǎi mọi bài toán
có dạng đã cho.
TOÁN RỜI RẠC
10
Ví dụ 2.2.1:
Mô tǎ một thuªt toán để tìm giá trị lớn nhất trong một dãy số
nguyên húu hạn?
TOÁN RỜI RẠC
11
Giái:
Ta có thể tiến hành theo các bước sau:
Buác 1:
Đ°t giá trị lớn nhất tạm thời (max) bằng số đầu tiên cǔa dãy.
Buác 2:
So sánh số ngay gần sau trong dãy với max, và nếu số này lớn hơn
max thì đ°t lại max bằng số vøa so sánh.
Buác S:
L°p lại bước trên nếu dãy còn có thêm nhiều số hạng.
Buác 4:
Døng lại nếu không còn số hạng nào cǔa dãy. Giá trị lớn nhất tạm
thời ơ bước này chính là giá trị lớn nhất cǔa dãy.
TOÁN RỜI RẠC
12
Giái (Ví dụ 2.2.1): Cho ví dụ quá trình thục hiên thuªt toán trên vái dãy
gồm a
1
= 1, a
2
= 4, a
3
= 3 nhu sau:
+ Tại Bước 1, đ°t max (giá trị lớn nhất tạm thời):=a
1
(=1).
+ Tại Bước 2, số hạng ngay sau là
a
2
=
4
và thấy
a
2
=
4
> max
nên thay đỗi
max và đ°t max:=4.
+ Do dãy số còn số hạng chưa duyệt nên chuyển sang Bước 3: So sánh
a
3
=
3
với max và thấy
a
3
< max
nên không làm gì, tùc max=4.
+ Do dãy số không còn số hạng tiếp nên chuyển sang Bước 4, tùc là kết thúc
thuªt toán. Giá trị lớn nhất cǔa dãy là
4
.
TOÁN RỜI RẠC
13
Giái (Ví dụ 2.2.1): Bây già, ta chí ra thuªt toán vøa mô tá có các đ°c trung
cơ bán:
Đầu vào:
dãy húu hạn các số.
Đầu ra:
số lớn nhất trong dãy.
Chính xác, đơn tr$:
Thuªt toán chǐ có các phép gán, một vòng l°p húu hạn và
các câu lệnh có điều kiện nên mői bước được xác định chính xác; khi thuªt
toán kết thúc, max chính là số lớn nhất cǔa dãy; nếu đầu vào đã xác định thì
kết quǎ ơ mői bước được xác định duy nhất và kết quǎ này chǐ phụ thuộc
vào đầu vào và các kết quǎ cǔa các bước trước đó.
Húu hạn: Thuªt toán kết thúc khi tất cǎ các số hạng được kiểm tra nên nó
thục hiện sau một số húu hạn bước.
Tổng quát: Thuªt toán luôn đưa ra giá trị lớn nhất cǔa dãy bất kỳ.
TOÁN RỜI RẠC
14
Giái (Ví dụ 2.2.1):
Đoạn chương trình cǔa thuªt toán trên:
int max
−
value(int a[],
int n){
max = a[0];
for (i = 1; i < n, i + +){
if max < a[i]{
max = a[i];
}
}
return (max);
}
TOÁN RỜI RẠC
15
D Phuơng pháp biểu diễn thuªt toán:
•
Ngôn ngú tụ nhiên:
Là phương tiện giao tiếp giúa con người với con
người. Ta có thể sû dụng nó để mô tǎ thuªt toán.
•
Ngôn ngú hình thùc:
Là phương tiện giao tiếp trung gian giúa con
người và máy tính; chẫng hạn: ngôn ngú sơ đồ khối, ngôn ngú đ°c tǎ,
ngôn ngú tụa tụ nhiên... Thông thường người ta hay dùng ngôn ngú
này để mô tǎ thuªt toán.
•
Ngôn ngú máy tính:
Là phương tiện giao tiếp giúa các máy tính với
nhau. Người ta có thể sû dụng bất kỳ ngôn ngú lªp trình nào để biểu
dien thuªt toán.
TOÁN RỜI RẠC
16
Ví dụ 2.2.2:
Mô tǎ thuªt toán tìm ước chung lớn nhất cǔa hai số tụ nhiên
a, b
(ký hiệu:
UCLN
(
a, b
)
) bằng ngôn ngú tụ nhiên?
TOÁN RỜI RẠC
17
Giái:
Đầu vào:
Đưa vào hai số tụ nhiên
a
và
b
.
Đầu ra:
Số nguyên không âm
u
lớn nhất để
a
và
b
đều chia hết cho
u.
Thuªt toán (thuªt toán Euclide):
B1.
Đưa vào hai số tụ nhiên
a
và
b.
B2.
Nếu
b
≠
0
thì chuyển đến bước 3; còn nếu
b
=
0
thì thục hiện bước 4.
BS.
Đ°t
r
=
a
mod
b
; đỗi
a
=
b
và
b
=
r
. Sau đó quay trơ lại bước 2.
B4.
Kết luªn
u
=
a
là số cần tìm.
TOÁN RỜI RẠC
18
Ví dụ 2.2.S:
Mô tǎ thuªt toán tìm ước chung lớn nhất cǔa hai số tụ nhiên
a, b
(ký hiệu:
UCLN
(
a, b
)
) bằng ngôn ngú hình thùc?
TOÁN RỜI RẠC
19
Giái: Thuªt toán Euclide:
Đầu vào: a ∈ N, b ∈ N.
Đầu ra: s = max{u ∈ N | a mod u = 0, b mod u = 0}.
Format: s =
Euclid (a, b).
Actions:
while
(
b
≠
0)
do
r = a mod b; a = b; b = r;
endwhile;
return (a);
Endactions.
TOÁN RỜI RẠC
20
Ví dụ 2.2.4:
Mô tǎ thuªt toán tìm ước chung lớn nhất cǔa hai số tụ nhiên
a, b
(ký hiệu:
UCLN
(
a, b
)
) bằng ngôn ngú máy tính (dùng ngôn ngú lªp
trình
C
+ +
)?

Tài liệu khác của Học viện Nông nghiệp Việt Nam

Preview text:


BÀI GIÁNG TOÁN RàI RẠC
PHẦN 1: LÝ THUYẾT TỔ HỢP TOÁN RỜI RẠC N⑥I DUNG
• Sơ lược về tỗ hợp. • Bài toán đếm • Bài toán liệt kê 2 TOÁN RỜI RẠC 2. BÀI TOÁN LIST KÊ N⑥I DUNG
2.1. Giái thi»u bài toán
2.2. Thuªt toán và độ phùc tạp tính toán
2.3. Phuơng pháp sinh
2.4. Thuªt toán quay lui 3 TOÁN RỜI RẠC
2.1. Giái thi»u bài toán
Ví dụ 2.1.1: Cho các số a1, a2, . . . , an và số M. Hãy tìm tất cǎ các tªp con
gồm k phần tû được lấy tø n số đã cho sao cho tỗng các phần tû trong mői
tªp con này đúng bằng M. 4 TOÁN RỜI RẠC Phân tích:
De dàng thấy rằng số các tªp con gồm k phần tû lấy tø {a1, a2, . . . , an} là Ckn .
Như vªy, ta cần duyệt trong số Ck tªp con k phần tû để lấy ra các tªp có n
tỗng các phần tû đúng bằng M.
Tuy nhiên, ta sẽ g°p rất nhiều khó khăn để xác định có bao nhiêu tªp con
gồm k phần tû lấy tø n mà tỗng các phần tû cǔa tªp con này đúng bằng M.
Do vªy, một phương pháp thích hợp cho bài toán này là xây dụng các bước
phù hợp để liệt kê được hết tất cǎ các tªp con thǒa mãn. Đây là bài toán
thuộc nhóm bài toán li»t kê. 5 TOÁN RỜI RẠC
D Bài toán đưa ra danh sách tất cǎ các cấu hình tỗ hợp có thể có được được
gọi là bài toán li»t kê.
D Phuơng pháp chung để giái bài toán: Xác định một thuªt toán để theo
đó có thể xây dụng được lần lượt tất cǎ các cấu hình cần quan tâm.
D Phuơng pháp li»t kê phái đám báo hai nguyên tắc:
• Không được l°p lại bất kỳ một cấu hình nào.
• Không được bǒ sót bất kỳ một cấu hình nào. 6 TOÁN RỜI RẠC
D Các buác tiến hành giái bài toán trên máy tính:
• Hiểu yêu cầu cǔa bài toán.
• Chọn cấu trúc dú liệu biểu dien phương án cần duyệt.
• Chọn thuªt toán phù hợp với cấu trúc dú liệu.
• Cài đ°t thuªt toán và thû nghiệm chương trình.
• Tối ưu hóa chương trình. 7 TOÁN RỜI RẠC
2.2. Thuªt toán và độ phùc tạp tính toán 2.2.1. Thuªt toán
D Định nghĩa: Dãy húu hạn các thao tác sơ cấp F = F1F2 · · · Fn : Input →
Output được gọi là một thuªt toán trên tªp thông tin vào Input để có
được kết quǎ ra Output. Dãy các thao tác sơ cấp được hiểu là các phép toán
số học, các phép toán logic, các phép toán so sánh.
D Các đ°c trung cơ bán cúa thuªt toán:
• Đầu vào (Input): Thuªt toán nhªn dú liệu vào tø một tªp nào đó.
• Đầu ra (Output): Với mői tªp các dú liệu đầu vào, thuªt toán đưa ra các
dú liệu tương ùng với lời giǎi cǔa bài toán. 8 TOÁN RỜI RẠC
• Chính xác (Precision): Các bước cǔa thuªt toán được mô tǎ chính xác.
• Húu hạn (Finiteness): Thuªt toán cần phǎi đưa được đầu ra sau một số
húu hạn (có thể rất lớn) bước với mọi đầu vào.
• Đơn trị (Uniqueness): Các kết quǎ trung gian cǔa tøng bước thục hiện
thuªt toán được xác định một cách đơn trị và chǐ phụ thuộc vào đầu vào
và các kết quǎ cǔa các bước trước.
• Tổng quát (Generality): Thuªt toán có thể áp dụng để giǎi mọi bài toán có dạng đã cho. 9 TOÁN RỜI RẠC
Ví dụ 2.2.1: Mô tǎ một thuªt toán để tìm giá trị lớn nhất trong một dãy số nguyên húu hạn? 10 TOÁN RỜI RẠC
Giái: Ta có thể tiến hành theo các bước sau:
Buác 1: Đ°t giá trị lớn nhất tạm thời (max) bằng số đầu tiên cǔa dãy.
Buác 2: So sánh số ngay gần sau trong dãy với max, và nếu số này lớn hơn
max thì đ°t lại max bằng số vøa so sánh.
Buác S: L°p lại bước trên nếu dãy còn có thêm nhiều số hạng.
Buác 4: Døng lại nếu không còn số hạng nào cǔa dãy. Giá trị lớn nhất tạm
thời ơ bước này chính là giá trị lớn nhất cǔa dãy. 11 TOÁN RỜI RẠC
Giái (Ví dụ 2.2.1): Cho ví dụ quá trình thục hiên thuªt toán trên vái dãy
gồm a1 = 1, a2 = 4, a3 = 3 nhu sau:
+ Tại Bước 1, đ°t max (giá trị lớn nhất tạm thời):=a1 (=1).
+ Tại Bước 2, số hạng ngay sau là a2 = 4 và thấy a2 = 4 > max nên thay đỗi max và đ°t max:=4.
+ Do dãy số còn số hạng chưa duyệt nên chuyển sang Bước 3: So sánh
a3 = 3 với max và thấy a3 < max nên không làm gì, tùc max=4.
+ Do dãy số không còn số hạng tiếp nên chuyển sang Bước 4, tùc là kết thúc
thuªt toán. Giá trị lớn nhất cǔa dãy là 4. 12 TOÁN RỜI RẠC
Giái (Ví dụ 2.2.1): Bây già, ta chí ra thuªt toán vøa mô tá có các đ°c trung cơ bán:
Đầu vào: dãy húu hạn các số. Đầu ra: số lớn nhất trong dãy.
Chính xác, đơn tr$: Thuªt toán chǐ có các phép gán, một vòng l°p húu hạn và
các câu lệnh có điều kiện nên mői bước được xác định chính xác; khi thuªt
toán kết thúc, max chính là số lớn nhất cǔa dãy; nếu đầu vào đã xác định thì
kết quǎ ơ mői bước được xác định duy nhất và kết quǎ này chǐ phụ thuộc
vào đầu vào và các kết quǎ cǔa các bước trước đó.
Húu hạn: Thuªt toán kết thúc khi tất cǎ các số hạng được kiểm tra nên nó
thục hiện sau một số húu hạn bước.
Tổng quát: Thuªt toán luôn đưa ra giá trị lớn nhất cǔa dãy bất kỳ. 13 TOÁN RỜI RẠC
Giái (Ví dụ 2.2.1): Đoạn chương trình cǔa thuªt toán trên:
int max−value(int a[], int n){
max = a[0];
for (i = 1; i < n, i + +){
if max < a[i]{
max = a[i]; } }
return (max); } 14 TOÁN RỜI RẠC
D Phuơng pháp biểu diễn thuªt toán:
• Ngôn ngú tụ nhiên: Là phương tiện giao tiếp giúa con người với con
người. Ta có thể sû dụng nó để mô tǎ thuªt toán.
• Ngôn ngú hình thùc: Là phương tiện giao tiếp trung gian giúa con
người và máy tính; chẫng hạn: ngôn ngú sơ đồ khối, ngôn ngú đ°c tǎ,
ngôn ngú tụa tụ nhiên... Thông thường người ta hay dùng ngôn ngú
này để mô tǎ thuªt toán.
• Ngôn ngú máy tính: Là phương tiện giao tiếp giúa các máy tính với
nhau. Người ta có thể sû dụng bất kỳ ngôn ngú lªp trình nào để biểu dien thuªt toán. 15 TOÁN RỜI RẠC
Ví dụ 2.2.2: Mô tǎ thuªt toán tìm ước chung lớn nhất cǔa hai số tụ nhiên
a, b (ký hiệu: UCLN(a, b)) bằng ngôn ngú tụ nhiên? 16 TOÁN RỜI RẠC Giái:
Đầu vào: Đưa vào hai số tụ nhiên a và b.
Đầu ra: Số nguyên không âm u lớn nhất để a và b đều chia hết cho u.
Thuªt toán (thuªt toán Euclide):
B1. Đưa vào hai số tụ nhiên a và b.
B2. Nếu b ≠ 0 thì chuyển đến bước 3; còn nếu b = 0 thì thục hiện bước 4.
BS. Đ°t r = a mod b; đỗi a = b và b = r. Sau đó quay trơ lại bước 2.
B4. Kết luªn u = a là số cần tìm. 17 TOÁN RỜI RẠC
Ví dụ 2.2.S: Mô tǎ thuªt toán tìm ước chung lớn nhất cǔa hai số tụ nhiên
a, b (ký hiệu: UCLN(a, b)) bằng ngôn ngú hình thùc? 18 TOÁN RỜI RẠC
Giái: Thuªt toán Euclide:
Đầu vào: a ∈ N, b ∈ N.
Đầu ra: s = max{u ∈ N | a mod u = 0, b mod u = 0}.
Format: s = Euclid (a, b). Actions:
while (b ≠ 0) do
r = a mod b; a = b; b = r; endwhile;
return (a); Endactions. 19 TOÁN RỜI RẠC
Ví dụ 2.2.4: Mô tǎ thuªt toán tìm ước chung lớn nhất cǔa hai số tụ nhiên
a, b (ký hiệu: UCLN(a, b)) bằng ngôn ngú máy tính (dùng ngôn ngú lªp trình C + +)? 20

Tài liệu liên quan: