Mục lục bài họcĐang ở d06-b1
Decomposition and design tools
The program development life cycle
- analysis — work out exactly what the problem is and what the program must do;
- design — plan the solution using structure diagrams, flowcharts or pseudocode;
- coding — write the program in a programming language;
- testing — run it with planned test data and correct the errors found.
The order matters, and the reason is practical: an error found in analysis costs minutes to fix; the same error found after coding may mean rewriting a large part of the program.
Decomposition
Decomposition means breaking a problem into smaller sub-problems until each is simple enough to solve. Every problem is described in terms of:
- inputs — the data that goes in;
- processes — what is done with that data;
- outputs — the results that come out.
Why it helps: each sub-problem can be written and tested separately, several people can work on different parts at once, and a part written once can be reused.
Three design tools
| structure diagram | shows the hierarchy — how the problem breaks into sub-tasks, and how those break down further |
| flowchart | shows the order of steps and the decisions taken |
| pseudocode | describes the steps in structured English, close to code but not a real language |
Flowchart symbols to know: an oval for start and stop; a parallelogram for input and output; a rectangle for a process; a diamond for a decision, with one arrow in and two out labelled yes and no.
Pseudocode is not a real language — it cannot be run. Its purpose is to let the programmer plan the logic without worrying about the exact syntax of any one language, and to communicate the design to someone who uses a different language.
Standard methods
Linear search — check each item in turn from the start until the target is found or the list ends.
It works on any list, sorted or not, but on a long list it is slow: on average it checks half the items.
Bubble sort — compare each pair of adjacent items and swap them if they are in the wrong order; repeat passes until a whole pass makes no swaps.
Note why the "no swaps" condition is the correct stopping rule: it is the only way the algorithm can know the list is fully sorted.
Totalling and counting
Two operations that appear in almost every algorithm:
- totalling — keeping a running sum: $\text{total} \leftarrow \text{total} + \text{value}$;
- counting — keeping a running count: $\text{count} \leftarrow \text{count} + 1$.
Both must be initialised to zero before the loop. Forgetting this is one of the most common errors in written algorithms.
Vòng đời phát triển chương trình.
- phân tích — xác định chính xác vấn đề là gì và chương trình phải làm được những gì;
- thiết kế — lập kế hoạch lời giải bằng sơ đồ cấu trúc, lưu đồ hoặc mã giả;
- viết mã — viết chương trình bằng một ngôn ngữ lập trình;
- kiểm thử — chạy với bộ dữ liệu thử đã chuẩn bị và sửa các lỗi tìm được.
Thứ tự này quan trọng, và lý do rất thực tế: một sai sót phát hiện ở bước phân tích tốn vài phút để sửa; đúng sai sót đó phát hiện sau khi đã viết mã có thể buộc phải viết lại một phần lớn chương trình.
Phân rã bài toán. Phân rã nghĩa là chia một bài toán thành các bài toán con nhỏ hơn cho tới khi mỗi phần đủ đơn giản để giải. Mọi bài toán đều được mô tả qua ba thứ:
- đầu vào — dữ liệu đưa vào;
- xử lý — làm gì với dữ liệu đó;
- đầu ra — kết quả đưa ra.
Vì sao phân rã có ích: mỗi bài toán con viết và kiểm thử riêng được, nhiều người làm song song các phần khác nhau, và một phần đã viết có thể dùng lại.
Ba công cụ thiết kế.
- Sơ đồ cấu trúc — cho thấy thứ bậc: bài toán chia thành những nhiệm vụ con nào, và mỗi nhiệm vụ con lại chia tiếp ra sao;
- Lưu đồ — cho thấy trình tự các bước và các nhánh rẽ;
- Mã giả — mô tả các bước bằng tiếng Anh có cấu trúc, gần với mã thật nhưng không phải ngôn ngữ lập trình.
Các ký hiệu lưu đồ cần thuộc: hình bầu dục cho bắt đầu và kết thúc; hình bình hành cho nhập và xuất; hình chữ nhật cho một bước xử lý; hình thoi cho một quyết định, với một mũi tên vào và hai mũi tên ra ghi có và không.
Mã giả không chạy được. Mục đích của nó là để lập trình viên lập kế hoạch cho phần logic mà chưa phải lo cú pháp chính xác của ngôn ngữ nào, và để truyền đạt thiết kế cho người dùng ngôn ngữ khác.
Các phương pháp chuẩn.
Tìm kiếm tuyến tính — kiểm lần lượt từng phần tử từ đầu danh sách cho tới khi tìm thấy hoặc hết danh sách.
Nó dùng được cho mọi danh sách, sắp xếp hay chưa, nhưng với danh sách dài thì chậm: trung bình nó phải kiểm một nửa số phần tử.
Sắp xếp nổi bọt — so sánh từng cặp phần tử liền kề và đổi chỗ nếu chúng sai thứ tự; lặp lại các lượt duyệt cho tới khi có một lượt không đổi chỗ lần nào.
Chú ý vì sao điều kiện “không đổi chỗ lần nào” là quy tắc dừng đúng: đó là cách duy nhất để thuật toán biết được danh sách đã sắp xong.
Tính tổng và đếm. Hai thao tác có mặt trong gần như mọi thuật toán:
- tính tổng — giữ một tổng chạy: $\text{tong} \leftarrow \text{tong} + \text{gia\_tri}$;
- đếm — giữ một biến đếm: $\text{dem} \leftarrow \text{dem} + 1$.
Cả hai bắt buộc phải được gán bằng không trước vòng lặp. Quên bước này là một trong những lỗi phổ biến nhất khi viết thuật toán.
Một chương trình đọc điểm của $30$ học sinh, tính điểm trung bình, và đếm bao nhiêu em đạt từ $50$ trở lên. (a) Phân rã bài toán thành đầu vào, xử lý, đầu ra. (b) Viết mã giả. (c) Nêu lỗi phổ biến nhất khi viết thuật toán dạng này.
(a) Phân rã bài toán.
Đầu vào: $30$ điểm số.
Xử lý: cộng dồn các điểm thành một tổng; kiểm mỗi điểm xem có $\ge 50$ không và đếm số em đạt; chia tổng cho $30$ để ra điểm trung bình.
Đầu ra: điểm trung bình, và số học sinh đạt.
(b) Mã giả.
$\text{tong} \leftarrow 0$
$\text{dem\_dat} \leftarrow 0$
$\textbf{FOR } i \leftarrow 1 \textbf{ TO } 30$
$\quad \textbf{INPUT } \text{diem}$
$\quad \text{tong} \leftarrow \text{tong} + \text{diem}$
$\quad \textbf{IF } \text{diem} \ge 50 \textbf{ THEN}$
$\quad\quad \text{dem\_dat} \leftarrow \text{dem\_dat} + 1$
$\quad \textbf{ENDIF}$
$\textbf{NEXT } i$
$\text{trung\_binh} \leftarrow \text{tong} / 30$
$\textbf{OUTPUT } \text{trung\_binh}, \text{dem\_dat}$
(c) Lỗi phổ biến nhất: quên gán biến bằng không trước vòng lặp.
Cả biến tổng lẫn biến đếm đều phải được đặt về $0$ trước khi vòng lặp bắt đầu.
Nếu quên: biến sẽ mang một giá trị không xác định — có thể là rác trong bộ nhớ, hoặc giá trị còn sót từ lần chạy trước. Mọi phép cộng dồn sau đó đều cộng lên một nền sai.
Điều nguy hiểm là chương trình vẫn chạy và vẫn cho ra một con số, chỉ là con số đó sai. Lỗi kiểu này không báo gì cả nên rất khó phát hiện.
Lỗi phổ biến thứ hai: đặt lệnh gán bằng không bên trong vòng lặp. Khi đó tổng bị xoá về $0$ ở mỗi vòng, nên kết quả cuối chỉ bằng điểm của học sinh cuối cùng.
Giải thích cách sắp xếp nổi bọt hoạt động, và vì sao điều kiện dừng phải là “một lượt duyệt không đổi chỗ lần nào” chứ không phải một số lượt cố định.
Cách hoạt động.
Bước 1. Bắt đầu từ đầu danh sách, so sánh hai phần tử liền kề.
Bước 2. Nếu chúng sai thứ tự thì đổi chỗ cho nhau.
Bước 3. Dịch sang cặp tiếp theo và lặp lại tới cuối danh sách. Đó là một lượt duyệt.
Bước 4. Lặp lại các lượt duyệt cho tới khi một lượt trọn vẹn không đổi chỗ lần nào.
Vì sao gọi là “nổi bọt”: sau mỗi lượt, phần tử lớn nhất trong phần chưa sắp sẽ trôi dần về cuối, giống bọt khí nổi lên.
Vì sao quy tắc dừng phải là “không đổi chỗ lần nào”.
Lý do một — đó là dấu hiệu duy nhất chứng minh đã sắp xong.
Nếu một lượt duyệt đi hết danh sách mà không phải đổi chỗ lần nào, nghĩa là mọi cặp liền kề đều đã đúng thứ tự. Mà nếu mọi cặp liền kề đều đúng thứ tự thì cả danh sách đã đúng thứ tự.
Đây là cách duy nhất thuật toán biết được nó đã xong — nó không nhìn tổng thể danh sách bao giờ.
Lý do hai — một số lượt cố định thì hoặc thừa, hoặc thiếu.
Danh sách gần như đã sắp sẵn có thể xong sau một lượt. Nếu ép chạy đủ số lượt cố định, ta lãng phí rất nhiều lượt duyệt vô ích.
Ngược lại, nếu đặt số lượt quá ít, thuật toán sẽ dừng khi danh sách còn chưa sắp xong — và nó trả về kết quả sai mà không báo gì cả.
Điểm đáng nêu thêm. Để chắc chắn trong mọi trường hợp, một danh sách $n$ phần tử cần tối đa $n-1$ lượt duyệt. Nhưng dùng cờ báo “có đổi chỗ hay không” vẫn tốt hơn, vì nó dừng ngay khi xong thay vì luôn chạy hết số lượt tối đa.
Đọc xong rồi — làm thử ngay
Bài tập của chương Algorithm Design and Problem-Solving 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í.