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