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ệ

Chia sẻ: Ca Phe Sua | Ngày: | Loại File: PDF | Số trang:72

Thêm vào BST

Báo xấu

31
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

(NB) Giáo trình Cơ sở toán cho tin học cung cấp cho người học những kiến thức như: Quan hệ - Suy luận toán học; tính toán và xác suất; ma trận và thuật toán; phương pháp tính. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ệ

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