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

Chia sẻ: Lê Trung Thống | Ngày: | Loại File: PPT | Số trang:19

Thêm vào BST

Báo xấu

164
lượt xem 46
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đâ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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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  ⋅ AT A[ n ] AΟ B ( a k  a0 ) b [aij ] r  R∗ deg + (v) ∆ C (n; n1 , , nm ) p( E | F ) [a ]R 10/21/11 (c)2001-2004, Michael P. Frank 8
Tại sao phải học Toán rời rạc? • Cơ sở của mọi quá trình xử lý thông tin kỹ thuật số là: Thao tác rời rạc của các cấu trúc rời rạc trong bộ nhớ. • Là ngôn ngữ cơ bản và khái niệm cơ sở cho mọi thức khác của Khoa học máy tính. • Các khái niệm toán rời rạc được dùng rộng rãi trong Toán học, Khoa học, Công nghệ, Kinh tế, Sinh học, … • Là công cụ có ích nói chung cho mọi suy nghĩ hợp lý! 10/21/11 (c)2001-2004, Michael P. Frank 9
Ứng dụng của Toán rời rạc trong Khoa học máy tính • Cấu trúc dữ liệu và • Hệ quản trị cơ sở dữ giải thuật liệu • Chương trình dịch. • Mã hoá-Cryptography • Mạng máy tính • Lập trình chỉnh lỗi Computer networks Error correction codes • Hệ điều hành • Cơ chế trò chơi, thuật toán mô phỏng và đồ Operating systems họa… • Kiến trúc máy tính • Mọi lĩnh vực! Computer architecture 10/21/11 (c)2001-2004, Michael P. Frank 10
Instructors: customize topic content & order for your own course Course Outline (as per Rosen) 1. Logic (§1.1-4) 13. Summations (§3.2) 2. Proof methods (§1.5) 14. Countability (§3.2) 3. Set theory (§1.6-7) 15. Inductive Proofs (§3.3) 4. Functions (§1.8) 16. Recursion (§3.4-5) 5. Algorithms (§2.1) 17. Program verification (§3.6) 6. Orders of Growth (§2.2) 18. Combinatorics (ch. 4) 7. Complexity (§2.3) 19. Probability (ch. 5) 8. Number theory (§2.4-5) 20. Recurrences (§6.1-3) 9. Number theory apps. (§2.6) 21. Relations (ch. 7) 10. Matrices (§2.7) 22. Graph Theory (chs. 8+9) 11. Proof strategy (§3.1) 23. Boolean Algebra (ch. 10) 12. Sequences (§3.2) 24. Computing Theory (ch.11) 10/21/11 (c)2001-2004, Michael P. Frank 11
Một số chủ đề bỏ qua Do có thể học ở các môn khác: 8. Lý thuyết số (ch. 8) - học trong môn an toàn thông tin. 9. Ứng dụng lý thuyết số (ch. 9) 10. Ma trận: Đại số tuyến tính 13. Tính tổng: Giải tích 19 Xác suất: Môn Xác suất & thống kê 24. Đại số trừu tượng: An toàn thông tin 24. - Groups, rings, fields, vector spaces, algebras, etc. etc. 10/21/11 (c)2001-2004, Michael P. Frank 12
Mục đích môn học • Học xong môn này sinh viên có thể: – Lập luận các suy luận logic đơn giản (chứng minh). – Kiểm tra tính đúng đắn của các thuật toán đơn giản. – Tự xây dựng các suy luận và các thuật toán đúng đắn. – Mô tả các định nghĩa và các tính chất của nhiều kiểu cấu trúc dữ liệu rời rạc. – Hiểu, biểu diễn và phân tích đúng đắn nhiều kiểu cấu trúc dữ liệu rời rạc sử dụng các khái niệm chuẩn 10/21/11 (c)2001-2004, Michael P. Frank 13
Kế hoạch học tập • Tuần 1: Logic • Tuần 2: Logic (tiếp) • Tuần 3: Chứng minh • Tuần 4: Tập hợp • Tuần 5: Hàm số • Tuần 6: Quan hệ • Tuần 7: Thuật toán • Tuần 8: Cấp độ tăng và độ phức tạp thuật toán 10/21/11 (c)2001-2004, Michael P. Frank 14
Kế hoạch học (tiếp) • Tuần 9: Qui nạp & Đệ qui • Tuần 10: Kiểm chứng & Truy hồi • Tuần 11: Tổ hợp • Tuần 12: Đồ thị • Tuần 13: Đồ thị (tiếp) • Tuần 14: Đại số Bool • Tuần 15: Mô hình & Tổng ôn 10/21/11 (c)2001-2004, Michael P. Frank 15
Kế hoạch bài tập, thực hành, kiểm tra • Mỗi tuần có 1 tiết chữa bài tập • Trong tuần 4 nộp bài cài đặt 1, 2 • Trong tuần 7: nộp vở bài tập đợt 1 • Trong tuần 8: bài kiểm tra giữa kỳ 20% • Trong tuần 9: nộp bài cài đặt 3, 4 • Trong tuần 13: nộp vở bài tập đợt 2 • Trong tuần 14: nghiệm thu bài cài đặt 1-6. 20% • Thi viết: phần đầu trắc nghiệm, phần sau tự luận 60% = 20% + 40% 10/21/11 (c)2001-2004, Michael P. Frank 16
A Proof Example • Theorem: (Pythagorean Theorem Pythagoras of Samos of Euclidean geometry) For any of any (ca. 569-475 B.C.) real numbers a, b, and c, if a and b are the and if base-length and height of a right triangle, and c is the length of its hypo- c = a2 + b2 tenuse, then a + b = c . tenuse, 2 2 2 b • Proof: See next slide. a 10/21/11 (c)2001-2004, Michael P. Frank 17
Proof of Pythagorean Theorem • Proof. Consider the below diagram: – Exterior square area = c2, the sum of the following regions: Exterior • The area of the 4 triangles = 4(½ab) = 2ab • The area of the small interior square = (b−a)2 = b2−2ab+a2. – Thus, c2 = 2ab + (b2−2ab+a2) = a2 + b2. ■ Thus, ab Note: It is easy to show that the exterior and c a ½ab interior quadrilaterals in this construction are c b indeed squares, and that the side length of b a the internal square is indeed b−a (where b is ½ab (b−a)2 ½ab defined as the length of the longer of the two a b perpendicular sides of the triangle). These b c steps would also need to be included in a a ½ab c more complete proof. Areas in this diagram are in boldface; lengths are in a normal font weight. 10/21/11 (c)2001-2004, Michael P. Frank 18
Finally: Have Fun! 10/21/11 (c)2001-2004, Michael P. Frank 19