Bỏ qua tới nội dung chính

Hướng dẫn học chủ đề

Cấu trúc dữ liệu và giải thuật

Trung bìnhkhoảng 60 giờ6 bước

Mảng, danh sách liên kết, ngăn xếp, hàng đợi, cây, bảng băm, đồ thị, sắp xếp và phân tích độ phức tạp — kèm góc nhìn kỹ thuật máy tính: bố trí dữ liệu trong bộ nhớ, bộ nhớ đệm và giới hạn tài nguyên của hệ nhúng.

Bắt đầu học

Bạn sẽ học được gì

  • Phân tích độ phức tạp thời gian và bộ nhớ của thuật toán bằng ký hiệu tiệm cận, kể cả phân tích khấu hao
  • Cài đặt bằng C mảng động, danh sách liên kết, ngăn xếp, hàng đợi, bộ đệm vòng, bảng băm, cây tìm kiếm và heap
  • Cài đặt và so sánh các thuật toán sắp xếp dựa trên so sánh và sắp xếp cơ số
  • Biểu diễn đồ thị và cài đặt BFS, DFS, Dijkstra và thuật toán cây khung nhỏ nhất
  • Đo thời gian chạy và số lần trượt cache, giải thích chênh lệch giữa lý thuyết O lớn và kết quả đo trên máy thật
  • Chọn cấu trúc dữ liệu phù hợp với giới hạn bộ nhớ và yêu cầu thời gian thực của hệ nhúng

Nên học trước

Giới thiệu

Cấu trúc dữ liệu và giải thuật là môn nền của mọi ngành máy tính: mảng, danh sách liên kết, ngăn xếp, hàng đợi, bảng băm, cây, heap, đồ thị, sắp xếp và phân tích độ phức tạp. Lộ trình Khoa học máy tính có chủ đề Data Structures and Algorithms đi sâu vào lý thuyết và chứng minh; ở lộ trình Kỹ thuật máy tính, bạn học cùng nội dung cốt lõi nhưng với một câu hỏi thường trực: cấu trúc này nằm trong bộ nhớ thế nào, và phần cứng thật đối xử với nó ra sao?

Vì sao kỹ sư máy tính cần góc nhìn riêng

Phân tích tiệm cận (ký hiệu O lớn) cho biết thuật toán tăng trưởng thế nào khi dữ liệu lớn lên, nhưng bỏ qua hằng số. Trên máy thật, hằng số đó phụ thuộc rất nhiều vào bộ nhớ đệm (cache): đọc một phần tử nằm sẵn trong cache L1 mất vài chu kỳ, còn phải lấy từ DRAM có thể mất hàng trăm chu kỳ. Vì vậy:

  • Duyệt một mảng liền nhau thường nhanh hơn nhiều lần so với duyệt danh sách liên kết cùng độ dài, dù cả hai đều là O(n), vì mảng tận dụng tính cục bộ không gian và bộ nạp trước của CPU.
  • Bảng băm địa chỉ mở dò tuyến tính thường nhanh hơn bảng băm nối chuỗi trên CPU hiện đại, cũng vì tính cục bộ.
  • Heap nhị phân lưu trong mảng không cần con trỏ, gọn và nhanh — lý do nó có mặt trong bộ lập lịch của hệ điều hành và hàng đợi hẹn giờ của firmware.

Trong hệ nhúng, còn thêm giới hạn: vài chục KB RAM, thường không dùng cấp phát động, cần thời gian thực thi có cận trên xác định. Một cấu trúc có trường hợp xấu nhất tệ (như bảng băm khi xung đột nhiều) có thể không chấp nhận được dù trung bình rất nhanh.

Nội dung chính

  • Phân tích độ phức tạp: O, Ω, Θ; phân tích trường hợp xấu nhất, trung bình và khấu hao (mảng động nhân đôi dung lượng).
  • Danh sách: mảng động, danh sách liên kết đơn và kép, ngăn xếp, hàng đợi, hàng đợi hai đầu, bộ đệm vòng.
  • Bảng băm: hàm băm, nối chuỗi, địa chỉ mở, hệ số tải.
  • Cây: cây nhị phân tìm kiếm, cây cân bằng (đỏ – đen, AVL), heap và hàng đợi ưu tiên; cây B cho bộ nhớ ngoài và bộ nhớ flash.
  • Sắp xếp: sắp xếp chèn, trộn, nhanh, heap; sắp xếp đếm và cơ số với số nguyên.
  • Đồ thị: biểu diễn bằng danh sách kề và ma trận kề, BFS, DFS, đường đi ngắn nhất, cây khung nhỏ nhất.

Cách học

Sách chính là Open Data Structures của Pat Morin, sách mở với mã nguồn cho từng cấu trúc và phân tích chặt chẽ nhưng dễ đọc. Với mỗi cấu trúc, hãy tự cài đặt bằng C trước khi dùng thư viện, viết kiểm thử, rồi đo: thời gian chạy với dữ liệu 10 nghìn, 1 triệu, 10 triệu phần tử; lượng bộ nhớ dùng; số lần trượt cache bằng valgrind (công cụ cachegrind) hoặc perf trên Linux. Vẽ đồ thị kết quả bằng Python và giải thích chỗ lệch khỏi lý thuyết. Khóa Cấu trúc dữ liệu & Giải thuật (UC Berkeley) trên trang có bài đọc tiếng Việt và bài tập cho từng cấu trúc; video MIT 6.006 giảng rõ phần phân tích.

Khi cần chứng minh sâu hơn hoặc thuật toán nâng cao (luồng cực đại, NP-khó), đọc Algorithms của Jeff Erickson (miễn phí) hoặc Introduction to Algorithms của Cormen và cộng sự.

Chuẩn bị

Cần lập trình C vững (con trỏ, struct, malloc) và toán rời rạc: quy nạp, tổng, đồ thị cơ bản. Nếu chứng minh quy nạp còn yếu, học song song chủ đề Toán rời rạc của lộ trình Toán học.

Giáo trình & sách tham khảo

Xem tất cả trong tab Sách

Giáo trình chính

Open Data Structures

Pat Morin · 2013

CC BY 2.5 CanadaCơ bảnTiếng Anh344 trang

Vì sao chọn: Sách mở (CC BY 2.5 Canada) của Pat Morin, đọc miễn phí trên opendatastructures.org với mã nguồn Java, C++ và mã giả. Mỗi cấu trúc có phân tích đầy đủ nhưng ngắn gọn, rất hợp để tự cài đặt lại bằng C. Chương 4 (skiplist), 7–8 (cây tìm kiếm ngẫu nhiên, scapegoat) là phần đọc thêm.

Nên đọc: Chương 1–3, 5–6, 9–13; đọc lướt Chương 14

Algorithms

Jeff Erickson · 2019

CC BYTrung bìnhTiếng Anh472 trang

Sách mở (CC BY 4.0) của Jeff Erickson (Đại học Illinois), miễn phí trọn bộ. Giải thích thuật toán đồ thị và đệ quy rất sâu; dùng khi cần chứng minh chặt chẽ hoặc muốn học tiếp luồng cực đại và NP-khó.

Nên đọc: Chương 1 Recursion; Chương 5 Basic Graph Algorithms; Chương 7 Minimum Spanning Trees; Chương 8 Shortest Paths

Introduction to Algorithms

Thomas H. Cormen, Charles E. Leiserson và 2 tác giả khác · 2022 · Bản thứ 4

Có phíTrung bìnhTiếng Anh1.332 trang

Sách tham khảo chuẩn mực (MIT Press, bản thứ 4, trả phí), thường được gọi là CLRS. Dùng để tra cứu định nghĩa, chứng minh và thuật toán khi hai sách mở chưa đủ; không cần đọc tuần tự.

Các bước học

Đăng nhập để đánh dấu các bước đã hoàn thành.

  1. Bước 1: Phân tích độ phức tạp và mảng động

    khoảng 8 giờ

    Học mô hình tính toán, ký hiệu tiệm cận, phân tích khấu hao và danh sách dựa trên mảng. Thực hành: cài đặt mảng động bằng C với hệ số tăng 2 và 1,5; đo tổng thời gian thêm 10 triệu phần tử và số lần gọi realloc với mỗi hệ số; chứng minh bằng tổng cấp số nhân rằng chi phí khấu hao mỗi lần thêm là O(1).

  2. Bước 2: Danh sách liên kết, ngăn xếp, hàng đợi và cache

    khoảng 10 giờ

    Học danh sách liên kết đơn, kép, ngăn xếp, hàng đợi, hàng đợi hai đầu. Thực hành: cài đặt danh sách liên kết kép và hàng đợi bằng bộ đệm vòng; đo thời gian cộng dồn 10 triệu số nguyên khi lưu trong mảng và trong danh sách liên kết (các nút cấp phát rời rạc), rồi chạy valgrind --tool=cachegrind để đếm số lần trượt cache và giải thích chênh lệch dù cả hai đều O(n).

  3. Bước 3: Bảng băm

    khoảng 10 giờ

    Học hàm băm, băm nối chuỗi, địa chỉ mở dò tuyến tính, hệ số tải và phân tích kỳ vọng. Thực hành: cài đặt hai bảng băm cho khóa 32 bit — nối chuỗi và dò tuyến tính trên mảng tĩnh không cấp phát động (kiểu dùng trong firmware); đo thời gian tra cứu và độ dài dò trung bình khi hệ số tải là 0,5, 0,75 và 0,9; thử một hàm băm kém để thấy trường hợp xấu nhất.

  4. Bước 4: Cây tìm kiếm, heap và hàng đợi ưu tiên

    khoảng 10 giờ

    Học cây nhị phân, cây nhị phân tìm kiếm, cây đỏ – đen và heap. Thực hành: cài đặt heap min trong mảng và dùng nó làm hàng đợi hẹn giờ — mỗi phần tử là (thời điểm hết hạn, mã tác vụ), vòng lặp chính lấy ra tác vụ đến hạn; so sánh với danh sách liên kết được sắp xếp khi có 10 nghìn bộ hẹn giờ. Đọc lướt cây B trong chương bộ nhớ ngoài để thấy vì sao hệ thống tệp trên flash dùng cây nhiều nhánh.

    • Đọc: Chương 6 Binary Trees; Chương 9 Red-Black Trees; Chương 10 Heaps; đọc lướt Chương 14 External Memory Searching — Open Data Structures
  5. Bước 5: Sắp xếp và cấu trúc cho số nguyên

    khoảng 10 giờ

    Học sắp xếp trộn, nhanh, heap, cận dưới cho sắp xếp so sánh, sắp xếp đếm và cơ số; đệ quy và chia để trị. Thực hành: cài đặt sắp xếp nhanh, trộn và cơ số (4 lượt 8 bit) cho 10 triệu số uint32; so sánh với qsort của thư viện chuẩn; giải thích vì sao sắp xếp cơ số có thể nhanh hơn dù "khác lớp" độ phức tạp, và khi nào nó thua: khi dùng nhóm 16 bit (bảng đếm 65 536 phần tử) hoặc khi ghi phân tán tới quá nhiều vị trí làm trượt cache và TLB.

  6. Bước 6: Đồ thị và dự án tìm đường

    khoảng 12 giờ

    Học biểu diễn đồ thị, BFS, DFS, đường đi ngắn nhất và cây khung nhỏ nhất. Dự án: mô hình một bản đồ lưới 1000 × 1000 ô có vật cản cho robot; cài đặt BFS và Dijkstra với heap trên biểu diễn danh sách kề nén (CSR); đo thời gian và bộ nhớ, rồi thử giới hạn bộ nhớ 64 KB như trên vi điều khiển và cho biết cần thay đổi gì (lưới nhỏ hơn, bit map thay cho mảng khoảng cách đầy đủ).

    • Đọc: Chương 12 Graphs — Open Data Structures
    • Đọc: Chương 5 Basic Graph Algorithms; Chương 7 Minimum Spanning Trees; Chương 8 Shortest Paths — Algorithms

Khái niệm chính

Ký hiệu tiệm cận
O, Ω, Θ mô tả tốc độ tăng của thời gian hoặc bộ nhớ theo kích thước dữ liệu n, bỏ qua hằng số và số hạng bậc thấp; f = O(g) nghĩa là f không tăng nhanh hơn g sai khác một hằng số.
Phân tích khấu hao
Tính chi phí trung bình của mỗi thao tác trên một dãy thao tác xấu nhất; ví dụ mảng động nhân đôi dung lượng có chi phí thêm phần tử khấu hao O(1) dù một lần sao chép tốn O(n).
Tính cục bộ và bộ nhớ đệm
Chương trình truy cập lại dữ liệu vừa dùng (cục bộ thời gian) hoặc dữ liệu nằm cạnh nhau (cục bộ không gian) thì dùng cache hiệu quả; cấu trúc liền mạch trong bộ nhớ thường nhanh hơn cấu trúc dùng nhiều con trỏ.
Danh sách liên kết
Dãy nút mỗi nút chứa dữ liệu và con trỏ tới nút kế; chèn, xóa tại vị trí đã biết là O(1) nhưng truy cập theo chỉ số là O(n) và kém thân thiện với cache.
Bộ đệm vòng
Hàng đợi cài trên mảng kích thước cố định với chỉ số đầu và cuối quay vòng; không cấp phát động nên rất phổ biến trong trình điều khiển và firmware.
Bảng băm
Cấu trúc ánh xạ khóa tới vị trí qua hàm băm, cho tìm kiếm trung bình O(1); xung đột được xử lý bằng nối chuỗi hoặc địa chỉ mở, hiệu năng phụ thuộc hệ số tải.
Cây nhị phân tìm kiếm cân bằng
Cây mà khóa ở cây con trái nhỏ hơn, cây con phải lớn hơn nút gốc, và chiều cao luôn O(log n) nhờ các phép quay (cây đỏ – đen, AVL).
Heap nhị phân
Cây nhị phân gần đầy lưu trong mảng, nút cha luôn không lớn hơn các con (heap min); thêm và lấy phần tử nhỏ nhất đều O(log n), dùng cho hàng đợi ưu tiên.
Sắp xếp dựa trên so sánh
Mọi thuật toán sắp xếp chỉ dùng phép so sánh cần Ω(n log n) phép so sánh trong trường hợp xấu nhất; sắp xếp trộn và heap đạt cận này.
Sắp xếp cơ số
Sắp xếp số nguyên theo từng nhóm chữ số bằng sắp xếp đếm ổn định; chạy O(k·(n + b)) với k số lượt và b số giá trị mỗi nhóm, không bị cận Ω(n log n) ràng buộc.
Biểu diễn đồ thị
Danh sách kề tiết kiệm bộ nhớ với đồ thị thưa, ma trận kề cho kiểm tra cạnh O(1) với đồ thị dày; dạng nén CSR gom danh sách kề vào hai mảng liền nhau.
Thuật toán Dijkstra
Tìm đường đi ngắn nhất từ một đỉnh trên đồ thị có trọng số không âm bằng cách lần lượt chốt đỉnh gần nhất, dùng hàng đợi ưu tiên; O((V + E) log V) với heap nhị phân.

Học xong để làm gì

  • Hàng đợi dữ liệu giữa trình phục vụ ngắt và chương trình chính trong firmware
  • Bộ lập lịch tác vụ và hàng đợi hẹn giờ trong hệ điều hành và RTOS
  • Bảng định tuyến, bảng tra cứu trong thiết bị mạng và bộ nhớ đệm phần mềm
  • Hệ thống tệp và cơ sở dữ liệu trên bộ nhớ flash dùng cây B
  • Tìm đường cho robot và định tuyến trong mạng trên chip
  • Tối ưu hiệu năng phần mềm dựa trên hiểu biết về cache và bố trí bộ nhớ

Câu hỏi thường gặp

Chủ đề này khác gì chủ đề Data Structures and Algorithms trong lộ trình Khoa học máy tính?

Nội dung cốt lõi giống nhau và dùng chung môn học trên trang. Khác biệt là ở cách làm bài: ở đây bạn cài đặt bằng C, đo trên máy thật, chú ý bố trí bộ nhớ, cache và giới hạn của hệ nhúng. Muốn đi sâu về chứng minh và thuật toán nâng cao, xem thêm chủ đề Data Structures and Algorithms của lộ trình Khoa học máy tính.

Có nên dùng thư viện có sẵn thay vì tự cài đặt?

Trong dự án thật thì nên dùng thư viện đã được kiểm chứng. Nhưng khi học, tự cài đặt ít nhất một lần giúp bạn hiểu chi phí thật của mỗi thao tác — điều không thể thấy khi chỉ gọi hàm thư viện.

Sách chính có miễn phí không?

Có. Open Data Structures của Pat Morin là sách mở (CC BY 2.5 Canada), có bản HTML và PDF miễn phí với mã Java, C++ và mã giả. Algorithms của Jeff Erickson cũng miễn phí (CC BY 4.0). Introduction to Algorithms của Cormen và cộng sự là sách trả phí, dùng để tra cứu.

Làm sao đo số lần trượt cache?

Trên Linux, chạy valgrind --tool=cachegrind để mô phỏng cache và đếm số lần trượt theo từng dòng mã, hoặc dùng perf stat với các sự kiện cache-misses để đọc bộ đếm hiệu năng thật của CPU. Chủ đề Lập trình hệ thống với C giải thích chi tiết phân cấp bộ nhớ.

Mất bao lâu?

Khoảng 60 giờ cho lượt học đầu, tức 10 tuần với 6 giờ mỗi tuần, phần lớn là cài đặt và đo. Đây là thời lượng tối thiểu; một học phần tương đương ở đại học thường cần 120–150 giờ.

Chọn nguồn tự học

Tự cài đặt từng cấu trúc bằng C trước khi dùng thư viện có sẵn; với mỗi cấu trúc, đo thời gian chạy và lượng bộ nhớ trên dữ liệu thật để thấy lý thuyết độ phức tạp gặp phần cứng ra sao.