Mục lục bài họcĐang ở d04-b1
Computational Thinking, Algorithm Design and Tracing
The four habits of computational thinking. Abstraction is deciding what to leave out: a route-planning program models a road network as nodes and weighted edges and ignores the colour of the tarmac, because those details do not affect the answer. Decomposition breaks a problem into sub-problems that can be solved and tested separately. Pattern recognition notices that two sub-problems have the same shape so that one solution serves both. Algorithmic thinking expresses the solution as an unambiguous finite sequence of steps. Examiners award marks for showing these in use, not for defining them.
Expressing an algorithm. A flowchart shows control flow graphically and is easy for non-programmers to read but becomes unwieldy for long algorithms. Pseudocode is language-independent, compact and close to real code, which is why it is used in examinations. Whichever is used, an algorithm must be unambiguous, must terminate, and must have defined inputs and outputs.
The building blocks. Every algorithm is built from four constructs. Sequence executes steps in order. Selection chooses between paths using a condition. Iteration repeats: a count-controlled loop repeats a known number of times, while a condition-controlled loop repeats until something becomes true, which is what you must use when the number of repetitions is not known in advance. Sub-programs package a block of code under a name and take parameters.
Why sub-programs matter more than they appear to. They avoid duplicating code, so a correction is made once rather than in many places. They allow independent testing, since a sub-program with defined inputs and outputs can be tested on its own. They let a large program be divided among several developers. And they support abstraction: the caller needs to know what the sub-program does, not how it does it, so the implementation can be replaced without touching the callers.
Tracing. A trace table records the value of every variable after each step. It is the standard way of determining what an unfamiliar algorithm actually does and of locating a fault. The discipline matters: one column per variable, one column per condition, one row per iteration, and an initialisation row before the loop begins. Attempting to trace mentally rather than on paper is the most common cause of lost marks in this topic.
Bốn thói quen của tư duy tính toán. Trừu tượng hoá là việc quyết định BỎ ĐI cái gì: một chương trình tìm đường mô hình hoá mạng lưới giao thông thành các đỉnh và các cạnh có trọng số, và bỏ qua màu của mặt đường, vì những chi tiết đó không ảnh hưởng tới đáp án. Phân rã chia một bài toán thành các bài toán con giải và kiểm thử được riêng rẽ. Nhận dạng mẫu nhận ra rằng 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. Tư duy thuật toán diễn đạt lời giải thành một dãy bước hữu hạn không mơ hồ. Giám khảo cho điểm khi thấy bốn thói quen này được SỬ DỤNG, không cho điểm cho việc định nghĩa chúng.
Diễn đạt một thuật toán. Lưu đồ thể hiện luồng điều khiển bằng hình vẽ nên người không biết lập trình đọc được, nhưng trở nên cồng kềnh với thuật toán dài. Mã giả độc lập với ngôn ngữ, gọn và gần với mã thật, đó là lý do nó được dùng trong bài thi. Dù dùng cách nào, một thuật toán phải không mơ hồ, phải dừng lại, và phải có đầu vào cùng đầu ra được xác định rõ.
Các khối xây dựng. Mọi thuật toán đều dựng từ bốn cấu trúc. Tuần tự thực hiện các bước theo thứ tự. Rẽ nhánh chọn giữa các hướng đi dựa trên một điều kiện. Lặp lặp lại: vòng lặp điều khiển bằng số đếm lặp một số lần đã biết, còn vòng lặp điều khiển bằng điều kiện lặp cho tới khi một điều kiện trở thành đúng — và đây là loại bắt buộc phải dùng khi chưa biết trước số lần lặp. Chương trình con đóng gói một khối mã dưới một cái tên và nhận tham số.
Vì sao chương trình con quan trọng hơn vẻ ngoài của nó. Nó tránh việc lặp mã, nên một chỗ sửa được làm một lần thay vì ở nhiều nơi. Nó cho phép kiểm thử độc lập, vì một chương trình con có đầu vào và đầu ra rõ ràng thì kiểm thử riêng được. Nó cho phép chia một chương trình lớn cho nhiều người cùng làm. Và nó hỗ trợ trừu tượng hoá: bên gọi chỉ cần biết chương trình con LÀM GÌ chứ không cần biết nó làm THẾ NÀO, nên phần cài đặt bên trong có thể thay hoàn toàn mà không phải sửa chỗ nào gọi nó.
Lần vết. Bảng lần vết ghi lại giá trị của mọi biến sau từng bước. Đây là cách chuẩn để xác định một thuật toán lạ thực sự làm gì và để định vị lỗi. Kỷ luật lập bảng là điều quan trọng: một cột cho mỗi biến, một cột cho mỗi điều kiện, một hàng cho mỗi lần lặp, và một hàng khởi tạo trước khi vào vòng lặp. Việc lần vết nhẩm trong đầu thay vì viết ra giấy là nguyên nhân mất điểm nhiều nhất trong chuyên đề này.
Cho thuật toán sau, với N là một số nguyên dương:
R = 0 ; T = N ; loop while T lớn hơn 0 ; R = R nhân 10 cộng T mod 10 ; T = T div 10 ; end loop ; output R
Lần vết với N bằng 4 073 và cho biết thuật toán làm gì. Sau đó chỉ ra nó gặp vấn đề gì với đầu vào 1 200.
Bảng lần vết với N bằng 4 073. Ba cột: T, T mod 10, R. Hàng khởi tạo: T bằng 4 073 và R bằng 0.
Lần 1: T mod 10 bằng 3, nên R bằng 0 nhân 10 cộng 3 bằng 3; T bằng 4 073 div 10 bằng 407.
Lần 2: T mod 10 bằng 7, nên R bằng 3 nhân 10 cộng 7 bằng 37; T bằng 40.
Lần 3: T mod 10 bằng 0, nên R bằng 37 nhân 10 cộng 0 bằng 370; T bằng 4.
Lần 4: T mod 10 bằng 4, nên R bằng 370 nhân 10 cộng 4 bằng 3 704; T bằng 0.
Kiểm tra điều kiện: T bằng 0 nên vòng lặp dừng. Kết quả xuất ra là 3 704.
Thuật toán làm gì. Đầu vào 4 073 cho đầu ra 3 704, tức các chữ số bị đảo ngược thứ tự. Cơ chế gồm hai phép toán phối hợp: phép mod 10 lấy ra chữ số cuối cùng, còn phép div 10 bỏ chữ số cuối đi. Việc nhân R với 10 trước khi cộng chữ số mới đẩy các chữ số đã có sang trái một vị trí, nên chữ số lấy ra sau cùng lại nằm ở vị trí cao nhất. Cặp mod 10 và div 10 là công cụ chuẩn cho mọi bài toán xử lý từng chữ số, và nhận ra nó là cách nhanh nhất để trả lời câu hỏi "thuật toán này làm gì".
Vấn đề với đầu vào 1 200. Lần vết nhanh: R lần lượt là 0, rồi 0, rồi 2, rồi 21. Đầu ra là 21 chứ không phải 0021. Nguyên nhân là kết quả được giữ dưới dạng số, và số không có khái niệm chữ số 0 đứng đầu. Về mặt toán học kết quả không sai, nhưng nếu yêu cầu là đảo ngược một chuỗi chữ số thì nó sai.
Cách sửa và bài học chung. Nếu cần giữ các chữ số 0 đứng đầu thì phải xử lý đầu vào như một chuỗi ký tự chứ không như một số, và đảo chuỗi đó. Bài học để nêu trong bài thi: chọn kiểu dữ liệu là một quyết định thiết kế chứ không phải chi tiết kỹ thuật — cùng một dãy chữ số, biểu diễn bằng số hay bằng chuỗi sẽ cho hai hành vi khác nhau, và trường hợp lộ ra khác biệt đó là các trường hợp biên như số kết thúc bằng 0.
Một chương trình quản lý điểm dài 400 dòng viết liền một mạch trong thân chính. Hãy nêu các vấn đề nó gây ra và mô tả việc phân rã thành chương trình con thay đổi tình hình như thế nào.
Vấn đề 1 — không kiểm thử được từng phần. Với mã viết liền, cách duy nhất để kiểm thử là chạy cả chương trình và nhìn kết quả cuối. Nếu kết quả sai, lỗi có thể nằm ở bất cứ đâu trong 400 dòng. Khi tách thành các chương trình con như đọc điểm, tính trung bình, xếp loại và xuất báo cáo, mỗi chương trình con có đầu vào và đầu ra xác định nên kiểm thử được riêng: gọi hàm xếp loại với các giá trị biên 39, 40, 69, 70 và xác nhận nó trả về đúng, hoàn toàn độc lập với phần còn lại.
Vấn đề 2 — mã lặp lại, nên lỗi cũng lặp lại. Trong mã viết liền, cùng một đoạn kiểm tra tính hợp lệ của điểm thường bị chép lại ở nhiều chỗ. Khi phát hiện lỗi ở đoạn đó, người sửa phải nhớ tìm hết mọi bản sao; bỏ sót một bản là để lại lỗi. Với một chương trình con duy nhất, chỗ sửa chỉ có một.
Vấn đề 3 — không chia việc được. Bốn người không thể cùng sửa một tệp 400 dòng viết liền mà không giẫm chân nhau. Khi chương trình được phân rã và các chương trình con giao tiếp qua tham số và giá trị trả về, mỗi người nhận một phần và chỉ cần thống nhất về giao diện giữa chúng.
Vấn đề 4 — không thay được phần cài đặt. Đây là điểm sâu nhất và cũng là điểm ăn điểm. Khi thuật toán xếp loại nằm rải rác trong thân chính, việc đổi thang điểm buộc phải đọc lại toàn bộ chương trình để tìm mọi chỗ liên quan. Khi nó nằm gọn trong một chương trình con, bên gọi chỉ cần biết nó nhận một điểm và trả về một xếp loại; phần bên trong có thể được viết lại hoàn toàn — đổi thang, đổi cách làm tròn, tra cứu từ tệp cấu hình — mà không một dòng nào ở chỗ gọi phải sửa. Đây chính là trừu tượng hoá áp dụng vào cấu trúc chương trình.
Hai khái niệm nên nêu tên để lấy điểm. Phân rã tốt hướng tới độ gắn kết cao trong mỗi chương trình con — nó làm đúng một việc rõ ràng — và độ ràng buộc thấp giữa các chương trình con, tức chúng trao đổi với nhau qua tham số chứ không qua các biến toàn cục dùng chung. Ràng buộc qua biến toàn cục là nguyên nhân khiến một thay đổi ở nơi này gây lỗi ở nơi tưởng như không liên quan.
Bẫy 2 — dùng vòng lặp có số đếm khi chưa biết trước số lần lặp. Nếu số lần lặp phụ thuộc dữ liệu hoặc phụ thuộc người dùng, phải dùng vòng lặp điều khiển bằng điều kiện. Chọn sai loại vòng lặp là lỗi thiết kế, không phải lỗi cú pháp.
Bẫy 3 — chỉ ĐỊNH NGHĨA trừu tượng hoá và phân rã thay vì CHỈ RA chúng trong ví dụ. Câu hỏi luôn hỏi các khái niệm này được áp dụng thế nào vào tình huống cụ thể trong đề, nên câu trả lời phải bám vào tình huống đó.
Đọc xong rồi — làm thử ngay
Bài tập của chương Computational Thinking, Problem-Solving and Programming gồm 14 câu trắc nghiệm và 5 đề tự luận. Đáp án hiện ngay khi chọn, miễn phí.