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: MH17) là tài liệu giảng dạy và học tập thuộc khối kiến thức cơ sở ngành bắt buộc trong chương trình đào tạo chuyên ngành Công nghệ thông tin và các ngành kỹ thuật liên quan. Trong khung chương trình đào tạo, môn học được bố trí giảng dạy sau khi người học đã hoàn thành các học phần tiên quyết bao gồm "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 tập trung vào việc trang bị cho sinh viên hệ thống kiến thức nền tảng về các kiểu dữ liệu trừu tượng (danh sách, ngăn xếp, cây, đồ thị), các cấu trúc lưu trữ dữ liệu tương ứng (lưu trữ kế tiếp trên mảng và lưu trữ móc nối qua con trỏ), cùng hệ thống các giải thuật xử lý tiêu chuẩn. Sau khi hoàn thành nội dung giáo trình, người học có khả năng phân tích mối quan hệ giữa cấu trúc dữ liệu và giải thuật, đánh giá độ phức tạp tính toán của thuật toán, lựa chọn và tổ chức cấu trúc dữ liệu tối ưu nhằm cài đặt chương trình máy tính giải quyết các bài toán kỹ thuật cụ thể.

Về mặt cấu trúc, giáo trình được thiết kế với tổng thời lượng 90 tiết, bao gồm 45 tiết lý thuyết, 41 tiết thực hành và 4 tiết kiểm tra đánh giá, phân bổ qua 7 chương nội dung:

  • Chương 1: Tổng quan về Cấu trúc dữ liệu và giải thuật (5 tiết: 4 lý thuyết, 1 thực hành)
  • Chương 2: Đệ quy và giải thuật đệ quy (5 tiết: 2 lý thuyết, 2 thực hành, 1 kiểm tra)
  • Chương 3: Danh sách (30 tiết: 15 lý thuyết, 14 thực hành, 1 kiểm tra)
  • Chương 4: Các phương pháp sắp xếp cơ bản (22 tiết: 10 lý thuyết, 11 thực hành, 1 kiểm tra)
  • Chương 5: Tìm kiếm (8 tiết: 2 lý thuyết, 5 thực hành, 1 kiểm tra)
  • Chương 6: Cây (10 tiết: 6 lý thuyết, 4 thực hành)
  • Chương 7: Đồ thị (10 tiết: 6 lý thuyết, 4 thực hành)

Giáo trình tiếp cận kiến thức theo nguyên lý kết hợp chặt chẽ giữa đặc tả toán học trừu tượng và cài đặt kỹ thuật bộ nhớ vật lý, áp dụng phương pháp thiết kế giải thuật "tinh chỉnh từng bước" (stepwise refinement) để chuyển hóa bài toán từ mô hình thực tiễn sang mã nguồn thực thi.

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 triển khai tuần tự qua 7 chương học thuật với cấu trúc logic từ cơ bản đến phức tạp:

  • Chương 1: Tổng quan về Cấu trúc dữ liệu và giải thuật: Giới thiệu 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 (khoảng năm 825). Xác định 6 đặc trưng của giải thuật: Dữ liệu vào (Input), Dữ liệu ra (Output), Tính xác định, Tính dừng, Tính phổ dụng và Tính hiệu quả. Trình bày 4 phương pháp biểu diễn giải thuật (ngôn ngữ tự nhiên, sơ đồ khối/flowchart với các khối điều kiện hình thoi và khối xử lý hình chữ nhật, mã giả pseudocode, ngôn ngữ lập trình). Thiết lập quy cách cấu trúc chương trình, câu lệnh điều khiển, cấu trúc dữ liệu cơ bản (kiểu nguyên, thực, ký tự, chuỗi ký tự String tối đa 255 ký tự trong Pascal), kiểu bản ghi (Record), kiểu con trỏ và cấp phát động. Phân tích cấu trúc lưu trữ kế tiếp của mảng một chiều, ma trận hai chiều theo thứ tự ưu tiên hàng và ưu tiên cột cùng công thức giải tích xác định địa chỉ bộ nhớ; cấu trúc danh sách liên kết; đánh giá độ phức tạp thuật toán qua ký hiệu $O$ lớn ($O(1), O(\log_2 n), O(n), O(n\log_2 n), O(n^2), O(n^3), O(2^n)$); và thiết lập mối quan hệ nền tảng: $\text{Cấu trúc dữ liệu} + \text{Giải thuật} = \text{Chương trình}$.
  • Chương 2: Đệ quy và giải thuật đệ quy: Định nghĩa đối tượng đệ quy, phân tích cấu trúc chương trình con đệ quy gồm hai phần bắt buộc: 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 kinh điển: tính giai thừa $n!$, dãy số Fibonacci ($F(n) = F(n-1) + F(n-2)$ xuất phát từ bài toán sinh sản đàn thỏ), bài toán Tháp Hà Nội (ngôi đền Benares với $n$ đĩa vàng trên 3 cọc), và thuật toán Euclide tìm ước số chung lớn nhất (USCLN) qua cả hai phương pháp đệ quy và lặp.
  • Chương 3: Danh sách: Khảo sát kiểu dữ liệu trừu tượng danh sách và các phép toán cơ bản (khởi tạo rỗng, kiểm tra rỗng, chèn, xóa, tìm kiếm, sắp xếp, ghép, tách). Phân tích chi tiết hai phương thức cài đặt: cài đặt danh sách tuyến tính bằng mảng tĩnh và cài đặt bằng danh sách liên kết động (danh sách liên kết đơn với con trỏ pHead/pTail, danh sách liên kết kép với hai liên kết LPTR/RPTR, danh sách liên kết vòng sử dụng nút đầu danh sách - dummy node). Phân tích cấu trúc dữ liệu đặc biệt: Ngăn xếp (Stack) hoạt động theo cơ chế LIFO (Last-In-First-Out) tại đỉnh Top, xử lý hiện tượng tràn bộ nhớ (overflow) và cạn bộ nhớ (underflow) trên cả mảng và danh sách liên kết.
  • Chương 4: Các phương pháp sắp xếp cơ bản: Định nghĩa bài toán sắp xếp và cài đặt chi tiết 5 thuật toán sắp xếp trên mảng dữ liệu: 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: Trình bày nguyên lý, giải thuật và ví dụ minh họa của hai phương pháp tìm kiếm dữ liệu cơ bản: Tìm kiếm tuyến tính (Linear Search) và Tìm kiếm nhị phân (Binary Search) trên tập dữ liệu đã sắp thứ tự.
  • Chương 6: Cây: Định nghĩa cấu trúc phân nhánh cây và cây nhị phân; các phương pháp biểu diễn cây nhị phân và cây tổng quát trong bộ nhớ máy tính; giải thuật duyệt cây nhị phân theo 3 thứ tự: duyệt trước (NLR: Gốc – Trái – Phải), duyệt giữa (LNR: Trái – Gốc – Phải), duyệt sau (LRN: Trái – Phải – Gốc).
  • Chương 7: Đồ thị: Định nghĩa cấu trúc đồ thị phi tuyến; hai phương pháp biểu diễn đồ thị chính: Ma trận kề (Adjacency Matrix) và Danh sách đỉnh kề (Adjacency List); 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

  • Lý thuyết độ phức tạp tính toán: Phân định phương pháp đánh giá thực nghiệm và phương pháp lý thuyết toán học. Thiết lập hàm thời gian $T(n)$ dựa trên số lượng phép toán sơ cấp và quy chuẩn hóa bằng ký hiệu tiệm cận $O(f(n))$, phân biệt rõ rệt giữa thuật toán cấp đa thức ($O(1), O(\log_2 n), O(n), O(n\log_2 n), O(n^2), O(n^3)$) và thuật toán cấp hàm mũ ($O(2^n), O(n!), O(n^n)$).
  • Nguyên lý ánh xạ cấu trúc lưu trữ trong bộ nhớ: Cung cấp cơ sở giải tích để xác định địa chỉ vật lý của phần tử dữ liệu:
    • Mảng 1 chiều có địa chỉ gốc $L_0$, kích thước mỗi phần tử $\omega$ từ máy và chỉ số bắt đầu từ $b$: $$\text{LOC}(A[i]) = L_0 + \omega \times (i - b)$$
    • Ma trận 2 chiều kích thước $m \times n$ lưu theo thứ tự ưu tiên hàng: $$\text{LOC}(B[i,j]) = L_0 + [(i - 1) \times n + (j - 1)] \times \omega$$
    • Ma trận 2 chiều lưu theo thứ tự ưu tiên cột: $$\text{LOC}(B[i,j]) = L_0 + [(j - 1) \times m + (i - 1)] \times \omega$$
  • Mô hình kiểu dữ liệu trừu tượng (Abstract Data Types - ADT): Tách rời tầng khái niệm toán học và tầng cài đặt kỹ thuật, định nghĩa tập hợp giá trị cùng các phép toán nguyên tử trên danh sách, ngăn xếp, cây và đồ thị.

Kỹ năng phát triển

  • Kỹ năng kỹ thuật (Technical skills): Cài đặt giải thuật bằng các ngôn ngữ lập trình có cấu trúc (như Pascal, C/C++, C#); khai báo cấu trúc bản ghi (Record/struct), quản trị và cấp phát bộ nhớ động thông qua con trỏ (pointer, hàm new, dispose, malloc, free); thao tác an toàn trên các liên kết node (pNext, LPTR, RPTR).
  • Kỹ năng phân tích (Analytical skills): Phân tích và đánh giá ưu/nhược điểm giữa cấu trúc dữ liệu tĩnh và cấu trúc dữ liệu động; so sánh hiệu năng của giải thuật đệ quy với giải thuật lặp; nhận diện hiện tượng tràn (overflow) và cạn (underflow) ngăn xếp; phân tích chi phí thời gian và không gian bộ nhớ của các thuật toán sắp xếp và tìm kiếm.
  • Năng lực thực hành giải quyết vấn đề (Practical competencies): Xây dựng giải pháp kỹ thuật từ bài toán thực tế (ví dụ: chuyển đổi bài toán quản lý bảng điểm sinh viên $3 \times 4$ sang mô hình mảng phù hợp); thiết kế thuật toán xử lý dữ liệu theo phương pháp tinh chỉnh từng bước; lập trình kiểm nghiệm và tối ưu hóa giải thuật trên hệ thống máy tính.

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

Giáo trình Cấu trúc dữ liệu và giải thuật áp dụng phương pháp tiếp cận sư phạm định hướng thực hành kết hợp chặt chẽ với phân tích lý thuyết giải tích. Với cơ cấu thời lượng 45 tiết lý thuyết và 41 tiết thực hành, tiến trình giảng dạy được tổ chức theo phương pháp "tinh chỉnh từng bước" (stepwise refinement): xuất phát từ phân tích yêu cầu dữ liệu đầu vào (Input) và đầu ra (Output) của bài toán thực tế, mô hình hóa giải thuật bằng sơ đồ khối hoặc mã giả, sau đó tiến hành phân rã module và cụ thể hóa thành mã nguồn chương trình hoàn chỉnh.

+-----------------------------------------------------------------------------------+
|               TIẾN TRÌNH THIẾT KẾ GIẢI THUẬT THEO GIÁO TRÌNH                      |
|                                                                                   |
|  [Bài toán thực tế] ---> [Xác định Input/Output] ---> [Sơ đồ khối / Mã giả]       |
|                                                               |                   |
|                                                               v                   |
|  [Mã nguồn thực thi] <-- [Cài đặt CTDL / Con trỏ] <-- [Tinh chỉnh từng bước]     |
+-----------------------------------------------------------------------------------+

Hệ thống bài tập và nghiên cứu tình huống (case studies) trong giáo trình được xây dựng bám sát các mô hình thực tiễn và toán học kinh điển, tiêu biểu như:

  • Tình huống tổ chức dữ liệu quản lý điểm học phần của sinh viên (so sánh phương án mảng 1 chiều 12 phần tử và mảng 2 chiều kích thước $3 \times 4$);
  • Tình huống quản lý hồ sơ nhân sự bằng kiểu dữ liệu bản ghi Record (Mã nhân sự, Họ tên, Lương, Địa chỉ);
  • Mô hình bài toán cổ về đàn thỏ Fibonacci và bài toán di chuyển $n$ đĩa vàng tại đền Benares trong Tháp Hà Nội;
  • Lập bảng biến thiên trạng thái các biến $p, q, r$ trong giải thuật Euclide tìm ước số chung lớn nhất.

Về phương pháp đánh giá kết quả hoàn thành học phần, giáo trình quy định khung đánh giá định lượng tổng hợp dựa trên 3 tiêu chí với hệ số cụ thể:

Tiêu chí đánh giá Hình thức và nội dung đánh giá Trọng số hệ số
Kiến thức Đánh giá qua bài kiểm tra viết hoặc trắc nghiệm: hiểu mối quan hệ giữa cấu trúc dữ liệu và giải thuật, phân tích các kiểu dữ liệu, đánh giá độ phức tạp $O(f(n))$, nắm vững các thuật toán sắp xếp, tìm kiếm, duyệt cây, đồ thị. 0,3
Kỹ năng Đánh giá kỹ năng thực hành trên máy tính: sử dụng ngôn ngữ lập trình cụ thể để cài đặt, biên dịch và chạy đúng các bài toán về đệ quy, danh sách liên kết, ngăn xếp, cây nhị phân, đồ thị, sắp xếp và tìm kiếm. 0,5
Thái độ Đánh giá ý thức học tập: tính cẩn thận, tỉ mỉ, thao tác chuẩn xác, bảo đảm an toàn cho người và thiết bị máy tính, tinh thần tự giác trong học tập. 0,2

Đối với hoạt động tự học, giáo trình cung cấp hệ thống câu hỏi lý thuyết, bài tập lập trình kèm theo phần gợi ý làm bài chi tiết ở cuối mỗi chương, cho phép người học tự kiểm tra tính đúng đắn của giải thuật và theo dõi sự thay đổi trạng thái của dữ liệu qua từng bước thực thi.

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

  • Phân định rạch ròi giữa cấu trúc dữ liệu và cấu trúc lưu trữ: Giáo trình làm rõ ranh giới giữa mô hình dữ liệu ở mức khái niệm (kiểu dữ liệu trừu tượng) và cách thức tổ chức vật lý tương ứng trong bộ nhớ máy tính (cấu trúc lưu trữ kế tiếp trên mảng hoặc cấu trúc lưu trữ móc nối qua biến con trỏ), giúp người học hiểu rõ bản chất cấp phát tĩnh và cấp phát động.
  • Chuẩn hóa công thức giải tích tính toán địa chỉ bộ nhớ: Thay vì chỉ mô tả định tính, giáo trình cung cấp công thức toán học xác định địa chỉ chính xác của phần tử mảng một chiều, mảng hai chiều (theo thứ tự ưu tiên hàng $\text{LOC}(B[i,j]) = L_0 + [(i-1)n + (j-1)]\omega$ và thứ tự ưu tiên cột $\text{LOC}(B[i,j]) = L_0 + [(j-1)m + (i-1)]\omega$), cũng như trường hợp mảng có cận dưới chỉ số tùy ý ($b_1 \le i \le u_1, b_2 \le j \le u_2$).
  • Tích hợp lịch sử toán học và mô hình hóa thuật toán: Đưa vào giáo trình nguồn gốc lịch sử của thuật toán từ nhà toán học Abu Ja'far Mohammed ibn Musa al Khowarizmi, cùng các bài toán quy nạp kinh điển (Tháp Hà Nội, dãy số Fibonacci, thuật toán Euclide), tạo dựng nền tảng tư duy toán học cho lập trình viên.
  • Phương pháp biểu diễn đa dạng và chuẩn hóa: Cung cấp cách tiếp cận giải thuật đa tầng: từ ngôn ngữ tự nhiên, sơ đồ khối chuẩn (phân biệt thao tác chọn lựa hình thoi và thao tác xử lý hình chữ nhật), mã giả cấu trúc (đầy đủ các cấu trúc điều khiển if-then-else, case, for, while, repeat..until) đến mã nguồn cài đặt cụ thể trên ngôn ngữ lập trình có cấu trúc.
  • Xử lý các trường hợp biên và cấu trúc đặc biệt: Phân tích sâu các giải pháp kỹ thuật nhằm khắc phục hạn chế của cấu trúc dữ liệu, như việc bổ sung "nút đầu danh sách" (dummy node) để tránh chu trình vô tận trong danh sách liên kết vòng, hay xử lý các điều kiện biên Last = MaxLength (tràn mảng), T = 0 (cạn ngăn xếp).

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

  • Sinh viên chuyên ngành Công nghệ thông tin: Tài liệu được biên soạn phục vụ trực tiếp cho sinh viên trình độ đại học và cao đẳng thuộc các ngành: Khoa học máy tính, Kỹ thuật phần mềm, Công nghệ thông tin, Hệ thống thông tin, Mạng máy tính và Truyền thông dữ liệu.
  • Yêu cầu kiến thức tiên quyết (Prerequisites): Người học cần hoàn thành các học phần nền tảng:
    • Lập trình căn bản: Đã nắm vững cú pháp lập trình có cấu trúc, biến số, kiểu dữ liệu cơ sở, cấu trúc điều khiển rẽ nhánh, vòng lặp, mảng dữ liệu và xây dựng chương trình con (hàm/thủ tục);
    • Cơ sở dữ liệu: Đã có hiểu biết về tổ chức và lưu trữ dữ liệu có cấu trúc.
  • Giảng viên và cơ sở đào tạo: Giáo trình đóng vai trò là đề cương chi tiết và tài liệu giảng dạy chuẩn cho học phần Cấu trúc dữ liệu và giải thuật (MH17), cung cấp sẵn khung phân bổ giờ lý thuyết - thực hành, mục tiêu bài học, nội dung chi tiết từng chương và bảng tiêu chí đánh giá kết quả học tập định lượng.
  • Lập trình viên tự học và tham khảo học thuật: Tài liệu phù hợp cho các kỹ sư phần mềm, người tự học lập trình có nhu cầu hệ thống hóa lại kiến thức nền tảng về tổ chức dữ liệu, quản trị bộ nhớ động, cơ chế ngăn xếp, cấu trúc cây nhị phân, đồ thị và các giải thuật sắp xếp/tìm kiếm chuẩn mực.

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?

Giáo trình được thiết kế chuẩn mực cho sinh viên đại học, cao đẳng các ngành Công nghệ thông tin và Kỹ thuật phần mềm đang theo học học phần Cấu trúc dữ liệu và giải thuật (Mã học phần: MH17), cũng như lập trình viên cần tài liệu tham khảo để củng cố nền tảng giải thuật và tổ chức bộ nhớ.

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 giáo trình?

Học viên bắt buộc phải có kiến thức nền tảng từ hai môn học tiên quyết: "Lập trình căn bản" (nắm vững câu lệnh điều khiển, mảng, hàm, thủ tục và khái niệm con trỏ) và "Cơ sở dữ liệu" (hiểu về cách thức biểu diễn và lưu trữ thông tin).

3. Giáo trình Cấu trúc dữ liệu và giải thuật (MH17) có đặc điểm gì khác biệt về mặt cấu trúc?

Giáo trình phân bổ tỷ lệ cân bằng giữa lý thuyết và thực hành (45 tiết lý thuyết / 41 tiết thực hành trên tổng số 90 tiết). Nội dung trình bày chi tiết công thức giải tích tính toán địa chỉ bộ nhớ vật lý, phân định rõ giữa kiểu dữ liệu trừu tượng và cấu trúc lưu trữ, đồng thời kết hợp đa dạng các công cụ diễn đạt từ sơ đồ khối, mã giả đến mã nguồn cụ thể.

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

Học viên nên đọc kỹ phần lý thuyết khái niệm, tự vẽ lại sơ đồ khối hoặc lập bảng theo dõi biến trung gian từng bước của thuật toán (như bảng vết giá trị $p, q, r$ trong thuật toán Euclide), sau đó tự cài đặt mã nguồn trên máy tính và hoàn thành các bài tập thực hành kèm phần gợi ý giải ở cuối mỗi chương.

5. Giáo trình có cung cấp tài liệu bổ trợ và tiêu chí đánh giá kèm theo không?

Giáo trình tích hợp sẵn hệ thống bài tập thực hành ở cuối mỗi chương (có hướng dẫn và gợi ý làm bài), quy cách cấu trúc chương trình mẫu, bảng phân loại cấp độ phức tạp $O(f(n))$, và khung tiêu chuẩn đánh giá kết quả học tập với 3 trọng số rõ ràng: Kiến thức (0,3), Kỹ năng (0,5) và Thái độ (0,2).

Kết luận

Giáo trình Cấu trúc dữ liệu và giải thuật (MH17) cung cấp hệ thống kiến thức học thuật hoàn chỉnh và chuẩn mực về các cấu trúc dữ liệu từ tuyến tính đến phi tuyến, cùng các giải thuật xử lý tương ứng trên máy tính. Bằng việc làm sáng tỏ công thức $\text{Cấu trúc dữ liệu} + \text{Giải thuật} = \text{Chương trình}$, tài liệu giúp người học xây dựng tư duy phân tích độ phức tạp thuật toán và kỹ năng tối ưu hóa lưu trữ bộ nhớ. Lộ trình học tập đề xuất là tiếp cận tuần tự từ nguyên lý đánh giá thuật toán và cấu trúc lưu trữ ở Chương 1, giải thuật đệ quy ở Chương 2, các cấu trúc danh sách và ngăn xếp ở Chương 3, các thuật toán sắp xếp và tìm kiếm ở Chương 4 và 5, trước khi hoàn thiện các cấu trúc nâng cao về cây và đồ thị ở Chương 6 và 7. Để hoàn thành tốt chương trình, người học cần kết hợp việc nghiên cứu lý thuyết với thực hành lập trình trực tiếp trên các môi trường phát triển phần mềm chuẩn.