Toán rời rạc - Bài mở đầu - Tổng quan

Đây là bài giảng toán rời rạc bằng tiếng anh dành cho giáo viên, sinh viên tham khảo để ôn tập tốt môn toán rời rạc.
Nội dung trích xuất từ tài liệu:
Toán rời rạc - Bài mở đầu - Tổng quan University of Florida Dept. of Computer & Information Science & Engineering COT 3100 Applications of Discrete Structures Dr. Michael P. Frank Slides for a Course Based on the Text Discrete Mathematics & Its Applications (5th Edition) (5 by Kenneth H. Rosen Slides are online at http://www.cise.ufl.edu/~mpf/cot3100lecs 10/21/11 (c)2001-2004, Michael P. Frank 1 Module #0: Tổng quan Course Overview A few general slides about the subject few matter of this course. matter 14 slides, ½ lecture 10/21/11 (c)2001-2004, Michael P. Frank 2 Toán học trên thực tế là gì? • Đây không phải chỉ về các số! • Toán học thực tế nhiều hơn thế: Toán học, nói tổng quát, là nghiên cứu về mọi chân lý đúng tuyệt đối về mọi khái niệm được định nghĩa một cách đúng đắn. • Nhưng, những khái niệm này có thể là về các con số, ký hiệu, đối tượng, hình ảnh, âm thanh hay bất cứ cái gì khác! hay 10/21/11 (c)2001-2004, Michael P. Frank 3 Physics from Mathematics • Starting from simple structures of logic & Starting set theory, set – Mathematics builds up structures that include Mathematics all the complexity of our physical universe… all • Except for a few “loose ends.” • One theory of philosophy: – Perhaps our universe is nothing other than just a Perhaps is complex mathematical structure! complex • It’s just one that happens to include us! From Max Tegmark, ‘98 10/21/11 (c)2001-2004, Michael P. Frank 4 Vậy môn học này dạy về cái gì? Cấu trúc “rời rạc” là cái gì? • “Discrete” - rời rạc gồm các phần riêng biệt. (Đối nghịch với liên tục) rời rạc:liên tục :: kỹ thuật số:tương tự • “Cấu trúc” – Các đối tượng được xây dựng từ các đối tượng đơn giản hơn nhờ các mẫu xác định. • “Toán rời rạc” – nghiên cứu về các cấu trúc và đối tượng toán học rời rạc. 10/21/11 (c)2001-2004, Michael P. Frank 5 Chúng ta sẽ học • Mệnh đề - Propositions • Dãy - Sequences ãy Sequences • Xâu - Strings âu Strings Vị từ - Predicates • • Hoán vị - Permutations • Chứng minh - Proofs • Tổ hợp - Combinations • Tập hợp - Sets • Quan hệ - Relations • Hàm số - Functions • Đồ thị - Graphs • Tốc độ tăng - Orders of Orders • Cây - Trees ây Trees Growth Growth • Mạch logic - Logic • Thuật toán - Algorithms Logic Circuits Circuits • Số nguyên - Integers • Ôtômat - Automata Ôtômat Automata • Lấy tổng - Summations 10/21/11 (c)2001-2004, Michael P. Frank 6 Mối quan hệ giữa các cấu trúc • “→” :≝ “Can be defined in terms of” Programs Proofs Groups Operators Trees Complex Propositions numbers Graphs Real numbers Strings Functions Integers Matrices Relations Natural numbers Sequences Infinite Bits n-tuples Vectors ordinals Sets Not all possibilities are shown here. 10/21/11 (c)2001-2004, Michael P. Frank 7 Một số ký hiệu mà ta sẽ học ¬p p∧q p⊕q p→q p⇔q ∀x P ( x) ∃x P ( x) ∴ x∉S {a1 , , an } Z, N, R {x | P( x)} n ∅ S ⊆T A∪ B A |S| A i i =1 n ∑ aα ∏a  x f −1 ( x) f :A→ B f g i α∈S i =1 O, Ω, Θ a ≡ b (mod m) min, max a/b | gcd, lcm mod n ...