Giáo trình Toán rời rạc: Phần 1 - ĐH Sư phạm kỹ thuật Nam Định

Giáo trình Toán rời rạc: Phần 1 cung cấp cho người học những kiến thức như: Một số kiến thức mở đầu về lý thuyết tổ hợp, bài toán đếm, bài toán tồn tại, bài toán liệt kê, bài toán tối ưu. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Giáo trình Toán rời rạc: Phần 1 - ĐH Sư phạm kỹ thuật Nam Định Lời nói đầu Tài liệu Toán rời rạc được biên soạn nhằm phục vụ công việc giảng dạy và học tập môn học Toán rời rạc của các ngành học thuộc khoa Công nghệ thông tin trường Đại học sư phạm kỹ thuật Nam Định. Với thời lượng 60 tiết nội dung của tài liệu chỉ đề cập đến các kiến thức cơ bản của lý thuyết tổ hợp và lý thuyết đồ thị là hai lĩnh vực có nhiều ứng dụng của toán rời rạc. Nội dung tài liệu gồm 10 chương: Từ chương 1 đến chương 5 nhằm giới thiệu các kiến thức cơ bản của lý thuyết tổ hợp, từ chương 6 đến chương 10 nhằm giới thiệu các kiến thức cơ bản của lý thuyết đồ thị. Trong từng chương các vấn đề đưa ra đều được minh họa bằng các ví dụ. Cuối mỗi chương đều có một hệ thống các bài tập nhằm giúp người học củng cố các kiến thức đã được học đồng thời rèn luyện khả năng vận dụng các kiến thức để giải quyết một số bài toán trong thực tế. Tài liệu được biên soạn theo chương trình môn học Toán rời rạc của các ngành học thuộc khoa Công nghệ thông tin trường Đại học sư phạm kỹ thuật Nam Định. Nội dung tài liệu được biên soạn dựa trên cơ sở nội dung các bài giảng môn học này của tác giả trong một số năm qua tại khoa Công nghệ thông tin trường Đại học sư phạm kỹ thuật Nam Định. Trong quá trình biên soạn, tác giả đã nhận được nhiều ý kiến đóng góp cùng với sự động viên, khích lệ của bạn bè đồng nghiệp trong khoa và trong trường. Tác giả xin được tỏ lòng cảm ơn với những ý kiến đóng góp và động viên khích lệ này. Với lần biên soạn đầu tiên, mặc dù đã hết sức cố gắng song chắc chắn tài liệu không thể tránh khỏi những thiếu sót. Rất mong nhận được các ý kiến đóng góp để tài liệu ngày càng hoàn thiện hơn. Phạm Cao Hào 1 Chƣơng 1 MỘT SỐ KIẾN THỨC MỞ ĐẦU VỀ LÝ THUYẾT TỔ HỢP 1.1. Giới thiệu về tổ hợp Toán rời rạc là một lĩnh vực của toán học nghiên cứu về các đối tượng rời rạc. Các tập hợp dùng để nhóm các đối tượng lại với nhau. Thông thường, các đối tượng trong một tập hợp có các tính chất tương tự nhau. Ví dụ, các sinh viên vừa mới nhập trường lập nên một tập hợp. Tương tự như vậy, các sinh viên khoa CNTT lập nên một tập hợp. Các dãy nhị phân có độ dài n cũng lập nên một tập hợp. Có thể nói tập hợp là một cấu trúc rời rạc cơ bản từ đó lập nên các cấu trúc khác. Tổ hợp như là một lĩnh vực của toán học rời rạc. Hiện nay, lý thuyết tổ hợp được áp dụng trong nhiều lĩnh vực khác nhau: tin học, lý thuyết số, xác suất thống kê, quy hoạch thực nghiệm,... Tổ hợp liên quan đến nhiều vấn đề khác nhau của toán học, do đó khó có thể định nghĩa nó một cách hình thức. Nói chung, lý thuyết tổ hợp gắn liền với việc nghiên cứu phân bố các phần tử vào các tập hợp. Thông thường, các phần tử này là hữu hạn và việc phân bố chúng phải thỏa mãn những điều kiện nhất định nào đó. Mỗi cách phân bố như thế được gọi là một cấu hình tổ hợp. Vài nét về lịch sử Có thể nói tư duy về tổ hợp ra đời từ rất sớm. Thời nhà Chu, người ta đã biết đến các hình vẽ có liên quan đến các hình vuông thần bí. Thời cổ Hy Lạp có nhà triết học đã biết cách tính số các từ khác nhau lập từ một bảng chữ cái cho trước. Nhà toán học Pitago đã tìm ra được nhiều con số có các tính chất đặc biệt, chẳng hạn số 36 không những là tổng của 4 số chẵn và 4 số lẻ đầu tiên mà cồn là tổng lập phương của 3 số tự nhiên đầu tiên. Một định lý nổi tiếng của trường phái này là định lý về độ dài các cạnh của một tam giác vuông, và từ đó đã tìm ra các số mà bình phương của một số này bằng tổng bình phương của hai số khác. Việc tìm ra được các số như vậy, đòi hỏi phải có 2 một nghệ thuật tổ hợp nhất định. 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 là vào khoảng thế kỷ 17 bằng một loạt các công trình nghiên cứu nghiêm túc của các nhà toán học như Pascal, Fermat, Euler, .... Trong thời gian hiện nay, mối tương quan giữa toán học hữu hạn và toán học cổ điển đã có nhiều thay đổi, đặc biệt khi máy tính điện tử ra đời và phát triển. Nhiều bài toán nổi tiếng đã được giải trên máy tính bằng những thuật toán của toán hữu hạn. Các lĩnh vực trừu tượng của toán học như đại số lôgic, ngôn ngữ hình thức, ... đã trở thành khoa học ứng dụng để xây dựng các ngôn ngữ lập trình cho máy tính. Trong thời đại phát triển của toán học hữu hạn, vai trò của lý thuyết tổ hợp cũng khác xưa. Từ lĩnh vực nghiên cứu các trò chơi tiêu khiển hay phân tích giải mã các bức thư cổ, tổ hợp đã chuyển sang lĩnh vực toán ứng dụng với sự phát triển mạnh mẽ. Các bài toán tổng quát Trong các tài liệu về tổ hợp, thường gặp các dạng bài toán dưới đây: * Bài toán đếm: Đây là các bài toán nhằm trả lời câu hỏi “ Có bao nhiêu cấu hình thoả mãn điều kiện đã nêu? “. Phương pháp đếm thường dựa vào một số nguyên lý cơ bản và một ...