GIÁO TRÌNH CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (ThS. NGUYỄN THỊ HƯƠNG - ĐẠI HỌC THÁI NGUYÊN)

Tổng quan về giáo trình (250-300 từ)

Giáo trình Cấu trúc dữ liệu và giải thuật do ThS. Nguyễn Thị Hương biên soạn, Nhà xuất bản Khoa học và Kỹ thuật xuất bản năm 2010 (Chịu trách nhiệm xuất bản: TS. Phạm Văn Diễn; Biên tập: Minh Luận - Phương Liên; Số đăng ký KHXB: 215-2010/CXB/367-17/KHKT; Quyết định xuất bản: 119/QĐXB-NXBKHKT). Giáo trình được thiết kế phục vụ giảng dạy cho hệ đại học tại Đại học Thái Nguyên, đóng vai trò là học phần cơ sở ngành bắt buộc trong chương trình đào tạo Khoa học máy tính và Công nghệ thông tin.

Mục tiêu học tập của giáo trình là cung cấp cho người học hệ thống kiến thức nền tảng về mối quan hệ giữa cấu trúc dữ liệu và giải thuật, phương pháp phân tích bài toán, đánh giá độ phức tạp tính toán $O(g(n))$, các kỹ thuật thiết kế giải thuật (chia để trị, tinh chỉnh từng bước, đệ quy, quay lui) và cách tổ chức, cài đặt các cấu trúc dữ liệu tuyến tính cùng các giải thuật xử lý tương ứng. Đồng thời, giáo trình trang bị phương pháp luận giải quyết bài toán làm nền tảng trực tiếp để tiếp cận các học phần chuyên sâu như Chương trình dịch, Trí tuệ nhân tạo và Hệ chuyên gia.

Về cấu trúc tổng thể, giáo trình gồm 3 phần:

  • Phần 1 - Giải thuật: Giới thiệu kiến thức cơ bản về phân tích, thiết kế giải thuật và đánh giá hiệu năng.
  • Phần 2 - Cấu trúc dữ liệu: Trình bày từ mô hình trừu tượng, cấu trúc lưu trữ trong/ngoài đến các thao tác xử lý trên mảng, danh sách tuyến tính, ngăn xếp và hàng đợi.
  • Phần 3 - Sắp xếp và tìm kiếm: Phân tích và cài đặt các giải thuật sắp xếp, tìm kiếm từ cơ bản đến nâng cao.

Điểm đặc trưng trong phương pháp tiếp cận của giáo trình là sự kết hợp chặt chẽ giữa mô hình hóa giải thuật bằng ngôn ngữ tự nhiên, sơ đồ khối (lưu đồ thuật toán) và mã giả tựa Pascal (pseudocode), giúp người học nắm bắt bản chất logic trước khi chuyển đổi sang các ngôn ngữ lập trình cụ thể.

Nội dung kiến thức cốt lõi (500-600 từ)

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

Nội dung giáo trình được triển khai theo tiến trình logic chặt chẽ, từ tư duy thuật toán hình thức đến việc biểu diễn dữ liệu vật lý trong bộ nhớ:

  • Chương 1 - Mở đầu: Định nghĩa hình thức về giải thuật (dãy câu lệnh xác định thao tác trên đối tượng dữ liệu để đạt kết quả sau hữu hạn bước) và dữ liệu (nguyên tử và cấu trúc). Phân tích mối quan hệ hữu cơ: cấu trúc dữ liệu thay đổi kéo theo giải thuật thay đổi (minh họa qua bài toán tra cứu số điện thoại theo danh sách ngẫu nhiên, danh sách sắp thứ tự từ điển, và bảng chỉ dẫn theo chữ cái đầu). Trình bày các công cụ biểu diễn giải thuật: ngôn ngữ tự nhiên, lưu đồ khối (gồm 4 thành phần: nút giới hạn hình ôvan, nút thao tác hình chữ nhật, nút điều kiện hình thoi, và các cung liên kết) cùng hệ thống mã giả tựa Pascal (cấu trúc chọn if-then-else, cấu trúc lặp while-do, repeat-until, for-to/downto, lệnh nhảy goto và lệnh ngắt break).
  • Chương 2 - Phân tích và thiết kế giải thuật: Trình bày phương pháp mô đun hóa theo chiến lược "chia để trị" (divide and conquer) và thiết kế từ trên xuống (top-down design) thông qua bài toán quản lý, bảo trì hồ sơ học bổng sinh viên (chia nhỏ thành các nhiệm vụ: đọc tệp, xử lý tệp, ghi tệp; trong đó xử lý tệp gồm tìm kiếm, cập nhật, in ấn). Phân tích phương pháp tinh chỉnh từng bước (stepwise refinement) qua thuật toán sắp xếp chọn (Procedure SORT) và thuật toán in các phần tử thuộc đường chéo song song với đường chéo chính của ma trận vuông cấp $n \times n$ (Program INCHEO). Thiết lập phương pháp đánh giá thời gian thực hiện $T(n)$, độ phức tạp tính toán tiệm cận $O(g(n))$, phân tích trường hợp tốt nhất, xấu nhất, trung bình; quy tắc cộng $T_1(n) + T_2(n) = O(\max(f(n), g(n)))$, quy tắc nhân $T_1(n) \cdot T_2(n) = O(f(n) \cdot g(n))$ và khái niệm phép toán tích cực (active operation) qua việc so sánh hai thuật toán tính chuỗi $e^x \approx \sum_{i=0}^n \frac{x^i}{i!}$ (Program EXP1 có độ phức tạp bậc hai so với Program EXP2 tối ưu về bậc tuyến tính $O(n)$).
  • Chương 3 - Đệ quy và giải thuật đệ quy: Định nghĩa đệ quy trực tiếp và đệ quy gián tiếp; xác định trường hợp suy biến (base case) và cơ chế thu nhỏ kích thước bài toán qua từng mức gọi. Khảo sát các bài toán kinh điển: tính giai thừa $n!$ (Function FACTORIAL), tính số Fibonacci $F(n)$, bài toán Tháp Hà Nội (Procedure HANOI(n, B, A, C)), và bài toán 8 quân hậu (Procedure TRY(i)) kết hợp đệ quy với kỹ thuật quay lui (backtracking) trên bàn cờ $8 \times 8$ sử dụng các mảng Boolean kiểm tra an toàn: $a[i]$ (hàng), $b[i+j]$ (đường chéo thuận), $c[i-j]$ (đường chéo nghịch). Trình bày kỹ thuật khử đệ quy thành giải thuật lặp và phương pháp quy nạp toán học để chứng minh tính đúng đắn của thuật toán.
  • Chương 4 - Mảng và danh sách: Phân tích cấu trúc mảng tĩnh và cấu trúc lưu trữ kế tiếp (sequential storage allocation). Thiết lập công thức hàm địa chỉ $Loc(a_i) = L_0 + c \cdot (i - b)$ cho mảng một chiều, công thức lưu trữ ma trận theo thứ tự ưu tiên cột (column-major order trong Fortran: $Loc(a_{ij}) = L_0 + (j-1)n + (i-1)$) và theo thứ tự ưu tiên hàng (row-major order trong Pascal, ALGOL-60, PL-1: $Loc(a_{ij}) = L_0 + (i-b_1)(u_2-b_2+1) + (j-b_2)$), mở rộng cho mảng $n$ chiều. Phân tích nhược điểm lãng phí bộ nhớ của mảng khi biểu diễn đa thức bằng ma trận thưa. Cung cấp định nghĩa danh sách tuyến tính; phân tích cấu trúc Ngăn xếp (Stack - LIFO) với các thao tác Push, Pop, phương pháp xử lý tràn ngăn xếp bằng mô hình 2 stack chung vùng nhớ đối đỉnh hoặc dịch chuyển đáy cho $\ge 3$ stack. Khảo sát ứng dụng Stack: đổi cơ số thập phân sang nhị phân, định giá biểu thức tiền tố/hậu tố Ba Lan (Program DINH_GIA), và cơ chế cài đặt thủ tục đệ quy bằng Stack bản ghi (lưu biến động $N$ và địa chỉ quay lui RETADD). Phân tích cấu trúc Hàng đợi (Queue - FIFO) với hai con trỏ Front ($F$), Rear ($R$) và kỹ thuật tổ chức hàng đợi vòng tròn (Circular Queue) để khắc phục hiện tượng trôi dải nhớ.

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

  • Lý thuyết tiệm cận và phân tích thuật toán: Xây dựng định nghĩa hình thức về ký pháp Big-O ($f(n) \le c \cdot g(n)$ với mọi $n > n_0$), các cấp độ phức tạp phổ biến ($\log_2 n, n, n\log_2 n, n^2, n^3, 2^n, n!, n^n$), và kỹ thuật đếm phép toán tích cực để đánh giá hiệu năng độc lập với phần cứng.
  • Nguyên lý thiết kế giải thuật có cấu trúc: Xây dựng phương pháp tư duy phân rã bài toán từ trên xuống (Top-down design), chuyển đổi mức trừu tượng từ "làm cái gì" sang "làm như thế nào" qua từng bước tinh chỉnh (Stepwise refinement), và nguyên lý vét cạn có định hướng thông qua quay lui.
  • Nguyên lý tổ chức dữ liệu logic và lưu trữ vật lý: Phân định rõ ràng giữa cấu trúc dữ liệu trừu tượng (mảng, danh sách tuyến tính, LIFO, FIFO) và cách ánh xạ cụ thể vào các ô nhớ kế tiếp trong bộ nhớ trong (RAM) hoặc thiết bị lưu trữ ngoài (tệp bản ghi).

Kỹ năng phát triển

  • Kỹ năng kỹ thuật (Technical skills): Viết và chuyển đổi thành thạo mã giả tựa Pascal sang các ngôn ngữ lập trình cấu trúc; tính toán chính xác địa chỉ ô nhớ của mảng đa chiều; tự cài đặt các cấu trúc Stack và Queue bằng mảng một chiều hoặc cơ chế con trỏ vòng tròn.
  • Kỹ năng phân tích (Analytical skills): Phân tích, xác định phép toán tích cực của giải thuật để thiết lập hàm thời gian $T(n)$; nhận diện bài toán có cấu trúc đệ quy, chỉ ra trường hợp suy biến và phân tích cây đệ quy; đánh giá ưu/nhược điểm giữa cấu trúc lưu trữ kế tiếp và lưu trữ động.
  • Kỹ năng thực hành (Practical competencies): Khử đệ quy thủ công bằng cách sử dụng Stack lưu vết trạng thái; hiện thực hóa các giải thuật xử lý chuỗi ký pháp Ba Lan (tiền tố, hậu tố); tối ưu hóa thuật toán lặp để giảm độ phức tạp tính toán (như bài toán tính chuỗi số mũ $e^x$).

Phương pháp giảng dạy và học tập (300-350 từ)

Phương pháp tiếp cận sư phạm

Giáo trình triển khai phương pháp tiếp cận sư phạm đi từ trực quan đến hình thức hóa toán học và cài đặt chương trình. Mỗi chủ đề được xây dựng theo quy trình 4 giai đoạn chuẩn:

  1. Đặt vấn đề từ các bài toán thực tiễn hoặc toán học kinh điển.
  2. Trình bày tư tưởng giải thuật bằng ngôn ngữ tự nhiên và mô hình hóa trực quan qua lưu đồ khối (hệ thống nút ôvan, chữ nhật, thoi và cung nối).
  3. Hình thức hóa thành mã giả cấu trúc tựa Pascal thông qua phương pháp tinh chỉnh từng bước.
  4. Cài đặt chi tiết thành chương trình hoàn chỉnh, phân tích cấu trúc bộ nhớ và đánh giá độ phức tạp thuật toán.

Bài tập và Case studies điển hình

Giáo trình sử dụng hệ thống case study mẫu mực, có tính thực tiễn và tính học thuật cao:

  • Case study Quản lý tệp: Bài toán quản lý học bổng sinh viên minh họa phương pháp phân rã mô đun hóa (đọc tệp, xử lý cập nhật/tìm kiếm/báo cáo, ghi tệp đĩa).
  • Case study Tối ưu hóa: Bài toán tính giá trị $e^x$ đối chiếu trực tiếp giữa Program EXP1 (tính lại giai thừa từng bước gây lãng phí tính toán) và Program EXP2 (kế thừa kết quả số hạng trước đó: $x^n/n! = x^{n-1}/(n-1)! \cdot x/n$), chứng minh trực quan sự chênh lệch giữa $O(n^2)$ và $O(n)$.
  • Case study Quay lui - Đệ quy: Bài toán xếp 8 quân hậu trên bàn cờ $8 \times 8$ (Program EIGHT-QUEEN), mô tả chi tiết quá trình thử, kiểm tra điều kiện an toàn $a[i] \land b[i+j] \land c[i-j]$, ghi nhận lời giải và phục hồi trạng thái (backtrack).
  • Case study Xử lý biểu thức: Bài toán định giá biểu thức hậu tố Ba Lan (Program DINH_GIA), mô tả cơ chế đọc toán hạng đẩy vào Stack và rút toán hạng khi gặp toán tử.

Phương pháp kiểm tra đánh giá và hướng dẫn tự học

  • Đánh giá năng lực: Đo lường qua khả năng vẽ lưu đồ thuật toán, truy vết biến (trace code) qua bảng trạng thái bộ nhớ, chứng minh thuật toán đệ quy bằng quy nạp toán học, và tính toán độ phức tạp $O(g(n))$.
  • Hướng dẫn tự học: Người học tự đọc theo trình tự tinh chỉnh từng bước; sau khi hiểu mã giả, cần tự cài đặt trên máy tính bằng một ngôn ngữ lập trình cụ thể; thực hành vẽ sơ đồ phân cấp mô đun và tự triển khai thủ tục khử đệ quy cho các bài toán kinh điển (như tính $n!$, Fibonacci, Tháp Hà Nội).

Điểm nổi bật và cập nhật (250-300 từ)

Giáo trình thể hiện rõ nét tính chuẩn mực học thuật của chương trình đào tạo đại học kỹ thuật giai đoạn 2010 với các đặc điểm nổi bật:

  • Tính chuẩn hóa trong mô hình hóa dữ liệu: Giáo trình đối chiếu chi tiết khả năng mô phỏng dữ liệu giữa các ngôn ngữ lập trình khác nhau. Điển hình là việc so sánh kiểu bản ghi (record) trong Pascal cho phép tổ chức dữ liệu không đồng nhất (như hồ sơ cán bộ/sinh viên) với sự hạn chế của Fortran (chỉ dùng vector/ma trận), từ đó làm rõ yêu cầu cần thiết của việc xây dựng cấu trúc dữ liệu mới cho các bài toán phi số (non-numerical problems).
  • Công thức hóa tường minh việc cấp phát bộ nhớ: Khác với các tài liệu chỉ mô tả logic, giáo trình cung cấp hệ thống công thức toán học chính xác để tính toán địa chỉ bộ nhớ vật lý $Loc(a_{ij})$ theo cả thứ tự ưu tiên hàng (Row-major trong Pascal, ALGOL-60, PL-1) và ưu tiên cột (Column-major trong Fortran), kèm công thức tổng quát mở rộng cho mảng $n$ chiều với cận dưới $b_i$ tùy ý.
  • Giải pháp cơ chế bộ nhớ cụ thể: Giáo trình giải quyết triệt để các bài toán kỹ thuật biên dịch và quản lý bộ nhớ:
    • Hiện tượng tràn ngăn xếp cục bộ: Đưa ra giải pháp chia sẻ bộ nhớ cho 2 stack phát triển ngược chiều nhau từ 2 đầu vector, và kỹ thuật dồn dịch đáy cho $\ge 3$ stack.
    • Hiện tượng tràn hàng đợi: Đưa ra giải pháp hàng đợi vòng tròn (Circular Queue kết nối $Q[1]$ liền sau $Q[n]$).
    • Biểu diễn ma trận thưa: Phân tích sự lãng phí tài nguyên của mảng tĩnh khi biểu diễn đa thức bậc cao.
  • Cơ sở cho kỹ thuật phần mềm nâng cao: Cung cấp mô hình chi tiết về cách bộ nhớ Stack của hệ điều hành quản lý lời gọi đệ quy (lưu tham số, biến cục bộ, địa chỉ quay lui RETADD), tạo nền tảng vững chắc cho sinh viên khi học môn Chương trình dịch và Trí tuệ nhân tạo.

Đối tượng sử dụng giáo trình (200-250 từ)

  • Sinh viên đại học: Tài liệu học tập bắt buộc dành cho sinh viên năm thứ nhất và năm thứ hai các ngành Khoa học máy tính, Công nghệ thông tin, Kỹ thuật phần mềm, Hệ thống thông tin và Sư phạm Tin học.
  • Điều kiện tiên quyết (Prerequisites):
    • Đã học xong học phần Cơ sở lập trình / Nhập môn lập trình (nắm vững cú pháp cơ bản, các cấu trúc điều khiển rẽ nhánh, vòng lặp, mảng, hàm, thủ tục và khái niệm con trỏ).
    • Có kiến thức nền tảng về Toán rời rạc (phương pháp quy nạp toán học, đại số logic Boolean, lý thuyết đồ thị cơ bản) và Giải tích (khái niệm giới hạn, hàm số để phân tích tiệm cận).
  • Giảng viên đại học và cao đẳng: Sử dụng làm tài liệu chuẩn để biên soạn đề cương bài giảng, thiết kế bài tập lớn, ra đề thi kết thúc học phần và hướng dẫn thực hành giải thuật.
  • Người tự học và nghiên cứu: Phù hợp cho lập trình viên muốn củng cố bản chất toán học của thuật toán, cơ chế cấp phát bộ nhớ máy tính, và sinh viên chuẩn bị học các môn nâng cao như Trí tuệ nhân tạo, Hệ chuyên gia và Xây dựng trình biên dịch.

Câu hỏi thường gặp (250-300 từ)

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

Giáo trình được thiết kế chuẩn cho sinh viên đại học khối ngành Công nghệ thông tin và Khoa học máy tính, cũng như người học cần nắm vững bản chất tổ chức dữ liệu và phân tích hiệu năng thuật toán.

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

Người học cần có kiến thức cơ bản về lập trình cấu trúc (đặc biệt là cú pháp tựa Pascal hoặc C), hiểu các cấu trúc điều khiển (lặp, rẽ nhánh), kiểu dữ liệu mảng, bản ghi (record) và phương pháp chứng minh quy nạp toán học.

3. Giáo trình sử dụng ngôn ngữ nào để mô tả giải thuật?

Giáo trình sử dụng phối hợp ngôn ngữ tự nhiên, sơ đồ khối (lưu đồ 4 thành phần chuẩn) và mã giả tựa Pascal. Cách tiếp cận này giúp diễn đạt trong sáng logic thuật toán mà không bị ràng buộc vào các chi tiết cú pháp phức tạp của một ngôn ngữ cụ thể.

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

Người học nên tuân thủ phương pháp tinh chỉnh từng bước: phân tích bài toán -> đọc hiểu mã giả -> vẽ bảng truy vết giá trị biến và trạng thái bộ nhớ -> tự cài đặt lại bằng ngôn ngữ lập trình cụ thể (Pascal, C/C++) -> thực hiện bài toán khử đệ quy bằng Stack.

5. Có những case study thực tế nào được phân tích chi tiết trong sách?

Giáo trình phân tích sâu các bài toán: thiết kế hệ thống quản lý hồ sơ học bổng sinh viên (Top-down), tối ưu hóa thuật toán tính $e^x$, thuật toán in đường chéo ma trận, đổi cơ số sang nhị phân, định giá biểu thức hậu tố Ba Lan, bài toán Tháp Hà Nội và bài toán xếp 8 quân hậu bằng kỹ thuật quay lui.

Kết luận (150 từ)

Giáo trình Cấu trúc dữ liệu và giải thuật của ThS. Nguyễn Thị Hương (Đại học Thái Nguyên - NXB Khoa học và Kỹ thuật) là tài liệu học thuật chuẩn mực, cung cấp bức tranh toàn diện về mối quan hệ giữa giải thuật và tổ chức dữ liệu. Giá trị cốt lõi của giáo trình nằm ở phương pháp luận thiết kế giải thuật có cấu trúc (Top-down, Stepwise Refinement), lý thuyết đánh giá tiệm cận $O(g(n))$, và kỹ thuật ánh xạ chi tiết cấu trúc dữ liệu tuyến tính vào bộ nhớ máy tính.

Lộ trình học tập đề xuất:

  1. Làm chủ khái niệm cơ bản, công cụ mã giả và kỹ thuật đánh giá $O(g(n))$ (Chương 1, 2).
  2. Rèn luyện tư duy đệ quy, kỹ thuật quay lui và khử đệ quy (Chương 3).
  3. Nắm vững cấu trúc mảng, danh sách tuyến tính, cơ chế ngăn xếp (LIFO), hàng đợi (FIFO) và ứng dụng thực tiễn (Chương 4).
  4. Nghiên cứu các cấu trúc phi tuyến và giải thuật sắp xếp, tìm kiếm nâng cao (Phần 3).

Tài liệu bổ trợ khuyến nghị: Người học nên kết hợp môi trường dịch mã nguồn (như Free Pascal, Dev-C++, GCC) để thực thi các giải thuật mẫu và tham khảo thêm tài liệu về Lý thuyết ngôn ngữ & Trình biên dịch cùng Trí tuệ nhân tạo cơ sở để mở rộng phạm vi ứng dụng.