MAD101 - Toán rời rạc
Chủ đề học tập
MAD101 - Phần 1: Logic mệnh đề và logic vị từ
Ứng với CLO1, buổi 1-8. Tương ứng Chương 1 của Rosen ở cả ấn bản 6 và 7. Phần logic mệnh đề gồm mệnh đề và giá trị chân lý, các phép nối phủ định - hội - tuyển - tuyển loại - kéo theo - tương đương, bảng chân trị, độ ưu tiên toán tử, mệnh đề đảo và phản đảo và nghịch, dịch qua lại giữa câu tiếng Việt và biểu thức logic. Phần tương đương logic gồm hằng đúng, mâu thuẫn, tiếp liên, các luật tương đương và luật De Morgan, cách chứng minh hai mệnh đề tương đương. Phần vị từ và lượng từ gồm phân biệt vị từ với mệnh đề, lượng từ với mọi và tồn tại, phủ định lượng từ, lượng từ lồng nhau cùng khác biệt giữa hai thứ tự lượng từ. Khép lại bằng các quy tắc suy diễn và cách kiểm tra một lập luận có hợp lệ hay không. Theo syllabus, bỏ qua mạch logic và tính thoả được.
MAD101 - Phần 2: Tập hợp, hàm số và dãy số
Ứng với CLO2, buổi 9-14. Tương ứng Chương 2 của Rosen ở cả ấn bản 6 và 7. Phần tập hợp gồm phần tử, tập con và tập con thực sự, tập rỗng, lực lượng, tập luỹ thừa, tích Descartes và cách biểu diễn một tập con bằng chuỗi bit trong máy tính. Phần phép toán tập hợp gồm hợp, giao, hiệu, phần bù, hiệu đối xứng, các đẳng thức tập hợp và cách chứng minh hai tập bằng nhau, hợp và giao suy rộng. Phần hàm số gồm miền xác định, miền giá trị, ảnh và tạo ảnh, hàm đơn ánh, toàn ánh, song ánh, hàm ngược, hàm hợp, hàm sàn và hàm trần cùng ứng dụng so sánh lực lượng hai tập. Phần dãy số gồm tìm công thức tổng quát, cấp số cộng và cấp số nhân, tính tổng hữu hạn với các công thức tổng đặc biệt. Theo syllabus, bỏ qua hàm bộ phận và hệ thức truy hồi ở mục này.
MAD101 - Phần 3: Nguyên lý đếm cơ bản
Ứng với CLO6, buổi 15-16, và là phần cuối cùng nằm trong Progress Test 1. Đây là mục 5.1 theo cách đánh số của syllabus, tương ứng mục 6.1 của Rosen ấn bản 7. Nội dung xoay quanh bốn quy tắc đếm nền tảng: quy tắc nhân cho các lựa chọn thực hiện nối tiếp nhau, quy tắc cộng cho các trường hợp rời nhau, quy tắc trừ tức nguyên lý bù trừ cho hai tập giao nhau, và quy tắc chia khi mỗi kết quả bị đếm lặp một số lần như nhau. Phần bài tập tập trung vào cách nhận ra nên dùng quy tắc nào, cách kết hợp nhiều quy tắc trong một bài toán, dùng sơ đồ cây để liệt kê có hệ thống, và các ứng dụng đếm quen thuộc trong tin học như đếm số mật khẩu hợp lệ, số chuỗi bit thoả điều kiện, số địa chỉ mạng hay số biển số.
MAD101 - Phần 4: Thuật toán và độ phức tạp
Ứng với CLO3, buổi 19-21. Đây là mục 3.1-3.3 theo cách đánh số của syllabus, tương ứng Chương 3 của Rosen ấn bản 7. Phần thuật toán trình bày định nghĩa và các tính chất bắt buộc gồm đầu vào, đầu ra, tính xác định, tính đúng đắn, tính hữu hạn, tính hiệu quả và tính tổng quát, cách viết mã giả, cùng các thuật toán mẫu: tìm kiếm tuyến tính, tìm kiếm nhị phân, sắp xếp nổi bọt, sắp xếp chèn và thuật toán tham lam. Phần độ tăng của hàm giới thiệu ký hiệu big-O cùng cặp nhân chứng, và hai ký hiệu bổ sung big-Omega cho cận dưới và big-Theta cho cận chặt, kèm thứ tự tăng của các hàm thông dụng. Phần độ phức tạp bàn về độ phức tạp thời gian, trường hợp xấu nhất và trung bình, bài toán khả giải và bất khả giải trên thực tế.
MAD101 - Phần 5: Số nguyên, số nguyên tố và số học modulo
Ứng với CLO4, buổi 22-28. Đây là mục 3.4-3.6 theo cách đánh số của syllabus, nhưng tương ứng Chương 4 của Rosen ấn bản 7. Phần số nguyên và phép chia gồm quan hệ chia hết, thuật toán chia với thương và số dư, hai phép div và mod, đồng dư thức và số học theo modulo, cùng ba ứng dụng trong tin học là hàm băm, sinh số giả ngẫu nhiên bằng phương pháp đồng dư tuyến tính và mật mã cổ điển với mã Caesar. Phần số nguyên tố gồm định lý cơ bản của số học, kiểm tra tính nguyên tố bằng phép chia thử, sàng Eratosthenes, tính vô hạn của tập số nguyên tố, ước chung lớn nhất và bội chung nhỏ nhất, số nguyên tố cùng nhau và thuật toán Euclid. Phần thuật toán trên số nguyên gồm biểu diễn cơ số b, hệ nhị phân - bát phân - thập lục phân, phép cộng và nhân nhị phân, luỹ thừa modulo nhanh.
MAD101 - Phần 6: Quy nạp và đệ quy
Ứng với CLO5, buổi 29-34. Đây là Chương 4 theo cách đánh số của syllabus, tương ứng Chương 5 của Rosen ấn bản 7. Phần quy nạp toán học trình bày cấu trúc hai bước gồm bước cơ sở và bước quy nạp, cách viết một chứng minh quy nạp hoàn chỉnh, và các dạng bài quen thuộc: chứng minh công thức tổng, chứng minh bất đẳng thức, chứng minh tính chia hết. Phần quy nạp mạnh chỉ ra khi nào giả thiết quy nạp thông thường là chưa đủ và phải giả thiết đúng với mọi giá trị nhỏ hơn, kèm mối liên hệ với nguyên lý sắp thứ tự tốt. Phần định nghĩa đệ quy gồm hàm định nghĩa đệ quy như giai thừa và dãy Fibonacci, tập hợp và cấu trúc định nghĩa đệ quy, cùng quy nạp cấu trúc. Phần thuật toán đệ quy so sánh đệ quy với lặp và phân tích thuật toán sắp xếp trộn.
MAD101 - Phần 7: Hệ thức truy hồi và chia để trị
Ứng với CLO6, buổi 35-36, khép lại nội dung của Progress Test 2. Đây là Chương 7 theo cách đánh số của syllabus, tương ứng Chương 8 của Rosen ấn bản 7. Phần hệ thức truy hồi bắt đầu từ việc mô hình hoá một bài toán đếm bằng hệ thức truy hồi, với các ví dụ kinh điển là lãi kép, bài toán sinh sản của thỏ dẫn tới dãy Fibonacci, tháp Hà Nội và đếm chuỗi bit thoả điều kiện; sau đó là kỹ thuật giải hệ thức truy hồi tuyến tính thuần nhất hệ số hằng qua phương trình đặc trưng, xử lý cả trường hợp nghiệm phân biệt lẫn nghiệm bội. Phần chia để trị xây dựng hệ thức truy hồi dạng chia để trị cho các thuật toán như tìm kiếm nhị phân, sắp xếp trộn và nhân số nguyên nhanh, rồi dùng định lý thợ để ước lượng độ phức tạp. Theo syllabus, bỏ qua quy hoạch động.
MAD101 - Phần 8: Đồ thị
Ứng với CLO7, buổi 39-48. Đây là Chương 9 theo cách đánh số của syllabus, nhưng tương ứng Chương 10 của Rosen ấn bản 7. Nội dung gồm: phân loại đồ thị thành đơn đồ thị, đa đồ thị, giả đồ thị và đồ thị có hướng cùng các mô hình đồ thị trong thực tế; thuật ngữ với kề, liên thuộc, bậc đỉnh và định lý bắt tay, các đồ thị đặc biệt gồm đồ thị đầy đủ, chu trình, bánh xe, khối n chiều và đồ thị hai phía cùng bài toán ghép cặp; biểu diễn đồ thị bằng danh sách kề, ma trận kề, ma trận liên thuộc và bài toán đẳng cấu đồ thị qua các bất biến; tính liên thông, thành phần liên thông, đỉnh cắt và cạnh cắt, đếm đường đi bằng luỹ thừa ma trận kề; điều kiện tồn tại đường đi và chu trình Euler theo bậc đỉnh, đường đi và chu trình Hamilton cùng điều kiện đủ Dirac và Ore; cuối cùng là đồ thị có trọng số và thuật toán Dijkstra tìm đường đi ngắn nhất.
MAD101 - Phần 9: Cây
Ứng với CLO8, buổi 49-58, phần cuối cùng của môn. Đây là Chương 10 theo cách đánh số của syllabus, nhưng tương ứng Chương 11 của Rosen ấn bản 7. Phần nhập môn định nghĩa cây là đồ thị liên thông không có chu trình, cây có gốc cùng bộ thuật ngữ cha - con - anh em - tổ tiên - hậu duệ - lá - đỉnh trong - cây con, cây m-phân và cây m-phân đầy đủ, mức và chiều cao, cùng các tính chất đếm đỉnh và cạnh. Phần ứng dụng gồm cây tìm kiếm nhị phân, cây quyết định và cận dưới độ phức tạp của sắp xếp bằng so sánh, mã tiền tố và mã Huffman. Phần duyệt cây gồm duyệt theo thứ tự trước, giữa, sau và ký pháp trung tố - tiền tố - hậu tố cùng cách tính giá trị biểu thức. Phần cây khung gồm tìm kiếm theo chiều sâu, theo chiều rộng, và tìm cây khung nhỏ nhất bằng thuật toán Prim và Kruskal.