Bài giảng Toán rời rạc

University of FloridaDept. of Computer & Information Science & EngineeringCOT 3100Applications of Discrete StructuresDr. Michael P. Frank Slides for a Course Based on the TextDiscrete Mathematics & Its Applications (5th Edition)by Kenneth H. Rosen Slides are online at Module #0:Tổng quan Course Overview A few general slides about the subject matter of this course. 14 slides, ½ lecture 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ế: 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! 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. Physics from Mathematics Starting from simple structures of logic & set theory, Mathematics builds up structures that include all the complexity of our physical universe… Except for a few “loose ends.” One theory of philosophy: Perhaps our universe is nothing other than just a complex mathematical structure! It’s just one that happens to include us! From Max Tegmark, ‘98 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. Chúng ta sẽ học Mệnh đề - Propositions Vị từ - Predicates Chứng minh - Proofs Tập hợp - Sets Hàm số - Functions Tốc độ tăng - Orders of Growth Thuật toán - Algorithms Số nguyên - Integers Lấy tổng - Summations Dãy - Sequences Xâu - Strings Hoán vị - Permutations Tổ hợp - Combinations Quan hệ - Relations Đồ thị - Graphs Cây - Trees Mạch logic - Logic Circuits Ôtômat - Automata Mối quan hệ giữa các cấu trúc “→” :≝ “Can be defined in terms of” Sets Sequences n-tuples Matrices Naturalnumbers Integers Relations Functions Graphs Real numbers Complex numbers Strings Propositions Proofs Trees Operators Programs Infiniteordinals Vectors Groups Bits Not all possibilitiesare shown here. Một số ký hiệu mà ta sẽ học 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ý! Ứ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à giải thuật Chương trình dịch. Mạng máy tính Computer networks Hệ điều hành Operating systems Kiến trúc máy tính Computer architecture Hệ quản trị cơ sở dữ liệu Mã hoá-Cryptography Lập trình chỉnh lỗi Error correction codes Cơ chế trò chơi, thuật toán mô phỏng và đồ họa… Mọi lĩnh vực! Course Outline (as per Rosen) Logic (§1.1-4) Proof methods (§1.5) Set theory (§1.6-7) Functions (§1.8) Algorithms (§2.1) Orders of Growth (§2.2) Complexity (§2.3) Number theory (§2.4-5) Number theory apps. (§2.6) Matrices (§2.7) Proof strategy (§3.1) Sequences (§3.2) Summations (§3.2) Countability (§3.2) Inductive Proofs (§3.3) Recursion (§3.4-5) Program verification (§3.6) Combinatorics (ch. 4) Probability (ch. 5) Recurrences (§6.1-3) Relations (ch. 7) Graph Theory (chs. 8+9) Boolean Algebra (ch. 10) Computing Theory (ch.11) Instructors: customize topic content & order for your own course 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 - Groups, rings, fields, vector spaces, algebras, etc. 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 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 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 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% A Proof Example Theorem: (Pythagorean Theorem of Euclidean geometry) For any real numbers a, b, and c, if a and b are the base-length and height of a right triangle, and c is the length of its hypo-tenuse, then a2 + b2 = c2. Proof: See next slide. a b Pythagoras of Samos(ca. 569-475 B.C.) Proof of Pythagorean Theorem Proof. Consider the below diagram: Exterior square area = c2, the sum of the following regions: 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. ■ c c c c a a a a b b b b (b−a)2 Note: It is easy to show that the exterior and interior quadrilaterals in this construction are indeed squares, and that the side length of the internal square is indeed b−a (where b is defined as the length of the longer of the two perpendicular sides of the triangle). These steps would also need to be included in a more complete proof. ½ab ½ab ½ab ½ab Areas in this diagram are in boldface; lengths are in a normal font weight. Finally: Have Fun!