Tóm tắt luận văn thạc sĩ khoa học: Bài toán đếm nâng cao trong tổ hợp và ứng dụng

Tóm tắt luận văn thạc sĩ khoa học: Bài toán đếm nâng cao trong tổ hợp và ứng dụng nhằm nghiên cứu về các cầu hình tổ hợp từ cơ bản đến nâng cao, nguyên lý bù trừ, lý thuyết hàm sinh, công thức truy hồi...từ đó đưa ra được hệ thống các phương pháp và ứng dụng điển hình của bài toán đếm nâng cao trong tổ hợp.
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: Bài toán đếm nâng cao trong tổ hợp và ứng dụng 1 B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG TRƯƠNG NH T LÝ BÀI TOÁN Đ M NÂNG CAO TRONG T H P VÀ NG D NG 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 2011 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: PGS.TSKH. TR N QU C CHI N Ph n bi n 1: Ph n bi n 2: Lu n văn ñư 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 vào 22 ngày tháng 10 năm 2011 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 T h p có v trí ñ c bi t trong toán h c không ch như là nh ng ñ i tư ng ñ nghiên c u mà còn ñóng vai trò như m t công c ñ c l c c a các mô hình r i r c c a gi i tích, ñ i s , ... Các bài toán t h p ngày càng chi m m t v trí quan tr ng trong các kỳ thi olympic, vô ñ ch toán ... Toán t h p là m t d ng toán khó, ñòi h i tư duy lôgic, tư duy thu t toán cao, tính hình tư ng t t, phù h p v i m c ñích tuy n ch n h c sinh có kh năng và năng khi u toán h c. Hơn n a, n i dung các bài toán ki u này ngày càng g n v i th c t cu c s ng chúng ta, và ñi u ñó hoàn toàn phù h p v i xu hư ng c a toán h c hi n ñ i. Chính vì nh ng lý do trên, chúng tôi ñã nghiên c u và ch n ñ tài “Bài toán ñ m nâng cao trong t h p và ng d ng” nh m h th ng các phương pháp gi i ñ ng th i nâng cao hơn n a nh n th c và ng d ng c a nó trong h c t p, nghiên c u và công tác sau này. 2. M C ĐÍCH NGHIÊN C U Nghiên c u lý thuy t v lý thuy t t h p và t ñó nh m h th ng các phương pháp gi i bài toán ñ m và ng d ng c a nó vào nghiên c u, h c t p cũng như trong th c ti n. Đ tài cũng ñư c làm tài li u tham kh o cho h c sinh, sinh viên ñ i h c và cao ñ ng, h c viên cao h c, thi h c sinh gi i c p qu c gia, qu c t và nh ng ai quan tâm ñ n lý thuy t t h p. 3. NHI M V NGHIÊN C U Nhi m v c a ñ tài này là nghiên c u v các c u hình t h p t cơ b n ñ n nâng cao, nguyên lý bù tr , lý thuy t v hàm sinh, công th c truy h i... T ñó ñưa ra ñư c h th ng các phương pháp và ng d ng ñi n hình c a bài toán ñ m nâng cao trong t h p. 4. Đ I TƯ NG VÀ PH M VI NGHIÊN C U • Lý thuy t v các c u hình t h p cơ b n và m r ng và các ki n th c liên quan ñ n bài toán ñ m. • Phương pháp gi i bài toán ñ m và các bài toán áp d ng. • ng d ng c a bài toán ñ m t h p. 5. PHƯƠNG PHÁP NGHIÊN C U S d ng phương pháp nghiên c u tài li u liên quan ñ n lu n văn ñ thu th p thông tin, t ñó phân tích, h th ng và phân lo i các phương pháp gi i cũng như m t s ng d ng ñi n hình liên quan ñ n bài toán ñ m trong t h p. 4 6. Ý NGHĨA KHOA H C VÀ TH C TI N C A Đ TÀI Đ tài h th ng ki n th c v các nguyên lý ñ m, các c u hình t h p, lý thuy t hàm sinh, h th c truy h i và các ki n th c liên quan ñ n bài toán ñ m t h p. T ñó hình thành các phương pháp t cơ b n ñ n nâng cao và m t s ng d ng liên quan ñ n bài toán ñ m. Qua ñó b sung thêm cho các em h c sinh, sinh viên v các phương pháp gi i các bài toán ñ m t h p t cơ b n ñ n khó và r t khó, ñ c bi t là trư c các kì thi h c sinh gi i t c p t nh, c p qu c gia ñ n thi Olympic qu c t và các kỳ thi khác. Đ tài còn có th làm ngu n tham kh o cho nh ng ai quan tâm ñ n lý thuy t t h p mà c th là phương pháp gi i và ng d ng c a bài toán ñ m t h p. 7. C U TRÚC C A LU N VĂN Lu n văn ñư c c u trúc b i 3 chương: Chương 1: T ng quan v t h p Chương 2: M t s phương pháp ñ m nâng cao Chương 3: M t s ng d ng Chương 1 T NG QUAN V T H P 1.1. SƠ LƯ C V L CH S T H P Có th nói tư duy t h p ra ñ i r t s m. Vào th i nhà Chu Trung Qu c ngư i ta ñã bi t ñ n nh ng hình vuông th n bí. Th i c Hi l p, th k th 4 trư c Công nguyên, nhà tri t h c Kxenokrat ñã bi t cách tính s các t khác nhau l p t b ng ch cái cho trư c. Tuy nhiên có th nói r ng, lý thuy t t h p ñư c hình thành như m t ngành toán h c m i vào th k 17 b ng m t lo t công trình nghiên c u c a các nhà toán h c xu t s c như Pascal, Fermat, Euler, Leibnitz … Các bài toán t h p có ñ c trưng bùng n t h p v i s c u hình t h p kh ng l . Vì v y trong th i gian dài, khi mà các ngành toán h c như Phép tính vi phân, Phép tính tích phân, phương trình vi phân… phát tri n như vũ bão, thì dư ng như nó n m ngoài s phát tri n và ng d ng c a toán h c. Tình th thay ñ i t khi xu t hi n máy tính và s phát tri n c a toán h c h u h n. Nhi u v n ñ t h p ñã ñư c gi i quy t trên máy tính và phát tri n r t m nh m . 1.2. CÁC D NG BÀI TOÁN T H P D ng 1: Bài toán t n t i D ng 2: Bài toán ñ m D ng 3: Bài toán li t kê D ng 4: Bài toán t i ưu t h p 5 1.3. CÁC C U HÌNH T H P CƠ B N VÀ M R NG 1.3.1. Hai nguyên lý ñ m cơ b n 1.3.1.1. Nguyên lý c ng 1.3.1.2. Nguyên lý nhân 1.3.2. Các c u hình t h p 1.3.2.1. Hoán v không l p 1.3.2.2. Hoán v l p 1.3.2.3. Ch nh h p không l p 1.3.2.4. Ch nh h p l p Đ nh nghĩa 1.4: Ch nh h p l p ch p k c a n ph n t khác nhau là m t b có th t g m k thành ph n l y t n ph n t ñã cho, các ph n t có th ñư c l p l i. Đ nh lí 1.2: S lư ng các ch nh h p l p ch p k c a n ph n t ñư c kí hi u và xác ñ nh b i công th c sau: A k = AR(n, k) = nk. n 1.3.2.5. T h p không l p 1.3.2.6. T h p l p Đ nh nghĩa 1.6: T h p l p ch p k c a n ph n t khác nhau là m t nhóm không phân bi t th t g m k ph n t trích t n ph n t ñã cho, trong ñó các ph n t có th ñ c l p l i. Đ nh lý 1.3: Gi s X có n ph n t khác nhau. Khi ñó s t h p l p ch p k c a n ph n t c a ...