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

Đề 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ý đó.
Nội dung trích xuất từ tài liệu:
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ỘITRƯỜ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ỘITRƯỜ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- 2014Mục lụcMở đầu 31 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 . . . . . . . . . . . . . . . . . . . . . . . . . 202 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 . . . . . . . . . . . . . . . . . . . . 513 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 1Lời cảm ơnTô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ănNhỉ. Thầy đã dành nhiều thời gian hướng dẫn cũng như giải đáp các thắcmắ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ơ - Tinhọc, Phòng Sau đại học - Trường Đại học Khoa học Tự nhiên- Đại học Quốcgia 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 độngviên tôi trong suốt quá trình học tập và thực hiện luận văn. 2Mở đầuTư 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ọcvà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ánhọ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óichung và của toán rời rạc nói riêng. Nó không chỉ có nội dung phong phú, đadạ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áctính chất nào đó. Để làm được việc này, ngoài việc sử dụng hai quy tắc đếmcơ bản, ...