Giáo trình Cơ sở toán cho tin học - Trình độ: Cao đẳng - Trường Cao đẳng nghề kỹ thuật công nghệ

Nội dung text: Giáo trình Cơ sở toán cho tin học - Trình độ: Cao đẳng - Trường Cao đẳng nghề kỹ thuật công nghệ

1. 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ộ)
2. 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
3. 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
4. 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
5. 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
6. 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
7. 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 ∈ℜ ∈
8. - 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
9. 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 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
10. 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
11. Đị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
12. 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
13. 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
14. 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. b. 1 + 2 + 22 + + 2n = 2n+1 -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ínha 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 í î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
15. 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
16. 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
17. 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) k k Nếu A1 = A2 = =Ak thì N(A ) = N(A) 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
18. 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 k thức:A = n 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
19. 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
20. 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
21. Bài toán dẫn đến việc tìm xem có bao nhiêu dãy nhị phân có độ dài m+n trong đó có đúng m thành phần 1.Nói cách khác là số cách chọn m vị trí trong m+n vị trí để xếp số 1. Vậy số đường đi sẽ là C (hoặc C ) Ví dụ 1.21: Xét đoạn chương trình phỏng Pascal sau: for i := 1 to n – 1 do for j := i + 1 to n do if ai> aj then begin {đổi chỗ ai, aj } t : = ai ; ai := aj ; aj := t ; end; Đây là một trong các thuật toán để xếp dãy số a1, a2, , an theo thứ tự tăng dần. Hãy đếm số phép so sánh các ai được thực hiện trong đoạn chương trình trên. Giải: Tại mỗi vòng lặp i = k thì vòng lặp j phải thực hiện n – k + 1 bước. Nghĩa là với mỗi i = k phải thực hiện n – k +1 phép so sánh (k = 2, 3, , n). Từ đó theo nguyên lýcộng, số các phép so sánh là: ( ) (n+1) + (n+2) + . . .+1= Cũng có thể giải như sau: Vì mọi cặp ai, aj (i j) đều phải so sánh với nhau, do đótổng các phép so sánh là C . 1.4. Nguyên lý bù trừ ≠ Một số bài toán đếm ph ức tạp , được dựa vào nguyên lý tổng quát của nguyên lý cộng. Nếu không có giả thiết gì về sự rời nhau giữa 2 tập A và B thì N(A  B) = N(A) + N(B) – N(A Ç B). (1.1) Công thức (1) được mở rông cho trường hợp nhiều tập như sau : Định lý:Giả sử A1, A2, , Am là các tập hữu hạn. Khi đó m-1 N(A1  A2  Am) = N1 – N2 + + (-1) Nm (1.2) Trong đó Nk là tổng phần tử của tất cả các giao của k tập lấy từ m tập đã cho (nói riêng N1 = N(A1) + + N(Am), Nm = N(A1 Ç A2 Ç Ç Am) ) Bây giờ ta đồng nhất tập Ak với tính chất Ak cho trên một tập X nào đó và đếm xem có bao nhiêu phần tử của X không thoả mãn bất cứ một tính chất Ak nào cả. Gọi N là số cần đếm, N là số phần tử của X, ta có : m N = N – N(A1  A2  Am) = N – N1 + N2 - + (-1) Nm(1.3) Trong đó Nk là tổng các phần tử của X thoả mãn k tính chất lấy tử m tính chất đa cho. Công thức (1.3) được gọi là nguyên lý bù trừ.Nó cho phép tính N qua các Nk trong trường hợp các số này dễ tính toán hơn. Ví dụ 1.22:Hỏi có bao nhiêu xâu nhị phân độ dài 10 hoặc bắt đầu bởi 00 hoặc kết thúc bởi 11 ? Giải: Dễ thấy là số xâu nhị phân độ dài 10 bắt đầu bởi 00 là 28 = 256 và số xâu nhị phân độ dài 10 kết thúc bởi 11 là 28 = 256. Ngoài ra, số xâu nhị phân độ dài 10 bắt đầu bởi 00 và kết thúc bởi 11 là 26 = 64.theo công thức (2.7) suy ra số xâu nhị phân hoặc bắt đầu bởi 00 hoặc kết thúc bởi 11 là 256 + 256 -64 = 448 Ví dụ1.23:Hỏi trong tập X = {1, 2, , 10000} có bao nhiêu số không chia hết cho bất cứ số nào trong các số sau : 3, 4, 7 ? Giải: Gọi Ai = { x X : x chia hết cho i }, i = 3, 4, 7. 20
22. Khi đó A3  A4  A7 là tập các số trong X chia hết cho ít nhất một trong 3 số 3, 4, 7. Suy ra theo công thức (2.9), số lượng các số cần đếm sẽ là N(X) – N(A3  A4  A7 ) = N1 – N2 + N3 Ta có : N1 = N(A3) + N(A4) + N(A7) = (10000/3) + (10000/4) + (10000/7) = 3333 + 2500 + 1428 = 7261 N2 = N(A3 Ç A4 ) + N(A3 Ç A7) + N(A4 Ç A7) = [10000/(3↔ 4)] + [10000/(3↔ 7)] + [10000/(4↔ 7)] = 833 + 476 + 357 = 1666 N3 = N(A3 Ç A4 Ç A7) = [10000/(3↔ 4↔ 7)] = 119. ở đây ký hiệu [r] để chỉ số nguyên lớn nhất không vượt quá r. Từ đó số lượng các số cần đếm là 10000 – 7261 + 1666 – 119 =4286. 1.5. Nguyên lý Dirichlet Trong rất nhiều bài toán tổ hợp, để chứng minh sự tồn tại của một cấu hình với những tính chất cho trước, người ta sử dụng nguyên lý đơn giản sau, gọi là nguyên lý Dirichlet: Nguyên lý Dirichlet: Nếu đem xếp nhiều hơn n đối tượng vào n cái hộp, thì luôn tìm được một cái hộp chứa không ít hơn 2 đối tượng. Chứng minh: Việc chứng minh nguyên lý trên chỉ là một lập luận phản chứng đơn giản. Giả sử ngược lại là không tìm thấy các hộp nào chứa không ít hơn 2 đối tượng.Điều đó có nghĩa là mỗi cái hộp chứa không quá 1 đối tượng.Từ đó suy ra tổng số đối tượng xếp trong n cái hộp là không vượt quá n, trái với giả thiết là có nhiều hơn n đối được xếp trong chúng. Lập luận tương tự, có thể chứng minh nguyên lý Dirichlet tổng quát sau: Nguyên lý Dirichlet tổng quát: Nếu đem xếp n đối tượng vào k cái hộp, thì luôn tìm được một cái hộp chứa không ít hơn n/k đối tượng. Ví dụ 1.24: Trong số 367 người bao giờ cũng tìm được hai người có ngày sinh nhật giống nhau bởi vì chỉ có tất cả 366 ngày sinh nhật khác nhau. Ví dụ 1.25: Trong 100 người có ít nhất 9 người sinh cùng một tháng. Giải: Xếp những người sinh cùng một tháng vào một nhóm. Có 12 tháng tất cả. Vậy theo nguyên lý Dirchlet, tồn tại ít nhất một nhóm có không ít hơn 100/12 = 8.3 nghĩa là 9 người. 2. Xác suất Mục tiêu: - Mô tả chính xác sự kiện ngẫu nhiên, không gian mẫu và các định lý xác suất; - Xác định các xác suấttrong bài toán cụ thể. 2.1. Sự kiện ngẫu nhiên Trong thế giới xung quanh, ta luôn gặp các hiện tượng ngẫu nhiên : nhiệt độ, độ âm trong ngày, kết quả cảu một cuộc quay xổ số, kết quả của việc gieo một con súc sắc hay tung một đồng tiền, dân số của một thành phố, số người sinh, chết, số người gọi điện thoại ở một trạm điện thoại trong một ngày song các hiện tượng ngẫu nhiên đó đều có tính quy luật. a. Phép thử và sự kiện. Không gian gốc Các khái niệm được gặp đầu tiên trong lý thuyết xác suất là “phép thử” và “sự kiện”. 21
23. Danh từ “phép thử” được hiểu là thực hiện một bộ điều kiện xác định, nó có thể là một thí nghiệm cụ thể hay việc quan sát sự xuất hiện một hiện tượng nào đó. Một phép thử có thể có nhiều kết cục khác nhau, các kết cục nay được gọi là các “sự kiện”. Sự kiện được ký hiệu bởi các chữ in A, B, C đôi khi có kèm theo chỉ số. Một phép thử được gọi là ngẫu nhiên nếu không thể biết trước các kết cục của nó, lúc này mỗi kết cục là một sự kiện ngẫu nhiên.Tập hợp ∑ tất cả các sự kiện ngẫu nhiên có thể của một phép thử ngẫu nhiên được gọi là không gian gốc. Ví dụ 2.1: Việc tung một đồng tiền là một phép thử ngẫu nhiên. Không gian gốc ∑ = {sấp, ngửa}= {0, 1}, sấp = 0, ngửa = 1. Ví dụ 2.2: Việc gieo một con súc sắc là một phép thử ngẫu nhiên. Không gian gốc ∑ = {1, 2, 3, 4, 5, 6} = {ω 1, ω 2, ω 3, ω 4, ω 5, ω 6 } Một kết cục được gọi là một điểm của không gian gốc.Nó có thể biểu diễn một cách thuận tiện bằng đồ thị nếu diều đó cho phép. Ví dụ 2.3: Ta tung đồng tiền 2 lần. Không gian gốc có thể được biểu diễn bởi các điểm : ∑ = {(sấp, sấp), (sấp, ngửa), (ngửa, sấp), (ngửa, ngửa)} (sấp, sấp) = (0, 0) (sấp, ngửa) = (0, 1) (ngửa, sấp) = (1, 0) (ngửa, ngửa) = (1, 1) 〈 Nếu không gian gốc bao gồm một số hữu hạn điểm như trong các ví dụ trên thì nó được gọi là không gian gốc hữu hạn. 〈 Nếu nó gồm một số điểm như tập các số tự nhiên thì nó được gọi là không gian gốc vô hạn đếm được. 〈 Nếu nó gồm một số điểm như trong như khoảng nào đó thì nó được gọi là không gian vô hạn không đếm được - Một số không gian gốc hữu hạn hay vô hạn đếm được gọi là rời rạc. - Một số không gian gốc vô hạn không đếm đựơc gọi là liên tục. Sự kiện ngẫu nhiên có thể coi là một tập con A của không gian gốc ∑ Ví dụ 2.4: Trong trường hợp tung 2 lần một đông tiền, một sự kiện bao gồm nhận được chỉ một mặt sấp là tập con A = { ( sấp, ngửa), (ngủa, sấp)} = {(0,1), (1, 0)} Ký hiệu card A là lực lượng của A (số phần tử của A). 〈 Nếu card A = 1 ta gọi A là một sự kiện cơ bản. 〈 Nếu A ∑ thì A được gọi là sự kiện chắc chắn hay tất yếu ( nhất thiết xảy ra khi phép thử được thực hiện) 〈 Nếu A = Ø thì A được gọi là sự kiện không thể (nhất thiết không xảy ra khi phép thử thực hiện) b. Các quan hệ và phép toán trên sự kiện (đại số sự kiện) Trong việc coi mỗi sự kiện là một tập hợp, tất cả các mệnh đề liên quan tới các sự kiện có thể phát biểu theo ngôn ngữ của lý thuyết các tập hợp và ngược lại. Giả sử A và B là các sự kiện, khi đó : 1. A  B là sự kiện A hoặc B 2. A Ç B là sự kiện đồng thời A và B 3. A – B là sự kiện A mà không B 4. Nếu A Ç B = Ø thì ta nói A và B là các sự kiện sung khắc với nhau. 22
24. 5. Hai sự kiện A và A đối lập nhau khi và chỉ khi nếu A xảy ra thì A không xảy ra và nếu A xảy ra thì A nhất định không xảy ra. Ø Chú ý : Hai sự kiện đối lập nhau thì nhất thiết sung khắc và tổng của chúng là sự kiện tất yếu. A  A = ∑ 6. Giả sử khi phép thử được thực hiện, ta có thể có một nhóm các sự kiện A1, A2, , An có 2 tính chất sau : a) Ai Ç Aj = Ø (i ¹ j) n ∑ b) Υ Ai = i=1 Khi đó ta nói các sự kiện A 1, A2, , An tạo nên một nhóm đầy đủ các sự kiện (trong lý thuyết tập hợp ta có một phân hoạch) Ví dụ 2.5: Trong trường hợp tung 2 lần một đồng tiền, giả sử ta gọi : A là sự kiện “có ít nhất một mặc sấp” B là sự kiện “ngữa ở lần tung thứ hai” C là sự kiện “cả hai lần đều sấp” Ta có : A = {SN, NS, SS}, B = {SN, NN}, C = {SS} Khi đó : A  B = {SN, NS, SS, NN} = R A Ç B = {SN} , B Ç C = Ø Þ B và C là hai sự kiện sung khắc A – B = {NS, SS}. 2.2. Các định nghĩa xác suất a. Định nghĩa cổ điển và cách tính Định nghĩa 2.1: Giả sử có một phép thử có tất cả n kết cục đồng khả năng, trong đó m kết cục thích hợp cho sự kiện A. Khi đó, xác suất của A là tỉ số kết cục thích hợp cho A trên số kết cục đồng khả năng của phép thử. m P(A) = (2.1) n (m : là số kết cục thích hợp cho A, n : là số kết cục đồng khả năng) Ví dụ 2.1: Trong một thùng kín đựng n quả cầu giống nhau về mọi mặt và chỉ khác nhau về màu sắc; trong đó có m quả cầu trắng và n – m quả cầu đen. Thực hiện thép thử : rút ngẫu nhiên 1 quả . Thử quả xác suất rút được quả trắng là bao nhiêu ? Vì thùng có m quả cầu nên phép thử có thể kết thúc bởi một trong n kết cục khác nhau : rút được quả số 1, quả số 2, , quả số n. Do tính đối xứng hoàn toàn của các quả cầu nên mỗi quả đều có cùng khả năng được rút như nhau. Nếu gọi A là sự kiện rút được quả cầu có màu trắng thì ta thấy trong số n kết cục đồng khẳnng của m phép thử có m kết cục thích hợp cho A. Vì vậy, tự nhiên ta lấy tỷ số là xác suất của n sự kiện A. Từ công thức (1) dễ dàng suy ra các tính chất của P(A) : 1. Nếu A là sự kiện tất yếu thì mọi kết cục đồng khả năng của phép thử đều n thích hợp cho A nên m = n, do đó P(A) = = 1. n 2. Nếu A là sự kiện không thể thì không có kết cục nà thích hợp cho A nên m 0 = 0, do đó P(A) = = 0 n 23
25. m 3. Nếu A là sự kiện bất kỳ thì do 0 ≤ m ≤ n nên 0 ≤P(A) = ≤ 1. n b. Định nghĩa thống kê của xác suất Định nghĩa cổ diển của sác xuất có hạn chế là dòi hỏi phép thử phải có một số hữu hạn kết cục đồng khả năng. Vì vậy, người ta đưa vào định nghĩa sác xuất theo quan điểm thống kê. Tần suất của sự kiện A trong loạt phép thử là tỷ số giữa số các phép thử mà A xảy ra trên tổng số phép thử tiến hành, ký hiệu : M W(A) = N Trị số của tần suất nói chung phụ thuộc vào số lượng phép thử tiến hành N. Khi N bé, tần suất thay đổi rỏ rệt nếu ta chuyển từ loạt N phép thử này sang loạt N phép thử khác. Tuy nhiên, thực nghiệm (và sau này được chứng minh ở luật số lớn Becnuly) chứng tỏ rằng khi số phép thử N khá lớn thì trị số của tần suất biến thiên rất ít xung quanh một hằng số nào đó. Định nghĩa 2.2:Xác suất của sự kiện là trị số ổn định của tần suất khi số phép thử tăng lên vô hạn. Đó là định nghĩa thống kê của sác xuất.Tính ổn định của tần suất khi số phép thử đủ lớn được chứng minh bằng nhiều thí nghiệm công phu. 2.3. Các định lý về xác suất 2.3.1. Định lý cộng xác suất Định lý 2.1: Giả sử A và B là 2 biến cố liên kết với cùng 1 phép thử và xung khắc lẫn nhau khi đó ta có : P(A B)=P(A)+P(B) Ví dụ 2.2: Một hộp có 6 bi đỏ và 4 bi xanh hoàn toàn giống nhau về kích thước và trọng lượng. Ta lấy ngẫu nhiên∪ 2 bi. Tìm xác suất để 2 bi lấy ra cùng màu. Bài giải : Gọi A là biến cố 2 bi lấy ra đều bi xanh Gọi B là biến cố 2 bi lấy ra đều bi đỏ Gọi C là biến cố 2 bi lấy ra đều bi cùng màu Khi đó C= A B và A,B xung khắc nên P(C)=P(A B)=P(A)+P(B) Ta có: P(A)= = = ∪ ∪ P(B)== = P(C)=+ = Ví dụ 2.3: Có 30 đề thi trong đó có 10 đề khó, 20 đề trung bình. Tìm xác suất để: a. Một Sinh viên bắt một đề gặp được đề trung bình. b. Một Sinh viên bắt hai đề, được ít nhất một đề trung bình. Giải a. Gọi A là biến cố Sinh viên bắt được đề trung bình: 1 C20 202 P(A) =1 == C30 303 b. Gọi B là biến cố sinh viên bắt được 1 đề trung bình và một đề khó Gọi C là biến cố sinh viên bắt được 2 đề trung bình. Gọi D là biến cố sinh viên bắt hai đề, được ít nhất một đề trung bình. 24
26. 112 C20 .C 10++ C 20 200 190 Khi đó: P(D)=2 == 0,896 C30 435 Định lý 2.2:Định lý cộng mở rộng Nếu A, B là 2 sự kiện bất kỳ liên kết với cùng một 1 thử thì: P(A B)=P(A)+P(B)-P(A B) Ví dụ 2.4: Có hai lớp 10A và 10 B mỗi lớp có 45 sinh viên, số sinh viên giỏi văn và số sinh viên∪ giỏi toán được cho∩ trong bảng sau. Có một đoàn thanh tra.Hiệu trưởng nên mời vào lớp nào để khả năng gặp được một em giỏi ít nhất một môn là cao nhất? Lớp 10A 10B Giỏi Văn 25 25 Toán 30 30 Văn và Toán 20 10 Giải: Gọi V là biến cố sinh viên giỏi Văn, T là biến cố sinh viên giỏi Toán. Ta có: Lớp 10A 25 30 20 7 P(V+= T) P(V) + P(T) − P(VT) =+−= 45 45 45 9 Lớp 10B: 25 30 10 P(V+= T) P(V) + P(T) − P(VT) =+−= 1 45 45 45 Vậy nên chọn lớp 10B. 2.3.2. Xác xuất có điều kiện a. Khái niệm về xác suất có điều kiện, khái niệm độc lập Định nghĩa:Xác suất của sự kiện A được tính với giả thiết sự kiện B đã xảy ra gọi là xác suất có điều kiện của A với điều kiện B, ký hiệu : P(A/B) hoặc PB(A) Ví dụ2.5: 5 người rút thăm, trong đó có 2 vé xem đá bóng. Trước lúc bắt thăm, xác suất rút đuợc vé của anh A (cũng như của anh B) là 2 P(A) = . Nếu cho biết thêm điều kiện trước đó B đã rút được một vé thì xác suất để 5 1 A rút được vé là . Rõ ràng sự xuất hiện B (anh B rút được vé) đã thay đổi khả năng 4 rút vé của anh A. Trường hợp riêng : khi P(A/B) = P(A) tức là việc xuất hiện sự kiện B không ảnh hưởng gì đến khả năng xuất hiện sự kiện A thì ta nói A độc lập với B. Trường hợp trái lại, khi P(A/B) ¹ P(A) ta nói sự kiện A phụ thộc sự kiện B. b. Định lý nhân xác suất Định lý2.3: Xác suất của tích hai sự kiện bằng tích xác suất của một trong chúng nhân với xác suất có điều kiện của sự kiện kia với giả thiết sự kiện thứ nhất đã xảy ra : P(A Ç B) = P(A)P(B/A) = P(B). P(A/B) 25
27. Ví dụ 2.6: Một lớp học có 70 em, trong đó có 40 em nữ. Trong lớp có 32 em giỏi An văn - có 20 nữ và 12 nam. Giáo viên mở sổ điểm danh gọi một sinh viên bất kỳ.Tìm xác suất để sinh viên được gọi là một em nữ giỏi Anh văn. Giải : Gọi A là biến cóo gọi đúng một em giỏi Anh văn. B là biến cố gọi một em nữ. Như vậy ta cần tính P(A.B). 40 Nhưng trước hết ta có thông tin em được gọi là em với xác suất P(B) = và 70 20 sau đó xác suất P(A/B) của biến cố em nữ đó giỏi Anh văn : P(A/B) = . Vì vậy : 40 40 20 20 2 P(A Ç B) = P()(B . P A / B)= . = = 70 40 70 7 Định lý 2.4:Định lý nhân mở rộng P(A1A2A3)=P(A1).P(A2/A1)P(A3/A1A2) Ví dụ 2.7: Trong một hộp có 12 bóng đèn, trong đó có 3 bóng hỏng.Lấy ngẫu nhiên không hoàn lại ba bóng để dùng. Tính xác suất để: a) Cả ba bóng đều hỏng. b) Cả ba bóng đều không hỏng? c) Có ít nhất một bóng không hỏng? d) Chỉ có bóng thứ hai hỏng? Giải Gọi F là biến cố mà xác suất cần tìm và Ai là biến cố bóng thứ i hỏng 3211 a) P(F)= P( AAA) = P( A )( P A /A) P( A /AA) == . . 123 1 2 1 3 12 12 11 10 220 987 21 b) P(F)PA.A.A= = PA PA/APA/AA == . . ( 1 2 3) () 1( 2 1)( 3 12)12 11 10 55 1 219 c) P(F)1PAAA1=−( ) =−= 123 220 220 9389 d) P(F)PA.A.A= = PA PA/APA/AA == . . ( 1 2 3) () 1( 2 1)( 3 12)12 11 10 55 Hệ quả 2.1: Nếu A độc lập với B thì B độc lập với A. Chứng minh : Theo giả thiết P(A/B) = P(A) Vì vậy, ta có : P(A Ç B) = P(B) .P(A) = P(A) . P(B/A) Suy ra P(B) = P(B/A) tức là B độc lập với A. Hệ quả 2.2: Xác suất của tích 2 sự kiện độc lập bằng tích các xác suất của chúng. Thật vậy: P(A Ç B) = P(A) . P(B/A) = P(A) . P(B) = P(B) . P(A/B) = P(B) . P(A) c. Công thức xác suất toàn phần và công thức Bayes Giả sử A1, A2, , An là một nhóm đầy đủ các sự kiện xung khắc và B là một sự kiện nào đó (trong cùng một phép thử). * Cho biết xác suất P(Ai) và P(B/Ai) ; i = 1,2, , n. Hãy tính xác suất của B? Theo giả thiết, rõ ràng ta có : B = A1Ç B + A2Ç B + AnÇ B 26
28. Vì các sự kiện Ai xung khắc, nên các sự kiện AcÇB cũng sung khắc, theo định lý 8: n P()B=åP(AiÇB) i=1 Hơn nữa, theo định lý nhân xác xuất. P(AiÇB)=P(Ai)P(B/Ai) Do vậy : n P()B=åP(Ai )(PB/Ai) i=1 Đây là công thức xác suất toàn phần. Ví dụ 2.8: Một nhà máy sản xuất bóng đèn gồm 3 phân xuởng : phân xưởng 1 sản xuất 50% tổng số bóng đền của toàn nhà máy, phân xưởng 2 sản xuất 20%, phân xưởng 3 sản xuất 30%. Tỷ lệ phế phẩm tương ứng của các phân xưởng là 2%, 3% và 4%. Hãy tính tỷ lệ phế phẩm chung của toàn nhà máy. Giải : Tỷ lệ phế phẩm cần tìm chính là xác suất để một bóng đèn chọn ngẫu nhiên từ ho sản phẩm của nhà máy là phế phẩm. Gọi Ai (i = 1, 2, 3) là sự kiện bóng đèn chọn ra thuộc phân xưởng i = 1,2, 3. Gọi B là sự kiện bóng đèn chọn ra là phế phẩm. P (A1) = 0,5 ; P (A2) = 0,2 ; P (A3) = 0,3 P (B/A1) = 0,02 ; P (B/A2) = 0,03 ; P (B/A3) = 0,04 Do đó : P (B) = P (A1). P (B/A1) +P (A2).P (B/A2) +P (A3). P (B/A3) = 0,5.0,02 + 0,2.0,03+0,3.0,04 = 0,028 = 2,8% * Bây giờ giả sử phép thử được thực hiện và kết quả là sự kiện B xảy ra. Vì các Ai (i = 1, 2, ,n) họp thành nhóm đầy đủ nên cùng với B phải có một sự kiện Ai nào đó xảy ra (và chỉ một). Hãy tính các xác suất có điều kiện P(Ai/B) (i = 1, , n). ? Theo quy tắc nhân xác suất ta có : P(B).P(Ai/B) = P(Ai).P(Bi/AI) P(A ).P(B/A ) Suy ra : P(A /B) = i i i P(B) Thay P (B) bởi công thức toàn phần ta được : P(Ai ).P(B/Ai ) P(Ai /B) = n å P(A i )P(B / A i ) i =1 Đó là công thúc Bayes. Ví dụ : Một thiết bị gồm 3 loại linh kiện : - Loại 1 chiếm 35% tổng số các linh kiện - Loại 2 chiếm 25% - Loại 3 chiếm 40% Cho biết xác suất hỏng (tại thời điểm đang xét) của linh kiện loại 1 là 15%, loại 2 là 25%, loại 3 là 5%. Máy hiện bị hỏng (sự kiện B đã xảy ra). Tính xem loại linh kiện nào có xác suất hỏng lớn nhất (để kiểm tra và xử lý trước) ? Giải : Gọi Ai là sự kiện linh kiện loại i bị hỏng, i = 1, 2, 3. Theo công thức Bayes ta có : 27
29. 35 15 . 525 525 P(A / B) = 100 100 = = = 0,389 1 35 15 25 25 40 5 525+ 625+ 200 1350 . + . + . 100 100 100 100 100 100 625 Tương tự : P(A /B) = = 0,463 2 1350 200 P(A /B) = = 0,148 3 1350 Vậy linh kiện loại 2 có xác suất hỏng lớn nhất nên kiểm tra trước. 28
30. Bài tập chương 2 của học sinh, sinh viên Bài 1 : Gieo một con súc sắc đối xứng và đồng chất. Tìm xác suất để được : a) Mặt sáu chấm xuất hiện b) Mặt có số chẵn chấm xuất hiện Bài 2 : Thang máy của một toà nhà 7 tầng xuất phát từ tầng một 3 khách . Tìm xác suất để : a) Tất cả cùng ra ở tầng 4 b) Tất cả cùng ra ở một tầng c) Mỗi người ra ở một tầng khác nhau Bài 3 : Cơ cấu chất lượng sản phẩm của 1 nhà máy như sau : Sản phẩm loại 1 : 40%, sản phẩm loại 2 : 50%, còn lại là phế phẩm. Lấy ngẫu nhiên 1 sản phẩm của nhà máy. Tính xác suất sản phẩm lấy ra thuộc loại 1 hoặc loại 2. Bài 4 : Hai người cùng bán vào mục tiêu. Khả năng bắn trúng của từng người là 0,8 và 0,9. Tìm xác suất : a) Chỉ có 1 người bắn trúng mục tiêu b) Có người bắn trúng mục tiêu c) Cả 2 người bắn trượt Bài 5 : Xác suất để bắn một viên đạn trúng đích là 0,8. Hỏi phải bắn bao nhiêu viên đạn để với xác suất nhỏ hơn 0,4 có thể hy vọng rằng không có viên nào trượt. Bài 6 : Có 30 sản phẩm, trong đó có 3 phế phẩm được bỏ ngẫu nhiên vào 3 hộp với số lượng bằng nhau. Tìm xác suất để 1 hộp nào đó có 1 phế phẩm. Bài 7 :Có bao nhiêu số nguyên dương nhỏ hơn hoặc bằng 1000 không chia hết cho bất của số nào trong các số 3,4,5 ? Bài 8 : Có bao nhiêu xâu nhị phân độ dài 10 hoặc là bắt đầu bởi 00 hoặc là kết thúc bởi 11 ? Bài 9 : Có năm loại học bổng khá nhau. Hỏi rằng phải có ít nhất bao nhiêu sinh viên để chắc chắn rằng có ít ra là 6 người cùng nhận học bổng như nhau ? Bài 10 : Biển số xe máy gồm 7 ký tự : NN- NNN - XX Trong đó 2 ký tự đầu là mã số địa danh, 3 ký tự tiếp theo là số hiệu xe, mỗi ký tự là 1 số từ 0 đến 9, hai ký tự cuối là mã đăng ký gồm 2 chũ cái lấy trong bảng chữ cái la tinh gồm 26 chữ cái. Hỏi rằng, để có 2 triệu biển số xe máy khá nhau thì cần phải có ít nhất bao nhiêu mã địa danh khác nhau ? Hướng dẫn thực hiện bài tập mở rộng và nâng cao Bài 1: Gọi các biến cố theo yêu cầu. Sau đó tính xác suất của biến cốcâu a và câu b dựa vào định nghĩa xác suất. Bài 2: Gọi các biến cố theo yêu cầu. Sử dụng định nghĩa xác suất tính xác suất củabiến cốcâu a, câu b và câu c. Bài 3: Để tính xác suất sản phầm lấy ra thuộc loại 1 hoặc loại 2 ta dựa vào định lý cộng xác suất. Bài 4: Gọi các biến cố theo yêu cầu. Tính xác suất của biến cố câu a, câu b và câu cdựa vào định lý cộng xác suất và độc lập các biến cố. 29
31. Bài 5: Gọi các biến cố theo yêu cầu. Tính xác suất của biến cố dựa vào phép nhân các biến cố độc lập. Bài 6: Gọi các biến cố theo yêu cầu. Tính xác suất của biến cố dựa vào định lý cộng xác suất mở rộng và định lý nhân xác suất. Bài 7: Sử dụng nguyên lý bù trừ để giải bài toán theo yêu cầu. Bài 8: Sử dụng nguyên lý bù trừ để giải bài toán theo yêu cầu. Bài 9: Sử dụng nguyên lý Dirichlet để giải bài toán theo yêu cầu. Bài 10: Sử dụng nguyên lý Dirichlet để giải bài toán theo yêu cầu. 30
32. CHƯƠNG 3: MA TRẬN VÀ THUẬT TOÁN Mã chương: MH11-03 Giới thiệu: Ma trận và các phép toán liên quan tới nó là một phần rất quan trọng trong hầu hết mọi thuật toán liên quan đến số học. Khi thiết kế và cài đặt một phần mềm tin học cho một vấn đề nào đó, ta cần phải đưa ra phương pháp giải quyết mà thực chất đó là thuật toán giải quyết vấn đề này. Rõ ràng rằng, nếu không tìm được một phương pháp giải quyết thì không thể lập trình được. Chính vì thế, thuật toán là khái niệm nền tảng của hầu hết các lĩnh vực của tin học. Mục tiêu: - Thực hiện các phép toán đối với một ma trận (ma trận 2 chiều). - Áp dụng triển khai các thuật toán trên ma trận. - Tính toán chính xác độ phức tạp của một thuật toán đơn giản. - Trả lời chính xác các bảng test về ma trận và độ phức tạp của thuật toán. - Sử dụng đúng các thuật toán áp dụng cho ma trận. - Thực hiện các thao tác an toàn với máy tính. Nội dung chính: 1. Ma trận Mục tiêu: - Thực hiện được các phép toán đối với ma trận; - Áp dụng triển khai thuật toán cộng và nhân hai ma trận. 1.1. Mở đầu Định nghĩa 1.1:Ma trận là một bảng số hình chữ nhật gồm mxn số thực được viết thành m hàng và n cột có dạng như sau : i: chỉ thứ tự hàng (i=1, ) j: chỉ thứ tự cột (j=1, ) mn: cấp của ma trận A = ⎡ ⎤ a : phần tử nằm ở hàng i cột j ⎢ ⎥ ij ⎢ ⎥ ⎢ ⎥ Ký hi⎢ệu: A=[aij]mn ⎥ Ví dụ⎣ 1.1: Ma trận ⎦ 1213 241 2là ma trận cấp 3x4 15 1 1.2. Số học ma trận : − a. Phép cộng hai3− ma trận : Định nghĩa1.2:Cho A=[aij]mn và B=[bij]mn. Tổng của hai ma trận A,B là ma trận C=[cij]mn sao cho cij = aij + bij∀i,j: i=1, ; j=1, Ký hiệu: C=A+B Ví dụ 1.2: 23 3 3 42 5 1 14 6 + 172 = 0118 20− 632 217 −2 Tổng của hai ma tr−ận có cùng kích thước nhận được bằng cách cộng các phần tử ở nhữ4−ng vị trí tương ứng.Các− ma trận có− kích thuớc khác nhau không thể cộng được 31
33. với nhau, vì tổng của hai ma trận chỉ được xác định khi cả hai ma trận có cùng số hàng và cùng số cột. Tính chất :Giả sử A, B là hai ma trận cùng cấp, khi đó : 〈 A+B=B+A (giao hoán) 〈 A+(B+C)=(A+B)+C (kết hợp) b. Phép nhân hai ma trận Định nghĩa1.3:Cho A=[aik]mq và B=[bkj]qn. Tích của ma trận A với ma trận B là ma trận C=[cij]mn với c a b +a b +a b +a b = a b ∀i,j: i=1,m, j=1,n + ⋯ +⋯ Ký hiệu: A.B hay AB ∑ Chú ý : Tích của hai ma trận chỉ được xác định khi số cột của ma trận thứ nhất bằng số hàng của ma trận thứ hai. a a a a a a b b b b b b ⎡ ⎤ = ⎢ ⎥ ⎡ ⎤ ⋮ ⋮ ⋮ ⋮ ⎢ ⎥ ⎢b b b⎥ ⎢a a a ⎥ ⎢ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⎥ ⎢ ⋮ ⋮ ⋮ ⋮ ⎥ ⎣ ⎦ ⎣ c c⎦ c c c c = c c c ⋮ Hình⋮ 2.1: Tích⋮ A=[aik]mq và B=[bkj]qn Ví dụ 1.3: Cho é1 0 4ù é2 4ù ê2 1 1ú A = ê ú vaì B = ê1 1 ú ê3 1 0ú ê ú ê ú ëê3 0 ûú ë0 2 2û Tìm AB. Giải : Vì A là ma trận 4x3 và B là ma trận 3x2 nên tích của AB là xác định và là ma trận 4x2. Để tìm các phần tử của AB, các phần tử tương ứng của các hàng của A và các cột của B ban đầu được nhân với nhau rồi sau đó các tích đó sẽ đuợc cộng lại. Ví dụ, phần tử ở vị trí (3,1) của AB là tổng các tích của các phần tử ở hàng thứ ba của A và cột thứ nhất của B, cụ thể là 3.2 + 1.1 + 0.3 = 7. Khi tất cả các phần tử của AB đã được : é14 4ù ê8 9 ú AB = ê ú ê7 13ú ê ú ë8 2 û Phép nhân ma trận không có tính chất giao hoán. Tức là nếu A và B là hai ma trận, thì không nhất thiết AB phải bằng BA. Thực tế có thể chỉ một trong hai tích đó là xác định. Ví dụ, nếu A là ma trận 2x3 và B là ma trậ 3x4, khi đó AB là xác định và là 18
34. ma trận 2x4, tuy nhiên ma trận BA là không xác định vì không thể nhân ma trận 3x4 với ma trận 2x3. Giả sử A là ma trận m x n và B là ma trận r x s. Khi đó AB là xác định chỉ khi n = r và BA là xác định chỉ khi s = m. Hơn nữa, khi AB và BA đều xác định, thì chúng cũng sẽ không cùng kích thước trừ trường hợp m = n = r = s. Do đó, nếu cả hai AB và BA xác định và có cùng kích thước thì cả A và B đều phải là các ma trận vuông và có cùng kích thước. Thậm chí nếu cả A và B dều là các ma trận n x n, thì AB và BA cũng không nhất thiết phải bằng nhau, như ví dụ dưới đây cho thấy: é1 1ù é2 1ù Ví dụ 1.4: Cho A = ê ú vaìB = ê ú ë2 1û ë1 1û Hỏi AB có bằng BA không ? Giải : Ta tìm được é3 2ù é4 3ù AB = ê ú vaìBA = ê ú ë5 3û ë3 2û Vậy : AB ¹ BA Tính chất: 〈 A cấp mxn, B cấp nxp, C cấp pxq A.(B.C)=(A.B).C (kết hợp) 〈 A cấp mxn, B và cấp nxp A.(B+C)=A.B+A.C (phân phối) 〈 A,B cấp mxn , C cấp nxp (A+B).C=A.C+B.C (phân phối) c. Thuật toán cộng hai ma trận : Giả sử rằng C=[cij]mn, là tổng của ma trận A=[aij]mnvà ma trận B=[bij]mn. Thuật toán dựa trên định nghĩa cộng ma trận được biểu diễn dưới dạng giả mã như sau : Thuật toán 1: Cộng ma trận Procedure cong_ma_tran (A, B: ma tran) Begin for i : =1 to m for j :=1 to n cij := aij + bij; End; d. Thuật toán nhân ma trận : Định nghĩa của tích hai ma trận dẫn tới thuật toán tính tích của hai ma trận. Giả sử rằng C=[cij]mn, là tích của ma trận A=[aiq]mkvà ma trận B=[bqj]kn. Thuật toán dựa trên định nghĩa nhân ma trận được biểu diễn dưới dạng giả mã như sau : Thuật toán2: Nhân ma trận Procedure nhan_ma_tran (A, B: ma tran) Begin for i : =1 to m forj :=1 to n begin cij = 0; fork := 1 to q do cij := cij + aikbkj; end; 19
35. End; {C = [cij] là tích của A và B} 1.3. Chuyển vị và luỹ thừa các ma trận Định nghĩa1.4: Ma trận đồng nhất (hay còn gọi là ma trận đơn vị) bậc n là ma trận In=[δij]nn vớiδij = 1 nếu i = jvà δij = 0 nếu i ¹ j. Do đó: 10 0 01 0 00 1 Nhân một ma trận với ma trận⋮⋮⋮⋮ đơn vị kích thước thích hợp không làm thay đổi ma trận đó. Nói cách khác, khi A là ma trận m x n, ta có: Ain = ImA = A Người ta cũng có thể định nghĩa luỹ thừa của các ma trận vuông khi A là một ma trận n x n, ta có: A =I , A =A.A.A A Phép toán chuyển hàng thành cột và cột thành hàng của một ma trận vuông cũng được sử dụng trong nhiều thuận toán. ầ Định nghĩa 1.5: Cho A = [aij] là ma trận cấp m x n. Chuyển vị của A được ký hiệu là At, là ma trận n x m nhận được bẳng cách trao đổi các hàng và cột của ma trận t A cho nhau. Nói cách khác, nếu A = [bij] thì bij = aji với i = 1, 2, , m. é1 4ù é1 2 3ù ê ú Ví dụ 1.6: Chuyển vị của ma trận ê ú laìma tráûn2 5 ë4 5 6 û ê ú ëê3 6ûú Các ma trận không đổi khi trao đổi các hàng và cột của nó cho nhau thường đóng vai trò quan trọng. Định nghĩa 1.6: Một ma trận vuông A được gọi là đối xứng nếu A =At. Như vậy A = [aij] là đối xứng nếu aij = aji với mọi i và j ; 0 ≤ i ≤ n và 0 ≤ j ≤ n. Chú ý rằng một ma trận là đối xứng nếu và chỉ nếu nó là ma trận vuông và đối xứng qua đường chéo chính của nó.Phép đối xứng này được minh hoạ trên hình 2.2. a a Hình 2.2 : Ma trận đối xứng é 1 1 0 ù Ví dụ 7 : Ma trận đối xứng ê 1 0 1 ú laì ê ú ëê 0 1 0 ûú 1.4. Các ma trận 0 - 1 (không - một) Các ma trận có các phần tử là 0 hoặc 1 được gọi là các ma trận không - một. Các ma trận không - một thường được dùng để biểu diễn các cấu trúc rời rạc. Các thuật toán dùng các cấu trúc này dựa trên số học Boole cho các ma trận không - một. Số học này lại dựa trên các phép toán Boole  và ∫ thực hiện trên các cặp bit và được định nghĩa bởi: 1 u b =b =1 b b = 0 các tr ng p còn i nế ∧ 20 ườ hợ lạ
36. 0 u b =b =0 b b = 1 các tr ng p còn i nế Định∨ ngh ĩa 1.7:Cho A = [aij] là các ma trận không - một m x n. Khi đó hợp của A và B, được ký hiệ u làườ A ∫ hợ B là ma lạ trận không - một với phần tử ở vị trí (i, j) là aij ∫ bij. Giao của A và B được ký hiệu là A  B, là ma trận không, một với phần tử ở vị trí (i, j) là aij  bij. Ví dụ 1.7:Tìm hợp giao của các ma trận không – một sau : 101 011 A= B= 010 110 Giải : Hợp của A và B là : é1 ∫ 0 0 ∫ 1 1 ∫ 0ù é1 1 1ù A ∫ B = ê ú = ê ú ë0 ∫ 1 1 ∫ 1 0 ∫ 0û ë1 1 0û Giao của A và B là : é1  0 0  1 1  0ù é0 0 0ù A  B = ê ú = ê ú ë0  1 1  1 0  0û ë0 1 0û Định nghĩa 1.8: Cho A = [aij] là ma trận không - một m x k và B = [bij] là ma trận không - một k x n. Khi đó tích Boole của A và B được ký hiệu là A ο B là ma trận m x n với phần tử ở vị trí (i, j) [cij] là: cij = (ai1  b1j ) ∫ (ai 2  b2j ) ∫ ∫(aik  bkj ) Chú ý rằng tích Boole của A và B nhận được bằng cách tương tự với tích thông thường của hai ma trận đó, nhưng với phép cộng được thay bằng phép ∫ và với phép nhân được thay bằng phép . Dưới đây là ví dụ về tích Boole của các ma trận. Ví dụ 1.9 : Tìm tích Boole của A với B, với: é1 0ù ê ú é1 1 0ù A = 0 1 vaì B = ê ú ê ú ë0 1 1û ëê1 0ûú Giải : Tích Boole A B được cho bởi: (1 1) (0⨀ 0) (1 1) (0 1) (1 0) (0 1) A B = (0 1) (1 0) (0 1) (1 1) (0 0) (1 1) (1∧1)∨(0∧0) (1∧1)∨(0∧1) (1∧0)∨(0∧1) ⨀ ∧ ∨ ∧ ∧ ∨ ∧ ∧ ∨ ∧ ∧0∨ 1 0∧ 0 0 ∧ 110∨ ∧ ∧ ∨ ∧ = 0 0 1 0 1 = 011 1∨0 1∨0 0∨0 110 0∨ ∨ ∨ Thuật toán31∨ dưới dạng∨ giả mã∨ sau đây mô tả thuật toán tính tích Boole của hai ma trận. Thuật toán 3: Tích Boole Procedure tich_Boole(A,B: các ma trận không - một) Begin for i : = 1 to m 21
37. for j :=1 to n begin cij := 0; for q :=1 to k cij := cij∫ (aiq bqj); end; End; {C=[cij] là tích Boole của A và B} Chúng ta cũng có thể định nghĩa luỹ thừa Boole của các ma trận không - một vuông.Các luỹ thừa này sẽ được dùng trong các nghiên cứu sau này về các đường trong đồ thị, các đường này được dùng, chẳng hạn để mô hình các đường liên lạc trong các mạng máy tính. Định nghĩa 1.9: Cho A là ma tận không - một vuông và r là một số nguyên dương. Luỹ thừa Boole bậc r của A được ký hiệu là A[r] với: A[ ] = A A [r] (A là hoàn toàn xác định vì tích Boole⨀A⨀ có ⨀tính chất kết hợp) [r] ầ Chúng ta cũng có thể định nghĩa A là In. é 0 0 1 ù Ví dụ 1.10. Cho A = ê1 0 0ú ê ú ëê1 1 0ûú Tìm A[r] với mọi n nguyên dương. Giải : Ta thấy ngay rằng : é1 1 0 ù [2] ê 0 0 1 ú A = A A = ê ú ê1 0 1 ú ⨀ ë û Ta cũng tìm được : é1 0 1 ù é1 1 1ù [3] [2] ê1 1 0ú [4] [3] ê1 0 1ú A = A A = ê ú và A = A A = ê ú ê1 1 1ú ê1 1 1ú ⨀ ë û ⨀ ë û Tính thêm 1 lần nữa, ta được : é1 1 1ù [5] [4] ê1 1 1ú A = A A = ê ú ê1 1 1ú ⨀ ë û Có thể thấy rằng A[n] = A[5] với mọi n nguyên dương không nhỏ hơn 5. Số các phép toán bit được dùng để tích Boole của hai ma trận n x n cũng dễ dàng xác định được. Ví dụ 1.11: Có bao nhiêu phép toán bit được dùng để tính A B với A, B là các ma trận không - một n x n. Giải: Có n2phép toán bit trong A B. ⨀ 2. Thuật toán Mục tiêu: ⨀ - Tính toán chính xác độ phức tạp của thuật toán; 22
38. - Trả lời chính xác các bảng test về độ phức tạp của thuật toán; - Ứng dụng đánh giá độ phức tạp thuật toán trong thực tế. 2.1. Khái niệm thuật toán Định nghĩa 2.1:Thuật toán (algorithm) là một dãy các quy tắc nhằm xác định một dãy các thao tác trên các đối tượng sao cho sau một số hữu hạnbước thực hiện sẽ đạt được mục tiêu đặt ra. 2.2. Các đặc trưng của thuật toán 〈 Đầu vào (Input): Một thuật toán có các giá trị đầu vào từ một tập đã được chỉ rõ. 〈 Đầu ra (Output): Từ mỗi tập các giá trị đầu vào, thuật toán sẽ tạo ra các giá trị đầu ra. Các giá trị đầu ra chính là nghiệm của bài toán. 〈 Tính dừng: Sau một số hữu hạn bước thuật toán phải dừng. 〈 Tính xác định: Ở mỗi bước, các bước thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng. Nói rõ hơn, trong cùng một điều kiện hai bộ xử lý cùng thực hiện một bước của thuật toán phải cho những kết quả như nhau. 〈 Tính hiệu quả: Trước hết thuật toán cần đúng đắn, nghĩa là sau khi đưa dữ liệu vào thuật toán hoạt động và đưa ra kết quả như ý muốn. 〈 Tính phổ dụng: Thuật toán có thể giải bất kỳ một bài toán nào trong lớp các bài toán. Cụ thể là thuật toán có thể có các đầu vào là các bộ dữ liệu khác nhau trong một miền xác định. 2.3. Ngôn ngữ thuật toán Có nhiều cách trình bày thuật toán: dùng ngôn ngữ tự nhiên, ngôn ngữ lưu đồ (sơ đồ khối), ngôn ngữ lập trình. Tuy nhiên, một khi dùng ngôn ngữ lập trình thì chỉ những lệnh được phép trong ngôn ngữ đó mới có thể dùng được và điều này thường làm cho sự mô tả các thuật toán trở nên rối rắm và khó hiểu.Hơn nữa, vì nhiều ngôn ngữ lập trình đều được dùng rộng rãi, nên chọn một ngôn ngữ đặc biệt nào đó là điều người ta không muốn.Vì vậy ở đây các thuật toán ngoài việc được trình bày bằng ngôn ngữ tự nhiên cùng với những ký hiệu toán học quen thuộc còn dùng một dạng giả mã để mô tả thuật toán.Giả mã tạo ra bước trung gian giữa sự mô tả một thuật toán bằng ngôn ngữ thông thường và sự thực hiện thuật toán đó trong ngôn ngữ lập trình.Các bước của thuật toán được chỉ rõ bằng cách dùng các lệnh giống như trong các ngôn ngữ lập trình. Ví dụ 2.1:Mô tả thuật toán tìm phần tử lớn nhất trong một dãy hữu hạn các số nguyên. a) Dùng ngôn ngữ tự nhiên để mô tả các bước cần phải thực hiện: B1: Đặt giá trị cực đại tạm thời bằng số nguyên đầu tiên trong dãy. (Cực đại tạm thời sẽ là số nguyên lớn nhất đã được kiểm tra ở một giai đoạn nào đó của thủ tục.) B2: So sánh số nguyên tiếp sau với giá trị cực đại tạm thời, nếu nó lớn hơn giá trị cực đại tạm thời thì đặt cực đại tạm thời bằng số nguyên đó. B3: Lặp lại bước trước nếu còn các số nguyên trong dãy. B4: Dừng khi không còn số nguyên nào nữa trong dãy. Cực đại tạm thời ở điểm này chính là số nguyên lớn nhất của dãy. b) Dùng đoạn giả mã: Proceduremax(a1, a2, , an: integers); Begin max:= a1; for i:= 2 to n 23
39. if max 0) doi:= i+1; nguyen_to := i > k; End; * Thuật toán tìm và in ra các nguyên tố nhỏ hơn nguyên dương n. Thuật toán này sử dụng thuật toán nguyên_to ở trên như là thủ tục con. - Đầu vào: số nguyên dương n - Đầu ra: các số nguyên tố nhỏ hơn n Procedurelist_nguyen_to(n) Begin For i:= 2 to n=1 do ifnguyen_to (i) then write (i,”); End; 2.4. Độ phức tạp của thuật toán 2.4.1. Khái niệm về độ phức tạp của thuật toán Thước đo hiệu quả của một thuật toán là thời gian mà máy tính sử dụng để giải bài toán theo thuật toán đang xét, khi các giá trị đầu vào có một kích thước xác định. Một thước đo thứ hai là dung lượng bộ nhớ đòi hỏi để thực hiện thuật toán khi các giá trị đầu vào có kích thước xác định. Các vấn đề như thế liên quan đến độ phức tạp tính toán của một thuật toán.Sự phân tích thời gian cần thiết để giải một bài toán có kích thước đặc biệt nào đó liên quan đến độ phức tạp thời gian của thuật toán.Sự phân tích bộ nhớ cần thiết của máy tính liên quan đến độ phức tạp không gian của thuật toán.Việc xem xét độ phức tạp thời gian và không gian của một thuật toán là một vấn đề rất thiết yếu khi các thuật toán được thực hiện.Biết một thuật toán sẽ đưa ra đáp số trong một micro giây, trong một phút hoặc trong một tỉ năm, hiển nhiên là hết sức quan trọng. Tương tự như vậy, dung lượng bộ nhớ đòi hỏi phải là khả dụng để giải một bài toán,vì vậy độ phức tạp không gian cũng cần phải tính đến.Vì việc xem xét độ 24
40. phức tạp không gian gắn liền với các cấu trúc dữ liệu đặc biệt được dùng để thực hiện thuật toán nên ở đây ta sẽ tập trung xem xét độ phức tạp thời gian. Độ phức tạp thời gian của một thuật toán có thể được biểu diễn qua số các phép toán được dùng bởi thuật toán đó khi các giá trị đầu vào có một kích thước xác định.Sở dĩ độ phức tạp thời gian được mô tả thông qua số các phép toán đòi hỏi thay vì thời gian thực của máy tính là bởi vì các máy tính khác nhau thực hiện các phép tính sơ cấp trong những khoảng thời gian khác nhau. Hơn nữa, phân tích tất cả các phép toán thành các phép tính bit sơ cấp mà máy tính sử dụng là điều rất phức tạp. Ví dụ2.3: Xét thuật toán tìm số lớn nhất trong dãy n số a1, a2, , an. Có thể coi kích thước của dữ liệu nhập là số lượng phần tử của dãy số, tức là n. Nếu coi mỗi lần so sánh hai số của thuật toán đòi hỏi một đơn vị thời gian (giây chẳng hạn) thì thời gian thực hiện thuật toán trong trường hợp xấu nhất là n-1 giây. Với dãy 64 số, thời gian thực hiện thuật toán nhiều lắm là 63 giây. Ví dụ2.4: Thuật toán về trò chơi “Tháp Hà Nội” Trò chơi “Tháp Hà Nội” như sau: Có ba cọc A, B, C và 64 cái đĩa (có lỗ để đặt vào cọc), các đĩa có đường kính đôi một khác nhau. Nguyên tắc đặt đĩa vào cọc là: mỗi đĩa chỉ được chồng lên đĩa lớn hơn nó. Ban đầu, cả 64 đĩa được đặt chồng lên nhau ở cột A; hai cột B, C trống. Vấn đề là phải chuyển cả 64 đĩa đó sang cột B hay C, mỗi lần chỉ được di chuyển một đĩa. Xét trò chơi với n đĩa ban đầu ở cọc A (cọc B và C trống). Gọi Sn là số lần chuyển đĩa để chơi xong trò chơi với n đĩa. Nếu n=1 thì rõ ràng là S1=1. Nếu n>1 thì trước hết ta chuyển n-1 đĩa bên trên sang cọc B (giữ yên đĩa thứ n ở dưới cùng của cọc A). Số lần chuyển n-1 đĩa là Sn-1. Sau đó ta chuyển đĩa thứ n từ cọc A sang cọc C. Cuối cùng, ta chuyển n-1 đĩa từ cọc B sang cọc C (số lần chuyển là Sn- 1). Như vậy, số lần chuyển n đĩa từ A sang C là: 2 n-1 n-2 Sn= Sn-1+ 1+ Sn= 2Sn-1+ 1=2(2Sn-2+ 1) + 1 = 2 Sn-2+ 2 + 1 = = 2 S1+ 2 + + 2+1 = 2n-1. Thuật toán về trò chơi “Tháp Hà Nội” đòi hỏi 264 - 1 lần chuyển đĩa (xấp xỉ 18,4 tỉ tỉ lần). Nếu mỗi lần chuyển đĩa mất 1 giây thì thời gian thực hiện thuật toán xấp xỉ 585 tỉ năm! Hai thí dụ trên cho thấy rằng: một thuật toán phải kết thúc sau một số hữu hạn bước, nhưng nếu số hữu hạn này quá lớn thì thuật toán không thể thực hiện được trong thực tế. Ta nói: thuật toán trong Ví dụ 2.3 có độ phức tạp là n-1 và là một thuật toán hữu hiệu (hay thuật toán nhanh); thuật toán trong Ví dụ 2.4 có độ phức tạp là 2n-1 và đó là một thuật toán không hữu hiệu (hay thuật toán chậm). 2.4.2. So sánh độ phức tạp thuật toán Thông thường trong các ứng dụng thực tế, thời gian chính xác mà thuật toán đòi hỏi để thực hiện nó ít được quan tâm hơn so với việc xác định mức độ tăng lên của thời gian thực hiện thuật toán khi kích thước của dữ liệu đầu vào tăng lên. Chẳng hạn một thuật toán đang được xem xét nào đó có thời gian tính trong trường hợp tồi nhất là :t(n) = 30n2 + 6n + 6 với đầu vào kích thước n. n t(n) = 30n2 + 6n + 6 30n2 10 3066 3000 100 300606 300000 25
41. 1000 30006006 30000000 10000 3000060006 3000000000 Khi n lớn thì ta có thể lấy xấp xỉT(n) = 0.5n2 + 0.1n + 0.1 sẽ cho ta thời gian tính cho bằng phút. Khi mô tả tốc độ tăng thời gian tính của thuật toán khi kích thước đầu vào tăng ta chỉ quant âm đến số hạng trội (30n2), có thể bỏ qua các hằng số. Với giả thiết như vậy, thời gian tính T(n) tăng gống như n2 khi n tăng. Việc làm ở đây là thay thế biểu thức T(n) = 0.5n2 + 0.1n + 0.1 bởi n2 có cùng tốc độ tăng với T(n). Ta đi đến định nghĩa sau : Định nghĩa 2.2:Giả sử f và g là các hàm đối số nguyên dương. 〈 Ta nói f(n) có bậc không quá g(n), ký hiệu f(n) = O(g(n)), nếu tồn tại hằng số dương C1 và số nguyên dương N1 sao cho |f(n)|≤C1|g(n)| với mọi n ³ N1. 〈 Ta nói f(n) có bậc ít nhất là g(n), ký hiệu f(n) = Ω(g(n)), nếu tồn tại hằng số dương C2 và số nguyên dương N2 sao cho |f(n)|³C2|g(n)| với mọi n ³ N2. 〈 Ta nói f(n) có bậc là g(n), ký hiệuf(n) = (g(n)), nếu f(n) = O(g(n)) và f(n) = Ω(g(n)). Ví dụ 2.5: Xét hàm f(n) = 60n2 +9n +9 θ Do 60n2 +9n +9 ≤ 60n2 +9n2 +n2 = 70n2 với mọi n³1 2 Chọn C1 = 70 theo định nghĩa ta có: f(n)=O(n ), Do 60n2 +9n +9 ³60n2 với mọi n³1 2 Chọn C2 = 70 theo định nghĩa ta có: f(n)=Ω(n ), è Từ đó ta có f(n) = θ(n2) Định nghĩa 2.3: 〈 Nếu thuật toán đòi hỏi thời gian tính tốt nhất là t(n) với kích thước đầu vào n và t(n) = O(g(n)) ta nói thời gian tính tốt nhất của thuật toán có bậc không quá g(n) hay thời gian tính tốt nhất của thuật toán là O(g(n)). 〈 Nếu thuật toán đòi hỏi thời gian tính tồi nhất là t(n) với kích thước đầu vào n và t(n) = O (g(n)) ta nói thời gian tính tồi nhất của thuật toán có bậc không quá g(n) hay thời gian tính tồi nhất của thuậttoán là O(g(n)). 〈 Nếu thuật toán đòi hỏi thời gian tính trung bình là t(n) với kích thước đầu vào n và t(n) = O(g(n)) ta nói thời gian trung bình của thuật toán có bậc không quá g(n) hay thời gian tính trung bình của thuật toán là O(g(n)). Trong định nghĩa trên, nếu thay O bởi Ω và không quá bởi ít nhất ta có bậc ít nhất của thời gian tính tốt nhất, tồi nhất và trung bình của thuật toán. Nếu thời gian tính tốt nhất của thuật toán vừa là O(g(n)) vừa là Ω(g(n)), tá nói thời gian tính tốt nhất của thuật toán là θ(g(n)). Tương tự như vậy ta cũng định nghĩa thời gian tính tồi nhất và trung bình của thuật toán là θ(g(n)). Cần đánh giá thời gian tính tốt nhất, tồi nhất và trung bình của thuật toán so với kích thước đầu vào n. Thời gian tính của thuậ toán có thể đánh giá bởi số lần thực hiện câu lệnh trong vòng lặop repeat. - Nếu a1 = x thì câu lệnh i:=i+1 trong thân vòng lặp repeat thực hiện một lần. Do đó thời gian tính tốt nhất của thuật toán là θ(1). - Nếu x khôngcó mặt trong dãy đã cho, thì câu lệnh i:=i+1 thực hiện n lần. Do đó thời gian tính tốt nhất của thuật toán là θ(1). - Cuối cùng ta tìm thời gian tính trung bình của thuật toán. Nếu x tìm thấy ở vị trí thứ i của dãy (x = ai) thì câu lệnh i:=i+1 phải thực hiện i lần (i = 1,2, n); nếu x 26
42. không có mặt trong dãy đã cho thì câu lệnh i := i+1 thực hiện n lần. Từ đó suy ra số lần trung bình phải thực hiện câu lệnh i :=i+1 là : [(1+2+ + n) + n]/ (n+1) ≤ (n2 + n)/(n + 1) = n Vậy thời gian tính trung bình của thuật toán là O(n). Mặt khác, do [(1 + 2 + + n)]/(n+1) ³ (n2/4 + n)/(n+1) ³ (n2/4 + n/4)/(n+1) = n/4 nên thời gian tính trung bình của thuật toán là θ(n). 2.4.3. Đánh giá độ phức tạp của thuật toán Một điều quan trọng cần phải biết là máy tính phải cần bao lâu để giải xong một bài toán.Thí dụ, nếu một thuật toán đòi hỏi 10 giờ, thì có thể còn đáng chi phí thời gian máy tính đòi hỏi để giải bài toán đó.Nhưng nếu một thuật toán đòi hỏi 10 tỉ năm để giải một bài toán, thì thực hiện thuật toán đó sẽ là một điều phi lý. Một trong những hiện tượng lý thú nhất của công nghệ hiện đại là sự tăng ghê gớm của tốc độ và lượng bộ nhớ trong máy tính. Một nhân tố quan trọng khác làm giảm thời gian cần thiết để giải một bài toán là sự xử lý song song - đây là kỹ thuật thực hiện đồng thời các dãy phép tính. Do sự tăng tốc độ tính toán và dung lượng bộ nhớ của máy tính, cũng như nhờ việc dùng các thuật toán lợi dụng được ưu thế của kỹ thuật xử lý song song, các bài toán vài năm trước đây được xem là không thể giải được, thì bây giờ có thể giải bình thường. Các thuật ngữ thường dùng cho độ phức tạp của một thuật toán Dạng đánh giá Tên gọi θ(1) Hằng số θ(log2n) Logarithm θ(n) Tuyến tính n log n θ(nlog2n) θ(n2) Bậc hai θ(n3) Bậc ba m Đa thức θ(n ) Hàm mũ θ(mn), m ³ 2 Giai thừa θ(n!) Hình 2.1: Các đánh giá thông dụng Trong bảng, các đánh giá được sắp xếp theo thứ tự tăng dần của tốc độ tăng (ngoại trừ trường hợp θ(nm)) Bảng dưới đây cho ta thấy thời gian tính tăng như thế nào với các đánh giá khác nhau khi sử dụng đơn vị thời gian 0,001 giây (những số có đơn vị kèm theo là những số gần đúng). Thời gian tính nếu n = Đánh giá 2 8 32 64 1 0,001 0,001 0,001 0,001 log2n 1 3 5 6 n 2 8 32 24 nlog2n 2 24 160 384 n2 4 64 1,02 giây 4,09 giây n3 8 512 32,7 giây 4,36 giây 2n 4 256 49,71 giây 5,85 . 108 năm N ! 2 40,3 giây 8,34.1023 năm 4,02.1078 năm 27
43. Bài tập chương 3 của học sinh, sinh viên é1 − 2 3ù Bài 1 : Cho A = ê2 − 4 1ú vàf(x) = 3x2- 2x + 5. ê ú ëê3 − 5 2ûú Hãy tính f (A)? n é2 −1ù Bài 2 :Tìm A với A = ê ú ë3 − 2û Bài 3 :Hãy viết ma trận hệ số hệ phương trình : ì3x1 − 5x 2 + 2x 3 + 4x 4 = 2 ï a) í7x1 − 4x 2 + 2x 3 + 3x 4 = 5 ï î5x1 + 7x 2 − 4x 3 − 6x 4 = 3 ìax1 + x 2 + x 3 + x 4 =1 ï b) íx1 − ax2 + x 3 + x 4 = a ï 2 îx1 + x 2 + ax3 + x 4 = a Bài 4 : Cho ma trận : é1 2 3ù A = ê5 7 10ú và I là ma trận đơn vị cấp 3. ê ú ëê4 3 1 ûú Hãy tính A + 2I ? Bài 5 :Cho 2 ma trận : é1 2 3ù é502ù A = ê2 0 1ú ; B=ê123ú ê ú ê ú ëê3 − 1 1ûú ëê−102ûú Hãy tính AB và BA ? Bài 6 :Cho ma trận: é1 2ù A = ê ú ë3 4û Hãy tính A2và A2 + 5A Bài 7: Chứng minh rằng: a. = O(x) b.2 n+ 17 = O(3n) Bài 8: Tìm một số nguyên n nhỏ nhất sao cho f(x)=O(xn), nếu: a. f(x)=2x3 + x2lgx b. f(x)= Bài 9: Lập thuật toán tìm trong dãy số nguyên dương cho trước số hạng đầu tiên nhỏ hơn sốhạng đứng ngay trước nó. Xác định độ phức tạp của thuật toán? 28
44. Hướng dẫn thực hiện bài tập mở rộng và nâng cao Bài 1: Thay giá trị f(A) vào hàm f(x) = 3x2- 2x + 5. Sau đó sử dụng quy tắc cộng và quy tắc nhân hai ma trận để tính giá trị của f(A). Bài 2: Sử dụng lũy thừa các ma trận và quy tắc nhân hai ma trận để xác định An(xét n với giá trị chẵn và lẻ). Bài 3:Tìm ma trận hệ số theo ma trận A dưới đây: a a a a a a Ma trận A = gọi là ma trận hệ số của hệ phương trình: a a a a x +a x +a x =a a x +a x +a x =a +⋯ ax +ax +⋯+ax =a Bài 4: +⋯ Sử dụng quy tắc nhân vô hướng một số thực với ma trận để tính: 2I Sử dụng quy tắc cộng hai ma trận để xác định kết quả: A + 2I. Bài 5: Sử dụng quy tắc nhân hai ma trận để xác định kết quả: AB và BA. Bài 6: Sử dụng quy tắc nhân và lũy thừa các ma trận tính A2 Sử dụng quy tắc nhân vô hướng một số thực với ma trận để tính: 5A Sử dụng quy tắc cộng hai ma trận tính A2 + 5A. Bài 7: Để tìm độ phức tạp ta dựa vào định nghĩa sau: f(n) = O(g(n)) nếu tồn tại hằng số dương C1 và số nguyên dương N1 sao cho |f(n)|≤C1|g(n)| với mọi n ³ N1. Bài 8: Xác định n dựa vào định nghĩa sau: f(n) = O(g(n)) nếu tồn tại hằng số dương C1 và số nguyên dương N1 sao cho |f(n)|≤C1|g(n)| với mọi n ³ N1. Giá trị n nguyên nhỏ nhất là N1 (n=N1). Bài 9: 〈 Procedure find decrease (a1 a2 an: nguyên dương); location := 0; i := 2; while i ≤ n and location = 0 do begin j := 1; while j < i and location := 0 do if ai = aj then location := i else j := j +1; i := i +1; end; {location là chỉ số của giá trị đầu tiên lặp lại giá trị trước trong dãy} 〈 Độ phức tạp của thuật toán là O(n2). 29
45. CHƯƠNG 4: PHƯƠNG PHÁP TÍNH Mã chương: MHLTV 11-04 Giới thiệu: Mục tiêu: - Thực hiện đúng các bài toán về xấp xỉ và sai số, các phương trình, hệ phương trình, nội suy và bình phương cực tiểu, Tính gần đúng đạo hàm và tích phân xác định; - Mô tả được các cách tính: bài toán về xấp xỉ và sai số, các phương trình, hệ phương trình, nội suy và bình phương cực tiểu, Tính gần đúng đạo hàm và tích phân xác định; - Trả lời chính xác các bảng test trên giấy về các nội dung của phương pháp tính; - Thực hiện các thao tác an toàn với máy tính. Nội dung chính: 1. Số xấp xỉ và sai số Mục tiêu: - Mô tả được các cách tính toán về số xấp xỉ và sai số; - Thực hiện đúng các bài toán về số xấp xỉ và sai số. 1.1. Số xấp xỉ Trong thực hành, giá trị của các đại lượng nhận được bằng phép đo, bằng thực nghiệm thường không được biết một cách chính xác. Vì vậy trong tính toán , chúng ta làm việc chủ yếu với giá trị xấp xỉ (còn gọi là giá trị gần đúng) của các đại lượng. Định nghĩa 1.1: a gọi là số xấp xỉ của số đúng A, ký hiệu a≈A , nếu a khác A không đáng kể và được dùng thay cho A trong tính toán . Nếu a A thì a gọi là xấp xỉ thừa của A Ví dụ 1.1: Đối với số π thì 3.14 là xấp xỉ thiếu của π , còn 3.15 là xấp xỉ thừa của π , vì dễ thấy rằng : 3.14 < π < 3.15 1.2. Sai số tuyệt đối Định nghĩa1.2: Hiệu Δa = A - a (hoặc Δa = a - A) gọi là sai số tuyệt đối của số xấp xỉ a. Trị tuyệt đối : Δ = Δa = A - a (1.1) gọi là sai số tuyệt đối của số xấp xỉ a Thông thường, không biết số đúng A , do đó không xác định được sai số tuyệt đối của số xấp xỉ a. Vì vậy, cùng với khái niệm sai số tuyệt đối, người ta đưa thêm vào khái niệm sai số tuyệt đối giới hạn. Định nghĩa1.3: Sai số tuyệt đối giới hạn của số xấp xỉ a là số không nhỏ hơn sai số tuyệt đối của số xấp xỉ a. Do đó, nếu gọi Δa là sai số tuyệt đối giới hạn của số xấp xỉ a thì : Δ = Δa = A - a ≤Δa (1.2) Từ đó, suy ra : a - Δa ≤ A ≤ a + Δa (1.3) 30
46. Vậy a -Δa là xấp xỉ thiếu của A, còn a + Δa l à xấp xỉ thừa của A . Để đơn giản , thường qui ước viết (1.3) dưới dạng : A = a µ Δa (1.4) Ví dụ 1.1: Xác định sai số tuyệt đối giới hạn của số xấp xỉ a = 3,14 thay cho số π Giải : Ví 3.14 <π < 3.15 nên : < 0.01 và có thể chọn Δa = 0.01. Nếu chú ý rằng : 3.14 <π < 3.142a− thì : < 0.002 và do đó nhận được giá trị tốt hơn Δa = 0.002 Qua ví dụ trên, thấy rằng địa−nh ngh ĩa sai số tuyệt đối giới hạn không đơn trị : sai số tuyệt đối giới hạn của số xấp xỉ a là số bất kỳ trong trong tập vô hạn các số không âm Δa thoả mãn (1.2). Vì vậy, trong thực hành, người ta thường chọn Δa là số nhỏ nhất có thể được, thoả mãn (1.2). 1.3. Sai số tương đối Sai số tuyệt đối và sai số tuyệt đối giới hạn không thể hiện một cách đầy đủ mức độ chính xác của phép đo hoặc tính toán. Chẳng hạn, đo chiều dài của hai cái trục, nhận được những kết quả sau : l1 = 158.6cm µ 0.1 cm l2 = 5.4 cm µ 0.1 cm Tuy sai số tuyệt đối giới hạn của hai phép đo trên bằng nhau nhưng rổ ràng phép đo l1 chính xác hơn phép đo l2. Để thể hiện được điều đó, người ta đưa vào những khái niệm sau : Định nghĩa1.4: Sai số tương đối của số xấp xỉ a, ký hiệu δ , là : Δ Α-a δ = = (1.5) Α Α với giả thiết A ≠ 0. Từ đó :Δ =|A|. , ở đây nói chung A chưa biết. Định nghĩa1.5: δ Δa Sai số tương đối giới hạn của số xấp xỉ a, ký hiệu δ = (1.6) a a Từ đó suy ra :δ a = a δ a (1.7) Chú ý rằng, sai số tuyệt đối và sai số tuyệt đối giới hạn có cùng thứ nguyên với số xấp xỉ, còn sai số tương đối và sai số tương đói giới hạn không có thứ nguyên Thay (6.7) vào (6.4), ta có : A = a(1 µ δ a ) (1.8) Trở lại với kết quả phép đo chiều dài của hai cí trục nêu trên, dễ thấy rằng sai số tương đối giới hạn của phép đo l1 nhỏ hơn sai số tương đối giới hạn của phép đo l2. 2. Giải gần đúng các phương trình Mục tiêu: - Xác định các phương pháp giải gần đúng nghiệm phương trình; - Biết cách đánh giá sai số của từng phương pháp. 2.1. Nghiệm và khoảng phân ly nghiệm a. Nghiệm thực của phương trình một ẩn Xét phương trình một ẩn : f(x) = 0 (2.1) 31
47. trong đó f là một hàm số cho trước của đối số x. Nghiệm thực của phương trình (2.1) là số thực α thoả mãn (2.1) tức là khi thay α vào x ở vế trái ta được f( α ) = 0 (2.2) b. Sự tồn tại nghiệm thực của phương trình (1) Trước khi tìm cách tính gần đúng nghiệm thực của phương trình (2.1) ta phải tự hỏi nghiệm ấy có tồn tại không. Để trả lời câu hỏi đó ta có định lí sau : Định lí 2.1: Nếu có hai số thực a và b (a < b) sao cho f(a) và f(b) trái dấu tức là f(a) . f(b) < 0 (2.3) đồng thời f(x) liên tục trên [a, b] thì ở trong khoảng [a, b] có ít nhất một nghiệm thực của phương trình (2.1). c. Khoảng phân li nghiệm (còn gọi là khoảng tách nghiệm) Định nghĩa2.1: Khoảng [a, b] nào đó gọi là khoảng phân ly nghiệmcủa phương trình (1) nếu nó chứa một và chỉ một nghiệm của phương trình đó. Để tìm khoảng phân li nghiệm ta có định lí : Định lí 2.2: Nếu [a, b] là một khoảng trong đó hàm số f(x) liên tục và đơn điệu, đồng thời f(a) và f(b) trái dấu, tức là có f(a) . f(b) < 0 thì [a, b] là một khoảng phân li nghiệm của phương trình (1). Định lí 2.3: Nếu [a, b] là một khoảng trong đó hàm f(x) liên tục, đạo hàm f’(x) không đổi dấu thì [a, b] là một khoảng phân li nghiệm của phương trình (1) Để tìm các khoảng phân li nghiệm của phương trình (1) thường người ta nghiên cứu sự biến thiên của hàm số y = f(x) rồi áp dụng định lí 2.3 Ví dụ2.1: Cho phương trình f(x) = x3 - x - 1 = 0 (*) Hãy chứng tỏ phương trình này có nghiệm thực và tìm khoảng phân li nghiệm. Giải:Trước hết ta xét sự biến thiên của hàm số f(x). Nó xác định và liên tục tại mọi x, đồng thời 1 f’(x) = 3x2 - 1 = 0 tại x = µ 3 Ta suy ra bảng biến thiên X - × - 1 3 1 3 + × f’(x) + 0 - 0 + f(x) M + × -m× 32
48. 1 1 trong đó M = f(- 1 3 ) = - + - 1 0 x Vậy khoảng [1, 2] chứa nghiệm của phương trình (*). Nhưng vì phương trình này chỉ α có một nghiệm nên chính nghiệm ấy phân li trong [1, 2] Tóm lại: Trước khi giải phương trình f(x) = 0, ta cần cô lập các nghiệm (tìm khoảng phân li nghiệm. Tức là tìm [a, b] thoả mãn các điều kiện sau: 1. f(a).f(b) 0 a x1 b f’’(x) 0 B Hình 4.1: Phương pháp dây cung Phương trình dây cung AB là phương trình đường thẳng qua hai điểm nên có dạng: y - f(x ) x - x 0 = 0 (2.7) f(d) - f(x 0 ) d - x 0 trong đó x0 có thể lấy là a (hoặc b)thì d sẽ là b (hoặc a). Vì vậy cung cắt trục Ox tại điểm (x1, 0) trong phương trình 2.7 cho y = 0 và x = x1 ta được: d - x d - x 0 x1 = x0 - f(x0) (2.8) f(d) - f(x 0 ) Để nhận được nghiệm chính xác hơn, ta lặp lại quá trình trên đối với khoảng (x1,d); ta thu được: 33
49. d - x1 x2 = x1 - f(x1) và f(d) - f(x 1 ) Người ta đã chứng minh được rằng: Dãy x0, x1, x2, sẽ tiến dần đến nghiệm đúng của phương trình (2.1), nếu chọn x0 sao cho f’’(x) và f(x0) khác dấu, tức là f’’(x).f(x0) 0 x [1, 2] f’’(x) = 6x > 0 x [1, 2] Ta chọn : x0 = 1 (vì f(1) 0 B nghiệm f(a)<0 đúng a b=x0 x1 A Hình 4.2: Phương pháp tiếp tuyến Giả sử chọn x0 = a thì tại A(x0, f(x0)), phương trình tiếp tuyến với đường cong y = f(x) tại điểm A sẽ là : y - f(x0) = f’(x0)(x - x0). Vì tiếp tuyến cắt với trục Ox tại điểm (x1, 0) nên toạ độ đó phải thỏa mãn phương trình tiếp tuyến : - f(x0) = f’(x0)(x - x0) f(x 0 ) Từ đó ta có : x1 = x0 - (2.9) f' (x 0 ) Để nhận được nghiệm chính xác hơn, ta lặp lại quá trình trên đối với điểm (x1, f(x1 ) f(x1)) ta thu được : x2 = x1 - và f'(x1 ) 34
50. Người ta đã chứng minh được rằng : Dãy x0, x1, x2, sẽ tiến dần đến nghiệm đúng của phương trình (2.1), nếu chọn x0 sao cho f’’(x) và f(x0) cùng dấu, tức là f’’(x).f(x0) > 0. Ví dụ2.3: Tìm nghiệm gần đúng của phương trình : f(x) = x3 - x - 1 = 0, biết [1, 2] là khoảng phân li nghiệm, đã tìm ở trên. 2 Giải: Ta có f’(x) = 3x -1 > 0 ∀ x  [1, 2] f’’(x) = 6x > 0 ∀ x  [1, 2] Ta chọn: x0 = 2 (vì f(2) > 0, tức là f’’(x).f(2) > 0). 5 Theo công thức (2.9) ta có: x = 2 - ∪ 1.571 1 7 Ta áp dụng phương pháp tiếp tuyến một lần nữa, ta thay x0 bởi x1 : 1.306 x = 1.571 - ∪ 1.367 2 6.404 Vậy nghiệm gần đúng của phương trình là 1.367 (muốn thu được nghiệm chính xác hơn ta có thể áp dụng công thức (2.9) một vài lần nữa) 2.4. Phương pháp phối hợp Giả sử (a, b) là khoảng phân li nghiệm của phương trình f(x) = 0, nghĩa là: f(a).f(b) 0 f ’(x)>0 a a1 a2 b b2 b1 A Hình 4.3: Phương pháp phối hợp Ví dụ2.4: Tìm một nghiệm của phương trình : f(x) = xex - 2 = 0 với độ chính xác đến 0.01 bằng phương pháp phối hợp. Giải: Trước hết ta xác định khoảng phân li nghiệm . x f(x) ) = xe - 2 xác định và liên tục ∀ x R f’(x) = ex + xex = ex(1 + x) = 0 ⇒ x = - 1 f’’(x) = ex + ex + xex = ex(2 + x) Ta có bảng biến thiên : x - × - 1 + × 35
51. f’(x) - 0 + f(x) m Ta có : f(0) = - 2 0 và f’(x) > 0 ∀ x  (0, 1) f’’(x) > 0 ∀ x  (0, 1) Vậy (0, 1) là khoảng phân li nghiệm.Do thỏa mãn 3 điều kiện (2.4) (2.5) (2.6) nên đồng thời áp dụng hai phương pháp dây cung và tiếp tuyến. Theo phương pháp dây cung : do f’’(x) > 0 nên chọn x0 sao cho f’’(x).f(x0) 0 nên chọn x0 = 1 vì f(1) >0. Theo công thức (2.9) : f(x 1 ) e - 2 1 1 = x - = 1 - = + ∪0.8679 x1 0 f' (x 0 ) 2e 2 e Vì - x1 = 0.8679 - 0.7358 = 0.1321 > 0.01 nên tiếp tục lần nữa hai phương x1 pháp trên trong (0.7358 ; 0.8679). Theo phương pháp dây cung : d1 - x 1 x2 = x1 - f(x1) (với d1 = 0.8679) f(d 1 ) - f(x 1 ) (0.8679- 0.7358)(0.7358.e0.7358 - 2) = 0.7358 - ∪ 0.8528. (0.8679.e0.8679 - 2) - (0.7358.e0.7358 - 2) Theo phương pháp tiếp tuyến : 0.8679 f(x 2 ) 0.8679.e - 2 = x - = 0.8679 - ∪ 0.8534. x2 1 0.8679 f' (x1 ) e (1+ 0.8679) Vì - x = 0.8534 - 0.8528 = 0.0006 < 0.01 x2 2 Vậy có thể xem nghiệm gần đúng của phương trình là : 1 1 x = (x2+ x ) = (0.8534 + 0.8528) = 0.8531. 2 2 2 2.5. Phương pháp chia đôi Giả sử phương trình f(x) = 0 (2.1) có nghiệm thực α phân li trong [a, b] . Ta tìm cách thu nhỏ dần khoảng phân li nghiệm bằng cách chia đôi liên tiếp các khảng phân li nghiệm đa tìm ra. Trước hêt ta chia đôi khoảng [a, b], điểm chia là: c = (a + b)/2. Rõ ràng khoảng phân li nghiệm mới sẽ là [a, c] hay [c, b]. Ta tính f(c). Nếu f(c) = 0 thì c chính là nghiệm đúngcủa phương trình (thường thì f(c) ¹ 0). Nếu f(c) ¹ 0 ta so sánh dấu của f(c) với dấu của f(a) để suy ra khoảng phân li nghiệm thu nhỏ. Nếu f(c) trái dấu với f(a) thì khoảng phân li nghiệm thu nhỏ là [a, c] . Nếu f(c) cùng dấu với f(a) thì khoảng phân li nghiệm thu nhỏ là [c, b] . Như vậy sau khi chia đôi khoảng [a,b] ta được khoảng phân li nghiệm thu nhỏ là [a, c] hay [c, b], ký hiệu là [a1, b1] , nó nằm trong khoảng [a, b] và chỉ dài bằng nửa khoảng [a, b] túc là 1 b - a = (b - a) 1 1 2 36
52. Tiếp tục chia đôi khoảng [a1, b1] và làm như trên ta sẽ được khoảng phân li nghiệm thu nhỏ mới, ký hiệu là [a2, b2], nó nằm trong khoảng [a1, b1] tức là trong [a, b] và chỉ dài bằng nửa khoảng [a1, b1] : 1 1 b - a = (b - a ) = (b - a) 2 2 2 1 1 22 Lặp lại việc làm trên đến lần thứ n ta được khoảng phân li nghiệm thu nhỏ thứ n n, ký hiệu là [an, bn] , nó nằm trong [a, b] và chỉ dài bằng 1/2 của [a, b] : (b - a) a ≤ α ≤ b ; b - a = n n n n 2n Vậy có thể lấy an làm giá trị gần đúng của α , lúc đó sai số là (b - a) α - a ≤b - a = (2.10) n n n 2n cũng có thể lấy bn làm giá trị gần đúng của α , lúc đó sai số là (b - a) α - b ≤b - a = (2.11) n n n 2n Do đó với n đủ lớn, an, hay bn đều đủ gần α . Khi n ♦ × thì an ♦ α , bn ♦ α . Ví dụ 2.5: Tìm nghiệm gần đúng của phương trình : f(x) = x3 - x - 1 = 0, biết [1, 2] là khoảng phân li nghiệm, đã tìm ở trên Giải: Ta có : α [1 , 2] và f(1) = 1 - 1 - 1 0 Ta chia đôi khoảng [1, 2] điểm chia là 3/2. 3 3 2 3 f( ) = ( ) - - 1 > 0 trái dấu với f(1) . Vậy α  [1, 3/2]. 2 2 2 Ta chia đôi khoảng [1, 3/2], điểm chia là 5/4. Ta có f(5/4) 0 , trái dấu với f(5/4). Vậy α  [5/4; 11/8]. Ta chia đôi khoảng [5/4; 11/8] , điểm chia là 21/16. Ta có f(21/16) 0, trái dấu với f(21/16). Vậy α  [21/16; 43/32]. Ta dừng quá trình chia đôi tại đây và lấy 21/16 = 1.3125 hay 43/32 = 1.34375 làm giá trị gần đúng của α thì sai số không vượt quá 1/25 = 1/32 = 0.03125. 2.6. Phương pháp lặp Giả sử phương trình f(x) = 0 có nghiệm thực α phân li trong [a, b]. Trước hết ta chuyển phương trình về dạng tương đương x = φ(x) (2.12) Sau đó ta chon một số x0 nào đó ∈ [a, b] làm xấp xỉ đầu rồi tính dần dãy số xntheo qui tắc xn = φ(xn - 1), n = 1, 2, (2.13) x0 cho trước ∈ [a, b] (2.14) Quá trình tính này được lặp đi lặp lại nên phương pháp này gọi là phương pháp lặp , hàm φ gọi là hàm lặp. Người ta chứng minh được rằng : Dãy x0, x1, x2, sẽ tiến dần đến nghiệm đúng α của phương trình (2.1), nếu chọn hàm φ(x) sao cho trị tuỵệt đối của hàm φ’(x) nhỏ 37
53. hơn q 0 ta có thể chọn x0 ∈ [a, b] một cách bất kì , còn nếu φ’(x) < 0 thì phải chọn theo qui tắc : (a + b) (a+ b) x = a khi a <α < 0 2 (a+ b) x = b khi <α < b (2.15) 0 2 a+ b Muốn biết α thuộc nữa khoảng nào ta chỉ cần tính f( ) rồi so sánh dấu của 2 nó với dấu của f(a). Và dừng quá trình tính khi x n - x n-1 < sai số cho phép. 3. Giải hệ thống phương trình đại số tuyến tính Mục tiêu: - Xác định được các phương pháp tìm nghiệm của hệ phươngtrình tuyến tính; - Biết cách đánh giá sai số của phương pháp. 3.1. Phát biểu bài toán Trong mục này, ta xét việc giải phương trình đại số tuyến tính n phương trình n ẩn : a x +a x +a x =a a x +a x +a x =a (3.1) +⋯ ax +ax +⋯+ax =a trong đó aij (i,j= 1,n) là những số đã biết, gọi là các hệ số của hệphương trình +⋯ (3.1); ain+1 (i=1,n) cũng là các số đã biết, gọi là vế phải của hệ thống phương trình (3.1); xi (i=1,n) là các ẩn số phải tìm. Ký hiệu : a a a a a a A = a a a gọi là ma trận hệ số của hệ phương trình (3.1) a x a x b= và x= a x gọi là vectơ vế phải và vectơ ẩn số của hệ phương trình (3.1). Hệ phương trình có thể viết gọn dưới dạng : Ax = b (3.2) Nếu ma trận hệ số A không suy biến, nghĩa là : a a a a a a detA = 0 a a a ≠ thì hệ phương trình (3.1) có nghi ệm duy nhất. 38
54. Thật vậy, vì detA 0 nên tồn tại ma trận nghịch đảo A . Nhân bên trái hai vế của (3.2) với A , nhận được : ≠ A Ax = A b x = A b (3.3) Như vậy, (3.3) cho ta nghiệm của hệ phương trình (3.1) và nghiệm ấy là duy nhất. Ta đã biết phương pháp Crame giải đúng hệphương trình (3.1) bằng công thức : X = , (i =1,n ) ∆ Trong đó : = detA; là định thức cấp n thu được từ bằng cách thay cột thứ i của bằng cột vế∆ phải b của hệphương trình (3.1). 3.2. Phương pháp∆ Gauss ∆ ∆ ∆Phương pháp Gaoxơ là một phương pháp được dùng phổ biến giải hệ phương trình (3.1) bằng cách khử dần các ẩn số, không phải tính một định thức nào. a. Nội dung phương pháp Để đơn giản việc trình bày, xét hệ 4 phương trình 4 ẩn số sau: a ( )x +a ( )x +a ( )x +a ( )x =a ( ) a ()x +a ()x +a ()x +a ()x =a () (3.4) ⎧a ()x +a ()x +a ()x +a ()x =a () ⎪ () () () () () a x +a x +a x +a x =a ⎨ ⎪ ⎩ Nội dung cơ bản của phương pháp Gaoxơ là khử dần các ẩn số để đưa hệ (3.4) về hệ “tam giác” tương đương (ma trận hệ số của hệ là ma trận tam giác trên): x +a ( )x +a ( )x +a ( )x =a ( ) x +a ( )x +a ( )x =a ( ) (3.5) ⎧ x +a ( )x =a ( ) ⎪ ( ) x=a ⎨ ⎪ Sau⎩ đó giải hệtừ dưới lên trên. Quá trình đưa hệ (3.4) về hệ (3.5) gọi là quá trình thuận, quá trình giải hệ (3.5) gọi là quá trình ngược. i) Quá trình thuận: (0) (0) Khử x1. Giả sử a11 ¹ 0 (a11 gọi là trụ thứ nhất). Chia phương trình đầu của (0) hệ (3.4) cho a11 , ta nhận được : (1) (1) (1) (1) x1 + a12 x2 + a13 x3 + a14 x4 = a15 (3.6) (1) (0) với a1j /a11 ; j = 2, 3, 4,5 Dùng phương trình (3.6) khử x1 trong ba phương trình còn lại của hệ (3.6). Muốn thế, đem phương trình thứ hai của hệ (3.4) trừ phương trình (3.6) đã nhân với (0) (0) a21 ; đem phương trình thứ ba của hệ (3.4) trừ phương trình (3.6) đã nhân với a31 ; (0) đem phương trình thứ tư của hệ (3.4) trừ phương trình (3.6) đã nhân với a41 . Kết quả nhận được hệ ba phương trình sau : 39