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

Giáo trình "Cấu trúc Dữ liệu và Giải thuật" (Lưu hành nội bộ) do ThS. Hoàng Thế Phương làm chủ biên, được biên soạn và phát hành năm 2019 tại Trường Đại học Công nghệ Giao thông Vận tải (Hà Nội). Trong chương trình đào tạo kỹ sư và cử nhân thuộc khối ngành Công nghệ thông tin, môn học Cấu trúc dữ liệu và Giải thuật giữ vị trí học phần cơ sở ngành bắt buộc, đóng vai trò nền tảng cho các học phần chuyên sâu về phát triển phần mềm, cơ sở dữ liệu và tối ưu hóa hệ thống.

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 lý thuyết về phương pháp phân tích, thiết kế giải thuật; đo lường và đánh giá hiệu năng thuật toán thông qua độ phức tạp thời gian; đồng thời cung cấp kiến thức toàn diện về các cấu trúc dữ liệu từ tuyến tính đến phi tuyến. Về mặt cấu trúc, tài liệu sử dụng phương pháp tiếp cận hai tầng: tầng thứ nhất sử dụng ngôn ngữ trừu tượng (ngôn ngữ tựa Pascal) để diễn đạt tư duy thuật toán và phương pháp luận thiết kế; tầng thứ hai sử dụng ngôn ngữ lập trình C (trên môi trường Turbo C) để cài đặt cụ thể các cấu trúc lưu trữ và giải thuật xử lý dữ liệu. Điểm đặc sắc của giáo trình là sự phân định rõ ràng giữa cấu trúc dữ liệu logic (dữ liệu nguyên tử, mối liên kết logic) và cấu trúc lưu trữ vật lý trong bộ nhớ (bộ nhớ trong, bộ nhớ ngoài), đồng thời chứng minh mối quan hệ hữu cơ không thể tách rời giữa cấu trúc dữ liệu và giải thuật.

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 tổ chức tuần tự theo các khối kiến thức từ cơ sở cú pháp, phương pháp luận giải thuật đến các cấu trúc dữ liệu cụ thể và thuật toán xử lý:

  • Chương 1: Các khái niệm cơ bản: Thiết lập nền tảng cú pháp của ngôn ngữ C (tập ký tự, 32 từ khóa Turbo C, quy tắc định danh không quá 32 ký tự, hệ thống kiểu dữ liệu nguyên thủy, các loại hằng số, biến và toán tử lấy địa chỉ &). Trình bày bản chất của giải thuật và cấu trúc dữ liệu; phân tích khái niệm dữ liệu nguyên tử (atoms), cấu trúc lưu trữ trong và ngoài. Giới thiệu ngôn ngữ tựa Pascal làm công cụ mô tả thuật toán; phương pháp thiết kế phân rã mô-đun "từ đỉnh xuống" (top-down / chia để trị) và kỹ thuật tinh chỉnh từng bước (stepwise refinement). Đưa ra phương pháp phân tích độ phức tạp thời gian $T(n)$ qua ký pháp Big-O, quy tắc tổng, quy tắc nhân, phân loại hàm đa thức và hàm mũ, cùng việc xác định thời gian thực hiện trong trường hợp thuận lợi nhất ($T_{\text{tốt}}$) và xấu nhất ($T_{\text{xấu}}$).
  • Chương 2: Các thành phần cơ bản và cấu trúc điều khiển chương trình: Khảo sát chi tiết các cơ chế vào/ra dữ liệu chuẩn trong C bao gồm các hàm ký tự (getchar(), putchar(), getch(), putch()), hàm xuất định dạng printf() với cấu trúc đặc tả %[-][fw][.pp]ký_tự, và hàm nhập dữ liệu scanf() đi kèm các kỹ thuật quét trường [...] và loại trừ [^...]. Định nghĩa biểu thức gán, biểu thức điều kiện và các toán tử số học hai ngôi.
  • Hàm và Con trỏ: Phân tích cơ chế tổ chức chương trình con, nguyên lý truyền tham số khi gọi hàm; bản chất địa chỉ ô nhớ và con trỏ; mối tương quan giữa con trỏ với mảng một chiều, mảng nhiều chiều; các phép toán số học trên con trỏ; cấu trúc mảng con trỏ và con trỏ trỏ tới hàm.
  • Cấu trúc dữ liệu tuyến tính và phi tuyến: Định nghĩa và cài đặt cấu trúc lưu trữ mảng, danh sách tuyến tính; cấu trúc dữ liệu Ngăn xếp (Stack) cùng các ứng dụng lưu trữ; cấu trúc Hàng đợi (Queue); các mô hình dữ liệu dạng Cây (Cây nhị phân, Cây tổng quát); mô hình Đồ thị và các phép toán duyệt đồ thị.
  • Giải thuật Sắp xếp và Tìm kiếm: Hệ thống hóa các thuật toán sắp xếp nội bao gồm sắp xếp chọn trực tiếp (Selection Sort), sắp xếp chèn trực tiếp (Insertion Sort), sắp xếp đổi chỗ trực tiếp (Bubble/Exchange Sort), sắp xếp trộn (Merge Sort); các bài toán tìm kiếm cơ bản gồm tìm kiếm tuần tự (Sequential Search) và tìm kiếm nhị phân (Binary Search).

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

Giáo trình xây dựng ba trục kiến thức lý thuyết cơ sở:

  1. Lý thuyết phân tích hiệu năng tiệm cận: Đánh giá sự biến thiên của hàm thời gian $T(n)$ theo kích thước dữ liệu vào $n$, chuẩn hóa việc nhận diện phép toán tích cực trong các cấu trúc lặp và rẽ nhánh.
  2. Mô hình hóa dữ liệu trừu tượng: Phân biệt giữa dữ liệu nguyên tử (atoms) và các cấu trúc dữ liệu phức hợp; giữa cấu trúc logic và cấu trúc lưu trữ vật lý tương ứng trên bộ nhớ máy tính.
  3. Kỹ thuật thiết kế phần mềm có cấu trúc: Phương pháp luận phân chia bài toán lớn thành hệ thống mô-đun phân cấp thông qua chiến lược "chia để trị", kiểm soát quá trình chuyển đổi từ ngôn ngữ tự nhiên sang giả mã rồi đến mã nguồn thực thi.

Kỹ năng phát triển

  • Kỹ năng kỹ thuật: Khả năng thao tác với các kiểu dữ liệu cơ sở và dẫn xuất trong ngôn ngữ C (xử lý con trỏ, tính toán địa chỉ, định dạng luồng vào/ra, kiểm soát bộ đệm bàn phím).
  • Kỹ năng phân tích thuật toán: Đánh giá độ phức tạp thuật toán qua các hàm $O(1), O(n), O(n^2), O(n\log_2 n)$; nhận diện trường hợp biên tốt nhất và xấu nhất trong các bài toán tìm kiếm và xử lý mảng.
  • Kỹ năng thiết kế và cài đặt: Hiện thực hóa các cấu trúc dữ liệu động (danh sách, ngăn xếp, hàng đợi, cây) và áp dụng các giải thuật sắp xếp/tìm kiếm phù hợp cho từng cấu trúc dữ liệu cụ thể.

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

Giáo trình triển khai phương pháp sư phạm tiếp cận theo tiến trình: Khái niệm logic $\rightarrow$ Đặc tả giả mã $\rightarrow$ Tinh chỉnh từng bước $\rightarrow$ Cài đặt mã nguồn C.

Trong quá trình trình bày, giáo trình lồng ghép các ca nghiên cứu và ví dụ minh họa cụ thể để làm sáng tỏ lý thuyết:

  • Bài toán tra cứu danh mục điện thoại: Minh họa mối quan hệ giữa cách tổ chức dữ liệu (danh sách ngẫu nhiên, danh sách sắp xếp thứ tự từ điển, danh sách có bảng mục lục theo chữ cái đầu) với độ hiệu quả của giải thuật tìm kiếm tương ứng.
  • Bài toán quản lý hồ sơ sinh viên nhận học bổng: Minh họa phương pháp thiết kế từ đỉnh xuống (top-down) bằng cách phân rã hệ thống thành ba nhiệm vụ chính (đọc tệp, xử lý tệp [tìm kiếm, cập nhật, in ấn], ghi tệp) và tiếp tục phân rã thành các chương trình con cấp dưới.
  • Bài toán tính giá trị hàm $e^x$ theo công thức chuỗi gần đúng: So sánh hai phương án cài đặt thuật toán EXP1 ($T(n) = O(n^2)$ do tính lại từng số hạng) và EXP2 ($T(n) = O(n)$ do tận dụng số hạng trước đó) nhằm làm rõ khái niệm phép toán tích cực và tối ưu hóa thời gian chạy.
  • Bài toán sắp xếp SORT và tìm kiếm SEARCH: Trình bày từng bước tinh chỉnh từ mô tả ngôn ngữ tự nhiên sang cấu trúc biến chỉ số, biến đổi thành thủ tục SORT(A, n) và phân tích trường hợp $T_{\text{tốt}} = O(1)$, $T_{\text{xấu}} = O(n)$ của thuật toán SEARCH.

Phương pháp đánh giá học tập dựa trên khả năng phân tích độ phức tạp của bài toán và kết quả thực thi chương trình trên máy tính. Người học được hướng dẫn phương pháp tự học thông qua việc theo dõi từng bước biến đổi trạng thái của biến, viết thử nghiệm các khối lệnh rẽ nhánh và vòng lặp, kiểm thử các trường hợp dữ liệu biên trên môi trường Turbo C.

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

  • Chuẩn hóa hệ thống diễn đạt giải thuật bằng ngôn ngữ tựa Pascal: Việc đưa ra hệ thống quy tắc cú pháp cho ngôn ngữ tựa Pascal (câu lệnh gán :=, khối lệnh begin...end, câu lệnh tuyển case...else...end case, vòng lặp for...to/downto, hàm function, thủ tục procedure) giúp người học tập trung nắm bắt bản chất của giải thuật mà không bị chi phối bởi các ràng buộc cú pháp nghiêm ngặt của ngôn ngữ lập trình bậc cao.
  • Chi tiết hóa các thông số kỹ thuật phần cứng và bộ nhớ trong ngôn ngữ C: Giáo trình cung cấp bảng phân loại kích thước bộ nhớ và miền giá trị chính xác của các kiểu dữ liệu trên kiến trúc 16-bit (Turbo C): kiểu char (1 byte, gồm signed char từ -128 đến 127 và unsigned char từ 0 đến 255; 3 nhóm ký tự ASCII), kiểu số nguyên (int 2 byte, unsigned int 2 byte, long 4 byte, unsigned long 4 byte), kiểu dấu phẩy động (float 4 byte, double 8 byte, long double 10 byte).
  • Quy chuẩn hóa cấu trúc định dạng vào/ra: Cung cấp hướng dẫn chuyên sâu về cơ chế điều khiển của printf và scanf, bao gồm cách thiết lập độ rộng hiển thị (fw), độ chính xác thập phân (pp), căn lề trái dấu trừ (-), điền số 0 (08), và kỹ thuật quét tập ký tự scanf("%[0123456789]%[^0123456789]...").

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

  • Sinh viên đại học chính quy: Sinh viên năm thứ nhất và năm thứ hai các ngành Công nghệ thông tin, Hệ thống thông tin, Kỹ thuật phần mềm và Mạng máy tính tại Trường Đại học Công nghệ Giao thông Vận tải và các cơ sở đào tạo kỹ thuật tương đương.
  • Điều kiện tiên quyết: Người học cần có kiến thức cơ sở về Toán rời rạc (logic mệnh đề, tập hợp, đồ thị cơ bản) và đã hoàn thành học phần Nhập môn tin học hoặc Lập trình cơ bản.
  • Giảng viên giảng dạy: Sử dụng làm giáo trình chính khóa để xây dựng đề cương bài giảng, thiết kế ngân hàng bài tập thực hành phòng máy và làm căn cứ xây dựng đề thi kết thúc học phần.
  • Người tự học và nghiên cứu: Lập trình viên cần hệ thống hóa kiến thức nền tảng về tổ chức cấu trúc dữ liệu nội vi và phương pháp đánh giá hiệu năng giải thuật độc lập với nền tảng phần cứng.

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

1. Giáo trình này phù hợp với đối tượng nào trong chương trình đào tạo?
Giáo trình được thiết kế chuẩn hóa cho sinh viên đại học khối ngành công nghệ thông tin và kỹ thuật, phục vụ học phần Cấu trúc dữ liệu và Giải thuật ở giai đoạn kiến thức cơ sở ngà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 tài liệu?
Người học cần nắm vững tư duy logic toán học, các khái niệm cơ bản về lập trình (biến, kiểu dữ liệu, biểu thức, cấu trúc rẽ nhánh, vòng lặp) và cú pháp cơ sở của ngôn ngữ C.

3. Điểm đặc trưng trong phương pháp trình bày của giáo trình là gì?
Giáo trình sử dụng song song ngôn ngữ tựa Pascal (mã giả) để mô tả thuật toán độc lập với cú pháp máy tính, sau đó áp dụng phương pháp tinh chỉnh từng bước để chuyển đổi hoàn chỉnh sang mã nguồn ngôn ngữ C.

4. Giáo trình hướng dẫn đánh giá độ phức tạp của giải thuật như thế nào?
Tài liệu sử dụng ký pháp tiệm cận Big-O, hướng dẫn xác định phép toán tích cực trong thuật toán và áp dụng các quy tắc cộng, quy tắc nhân để tính toán thời gian chạy $T(n)$ trong các trường hợp tốt nhất, trung bình và xấu nhất.

5. Các ví dụ mã nguồn trong giáo trình được cài đặt trên môi trường nào?
Các đoạn mã minh họa cú pháp và hàm vào/ra được chuẩn hóa theo trình biên dịch Turbo C, với bảng từ khóa gồm 32 từ chuẩn và các quy tắc quản lý bộ nhớ 16-bit.

Kết luận

Giáo trình "Cấu trúc Dữ liệu và Giải thuật" của ThS. Hoàng Thế Phương cung cấp một khung lý thuyết hoàn chỉnh và phương pháp luận chặt chẽ về cách thức tổ chức dữ liệu và thiết kế giải thuật xử lý trên máy tính. Lộ trình tiếp cận kiến thức đi từ cơ sở cú pháp ngôn ngữ C, công cụ toán học phân tích độ phức tạp, qua các kỹ thuật thiết kế mô-đun phân cấp, đến việc cài đặt cụ thể các cấu trúc dữ liệu kinh điển (danh sách, ngăn xếp, hàng đợi, cây, đồ thị) và các thuật toán sắp xếp, tìm kiếm. Đây là tài liệu học tập chuẩn mực phục vụ đào tạo nội bộ và tham khảo chuyên môn trong lĩnh vực khoa học máy tính.