Tóm tắt luận văn Thạc sĩ Khoa học: Ứng dụng công thức truy hồi giải toán sơ cấp

BỘ GIÁO DỤC VÀ ĐÀO TẠO<br /> ĐẠI HỌC ĐÀ NẴNG<br /> <br /> TRẦN THỊ THU HÀ<br /> <br /> ỨNG DỤNG CÔNG THỨC TRUY HỒI<br /> GIẢI TOÁN SƠ CẤP<br /> Chuyên ngành: Phương pháp toán sơ cấp<br /> Mã số : 60.46.01.13<br /> <br /> TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC<br /> <br /> Đà Nẵng – Năm 2015<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: PGS.TSKH. Trần Quốc Chiến<br /> <br /> Phản biện 1: TS. Phan Đức Tuấn<br /> Phản biện 2: GS.TS. Lê Văn Thuyết<br /> <br /> Luận văn đã được bảo vệ trước Hội đồng chấm Luận văn<br /> tốt nghiệp Thạc sĩ Khoa học họp tại Đại Học Đà Nẵng vào<br /> ngày 12 tháng 12 năm 2015.<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 /> 1<br /> MỞ ĐẦU<br /> 1. Lý do chọn đề tài<br /> Tổ hợp là ngành khoa học xuất hiện khá sớm vào đầu thế kỷ<br /> XVII, cho đến nay đã được áp dụng trong nhiều lĩnh vực khác nhau<br /> như lý thuyết số, hình học, đại số, xác suất thống kê, quy hoạch thực<br /> nghiệm…<br /> Các vấn đề liên quan đến lý thuyết tổ hợp là một bộ phận quan<br /> trọng, hấp dẫn của toán học nói chung và toán rời rạc nói riêng. Nó là<br /> một nội dung phong phú và được áp dụng nhiều trong thực tế cuộc<br /> sống. Trong toán sơ cấp, tổ hợp cũng xuất hiện rất nhiều trong các<br /> bài toán hay và khó.<br /> Một trong những chủ đề khá hay của lý thuyết tổ hợp đó là<br /> công thức truy hồi. Đây là một trong những kỹ thuật đếm cao cấp để<br /> giải các bài toán đếm và là công cụ rất hữu hiệu để giải các bài toán<br /> khác có liên quan.<br /> Vì vậy, tôi đã quyết định chọn đề tài : “Ứng dụng công thức<br /> truy hồi giải toán sơ cấp” để làm đề tài luận văn thạc sĩ của mình.<br /> 2. Mục tiêu nghiên cứu<br /> Nghiên cứu ứng dụng của công thức truy hồi trong giải toán sơ<br /> cấp.<br /> 3. Đối tượng và phạm vi nghiên cứu<br /> 3.1. Đối tượng nghiên cứu<br /> Công thức truy hồi.<br /> 3.2. Phạm vi nghiên cứu<br /> Công thức truy hồi, phương pháp giải và ứng dụng trong các<br /> bài toán sơ cấp.<br /> 4. Phương pháp nghiên cứu<br /> Nghiên cứu lý thuyết, phân tích, tổng hợp các dạng toán.<br /> <br /> 2<br /> 5. Ý nghĩa khoa học và thực tiễn của đề tài<br /> Đề tài nghiên cứu tính ứng dụng của công thức truy hồi.<br /> Giải quyết được các bài toán đặt ra từ thực tế.<br /> 6. Cấu trúc luận văn<br /> Ngoài phần mở đầu và kết luận, luận văn được chia làm ba<br /> chương:<br /> Chương 1: Cơ sở lý thuyết<br /> Chương 2: Công thức truy hồi<br /> Chương 3: Ứng dụng công thức truy hồi giải toán sơ cấp<br /> <br /> 3<br /> CHƯƠNG 1<br /> CƠ SỞ LÝ THUYẾT<br /> 1.1. TỔNG QUAN VỀ TỔ HỢP<br /> 1.1.1. Sơ lược về lịch sử<br /> 1.1.2. Bài toán tổ hợp<br /> a. Cấu hình tổ hợp và các dạng bài toán tổ hợp<br /> Cho các tập hợp<br /> ,<br /> ,…,<br /> . Giả sử là sơ đồ sắp xếp<br /> các phần tử , , … ,<br /> được mô tả bằng các quy tắc sắp xếp và<br /> , , …,<br /> là các điều kiện ràng buộc lên mỗi sắp xếp theo sơ đồ<br /> . Khi đó mỗi sắp xếp các phần tử của , , … ,<br /> thỏa mãn các<br /> điều kiện , , …,<br /> gọi là một cấu hình tổ hợp trên các tập<br /> , ,…,<br /> .<br /> Với các cấu hình tổ hợp, ta thường gặp bốn dạng bài toán sau:<br /> bài toán tồn tại, bài toán đếm, bài toán liệt kê, bài toán tối ưu.<br /> b. Bài toán đếm<br /> * Nguyên lý cộng và nguyên lý nhân<br /> } là một phân<br /> + Nguyên lý cộng. Giả sử { ,<br /> ,… ,<br /> hoạch của tập . Khi đó<br /> | | = | | + | | + ⋯ + | |.<br /> + Nguyên lý nhân. Giả sử một cấu hình tổ hợp được xây dựng<br /> qua bước, bước 1 có thể được thực hiện<br /> cách, bước 2 được thực<br /> hiện<br /> cách,…, bước được thực hiện<br /> cách. Khi đó, số cấu hình<br /> tổ hợp là<br /> . .…. .<br /> * Các cấu hình tổ hợp cơ bản<br /> + Chỉnh hợp lặp<br /> Định nghĩa 1.1. Một chỉnh hợp lặp chập của phần tử khác<br /> nhau là một bộ có thứ tự gồm thành phần lấy từ phần tử đã cho.<br /> Các thành phần có thể lặp lại.<br /> <br />