Luận văn Thạc sĩ Khoa học: Nâng cao hiệu quả bài toán sắp xếp với giải thuật song song

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:80

Thêm vào BST

Báo xấu

28
lượt xem 4
download

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

Đề tài nghiên cứu trình bày một số lý thuyết cơ bản về nguyên lý quy nạp và hai quy tắc đếm cơ bản, hoán vị, chỉnh hợp, tổ hợp, nhị thức Newton và đồ thị cây. Tác giả đã nhắc lại được các kiến thức cơ bản về tổ hợp trong chương trình toán trung học phổ thông. Đồng thời nêu được một số khái niệm về tổ hợp suy rộng, đó là: Hoán vị lặp, chỉnh hợp lặp, tổ hợp lặp. Trình bày bốn nguyên lý cơ bản trong tổ hợp và các ví dụ áp dụng các nguyên lý đó.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học: Nâng cao hiệu quả bài toán sắp xếp với giải thuật song song

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------ NGUYỄN NGỌC MAI MỘT VÀI NGUYÊN LÝ VÀ BÀI TOÁN TỔ HỢP LUẬN VĂN THẠC SỸ TOÁN HỌC HÀ NỘI- 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------ NGUYỄN NGỌC MAI MỘT VÀI NGUYÊN LÝ VÀ BÀI TOÁN TỔ HỢP Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60460113 LUẬN VĂN THẠC SỸ TOÁN HỌC Người hướng dẫn khoa học PGS. TS. ĐÀM VĂN NHỈ HÀ NỘI- 2014
Mục lục Mở đầu 3 1 Kiến thức chuẩn bị 5 1.1 Nguyên lý quy nạp . . . . . . . . . . . . . . . . . . . . 5 1.2 Hai quy tắc đếm cơ bản . . . . . . . . . . . . . . . . . . 8 1.3 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.5.1 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . 14 1.5.2 Ứng dụng trong số học . . . . . . . . . . . . . . 16 1.6 Nhị thức Newton . . . . . . . . . . . . . . . . . . . . . 18 1.7 Đồ thị cây . . . . . . . . . . . . . . . . . . . . . . . . . 20 2 Một vài nguyên lý trong tổ hợp 26 2.1 Nguyên lý Dirichlet . . . . . . . . . . . . . . . . . . . . 26 2.1.1 Nguyên lý Dirichlet . . . . . . . . . . . . . . . . 26 2.1.2 Nguyên lý Dirichlet áp dụng trong hình học tổ hợp 31 2.2 Nguyên lý bù trừ . . . . . . . . . . . . . . . . . . . . . 34 2.3 Nguyên lý cực hạn . . . . . . . . . . . . . . . . . . . . . 42 2.4 Nguyên lý bất biến . . . . . . . . . . . . . . . . . . . . 51 3 Một vài đồng nhất thức trong tổ hợp 60 3.1 Xây dựng đồng nhất thức qua hệ phương trình . . . . . 60 3.2 Xây dựng đồng nhất thức qua số phức . . . . . . . . . 66 3.3 Xây dựng đồng nhất thức qua hàm sinh . . . . . . . . . 69 3.3.1 Khái niệm hàm sinh . . . . . . . . . . . . . . . . 70 3.3.2 Một số đồng nhất thức liên quan đến hàm sinh . 70 3.3.3 Ứng dụng của hàm sinh . . . . . . . . . . . . . . 71 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . 78 1
Lời cảm ơn Tôi xin được bày tỏ lòng kính trọng và biết ơn sâu sắc đến PGS.TS Đàm Văn Nhỉ. Thầy đã dành nhiều thời gian hướng dẫn cũng như giải đáp các thắc mắc của tôi trong suốt quá trình tôi thực hiện đề tài. Tôi xin gửi lời cảm ơn chân thành tới các thầy cô Khoa Toán - Cơ - Tin học, Phòng Sau đại học - Trường Đại học Khoa học Tự nhiên- Đại học Quốc gia Hà Nội; các thầy cô đã tham gia giảng dạy khóa cao học 2011-2013. Cuối cùng, tôi xin chân thành cảm ơn gia đình và bạn bè đã luôn động viên tôi trong suốt quá trình học tập và thực hiện luận văn. 2
Mở đầu Tư duy về tổ hợp xuất hiện từ rất sớm trong lịch sử phát triển của nhân loại. Tuy nhiên, lý thuyết tổ hợp được xem hình thành như một ngành toán học vào khoảng thế kỷ 17 bằng một loạt các công trình nổi tiếng của các nhà toán học như Passcal, Fermat, Leibniz, Euler, . . . . Kể từ sau khi tin học ra đời, lý thuyết tổ hợp phát triển ngày càng mạnh mẽ. Các vấn đề liên quan đến lý thuyết tổ hợp là một bộ phận quan trọng, hấp dẫn và lí thú của toán học nói chung và của toán rời rạc nói riêng. Nó không chỉ có nội dung phong phú, đa dạng, mà còn có nhiều ứng dụng trong thực tế đời sống. Trong toán sơ cấp, tổ hợp cũng xuất hiện với nhiều bài toán hay với độ khó cao. Khi giải các bài toán tổ hợp, ta phải liệt kê, đếm các đối tượng theo các tính chất nào đó. Để làm được việc này, ngoài việc sử dụng hai quy tắc đếm cơ bản, các kiến thức về hoán vị, chỉnh hợp, tổ hợp, trong nhiều bài toán ta phải sử dụng một số nguyên lý khác trong tổ hợp. Vì vậy, để hiểu rõ và nắm bắt sâu hơn vể vấn đề này, tôi đã chọn đề tài Một vài nguyên lý và bài toán tổ hợp. Luận văn đã trình bày một số nguyên lý cơ bản trong tổ hợp và xây dựng một số bài toán áp dụng. Luận văn gồm phần mở đầu, ba chương, kết luận và danh mục tài liệu tham khảo. Chương 1 : Kiến thức chuẩn bị. Trong chương này, tác giả đã trình bày một số lý thuyết về nguyên lý quy nạp, hai quy tắc đếm cơ bản, hoán vị, chỉnh hợp, tổ hợp, nhị thức Newton và đồ thị cây. Chương 2 : Một vài nguyên lý trong tổ hợp. Chương 2 gồm 4 nội dung chính, trình bày bốn nguyên lý cơ bản trong tổ hợp và các ví dụ áp dụng các nguyên lý đó. Cụ thể là: Mục 2.1 trình bày nguyên lý thứ nhất: Nguyên lý Dirichlet. Nguyên lý này còn được gọi là nguyên lý lồng chim bồ câu. Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì ít nhất có ngăn 3
có nhiều hơn 1 con chim. Phát triển dạng toán này, Piter Gustave Dirichlet đã đưa ra một nguyên lý chứng minh toán học đơn giản, được phát biểu như sau: "Nếu có N đồ vật được đặt vào k hộp thì tồn tại một hộp chứa ít nhất N + 1 đồ vật." k Mục 2.2 trình bày Nguyên lý bù trừ. Khi hai công việc có thể làm đồng thời, chúng ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả hai việc. Cộng số cách thực hiện mỗi việc sẽ dẫn đến sự trùng lặp, vì những cách làm cả hai công việc sẽ được tính hai lần. Để tính đúng số cách thực hiện nhiệm vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai công việc. Nguyên lý này được mở rộng cho trường hợp đếm số phần tử của hợp các tập hợp bất kì. Đó là Nguyên lý bù trừ. Nguyên lý thứ 3 là Nguyên lý cực hạn, được trình bày trong mục 2. 3. Nguyên lý này chỉ ra rằng tồn tại phần tử lớn nhất và phần tử nhỏ nhất của một tập hợp hữu hạn. Nguyên lý này có rất nhiều ứng dụng trong việc giải các bài toán tổ hợp, giải một số phương trình nghiệm nguyên, chứng minh các bất đẳng thức, . . . . Cuối cùng, mục 2. 4 trình bày nguyên lý thứ 4 là Nguyên lý bất biến. Trong mục này, tác giả đã trình bày hai mẫu bài toán tổng quát thường được giải bằng nguyên lý bất biến và đưa ra một ví dụ sử dụng nguyên lý bất biến. Chương 3. Một vài đồng nhất thức trong tổ hợp. Chương này trình bày một số ví dụ về xây dựng đồng nhất thức trong tổ hợp qua hệ phương trình, số phức và hàm sinh, . . . 4
Chương 1 Kiến thức chuẩn bị 1.1 Nguyên lý quy nạp Mệnh đề 1.1. [Nguyên lý thứ nhất]. Nếu mệnh đề P (n), phụ thuộc vào số tự nhiên n thỏa mãn: (i) P (α) đúng với một α ∈ N. (ii) P (n + 1) đúng khi P (n) đúng, ở đó n ≥ α, n ∈ N thì P (n) đúng với mọi số tự nhiên n ≥ α. Mệnh đề 1.2. [Nguyên lý thứ hai]. Nếu mệnh đề P (n), phụ thuộc vào số tự nhiên n thỏa mãn: (i) P (α) đúng với một α ∈ N. (ii) P (n + 1) đúng khi P (α), P (α + 1), ..., P (n) đúng, ở đó n ≥ α, n ∈ N, thì P (n) đúng với mọi số tự nhiên n ≥ α. Cách chứng minh một định lý hay một bài toán có sử dụng nguyên lý quy nạp được gọi là phép quy nạp hay phương pháp quy nạp toán học. Sau đây, ta sẽ xét một số ví dụ áp dụng hai nguyên lý này. Ví dụ 1.1. Chứng minh rằng, với số nguyên n ≥ 1 và số thực a > 0 ta luôn có đồng nhất thức n X (−1)k Cnk n!an = Qn . ak + 1 k=1 (1 + ka) k=1 Lời giải. Trước tiên, ta chứng minh bằng quy nạp theo n rằng Z 1 n!an (1 − xa )n dx = Qn . 0 k=1 (1 + ka) 5
Thật vậy Với n = 1 ta có 1 xa+1
1 1!a1 Z a
a (1 − x )dx = x −
= = . 0 a+1 0 a+1 1 + 1.a Suy ra khẳng định đúng với n = 1. Đặt Z 1 In = (1 − xa )n dx. 0 Giả sử n!an In = Qn . k=1 (1 + ka) Ta phải chứng minh (n + 1)!an+1 In+1 = Qn+1 . k=1 (1 + ka) Ta có Z 1 Z 1 a n+1 In+1 = (1 − x ) dx = (n + 1)a xa (1 − xa )n dx = (n + 1)a(In − In+! ). 0 0 Hay (n + 1)a In+1 = In . 1 + (n + 1)a Theo giả thiết quy nạp ta có (n + 1)!an+1 In+1 = Qn+1 . k=1 (1 + ka) Suy ra khẳng định trên đúng với n + 1. Vậy khẳng đinh trên đúng với mọi n ≥ 1. Từ đó suy ra n n 1 1 (−1)k C k n!an X X Z Z n k = (−1) Cnk ak x dx = (1 − xa )n dx = Qn . ak + 1 0 0 k=1 (1 + ka) k=0 k=0 Ví dụ 1.2. Chứng minh rằng với số nguyên n > 0 ta có đồng nhất thức 1.2 + 2.22 + · · · + n.2n = (n − 1)2n+1 + 2. 6
Lời giải. Ta chứng minh bằng quy nạp theo n. + Với n = 1 ta có 1.2 = 2 = (1 − 1)21+1 + 2. Chứng tỏ kết luận đúng với n = 1. + Giả sử kết luận đúng với n ≥ 1. Khi đó 1.2 + 2.22 + · · · + n.2n = (n − 1)2n+1 + 2. + Ta phải chứng minh kết luận đúng với n + 1. Tức là 1.2 + 2.22 + · · · + n.2n + (n + 1)2(n+1) = n2n+2 + 2. Thật vậy, ta có 1.2 + 2.22 + · · · + n.2n + (n + 1)2(n+1) = (n − 1)2n+1 + 2 + (n + 1)2n+1 = n2n+2 + 2. Chứng tỏ kết luận đúng với n + 1. Vậy khẳng định đúng với mọi số nguyên n > 0. Ví dụ 1.3. Dãy (an ) được cho như sau: a0 = 1, a1 = 3, a2 = 6, a3 = 10, a4 = 15, a5 = 21, .... Xác định (an ) theo n và chứng minh bất đẳng thức 1 1 1 1 1 1 T = 1− 1− 1− ... 1 − < + . 3 6 10 an 3 n Lời giải. Ta có a0 = 1, a1 = 3 = a0 + 1 + 1, a2 = 6 = a1 + 2 + 1, a3 = 10 = a2 + 3 + 1, a4 = 15 = a3 + 4 + 1, a5 = 21 = a4 + 5 + 1, ... Suy ra an = an−1 + n + 1. Điều này dễ dàng có được bằng chứng minh quy nạp. (n + 1)(n + 2) Vậy an = 1 + 2 + 3 + 4 + ... + n + n + 1 = . 2 1 ak − 1 (k + 1)(k + 2) − 2 k(k + 3) Suy ra 1 − = = = . ak ak (k + 1)(k + 2) (k + 1)(k + 2) Như vậy 1 1 1 1− = 1− 1+ . ak k+1 k+2 7
Suy ra 1 1 1 1 1 1 T = 1− 1+ 1− 1+ ... 1 − 1+ 2 3 3 4 n+1 n+2 1 1 1 1 1 1 = 1 − 2 1 − 2 1 − 2 ... 1 − 2 1+ 2 3 4 5 (n + 1) (n + 2) 2 2 1 3 − 1 4 − 1 5 − 1 2 2 (n + 1) − 1 1 = . . . 1 + 2 32 42 52 (n + 1)2 (n + 2) 2 2 2 2 2.3.4 .5 . . . (n − 1) .n (n + 1)(n + 2)(n + 3) = 2.32 .42 .52 . . . (n − 1)2 .n2 (n + 1)2 (n + 2) n+3 n+3 1 1 = < = + . 3(n + 1) 3n 3 n (n + 1)(n + 2) 1 1 Vậy an = và T < + . 2 3 n 1.2 Hai quy tắc đếm cơ bản Chương trình toán phổ thông lớp 11 đã trang bị cho học sinh hai quy tắc đếm cơ bản, đó là quy tắc cộng và quy tắc nhân. Đây là hai công cụ quan trọng giúp học sinh giải được một số bài toán tổ hợp đơn giản. Quy tắc cộng được phát biểu như sau: Giả sử, một công việc có thể được thực hiện theo một trong k phương án A1 , A2 , . . . , Ak . Có n1 cách thực hiện phương án A1 , n2 cách thực hiện phương án A2 , . . . , nk cách thực hiện phương án Ak . Khi đó công việc có thể được thực hiện bởi n1 + n2 + · · · + nk cách. Bản chất của quy tắc cộng là công thức tính số phần tử của hợp n tập hợp hữu hạn đôi một không giao nhau. Cụ thể ta có: Cho A1 , A2 , . . . , Ak là các tập rời nhau. Khi đó