Tổng quan về giáo trình

Giáo trình Cấu trúc dữ liệu & Giải thuật (Mã học phần: CSC106200) do tác giả Nguyễn Thị Vân chủ biên, được Khoa Công nghệ Thông tin – Trường Cao đẳng Công nghệ Thủ Đức biên soạn và ban hành vào năm 2018. Trong chương trình đào tạo chuyên ngành Công nghệ thông tin cũng như ngành Truyền thông & Mạng máy tính, đây là học phần bắt buộc thuộc khối kiến thức cơ sở chuyên ngành, đóng vai trò bản lề giúp người học chuyển tiếp từ kỹ năng lập trình căn bản sang kỹ năng thiết kế, tổ chức dữ liệu và tối ưu hóa giải thuật giải quyết các bài toán trên máy tính.

Về mục tiêu học tập (learning outcomes), giáo trình hướng đến việc trang bị cho sinh viên năng lực phân loại và phân biệt các cấu trúc dữ liệu cơ bản (tuyến tính và phi tuyến tính); nắm vững nguyên lý hoạt động của cấu trúc cây và các phép duyệt cây; đồng thời có khả năng phân tích, ước lượng thời gian thực thi của thuật toán thông qua ký hiệu toán học Big-O. Về mặt thực hành, sinh viên được yêu cầu tự cài đặt thành thạo các cấu trúc dữ liệu như danh sách đặc (mảng), danh sách liên kết đơn, ngăn xếp (stack), hàng đợi (queue), cùng các giải thuật tìm kiếm và sắp xếp dữ liệu trên ngôn ngữ lập trình C/C++. Ngoài ra, học phần xác lập chuẩn đầu ra về năng lực tự chủ và trách nhiệm nghề nghiệp: rèn luyện quy chuẩn viết mã nguồn sạch (code convention), tinh thần tự học và ý thức kỷ luật hoàn thành bài tập đúng hạn.

Cấu trúc giáo trình được thiết kế theo hướng tiếp cận logic hình thức: khởi đầu từ việc phân biệt giữa kiểu dữ liệu cơ sở và kiểu dữ liệu trừu tượng (Abstract Data Types - ADTs), tiếp nối bằng các công cụ toán học dùng để phân tích độ phức tạp thuật toán, sau đó lần lượt triển khai chi tiết các giải thuật và cấu trúc dữ liệu từ cơ bản đến phức tạp. Điểm đặc thù của tài liệu là việc bám sát khung chuẩn đào tạo CDIO (Conceive - Design - Implement - Operate), kết hợp song song giữa chứng minh toán học, biểu đồ mô phỏng trạng thái từng bước chạy của thuật toán và các đoạn mã nguồn C/C++ cụ thể.

Nội dung kiến thức cốt lõi

Các chương/chủ đề chính

Giáo trình được cấu trúc thành hệ thống các chương học phần với lộ trình phát triển kiến thức tuần tự:

  1. Chương 1: Biến, Kiểu dữ liệu, Cấu trúc dữ liệu, Kiểu dữ liệu trừu tượng (ADTs) và Phân tích giải thuật: Trình bày định nghĩa biến, kích thước bộ nhớ của các kiểu dữ liệu cơ sở (int, float, char, wchar_t theo UTF-16), kiểu cấu trúc tự định nghĩa (struct), phân loại cấu trúc dữ liệu tuyến tính và phi tuyến tính; định nghĩa ADT kết hợp trừu tượng hóa dữ liệu (data abstraction) và trừu tượng hóa chức năng (function abstraction). Chương này xác lập nền tảng lý thuyết phân tích giải thuật: khái niệm kích thước dữ liệu vào $n$, phép toán tích cực, thời gian chạy trong trường hợp tốt nhất $T(n)$, xấu nhất $T(n)$, trung bình $T_{n}(n)$, và định nghĩa toán học của ký hiệu Big-O ($f(n) \le C_1 \cdot g(n)$ với mọi $n \ge N_1$).
  2. Chương 2: Một số giải thuật tìm kiếm: Phân tích bài toán tìm kiếm trên bảng khóa với hai phương pháp chính: Tìm kiếm tuần tự (Linear Search) có độ phức tạp $O(n)$ trên mảng chưa sắp xếp và mảng có thứ tự; Tìm kiếm nhị phân (Binary Search) có độ phức tạp $O(\log n)$ trên mảng đã sắp xếp dựa trên kỹ thuật chia đôi không gian tìm kiếm.
  3. Chương 3: Một số thuật toán sắp xếp: Trình bày chi tiết 7 thuật toán sắp xếp:
    • Sắp xếp lựa chọn (Selection Sort): Chọn phần tử nhỏ nhất đưa về đầu dãy, độ phức tạp $O(n^2)$, thực hiện $n^2/2$ phép so sánh và $n$ lần hoán vị.
    • Sắp xếp chèn (Insertion Sort): Chèn phần tử vào vị trí đúng trong đoạn đã sắp xếp, độ phức tạp $O(n^2)$ ở trường hợp xấu nhất và đạt $O(n + d)$ khi dãy đã có thứ tự một phần.
    • Sắp xếp đổi chỗ trực tiếp (Interchange Sort): Triệt tiêu các cặp nghịch thế ($a_i > a_j$ với $i < j$), độ phức tạp $O(n^2)$.
    • Sắp xếp nổi bọt (Bubble Sort): Hoán đổi các phần tử liền kề, cải tiến trường hợp tốt nhất xuống $O(n)$ khi sử dụng biến cờ (flag).
    • Sắp xếp nhanh (Quick Sort): Phân hoạch mảng dựa trên phần tử chốt (mid), độ phức tạp trung bình $O(n \log_2 n)$, xấu nhất $O(n^2)$.
    • Sắp xếp trộn (Merge Sort): Phân tích phương pháp trộn tự nhiên và trộn trực tiếp (Direct Merge), phân phối luân phiên các dãy con vào hai dãy phụ $b, c$ và tiến hành trộn với độ phức tạp ổn định $O(n \log n)$ trong mọi trường hợp.
    • Sắp xếp vun đống (Heap Sort): Xây dựng đống cực đại (max-heap) hoặc đống cực tiểu (min-heap) dựa trên cây nhị phân gần đầy biểu diễn bằng mảng ($a[2i]$ và $a[2i+1]$), tiến hành vun đống và hoán vị phần tử gốc để thu được dãy có thứ tự.
  4. Chương 4: Kiểu dữ liệu danh sách: Khái niệm danh sách, phân loại danh sách đặc (cài đặt bằng mảng) và danh sách liên kết (Linked Lists ADT), kỹ thuật cấp phát bộ nhớ động, cấu trúc nút (node) và các thao tác thêm, xóa, duyệt trên danh sách liên kết đơn.
  5. Chương 5: Ngăn xếp (Stack) và Hàng đợi (Queue): Cơ chế LIFO (Last In First Out) của Stack và FIFO (First In First Out) của Queue; cài đặt bằng mảng và danh sách liên kết; ứng dụng thực tế và cách sử dụng thư viện mẫu chuẩn std::stack, std::queue trong C++ (STL).
  6. Chương 6: Cấu trúc cây (Tree Structures): Khái niệm cây tổng quát, biểu diễn cây nhị phân (Binary Tree), các giải thuật duyệt cây (tiền thứ tự, trung thứ tự, hậu thứ tự), Cây nhị phân tìm kiếm (Binary Search Tree - BST) và Cây nhị phân tìm kiếm cân bằng (AVL Tree) với các kỹ thuật quay cây để tái cân bằng hệ số chiều cao.

Kiến thức nền tảng được xây dựng

Giáo trình cung cấp các nguyên lý và khuôn mẫu lý thuyết cốt lõi trong khoa học máy tính:

  • Nguyên lý trừu tượng hóa dữ liệu: Phân tách hoàn toàn giữa giao diện định nghĩa thao tác (interface) và cơ chế cài đặt nội tại (implementation) của các ADTs.
  • Phân loại tổ chức bộ nhớ: Phân biệt giữa cấu trúc dữ liệu cấp phát tĩnh (danh sách đặc/mảng với kích thước cố định) và cấu trúc dữ liệu cấp phát động (danh sách liên kết với các con trỏ móc nối).
  • Hệ thống phân cấp độ phức tạp: Thang đo chuẩn Big-O phân loại độ tăng hàm thời gian: $$\text{Hằng số } O(1) < \text{Logarit } O(\log_2 n) < \text{Tuyến tính } O(n) < O(n \log_2 n) < \text{Bậc hai } O(n^2) < \text{Bậc ba } O(n^3) < \text{Đa thức } O(n^k) < \text{Mũ } O(a^n) < \text{Giai thừa } O(n!)$$

Kỹ năng phát triển

Thông qua nội dung giảng dạy, người học hình thành các nhóm kỹ năng cụ thể:

  • Kỹ năng phân tích thuật toán: Đọc hiểu và phân tích cấu trúc mã nguồn thông qua các quy tắc đánh giá vòng lặp đơn ($O(n)$), vòng lặp lồng nhau ($O(n^2)$), câu lệnh rẽ nhánh điều kiện ($O(\max(f(n), g(n)))$) và phép lặp bước nhảy nhân/chia đôi ($O(\log n)$).
  • Kỹ năng lập trình cài đặt: Chuyển đổi mã giả (pseudocode) và sơ đồ thuật toán thành mã nguồn C/C++ hoàn chỉnh, thao tác trực tiếp với con trỏ, quản lý bộ nhớ, định nghĩa các bản ghi cấu trúc dữ liệu phức hợp (struct SinhVien { string maSV, hoTen; float dtb; }).
  • Kỹ năng giải quyết bài toán: Lựa chọn giải thuật và cấu trúc lưu trữ phù hợp dựa trên kích thước tập dữ liệu đầu vào và yêu cầu tối ưu tài nguyên tính toán.

Phương pháp giảng dạy và học tập

Giáo trình được định hình theo phương pháp sư phạm tiếp cận kỹ thuật CDIO, chú trọng tính minh bạch của quy trình truyền đạt và khả năng tự kiểm chứng của người học:

  • Tiếp cận diễn dịch kết hợp mô phỏng từng bước (Step-by-step Tracing): Mỗi giải thuật luôn đi kèm với phần định nghĩa bài toán (Input/Output), các bước giải thuật tuần tự, bảng mô phỏng biến thiên dữ liệu theo từng vòng lặp (trace table) trên các dãy số cụ thể (ví dụ: dãy 12, 2, 8, 5, 1, 6, 4, 15), tiếp nối bằng đoạn mã cài đặt chuẩn và phần chứng minh độ phức tạp.
  • Hệ thống bài tập định lượng và bài tập tình huống: Tài liệu tích hợp các dạng bài tập yêu cầu người học:
    1. Tính toán giá trị toán học của hàm thời gian $T(n)$ và quy đổi sang ký hiệu Big-O từ các đoạn chương trình cho trước (như hàm maxElement, uniqueElements, thuật toán tạo ma trận đơn vị cấp $n$).
    2. Cải tiến giải thuật: mở rộng tìm kiếm tuyến tính để ghi nhận mọi vị trí xuất hiện của khóa, viết chương trình in ra số lần chia đôi mảng và các khoảng chỉ số con [left..right] trong thuật toán tìm kiếm nhị phân.
    3. Cài đặt các bài toán quản lý dữ liệu: nhập xuất danh sách sinh viên, tìm kiếm và xóa/sửa thông tin học viên theo khóa nhận dạng (maSV, hoTen).
  • Phương pháp đánh giá kết quả học tập:
    • Đánh giá quá trình: Kiểm tra mức độ hiểu thuật toán thông qua khả năng phân tích độ phức tạp của các đoạn mã bất kỳ và viết code tuân thủ chuẩn cú pháp.
    • Đánh giá thực hành: Đánh giá khả năng tự lập trình, chạy thử nghiệm và gỡ lỗi trên môi trường máy tính; mức độ hoàn thành bài tập về nhà và nộp đúng thời hạn quy định.
    • Đánh giá kỹ năng mềm: Kiểm tra khả năng trình bày, thuyết minh giải thuật và bảo vệ giải pháp kỹ thuật trước lớp học.
  • Hướng dẫn tự học: Sinh viên được yêu cầu phân tích độc lập các bài toán mẫu, tự kiểm tra lại các trường hợp biên (biên rỗng, phần tử ở đầu/cuối danh sách, khóa tìm kiếm không tồn tại) và tự cài đặt lại các cấu trúc dữ liệu nâng cao như Cây AVL hoặc giải thuật Merge Sort trực tiếp.

Điểm nổi bật và cập nhật

Nội dung giáo trình phản ánh các chuẩn mực đào tạo kỹ thuật với các yếu tố cập nhật chuyên môn:

  • Thiết kế theo chuẩn kiểm định CDIO: Nội dung được biên soạn bám sát đề cương chi tiết học phần mới của Khoa Công nghệ Thông tin – Trường Cao đẳng Công nghệ Thủ Đức, tích hợp đầy đủ các tiêu chuẩn về kiến thức kỹ thuật, kỹ năng thực hành và thái độ làm việc chuyên nghiệp.
  • Khảo sát hệ thống toàn diện 7 thuật toán sắp xếp kinh điển: Thay vì chỉ giới thiệu các giải thuật cơ bản, giáo trình phân tích sâu cả các thuật toán có cấu trúc phân chia phức tạp. Trong đó, tài liệu làm rõ sự khác biệt giữa phương pháp Trộn tự nhiên (Natural Merge) và Trộn trực tiếp (Direct Merge), cũng như phân tích bản chất liên đới giữa chỉ số mảng và cấu trúc Cây nhị phân gần đầy trong thuật toán Sắp xếp vun đống (Heap Sort).
  • Tích hợp thư viện chuẩn STL trong C++: Bên cạnh việc hướng dẫn sinh viên tự xây dựng cấu trúc dữ liệu từ mức con trỏ cơ sở để hiểu rõ bản chất quản trị bộ nhớ, giáo trình mở rộng phần giới thiệu các container chuẩn std::stack và std::queue từ thư viện C++ STL, giúp người học làm quen với các công cụ lập trình tiêu chuẩn trong công nghiệp phần mềm.
  • Tính toán tài nguyên chi tiết trên phần cứng: Giáo trình đưa ra các ví dụ cụ thể về kích thước chiếm dụng bộ nhớ của các kiểu dữ liệu (int 2 bytes từ $-2^{15}$ đến $2^{15}-1$ hoặc 4 bytes từ $-2^{31}$ đến $2^{31}-1$; kiểu ký tự char 1 byte mã ASCII và wchar_t 2 bytes mã UTF-16), giúp người học nhận thức rõ mối tương quan giữa kiểu dữ liệu lập trình và kiến trúc hệ thống máy tính.

Đối tượng sử dụng giáo trình

Nhóm đối tượng Yêu cầu / Điều kiện tiên quyết (Prerequisites) Mục đích sử dụng
Sinh viên chuyên ngành Công nghệ thông tin Đã hoàn thành học phần Nhập môn lập trình / Kỹ thuật lập trình (ngôn ngữ C/C++), nắm vững biến, vòng lặp, hàm, con trỏ và mảng. Học tập chính khóa, rèn luyện tư duy thuật toán, cài đặt các cấu trúc dữ liệu cơ sở phục vụ các môn học chuyên ngành tiếp theo.
Sinh viên ngành Truyền thông & Mạng máy tính Kiến thức lập trình căn bản, cấu trúc điều khiển và kiểu dữ liệu cơ bản. Nắm bắt cơ chế tổ chức bộ nhớ đệm (buffer/queue), hàng đợi gói tin và các giải thuật tìm kiếm định tuyến cơ bản.
Giảng viên các trường Cao đẳng/Đại học Chuyên môn khoa học máy tính và kỹ thuật phần mềm. Sử dụng làm khung tài liệu giảng dạy lý thuyết, chuẩn hóa ngân hàng câu hỏi phân tích Big-O và bài tập thực hành trên máy.
Lập trình viên và người tự học Kiến thức cơ sở về cú pháp C/C++. Tài liệu tra cứu hình thức về giải thuật sắp xếp, cấu trúc cây nhị phân, cây AVL và phương pháp đánh giá hiệu năng mã nguồn.

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

1. Giáo trình này được biên soạn phù hợp cho đối tượng người học nào?

Giáo trình được thiết kế chuẩn hóa cho sinh viên hệ Cao đẳng và Đại học thuộc khối ngành Công nghệ thông tin, Truyền thông & Mạng máy tính khi theo học học phần Cấu trúc dữ liệu & Giải thuật (Mã học phần: CSC106200).

2. Người học cần chuẩn bị kiến thức nền tảng nào trước khi tiếp cận tài liệu?

Người học cần có kiến thức vững vàng về lập trình căn bản bằng ngôn ngữ C hoặc C++, bao gồm: cú pháp khai báo biến, các kiểu dữ liệu cơ sở (int, float, char, bool), cấu trúc điều khiển rẽ nhánh (if-else), vòng lặp (for, while), thao tác với mảng một chiều, bản ghi cấu trúc (struct) và khái niệm cơ bản về biến con trỏ.

3. Cấu trúc nội dung của giáo trình có điểm gì khác biệt so với các tài liệu nhập môn lập trình thông thường?

Giáo trình không đi sâu vào cú pháp ngôn ngữ mà tập trung trực tiếp vào tính trừu tượng hóa dữ liệu (ADTs), kỹ thuật phân tích hiệu năng bằng ký hiệu Big-O, và triển khai đầy đủ các cấu trúc dữ liệu từ tuyến tính (mảng, danh sách liên kết, stack, queue) đến phi tuyến tính (cây nhị phân, BST, cây cân bằng AVL), đồng thời cung cấp chi tiết 7 thuật toán sắp xếp và các phương pháp tìm kiếm chuẩn.

4. Phương pháp tự học giáo trình này như thế nào để đạt hiệu quả cao nhất?

Người học nên kết hợp đọc lý thuyết với việc mô phỏng tay (trace) các bước chạy của giải thuật trên dữ liệu mẫu theo bảng hướng dẫn trong giáo trình; sau đó tự viết lại mã nguồn trên trình biên dịch C/C++ mà không nhìn mã mẫu, thực hiện giải các bài tập phân tích độ phức tạp thời gian ở cuối mỗi chương.

5. Tài liệu có cung cấp các ví dụ thực hành và bài tập ứng dụng không?

Có. Giáo trình tích hợp hệ thống mã nguồn mẫu C/C++, các ví dụ quản lý danh sách sinh viên thực tế, bài tập phân tích độ phức tạp của hàm thuật toán (maxElement, uniqueElements), các bài toán xử lý mảng và danh mục tài liệu tham khảo chuyên ngành tại trang 146 của tài liệu.

Kết luận

Giáo trình Cấu trúc dữ liệu & Giải thuật của tác giả Nguyễn Thị Vân là tài liệu học thuật cơ sở chuyên ngành, hệ thống hóa đầy đủ các khái niệm nền tảng về cấu trúc dữ liệu và giải thuật trong khoa học máy tính. Lộ trình học tập đề xuất theo giáo trình bao gồm 3 giai đoạn:

  1. Nắm vững phương pháp luận phân tích giải thuật và toán học Big-O.
  2. Triển khai các cấu trúc dữ liệu tuyến tính (Danh sách đặc, Danh sách liên kết, Ngăn xếp, Hàng đợi) cùng các giải thuật tìm kiếm và sắp xếp ($O(n^2)$ và $O(n \log n)$).
  3. Làm chủ cấu trúc dữ liệu phi tuyến tính (Cây nhị phân, Cây nhị phân tìm kiếm BST và Cây cân bằng AVL).

Người học có thể tham khảo danh mục tài liệu chuyên sâu được công bố tại phần Tài liệu tham khảo (trang 146 của giáo trình) để mở rộng các nghiên cứu lý thuyết và ứng dụng nâng cao trong kỹ thuật phần mềm.