Báo cáo Phân tích và Mô tả Thư mục Học thuật: Giáo trình Cấu trúc Dữ liệu (Đại học Cần Thơ)

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

Giáo trình Cấu trúc Dữ liệu do tập thể giảng viên Khoa Công nghệ Thông tin – Trường Đại học Cần Thơ biên soạn (gồm Trần Cao Đệ, Nguyễn Văn Linh, Trương Thị Thanh Tuyền, Lâm Hoài Bảo, Phan Huy Cường, Trần Ngân Bình; hoàn thành tháng 12 năm 2003). Tài liệu được xây dựng nhằm phục vụ giảng dạy môn học Cấu trúc Dữ liệu – một học phần cơ sở ngành thuộc khối kiến thức bắt buộc đối với sinh viên chuyên ngành Tin học, Toán tin, Lý tin và là học phần tự chọn đối với các ngành Điện tử - Viễn thông và Tự động hóa.

Mục tiêu học tập của giáo trình được thiết lập xoay quanh việc cung cấp nền tảng lý thuyết về kiểu dữ liệu trừu tượng (Abstract Data Type - ADT) và các thao tác toán học trên từng mô hình dữ liệu. Sau khi hoàn thành học phần, người học được yêu cầu nắm vững sự phân biệt giữa kiểu dữ liệu, cấu trúc dữ liệu và kiểu dữ liệu trừu tượng; thực hiện cài đặt hoàn chỉnh các cấu trúc dữ liệu cơ bản (danh sách, ngăn xếp, hàng đợi, cây, tập hợp, bảng băm, đồ thị) bằng một ngôn ngữ lập trình cụ thể; đồng thời vận dụng các mô hình này để giải quyết các bài toán ứng dụng trong thực tế.

Cấu trúc giáo trình bao gồm 5 chương lý thuyết và bài tập với tổng thời lượng 60 tiết trên lớp. Cách tiếp cận sư phạm đi theo trình tự logic chặt chẽ: xuất phát từ việc phân tích và mô hình hóa bài toán thực tế, xác lập giải thuật không hình thức, chuyển giao qua ngôn ngữ giả (pseudo-code) cùng kỹ thuật tinh chế từng bước (stepwise refinement), định nghĩa kiểu dữ liệu trừu tượng và cuối cùng là cài đặt chi tiết trên ngôn ngữ lập trình C. Điểm đặc thù của tài liệu là sự kế thừa trực tiếp từ khung chương trình chuẩn quốc tế trong công trình Data Structures and Algorithms của Alfred V. Aho, John E. Hopcroft và Jeffrey D. Ullman (Addison-Wesley, 1983/1987), kết hợp với kinh nghiệm giảng dạy thực tiễn của đội ngũ tác giả.

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

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

Giáo trình triển khai hệ thống kiến thức qua 5 chương trọng tâm:

  1. Chương I: Mở đầu (Từ bài toán đến chương trình & Kiểu dữ liệu trừu tượng): Trình bày chu trình chuyển hóa từ bài toán thực tế sang chương trình thông qua mô hình toán học (ví dụ: bài toán tô màu bản đồ, bài toán điều khiển tín hiệu đèn giao thông ngã năm mô hình hóa thành bài toán tô màu đồ thị). Trình bày định nghĩa giải thuật theo Donald E. Knuth (1973) cùng 3 thuộc tính cơ bản: tính hữu hạn (finiteness), tính xác định (definiteness), tính hiệu quả (effectiveness). Giới thiệu giải thuật Heuristic tham lam (Greedy), phương pháp tinh chế từng bước và phân định ranh giới giữa ba khái niệm: Kiểu dữ liệu (Data Type), Cấu trúc dữ liệu (Data Structure) và Kiểu dữ liệu trừu tượng (ADT).
  2. Chương II: Các kiểu dữ liệu trừu tượng cơ bản:
    • Danh sách (List): Định nghĩa toán học, các phép toán nguyên thủy (INSERT_LIST, LOCATE, DELETE_LIST, NEXT, PREVIOUS, FIRST, EMPTY_LIST, MAKENULL_LIST, RETRIEVE). Các phương pháp cài đặt danh sách: mảng tĩnh (danh sách đặc), con trỏ (danh sách liên kết đơn có nút Header) và con nháy (cursor-based implementation trong không gian mảng SPACE với danh sách quản lý ô trống AVAILABLE). Giới thiệu cấu trúc danh sách liên kết kép (Double-lists).
    • Ngăn xếp (Stack): Cơ chế vào sau - ra trước (LIFO/FILO), thao tác tại đỉnh TOP (MAKENULL_STACK, TOP, POP, PUSH, EMPTY_STACK, FULL_STACK). Kỹ thuật cài đặt bằng danh sách, bằng mảng (chỉ số TOP_IDX) và con trỏ. Ứng dụng ngăn xếp để loại bỏ đệ quy (khử đệ quy bài toán Tháp Hà Nội thông qua mẩu tin hoạt động - activation record).
    • Hàng đợi (Queue): Khái niệm, các phép toán cơ bản, phương pháp cài đặt và ứng dụng.
  3. Chương III: Cấu trúc cây (Trees): Thuật ngữ cây tổng quát, cây có nhãn, cây biểu thức và các thứ tự duyệt cây. Phương pháp cài đặt cây bằng mảng, danh sách các con, biểu diễn theo quy tắc "con trái nhất và anh em ruột phải" (left-child right-sibling) và cài đặt bằng con trỏ. Nghiên cứu cây nhị phân (Binary Trees), giải thuật duyệt cây, ứng dụng xây dựng cây mã hóa Huffman và cấu trúc Cây tìm kiếm nhị phân (Binary Search Trees - BST).
  4. Chương IV: Tập hợp (Sets): Kiểu dữ liệu trừu tượng tập hợp; các kỹ thuật cài đặt bằng vector Bit, danh sách liên kết có thứ tự và không thứ tự. Cấu trúc dữ liệu Từ điển (Dictionary) với bộ ba phép toán Thêm, Xóa, Tìm kiếm; kỹ thuật cài đặt từ điển bằng mảng, bảng băm (Hash Table), các phương pháp xây dựng hàm băm và giải quyết đụng độ. Khái niệm và kỹ thuật cài đặt Hàng ưu tiên (Priority Queue).
  5. Chương V: Đồ thị (Graphs): Mô hình ADT Đồ thị, phương pháp biểu diễn bằng ma trận kề (Adjacency Matrix) và danh sách đỉnh kề (Adjacency List). Các giải thuật duyệt đồ thị: duyệt theo chiều sâu (Depth-First Search - DFS) và duyệt theo chiều rộng (Breadth-First Search - BFS). Các bài toán tối ưu trên đồ thị: tìm đường đi ngắn nhất từ một đỉnh (Single-source shortest path), tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh, bao đóng chuyển tiếp (Transitive closure) và tìm cây bao trùm tối thiểu (Minimum-cost spanning tree).

Progression logic của giáo trình đi tuyến tính từ các khái niệm cơ bản về lập trình cấu trúc và kiểu dữ liệu đơn lẻ, phát triển lên các cấu trúc dữ liệu tuyến tính (List, Stack, Queue), mở rộng sang cấu trúc phi tuyến tính có phân cấp (Tree), cấu trúc tập hợp/tra cứu nhanh (Set, Hash Table) và kết thúc ở cấu trúc mạng lưới quan hệ phức hợp (Graph).

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

  • Trừu tượng hóa dữ liệu và chương trình: Đóng gói các chi tiết cài đặt ở cấp độ thấp, cho phép mô tả thuật toán độc lập với ngôn ngữ lập trình.
  • Lý thuyết giải thuật: Các tiêu chuẩn chính xác hóa thuật toán theo Knuth, kỹ thuật Heuristic tiếp cận lời giải chấp nhận được cho các bài toán tối ưu tổ hợp.
  • Mô hình ánh xạ bộ nhớ vật lý: Cơ chế phân bổ bộ nhớ động (malloc/free), kỹ thuật quản lý con trỏ, tổ chức bộ nhớ ngăn xếp phục vụ lời gọi hàm và quản lý biến cục bộ trong giải thuật đệ quy.

Kỹ năng phát triển

  • Kỹ năng kỹ thuật (Technical skills): Cài đặt và quản trị các cấu trúc dữ liệu phức tạp bằng ngôn ngữ C; thao tác trực tiếp trên con trỏ, danh sách liên kết động, cấu trúc mảng và cấu trúc bản ghi (struct).
  • Kỹ năng phân tích (Analytical skills): Khả năng mô hình hóa bài toán thực tế thành bài toán đồ thị, tập hợp hoặc cây; đánh giá và lựa chọn cấu trúc dữ liệu phù hợp với yêu cầu về thời gian và không gian bộ nhớ của từng ứng dụng.
  • Năng lực thực hành (Practical competencies): Khử đệ quy bằng ngăn xếp thủ công; xây dựng bảng băm cho bài toán từ điển; cài đặt các giải thuật duyệt và tìm kiếm đường đi tối ưu trên đồ thị.

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

Giáo trình được thiết kế cho khung thời lượng 60 tiết học trên lớp, bao gồm 40 tiết giảng dạy lý thuyết và 20 tiết thảo luận, bài tập có hướng dẫn của giảng viên. Cấu trúc học phần còn đi kèm một tài liệu thực hành cấu trúc dữ liệu riêng biệt để tổ chức các giờ học tại phòng máy tính.

Phương pháp sư phạm cốt lõi được áp dụng là phương pháp tinh chế từng bước:

  1. Xác định bài toán và hình thức hóa bài toán thực tế thành mô hình toán học.
  2. Thiết kế giải thuật không hình thức (informal algorithm).
  3. Biểu diễn giải thuật bằng ngôn ngữ giả kết hợp các phép toán trừu tượng (ADT).
  4. Tinh chế dần các lệnh ngôn ngữ tự nhiên sang cấu trúc điều khiển của ngôn ngữ lập trình.
  5. Cài đặt chi tiết các hàm và cấu trúc dữ liệu bằng mã nguồn C cụ thể.

Hệ thống bài tập trong giáo trình gồm các câu hỏi suy luận lý thuyết (so sánh ưu nhược điểm của các phương pháp cài đặt mảng và con trỏ, phân tích trường hợp xấu nhất/tốt nhất), bài toán mô phỏng thuật toán trên dữ liệu mẫu và các yêu cầu hoàn thiện mã nguồn chương trình con.

Hướng dẫn tự học dành cho sinh viên:

  • Đọc kỹ định nghĩa hình thức và bảng đặc tả các phép toán nguyên thủy của từng ADT trước khi tiếp cận phần mã cài đặt.
  • Phân tích và viết lại giải thuật bằng ngôn ngữ giả trước khi trực tiếp biên dịch mã nguồn C.
  • Tự giải quyết các bài toán khử đệ quy và cài đặt bổ sung các hàm thao tác chưa được hiện thực hóa toàn phần trong giáo trình.

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

  • Kế thừa nền tảng học thuật quốc tế: Nội dung cơ bản được biên soạn dựa trên giáo trình kinh điển Data Structures and Algorithms của Alfred V. Aho, John E. Hopcroft và Jeffrey D. Ullman (Addison-Wesley, tái bản 1987), đảm bảo tính chuẩn xác và chặt chẽ về mặt khoa học máy tính.
  • Tách biệt mức quan niệm và mức cài đặt: Giáo trình duy trì sự phân định nhất quán giữa mức khái niệm (conceptual level - ADT) và mức cài đặt cụ thể (implementation level - mảng tĩnh, con trỏ, con nháy). Điều này giúp sinh viên hiểu rõ cấu trúc dữ liệu mà không bị phụ thuộc vào cú pháp của một ngôn ngữ lập trình nhất định.
  • Giải pháp kỹ thuật đa dạng (Cài đặt bằng con nháy): Bên cạnh hai kỹ thuật phổ biến là mảng và con trỏ động, giáo trình trình bày chi tiết giải pháp cài đặt danh sách liên kết bằng con nháy (cursor) trong không gian mảng SPACE kết hợp danh sách AVAILABLE. Kỹ thuật này cung cấp giải pháp xử lý danh sách liên kết cho các ngôn ngữ lập trình không hỗ trợ kiểu con trỏ trực tiếp.
  • Gắn liền với các bài toán mô hình hóa thực tế: Sử dụng các trường hợp điển hình như bài toán tô màu bản đồ thế giới và bài toán thiết kế chu kỳ đèn tín hiệu giao thông tại nút giao ngã năm để minh họa trực quan vai trò của mô hình đồ thị và giải thuật Heuristic Greedy.

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

  • Sinh viên đại học:
    • Đối tượng bắt buộc: Sinh viên năm thứ 2 các chuyên ngành Tin học, Toán tin, Lý tin.
    • Đối tượng tự chọn: Sinh viên năm thứ 2 các ngành Điện tử - Viễn thông và Tự động hóa.
    • Đối tượng tham khảo: Sinh viên các khối ngành kỹ thuật không chuyên tin và người học có nhu cầu nghiên cứu về cấu trúc dữ liệu và giải thuật.
  • Kiến thức tiên quyết (Prerequisites):
    • Kỹ năng lập trình căn bản: Sử dụng thành thạo kiểu dữ liệu cấu trúc (struct), mảng (array), con trỏ (pointer), các cấu trúc điều khiển, vòng lặp và kỹ thuật lập trình theo mô-đun (hàm/chương trình con).
    • Kiến thức Toán rời rạc: Các khái niệm cơ bản về tập hợp, quan hệ, logic mệnh đề và lý thuyết đồ thị.
  • Giảng viên: Sử dụng làm đề cương chi tiết, khung bài giảng lý thuyết 40 tiết và định hướng hệ thống bài tập 20 tiết trên lớp.
  • Tự học và tham khảo: Phục vụ tài liệu tự nghiên cứu cho các lập trình viên cần củng cố kiến thức nền tảng về tổ chức dữ liệu bộ nhớ và thiết kế thuật toán tối ưu.

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

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 biên soạn chuyên biệt cho sinh viên năm thứ 2 các ngành Tin học, Toán tin, Lý tin (thuộc khối kiến thức bắt buộc), sinh viên ngành Điện tử - Viễn thông, Tự động hóa (môn tự chọn) và người tự học cần nghiên cứu bài bản về cấu trúc dữ liệu và giải thuật.

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?

Người học bắt buộc phải hoàn thành các học phần về Kỹ năng lập trình căn bản (nắm vững biến con trỏ, cấp phát bộ nhớ động, cấu trúc bản ghi struct, mảng và hàm trong ngôn ngữ C/Pascal) cùng kiến thức Toán rời rạc (lý thuyết tập hợp, giải thuật tổ hợp và đồ thị cơ bản).

3. Điểm khác biệt của giáo trình so với các tài liệu cấu trúc dữ liệu khác là gì?

Tài liệu tập trung vào phương pháp luận trừu tượng hóa: xây dựng hoàn chỉnh kiểu dữ liệu trừu tượng (ADT) độc lập trước khi tiến hành cài đặt. Giáo trình cung cấp đầy đủ cả 3 phương pháp cài đặt: mảng đặc, con trỏ động và con nháy (cursor-based memory space), đồng thời giải quyết chi tiết cơ chế khử đệ quy bằng mẩu tin hoạt động (activation record).

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 tuân thủ chu trình: đọc hiểu mô hình toán học của ADT -> nghiên cứu giải thuật dưới dạng ngôn ngữ giả -> tự tay viết mã nguồn C cài đặt từng phép toán nguyên thủy -> giải bài tập khử đệ quy và các bài toán tối ưu trên đồ thị -> đối chiếu kết quả với chương trình mẫu.

5. Giáo trình có những tài liệu bổ trợ và tài liệu tham khảo chính nào?

Học phần đi kèm tài liệu thực hành cấu trúc dữ liệu riêng của Khoa CNTT – ĐH Cần Thơ. Ngoài ra, giáo trình trích dẫn hệ thống tài liệu tham khảo chuẩn mực gồm: Data Structures and Algorithms (Aho, Hopcroft, Ullman, 1983/1987), Cấu trúc dữ liệu + giải thuật = Chương trình (Niklaus Wirth, 1983), Cấu trúc dữ liệu và giải thuật (Đỗ Xuân Lôi), Cấu trúc dữ liệu (Nguyễn Trung Trực, 1990) và Data Structures and Algorithms in C++ (Goodrich, Tamassia, Mount, 2004).

Kết luận

Giáo trình Cấu trúc Dữ liệu của Khoa Công nghệ Thông tin – Trường Đại học Cần Thơ cung cấp hệ thống tri thức chuẩn mực về cấu trúc dữ liệu và giải thuật theo hướng tiếp cận trừu tượng hóa dữ liệu (ADT). Lộ trình học tập được thiết kế khoa học từ các cấu trúc tuyến tính cơ bản (danh sách, ngăn xếp, hàng đợi) đến các cấu trúc phi tuyến tính phức hợp (cây, tập hợp, bảng băm, đồ thị). Kết hợp với việc thực hành trên ngôn ngữ lập trình C và hệ thống tài liệu tham khảo chuẩn mực trong nước và quốc tế, giáo trình là tài liệu học tập và nghiên cứu học thuật nền tảng cho sinh viên khối ngành công nghệ thông tin và kỹ thuật máy tính.