BÀI MÔ TẢ HỌC THUẬT: GIÁO TRÌNH CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (MÃ HỌC PHẦN: MH11)

Tổng quan về giáo trình (250-300 từ)

Giáo trình Cấu trúc dữ liệu (tên môn học trong chương trình: Cấu trúc dữ liệu và giải thuật, mã môn học: MH11) do Thạc sĩ Đào Thị Xuân Hường chủ biên, được Khoa Công nghệ Thông tin – Trường Cao đẳng Bách Khoa Nam Sài Gòn biên soạn và ban hành chính thức theo Quyết định số 459/QĐ-NSG ngày 31 tháng 08 năm 2022 của Hiệu trưởng nhà trường. Tài liệu được thiết kế cho hệ đào tạo Cao đẳng thuộc ngành/nghề Tin học ứng dụng với tổng thời lượng thực hiện là 30 giờ, bao gồm 29 giờ giảng dạy lý thuyết và 01 giờ dành cho công tác kiểm tra đánh giá.

Về vị trí đào tạo, học phần MH11 thuộc khối kiến thức cơ sở ngành bắt buộc. Mục tiêu đào tạo của giáo trình hướng đến việc cung cấp kiến thức nền tảng về tổ chức lưu trữ thông tin và phương pháp luận thiết kế thuật toán xử lý dữ liệu. Sau khi hoàn thành học phần, người học được trang bị khả năng: nhận diện lập trình hướng đối tượng sử dụng các tính năng của ngôn ngữ; trình bày và vận dụng các cấu trúc dữ liệu cơ bản; hiện thực hóa các giải thuật tìm kiếm, sắp xếp trên máy tính; đồng thời rèn luyện tác phong công nghiệp và tính kỷ luật trong lập trình.

Cấu trúc giáo trình bao gồm 4 chương trọng tâm:

  • Chương 1: Tổng quan về cấu trúc dữ liệu và thuật giải trong một đề án tin học
  • Chương 2: Kỹ thuật tìm kiếm
  • Chương 3: Kỹ thuật sắp xếp (Sorting)
  • Chương 4: Danh sách

Cách tiếp cận của giáo trình đi từ mô hình hóa toán học $T = \langle V, O \rangle$, phân tích không gian/thời gian, diễn giải bằng mã giả (pseudo code) đến hiện thực hóa chi tiết bằng mã nguồn ngôn ngữ lập trình C.

Nội dung kiến thức cốt lõi (500-600 từ)

  • CTDL + TG = Program    • Tìm kiếm nội:                   • Sắp xếp nội:           • Danh sách đặc
  • Kiểu dữ liệu T=<V,O>     LinearSearch, Sentinel,           BubbleSort, QuickSort,   (Condensed List)
  • Phân loại bộ nhớ         BinarySearch (đệ quy & lặp)       SelectionSort,         • Danh sách liên kết
  • Độ phức tạp T(n)       • Tìm kiếm ngoại:                   InsertionSort, MergeSort (Singly/Doubly LL)
                             FLinearSearch, IndexSearch      • Sắp xếp ngoại/chỉ mục  • Danh sách hạn chế

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

  • Chương 1: Tổng quan về cấu trúc dữ liệu và thuật giải trong một đề án tin học: Đặt nền tảng phương pháp luận thông qua đẳng thức $Cấu\ trúc\ dữ\ liệu + Giải\ thuật = Chương\ trình$. Trình bày khái niệm kiểu dữ liệu $T = \langle V, O \rangle$ ($V$: miền giá trị, $O$: tập phép toán), phân loại kiểu dữ liệu cơ sở (nguyên 1–4 bytes, thực 4–10 bytes, ký tự 1–2 bytes, chuỗi, luận lý 1 byte), kiểu có cấu trúc (mảng, struct/record), con trỏ (near pointer 2 bytes, far pointer 4 bytes) và kiểu tập tin (file). Thiết lập hệ tiêu chuẩn đánh giá cấu trúc dữ liệu (tiết kiệm bộ nhớ trong, phản ánh đúng thực tế, thuận tiện thao tác) và phương pháp ước lượng độ phức tạp thời gian thuật toán qua ba trường hợp: tốt nhất ($T_{min}$), xấu nhất ($T_{max}$) và trung bình ($T_{avg}$).
  • Chương 2: Kỹ thuật tìm kiếm: Phân tích mô hình dữ liệu tổng quát DataType gồm trường khóa Key và trường thông tin Info. Phân định hai nhóm giải thuật: tìm kiếm nội (trên mảng RAM) và tìm kiếm ngoại (trên tập tin đĩa). Các giải thuật tìm kiếm nội gồm: tìm kiếm tuyến tính (LinearSearch), tìm kiếm tuyến tính có phần tử cầm canh (LinearSearch1), tìm kiếm nhị phân đệ quy (RecBinarySearch/BinarySearch) và không đệ quy (NRecBinarySearch). Về tìm kiếm ngoại, chương cung cấp thuật toán duyệt tuần tự trên file (FLinearSearch) và tìm kiếm qua tập tin chỉ mục (IndexSearch) sử dụng cấu trúc IdxType (IdxKey, Pos).
  • Chương 3: Kỹ thuật sắp xếp (Sorting): Khảo sát các giải thuật sắp xếp nội và ngoại theo thứ tự khóa tăng dần. Nhóm đổi chỗ gồm sắp xếp nổi bọt (BubbleSort kết hợp hàm hoán vị Swap) và sắp xếp phân hoạch nhanh (QuickSort/PartitionSort dựa trên phần tử biên). Nhóm chọn lựa gồm sắp xếp chọn trực tiếp (SelectionSort). Nhóm chèn gồm sắp xếp chèn trực tiếp (InsertionSort) và bản hiệu chỉnh kết hợp dời chỗ lùi (InsertionSort1). Nhóm trộn (MergeSort) làm rõ khái niệm đường chạy (run), chiều dài đường chạy và cơ chế trộn đường chạy. Chương mở rộng sang các kỹ thuật sắp xếp ngoại và sắp xếp theo chỉ mục.
  • Chương 4: Danh sách: Khảo sát các cấu trúc dữ liệu động và tĩnh bao gồm danh sách đặc (Condensed List), danh sách liên kết đơn (Singly Linked List), danh sách liên kết kép (Doubly Linked List), các cấu trúc danh sách hạn chế (ngăn xếp, hàng đợi) cùng phạm vi ứng dụng thực tế của từng mô hình.

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

Giáo trình xây dựng ba trụ cột lý thuyết cốt lõi:

  1. Lý thuyết về kiểu dữ liệu trừu tượng và ánh xạ bộ nhớ: Định nghĩa hình thức kiểu dữ liệu dưới dạng bộ đôi $T = \langle V, O \rangle$, quy định kích thước lưu trữ vật lý của các kiểu dữ liệu sơ cấp và thứ cấp trong bộ nhớ máy tính.
  2. Nguyên lý phân tích và định lượng hiệu năng thuật toán: Phương pháp đếm số phép gán ($G$), số phép so sánh ($S$), số phép hoán vị ($H$) và số lần truy xuất đọc đĩa ($D$) trong ba trạng thái vận hành ($min, max, avg$).
  3. Mô hình truy xuất dữ liệu phân cấp: Phân định ranh giới và phương pháp xử lý giữa bộ nhớ trong (RAM - cấu trúc mảng, con trỏ, tốc độ cao) và bộ nhớ ngoài (Đĩa cứng - cấu trúc tập tin nhị phân, tập tin chỉ mục, giảm thiểu I/O).

Kỹ năng phát triển

  • Kỹ năng kỹ thuật (Technical skills): Cài đặt cấu trúc dữ liệu bằng ngôn ngữ C; quản trị con trỏ; thao tác đọc/ghi luồng tập tin nhị phân (fopen, fread, fclose, rewind, feof); chuyển đổi giải thuật đệ quy sang phi đệ quy.
  • Kỹ năng phân tích (Analytical skills): Đánh giá chi phí thời gian thực thi của thuật toán; so sánh hiệu năng giữa thuật toán nguyên thủy và thuật toán cải tiến (ví dụ: đối chuẩn LinearSearch với LinearSearch1 dùng lính canh; InsertionSort với InsertionSort1).
  • Kỹ năng giải quyết bài toán thực tế (Practical competencies): Xây dựng cấu trúc dữ liệu lưu trữ bảng giờ tàu hỏa Bắc – Nam, mô phỏng hệ thống điều khiển đèn giao thông ngã tư, biểu diễn ma trận trạng thái bàn cờ Caro $M \times N$, và thiết kế hệ thống quản lý hồ sơ nhân sự dạng tập tin kèm bảng chỉ mục.

Phương pháp giảng dạy và học tập (300-350 từ)

Giáo trình áp dụng phương pháp sư phạm diễn dịch kết hợp thực nghiệm quy nạp. Tiến trình giảng dạy mỗi chủ đề được tổ chức theo quy trình 6 bước chuẩn hóa:

  1. Đặt vấn đề và mô hình hóa cấu trúc dữ liệu đầu vào.
  2. Trình bày tư tưởng giải thuật.
  3. Quy định các bước thuật toán (mã giả/bước lặp).
  4. Cài đặt chi tiết hàm bằng mã nguồn ngôn ngữ C chuẩn.
  5. Phân tích định lượng số phép toán ($G, S, H, D$).
  6. Cung cấp bảng theo dõi từng bước (trace table) qua dữ liệu mẫu cụ thể.

Hệ thống bài tập cuối mỗi chương được thiết kế đa dạng từ bài tập lý thuyết phân tích đến các đề án mô phỏng thực tế:

  • Xử lý số học và đại số: Xây dựng cấu trúc dữ liệu biểu diễn đa thức bậc $n$ trên trường số thực $\mathbb{R}$ và trường số hữu tỷ $\mathbb{Q}$, viết chương trình tính giá trị đa thức tại điểm $x_0$, tính tổng và tích hai đa thức.
  • Hệ thống dữ liệu giao thông: Thiết kế cấu trúc lưu trữ bảng giờ tàu chạy từ ga Sài Gòn đi Hà Nội qua 17 ga trung gian (S2, S4, S6, S8, S10, S12, S14, S16, S18, LH2, SN2) trên cả bộ nhớ trong và đĩa từ; xử lý các yêu cầu truy vấn giờ tàu đến ga, phân biệt điểm dừng đỗ đón trả khách và dừng tránh tàu.
  • Mô phỏng hệ thống: Xây dựng cấu trúc dữ liệu và giải thuật mô phỏng chu kỳ chuyển trạng thái của 2 cột đèn giao thông (Xanh, Đỏ, Vàng) tại giao lộ ngã tư.
  • Xử lý trò chơi và ma trận: Biểu diễn trạng thái bàn cờ Caro kích thước $M \times N$ ($0 \le M, N \le 20$) và giải thuật kiểm tra điều kiện thắng/thua.
  • Quản lý dữ liệu tập tin: Tổ chức cơ sở dữ liệu nhân sự trên file NHANSU.DAT (gồm 8 trường: Mã số, Họ đệm, Tên, Ngày tháng năm sinh, Phái, Hệ số lương, Lương căn bản, Phụ cấp) và xây dựng hệ thống tập tin chỉ mục NSTEN.IDX để tối ưu hóa truy vấn tìm kiếm theo tên.

Về kiểm tra đánh giá, học phần dành 01 giờ cho kiểm tra tổng hợp, đòi hỏi sinh viên kết hợp khả năng viết thuật toán trên giấy và lập trình thực thi. Để tự học hiệu quả, người học cần vẽ bảng lần lặp (trace table) cho từng thuật toán với kích thước mảng nhỏ ($N=10$) trước khi thực hiện viết code và kiểm thử bằng hàm sinh số ngẫu nhiên random() cho tập dữ liệu lớn ($N \ge 1.000$).

Điểm nổi bật và cập nhật (250-300 từ)

Tài liệu được xây dựng trên cơ sở tích hợp kinh nghiệm giảng dạy nhiều năm của tập thể giảng viên Khoa Công nghệ Thông tin – Trường Cao đẳng Bách Khoa Nam Sài Gòn, bám sát đề cương chi tiết môn học ban hành năm 2022. Giáo trình thể hiện tính thực tế qua các đặc trưng kỹ thuật:

Đặc trưng phân tích Nội dung kỹ thuật trong giáo trình
Phân tích thuật toán chi tiết Đưa ra công thức giải tích cụ thể cho số phép gán ($G$), số phép so sánh ($S$), số phép hoán vị ($H$), số lần đọc đĩa ($D$) trong các trường hợp $min, max, avg$.
Cải tiến thuật toán trực tiếp - Bổ sung phần tử cầm canh vào cuối mảng (LinearSearch1) để loại bỏ phép kiểm tra biên vòng lặp.
- Cải tiến InsertionSort1 kết hợp tìm vị trí và dời chỗ phần tử, xác định giá trị khởi tạo $K$ dựa trên chuỗi tăng đầu dãy.
Kỹ thuật xử lý tập tin và chỉ mục - Chuyển đổi dữ liệu tập tin vào RAM để giảm tải I/O đĩa cứng.
- Thiết kế cấu trúc chỉ mục IdxType (IdxKey, Pos) cho các bài toán dữ liệu lớn.
Tính ứng dụng thực tế Sử dụng các bài toán thực tiễn: lập lịch tàu hỏa Bắc - Nam, điều khiển đèn tín hiệu giao thông, quản lý hồ sơ nhân sự NHANSU.DAT.

Đối tượng sử dụng giáo trình (200-250 từ)

  • Sinh viên chuyên ngành: Tài liệu phục vụ trực tiếp cho sinh viên trình độ Cao đẳng ngành Tin học ứng dụng và các ngành thuộc khối Công nghệ thông tin tại Trường Cao đẳng Bách Khoa Nam Sài Gòn cũng như các cơ sở đào tạo nghề nghiệp tương đương.
  • Điều kiện tiên quyết (Prerequisites): Người học cần hoàn thành học phần Nhập môn lập trình / Kỹ thuật lập trình cơ bản; nắm vững cú pháp ngôn ngữ lập trình C hoặc Pascal (cấu trúc điều khiển, mảng, hàm, truyền tham chiếu, cấu trúc struct, con trỏ và thao tác tệp tin); hiểu biết cơ bản về mô hình lập trình hướng đối tượng.
  • Giảng viên chuyên ngành: Tài liệu làm khung tham chiếu chuẩn cho việc soạn bài giảng lý thuyết 29 giờ, cung cấp ngân hàng ví dụ mẫu (bảng tra vết thuật toán) và hệ thống đề bài tập lớn/tiểu luận môn học.
  • Người tự học và lập trình viên: Cung cấp tài liệu cô đọng để tra cứu các giải thuật sắp xếp/tìm kiếm kinh điển và phương pháp quản trị tập tin chỉ mục.

Câu hỏi thường gặp (250-300 từ)

1. Giáo trình này phù hợp với ai?

Tài liệu được biên soạn cho sinh viên hệ Cao đẳng ngành Tin học ứng dụng, đồng thời là tài liệu tham khảo cho sinh viên các khối ngành kỹ thuật phần mềm, công nghệ thông tin cần nắm vững cấu trúc dữ liệu và giải thuật cơ bản.

2. Cần kiến thức nền nào trước khi học giáo trình này?

Người học cần có kiến thức nền tảng về toán rời rạc, logic toán và thành thạo kỹ năng lập trình cơ bản trên ngôn ngữ C hoặc Pascal, đặc biệt là kỹ thuật xử lý mảng, con trỏ và kiểu dữ liệu cấu trúc (struct).

3. Điểm khác biệt của giáo trình so với các tài liệu lý thuyết thuần túy?

Giáo trình kết hợp chặt chẽ giữa phân tích giải tích độ phức tạp (công thức $G, S, H, D$) với mã nguồn C hoàn chỉnh, đồng thời tích hợp mảng kiến thức về giải thuật ngoại (xử lý trên tập tin đĩa và lập chỉ mục IndexSearch), không chỉ giới hạn ở các cấu trúc dữ liệu nội trong bộ nhớ RAM.

4. Làm sao để tự học hiệu quả với giáo trình này?

Người học nên tự chạy tay từng bước (dry-run/trace) trên các bảng dữ liệu mẫu $N=10$ được cung cấp trong giáo trình, sau đó tự cài đặt lại hàm C mà không nhìn code mẫu, cuối cùng thực hiện kiểm thử đo thời gian chạy thực tế trên tập dữ liệu $N \ge 1.000$ phần tử sinh bằng hàm random().

5. Có tài liệu và mã nguồn bổ trợ nào kèm theo?

Giáo trình cung cấp hệ thống nguyên mẫu hàm (prototypes), các khối mã nguồn cài đặt hoàn chỉnh bằng ngôn ngữ C cho toàn bộ các giải thuật tìm kiếm, sắp xếp và hệ thống bài tập thực hành ứng dụng cuối mỗi chương.

Kết luận (150 từ)

Giáo trình Cấu trúc dữ liệu (MH11) của Trường Cao đẳng Bách Khoa Nam Sài Gòn là tài liệu học tập chuẩn hóa, cô đọng, cung cấp hệ thống kiến thức toàn diện từ cấu trúc lưu trữ dữ liệu, kỹ thuật thiết kế thuật toán đến phương pháp phân tích độ phức tạp thời gian/không gian.

Lộ trình học tập được thiết kế mạch lạc: đi từ nền tảng biểu diễn dữ liệu và con trỏ ở Chương 1, làm chủ các kỹ thuật truy xuất tìm kiếm ở Chương 2, hoàn thiện các giải thuật sắp xếp nội/ngoại ở Chương 3, đến việc làm chủ các cấu trúc dữ liệu danh sách động và hạn chế ở Chương 4. Kết hợp thực hành các bài toán thực tế như quản lý tập tin chỉ mục, biểu diễn ma trận và mô phỏng hệ thống giúp người học hình thành tư duy thuật toán và kỹ năng lập trình có cấu trúc vững vàng.