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.
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ế.