Bài giảng Toán rời rạc - Nguyễn Đức Nghĩa

Nội dung text: Bài giảng Toán rời rạc - Nguyễn Đức Nghĩa

1. TOÁN RỜI RẠC Discrete Mathematics Fall 2009 Toán rời rạc 1
2. NguyÔn §øc NghÜa Bé m«n Khoa häc M¸y tÝnh §¹i häc B¸ch khoa Hµ néi Tel: 0438696121 (Off), 0903210111 (Mob) nghiand@it-hut.edu.vn Toán rời rạc 2
3. Đề nghị với các lớp trưởng ⚫ Hãy gửi cho tôi danh sách lớp theo địa chỉ email đã nêu Toán rời rạc 3
4. Toán rời rạc là gì? ⚫ What is discrete mathematics? • Là bộ phận của toán học nghiên cứu các đối tượng rời rạc. • Rời rạc bao hàm ý các phần tử phân biệt hay không liên tục. • Các phép toán: • Tổ hợp: Đếm các đối tượng rời rạc • Các phép toán logic, quan hệ: nói lên mối quan hệ giữa các đối tượng rời rạc • Làm việc với: Các đối tượng rời rạc: tập hợp, mệnh đề. Toán rời rạc 4
5. Định nghĩa hình thức - Wikipedia ⚫ Discrete mathematics, sometimes called finite mathematics, is the study of mathematical structures that are fundamentally discrete, in the sense of not supporting or requiring the notion of continuity. Most, if not all, of the objects studied in finite mathematics are countable sets, such as the integers. ⚫ Discrete mathematics has become popular in recent decades because of its applications to computer science. Concepts and notations from discrete mathematics are useful to study or express objects or problems in computer algorithms and programming languages. In some mathematics curricula, finite mathematics courses cover discrete mathematical concepts for business, while discrete mathematics courses emphasize concepts for computer science majors. ⚫ Discrete mathematics usually includes : • logic - a study of reasoning • set theory - a study of collections of elements • number theory • combinatorics - a study of counting • graph theory • algorithmics - a study of methods of calculation • information theory • the theory of computability and complexity - a study on theoretical limitations on algorithms Toán rời rạc 5
6. Nhập môn Toán rời rạc ⚫ Các ứng dụng của TRR: • Formal Languages (computer languages) • Machine translation • Compiler Design • Artificial Intelligence • Relational Database Theory • Network Routing • Algorithm Design • many more (almost all areas of computer science) A building block of computer science ! Toán rời rạc 6
7. Nhập môn Toán rời rạc ⚫ Các vấn đề chính được đề cập trong giáo trình này: • Cơ sở: logic, tập hợp, ánh xạ. • Lý thuyết tổ hợp (Combinatorial Theory) • 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 • Lý thuyết đồ thị (Graph theory): • Đồ thị, Đường đi, Liên thông • Biểu diễn đồ thị • Duyệt đồ thị • Các bài toán tối ưu trên đồ thị Toán rời rạc 7
8. Tài liệu tham khảo 1. Rosen K.H. Discrete Mathematics and its Applications. McGraw - Hill Book Company, 2003. 2. Johnsonbaugh R. Discrete Mathematics. Prentice Hall Inc., N. J., 1997. 3. Grimaldi R.P. Discrete and Combinatorial Mathematics (an Applied Introduction), Addison- Wesley, 5th edition, 2004. 4. R. Graham, O. Patashnik, and D.E. Knuth. Concrete Mathematics, Second Edition. Addison- Wesley, 1994. 8
9. Tài liệu tham khảo 5. Phan Đình Diệu. Lý thuyết ôtômat hữu hạn và thuật toán. NXB ĐHTHCN, Hà nội, 1977. 6. Nguyễn Hữu Anh. Toán rời rạc, NXB Giáo dục,1999. 7. Nguyễn Xuân Quỳnh. Cơ sởToán rời rạc và ứng dụng. NXB KHKT, Hà nội, 1996. 8. Đỗ Đức Giáo. Toán rời rạc. NXB KHKT, Hà nội, 2001. 9. Hoàng Chúng. Đại cương về toán hữu hạn. NXB Giáo dục, 1997. 9
10. Rosen’s Book Rosen K.H. Discrete Mathematics and its Applications. 5th Edition, McGraw - Hill Book Company, 2003. 10
11. Table of Contents Preface 6 Relations To the Student The Companion Web Site Relations and Their Properties, n-ary Relations and Their 1 The Foundations: Logic, Sets, and Functions Applications, Representing Relations, Closures of Logic, Propositional Equivalences, Predicates Relations, Equivalence Relations, Partial Orderings and Quantifiers, Sets, Set Operations, 7 Graphs Functions, Sequences and Summations, The Introduction to Graphs, Graph Terminology, Growth Functions Representing Graphs and Graph Isomorphism, 2 The Fundamentals: Algorithms, the Integers, Connectivity, Euler and Hamilton Paths, Shortest Path and Matrices Problems, Planar Graphs, Graph Coloring Algorithms, Complexity of Algorithms, The Integers and Division, Integers and Algorithms, 8 Trees Applications of Number Theory, Matrices Introduction to Trees , Applications of Trees, Tree 3 Mathematical Reasoning Traversal,Trees and Sorting, Spanning Trees, Minimum Methods of Proof, Mathematical Induction, Spanning Trees Recursive Definitions, Recursive Algorithms, 9 Boolean Algebra Program Correctness Boolean Functions, Representing Boolean Functions, 4 Counting Logic Gates, Minimization of Circuits The Basics of Counting, The Pigeonhole 10 Modeling Computation Principle, Permutations and Combinations, Discrete Probability, Probability Theory , Languages and Grammars, Finite-State Machines with Output, Generalized Permutations and Combinations, Finite-State Machines with No Output, Language Recognition, Generating Permutations and Combinations Turing Machines 5 Advanced Counting Techniques Appendixes Recurrence Relations, Solving Recurrence Suggested Readings Relations, Divide-and-Conquer Relations, Solutions to Odd-Numbered Exercises Generating Functions, Inclusion-Exclusion, Applications of Inclusion-Exclusion Index of Biographies Index 11
12. Johnsonbaugh Book Johnsonbaugh R. Discrete Mathematics. Prentice Hall Inc., N. J., 1997. 12
13. Table of Contents 1 Logic and Proofs 7 Recurrence Relations 1.1 Propositions 7.1 Introduction 1.2 Conditional Propositions and Logical Equivalence 7.2 Solving Recurrence Relations 1.3 Quantifiers 7.3 Applications to the Analysis of Algorithms 1.4 Nested Quantifiers 8 Graph Theory 1.5 Proofs 8.1 Introduction 1.6 Resolution Proofs 8.2 Paths and Cycles 1.7 Mathematical Induction 8.3 Hamiltonian Cycles and the TSP 1.8 Strong Form of Induction and the Well-Ordering Property 8.4 Shortest-Path Algorithm 2 The Language of Mathematics 8.5 Representations of Graphs 2.1 Sets 2.2 Functions 2.3 Sequences and Strings 9 Trees 3 Relations 9.1 Introduction 3.1 Relations 3.2 Equivalence Relations 9.2 Terminology and Characterizations of Trees 3.3 Matrices of Relations 3.4 Relational Databases 9.3 Spanning Trees 4 Algorithms 9.4 Minimal Spanning Trees 4.1 Introduction 4.2 Examples of Algorithms 9.5 Binary Trees 4.3 Analysis of Algorithms 4.4 Recursive Algorithms 9.6 Tree Traversals 5 Introduction to Number Theory 9.7 Decision Trees and the Minimum Time for Sorting 5.1 Divisors 9.8 Isomorphisms of Trees 5.2 Representations of Integers and Integer Algorithms 9.9 Game Trees 5.3 The Euclidean Algorithm 10 Network Models 5.4 The RSA Public-Key Cryptosystem 10.1 Introduction 6 Counting Methods and the Pigeonhole Principle 10.2 A Maximal Flow Algorithm 6.1 Basic Principles 10.3 The Max Flow, Min Cut Theorem 6.2 Permutations and Combinations 10.4 Matching 6.3 Algorithms for Generating Permutations and Combinations 11 Boolean Algebras and Combinatorial Circuits 6.6 Generalized Permutations and Combinations 12 Automata, Grammars, and Languages 6.7 Binomial Coefficients and Combinatorial Identities 13 Computational Geometry 6.8 The Pigeonhole Principle Appendix Index 13
14. Grimadi’s Book Grimaldi R.P. Discrete and Combinatorial Mathematics (an Applied Introduction), Addison-Wesley, 5th edition, 2001. 14
15. Table of Contents PART 1. FUNDAMENTALS OF DISCRETE MATHEMATICS. Derangements: Nothing Is in Its Right Place. 1. Fundamental Principles of Counting. Rook Polynomials. The Rules of Sum and Product. Arrangements with Forbidden Positions. Permutations. Combinations: The Binomial Theorem. 9. Generating Functions. Combinations with Repetition. Introductory Examples. 2. Fundamentals of Logic. Definition and Examples: Calculational Techniques. 3. Set Theory. Partitions of Integers. Sets and Subsets. 10. Recurrence Relations. Set Operations and the Laws of Set Theory. Counting and Venn Diagrams. PART 3. GRAPH THEORY AND APPLICATIONS. A First Word on Probability. 11. An Introduction to Graph Theory. 4. Properties of the Integers: Mathematical Induction. Definitions and Examples. The Well-Ordering Principle: Mathematical Induction. Subgraphs, Complements, and Graph Isomorphism. Recursive Definitions. Vertex Degree: Euler Trails and Circuits. The Division Algorithm: Prime Numbers. Planar Graphs. Hamilton Paths and Cycles. The Greatest Common Divisor: The Euclidean Algorithm. 12. Trees. The Fundamental Theorem of Arithmetic. Definitions, Properties, and Examples. 5. Relations and Functions. Rooted Trees. Trees and Sorting. Cartesian Products and Relations. Weighted Trees and Prefix Codes. Functions: Plain and One-to-One. Biconnected Components and Articulation Points. Onto Functions: Stirling Numbers of the Second Kind. 13. Optimization and Matching. Special Functions. Dijkstra's Shortest Path Algorithm. The Pigeonhole Principle. Minimal Spanning Trees: The Algorithms of Kruskal and Prim. Function Composition and Inverse Functions. Transport Networks: The Max-Flow Min-Cut Theorem. Computational Complexity. Matching Theory. Analysis of Algorithms. 6. Languages: Finite State Machines. PART 4. MODERN APPLIED ALGEBRA. 7. Relations: The Second Time Around. 14. Rings and Modular Arithmetic. PART 2. FURTHER TOPICS IN ENUMERATION. 15. Boolean Algebra and Switching Functions. 8. The Principle of Inclusion and Exclusion. 16. Groups, Coding Theory, and Polya's Theory of Enumeration. The Principle of Inclusion and Exclusion. 17. Finite Fields and Combinatorial Designs. 15
16. Graham, Knuth, Patashnik’s Book Ronald L. Graham Donald E. Knuth Oren Patashnik Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley Professional 1994, 672 pp 16
17. Table of Contents 6. Special Numbers. 1. Recurrent Problems. Stirling Numbers. The Tower of Hanoi. Eulerian Numbers. Lines in the Plane. Harmonic Numbers. The Josephus Problem. Harmonic Summation. 2. Sums. Bernoulli Numbers. Notation. Fibonacci Numbers. Sums and Recurrences. Continuants. Manipulation of Sums. 7. Generating Functions. Multiple Sums. Domino Theory and Change. General Methods. Basic Maneuvers. Finite and Infinite Calculus. Solving Recurrences. Infinite Sums. Special Generating Functions. 3. Integer Functions. Convolutions. Floors and Ceilings. Exponential Generating Functions. Floor/Ceiling Applications. Dirichlet Generating Functions. Floor/Ceiling Recurrences. 8. Discrete Probability. 'mod': The Binary Operation. Definitions. Floor/Ceiling Sums. Mean and Variance. 4. Number Theory. Probability Generating Functions. Divisibility. Flipping Coins. Factorial Factors. Hashing. Relative Primality. 9. Asymptotics. 'mod': The Congruence Relation. A Hierarchy. Independent Residues. O Notation. Additional Applications. O Manipulation. Phi and Mu. Two Asymptotic Tricks. 5. Binomial Coefficients. Euler's Summation Formula. Basic Identities. Basic Practice. Tricks of the Trade. Final Summations. Generating Functions. A. Answers to Exercises. Hypergeometric Functions. B. Bibliography. Hypergeometric Transformations. C. Credits for Exercises. 17
18. Tài liệu tham khảo chính Nguyễn Đức Nghĩa, Nguyễn Tô Thành TOÁN RỜI RẠC (in lần thứ ba) Nhà xuất bản Đại học Quốc gia Hà nội, 2003, 290 trang 18
19. Mục lục PhÇn I. Lý thuyÕt Tæ hîp PhÇn 2. Lý thuyÕt ®å thÞ Chương 1. Mở đầu Chương 1. Các khái niệm cơ bản của lý thuyết đồ thị 1.1 Sơ lược về tổ hợp 1.1 Định nghĩa đồ thị 1.2 Nhắc lại lý thuyết tập hợp 1.2 Các thuật ngữ cơ bản 1.3 Một số nguyên lý cơ bản 1.3 Đường đi, Chu trình, Đồ thị liên thông 1.4 Các cấu hình tổ hợp đơn giản 1.4 Một số dạng đồ thị đặc biệt Chương 2. Bài toán đếm Chương 2. Biểu diễn đồ thị trên máy tính 2.1 Giới thiệu bài toán 2.1 Ma trận kề. Ma trận trọng số, 2.2 Danh sách cạnh 2.3 Danh 2.2 Nguyên lý bù trừ sách kề 2.3 Quy về các bài toán đơn giản Chương 3. Các thuật toán tìm kiếm trên đồ thị và ứng dụng 2.4 Công thức truy hồi 3.1 Tìm kiếm theo chiều sâu trên đồ thị 2.5 Liệt kê 3.2 Tìm kiếm theo chiều rộng trên đồ thị Chương 3. Bài toán tồn tại 3.3 Tìm đường đi và kiểm tra tính liên thông 3.1 Giới thiệu bài toán Chương 4. Đồ thị Euler và đồ thị Hamilton 3.2 Phương pháp phản chứng 4.1 Đồ thị Euler 4.2 Đồ thị Hamilton 3.3 Nguyên lý Dirichlet Chương 5. Cây và cây khung của đồ thị 3.4 Hệ đại diện phân biệt 5.1 Cây và các tính chất của cây Chương 4. Bài toán liệt kê 5.2 Cây khung của đồ thị 4.1 Giới thiệu bài toán 5.3 Xây dựng tập các chu trình cơ bản của đồ thị 4.2 Thuật toán và độ phức tạp tính toán 5.4 Bài toán cây khung nhỏ nhất 4.3 Phương pháp sinh Chương 6. Bài toán đường đi ngắn nhất 4.4 Thuật toán quay lui Chương 7. Bài toán luồng cực đại trong mạng Chương 5. Bài toán tối ưu 5.1 Phát biểu bài toán PhÇn 3. Hµm ®¹i sè l«gic 5.2 Các thuật toán duyệt Chương 1. Mở đầu 5.3 Thuật toán nhánh cận giải bài toán người du lịch Chương 2. Dạng tuyển chuẩn tắc của hàm đại số lôgic 5.4 Bài toán lập lịch gia công trên hai máy Chương 3. Thuật toán tìm dạng tuyển chuẩn tắc tối thiểu Tài liệu tham khảo 19
20. Quetions? 20
21. Fall 2006 Toán rời rạc 21
22. Fall 2006 Toán rời rạc 22
23. Ứng dụng: Ngôn ngữ hình thức Formal Language ⚫ Formal language: • Ngôn ngữ được sinh bởi ngữ pháp (grammars) • Grammars: • Sinh ra các từ (words) của ngôn ngữ • Xác định một từ có thuộc ngôn ngữ hay không • Từ (Words): • Có thể tổ hợp bằng nhiều cách • Ngữ pháp cho biết tổ hợp từ có là một câu hợp lệ (valid sentence) hay không • Ứng dụng: • Thiết kế các Ngôn ngữ lập trình và Chương trình dịch (Programming Languages and Compilers) Fall 2006 Toán rời rạc 23
24. Ứng dụng: Ngôn ngữ hình thức ⚫ Ví dụ 1: • Ngôn ngữ tự nhiên: English • Có phải “the hungry rabbits eats quickly” là câu tiếng Anh? • Cây cú pháp của câu (Derivation tree of the sentence): sentence noun phrase verb phrase article adjective noun verb adverb the hungry rabbit eats quickly Fall 2006 Toán rời rạc 24
25. Ứng dụng: Ngôn ngữ hình thức ⚫ Ví dụ 2: • Bài toán điển hình trong xây dựng Chương trình dịch. • Xác định từ cbab có thuộc ngôn ngữ sinh bởi ngữ pháp G = (V, T, S, P), trong đó: • V = a, b, c, A, B, C, S  • T = a, b, c  • S là ký tự đầu tiên (starting symbol) • P là các luật sản xuất (productions): S → AB A → Ca B → Ba B → Cb B → b C → cb C → b Fall 2006 Toán rời rạc 25
26. Ứng dụng: Ngôn ngữ hình thức ⚫ Ví dụ 2 (tiếp tục): • Giải: • Bắt đầu bởi S và tìm cách dẫn ra cbab sử dụng dãy các luật sản xuất. • Do chỉ có một luật bắt đầu vớiS, ta phải bắt đầu với S AB • Sử dụng luật đối với A để thu được: S AB CaB • Sử dụng luật đối với C → cb vì cbab bắt đầu bởi cb: S AB CaB cbaB • Cuối cùng sử dụng luật đối với B → b: S AB CaB cbaB cbab Fall 2006 Toán rời rạc 26
27. Ứng dụng: Graph Theory ⚫ Ví dụ 3 • Bài toán về 7 cái cầu (Konigsberg 7-bridge problem) • Konigsberg là thành phố của Nga • Có 4 vùng đất, và 7 cái cầu nối chúng • Euler giải được bài toán năm 1736; là khởi nguồn của lý thuyết đồ thị Fall 2006 Toán rời rạc 27
28. Ứng dụng: Graph Theory ⚫ Bài toán: Vẽ đường đi (hoặc vòng kín) bởi bút chì sao cho có thể đi qua mỗi cái cầu đúng một lần mà không được nhấc đầu bút khỏi mặt giấy (vẽ một nét) Fall 2006 Toán rời rạc 28
29. Ứng dụng: Lý thuyết tập hợp (Set Theory) ⚫ Có phải số lượng số nguyên là nhiều hơn số lượng số nguyên dương? ⚫ Có phải số lượng số nguyên là nhiều hơn số lượng số thực? Fall 2006 Toán rời rạc 29
30. Ứng dụng: Lý thuyết độ phức tạp (Complexity Theory) ⚫ Ví dụ 5: • Bài toán người du lịch (The Traveling Salesman Problem) • Có ứng dụng quan trọng trong • Thiết kế mạch (circuit design) • Hướng lộ trên mạng (network routing) • và nhiều bài toán trong tin học khác • Cho: • n thành phố c1, c2, . . . , cn • khoảng cách giữa thành phố i và j là dij • Tìm hành trình ngắn nhất. Fall 2006 Toán rời rạc 30
31. Ứng dụng: Lý thuyết độ phức tạp ⚫ Ví dụ 5 (tiếp): 2 4 1 3 • Có bao nhiêu hành trình khác nhau? • Thành phố đầu tiên có thể chọn bởi n cách, • thành phố thứ hai, n-1 cách, • thành phố thứ ba, n-2 cách, • v.v • # hành trình = n (n-1) (n-2) . . . .(2) (1) = n! (Tổ hợp) • Tính độ dài của một hành trình đòi hỏi n-1 phép cộng. • Tổng số phép cộng = (n-1) n! (Qui tắc nhân - Rule of Product) Fall 2006 Toán rời rạc 31
32. Ứng dụng: Lý thuyết độ phức tạp ⚫ Ví dụ 5 (tiếp): • Giả sử có PC tốc độ rất cao: • 1 GHz = 1,000,000,000 ops/sec 1 flop = 1 nanosecond = 10-9 sec. • Nếu n=8, T(n) = 7•8! = 282,240 flops << 1 second. • TUY NHIÊN . . . . . . . . . . . . . • Nếu n=50, T(n) = 49•50! = 1.48 1066 = 1.49 1057 seconds = 4.73 1049 năm. • quá lâu. Không ai trong số chúng ta có thể chờ được thời điểm kết thúc. • Có rất nhiều bài toán mà chúng ta còn chưa biết liệu có thuật toán hiệu quả để giải hay không! Fall 2006 Toán rời rạc 32
33. Ứng dụng: Lý thuyết độ phức tạp ⚫ Ví dụ 5 (tiếp): • Chúng ta có thể làm gì ? • Không có thời gian để chờ Do not waste time unless you are a genius to save the world • Mục đích khiêm tốn hơn • Với xác suất 90%, có thể tìm được hành trình tối ưu • Thuật toán tìm hành trình không tồi hơn 1.1 lần hành trình tối ưu Fall 2006 Toán rời rạc 33