Đại Học Quốc Gia TP.HCM Vietnam National University – HCMC Trường Đại Học Bách Khoa Ho Chi Minh City University of Technology Khoa KH&KT Máy Tính Faculty of Computer Science and Engineering Đề cương môn học CẤU TRÚC RỜI RẠC CHO KHOA HỌC MÁY TÍNH (Discrete Structures for Computing) Số tín chỉ 4 (3.2.7) MSMH CO1007 Số tiết Tổng: 60 LT: 60 TH: TN: BTL/TL: x Môn ĐA, TT, LV Tỉ lệ đánh giá BT: 10% TN: KT: 40% BTL/TL: 10% Thi: 40% Hình thức đánh giá - Bài tập: đánh giá trên bài tập sửa 3 tuần/ lần trên lớp và bài về nhà - Kiểm tra: trắc nghiệm, 60 phút - Thi: trắc nghiệm, 90 phút Môn tiên quyết Không Môn học trước Môn song hành Không CTĐT ngành Kỹ Thuật Máy Tính; Khoa Học Máy Tính Trình độ đào tạo Đại học Cấp độ môn học Cấp độ 1 (dạy cho sinh viên năm 1) Ghi chú khác 1. Mục tiêu của môn học Trang bị kiến thức căn bản về suy luận toán học mạch lạc, lý thuyết tập hợp và đồ thị. Các khối kiến thức này cần cho nhiều lãnh vực khác nhau trong ngành Khoa học- Kỹ thuật máy tính và Khoa học tính toán. Aims: The content of this subject is mainly a basic part of logic, and a key part of set theory and graph theory. This is the mathematical base for many topics of Computational Science. 2. Nội dung tóm tắt môn học ● Số học trên các số nguyên. ● Phép chứng minh phản chứng và quy nạp. ● Lý thuyết tập hợp: quan hệ, hàm, lượng số, quan hệ thứ tự ● Tổ hợp: phép đếm, nguyên lý cộng, nhân, chia, bao gồm và lọai trừ. ● Lý thuyết đồ thị: có hướng, vô hướng, sự đẵng cấu của đồ thị. 1/6 ● Đồ thị có trọng số, thuật toán tìm đường đi có trọng số nhỏ nhất trên đồ thị có trọng số, đồ thị dòng chảy ● Cây: tính chất cây, cây nhị phân, cây phủ bé nhất trong đồ thị liên thông có trọng số ● Mô hình hóa xác suất với biến ngẫu nhiên (biến rời rạc, kỳ vọng, phương sai). Course outline: ● Modular arithmetic over integers ● Proof methods: induction, contradiction. ● Set theory: relations, functions, cardinalities. ● Relation, equivalence equation. Partial order. ● Combinatorics: counting, principles of sum, multiplication, division, inclusion and exclusion. Graph theory: directed, undirected, isomorphism. ● Weighted graphs, algorithm for finding shortest paths, network flows. ● Trees: features, binary trees, minimum spanning trees in connected and weighted graphs. ● Probabilistic Modelling: introductory random variables. 3. Tài liệu học tập Sách, Giáo trình chính: [1] Discrete mathematics and applications – Kenneth H. Rosen. (Vietnamese translation – NXB KHKT 1997 Sách tham khảo: [2] Discrete mathematics, Richard Johnsonbaugh, Willey, 1997 [3] OCW MIT 4. Hiểu biết, kỹ năng, thái độ cần đạt được sau khi học môn học STT Chuẩn đầu ra môn học CDIO L.O.1 Hiểu biết về các cấu trúc logic (cơ bản) và cấu trúc rời rạc 1.1 L.O.1.1 – Nêu định nghĩa về logic mệnh đề và vị từ (cơ bản) 1.1.2 L.O.1.2 – Nêu khái niệm cơ bản trong các cấu trúc rời rạc (tập hợp, ánh xạ, 1.1.2 đồ thị ...) L.O.2 Diễn đạt và mô hình hóa (cơ bản) các vấn đề thực tế bằng cấu trúc rời rạc 4.1 L.O.2.1 – Biểu diễn logic một vài bài toán cơ bản trong ngành máy tính 4.1.1 L.O.2.2 – Thực hiện các phép chứng minh: trực tiếp, phản đảo, quy nạp 4.1.1 L.O.2.3 – Mô tả một bài toán thông qua các cấu trúc tổ hợp - rời rạc (tập 4.1.1 hợp, ánh xạ, đồ thị ...) L.O.3 Hiểu biết về xác suất (cơ bản) và biến ngẫu nhiên 1.1. L.O.3.1 – Hiểu biết về lý thuyết xác suất (cơ bản) 1.1.2 L.O.3.2 – Hiểu biết về biến ngẫu nhiên (chủ yếu biến rời rạc) 1.1.2 L.O.4 Tinh toán các cấu trúc rời rạc và xác suất 4.3 L.O.4.1 – Tính toán trên các cấu trúc rời rạc (tập hợp, đồ thị, cây...) 4.3.1 L.O.4.2 – Tính toán xác suất và biến ngẫu nhiên (xác suất sự kiện, xác suất 4.3.1 có điều kiện, định lý Bayes) 2/6 STT Course learning outcomes CDIO L.O.1 Understanding of logic and discrete structures 1.1 L.O.1.1 – Describe definition of propositional and predicate logic 1.1.2 L.O.1.2 – Define basic discrete structures: set, mapping, graphs, ... L.O.2 Represent and model practical problems with discrete structures 4.1 L.O.2.1 – Logically describe some problems arising in Computing 4.1.1 L.O.2.2 – Use proving methods: direct, contrapositive, induction 4.1.1 L.O.2.3 – Explain problem modeling using discrete structures 4.1.1 L.O.3 Understanding of basic probability and random variables 1.1. L.O.3.1 – Define basic probability theory 1.1.2 L.O.3.2 – Explain discrete random variables 1.1.2 L.O.4 Compute quantities of discrete structures and probabilities 4.3 L.O.4.1 – Operate (compute/ optimize) on discrete structures (graph, 4.3.1 tree,..) L.O.4.2 – Compute probabilities of various events, conditional ones, Bayes 4.3.1 theorem 5. Hướng dẫn cách học - chi tiết cách đánh giá môn học Hướng dẫn cách học: ● Tự đọc sách giáo khoa, giải các bài tập… ● Lưu ý quan sát các ứng dụng của Toán RR trong thế giới thực, xem thêm ở ● www.win.tue.nl/math/eidma/ hay là www.samsi.info/ ● Tham dự giờ giảng trên lớp (> 80%)+ làm bài tập ( > 60% bài tập đã nhận) Chi tiết cách đánh giá môn học: ● Về thực hiện báo cáo tiểu luận: không ● Bài kiểm tra có nội dung trước phần đồ thị ● Thi cuối kỳ : nội dung từ phần đồ thị ● Bài tập (10%) và Bài tập lớn (10%): Giảng viên đánh giá các bài làm của sinh viên ● Kiểm tra giữa kỳ (40%), trắc nghiệm - 60' ● Thi cuối kỳ (40%), thi trắc nghiệm – 90' ● Ghi chú về điều kiện cấm thi: vắng trên 50% số buổi học ● Tổng kết điểm: điểm thi tối thiểu phải đạt từ 2 trở lên mới tính là đạt cả MH 6. Dự kiến danh sách Cán bộ tham gia giảng dạy ● TS. Huỳnh Tường Nguyên - K.Khoa học Kỹ thuật máy tính ● PGS. TS. Trần Văn Hoài - K.Khoa học Kỹ thuật máy tính ● TS. Nguyễn An Khương - K.Khoa học Kỹ thuật máy tính ● TS. Lê Hồng Trang - K.Khoa học Kỹ thuật máy tính ● TS. Trần Tuấn Anh - K.Khoa học Kỹ thuật máy tính ● ThS. Võ Thanh Hùng - K.Khoa học Kỹ thuật máy tính 7. Nội dung chi tiết 3/6 Nội dung phần lý thuyết Tuần Nội dung Chuẩn đầu ra chi tiết Hoạt động Hoạt động dạy và học đánh giá 1 Chương 0. Giới thiệu Hiểu biết tổng quan về các thành tố môn học- a. Các hướng nghiên cứu và vai trò môn học- p ứng dụng mới nhất pháp học b. Giới thiệu phương pháp học c. Các phần mềm Yêu cầu tự học đ/v sinh viên: 2g 2, 3 Chương 1. Phép chứng L.O.1.1 – Nêu định Bài tập trên minh nghĩa về logic mệnh đề lớp 1.1. Số học của số nguyên và vị từ (cơ bản) 1.2. Logíc mệnh đề: logic nhị L.O.2.1 – Biểu diễn nguyên, vị từ và lượng từ logic một vài bài toán 1.3. Chứng minh phản chứng, cơ bản trong ngành quy nạp máy tính L.O.2.2 – Thực hiện 1.4. Ứng dụng của phép quy các phép chứng minh nạp (optional) (trực tiếp, phản đảo, ...) Yêu cầu tự học đ/v sinh viên: 6 giờ 4, 5 Chương 2. Lý thuyết tập L.O.1.2 – Nắm các Bài tập trên hợp khái niệm cơ bản trong lớp các cấu trúc rời rạc (tập Bài tập về nhà 1. hợp, ánh xạ, đồ thị ...) 2. L.O.2.3 – Mô tả một 2.1. Tập hợp, phép toán bài toán thông qua các 2.2. Ánh xạ, tính chất cấu trúc tổ hợp - rời rạc 2.3. Lượng số, tập đếm được (tập hợp, ánh xạ, đồ thị 2.4. Quan hệ, quan hệ tương ...) đương, thứ tự, các tập sắp thự tự 2.5. Tổ hợp và chỉnh hợp 2.6. Phép đếm, các nguyên lý (cộng, nhân, bao gồm, loại trừ) Yêu cầu tự học đ/v sinh viên: 12 giờ 6, 7 Chương 3. Mô hình hoá L.O.3.1 – Hiểu biết về Bài tập trên xác suất- nhập môn lý thuyết xác suất (cơ lớp, bản) Bài tập về nhà 1. 2. L.O.3.2 – Hiểu biết về 3. biến ngẫu nhiên (chủ 3.1. Xác suất- tiên đề- cách yếu biến rời rạc) tính L.O.4.2 – Tính toán 3.2. Giới thiệu biến ngẫu nhiên xác suất và biến ngẫu nhiên (xác suất sự kiện, 4/6