Tóm tắt luận văn Thạc sĩ Khoa học: Các nguyên lý và kỹ thuật thường dùng trong các bài toán tổ hợp

Luận văn sẽ cung cấp thêm một tài liệu về Tổ hợp đáp ứng được phần nào lòng yêu thích Toán học của học sinh, phục vụ cho công tác bồi dưỡng học sinh giỏi. Đồng thời đây cũng là một tài liệu để mọi người quan tâm đến Tổ hợp tham khảo.
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: Các nguyên lý và kỹ thuật thường dùng trong các bài toán tổ hợp 1 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG ---------------------------------- DƯƠNG THỊ THANH THỦY CÁC NGUYÊN LÝ VÀ KỸ THUẬT THƯỜNG DÙNG TRONG CÁC BÀI TOÁN TỔ HỢP Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60 46 40 Tóm tắt luận văn Thạc sĩ khoa học Đà Nẵng – năm 2012 2 Công trình ñược hoàn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học : Tiến Sĩ Nguyễn Duy Thái Sơn Phản biện 1:……………………………………… Phản biện 2:……………………………………… Luận văn sẽ ñược bảo vệ trước Hội ñồng chấm Luận văn tốt nghiệp thạc sĩ khoa học họp tại Đại học Đà Nẵng, ngày 01-02 tháng 12 năm 2012. Có thể tìm hiểu luận văn tại: - 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. 3 MỞ ĐẦU 1. Lý do chọn ñề tài Trong những năm qua, Tổ hợp ñã trở thành một phần căn bản trong sách giáo khoa cho học sinh các trường phổ thông và cả trong giáo trình dành cho sinh viên các trường ñại học. Các nguyên lý và kỹ thuật trong Tổ hợp ngày càng có nhiều ứng dụng trong nhiều lĩnh vực khác, ñặc biệt là trong khoa học máy tính và lý thuyết toán tử. Các bài toán trong Tổ hợp không chỉ thách thức các nhà nghiên cứu mà còn xuất hiện rất thường xuyên trong các cuộc thi Toán học, nhất là trong các kỳ thi Olympic Toán học quốc tế (IMO). Tuy nhiên, hiện nay tài liệu tiếng Việt về Tổ hợp chưa nhiều. Sinh viên và học sinh Việt Nam thường tỏ ra lúng túng trước các bài toán Tổ hợp. Trong luận văn này, tôi sẽ cố gắng tìm hiểu các nguyên lý và kỹ thuật (từ cơ bản ñến nâng cao) thường dùng trong các bài toán Tổ hợp. Bản thân là một giáo viên phổ thông, tôi hi vọng sẽ khám phá ñược nhiều ñiều thú vị khi rèn luyện các kỹ năng Tổ hợp. Mong rằng luận văn này - sau khi ñược hoàn thành - sẽ cung cấp thêm một tài liệu về Tổ hợp ñáp ứng ñược phần nào lòng yêu thích Toán học của học sinh, phục vụ cho công tác bồi dưỡng học sinh giỏi. Đồng thời ñây cũng là một tài liệu ñể mọi người quan tâm ñến Tổ hợp tham khảo. Với những lý do trên, tôi chọn ñề tài “Các nguyên lý và kỹ thuật thường dùng trong các bài toán Tổ hợp” ñể nghiên cứu. 2. Mục ñích và nhiệm vụ nghiên cứu Tôi mong muốn tìm kiếm ñược nhiều tài liệu từ các nguồn khác nhau, nghiên cứu kỹ càng các tài liệu ñó, cố gắng lĩnh hội ñầy ñủ các kiến thức cũ và mới về Tổ hợp ñể có thể trình bày lại các kiến thức ñó trong 4 luận văn này theo một thể khép kín và hy vọng luận văn có thể ñược sử dụng như một tài liệu tham khảo bổ ích cho học sinh và giáo viên các trường trung học phổ thông và những người quan tâm ñến Tổ hợp. 3. Đối tượng và phạm vi nghiên cứu 3.1. Đối tượng nghiên cứu: Nguyên lý và các kỹ thuật cơ bản trong lý thuyết Tổ hợp. 3.2. Phạm vi nghiên cứu: Các bài toán Tổ hợp. 4. Phương pháp nghiên cứu Cơ bản sử dụng phương pháp nghiên cứu tài liệu (sách, báo và các tài liệu trên internet có liên quan ñến ñề tài của luận văn) ñể thu thập thông tin nhằm tìm hiểu các nguyên lý và kỹ thuật cơ bản trong Tổ hợp, nghiên cứu cách giải và tập hợp các bài toán phục vụ cho yêu cầu của ñề tài. 5. Giả thuyết khoa học Xây dựng một giáo trình có tính hệ thống, khép kín và có thể giảng dạy ñược cho các học sinh chuyên toán bậc trung học phổ thông. Xây dựng ñược một hệ thống các bài toán (cũ và mới) với các mức ñộ khó dễ khác nhau ứng dụng các nguyên lý và kỹ thuật trong Tổ hợp. 6. Cấu trúc luận văn:Ngoài phần mở ñầu và kết luận, luận văn có nội dung chính sau - Chương 1: Hoán vị và tổ hợp - Chương 2: Hệ số nhị thức và hệ số ña thức - Chương 3: Nguyên lý bù trừ. 5 Chương 1 HOÁN VỊ VÀ TỔ HỢP 1.1. Hai nguyên lý ñếm cơ bản Trong cuộc sống hằng ngày, chúng ta thường phải liệt kê “các sự kiện” như: Sắp xếp các ñối tượng theo một cách nào ñó, phân chia các vật theo một ñiều kiện nhất ñịnh, phân phối sản phẩm theo một ñặc ñiểm kỹ thuật nhất ñịnh, v.v… Chẳng hạn, ta có thể ñối mặt với các bài toán ñếm có dạng: “Có bao nhiêu cách sắp xếp 5 người nam và 3 người nữ trong một hàng sao cho không có hai người nữ nào ñứng kề nhau?”. “Có bao nhiêu cách chia một nhóm gồm 10 người thành 3 nhóm con bao gồm một nhóm con 4 người, một nhóm con 3 người, một nhóm con 2 người và giữ lại 1 người.” Đó là hai ví dụ ñơn giản của bài toán ñếm liên quan ñến cái gọi là: “hoán vị” và “tổ hợp”. Trước khi giới thiệu trong phần tiếp theo thế nào là hoán vị và tổ hợp, ta hãy phát biểu hai nguyên lý ñếm cơ bản: Nguyên lý cộng (AP-Addition principle). Giả sử có: n1 cách ñể sự kiện n2 E1 xảy ra, cách ñể sự kiện E2 xảy ra, ... nk cách ñể sự kiện Ek xảy ra, trong ñó k > 1. Nếu các cách ñể xảy ra các sự kiện khác nhau nói trên là từng ñôi một rời nhau thì số cách ñể ít nhất một trong các sự kiện E1 ,E2,..., hoặc Ek xảy ra là : n1 + n2 +... + nk = ∑i=1 ni . k  ...