- Trang Chủ
- Kỹ thuật lập trình
- Giáo trình Cơ sở toán cho tin học (Nghề: Lập trình viên máy tính - Cao đẳng) - Trường CĐ Nghề Kỹ thuật Công nghệ
Xem mẫu
- BỘ LAO ĐỘNG -THƯƠNG BINH VÀ XÃ HỘI
TRƯỜNG CAO ĐẲNG NGHỀ KỸ THUẬT CÔNG NGHỆ
-----š› & š›-----
GIÁO TRÌNH
MÔN HỌC: CƠ SỞ TOÁN CHO TIN HỌC
NGHỀ: LẬP TRÌNH VIÊN MÁY TÍNH
TRÌNH ĐỘ: CAO ĐẲNG
Ban hành kèm theo Quyết định số: 13A/QĐ-CĐNKTCN ngày 10 tháng 01 năm 2019
của Hiệu trưởng Trường Cao đẳng nghề Kỹ thuật Công nghệ
Hà Nội, năm 2021
(Lưu hành nội bộ)
- TUYÊN BỐ BẢN QUYỀN
Tài liệu này thuộc loại sách giáo trình nên các nguồn thông tin có thể được phép
dùng nguyên bản hoặc trích dùng cho các mục đích về đào tạo và tham khảo.
Mọi mục đích khác mang tính lệch lạc hoặc sử dụng với mục đích kinh doanh
thiếu lành mạnh sẽ bị nghiêm cấm.
MÃ TÀI LIỆU: MHLTV 11
1
- LỜI GIỚI THIỆU
Trong những năm qua, dạy nghề đã có những bước tiến vượt bậc cả về số lượng
và chất lượng, nhằm thực hiện nhiệm vụ đào tạo nguồn nhân lực kỹ thuật trực tiếp đáp
ứng nhu cầu xã hội. Cùng với sự phát triển của khoa học công nghệ trên thế giới, lĩnh
vực Công nghệ thông tin nói chung và ngành Lập trình viên ở Việt Nam nói riêng đã
có những bước phát triển đáng kể.
Chương trình dạy nghề Lập trình viên máy tính đã được xây dựng trên cơ sở phân
tích nghề, phần kỹ năng nghề được kết cấu theo các môđun. Để tạo điều kiện thuận lợi
cho các cơ sở dạy nghề trong quá trình thực hiện, việc biên soạn giáo trình theo các
môđun đào tạo nghề là cấp thiết hiện nay.
Môn học11: Cơ sở toán cho tin học là môn học đào tạo nghề được biên soạn theo
hình thức tích hợp lý thuyết và thực hành. Trong quá trình thực hiện, nhóm biên soạn
đã tham khảo nhiều tài liệu liên quan, kết hợp với các kinh nghiệm trong thực tế.
Mặc dù đã có rất nhiều cố gắng, nhưng không tránh khỏi những khiếm khuyết, rất
mong nhận được sự đóng góp ý kiến của độc giả để giáo trình được hoàn thiện hơn.
Xin chân thành cảm ơn!
Hà Nội, ngày 25 tháng 04 năm 2021
Tham gia biên soạn
1. Chủ biên : Phùng Quốc Cảnh
2. Tập thể Giảng viên khoa CNTT
Mọi thông tin đóng góp chia sẻ xin gửi về hòm thư: canhdhtn86@gmail.com, hoặc liên
hệ số điện thoại: 0359300585
2
- MỤC LỤC
LỜI GIỚI THIỆU ........................................................................................................ 2
MỤC LỤC ................................................................................................................... 3
CHƯƠNG 1: QUAN HỆ VÀ SUY LUẬN TOÁN HỌC ............................................. 6
1. Quan hệ hai ngôi ................................................................................................. 6
1.1. Khái niệm về quan hệ hai ngôi .................................................................... 6
1.2. Các tính chất có thể có của quan hệ trong một tập hợp ................................ 6
1.3. Quan hệ tương đương ................................................................................. 7
1.4. Quan hệ thứ tự ............................................................................................ 7
2. Suy luận toán học ................................................................................................ 8
2.1. Quy nạp toán học ........................................................................................ 8
2.2. Định nghĩa bằng đệ quy .............................................................................. 9
2.3. Các thuật toán đệ quy................................................................................ 10
2.4. Tính đúng đắn của chương trình ................................................................ 11
Bài tập chương 1 của học sinh, sinh viên ................................................................... 13
CHƯƠNG 2: TÍNH TOÁN VÀ XÁC SUẤT ............................................................ 15
1. Tính toán ........................................................................................................... 15
1.1. Nguyên lý cộng ......................................................................................... 15
1.2. Nguyên lý nhân ......................................................................................... 16
1.3. Lý thuyết tổ hợp........................................................................................ 17
1.4. Nguyên lý bù trừ ....................................................................................... 20
1.5. Nguyên lý Dirichlet .................................................................................. 21
2. Xác suất ............................................................................................................ 21
2.1. Sự kiện ngẫu nhiên ................................................................................... 21
2.2. Các định nghĩa xác suất ............................................................................ 23
2.3. Các định lý về xác suất ............................................................................. 24
2.3.1. Định lý cộng xác suất ......................................................................... 24
2.3.2. Xác xuất có điều kiện ......................................................................... 25
Bài tập chương 2 của học sinh, sinh viên ................................................................... 29
CHƯƠNG 3: MA TRẬN VÀ THUẬT TOÁN .......................................................... 31
1. Ma trận .............................................................................................................. 31
1.1. Mở đầu ....................................................................................................... 31
1.2. Số học ma trận : .......................................................................................... 31
1.3. Chuyển vị và luỹ thừa các ma trận .............................................................. 20
1.4. Các ma trận 0 - 1 (không - một) .................................................................. 20
3
- 2. Thuật toán ......................................................................................................... 22
2.1. Khái niệm thuật toán ................................................................................. 23
2.2. Các đặc trưng của thuật toán ..................................................................... 23
2.3. Ngôn ngữ thuật toán.................................................................................. 23
2.4. Độ phức tạp của thuật toán........................................................................ 24
2.4.1. Khái niệm về độ phức tạp của thuật toán ............................................ 24
2.4.2. So sánh độ phức tạp thuật toán ........................................................... 25
2.4.3. Đánh giá độ phức tạp của thuật toán ................................................... 27
Bài tập chương 3 của học sinh, sinh viên ................................................................... 28
CHƯƠNG 4: PHƯƠNG PHÁP TÍNH ....................................................................... 30
1.1. Số xấp xỉ ................................................................................................... 30
1.2. Sai số tuyệt đối ......................................................................................... 30
1.3. Sai số tương đối ........................................................................................ 31
2.1. Nghiệm và khoảng phân ly nghiệm ........................................................... 31
2.2. Phương pháp dây cung .............................................................................. 33
2.3. Phương pháp tiếp tuyến (newton).............................................................. 34
2.4. Phương pháp phối hợp .............................................................................. 35
2.5. Phương pháp chia đôi ............................................................................... 36
2.6. Phương pháp lặp ....................................................................................... 37
3.1. Phát biểu bài toán...................................................................................... 38
3.2. Phương pháp Gauss .................................................................................. 39
4. Nội suy và phương pháp bình phương cực tiểu .................................................. 42
4.1. Đa thức nội suy ......................................................................................... 42
4.2. Tính giá trị của đa thức : sơ đồ Hoócne ..................................................... 43
4.3. Đa thức nội suy Lagrăng ........................................................................... 44
4.4. Đa thức nội suy Newton............................................................................ 47
4.5. Phương pháp bình phương cực tiểu ........................................................... 51
Bài tập chương 4 của học sinh, sinh viên ................................................................... 54
4
- GIÁO TRÌNH MÔN HỌC
Tên môn học: Cơ sở toán cho tin học
Mã môn học: MHLTV 11
Vị trí, tính chất, ý nghĩa và vai trò của môn học:
- Vị trí: Môn học được bố trí sau khi sinh viên học xong các môn học chung.
- Tính chất: Là môn học cơ sở nghề.
- Ý nghĩa và vai trò của môn học: Đây là mô đun đào tạo chuyên môn nghề, cung cấp
cho sinh viên các kỹ năng cơ bản nhất của nghề Quản trị mạng.
Mục tiêu của môn học:
- Về kiến thức:
+ Vận dụng các kiến thức đã sinh viên viên xây dựng các thuật toán tính : tổ hợp, hoán
vị, giải hệ phương trình, phương trình, tính tích phân;
- Về kỹ năng:
+ Sử dụng các kiến thức đã sinh viên viên xây dựng thuật toán quay lại, các bài toán
tối ưu, bài toán tồn tại;
+ Là nền tảng để sinh viên học môn cấu trúc dữ liệu và giải thuật, cài đặt các thuật
toán trong tin học;
- Về năng lực tự chủ và trách nhiệm
+ Bố trí làm việc khoa học đảm bảo an toàn cho người và phương tiện học tập.
Nội dung của môn học:
Thời gian
Số Tên chương, mục Thực Kiểm
Tổng Lý
TT hành tra/Thi
số thuyết
Bài tập
1 Chương 1: Quan hệ - Suy luận toán học 3 3 0
1. Quan hệ hai ngôi 1
2. Suy luận toán học 2
2 Chương 2: Tính toán và xác suất 8 6 2
1. Tính toán 3 1
2. Xác suất 3 1
3 Chương 3 : Ma trận và thuật toán 8 7 0 1
1. Ma trận 2
2. Thuật toán 5
4 Chương 4: Phương pháp tính 10 7 3
1. Số xấp xỉ và sai số 1
2. Giải gần đúng các phương trình 2 1
3. Giải hệ thống phương trình đại số
tuyến tính 2 1
4. Nội suy và phương pháp bình
phương cực tiểu 2 1
5 Thi kết thúc môn học 1 1
Cộng 30 23 5 2
5
- CHƯƠNG 1: QUAN HỆ VÀ SUY LUẬN TOÁN HỌC
Mã chương: MHLTV 11-01
Giới thiệu:
Mệnh đề là mảng kiến thức khá đơn giản nhưng ảnh hưởng rất nhiều đến các
định hướng logic trong toán học.
Mệnh đề có thể là một câu nhưng không phải mọi câu đều là mệnh đề. Có thể
chia các câu trong khoa học cũng như trong cuộc sống ra làm hai loại: loại thứ nhất
gồm những câu phản ánh tính đúng hoặc sai một thực tế khách quan và loại thứ hai
gồm những câu không phản ánh tính đúng hoặc sai một thực tế khách quan nào.
Suy luận là một hành động hay quá trình các kết luận logic phát sinh từ các
mệnh đề được biết hay được giả định là chân lý. Các kết luận rút ra cũng được gọi là
một thành ngữ. Quy tắc suy luận được nghiên cứu trong lĩnh vực logic.
Mục tiêu:
- Trình bày được các phép toán trong quan hệ hai ngôi;
- Trình bày được thứ tự các phép toán trong biểu thức;
- Biến đổi chính xác các quan hệ tương đương trong các bài toán theo dạng quan
hệ;
- Trả lời chính xác các bảng trắc nghiệm về quan hệ hai ngôi và suy luận toán học;
- Kiểm tra tính đúng của một chương trình cụ thể;
- Áp dụng được giải thuật quy nạp và đệ qui;
- Thực hiện các thao tác an toàn với máy tính.
Nội dung chính:
1. Quan hệ hai ngôi
Mục tiêu:
- Trình bày được các phép toán trong quan hệ hai ngôi;
- Trình bày được thứ tự các phép toán trong biểu thức;
- Biến đổi chính xác các quan hệ tương đương trong các bài toán theo dạng quan
hệ.
1.1. Khái niệm về quan hệ hai ngôi
Giả sử cho tập X khác rỗng và một tính chất  được thoả mãnvới một sốcặp
phần tử a, b nào đó của X . Khi đó ta nói a có quan hệ  với bvà viết a  b, còn Â
được gọi là một quan hệ hai ngôi trong X.
Ví dụ 1.1:
1) Trong tập R mọi số thực, quan hệ “a = b” hoặc quan hệ “a £ b” là quan hệ
hai ngôi.
2) Trong tập mọi đường thẳng trên mặt phẳng, quan hệ vuông góc giữa hai
đường thẳng là quan hệ hai ngôi.
3) Trên tập N* các số nguyên dương, “ a là ước số của b” là quan hệ hai ngôi.
4) Trên tập P(E) các phân tập của tập E quan hệ bao hàm A Ì B là quan hệ hai
ngôi.
1.2. Các tính chất có thể có của quan hệ trong một tập hợp
Quan hệ ℜ trong tập X (tức ℜ ⊂X2) có thể có các tính chất sau:
- Tính phản xạ : a ℜ a " a Î X (tức là (a, a)∈ ℜ " a ∈ X )
6
- - Tính đối xứng : a ℜ b Þ b ℜ a (tức nếu (a, b) ∈ ℜ thì (b, a) ∈ ℜ )
- Tính phản đối xứng : (a ℜb và b ℜa ) Þ a = b
- Tính bắc cầu : (a ℜb) và (b ℜc) Þ a ℜc
Ví dụ 1.2:
Trong tập hợp P(X) các phân tập của tập hợp X quan hệ bao hàm A⊂ B có tính
phản xạ, phản đối xứng và bắc cầu mà không có tính đối xứng.
Trong tập hợp mọi đa thức của một biến số thực, quan hệ bằng nhau có tính
phản xạ, đối xứng và bắc cầu.
1.3. Quan hệ tương đương
Quan hệ ℜ trong tập X gọi là quan hệ tương đương nếu nó có tính phản xạ, đối
xứng, bắc cầu.
Trong trường hợp này, ta viết a ~ b thay vì a ℜb .
Ví dụ1.3: Quan hệ song song giữa các đường thẳng trong tập mọi đường thẳng
của không gian (coi 2 đường thẳng trùng nhau là song song); quan hệ đồng dạng giữa
các tam giác; quan hệ cùng tỉnh của một tập hợp dân một thành phố là các ví dụ trực
quan của quan hệ tương đương.
Các lớp tương đương :
Giả sử ~ là một quan hệ tương đương trong X. Với mỗi phần tử a ∈ X,
ta ký hiệu C(a) là tập hợp mọi phần tử thuộc X tương đương với a và gọi nó là lớp
tương đương chứa a.
C(a) = {x∈X / x ~ a}
Do tính phản xạ a ≈ a nên mỗi tập con C(a) không rỗng. Hơn nữa nếu
C(a)∩C(b)≠Ø thì c(a) = c(b).
Thật vậy, giả sử c∈C(a)∩C(b), thì ta có :
c∈C(a) và c∈C(b)
Tức là c ~ a và c ~ b, hay b ~ c ~ a. Từ đó do tính chất bắc cầu, suy ra b ~ a, vậy
b∈C(a).
Lập luận tương tự ta cũng có a∈C(b), tức là C(a) = C(b).
Từ đó rút ra được định lý :
Một quan hệ tương đương trong X xác định một phân hoạch của X, mỗi phần tử
của phân hoạch này là một lớp tương đương.
Họ các lớp tương đương này được gọi là tập thương, ký hiệu X/~.
Ví dụ 1.4: Trong tập các số nguyên Z.
Xét quan hệ R : a ℜb⇔a – b = 2p a, b, p Î Z.
Ta có :
(a ℜ a) a – a = 2p (p = 0) phản xạ
(a ℜ b) a – b = 2p ⟶ (b – a) = -2p (b ℜ a) đối xứng
a – b = 2p, b – c = 2q
⇒(a – c) = (a – b) + (b – c) = 2(p + q) bắc cầu
Vậy ℜ là một quan hệ tương đương.
Ta có : a = b + 2p
- Lớp tương đương ứng với b = 0 là các số chẳn.
- Lớp tương đương ứng với b = 1 là các số lẻ.
1.4. Quan hệ thứ tự
Định nghĩa 1.1:Quan hệ ℜ trong X gọi là quan hệ thứ tự (hay quan hệ bộ phận)
nếu có tính phản đối xứng và bắc cầu.
7
- Nếu ngoài ra với bất kỳ hai phần tử nào x∈X, y ∈Y đều có x ℜy hoặc y ℜx
thì ℜgọi là quan hệ thứ tự toàn phần (hay thứ tự tuyến tính).
Khi ℜlà một quan hệ thứ tự trong X ta nói X được xếp thứ tự bởi ℜ và
thayvìx ℜy ta viết x ≤ y và đọc “x bé hơn y” hoặc “x đi trước y”. Ta cũng viết y ³ x
và đọc “y lớn hơn x” hoặc “y đi sau x”.
Nếu x ≤ y và x ≠ y ta viết x < y (hay y > x).
Ví dụ 1.5:
Quan hệ < hoặc≤ thông thường trong tập hợp các số thực là quan hệ thứ tự toàn
phần, R là tập được sắp thứ tự.
Quan hệ bao hàm⊂ trong tập P(X) mọi tập con của tập X là quan hệ thứ tự bộ
phận. Tuy nhiên nó không là thứ tự toàn phần.
Quan hệ “a⋮ b” tức a là bội số của b trong N* là quan hệ thứ tự bộ phận. Tập X
trong đó đã xác định một quan hệ thứ tự gọi là tập đựoc sắp xếp.
2. Suy luận toán học
Mục tiêu:
- Trình bày chính xác về quy nạp toán học và đệ quy;
- Kiểm tra tính đúng của một chương trình cụ thể;
- Áp dụng được giải thuật quy nạp và đệ quy.
2.1. Quy nạp toán học
Nhiều định lý phát biểu rằng P(n) là đúng với mọi n nguyên dương, trong đó
P(n) là một hàm mệnh đề. Quy nạp toán học là một kỹ thuật chứng minh các định lý
thuộc loại như thế. Nói cách khác quy nạp toán học thường được sử dụng để chứng
minh các mệnh đề "P(n), trong đó n là số nguyên dương tuỳ ý.
Qua trình chứng minh P(n) là đúng với mọi số nguyên dương n bao gồm hai
bước :
Bước cơ sở : Chỉ ra mệnh đề P(1) là đúng.
Bước quy nạp : chứng minh phép kéo theo P(n) " P(n + 1) là đúng với mọi số
nguyên dương n, trong khi đó người ta gọi P(n) là giả thiết quy nạp.
Khi hoàn thành cả hai bước chúng ta đã chứng minh P(n) là đúng với mọi n
nguyên dương, tức là đã chứng minh P(n) là đúng.
Ví dụ 2.1: Bằng quy nạp toán học hãy chứng minh rằng tổng n số nguyên
dương lẻ đầu tiên là n2.
Giải: Gọi P(n) là mệnh đề “tổng n số nguyên dương lẻ đầu tiên là n2”. Đầu tiên
ta cần làm bước cơ sở, tức là phải chỉ ra P(1) là đúng. Sau đó phải chứng minh bước
quy nạp, tức là cần chỉ ra P(n + 1) là đúng nếu giả sử P(n) là đúng.
Bước cơ sở : P(1) hiển nhiên là đúng vì 1 = 12.
Bước quy nạp : Giả sử P(n) đúng, tức là với mọi n nguyên dương lẻ ta có :
1+3+5+…+(2n-1) = n2
Ta phải chỉ ra P(n+1) là đúng, tức là :
1+3+5+…+(2n-1)+(2n+1) = (n+1)2
Do giả thuyết quy nạp ta suy ra :
1+3+5+…+(2n-1)+(2n+1)
= [1+3+5+…+(2n-1)]+(2n+1)
= n2+(2n+1) = (n+1)2
Đẳng thức này chứng tỏ P(n+1) được suy ra từ P(n).
8
- Vì P(1) là đúng và vì mệnh đề kéo theo. P(n) "P(n + 1) là đúng với mọi n
nguyên dương, theo nguyên lý quy nạp toán học chỉ ra rằng P(n) là đúng với mọi n
nguyên dương.
2.2. Định nghĩa bằng đệ quy
Đôi khi chúng ta rất khó định nghĩa một đối tượng một cách tường minh, nhưng
có thể dễ dàng địng nghĩa đối tượng này qua chính nó.Kỹ thuật này được gọi là đệ
quy.
a. Các hàm được định nghĩa bằng đệ quy
Để định nghĩa một hàm xác định trên tập các số nguyên không âm, chúng ta
cho:
· Giá trị của hàm tại n = 0.
· Công thức tính giá trị của nó tại số nguyên n từ các giá trị của nó tại các số
nguyên nhỏ hơn.
Định nghĩa như thế được gọi là định nghĩa đệ quy hay định nghĩa quy nạp.
Ví dụ 2.2: Giả sử f được định nghĩa bằng đệ quy như sau :
f(0) = 3, f(n+1) = 2f(n)+3
Hãy tìm f(1), f(2), f(3) và f(4).
Giải : Từ định nghĩa đệ quy ta suy ra :
f(1) = 2f(0) + 3 = 2.3 + 3 = 9
f(1) = 2f(1) + 3 = 2.9 + 3 = 21
f(1) = 2f(2) + 3 = 2.21 + 3 = 45
f(1) = 2f(3) + 3 = 2.45 + 3 = 93
Trong một số định nghĩa hàm bằng đệ quy, người ta cho giá trị của hàm tại k số
nguyên dương đầu tiên và cho qui tắc tính giá trị của hàm tại số nguyên dương lớn
hơn từ k giá trị này. Theo nguyên lý thứ hai của quy nạp toán học thì cách định nghĩa
này tạo ra các hàm hoàn toàn xác định.
b. Các tập hợp được định nghĩa bằng đệ quy
Các tập hợp thường được định nghĩa bằng đệ quy.Trước tiên người ta đưa ra tập
xuất phát.Sau đó là quy tắc tạo các phần tử mới từ các phần tử đã biết của tập.Những
tập đuợc mô tả bằng cách như vậy được gọi là các tập được dịnh nghĩa tốt, các định lý
về chúng có thể chứng minh bằng cách sử dụng định nghĩa đệ quy của chúng.
Ví dụ 2.3: Giã sử S được định nghĩa bằng đệ quy như sau :
3 ∈ S;
x+y ∈ S nếu x ∈ S và y ∈ S;
Hãy chỉ ra rằng S là tập các số nguyên chia hết cho 3.
Giải : Gọi A là tập các số nguyên dương chia hết cho 3. Để chúng minh A = S
ta sẽ chứng minh rằng A là một tập con của S và S là tập con của A. Để chứng minh A
là tập con của S, giả sử P(n) là mệnh đề “3n thuộc tập S”. P(1) đúng vì theo định nghĩa
của S “3.1 =3 ∈S”.
Giả sử P(n) đúng, tức là 3n ∈S. Vì 3 ∈Svà 3n ∈Snên theo định nghĩa 3+3n =
3(n+1) ∈S. Điều này có nghĩa là P(n+1) đúng. Theo quy nạp toán học mọi số có dạng
3n, với n nguyên dương, thuộc S, hay nói cách khác A là tập con của S.
Ngược lại, 3 ∈S, hiển nhiên 3 chia hết cho 3 nên 3 ∈A. Tiếp theo ta chứng minh
tất cả các phần tử của S sinh ra do phần tử thứ 2 của định nghĩa, cũng thuọcc A. Giả sử
x, y là hai phần tử của S, cũng là hai phần tử của A. Theo định nghĩa của S thì x+y
cũng là một phần tử của S, vì x và y đều chia hết cho 3 nên x+y cũng chia hết cho 3,
tức là x+y ∈A. Vậy S là tập con của A.
9
- Định nghĩa đệ quy thường được dùng khi nghiên cứu các xâu kí tự. Xâu là một
dãy kí tự thuộc bộ chữ cái∑. Tập hợp các xâu ứng với bộ chữ cái được ký hiệu bởi ∑*.
Hai xâu có thể kết hợp với nhau theo phép ghép. Ghép các xâu x và y cho xy là xâu tạo
nên bằng cách viết tiếp xâu y vào xâu x. Ví dụ : cho x = abra, y = cadabra, khi đó xy =
abracadabra. Khi chứng minh các kết quả về xâu người ta thường dùng định nghĩa đệ
quy.
Ví dụ2.4: Định nghĩa đệ quy của tập các xâu.
Giả sử ∑* là tập các xâu trên bộ chữ cái∑. Khi đó ∑* được định nghĩa bằng đệ
quy như sau :
· ∈ ∑*, trong đó là một xâu rỗng (không có phần tử nào);
· x∈ ∑* nếu ∈ ∑* và x ∈ ∑.
Phần đầu của định nghĩa nói rằng xâu rỗng thuộc∑*.Phần sau khẳng định bằng một
xâu mới tạo nên bằng cách ghép một kí tự của∑với một xâu của∑* cũng thuộc∑*.
Độ dài của xâu, tức là số kí tự trong xâu, cũng được định nghĩa bằng đệ quy.
Ví dụ2.5: Hãy định nghĩa bằng đệ quy độ dài của xâu .
Giải:Ta kí hiệu độ dài của là 1( ). Khi đó định nghĩa đệ quy của 1( ) như
sau :
· 1(λ) = 0, trong đóλ là xâu rỗng;
· 1(ωx) = 1(ω) + 1 nếu ω ∈ ∑* và x ∈ ∑.
2.3. Các thuật toán đệ quy
Định nghĩa 2.1:Một thuật toán được gọi là đệ quy nếu nó giải bài toán bằng các
cách rút gọn liên tiếp bài toán ban đầu tới bài toán cũng như vậy nhưng có dữ liệu vào
nhỏ hơn.
Ví dụ 2.6: Tìm thuật toán đệ quy tính giá trị an và a là số thực khác không và n
là số nguyên không âm.
Giải : Ta xây dựng thuật toán đệ quy như định nghĩa đệ quy của an , đó là an =
a.an-1 với n >0 và khi n = 0 thì a0 = 1. Vậy để tính an ta quy về các trường hợp có số mũ
nhỏ hơn, cho tới khi n = 0. Xem thuật toán 1 sau đây :
Thuật toán 1: thuật toán đệ quy tínhan
Procedure power(a: số thực khác không ; n: số nguyên không âm);
Begin
if n = 0 then power(a,n): = 1
elsepower(a,n): = a * power(a,n – 1);
End;
Định nghĩa đệ quy biểu diễn giá trị của hàm tại một số nguyênqua giá trị của nó
tại các số nguyên nhỏ hơn.Điều này có nghĩa là ta có thể xây dựng một thuật toán đệ
quy tính giá trị của hàm được định nghĩa bằng đệ quy tại một điểm nguyên.
Ví dụ 2.7: Thủ tục đệ quy sau đây cho ta giá rị của n! với n số nguyên dương.
Giải: Ta xây dựng thuật toán đệ quy như định nghĩa đệ quy của n! , đó là n! =
n.(n-1)! với n>1 và khi n = 1 thì 1!= 1.
Thuật toán 2: thuật toán đệ quy tính giai thừa
Procedure factorial(n: nguyên dương);
Begin
if n = 1 then factorial(n): = 1
elsefactorial(n): = n * factorial(n – 1);
End;
10
- Có cách khác tính hàm giai thừa của một số nguyên từ định nghĩa đệ quy của
nó.Thay cho việc lần lược rút gọn việc tính toán cho các giá trị nhỏ hơn, chúng ta có
thể xuất phát từ giá trị của hàm tại 1 và lần lược áp dụng định nghĩa đệ quy để tìm giá
trị của hàm tại các số nguyên lớn dần.Đó là thủ tục lặp. Nói cách khác để tìm n! ta xuất
phát từ n! = 1 (với n = 1), tiếp theo lần lượt nhân với các số nguyêncho tới khi bằng n.
Xem thuật toán 3:
Thuật toán 3: Thủ tục lặp tính giai thừa
Procedure factorial(n: nguyên dương);
Begin
x : = 1;
for i : = 1 to n
x : = i*x;
End; {x là n!}
2.4. Tính đúng đắn của chương trình
Mở đầu
Giả sử rằng chúng ta thiết kế được một thuật toán để giải một bài toán nào đó
và dã viết chương trình để thể hiện nó. Liệu ta có thể tin chắc rằng chương trình có
luôn luôn cho lời giải đúng hay không ?Sau khi tất cả các sai sót về mặc cú pháp được
loại bỏ, chúng ta có thể thử chương trình với các đầu vào mẫu.Tuy nhiên, ngay cả khi
chương trình cho kết quả đúng với tất cả các đầu vào mẫu, nó vẫn có thể luôn luôn tạo
ra các câu trả lời đúng (trừ khi tất cả các đầu vào đều đã được thử).Chúng ta cần phải
chứng minh rằng chương trình luôn luôn cho đầu ra đúng.
Kiểm chứng chương trình
Một chương trình gọi là đúng đắn nếu với mọi đầu vào khả dĩ, nó cho đầu ra
đúng.Việc chứng minh tính đúng dắn của chương trình gồm hai phần.Phần đầu chỉ ra
rằng nếu chương trình kết thúc thì nhận được kết quả đúng.Phần này xác minh tính
đúng đắn bộ phận của chương trình.Phần thứ hai chứng tỏ chương trình luôn luôn là
kết thúc.
Để định rõ thế nào là một chương trình cho thông tin ra đúng, người ta thường
dùng hai mệnh đề sau :
- Thứ nhất là khẳng định đầu, nó đưa ra những tính chất mà thông tin đầu vào
cần phải có.
- Mệnh đề thứ hai là khẳng định cuối, nó đưa ra những tính chất mà thông tin
đầu ra cần phải có, tùy theo mục đích của chương trình. Khi kiểm tra chương trình cần
phải chuẩn bị các khẳng định đầu và khẳng định cuối.
Định nghĩa 2.2:Chương trình hay đoạn chương trình S được gọi là đúng đắn bộ
phận đối với khẳng định đầu p và khẳng định cuối q, nếu p là đúng với các giá trị vào
của S và nếu S kết thúc thì q là đúng với các giá trị ra của S. Ký hiệu p{S}q có nghĩa
là chương trình hay đoạn chương trình S là đúng đắn bộ phận đối với khẳng định đầu p
và khẳng định cuối q.
Chú ý:Khái niệm đúng đắn bộ phận không đề cập tới việc chương trình có kết
thúc hay không. Nó chỉ nhằm kiểm tra xem chương trình có làm được cái mà nó định
làm hay không, nếu nó kết thúc.
Câu lệnh điều kiện
Trước tiên, chúng ta sẽ trình bày những quy tắc suy luận đối với câu lệnh điều
kiện. Giả sử một đoạn chương trình có dạng :
If điều-kiện then
11
- S
Trong đó S là một khối lệnh.Khối S sẽ được thi hành nếu điều kiện là đúng và S
sẽ không được thi hành nếu điều kiện là sai.
Tương tự, giả sử một đoạn chương trình có dạng :
If điều-kiện then
S1
Else
S2
Nếu điều kiện là đúng thì S1 được thi hành, nếu điều kiện là sai thì S2 được thi
hành.
Bất biến vòng lặp
Tiếp theo chúng ta sẽ trình bày cách chứng minh tính đúng đắncủa vòng lặp
While. Để xây dựng quy tắc suy luận cho đoạn chương trình dạng :
While điều-kiện
S
Hãy lưu ý rằng S được lặp đi lặp lại cho tới khi nào điều kiện trở nên sai. Ta gọi
một điều khẳng định nà đó là bất biến vọng lặp nếu nó vẫn còn đúng sau mỗi lần S thi
hành.
12
- Bài tập chương 1 của học sinh, sinh viên
Bài 1:Dùng quy nạp toán học chứng minh rằng:
a. 1+3+5+…+2n-1 = n2 "n nguyên dương.
2 n n+1
b. 1 + 2 + 2 + … + 2 = 2 -1"n≥0 và nguyên.
( )( )
c. 12 + 22 + … + n2 = "n≥0 và nguyên.
( )( )
d. 1.2 + 2.3 + …+ n(n+1) = "n nguyên dương.
Bài 2:Chứng minh đẳng thức sau đúng với mọi n > 1, a > -1 và a ¹ 0
(1 + a)n> 1 + na
Bài 3:Một dãy số a0, a1, a2 , ... an, ... có tính chất sau : a0 = 0, an = 2an-1 + 3 với mọi n ³
1. Tìm nghiệm của công thức truy hồi trên.Viết thuật toán đệ quy tính số hạng tổng
quát an.
Bài 4:Một dãy a0 , a1, a2, ... an ... có tính chất sau: a0 = 0, a1 = 1, an = an-1+ an-2 với
mọi n ³ 2 được gọi là dãy Fibonacci.Tìm nghiệm của công thức truy hồi trên.Viết
thuật toán đệ quy tính số hạng tổng quát an.
Bài 5: Hãy tìm f(1), f(2) và f(3) nếu f(n) được định nghĩa bằng đệ quy với f(0)=1 và
với n=1,2,…
a. f(n)=3.f(n-1)
b. f(n)=f(n-1)2 + f(n-1) + 1
Bài 6: Hãy tìm f(2), f(3) và f(4) nếu f(n) được định nghĩa bằng đệ quy với f(0)= -1,
f(1)=2 và n=2,3,…
a. f(n)=f(n-1)+3f(n-2)
b. f(n)=3f(n-1)2 – 4f(n-2)2
c. f(n)=f(n-2)/f(n-1)
Bài 7:Hãy cho định nghĩa đệ quy của hàm F(n)=a trong đó a là một số thực và n là
một số nguyên dương. Viết thuật toán đệ quy tính a
Bài 8:Xét 2 tập có thứ tự E và F, trong đó thứ tự cho bởi :£ 1 trên cả 2 tập hợp. Hãy
xác định quan hệ ℜ sau đây. Xác định trên E x F có phải là quan hệ thứ tự không ?
ìx < x '
(x, y) ℜ (x’, y’) í
îhay(x = x ' vaìy £ y' )
Bài 9:
Cho F: E -> F và T là ánh xạ tương đương trên F. Người ta xác định quan hệ ℜ
trên E bởi x ℜ y óf (x) T f(y).
Chứng minh rằng ℜ cũng là quan hệ tương đương.
Hướng dẫn thực hiện bài tập mở rộng và nâng cao
Bài 1:
a. Dùng hằng đẳng thức a2+2ab+b2=(a+b)2
b. Dùng đẳng thức an.am=am+n
c. Dùng phương pháp đặt thừa số chung.
d. Dùng phương pháp đặt thừa số chung.
Bài 2:
Dùng đẳng thức am+n=am.an
Bài 3:
13
- Sử dụng phương trình đặc trưng cho công thức truy hồi tuyến tính bậc hai giải
tìm nghiệm số hạng tổng quát an. Dựa vào công thức truy hồi viết thuật toán đệ quy
tính an.
Bài 4:
Sử dụng phương trình đặc trưng cho công thức truy hồi tuyến tính bậc hai giải
tìm nghiệm số hạng tổng quát an. Dựa vào công thức truy hồi viết thuật toán đệ quy
tính an.
Bài 5:
Dựa vào giả thiết là giá trị đầu f(0)và hàm đã được định nghĩa đệ quy f(n) ta suy
ra được các giá trị tiếp theo f(1), f(2) và f(3).
Bài 6:
Dựa vào giả thiết là giá trị đầu f(0),f(1) và hàm đã được định nghĩa đệ quy f(n)
ta suy ra được các giá trị tiếp theo f(2), f(3) và f(4).
Bài 7:
Dùng đẳng thức a = a . Từ đó suy ra kết quả.
Bài 8:
Sử dụng định nghĩa: Quan hệ ℜ trong X gọi là quan hệ thứ tự (hay quan hệ bộ
phận) nếu có tính phản đối xứng và bắc cầu.
· Tính phản xạ : a ℜ a " a Î X (tức là (a, a) ∈ ℜ " a ∈ X )
· Tính đối xứng : a ℜ b Þ b ℜ a (tức nếu (a, b) ∈ ℜ thì (b, a) ∈ ℜ )
· Tính bắc cầu : (a ℜ b) và (b ℜ c) Þ a ℜ c
Bài 9:
Sử dụng định nghĩa: Quan hệ ℜ trong tập X gọi là quan hệ tương đương nếu nó
có tính phản xạ, đối xứng, bắc cầu.
14
- CHƯƠNG 2: TÍNH TOÁN VÀ XÁC SUẤT
Mã chương: MHLTV 11-02
Giới thiệu:
Mục tiêu:
- Liệt kê được các nguyên lý trong việc tính toán các xác suất;
- Mô tả chính xác các xác suất;
- Trả lời chính xác các bảng test trên giấy về nguyên lý cộng, nguyên lý nhân,
nguyên lý bù trừ, nguyên lý Dirichlet, sự kiện ngẫu nhiên;
- Xác định các xác suất trong bài toán cụ thể;
- Thực hiện các thao tác an toàn với máy tính.
Nội dung chính:
1. Tính toán
Mục tiêu:
- Liệt kê được các nguyên lý trong việc tính toán các xác suất;
- Mô tả chính xác các xác suất;
- Trả lời chính xác các bảng test trên giấy về nguyên lý cộng, nguyên lý nhân,
nguyên lý bù trừ, nguyên lý Dirichlet.
1.1. Nguyên lý cộng
Quy tắc 1:Giả sử có k công việc T1, T2, ..., Tk. Các việc này có thể làm tương
ứng bằng n1, n2, ..., nk cách và giả sử không có hai việc nào có thể làm đồng thời. Khi
đó số cách làm một trong k việc đó là n1+n2+ ... + nk..
Quy tắc 2:Nguyên lý cộng có thể phát biểu dưới dạng của ngôn ngữ tập hợp
như sau:
Nếu A và B là 2 tập hợp rời nhau (A∩B = ∅) thì N(A∪B) = N(A) + N(B).
Nguyên lý này có thể mở rộng như sau: Giả sử A1, A2, ... , An là các tập con
của một tập X nào đó thoả mãn:
· Các Ai đôi một rời nhau (Ai∩Aj = ∅, khi i ≠ j)
· X = A1∪A2∪ ... ∪An .
(Các tập A1, A2, …, An thoả mãn 2 tính chất trên được gọi là một phân hoạch
của tập X)
Khi đó: N(X) = N(A1) + N(A2) + ... + N(An)
Đặc biệt, ta có N(A)=N(X)–N(A) trong đó A là tập bù của tập A trong X.
Ví dụ 1.1:Một khoá học có 3 danh sách lựa chọn các bài thực hành: Danh sách thứ
nhất có 10 bài; danh sách thứ hai có 15 bài; danh sách thứ ba có 25 bài. Mỗi sinh viên
được chọn 1 bài trong 3 danh sách trên để làm thực hành. Hỏi mỗi sinh viên có bao
nhiêu cách lựa chọn bài thực hành.
Giải: Có 10 cách lựa chọn trong danh sách thứ nhất, 15 cách lựa chọn trong danh sách
thứ hai và 25 cách lựa chọn trong danh sách thứ ba. Vậy có 10 + 15 + 25 = 50 cách lựa
chọn cho mỗi sinh viên.
Ví dụ 1.2: Giá trị của biến m bằng bao nhiêu sau khi đoạn chương trình sau được thực
hiện?
m := 0
for i1 := 1 to n1
15
- m := m+1
for i2 :=1 to n2
m := m+1
.......................
for ik := 1 to nk
m := m+1
Giải:Giá trị khởi tạo của m bằng 0. Khối lệnh này gồm k vòng lặp khác nhau. Sau mỗi
bước lặp của từng vòng lặp giá trị của k được tăng lên một đơn vị. Gọi Ti là việc thi
hành vòng lặp thứ i. Có thể làm Ti bằng ni cách vì vòng lặp thứ i có ni bước lặp. Do
các vòng lặp không thể thực hiện đồng thời nên theo quy tắc cộng, giá trị cuối cùng
của m bằng số cách thực hiện một trong số các nhiệm vụ Ti, tức là m = n1+n2+ ... + nk.
Ví dụ 1.3:Một đoàn vận động viên của một địa phương được cử đi thi đấu ở 2 môn:
bắn súng và bắn cung. Trong đoàn có 10 nam và số vận động viên bắn súng là 14 (kể
cả nam và nữ). Số nữ vận động viên bắn cung bằng số nam vận động viên bắn súng.
Hỏi đoàncó bao nhiêu người?
Giải: Gọi A, B tương ứng là các tập vận động viên nam, vận động viên nữ, ta có
N(A) = 10
A1, A2 tương ứng là các tập vận động viên nam bắn súng, vận động viên nam
bắn cung, ta có N(A1) + N(A2) = 10
B1, B2 tương ứng là các tập vận động viên nữ bắn súng, vận động viên nữ
bắncung, ta có N(B2) = N(A1) và N(B1) + N(A1) = 14
Từ đó N(B1) + N(B2) = 14, nghĩa là đoàn có 14 vận động viên nữ. Vậy toàn
đoàn có 10 + 14 = 24 vận động viên.
Ví dụ 1.4: Xét đoạn chương trình phỏng Pascal sau:
k := 0;
for i1:= 1 to n1 do k := k + 1;
for i2:= 1 to n2 do k := k + 1;
for i3:= 1 to n3 do k := k + 1;
Hỏi sau khi thực hiện xong đoạn chương trình trên, giá trị của k bằng bao nhiêu?
Giải: Giá trị ban đầu gán cho k là 0. Khối lệnh gồm 3 vòng lặp tuần tự, sau mỗi bước
lặpcủa từng vòng lặp giá trị của k được tăng thêm 1, vòng lặp thứ i (i = 1, 2, 3) có ni
bước nênsau vòng lặp thứ i giá trị của k được tăng thêm ni. Do các vòng lặp là tuần tự
nên sau cả 3vòng lặp thì giá trị của k là: k = n1 + n2 + n3.
1.2. Nguyên lý nhân
Quy tắc 1:Giả sử một nhiệm vụ nào đó được tách ra thành k việc T1, T2, ...,Tk.
Nếu việc Ti có thể làm bằng ni cách sau khi các việc T1, T2, ... Ti-1 đã được làm, khi đó
có n1.n2....nk cách thi hành nhiệm vụ đã cho.
Quy tắc 2:Nguyên lý nhân có thể được phát biểu tổng quát bằng ngôn ngữ tập
hợp như sau:
Nếu A1, A2,.., Ak là những tập hợp hữu hạn, khi đó số phần tử của tích đề các
các tập này bằng tích số các phần tử của mỗi tập thành phần. Hay đẳng thức:
N(A1∩A2∩ …∩Ak) = N(A1). N(A2) … N(Ak)
Nếu A1 = A2 =… =Ak thì N(Ak) = N(A)k
Ví dụ1.5: Người ta có thể ghi nhãn cho những chiếc ghế trong một giảng đường bằng
một chữ cái và một số nguyên dương không vượt quá 100. Bằng cách như vậy, nhiều
nhất có bao nhiêu chiếc ghế có thể được ghi nhãn khác nhau?
16
- Giải:Thủ tục ghi nhãn cho một chiếc ghế gồm hai việc, gán một trong 26 chữ cái và
sau đó gán một trong 100 số nguyên dương. Quy tắc nhân chỉ ra rằng có 26.100=2600
cách khác nhau để gán nhãn cho một chiếc ghế.Như vậy nhiều nhất ta có thể gán nhãn
cho 2600 chiếc ghế.
Ví dụ 1.6: Có bao nhiêu xâu nhị phân có độ dài n.
Giải: Mỗi một trong n bit của xâu nhị phân có thể chọn bằng hai cách vì mỗi bit hoặc
bằng 0 hoặc bằng 1. Bởi vậy theo quy tắc nhân có tổng cộng 2n xâu nhị phân khác
nhau có độ dài bằng n.
Ví dụ 1.7: Có thể tạo được bao nhiêu ánh xạ từ tập A có m phần tử vào tập B có n
phần tử?
Giải: Theo định nghĩa, một ánh xạ xác định trên A có giá trị trên B là một phép tương
ứng mỗi phần tử của A với một phần tử nào đó của B. Rõ ràng sau khi đã chọn được
ảnh của i - 1 phần tử đầu, để chọn ảnh của phần tử thứ i của A ta có n cách. Vì vậy
theo quy tắc nhân, ta có n.n...n=nm ánh xạ xác định trên A nhận giá trị trên B.
Ví dụ 1.8: Giá trị của biến k bằng bao nhiêu sau khi chương trình sau được thực hiện?
m := 0
for i1 := 1 to n1
for i2 := 1 to n2
.......................
for ik := 1 to nk
k := k+1
Giải: Giá trị khởi tạo của k bằng 0. Ta có k vòng lặp được lồng nhau. Gọi Ti là việc
thi hành vòng lặp thứ i. Khi đó số lần đi qua vòng lặp bằng số cách làm các việc T1,
T2, ..., Tk. Số cách thực hiện việc Tj là nj (j=1, 2,..., k), vì vòng lặp thứ j được duyệt với
mỗi giá trị nguyên ij nằm giữa 1 và nj. Theo quy tắc nhân vòng lặp lồng nhau này được
duyệt qua n1.n2....nk lần.Vì vậy giá trị cuối cùng của k là n1.n2....nk.
1.3. Lý thuyết tổ hợp
a. Chỉnh hợp lặp
Định nghĩa 1.1:Một chỉnh hợp lặp chập k của n phần tử là một bộ có thứ tự
gồm k phần tử (thành phần) lấy từ n phần tử đã cho. Các phần tử (thành phần) có thể
được lặp lại.
Số các chỉnh hợp lặp chập k của n được ký kiệu là A và được tính theo công
thức:A = nk
Chứng minh: Vì có n cách chọn cho mỗi phần tử thứ i (i = 1, 2, ..., k); nên theo
quy tắc nhân được công thức cần chứng minh.
Chú ý:Do mỗi phần tử có thể được lấy nhiều lần nên có thể k > n.
Ví dụ 1.9: Cho tập hợp X = {1, 2, 3}. Hỏi có bao nhiêu cặp gồm 2 phần tử ?
Giải:Số cặp gồm 2 phần tử chính là số chỉnh hợp lặp chập 2 của 3 phần tử đã cho
trong tập X :A = 32 = 9
Ví dụ 1.10:Tính số các dãy nhị phân có độ dài n.
Giải:Mỗi dãy nhị phân có độ dài n là một bộ có thứ tự gồm n thành phần được chọn
trong tập {0, 1}. Do đó số dãy nhị phân có độ dài n là 2n.
Ví dụ 1.11:Có thể lập được 9.A = 9. 103 = 9000 số nguyên dương có 4 chữ số.
Ví dụ1.12:Trong ngôn ngữ Pascal chuẩn quy định tên biến không quá 8 ký tự (mỗi
kýtự là một trong 26 chữ cái tiếng Anh hoặc một trong 10 chữ số) và phải bắt đầu bằng
17
- một chữ cái, ký tự là chữ không phân biệt chữ hoa và chữ thường. Hỏi có thể định
nghĩa được bao nhiêu biến khác nhau?
Giải: Tất cả có 8 loại biến: 1 ký tự, 2 ký tự, ..., 8 ký tự. Theo quy tắc nhân thì số
biếncó k ký tự là 26.36k – 1, (k = 1, 2, ..., 8). Từ đó áp dụng quy tắc cộng được số các
biến khác nhau trong ngôn ngữ Pascal là:
26(1 + 36 + 362 + ... + 367) = 2 095 681 645 538 ≈ 2. 1012.
Đây là một con số rất lớn, không thể nào duyệt hết được chúng. Hiện tượng các
số tổhợp tăng như vậy gọi là hiện tượng bùng nổ tổ hợp.
Sốkýtự 1 2 3 4 5 6 7
Sốbiến 26 962 34 658 1 247 714 44 917 730 1 617 038 306 58 213 379 042
b. Chỉnh hợp không lặp
Định nghĩa 1.2:Một chỉnh hợp không lặp chập k của n phần tử là một bộ có thứ
tự gồm k thành phần lấy từ n phần tử đã cho (k≤n). Các phần tử không được lặp lại .
Số các chỉnh hợp chập k của n phần tử, ký hiệu là A , được tính theo công
!
thức:A =n(n-1)(n-2) . . . (n-k-1)=
( )!
Chứng minh: Vì có n phần tử đã cho nên có n cách chọn phần tử đứng đầu,
tiếp theo cón – 1 cách chọn phần tử đứng thứ hai, n – 2 phần tử đứng thứ ba, ..., n – k
+ 1 cách chọn phần tử thứ k. Theo nguyên lý nhân được công thức cần chứng minh.
Ví dụ 1.13: Cho tập hợp X = {a, b, c}. Hỏi có bao nhiêu cặp gồm 2 phần tử khác nhau
?
Giải :Số cặp gồm 2 phần tử khác nhau chính là số chỉnh hợp không lặp chập 2 của 3
phần tử đã cho trong tập X : A = 3(3 – 2) = 3
Ví dụ 1.14: Có 10 vận động viên thi chạy. Hỏi có bao nhiêu cách dự đoán các vận
động viên về nhất, nhì, ba?Biết rằng các vận động viên đều có cùng khả năng như
nhau.
Giải: Số cách dự đoán là số cách chọn có thứ tự 3 trong 10 vận động viên, tức là:
A = 10. 9. 8 = 720 cách dự đoán.
Ví dụ1.15: Có thể lập được 9A = 9.9.8.7 = 4536 số nguyên có 4 chữ số khác nhau.
Ví dụ 1.16: Có bao nhiêu đơn ánh từ tập hợp A có k phần tử vào tập hợp B có n phần
tử(k ≤ n)?
Giải: Giả sử các phần tử của tập hợp A tương ứng với các số 1, 2, ..., k; khi đó
mỗiđơn ánh chính là một bộ có thứ tự các ảnh của các phần tử của tập hợp A. Vậy
cóA các đơn ánh từ A vào B.
c. Hoán vị
Định nghĩa 1.3:Ta gọi một hoán vị của n phần tử là một cách xếp có thứ tự của
n phần tử đó.
Dễ nhận ra rằng, một hoán vị của n phần tử chính là một chỉnh hợp không lặp
(hay chỉnh hợp) chập n của n (k=n). Do đó số các hoán vị của n phần tử , ký hiệu Pn ,
là:
Pn=A =n(n-1)...1=n!
Ví dụ1.17: Có 4 sinh viên được ngồi trên một bàn. Hỏi có bao nhiêu cách xếp ?Giải
:Số cách xếp 4 sinh viên ngồi trên một bàn là :
P4 = 4! = 1.2.3.4 = 24
18
- Ví dụ1.18: Một người phải đi kiểm tra 8 địa điểm khác nhau theo bất kỳ thứ tự nào.
Hỏi người đó có bao nhiêu cách đi nếu bắt đầu từ một trong 8 địa điểm đó sao cho mỗi
địa điểm đều được kiểm tra đúng một lần.
Giải: Người đó có P7 = 7! = 5040 cách đi.
d. Tổ hợp
Định nghĩa 1.4:Một tổ hợp chập k của n phần tử là một bộ không kể thứ tự
gồm k thành phần khác nhau lấy từ n phần tử đã cho (n≥k). Nói cách khác, ta có thể
coi một tổ hợp chập k của n phần tử là một tập con k phần tử của nó.
Số các tổ hợp chập k của n phần tử , ký hiệu là C , được tính như sau:
!
C =
!( )!
Chứng minh:Xét tập hợp tất cả các chỉnh hợp không lặp chập k của n phần tử.
Chia chúng thành những lớp sao cho hai chỉnh hợp thuộc cùng một lớp chỉ khác nhau
về thứ tự. Rõ ràng các lớp này là một phân hoạch trên một tập đang xét và mỗi lớp như
thế là tưong ứng với một tổ hợp chập k của n. Số chỉnh hợp trong mỗi lớp là bằng nhau
và bằng k! (số hoán vị). Số các lớp là bằng số tổ hợp chập k của n. Theo nguyên lý
cộng, tích của k! với số này là bằng số các chỉnh hợp không lặp chập k của n, nghĩa là
bằng n(n – 1)(n – 2) …(n – k + 1). Từ đó nhận được số tổ hợp chập của n.
A n!
A = k! C ⟹ C = =
k! k! (n − k)!
Ví dụ 1.19: Có 6 đội bóng thi đấu vòng tròn một lượt. Hỏi phải tổ chức bao nhiêu trận
đấu?
Giải: Cứ 2 đội gặp nhau một trận suy ra số trận đấu làC = 15 trận
Ví dụ 2:Tính số giao điểm của các đường chéo nằm phía trong một đa giác lồi n
cạnh(n ≥ 4). Biết rằng không có 3 đường chéo nào đồng quy tại 1 điểm ở phía trong
đa giác đó.
Giải: Cứ 4 đỉnh của đa giác cho ta một giao điểm thoả mãn bài toán. Vậy số điểm
cầnđếm là:
n(n − 1)(n − 2)(n − 3)
C =
24
Ví dụ1.20: Cho một lưới có m.n ô chữ nhật. Các nút được đánh số từ 0 đến n theo
chiều từ trái sang phải và từ 0 đến m theo chiều từ dưới lên trên (xem hình vẽ). Hỏi có
bao nhiêu đường đi khác nhau từ nút (0,0) đến nút (n,m), biết rằng mọi bước
đi là sự dịch chuyển hoặc sang phải hoặc lên trên của một ô hình chữ nhật (không dịch
chuyển sang trái hoặc xuống dưới).
(0,m) (n,m)
(0,0) (n,0)
Giải: Một đường đi như vậy được xem là gồm n+m bước, mỗi bước chỉ được
chọn một trong hai giá trị là 0 nếu đi lên và 1 nếu đi sang phải. Như vậy mỗi đường đi
tương ứng với một dãy nhị phân có độ dài m+n trong đó có đúng m giá trị 1 (và tất
nhiên có đúng n giá trị 0).
19
nguon tai.lieu . vn
