TỔNG QUAN HỌC THUẬT VỀ GIÁO TRÌNH CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (MÃ TÀI LIỆU: MH17)

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ã tài liệu: MH17) được ban hành kèm theo Quyết định số 120/QĐ-TCDN ngày 25 tháng 02 năm 2013 của Tổng cục trưởng Tổng cục Dạy nghề thuộc Bộ Lao động – Thương binh và Xã hội. Tài liệu do ThS. Ngô Thị Thanh Trang làm Chủ biên cùng tác giả Trương Văn Hòa tham gia biên soạn, phục vụ đào tạo trình độ Cao đẳng nghề cho nghề Quản trị mạng và các chuyên ngành liên quan đến Công nghệ thông tin. Trong chương trình đào tạo, môn học mang tính chất chuyên ngành và là môn học cơ sở ngành, được bố trí giảng dạy sau khi người học đã hoàn thành các môn học/mô-đun Lập trình căn bản và Cơ sở dữ liệu.

Mục tiêu học tập của giáo trình bao gồm:

  • Mô tả được các khái niệm về kiểu dữ liệu trừu tượng (danh sách, cây, đồ thị), kiểu dữ liệu cơ bản, cấu trúc dữ liệu và giải thuật.
  • Nắm vững và thực hiện các phép toán cơ bản tương ứng với từng cấu trúc dữ liệu và giải thuật.
  • Tổ chức dữ liệu khoa học, hợp lý cho các chương trình xử lý thông tin.
  • Áp dụng giải thuật phù hợp trên cấu trúc dữ liệu tương ứng để giải quyết bài toán trên máy tính điện tử.
  • Áp dụng thành thạo các phương pháp sắp xếp và tìm kiếm cơ bản.
  • Đảm bảo an toàn cho người và thiết bị trong quá trình thực hành.

Chương trình môn học có tổng thời lượng 90 giờ (trong đó gồm 45 giờ lý thuyết, 41 giờ thực hành và 4 giờ kiểm tra định kỳ). Tiếp cận theo luận điểm kinh điển của Niklaus Wirth: "Chương trình = Cấu trúc dữ liệu + Giải thuật" (Programs = Data Structures + Algorithms), giáo trình sử dụng ngôn ngữ tựa Pascal (pseudo-Pascal) làm công cụ mô tả thuật toán, giúp chuẩn hóa việc phân tích logic và thao tác bộ nhớ mà không bị phụ thuộc vào cú pháp riêng biệt của từng trình biên dịch thương mại.

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

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

Giáo trình được cấu trúc thành 7 chương với tiến trình phát triển kiến thức từ nền tảng lý thuyết, cấu trúc tuyến tính đến cấu trúc phi tuyến và giải thuật nâng cao:

[Chương 1: Tổng quan CTDL & Giải thuật] (5h)
[Chương 2: Đệ quy & Giải thuật đệ quy] (5h)
[Chương 3: Cấu trúc Danh sách, Stack, Queue] (30h)
[Chương 6: Cấu trúc Cây & Duyệt cây] (10h)
[Chương 7: Cấu trúc Đồ thị & Đường đi] (10h)
  • Chương 1: Tổng quan về Cấu trúc dữ liệu và giải thuật (5 giờ: 4 LT, 1 TH): Trình bày nguồn gốc thuật ngữ thuật toán từ nhà toán học Abu Ja'far Mohammed ibn Musa al Khowarizmi; các ngôn ngữ diễn đạt giải thuật; phương pháp thiết kế giải thuật theo nguyên lý "tinh chỉnh từng bước" (stepwise refinement); phương pháp đánh giá độ phức tạp thuật toán qua thời gian thực hiện $T(n)$ và ký hiệu $O$ lớn; hệ thống kiểu dữ liệu sơ cấp, kiểu bản ghi (record), biến con trỏ (pointer), kiểu dữ liệu trừu tượng (ADT); cấu trúc lưu trữ kế tiếp (mảng) và móc nối (danh sách liên kết); mối quan hệ tương hỗ giữa dữ liệu và thuật toán qua bài toán quản lý điểm sinh viên.
  • Chương 2: Đệ quy và giải thuật đệ quy (5 giờ: 2 LT, 2 TH, 1 KT): Định nghĩa về đối tượng và giải thuật đệ quy; cấu trúc chương trình con đệ quy gồm phần neo (điều kiện dừng) và phần đệ quy (quy nạp); cài đặt các bài toán đệ quy căn bản gồm hàm tính giai thừa ($n!$), bài toán dãy số Fibonacci (mô hình sinh sản của các cặp thỏ), và giải thuật Euclide tìm ước số chung lớn nhất (USCLN).
  • Chương 3: Danh sách (30 giờ: 15 LT, 14 TH, 1 KT): Định nghĩa danh sách tuyến tính; cài đặt danh sách trên mảng với các thủ tục MakeNull_List, Empty_List, Insert_List, Delete_List; cài đặt danh sách liên kết đơn (cấu trúc nút Node gồm Info và con trỏ Link, cấp phát New và giải phóng Dispose); kỹ thuật danh sách liên kết kép (con trỏ LPTR và RPTR), danh sách liên kết vòng (sử dụng "nút đầu danh sách"); các cấu trúc đặc biệt gồm Ngăn xếp (Stack - cơ chế LIFO, quản lý biến đỉnh $T$, xử lý tràn/cạn trên mảng và danh sách liên kết) và Hàng đợi (Queue - cơ chế FIFO).
  • Chương 4: Các phương pháp sắp xếp cơ bản (22 giờ: 10 LT, 11 TH, 1 KT): Định nghĩa bài toán sắp xếp dữ liệu; nguyên lý và cài đặt thuật toán sắp xếp chọn (Selection sort), sắp xếp chèn (Insertion sort), sắp xếp đổi chỗ (Interchange sort), sắp xếp nổi bọt (Bubble sort) và sắp xếp nhanh (Quick sort).
  • Chương 5: Tìm kiếm (8 giờ: 2 LT, 5 TH, 1 KT): Định nghĩa bài toán tra cứu dữ liệu; phân tích và cài đặt giải thuật tìm kiếm tuyến tính (Linear search) và tìm kiếm nhị phân (Binary search).
  • Chương 6: Cây (10 giờ: 6 LT, 4 TH): Khái niệm cây, cây nhị phân và cây tổng quát; phương pháp biểu diễn cây trong bộ nhớ; các thuật toán duyệt cây nhị phân theo thứ tự trước (Gốc – Trái – Phải), thứ tự giữa (Trái – Gốc – Phải) và thứ tự sau (Trái – Phải – Gốc).
  • Chương 7: Đồ thị (10 giờ: 6 LT, 4 TH): Định nghĩa cấu trúc đồ thị; kỹ thuật biểu diễn đồ thị bằng ma trận kề và danh sách các đỉnh kề; giải thuật giải quyết bài toán tìm đường đi trên đồ thị.

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

Giáo trình hình thành nền tảng lý thuyết có hệ thống thông qua ba trụ cột:

  1. Lý thuyết độ phức tạp tính toán: Phân loại thời gian chạy theo cấp hàm tiệm cận, sắp xếp theo thứ tự tăng dần về chi phí thực thi:
Ký hiệu Ô lớn Tên gọi thông thường Nhóm hàm
$O(1)$ Hằng số Đa thức
$O(\log_2 n)$ Logarit Đa thức
$O(n)$ Tuyến tính Đa thức
$O(n \log_2 n)$ $n \log_2 n$ Đa thức
$O(n^2)$ Bình phương Đa thức
$O(n^3)$ Lập phương Đa thức
$O(2^n)$ Mũ Loại mũ
  1. Nguyên lý cấu trúc lưu trữ và tính toán địa chỉ vật lý:
    • Mảng một chiều $A[i]$ với cận dưới chỉ số là $b$, địa chỉ gốc $L_0$, kích thước phần tử $\omega$: $$\text{LOC}(A[i]) = L_0 + \omega \times (i - b)$$
    • Ma trận $B[m, n]$ lưu trữ theo thứ tự ưu tiên hàng ($b_1 \le i \le u_1, b_2 \le j \le u_2$): $$\text{LOC}(B[i,j]) = L_0 + \left[(i - b_1) \times (u_2 - b_2 + 1) + (j - b_2)\right] \times \omega$$
    • Ma trận lưu trữ theo thứ tự ưu tiên cột: $$\text{LOC}(B[i,j]) = L_0 + \left[(j - 1) \times m + (i - 1)\right] \times \omega$$
  2. Mô hình cấp phát bộ nhớ: Phân biệt rõ giữa cấp phát tĩnh (bộ nhớ cố định khi biên dịch qua mảng) và cấp phát động (cấp phát thời gian chạy thông qua biến con trỏ Pointer, nút Node liên kết qua các mối nối địa chỉ).

Kỹ năng phát triển

  • Kỹ năng kỹ thuật (Technical skills): Cài đặt thành thạo các cấu trúc dữ liệu cơ bản và nâng cao (Danh sách đặc, DSLK đơn/kép/vòng, Stack, Queue, Cây nhị phân, Đồ thị); thực hiện các thao tác quản trị bộ nhớ động (New, Dispose); chuyển dịch mã thuật toán tựa Pascal sang ngôn ngữ lập trình cụ thể.
  • Kỹ năng phân tích (Analytical skills): Phân tích bài toán theo phương pháp tinh chỉnh từng bước; tính toán và đánh giá độ phức tạp thời gian $O(f(n))$ của thuật toán; lựa chọn cấu trúc lưu trữ tối ưu tương ứng với tần suất thao tác dữ liệu (truy xuất ngẫu nhiên so với chèn/xóa liên tục).
  • Kỹ năng thực hành (Practical competencies): Lập trình cài đặt các giải thuật sắp xếp và tìm kiếm; giải quyết bài toán đệ quy và chuyển đổi giữa thuật toán đệ quy sang thuật toán lặp (như trong bài toán tìm ước số chung lớn nhất Euclide và dãy số Fibonacci).

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

Tiếp cận sư phạm (Pedagogical approach)

Giáo trình triển khai phương pháp giảng dạy kết hợp giữa phân tích mô hình khái niệm trừu tượng (ADT) với việc cụ thể hóa cấu trúc lưu trữ vật lý trong bộ nhớ máy tính. Thuật toán được thiết kế bằng phương pháp "tinh chỉnh từng bước": đi từ việc xác định dữ liệu đầu vào (input) và đầu ra (output), phân chia bài toán thành các mô-đun con độc lập, sau đó mới hình thức hóa thành các câu lệnh điều khiển.

Ngôn ngữ tựa Pascal được sử dụng xuyên suốt tài liệu nhằm đảm bảo tính mô phạm, giúp sinh viên nắm bắt bản chất của các cấu trúc rẽ nhánh (if-then-else, case), vòng lặp xác định (for-to-do, for-downto-do), vòng lặp không xác định (while-do, repeat-until), và chương trình con dạng hàm (Function) hoặc thủ tục (Procedure).

Bài tập, ví dụ và bài toán điển hình

Các khái niệm kỹ thuật được giải thích thông qua các ví dụ và mô hình đối sánh:

  • Cơ chế hoán vị biến: Minh họa việc tráo đổi dữ liệu giữa hai phần tử $A[k]$ và $A[i]$ bằng ví dụ hoán vị chất lỏng giữa cốc đựng rượu và cốc đựng nước thông qua một cốc trung chuyển thứ ba (LOC := A[k]; A[k] := A[i]; A[i] := LOC;).
  • Tổ chức dữ liệu mảng: So sánh hai phương án tổ chức lưu trữ bảng điểm của 3 sinh viên qua 4 môn học bằng mảng một chiều (12 phần tử) và mảng hai chiều (kích thước $3 \times 4$), từ đó chứng minh phương án mảng hai chiều tạo điều kiện cho thuật toán xuất dữ liệu tự nhiên và tối ưu hơn.
  • Mô hình đệ quy: Bài toán cổ về sự sinh sản của các cặp thỏ không bao giờ chết để thiết lập công thức truy hồi Fibonacci $F(n) = F(n-1) + F(n-2)$; thuật toán chia lấy dư Euclide để tính ước số chung lớn nhất giữa 1260 và 198 qua các bước lặp $p, q, r$.

Đánh giá và hướng dẫn tự học

  • Phân bổ thời lượng: Tổng thời gian học tập là 90 giờ, trong đó thời lượng thực hành (41 giờ) chiếm tỷ trọng xấp xỉ thời lượng lý thuyết (45 giờ), tạo điều kiện cho việc rèn luyện kỹ năng viết mã trên máy tính.
  • Đánh giá kết quả: Giáo trình tích hợp 4 giờ kiểm tra định kỳ phân bổ tại các mốc trọng tâm: kết thúc Chương 2 (Đệ quy), Chương 3 (Danh sách), Chương 4 (Sắp xếp) và Chương 5 (Tìm kiếm).
  • Hướng dẫn tự học: Cuối mỗi chương đều có mục Bài tập thực hành của học viên đi kèm phần Gợi ý làm bài, cung cấp cấu trúc giải thuật mẫu (như thủ tục lặp FIBONACCI, hàm đệ quy RUSCLN, hàm lặp IUSCLN) để người học tự đối chiếu và kiểm tra logic lập trình.

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

  • Chuẩn hóa văn bản đào tạo nghề nghiệp: Giáo trình được ban hành chính thức theo Quyết định số 120/QĐ-TCDN năm 2013, bảo đảm tuân thủ khung chương trình quốc gia của Tổng cục Dạy nghề cho hệ Cao đẳng nghề.
  • Đặc tả chi tiết cấu trúc bộ nhớ vật lý: Tài liệu cung cấp chính xác các công thức tính toán địa chỉ từ máy ($\text{LOC}$) cho mảng một chiều và mảng đa chiều theo cả hai trường hợp ưu tiên hàng và ưu tiên cột. Điều này trang bị cho học viên ngành Quản trị mạng hiểu rõ cơ chế cấp phát tài nguyên và định vị vùng nhớ ở mức hệ thống.
  • Phân tách rạch ròi giữa ADT và Cấu trúc lưu trữ: Phân biệt rõ giữa khái niệm logic (Kiểu dữ liệu trừu tượng như Danh sách, Ngăn xếp, Hàng đợi, Cây) và cách cài đặt cụ thể trong bộ nhớ (Lưu trữ kế tiếp trên Mảng tĩnh hoặc Lưu trữ móc nối qua Biến con trỏ), giúp người học nhận thức rõ các ưu nhược điểm về hiệu năng và không gian nhớ.
  • Liên kết ứng dụng ngành Quản trị mạng: Các cấu trúc dữ liệu như danh sách liên kết, ngăn xếp, cấu trúc cây phân cấp và đồ thị có tính kết nối trực tiếp với các bài toán quản lý danh sách tiến trình, quản trị bộ đệm mạng, duyệt cây thư mục và tìm đường đi ngắn nhất trong hạ tầng mạng máy tính.

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

  • Sinh viên trình độ Cao đẳng nghề: Phục vụ trực tiếp cho sinh viên theo học nghề Quản trị mạng từ năm thứ nhất hoặc năm thứ hai (sau khi đã tích lũy các môn học cơ sở ban đầu). Đồng thời, tài liệu phù hợp làm giáo trình nền tảng cho sinh viên các khối ngành Công nghệ thông tin, Kỹ thuật phần mềm, và Hệ thống thông tin.
  • Kiến thức tiên quyết (Prerequisites): Người học bắt buộc phải hoàn thành và nắm vững kiến thức từ hai môn học/mô-đun:
    1. Lập trình căn bản (hiểu về cú pháp, biến, biểu thức, các cấu trúc điều khiển).
    2. Cơ sở dữ liệu (hiểu về tổ chức bản ghi, bảng dữ liệu và quan hệ thông tin).
  • Giảng viên chuyên ngành: Sử dụng làm tài liệu giảng dạy chuẩn hóa với đề cương chi tiết 90 giờ; khai thác hệ thống bài tập thực hành, cấu trúc thuật toán tựa Pascal và các bài toán mẫu để biên soạn bài giảng lý thuyết, bài thực hành phòng máy và đề thi đánh giá năng lực.
  • Tự học và tham khảo: Dành cho kỹ thuật viên và người học cần tài liệu tra cứu có hệ thống về cơ chế bộ nhớ, biểu diễn cây - đồ thị và các giải thuật sắp xếp/tìm kiếm kinh điển.

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

1. Giáo trình này được thiết kế dành cho đối tượng nào?

Tài liệu được biên soạn phục vụ đào tạo trình độ Cao đẳng nghề cho nghề Quản trị mạng theo khung chương trình của Tổng cục Dạy nghề, đồng thời dùng làm tài liệu cơ sở ngành cho sinh viên theo học các ngành liên quan đến Công nghệ thông tin.

2. Cần chuẩn bị kiến thức nền tảng nào trước khi học môn này?

Theo quy định của chương trình đào tạo, sinh viên cần học xong và nắm vững kiến thức của hai môn học/mô-đun tiên quyết là Lập trình căn bản và Cơ sở dữ liệu.

3. Ngôn ngữ nào được sử dụng để minh họa các thuật toán trong giáo trình?

Giáo trình sử dụng ngôn ngữ tựa Pascal (pseudo-Pascal) làm công cụ mô tả giải thuật. Ngôn ngữ này sử dụng các từ khóa chuẩn (Program, Function, Procedure, Record, Pointer, begin...end, if-then-else, for, while, repeat-until) và lược bỏ các khai báo rườm rà nhằm tập trung hoàn toàn vào cấu trúc logic của giải thuật.

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

Người học cần kết hợp đọc lý thuyết phân tích thuật toán, vẽ sơ đồ chuyển động của dữ liệu (như cơ chế hoạt động của con trỏ và các nút liên kết), sau đó tự giải các bài tập ở cuối mỗi chương trước khi đối chiếu với phần Gợi ý làm bài. Ngoài ra, người học cần cài đặt chuyển đổi mã tựa Pascal sang ngôn ngữ lập trình cụ thể để biên dịch và chạy thử nghiệm trên máy tính.

5. Tài liệu có cung cấp cấu trúc bài tập và hướng dẫn giải không?

Có. Cuối mỗi chương đều có mục Bài tập thực hành của học viên bao gồm các câu hỏi lý thuyết, bài tập tính toán địa chỉ bộ nhớ và yêu cầu viết mã giải thuật. Các bài toán phức tạp (như chuyển đổi thuật toán đệ quy sang thuật toán lặp cho bài toán Fibonacci và tìm ước số chung lớn nhất) đều có phần Gợi ý làm bài đi kèm mã nguồn mẫu.

Kết luận

Giáo trình Cấu trúc dữ liệu và giải thuật (Mã tài liệu: MH17) cung cấp hệ thống tri thức nền tảng và chuẩn hóa về phương pháp tổ chức dữ liệu và thiết kế giải thuật xử lý trên máy tính điện tử. Thông qua cấu trúc 7 chương học kết hợp chặt chẽ giữa 45 giờ lý thuyết và 41 giờ thực hành, tài liệu xác lập lộ trình học tập khoa học: đi từ đánh giá độ phức tạp thuật toán tiệm cận $O(f(n))$, kỹ thuật đệ quy, thao tác trên cấu trúc dữ liệu tuyến tính (Mảng, Danh sách liên kết, Stack, Queue), các thuật toán chuẩn về Sắp xếp và Tìm kiếm, đến các cấu trúc phi tuyến phức tạp (Cây, Đồ thị).

Nội dung giáo trình là tài liệu căn bản phục vụ trực tiếp cho việc thiết kế, xây dựng phần mềm và quản trị hạ tầng hệ thống máy tính trong chương trình đào tạo Cao đẳng nghề Quản trị mạng.