Tin học 12 KHMT: Thuật toán và lập trình, năm khâu và bản hợp đồng của chương trình | LUKATO AI
Bài giảng khái niệm Tin học 12 định hướng Khoa học máy tính: đi từ yêu cầu, dữ liệu, chiến lược, mã và ca thử đến phép đo, với 11 phòng lab tương tác, 14 bẫy…
LUKATO AI · TIN HỌC 12 · KHOA HỌC MÁY TÍNH
YÊU CẦU · DỮ LIỆU · CHIẾN LƯỢC · MÃ VÀ CA THỬ · PHÉP ĐO
Từ bài toán đến chương trình chạy đúng:
năm khâu và bản hợp đồng
mà mỗi thuật toán mang theo
Một chương trình tốt cần hơn là kết quả đúng với ví dụ mẫu. Nó còn phải chạy xong trong thời gian chấp nhận được, vừa bộ nhớ của thiết bị và đúng cả ở những dữ liệu biên mà người viết chưa nghĩ tới. Bài giảng này nối năm khâu : hiểu yêu cầu , đặt dữ liệu vào cấu trúc phù hợp, chọn chiến lược giải, viết mã và ca thử , rồi đo chi phí. Xuyên suốt cả năm khâu là một lớp nền: mỗi thuật toán và mỗi cấu trúc dữ liệu là một lời hứa kèm điều kiện, và điều kiện bị phá thì lời hứa không còn. Phần nào là kiến thức bổ sung đều được ghi rõ; các con số trong lab là số liệu minh họa.
- ① Vì sao hai chương trình cùng cho kết quả đúng mà một cái xong trong nháy mắt, còn cái kia chạy lâu hơn cả đời người?
- ② Điều gì phải đúng ở mỗi vòng lặp và mỗi lời gọi đệ quy để cả chương trình đúng?
- ③ Khi chương trình qua các ví dụ em đã thử, em còn thiếu gì để tin nó?
5+1
năm khâu của khung, cộng một lớp nền là bản hợp đồng điều kiện
11 lab
phòng lab: xếp khâu, bùng nổ vét cạn, bảng băm, chọn cấu trúc dữ liệu, duyệt từng lớp, vùng bất biến, sắp xếp chọn, bắt lỗi bằng ca thử, ghi nhớ kết quả, lắp hàm đệ quy, bộ nhớ
14 bẫy
mỗi bẫy có mục, phòng lab và bài để quay lại luyện
9 bài
8 chọn đáp án, 1 trả lời ngắn
01
Bản đồ chung
Năm khâu và bản hợp đồng của thuật toán
Giải một bài toán bằng máy tính là đi qua một dây chuyền: đọc cho rõ yêu cầu, chọn cách tổ chức dữ liệu, chọn chiến lược giải, viết mã rồi thử, và cuối cùng đo xem chương trình tốn bao nhiêu thời gian và bộ nhớ. Học từng thuật toán rời rạc thì dễ nhớ tên mà khó biết dùng khi nào. Cái giúp dùng đúng là một câu hỏi lặp lại ở cả năm khâu: thuật toán này hứa điều gì, và lời hứa ấy đúng với điều kiện nào? Em sẽ thấy câu hỏi ấy giải thích vì sao tìm đường ít cạnh nhất cần đồ thị không trọng số, vì sao hai chương trình cùng đúng vẫn khác nhau xa, và vì sao một ca thử đúng chưa đủ để tin cả chương trình.
Vuốt ngang để xem đầy đủ hình.
Bản đồ năm khâu: yêu cầu, dữ liệu, chiến lược, mã và ca thử, phép đo nối nhau theo dòng đi từ bài toán đến chương trình chạy đúng; kết quả đo quay lại để đổi cấu trúc hoặc chiến lược. Lớp nền bao quanh là bản hợp đồng điều kiện. Bấm vào một khối để đọc mô tả và số mục.
Điều giúp khung dùng được lâu là một phép đo gồm ba đại lượng. Một chương trình được xem là đạt khi nó thỏa đồng thời ba điều kiện:
\text{đạt}=\text{đúng}\ \land\ \text{đủ nhanh}\ \land\ \text{vừa bộ nhớ}
Ba vế này nằm ở ba khâu khác nhau. Vế đúng được bảo vệ ở khâu mã và ca thử. Vế đủ nhanh và vừa bộ nhớ được ước lượng ở khâu phép đo, nhưng thực ra đã được quyết định sớm hơn, từ lúc chọn cấu trúc dữ liệu và chiến lược. Thiếu một vế thì chương trình chưa đạt, dù hai vế còn lại rất đẹp. Đây là mô hình LUKATO để học, không phải một quy định chuẩn.
Năm khâu và lớp nền
Khâu
Việc làm
Ví dụ thường gặp
Mục
① YÊU CẦU
Đọc bài toán thành dữ liệu vào, kết quả ra và giới hạn của kích thước n
ghi n lớn nhất, hỏi dữ liệu đã sắp xếp chưa, đồ thị có độ dài cạnh không
② DỮ LIỆU
Chọn cách đặt dữ liệu trong bộ nhớ theo các thao tác sẽ làm nhiều nhất
mảng cho đọc theo số thứ tự, danh sách liên kết cho thêm vào đầu, bảng băm cho tra theo khóa
③ CHIẾN LƯỢC
Chọn cách duyệt hoặc cách chia nhỏ bài toán
vét cạn, duyệt từng lớp bằng hàng đợi, đệ quy, ghi nhớ kết quả bài toán con
4, 6
④ MÃ VÀ CA THỬ
Viết từng vòng lặp sao cho đúng và thử bằng các ca được chọn có chủ đích
câu đúng trước mỗi vòng, ca mảng rỗng, ca một phần tử, ca các giá trị bằng nhau
⑤ PHÉP ĐO
Ước lượng số bước và lượng bộ nhớ khi n tăng
số phép so sánh, thời gian khi n lớn, bộ nhớ khi số bản ghi tăng
LỚP NỀN · HỢP ĐỒNG
Ghi rõ điều kiện đi kèm mỗi lời hứa và kiểm tra điều kiện ấy trước khi dùng
dãy phải đã sắp, đồ thị không trọng số, khóa phân bố khá đều
1, 8
Chia thành năm khâu cộng một lớp nền là cách phân loại của LUKATO để xâu chuỗi các bài. Việc xếp «đệ quy» và «ghi nhớ kết quả» vào khâu chiến lược (cùng với vét cạn và duyệt từng lớp), còn «câu đúng trước mỗi vòng» vào khâu mã và ca thử, cũng thuộc cách phân loại này.
Bản hợp đồng: lời hứa nào đi kèm điều kiện nào
Bảng dưới đây là bản hợp đồng rút gọn của các kĩ thuật xuất hiện trong bài giảng. Cột giữa là điều nó hứa; cột phải là điều kiện để lời hứa có hiệu lực. Mỗi hàng sẽ được mở ra ở mục ghi bên phải.
Kĩ thuật
Lời hứa
Điều kiện đi kèm
Mục
Truy cập mảng theo số thứ tự
đọc phần tử thứ k chỉ trong một bước
các phần tử nằm liền nhau, cùng kích thước
Danh sách liên kết
thêm một phần tử vào đầu danh sách trong một bước
có con trỏ giữ nút đầu
Bảng băm
tra cứu theo khóa mất trung bình rất ít bước
khóa rải khá đều vào các ô và số ô đủ nhiều
Duyệt từng lớp bằng hàng đợi
cho số cạnh ít nhất từ đỉnh xuất phát
đồ thị không trọng số, mỗi đỉnh đánh dấu khi đã thăm
Vòng lặp hai vùng
giữ phần đầu mảng đã được phân loại đúng
câu bất biến đúng trước mỗi vòng
Đệ quy
dừng lại và cho kết quả đúng
có trường hợp cơ sở và mỗi lời gọi thu nhỏ bài toán
Ghi nhớ kết quả
mỗi bài toán con chỉ tính một lần
bài toán con lặp lại và kết quả của chúng không đổi
Tìm kiếm nhị phân
mỗi bước loại bỏ một nửa phần còn lại
dãy đã sắp xếp theo thứ tự
Vét cạn
không bỏ sót phương án nào
số phương án đủ nhỏ để duyệt hết
Kiến thức bổ sung: bài giảng dùng các tên gọi duyệt từng lớp trên đồ thị, danh sách liên kết, bảng băm, câu bất biến của vòng lặp, ghi nhớ kết quả bài toán con và xử lí dữ liệu theo luồng ở mức giới thiệu khái niệm. Các phần ấy được đánh dấu «kiến thức bổ sung» ở chỗ xuất hiện đầu tiên của mỗi mục.
Từ điển một dòng: đưa chuột hoặc chạm vào chữ gạch chân
Thuật ngữ
Nghĩa ngắn
Mục
bài toán
Dữ liệu vào, kết quả ra và giới hạn kích thước
cấu trúc dữ liệu
Cách đặt dữ liệu trong bộ nhớ, như mảng hay danh sách liên kết
danh sách liên kết
Các nút nối nhau bằng con trỏ, chỉ biết nút đầu
bảng băm
Hàm băm đổi khóa thành số hiệu ô chứa
đồ thị
Các đỉnh và các cạnh nối chúng
hàng đợi
Vào ở cuối, ra ở đầu
bất biến vòng lặp
Câu đúng trước mỗi vòng, giữ cho vòng lặp đúng
đệ quy
Hàm tự gọi chính nó với đầu vào nhỏ hơn
trường hợp cơ sở
Trường hợp nhỏ nhất, trả lời ngay
độ phức tạp thời gian
Số bước theo kích thước dữ liệu n
độ phức tạp không gian
Lượng bộ nhớ theo kích thước dữ liệu n
Đoán trước, rồi thử tay
Đoán trước: một nhóm bạn nhận bài: cho điểm kiểm tra của lớp, tìm điểm cao nhất. Trước khi nghĩ cách làm, nhóm ghi ra giấy ba dòng: «vào: dãy 40 số từ 0 đến 10; ra: một số là giá trị lớn nhất; giới hạn: tối đa 40 số». Theo việc chính mà ba dòng ấy làm, đây là khâu nào của khung? Hãy chọn trước, rồi mở phòng lab.
Việc ghi ra dữ liệu vào, kết quả ra và giới hạn thuộc khâu nào?
Cách dùng phòng lab
Xếp từng thẻ bằng cách chạm thẻ rồi chạm ô, hoặc cầm vào phần chấm ở mép trái thẻ và kéo thả vào ô. Sau khi bấm «Chấm các thẻ đã xếp», thẻ đúng viền xanh và thẻ sai viền đỏ; dòng kết luận giải thích ba thẻ sai đầu tiên. Phòng lab này luyện bẫy 1.
Thử tay: gọi tên khâu cho từng việc khi xếp lịch trực nhật cho một lớp
Một lớp có 36 bạn cần xếp lịch trực nhật theo tuần. Bạn lớp trưởng ghi lại: mỗi bạn trực đúng một lần, mỗi tuần trực 4 bạn, hai bạn không được trực cùng nhau nếu từng cãi nhau. Bạn đặt tên các bạn vào một bảng đánh số, thử xếp một phương án, kiểm tra xem có tuần nào vi phạm không, rồi đếm xem cách thử từng phương án một có kịp hay không. Hãy gọi tên khâu cho từng việc.
Gợi ý 1 · Hai việc đầu
Ghi «mỗi bạn trực đúng một lần, mỗi tuần 4 bạn, có cặp không được trực chung» là đọc ra dữ liệu vào, kết quả ra và ràng buộc: khâu YÊU CẦU. Đặt tên các bạn vào bảng đánh số là chọn cách đặt dữ liệu: khâu DỮ LIỆU.
Gợi ý 2 · Hai việc sau
Thử một phương án rồi kiểm tra từng tuần có vi phạm không là chạy một ca thử trên bản nháp lịch: khâu MÃ VÀ CA THỬ. Đếm xem thử hết các phương án có kịp không là ước lượng số bước: khâu PHÉP ĐO.
Đáp án · cả chuỗi
YÊU CẦU, DỮ LIỆU, rồi CHIẾN LƯỢC (ở đây là thử và kiểm tra từng phương án), MÃ VÀ CA THỬ, PHÉP ĐO; nếu phép đo cho thấy không kịp thì quay lại khâu CHIẾN LƯỢC. Lớp nền nhắc em ghi điều kiện: cách thử này chỉ dùng được khi số phương án đủ nhỏ, và mục 2 sẽ cho thấy con số ấy lớn đến mức nào.
Chỗ dễ nhầm ở bản đồ chung
Bẫy 1: đọc xong bài toán là gõ mã ngay, còn ca thử và ước lượng chi phí để cuối cùng nếu còn thời gian. Hãy hỏi: nếu có một sai sót ở khâu yêu cầu, sửa nó sau khi đã viết xong mã tốn bao nhiêu công? Sai ở khâu đầu lan xuống cả bốn khâu sau, nên khung đặt việc ghi rõ yêu cầu và điều kiện lên trước. Phòng lab 1 ở trên luyện việc gọi tên khâu.
Mục 2 đi vào khâu đầu tiên: đọc yêu cầu thành bảng vào, ra, giới hạn, và xem vì sao giới hạn của n đã quyết định cách làm nào còn dùng được.
02
Khâu ① YÊU CẦU · đo sớm bằng phép đo
Đọc bài toán thành ba mục, rồi xem giới hạn của n đóng cửa những cách nào
Hai bài toán có thể kể cùng một câu chuyện mà đòi hỏi hai cách làm rất khác nhau, chỉ vì con số n ở một bài là 8 còn ở bài kia là một triệu. Vì vậy việc đầu tiên khi nhận bài toán không phải là nghĩ ra thuật toán, mà là viết lại nó thành ba mục: dữ liệu vào , kết quả ra và giới hạn . Mục giới hạn là mục dễ bị bỏ quên nhất, nhưng chính nó nói cho ta biết trong năm khâu, cách nào còn dùng được và cách nào đã bị đóng cửa. Mục này chỉ ra điều đó bằng một thí nghiệm: đếm xem cách thử từng phương án một sẽ phải thử bao nhiêu phương án.
Từ câu chuyện đến mô hình
Câu chuyện có nhiều chi tiết, còn mô hình chỉ giữ những chi tiết cần cho phép tính. Nhìn bài toán là «ai với ai, cái gì nối cái gì» thì dữ liệu cần giữ là các thực thể và quan hệ giữa chúng; nhìn là «thứ tự» thì cần giữ vị trí; nhìn là «tra theo tên» thì cần giữ cặp khóa và giá trị. Chọn mô hình đúng là một nửa lời giải.
Vuốt ngang để xem đầy đủ hình.
Bốn câu chuyện và mô hình giữ lại từ mỗi câu chuyện. Phần bên phải là cấu trúc em sẽ gặp ở các mục sau: đồ thị ở mục 4, mảng và bảng băm ở mục 3, hàng đợi ở mục 4.
Câu chuyện
Chi tiết cần giữ
Mô hình
Mục
Tìm lối đi qua ít cửa nhất giữa hai phòng
các phòng và cửa nối từng cặp phòng
đồ thị
Điểm của cả lớp xếp theo số thứ tự
giá trị và vị trí của giá trị trong dãy
mảng
Các bạn xếp hàng chờ đến lượt vào phòng y tế
thứ tự đến, người đến trước được phục vụ trước
hàng đợi
Tra số điện thoại của một bạn theo tên
cặp tên và số, tên không có thứ tự sẵn
bảng băm
Ba mục vào, ra, giới hạn
Lấy một bài toán nhỏ làm mẫu: «có n thùng hàng, mỗi thùng có một khối lượng; cho biết thùng nặng nhất». Viết lại thành ba mục:
- Vào: số nguyên n và dãy n số, mỗi số là khối lượng một thùng.
- Ra: khối lượng lớn nhất, hoặc số thứ tự của thùng nặng nhất. Phải hỏi lại yêu cầu: nếu hai thùng cùng nặng nhất thì trả về thùng nào? Câu hỏi này thuộc lớp nền hợp đồng, vì nó là điều kiện của kết quả.
- Giới hạn: n lớn nhất là bao nhiêu, có thể n=1 hay n=0 không, các khối lượng có thể âm hoặc bằng không không. Mục giới hạn trả lời trước những câu mà ca thử ở mục 5 sẽ hỏi.
Sau khi có ba mục, hai quyết định sẽ dễ hơn: chọn cách đặt dữ liệu và chọn cách giải. Ví dụ, nếu n nhỏ như 30 và chỉ cần chạy một lần thì cách đơn giản nhất thường đủ. Nếu n lớn hoặc thao tác lặp lại nhiều lần thì phải cân nhắc kĩ hơn.
Vét cạn và con số khiến nó bị đóng cửa
Vét cạn (duyệt hết các phương án) là chiến lược ngây thơ nhất: liệt kê từng phương án, kiểm tra từng cái, giữ cái tốt nhất. Hợp đồng của nó rất rõ: nó không bỏ sót phương án nào, với điều kiện số phương án đủ nhỏ để duyệt hết . Điều kiện ấy phụ thuộc vào dạng phương án.
- Xếp thứ tự n phần tử khác nhau. Phần tử đầu có n cách chọn, phần tử thứ hai còn n-1 cách, và cứ thế, nên số phương án là n!=n\cdot(n-1)\cdots 2\cdot 1 (hoán vị).
- Chọn tập con của n phần tử. Mỗi phần tử hoặc có mặt hoặc vắng mặt, hai khả năng độc lập nhau, nên có 2\cdot 2\cdots 2=2^{n} tập con.
- Ghép cặp hai phần tử trong n phần tử. Số cặp là \dfrac{n(n-1)}{2}.
Vuốt ngang để xem đầy đủ hình.
Cây phương án khi xếp thứ tự 3 nhiệm vụ: 3 cách chọn nhiệm vụ đầu, 2 cách chọn nhiệm vụ thứ hai, 1 cách chọn nhiệm vụ cuối, tổng cộng 3\cdot 2\cdot 1=6 lá. Thêm một nhiệm vụ thì mỗi lá mọc ra thêm các nhánh mới, nên số lá được nhân lên chứ không chỉ cộng thêm.
Xếp thứ tự n!
Tập con 2^{n}
Cặp \frac{n(n-1)}{2}
120
32
10
3 628 800
1 024
45
15
1 307 674 368 000
32 768
105
20
2 432 902 008 176 640 000
1 048 576
190
Hãy nhìn cách ba cột lớn lên. Cột cặp tăng gần bốn lần mỗi khi n tăng gấp đôi (45 lên 190 khi n từ 10 lên 20), vì nó có dạng gần n^{2}/2. Cột tập con nhân đôi sau mỗi lần n tăng thêm một. Cột xếp thứ tự nhân với n+1 sau mỗi bước, và hệ số nhân ấy cũng tăng theo n: càng về sau càng bùng nổ. Đây là lí do vì sao em không thể nhìn vài giá trị đầu mà đoán thời gian của n lớn.