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.
Chưa có bài thi nào cho chủ đề này.
Chủ đề liên quan
MAD101 - Toán rời rạcMAD101 - 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ế.