Tóm tắt luận văn Thạc sĩ Khoa học: Nguyên lý bao hàm & loại trừ và ứng dụng

Đề tài góp phần nghiên cứu, hỗ trợ học sinh khi học phần tổ hợp, giải một số bài toán số học mà việc giải chúng có nhiều ứng dụng trong trong các lĩnh vực toán học, tin học. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Tóm tắt luận văn Thạc sĩ Khoa học: Nguyên lý bao hàm & loại trừ và ứng dụng12BỘ GIÁO DỤC VÀ ĐÀO TẠOCông trình ñược hoàn thành tạiĐẠI HỌC ĐÀ NẴNGĐẠI HỌC ĐÀ NẴNGTRẦN LÊ HẠNH ĐOANNgười hướng dẫn khoa học: PGS.TSKH.Trần QuốcChiếnNGUYÊN LÝ BAO HÀM & LOẠI TRỪ VÀPhản biện 1: TS. Cao Văn NuôiỨNG DỤNGPhản biện 2: PGS. TS. Trần Đạo DõngChuyên ngành: Phương pháp Toán sơ cấpMã số: 60.46.40Luận văn sẽ ñược bảo vệ tại Hội ñồng chấm Luận văntốt nghiệp thạc sĩ khoa học tại Đại học Đà Nẵng ngày29 tháng 05 năm 2011.TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌCCó thể tìm hiểu luận văn tại:Đà Nẵng - Năm 2011-Trung tâm thông tin - Học liệu, Đại học Đà Nẵng-Thư viện trường Đại học sư phạm, Đại học ĐàNẵng.43MỞ ĐẦU2. Mục ñích nghiên cứuTừ các ứng dụng nguyên lý bao hàm và loại trừ giải lớp các bài1. Lý do chọn ñề tàiCùng với sự phát triển với tốc ñộ nhanh của công nghệ thôngtoán tương tự cụ thể.tin, lý thuyết tổ hợp ñã trở thành lĩnh vực toán học quan trọng và cần3. Đối tượng nghiên cứuthiết cho nhiều lĩnh vực khoa học và ứng dụng. Nhiều bài toán hiệnĐối tượng nghiên cứu: nguyên lý bao hàm và loại trừ.nay ñược giải quyết bằng cách quy chúng về các bài toán tổ hợp.Phạm vi nghiên cứu: nội dung của nguyên lý bao hàm và loạiLý thuyết tổ hợp nghiên cứu việc phân bố, sắp xếp các phần tửcủa một hoặc nhiều tập hợp, thoả mãn một số ñiều kiện nào ñó.Các bài toán tổ hợp rất phong phú và ña dạng: bài toán tồn tại,bài toán ñếm, bài toán liệt kê và bài toán tối ưu. Trong các bài toánñó thì bài toán ñếm ñược ứng dụng rộng rãi và ña dạng. Từ các cấuhình tổ hợp cơ bản người ta hình thành nên hệ thống các cấu hình tổhợp mở rộng và nâng cao.trừ, ứng dụng của nguyên lý này.4. Phương pháp nghiên cứuGián tiếp thông qua các tài liệu: sách, giáo trình, tạp chí toánhọc tuổi trẻ, truy cập các trang web.Trực tiếp thông qua sự hướng dẫn của thầy và việc trao ñổithảo luận với các bạn.5. Ý nghĩa khoa học và thực tiễnCông thức xác ñịnh số phần tử của hợp một số tập hữu hạnĐề tài góp phần nghiên cứu, hỗ trợ học sinh khi học phần tổthường ñược dùng trong nhiều bài toán ñếm. Một trong những cônghợp, giải một số bài toán số học mà việc giải chúng có nhiều ứngthức ñó là nguyên lý bao hàm và loại trừ của tập hợp. Sử dụngdụng trong trong các lĩnh vực toán học, tin học.nguyên lý này và phối hợp một số phương pháp khác trên tập hợp6. Nội dung luận vănchẳng hạn phương pháp ánh xạ, ta có thể giải một số dạng toán.1) Mở ñầuTrong lý thuyết tổ hợp, nguyên lý bao hàm và loại trừ là2) Chương 1. Đại cương về tổ hợpphương pháp ñếm nâng cao giải các bài toán ñếm, nó có nhiều ứng3) Chương 2. Nguyên lý bao hàm và loại trừdụng hay. Trong các kỳ thi học sinh giỏi quốc gia, thi Olympic toán4) Chương 3. Ứng dụng của nguyên lý bao hàm và loại trừquốc tế, thi Olympic sinh viên giữa các trường ñại học và cao ñẳng5) Kết luậncác bài toán liên quan ñến dạng này hay ñược ñề cập và thường thuộcloại rất khó.Chính vì các lý do trên,tôi ñã nghiên cứu và chọn:“NGUYÊN LÝ BAO HÀM & LOẠI TRỪ VÀ ỨNG DỤNG ” làmñề tài luận văn thạc sĩ của mình.65CHƯƠNG 1. ĐẠI CƯƠNG VỀ TỔ HỢPNếu ta ký hiệu số chỉnh hợp có lặp chập k của n phần tử của Abằng AR (n, k) thì1.1 Sơ lược lịch sửAR (n, k) = nk1.2 Các quy tắc ñếm cơ bản1.2.1 Quy tắc tương ứng một – một. Nếu tồn tại tương ứng1.3.2 Chỉnh hợp không lặp• Định nghĩa. Một chỉnh hợp không lặp chập k của n phần tửmột – một giữa các phần tử của các tập hữu hạn A 1 và A 2 , thì A 1khác nhau là một bộ có thứ tự gồm k thành phần lấy từ n phần tử ñãvà A 2 có cùng số các phần tử.cho. Các thành phần không ñược lặp lại. Chỉnh hợp không lặp ñơnGiả sử A 1 , A 2 ,...A n là các tập hữu hạn bất kỳ. Ta ñịnh nghĩagiản gọi là chỉnh hợp.tích Đề-các của A 1 , A 2 ,...A n , kí hiệu là A 1 × A 2 ...× A n , là tậpbao gồm tất cả các bộ có thứ tự( a1 , a2 , ..., an )gồm n thành phầna1 , a2 , ..., an sao cho a1 ∈ A1 , a2 ∈ A2 ,..., an ∈ An1.2.2 Quy tắc nhân. Nếu A 1 , A 2 ,...A n là các tập hữu hạn bấtkỳ và A 1 × A 2 ...× A n là tích Đề các của các tập ñó thìA1 × A2 × ... × An = A1 A2 ... An1.2.3 Quy tắc cộng. Nếu A 1 , A 2 ,...A n là các tập hữu hạn ñôimột rời nhau, tức là Ai ∩ AJ = φ nếu i ≠ j thìKí hiệu số các chỉnh hợp chập k của n phần tử của A là A(n, k)ta có n!A ( n, k ) =  ( n − k ) !01.3 Cấu hình tổ hợp cơ bản1.3.1 Chỉnh hợp lặp• Định nghĩa. Một hoán vị của n phần tử khác nhau là mộtcách sắp xếp thứ tự các phần tử ñó.Hoán vị có thể coi là trường hợp riêng của chỉnh hợp khônglặp chập k của n trong ñó k = n. Ta có số hoán vị làP(n) = n!1.3.4 Hoán vị vòng quanhSố hoán vị vòng quanh của n phần tử khác nhau ( Qn ) ñượctính bằng công thứcQn = (n − 1)!• Định nghĩa. Một chỉnh hợp lặp chập k của n phần tử khácnhau là một bộ có thứ tự gồm k thành phần lấy từ n phần tử ñã cho.Các thành phần có thể ñược lặp lại.khi k > n1.3.3 Hoán vị không lặpA1 ∪ A2 ∪ ... ...