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

Giáo trình Cấu trúc dữ liệu và giải thuật do tác giả Trần Thị Kim Ngọc biên soạn năm 2018, được ban hành chính thức phục vụ công tác đào tạo nghề Lập trình máy tính và Tin học ứng dụng tại Trường Cao đẳng Nghề An Giang. Trong khung chương trình đào tạo trình độ Cao đẳng nghề và Trung cấp nghề, học phần mang mã số MH 16, thuộc nhóm môn học lý thuyết chuyên ngành với tổng thời lượng 60 giờ (gồm 20 giờ lý thuyết, 36 giờ thực hành/thảo luận và 4 giờ kiểm tra). Về vị trí đào tạo, học phần được bố trí giảng dạy sau khi người học đã hoàn thành hai học phần tiên quyết là Tin học căn bản và Lập trình căn bản.

Mục tiêu học tập của giáo trình được xác định cụ thể trên ba phương diện:

  • Kiến thức: Trang bị sự hiểu biết về dữ liệu, giải thuật và mối quan hệ tương hỗ giữa cấu trúc dữ liệu và giải thuật trong chương trình máy tính; cung cấp phương pháp phân tích độ phức tạp thời gian; hướng dẫn áp dụng các cấu trúc dữ liệu động (danh sách liên kết, ngăn xếp, hàng đợi) và các giải thuật sắp xếp, tìm kiếm vào việc giải quyết bài toán tin học.
  • Kỹ năng: Hình thành năng lực hiện thực hóa (cài đặt và biên dịch) các cấu trúc dữ liệu và giải thuật bằng ngôn ngữ lập trình cụ thể (ngôn ngữ C).
  • Năng lực tự chủ và trách nhiệm: Xây dựng phương pháp tư duy logic, tính cẩn thận và tác phong khoa học trong nghiên cứu kỹ thuật.

Cấu trúc giáo trình gồm 4 chương chính được thiết kế tiếp cận theo sự kết hợp giữa tư duy hướng đối tượng (tính đóng gói, tính tái sử dụng của các lớp cấu trúc dữ liệu) và tư duy lập trình thủ tục (cài đặt chi tiết các phương thức và giải thuật bên trong). Điểm đặc thù của tài liệu là việc phân tách rõ ràng giữa mô hình dữ liệu trừu tượng (Abstract Data Types) với các giải pháp cài đặt cụ thể trong bộ nhớ máy tính.

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

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

Nội dung giáo trình được phân bố qua 4 chương chuyên đề với tính kế thừa và logic phát triển chặt chẽ:

  • Chương 1: Giới thiệu cấu trúc dữ liệu và giải thuật: Trình bày mối liên hệ giữa giải thuật và cấu trúc dữ liệu; phân loại các lớp dịch vụ và các lớp lưu trữ xử lý dữ liệu lớn. Thiết lập phương pháp đánh giá hiệu quả giải thuật thông qua độ phức tạp thời gian trong trường hợp xấu nhất $T(n)$ và ký hiệu hàm chặn trên $O(f(n))$. Cung cấp các quy tắc xác định độ phức tạp tính toán: quy tắc cộng $O(\max(f(n), g(n)))$, quy tắc nhân $O(f(n) \cdot g(n))$, phương pháp phân tích chuỗi lệnh tuần tự, rẽ nhánh if, vòng lặp, cùng các lời gọi chương trình con không đệ quy. Đối với chương trình đệ quy, tài liệu hướng dẫn thành lập phương trình đệ quy và trình bày ba phương pháp giải: phương pháp truy hồi, đoán nghiệm quy nạp và lời giải tổng quát cho phương trình chia để trị $T(n) = aT(n/b) + d(n)$ dựa trên so sánh giữa nghiệm thuần nhất $a^{\log_b a}$ và nghiệm riêng từ hàm tiến triển nhân (multiplicative function) $d(n)$.
  • Chương 2: Các kiểu dữ liệu nâng cao: Trình bày đặc tả cú pháp và cơ chế biểu diễn bộ nhớ của mảng 1 chiều và mảng nhiều chiều (ma trận), bao gồm bộ mô tả (Descriptor: LB, UB, E, D) và công thức tính toán địa chỉ phần tử theo trật tự dòng: $$\text{Vị trí của } M[i][j] = \alpha + D + (i - LB_1) \times S + (j - LB_2 + 1) \times E$$ và trật tự cột. Phân tích sự khác biệt giữa cấp phát tĩnh và cấp phát động; cơ chế con trỏ/tham chiếu với hai phương pháp biểu diễn địa chỉ tuyệt đối và địa chỉ tương đối (độ dời offset). Hướng dẫn định nghĩa kiểu cấu trúc thông qua từ khóa struct và typedef struct, minh họa qua các cấu trúc dữ liệu NgayThang và SinhVien.
  • Chương 3: Danh sách: Khái niệm kiểu dữ liệu trừu tượng danh sách tuyến tính cùng tập hợp phép toán nguyên thủy (INSERT_LIST, LOCATE, DELETE_LIST, NEXT, PREVIOUS, FIRST, EMPTY_LIST, MAKENULL_LIST, RETRIEVE). Trình bày hai phương pháp cài đặt: danh sách đặc (dùng mảng với biến Last) và danh sách liên kết đơn (dùng con trỏ với nút Header). Định nghĩa cấu trúc ngăn xếp (Stack) theo cơ chế LIFO/FILO với các thao tác Push, Pop, Top, cài đặt bằng danh sách và mảng (Top_idx). Định nghĩa cấu trúc hàng đợi (Queue) theo cơ chế FIFO với hai đầu Front và Rear, đưa ra giải pháp xử lý tràn hàng bằng phương pháp di chuyển tịnh tiến và phương pháp mảng xoay vòng qua công thức $(Q.Front + 1) \pmod{\text{MaxLength}}$. Giới thiệu các ứng dụng: đảo ngược xâu ký tự, tính giá trị biểu thức hậu tố và chuyển đổi biểu thức trung tố sang hậu tố.
  • Chương 4: Sắp xếp và tìm kiếm: Trình bày các thuật toán sắp xếp kinh điển gồm sắp xếp chọn (Selection Sort), sắp xếp chèn (Insertion Sort), sắp xếp nổi bọt (Bubble Sort), sắp xếp nhanh (Quick Sort); cùng các thuật toán tìm kiếm gồm tìm kiếm tuần tự, tìm kiếm nhị phân và tìm kiếm tam phân.

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

  • Lý thuyết nền tảng: Lý thuyết tiệm cận toán học và ký hiệu Big-O ($O(1), O(\log n), O(n), O(n \log n), O(n^2), O(n^3), O(2^n)$); lý thuyết kiểu dữ liệu trừu tượng (ADT) tách rời đặc tả logic khỏi cấu trúc lưu trữ vật lý.
  • Nguyên lý cốt lõi: Nguyên lý vào sau - ra trước (LIFO) trong Stack; nguyên lý vào trước - ra trước (FIFO) trong Queue; nguyên lý quản lý không gian nhớ qua biến con trỏ và cấp phát động (malloc, free).
  • Khung cấu trúc: Mô hình lưu trữ tuần tự (Sequential allocation) và mô hình liên kết móc nối (Linked allocation); mô hình hàng đợi xoay vòng giải quyết bài toán tràn mảng vật lý.

Kỹ năng phát triển

  • Kỹ năng kỹ thuật: Cài đặt mã nguồn ngôn ngữ C cho các cấu trúc danh sách, ngăn xếp, hàng đợi; sử dụng thành thạo con trỏ, toán tử truy xuất trường (->, .), và quản lý bộ nhớ động.
  • Kỹ năng phân tích: Đánh giá độ phức tạp thuật toán qua các khối lệnh lặp và rẽ nhánh; thiết lập và giải các phương trình đệ quy tính thời gian thực thi $T(n)$.
  • Kỹ năng ứng dụng thực tế: Lập trình giải quyết các bài toán xử lý chuỗi, biến đổi biểu thức toán học trong trình biên dịch, quản lý bản ghi dữ liệu có cấu trúc và thao tác sắp xếp, tìm kiếm trên tập dữ liệu số nguyên.

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

Giáo trình áp dụng phương pháp sư phạm quy chuẩn theo định hướng tích hợp lý thuyết với thực hành:

  • Tiếp cận sư phạm: Kiến thức được triển khai từ trừu tượng đến cụ thể. Từng cấu trúc dữ liệu trước hết được đặc tả dưới dạng toán học và kiểu dữ liệu trừu tượng độc lập với ngôn ngữ lập trình, sau đó mới đi vào chi tiết cài đặt bằng các đoạn mã C hoàn chỉnh nhằm rèn luyện tư duy lập trình tường minh.
  • Phân bổ thời lượng giảng dạy: Tổng thời lượng 60 giờ được phân bổ khoa học: 20 giờ giảng dạy lý thuyết trên lớp (chiếm 33,3%), 36 giờ dành cho thực hành, thí nghiệm, thảo luận tại phòng máy (chiếm 60,0%), và 4 giờ kiểm tra đánh giá định kỳ (chiếm 6,7%). Tỷ trọng thực hành chiếm phần lớn nhằm đảm bảo người học làm chủ kỹ năng viết mã.
  • Hệ thống bài tập và thực hành: Sau mỗi chương, giáo trình thiết kế hệ thống bài tập phân cấp:
    • Chương 1: Bài tập tính thời gian thực thi của đoạn mã (tính tổng dãy số, tính tích ma trận vuông cấp $n$ với 3 vòng lặp lồng nhau); giải các phương trình đệ quy cụ thể ($T(n) = T(n/2) + 1$, $T(n) = 2T(n/2) + n$, $T(n) = 4T(n/3) + n^2$, $T(n) = 8T(n/2) + n^3$); viết hàm đệ quy tính số tổ hợp chập $k$ của $n$ ($C_n^k$) và tính chi phí thời gian.
    • Chương 2: Bài tập mảng (tính tổng bình phương số âm, đảo mảng, cộng/nhân ma trận cấp $m \times n$, kiểm tra tính tăng dần, tìm khoảng cách giữa phần tử lớn nhất và nhỏ nhất); bài tập struct (cộng, trừ, nhân, chia hai phân số).
    • Chương 3 & 4: Bài tập lập trình danh sách đặc, danh sách liên kết, bài tập ứng dụng ngăn xếp/hàng đợi và cài đặt các thuật toán sắp xếp nổi bọt, sắp xếp chọn.
  • Phương pháp đánh giá: Kết hợp đánh giá thường xuyên qua các bài thực hành biên dịch mã nguồn và đánh giá định kỳ 4 giờ kiểm tra tập trung vào khả năng phân tích thuật toán và cài đặt giải thuật đúng đắn.
  • Hướng dẫn tự học: Giáo trình bố trí các bài tập nâng cao ở cuối mỗi chương để kích thích người học tự nghiên cứu, đồng thời giao các nội dung tự cài đặt bổ sung (như cài đặt ngăn xếp bằng con trỏ) để sinh viên tự rèn luyện trên máy tính.

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

  • Chuyển đổi quan điểm lập trình: Khác với các giáo trình cấu trúc dữ liệu truyền thống thuần túy hướng thủ tục (vốn khiến việc phát triển giải thuật chậm, thiếu tính bao gói và khó bảo trì), tài liệu tiếp cận cấu trúc dữ liệu dựa trên quan điểm phân tích thiết kế hướng đối tượng: xem cấu trúc dữ liệu như các lớp có chức năng đóng kín và tái sử dụng, giúp mã nguồn tường minh và dễ dàng kiểm lỗi.
  • Phương pháp luận phân tích đệ quy hệ thống: Giáo trình hệ thống hóa việc giải phương trình đệ quy chia để trị qua công thức: $$T(n) = a T(n/b) + d(n)$$ xét chi tiết các trường hợp hàm tiến triển $d(n)$ là hàm nhân với ba nhánh điều kiện cụ thể giữa hệ số $a$ và giá trị $d(b)$, giúp sinh viên xác định chính xác cận trên $O(f(n))$ mà không cần suy đoán cảm tính.
  • Giải quyết triệt để các vấn đề kỹ thuật thực tế:
    • Trong cài đặt danh sách liên kết, giáo trình sử dụng kỹ thuật nút đầu giả (Header node) để chuẩn hóa thao tác chèn và xóa ở vị trí đầu tiên, hạn chế lỗi ngoại lệ khi con trỏ rỗng (NULL).
    • Trong cài đặt hàng đợi bằng mảng, giáo trình phân tích hiện tượng hàng bị tràn vật lý khi $Rear = \text{MaxLength} - 1$ và cung cấp hai giải pháp kỹ thuật chi tiết: kỹ thuật di chuyển tịnh tiến và kỹ thuật mảng xoay vòng dùng phép toán modulo.
  • Tính ứng dụng cao: Tích hợp trực tiếp các ca ứng dụng thực tế của cấu trúc dữ liệu như giải thuật đảo ngược xâu, giải thuật thẩm định và tính giá trị biểu thức dạng hậu tố (Postfix) bằng ngăn xếp, cùng các bài toán quản lý hồ sơ sinh viên thực tế.

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

  • Sinh viên mục tiêu: Sinh viên hệ Cao đẳng nghề và học sinh hệ Trung cấp nghề thuộc chuyên ngành Lập trình máy tính và Tin học ứng dụng (thường học ở học kỳ 2 hoặc năm thứ hai của khóa đào tạo).
  • Yêu cầu kiến thức tiên quyết (Prerequisites): Người học bắt buộc phải hoàn thành các môn học Tin học căn bản và Lập trình căn bản. Đòi hỏi người học có tư duy logic, nắm vững các cấu trúc điều khiển cơ bản (vòng lặp, rẽ nhánh), kiểu dữ liệu nguyên thủy, kỹ thuật viết hàm và khái niệm cơ bản về con trỏ trong ngôn ngữ lập trình C.
  • Giảng viên chuyên ngành: Sử dụng giáo trình làm tài liệu giảng dạy chuẩn mực để biên soạn đề cương bài giảng, phân bổ 20 giờ lý thuyết trên giảng đường, quản lý và hướng dẫn 36 giờ thực hành phòng máy, cũng như xây dựng ngân hàng câu hỏi kiểm tra đánh giá theo chuẩn đầu ra của môn học MH 16.
  • Tự học và tham khảo: Phù hợp làm tài liệu tham khảo cho người học ngành công nghệ thông tin muốn nghiên cứu lại nền tảng cấu trúc dữ liệu tuyến tính, phương pháp tính độ phức tạp thời gian thuật toán và kỹ thuật thao tác bộ nhớ qua con trỏ trong lập trình hệ thống.

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

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

Giáo trình được biên soạn phục vụ đào tạo trình độ Cao đẳng nghề và Trung cấp nghề cho hai ngành: Lập trình máy tính và Tin học ứng dụng. Đồng thời, tài liệu phù hợp làm nguồn tham khảo cho sinh viên chuyên ngành công nghệ thông tin cần củng cố kiến thức nền tảng về giải thuật.

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

Người học cần hoàn thành hai môn học tiên quyết là Tin học căn bản và Lập trình căn bản. Yêu cầu người học phải nắm vững tư duy logic toán học, cú pháp lập trình cơ bản (vòng lặp, câu lệnh điều kiện, chương trình con) và cách thức thao tác với ngôn ngữ C.

3. Điểm khác biệt của giáo trình so với các tài liệu khác là gì?

Tài liệu kết hợp giữa góc nhìn đóng gói hướng đối tượng với kỹ thuật lập trình thủ tục bằng ngôn ngữ C; trình bày chi tiết công thức tính toán vị trí ô nhớ của mảng nhiều chiều; cung cấp phương pháp giải toán học cho phương trình đệ quy chia để trị và xử lý triệt để hiện tượng tràn hàng đợi bằng mảng xoay vòng.

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

Người học cần đọc kỹ phần đặc tả kiểu dữ liệu trừu tượng trước khi đọc mã nguồn cài đặt, tự vẽ sơ đồ liên kết con trỏ trên giấy đối với các thao tác chèn/xóa, sau đó trực tiếp gõ mã nguồn, biên dịch và kiểm thử trên máy tính; đồng thời giải quyết toàn bộ hệ thống bài tập cơ bản và nâng cao ở cuối mỗi chương.

5. Có tài liệu bổ trợ nào kèm theo giáo trình?

Giáo trình tích hợp sẵn phần hệ thống mục lục chi tiết, danh mục thuật ngữ chuyên môn (trang 78) và danh mục tài liệu tham khảo (trang 79) để hỗ trợ sinh viên tra cứu thuật ngữ và mở rộng phạm vi nghiên cứu.

Kết luận

Giáo trình Cấu trúc dữ liệu và giải thuật (Mã môn học: MH 16) của Trường Cao đẳng Nghề An Giang cung cấp hệ thống kiến thức nền tảng về tổ chức dữ liệu và thiết kế giải thuật cho khối kỹ thuật trình độ cao đẳng và trung cấp nghề. Nội dung tài liệu làm rõ mối liên hệ giữa cấu trúc dữ liệu với giải thuật, xác lập phương pháp đánh giá độ phức tạp tính toán và hiện thực hóa các cấu trúc dữ liệu kinh điển từ mảng, con trỏ, struct đến danh sách, ngăn xếp, hàng đợi và các giải thuật sắp xếp, tìm kiếm.

Lộ trình học tập đề xuất cho người học gồm 4 giai đoạn tuần tự:

  1. Nắm vững phương pháp tính độ phức tạp $O(f(n))$ và giải phương trình đệ quy (Chương 1).
  2. Làm chủ kỹ thuật quản lý bộ nhớ mảng nhiều chiều và con trỏ (Chương 2).
  3. Hiện thực hóa các cấu trúc dữ liệu trừu tượng tuyến tính và ứng dụng ngăn xếp/hàng đợi (Chương 3).
  4. Áp dụng thành thạo các giải thuật sắp xếp và tìm kiếm vào thực tế (Chương 4).

Người học có thể khai thác thêm phần danh mục thuật ngữ chuyên môn và các tài liệu tham khảo được liệt kê ở cuối giáo trình để hoàn thiện kiến thức chuyên ngành.