Mục lục bài họcĐang ở d10-b3
Computational thinking and problem solving
The four elements
Decomposition breaks a problem into subproblems small enough to solve. Pattern recognition spots that two subproblems are the same shape, so one solution serves both. Abstraction removes detail that does not matter for the problem at hand. Algorithm design writes the sequence of steps.
Abstraction is the one that is misunderstood
It does not mean 'making something vague'. It means deliberately ignoring detail that is irrelevant to the purpose. A underground railway map is a classic example: it discards true distances and geography because a passenger only needs the order of stops and where lines cross. The same map would be useless for planning a walk — abstraction is always relative to a purpose, and saying that earns the mark.
Caching and prefetching as abstraction in hardware
A cache stores recently used data close to the processor so the next access is fast; it works because programs display locality of reference — they reuse the same data and run through nearby addresses. Prefetching guesses what will be needed next and loads it early.
Judging an algorithm
Correctness first: does it produce the right answer for every valid input, including boundary cases? Then efficiency in time and in memory. Then readability and maintainability, which matter because most of a system's cost is maintenance. A faster algorithm nobody can understand is a liability.
Bringing the course together
Almost every A2 question is a variant of the same shape: given a situation, choose an approach, justify it against the constraints in the case, and state what it costs. Data structure, algorithm, architecture, network and methodology questions all reward the same discipline — name the trade-off rather than declaring one option best.
Bốn thành phần
Phân rã chia bài toán thành các bài toán con đủ nhỏ để giải được. Nhận dạng quy luật phát hiện hai bài toán con có cùng hình dạng, nên một lời giải dùng được cho cả hai. Trừu tượng hoá loại bỏ những chi tiết không quan trọng với bài toán đang xét. Thiết kế thuật toán viết ra trình tự các bước.
Trừu tượng hoá là thành phần hay bị hiểu sai nhất
Nó KHÔNG có nghĩa là ‘làm cho mơ hồ đi’. Nó nghĩa là cố ý bỏ qua những chi tiết không liên quan tới mục đích. Bản đồ tàu điện ngầm là ví dụ kinh điển: nó bỏ khoảng cách thật và địa hình vì hành khách chỉ cần biết thứ tự các ga và chỗ các tuyến giao nhau. Chính bản đồ đó lại vô dụng nếu muốn đi bộ — trừu tượng hoá luôn gắn với một MỤC ĐÍCH, và nói được điều đó là chỗ ăn điểm.
Bộ nhớ đệm và nạp trước — trừu tượng hoá ở mức phần cứng
Bộ nhớ đệm giữ dữ liệu vừa dùng ở gần bộ xử lý để lần truy cập sau nhanh hơn; nó hiệu quả vì chương trình có tính cục bộ tham chiếu — chúng dùng lại cùng một dữ liệu và chạy qua các địa chỉ gần nhau. Nạp trước thì đoán thứ sắp cần và tải sẵn.
Đánh giá một thuật toán
Tính đúng đắn trước tiên: nó có cho kết quả đúng với MỌI đầu vào hợp lệ, kể cả các trường hợp biên, không? Rồi mới tới hiệu quả về thời gian và bộ nhớ. Sau đó là tính dễ đọc và dễ bảo trì, vốn quan trọng vì phần lớn chi phí của một hệ thống nằm ở khâu bảo trì. Một thuật toán nhanh mà không ai hiểu nổi là một gánh nặng.
Gói lại cả chương trình
Gần như mọi câu hỏi A2 đều là biến thể của cùng một khuôn: cho một tình huống, chọn một cách làm, biện minh dựa trên các ràng buộc trong tình huống đó, và nêu cái giá phải trả. Câu hỏi về cấu trúc dữ liệu, thuật toán, kiến trúc, mạng hay phương pháp luận đều thưởng cho cùng một kỷ luật — gọi tên sự đánh đổi thay vì tuyên bố một phương án là tốt nhất.
Một trường muốn xây hệ thống xếp thời khoá biểu: $60$ lớp, $45$ giáo viên, $30$ phòng, mỗi lớp cần $8$ môn mỗi tuần, không giáo viên nào dạy hai lớp cùng lúc, không phòng nào dùng cho hai lớp cùng lúc, và phòng thí nghiệm chỉ dùng cho môn thực hành.
Áp dụng bốn thành phần tư duy tính toán.
Phân rã — chia bài toán lớn thành các bài toán con giải được.
$1.$ Biểu diễn dữ liệu: lớp, giáo viên, phòng, môn, tiết học.
$2.$ Kiểm tra ràng buộc: cho một cách xếp, nó có vi phạm quy tắc nào không.
$3.$ Sinh phương án xếp lịch.
$4.$ Đánh giá và cải thiện một phương án hợp lệ (ví dụ giảm số tiết trống của giáo viên).
$5.$ Hiển thị và in thời khoá biểu.
Chú ý bài toán con số $2$ tách riêng khỏi số $3$: việc kiểm ràng buộc phải độc lập với việc sinh phương án, vì nó được gọi hàng nghìn lần và cần tối ưu riêng.
Nhận dạng quy luật — tìm chỗ giống nhau để viết một lời giải dùng nhiều lần.
Ba ràng buộc ‘giáo viên không dạy hai chỗ cùng lúc’, ‘phòng không dùng hai chỗ cùng lúc’ và ‘lớp không học hai môn cùng lúc’ có cùng một hình dạng: một tài nguyên không được xuất hiện hai lần trong cùng một tiết.
Vậy chỉ cần viết MỘT hàm KiemTrungLich(tai_nguyen, tiet) và gọi nó ba lần, thay vì viết ba đoạn mã gần giống nhau. Đây chính là giá trị thực tế của nhận dạng quy luật — ít mã hơn, ít lỗi hơn, và sửa một chỗ là sửa cả ba.
Trừu tượng hoá — bỏ những gì không liên quan tới mục đích.
Hệ thống KHÔNG cần biết: tên môn học đầy đủ, nội dung bài giảng, tuổi giáo viên, diện tích phòng, hay số học sinh trong lớp.
Nó chỉ cần: mã tài nguyên, tiết học nào, và một cờ đánh dấu phòng có phải phòng thí nghiệm không cùng cờ môn có phải môn thực hành không.
Lưu ý trừu tượng hoá gắn với mục đích: nếu sau này trường muốn hệ thống kiểm cả sức chứa phòng, thì số học sinh trở thành thông tin cần thiết. Cùng một dữ liệu, khác mục đích, khác mức trừu tượng.
Thiết kế thuật toán.
Cách đơn giản nhất là quay lui: xếp lần lượt từng lớp – từng môn vào tiết đầu tiên còn hợp lệ, và nếu bế tắc thì lùi lại đổi lựa chọn trước đó.
Nhưng phải nêu vấn đề hiệu năng: số tổ hợp cực lớn, nên quay lui thuần tuý có thể chạy rất lâu. Cách xử lý thực tế là xếp các ràng buộc CHẶT nhất trước — các môn thực hành cần phòng thí nghiệm, vì chúng có ít lựa chọn nhất — rồi mới xếp phần còn lại. Đây là ví dụ cho thấy chọn thứ tự xử lý quan trọng không kém việc chọn thuật toán.
Đọc xong rồi — làm thử ngay
Bài tập của chương Advanced Architecture, Networks and Computational Thinking gồm 14 câu trắc nghiệm và 3 đề tự luận. Đáp án hiện ngay khi chọn, miễn phí.