Giáo trình Cấu trúc dữ liệu và giải thuật (Trường Cao đẳng Nghề An Giang)

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

Giáo trình Cấu trúc dữ liệu và giải thuật (Mã môn học: MH 16) được biên soạn bởi tác giả Trần Thị Kim Ngọc, ban hành năm 2018 theo quyết định của Hiệu trưởng Trường Cao đẳng Nghề An Giang. Tài liệu được thiết kế theo khung chương trình môn học do Bộ ban hành, phục vụ công tác đào tạo chuyên ngành Lập trình máy tính và Tin học ứng dụng ở hai trình độ: Cao đẳng nghề và Trung cấp nghề.

Về vị trí trong chương trình đào tạo, môn học thuộc khối kiến thức chuyên ngành bắt buộc, được bố trí giảng dạy sau các học phần nền tảng là Tin học căn bản và Lập trình căn bản. Môn học yêu cầu người học có tư duy logic toán học và kỹ năng lập trình cơ sở để tiếp thu các phương pháp tổ chức dữ liệu và thiết kế giải thuật.

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

  • Kiến thức: Trang bị cho sinh viên bản chất của dữ liệu, giải thuật và mối quan hệ hữu cơ giữa cấu trúc dữ liệu và giải thuật trong chương trình máy tính; phương pháp phân tích độ phức tạp thời gian; nguyên lý hoạt động của các cấu trúc dữ liệu tĩnh, 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 thuật toán tìm kiếm, sắp xếp cơ bản.
  • Kỹ năng: Sinh viên có khả năng cài đặt, biên dịch và thực thi các chương trình ứng dụng cấu trúc dữ liệu trừu tượng trên máy tính bằng ngôn ngữ lập trình cụ thể (như C/C++).
  • Năng lực tự chủ và trách nhiệm: Rèn luyện phương pháp làm việc cẩn thận, tư duy khoa học, khả năng suy nghĩ độc lập và giải quyết vấn đề kỹ thuật có hệ thống.

Về cấu trúc và cách tiếp cận, giáo trình gồm 4 chương chính. Điểm đặc thù của tài liệu là tiếp cận cấu trúc dữ liệu dưới góc nhìn của lập trình hướng đối tượng (tính đóng gói, che giấu dữ liệu, khả năng tái sử dụng) kết hợp với kỹ thuật lập trình thủ tục trong việc hiện thực hóa chi tiết các giải thuật và phương thức thao tác ô nhớ.

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

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

Nội dung giáo trình được triển khai theo tiến trình logic từ phân tích toán học, tổ chức bộ nhớ vật lý đến xây dựng các cấu trúc trừu tượng và giải thuật xử lý:

Chương 1: Giới thiệu Cấu trúc dữ liệu và Giải thuật

Chương 2: Các kiểu dữ liệu nâng cao

Chương 3: Danh sách

Chương 4: Sắp xếp và Tìm kiếm
  • 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 dữ liệu và giải thuật; phân tích sự cần thiết của việc đánh giá giải thuật dựa trên ba tiêu chuẩn: tính đúng đắn, tính đơn giản và hiệu quả thời gian. Giới thiệu thời gian thực hiện $T(n)$ trong trường hợp xấu nhất, tỷ suất tăng (growth rate) và ký hiệu tiệm cận $O(f(n))$. Cung cấp quy tắc tính độ phức tạp cho các cấu trúc tuần tự (quy tắc cộng), cấu trúc lồng nhau (quy tắc nhân), lệnh rẽ nhánh IF, vòng lặp, chương trình con không đệ quy (ví dụ giải thuật BubbleSort, Swap) và chương trình con đệ quy (thành lập và giải phương trình đệ quy tổng quát $T(n) = aT(n/b) + d(n)$ qua hàm tiến triển, nghiệm thuần nhất và nghiệm riêng).
  • Chương 2: Các kiểu dữ liệu nâng cao: Trình bày chi tiết cú pháp, mô hình bộ nhớ và phép toán trên mảng một chiều, mảng nhiều chiều (ma trận). Thiết lập công thức toán học xác định địa chỉ ô nhớ theo trật tự dòng (row-major) và trật tự cột (column-major). Phân tích cơ chế cấp phát tĩnh, cấp phát động, con trỏ (địa chỉ tuyệt đối và địa chỉ tương đối), cùng cách định nghĩa, khai báo kiểu cấu trúc (struct, typedef struct) qua các ví dụ thực tế như cấu trúc NgayThang, SinhVien.
  • Chương 3: Danh sách: Định nghĩa kiểu dữ liệu trừu tượng danh sách tuyến tính ($a_1, a_2, \dots, a_n$) và các phép toán cơ bản (Insert_List, Delete_List, Locate, First, Next, Previous, Retrieve, Empty_List, MakeNull_List). Phân tích hai phương pháp cài đặt: danh sách đặc (sử dụng mảng và biến Last) và danh sách liên kết đơn (sử dụng con trỏ và nút đầu Header). Trình bày hai cấu trúc dữ liệu hạn chế là Ngăn xếp (Stack - LIFO) và Hàng đợi (Queue - FIFO). Phân tích hiện tượng tràn hàng đợi và hai giải pháp khắc phục: di chuyển tịnh tiến và sử dụng mảng xoay vòng (circular array). Giới thiệu các bài toán ứng dụng: đảo ngược xâu ký tự, tính giá trị biểu thức hậu tố (postfix) và chuyển đổi từ trung tố (infix) sang hậu tố.
  • Chương 4: Sắp xếp và tìm kiếm: Trình bày nguyên lý, các bước thực hiện và cài đặt mã nguồn cho các giải thuật sắp xếp nội: 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 giải thuật tìm kiếm dữ liệu: Tìm kiếm tuần tự (Sequential Search), Tìm kiếm nhị phân (Binary Search) và Tìm kiếm tam phân (Ternary Search).

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

  • Lý thuyết phân tích tiệm cận: Hệ thống hóa các lớp hàm độ phức tạp thường gặp trong tin học bao gồm $\log_2 n, n, n\log_2 n, n^2, n^3, 2^n, n!, n^n$, phân định giữa lớp hàm đa thức (chấp nhận được trong thực thi) và lớp hàm mũ (cần cải tiến giải thuật).
  • Mô hình ánh xạ bộ nhớ: Xây dựng công thức tính vị trí phần tử mảng dựa trên địa chỉ cơ sở $\alpha$, kích thước bộ mô tả $D$, cận dưới $LB$, cận trên $UB$ và kích thước phần tử $E$: $$\text{Vị trí } M[i][j] = \alpha + D + (i - LB_1) \times S + (j - LB_2 + 1) \times E$$
  • Lý thuyết kiểu dữ liệu trừu tượng (ADT): Phân tách độc lập giữa phần đặc tả phép toán trừu tượng và phần cài đặt cụ thể trên cấu trúc dữ liệu vật lý.

Kỹ năng phát triển

  • Kỹ năng kỹ thuật: Khai báo, thao tác biến con trỏ, cấp phát và thu hồi vùng nhớ động thông qua các hàm hệ thống (malloc, free); định nghĩa cấu trúc dữ liệu lồng nhau; xử lý chỉ số mảng xoay vòng bằng phép toán modulo.
  • Kỹ năng phân tích: Thiết lập phương trình đệ quy mô tả thời gian chạy của thuật toán chia để trị; chứng minh tiệm cận trên $O(f(n))$ bằng phương pháp toán học và quy nạp.
  • Kỹ năng giải quyết bài toán: Cài đặt các thao tác chèn, xóa, định vị, duyệt trên danh sách tuyến tính; chuyển đổi thuật toán lý thuyết thành chương trình chạy được trên máy tính.

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

Giáo trình được thiết kế với tổng thời lượng thực hiện là 60 giờ, phân bổ cụ thể theo cơ cấu:

  • Lý thuyết: 20 giờ (chiếm 33,3% tổng thời lượng)
  • Thực hành, thí nghiệm, thảo luận: 36 giờ (chiếm 60% tổng thời lượng)
  • Kiểm tra: 4 giờ (chiếm 6,7% tổng thời lượng)
Phân bổ thời lượng môn học (Tổng: 60 giờ)

Phương pháp tiếp cận sư phạm của tài liệu đi từ mô hình toán học trừu tượng đến mô hình bộ nhớ vật lý, sau đó chuyển giao sang mã giả và cài đặt mã nguồn hoàn chỉnh bằng ngôn ngữ C. Mỗi cấu trúc dữ liệu đều được phân tích ưu điểm, nhược điểm trong việc sử dụng bộ nhớ và tốc độ thực thi, giúp người học hiểu rõ nguyên nhân lựa chọn cấu trúc phù hợp cho từng bài toán.

Hệ thống bài tập trong giáo trình được phân loại theo từng chương:

  • Bài tập cơ bản: Củng cố lý thuyết và kỹ năng thao tác mảng (tính tổng bình phương số âm, đảo mảng, cộng/nhân ma trận, kiểm tra mảng tăng dần), tính toán độ phức tạp của các đoạn mã lặp lồng nhau, khai báo cấu trúc phân số và thực hiện phép tính số học.
  • Bài tập nâng cao: Giải các phương trình đệ quy dạng $T(n) = aT(n/b) + d(n)$, viết hàm đệ quy tính số tổ hợp chập $k$ của $n$ ($C_n^k$), cài đặt ngăn xếp/hàng đợi bằng danh sách liên kết, xử lý biểu thức toán học hậu tố và tối ưu thuật toán sắp xếp.

Về phương pháp đánh giá và tự học, giáo trình yêu cầu sinh viên kết hợp việc đọc hiểu lý thuyết với thực hành trực tiếp tại phòng máy (36 giờ thực hành). Người học cần tự viết chương trình, kiểm tra tính đúng đắn trên các bộ dữ liệu thử nghiệm (test cases), và rèn luyện kỹ năng phát hiện lỗi biên dịch cũng như lỗi logic trong quá trình cấp phát con trỏ.

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

  • Tính chuẩn hóa theo chương trình khung: Giáo trình được xây dựng dựa trên chương trình khung của Bộ ban hành cho hệ đào tạo nghề, bảo đảm tính thống nhất về khối lượng kiến thức và kỹ năng thực hành nghề nghiệp.
  • Tích hợp quan điểm hướng đối tượng trong giảng dạy cấu trúc dữ liệu: Tài liệu phân loại rõ ràng các lớp đối tượng trong phần mềm thành "lớp dịch vụ" và "lớp lưu trữ/xử lý lượng dữ liệu lớn". Việc nhấn mạnh tính đóng gói (encapsulation) giúp sinh viên tách biệt giao diện thao tác dữ liệu với chi tiết cài đặt bên trong, khắc phục nhược điểm mã nguồn khó bảo trì của phương pháp lập trình thủ tục truyền thống.
  • Trình bày trực quan cơ chế quản lý bộ nhớ: Giáo trình cung cấp các sơ đồ minh họa cụ thể về:
    • Cấu trúc khối ô nhớ mảng gồm bộ mô tả và vùng nhớ dữ liệu liên tiếp.
    • Cơ chế liên kết con trỏ sử dụng nút đầu Header đặc biệt nhằm đơn giản hóa thuật toán chèn và xóa nút.
    • Hiện tượng tràn hàng đợi và cơ chế khắc phục bằng kỹ thuật mảng xoay vòng.
  • Gắn kết giải thuật với các ứng dụng thực tế: Nội dung không dừng lại ở lý thuyết thuần túy mà tích hợp trực tiếp các giải thuật ứng dụng như: đảo ngược chuỗi ký tự kết thúc bằng ký tự quy ước, đánh giá và thực thi biểu thức số học dạng hậu tố (postfix), thuật toán chuyển đổi biểu thức trung tố sang hậu tố dùng ngăn xếp.

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

  • Sinh viên: Giáo trình được biên soạn chuyên biệt cho 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.
  • Điều kiện tiên quyết (Prerequisites): Người học cần hoàn thành các học phần Tin học căn bản và Lập trình căn bản. Cần nắm vững kiến thức toán logic, các cấu trúc điều khiển (rẽ nhánh if/else, vòng lặp for/while), khái niệm hàm và các kiểu dữ liệu cơ sở trong ngôn ngữ lập trình.
  • Giảng viên: Tài liệu đóng vai trò là giáo trình giảng dạy chính thức cho học phần Cấu trúc dữ liệu và giải thuật (MH 16), làm căn cứ xây dựng đề cương bài giảng, phân bổ giáo án 60 giờ (20 lý thuyết / 36 thực hành), thiết lập đề thi kết thúc học phần và xây dựng ngân hàng bài tập phòng máy.
  • Đối tượng tự học và tham khảo: Lập trình viên mới bắt đầu cần tài liệu hệ thống hóa về mặt bản chất các kiểu dữ liệu mảng, con trỏ, danh sách liên kết, ngăn xếp, hàng đợi, cũng như phương pháp tính độ phức tạp thời gian phục vụ tối ưu hóa mã nguồn.

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

1. Giáo trình này phù hợp với đối tượng người học nào?

Tài liệu được thiết kế cho người học trình độ Cao đẳng nghề và Trung cấp nghề ngành Lập trình máy tính và Tin học ứng dụng. Nội dung được trình bày từ mức độ cơ bản, tập trung vào kỹ năng cài đặt mã nguồn thực tế và tư duy giải thuật.

2. Cần chuẩn bị kiến thức nền tảng nào trước khi 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 nắm vững cú pháp lập trình cơ bản (biến, câu lệnh điều kiện, vòng lặp, hàm) và có tư duy logic toán học cơ sở.

3. Giáo trình này có điểm gì khác biệt trong cách tiếp cận nội dung?

Giáo trình kết hợp giữa việc giải thích bản chất lưu trữ vật lý trong bộ nhớ (công thức tính địa chỉ ô nhớ, quản lý con trỏ malloc/free) với tư duy lập trình hướng đối tượng (tính đóng kín và tái sử dụng của các lớp dữ liệu), đồng thời phân tích chi tiết phương pháp giải phương trình đệ quy tổng quát.

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

Người học nên kết hợp đọc lý thuyết với việc tự cài đặt lại các đoạn mã mẫu trong sách trên máy tính. Cần thực hiện đầy đủ các bài tập ở cuối mỗi chương, đặc biệt là các bài tập phân tích độ phức tạp thuật toán và các bài tập cài đặt danh sách liên kết, ngăn xếp, hàng đợi.

5. Giáo trình có tài liệu bổ trợ hoặc phần tra cứu nào đi kèm không?

Ở cuối tài liệu có hệ thống mục từ Các thuật ngữ chuyên môn (trang 78) giúp chuẩn hóa các khái niệm tin học, cùng danh mục Tài liệu tham khảo (trang 79) hỗ trợ người học mở rộng kiến thức chuyên sâu.

Kết luận

Giáo trình Cấu trúc dữ liệu và giải thuật của tác giả Trần Thị Kim Ngọc là tài liệu giảng dạy chuẩn hóa được ban hành theo quy định đào tạo nghề của Trường Cao đẳng Nghề An Giang. Giáo trình cung cấp hệ thống kiến thức toàn diện từ lý thuyết phân tích độ phức tạp giải thuật, kỹ thuật tổ chức bộ nhớ mảng và con trỏ, đến các cấu trúc dữ liệu động và thuật toán sắp xếp, tìm kiếm kinh điển.

Lộ trình học tập được khuyến nghị là tiếp cận tuần tự theo 4 chương: nắm vững phương pháp đánh giá thuật toán ở Chương 1; thực hành kiểu dữ liệu nâng cao ở Chương 2; làm chủ các cấu trúc danh sách, ngăn xếp, hàng đợi ở Chương 3; và hoàn thiện kỹ năng xử lý dữ liệu qua các giải thuật sắp xếp, tìm kiếm ở Chương 4. Người học có thể sử dụng bảng thuật ngữ và danh mục tài liệu tham khảo ở cuối sách để củng cố và tra cứu thuật ngữ chuyên ngành trong quá trình học tập.