GIÁO TRÌNH CẤU TRÚC RỜI RẠC – THS. NGUYỄN THỊ LIỆU

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

Giáo trình Cấu trúc rời rạc do ThS. Nguyễn Thị Liệu (Khoa Công nghệ, Trường Đại học Công nghệ Đồng Nai) biên soạn vào tháng 04/2021 dưới dạng báo cáo tổng kết đề tài nghiên cứu khoa học cấp trường. Trong chương trình đào tạo bậc đại học ngành Công nghệ Thông tin, tài liệu này đóng vai trò là học liệu cơ sở khối ngành, phục vụ trực tiếp cho hai học phần: Cấu trúc rời rạc và Lý thuyết đồ thị.

Mục tiêu học tập của giáo trình tập trung vào việc trang bị cho người học:

  • Năng lực mô hình hóa các bài toán thực tế sang ngữ cảnh toán học rời rạc.
  • Kỹ năng thiết kế, biểu diễn thuật toán bằng giả mã (pseudocode) và đánh giá độ phức tạp tính toán ($O$-lớn).
  • Khả năng vận dụng các nguyên lý đếm, phương pháp giải hệ thức truy hồi và phân tích cấu trúc đồ thị vào việc xây dựng cấu trúc dữ liệu và giải quyết bài toán tin học.

Cấu trúc giáo trình gồm 3 chương chính:

  1. Chương I: Thuật toán
  2. Chương II: Bài toán đếm
  3. Chương III: Đồ thị

Cách tiếp cận của tài liệu đi từ định nghĩa hình thức, định lý và mệnh đề chứng minh toán học, đến việc cài đặt thuật toán qua giả mã và phân tích các ví dụ số học hoặc bài toán thực tế. Điểm đặc thù của giáo trình là tính liên kết chặt chẽ giữa toán học rời rạc thuần túy và kiến trúc máy tính, thể hiện qua các bài toán biểu diễn số nhị phân, thuật toán chia để trị, phân tích mạng cục bộ (LAN) và mô hình kết nối mạng xử lý song song.

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

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

Nội dung giáo trình được triển khai qua 3 chương có sự tiếp nối logic chặt chẽ:

  • Chương I: Thuật toán: Trình bày khái niệm thuật toán bắt nguồn từ nhà toán học Al-Khowarizmi; 6 đặc trưng của thuật toán (đầu vào, đầu ra, tính dừng, tính xác định, tính hiệu quả, tính phổ dụng); phương pháp mô tả thuật toán bằng ngôn ngữ tự nhiên và giả mã. Khảo sát chi tiết thuật toán tìm kiếm tuyến tính ($O(n)$) và tìm kiếm nhị phân ($O(\log_2 n)$). Giới thiệu ký hiệu Big-O (khởi xướng bởi Paul Bachmann năm 1892) cùng bảng phân loại cấp độ phức tạp từ hằng số $O(1)$ đến giai thừa $O(n!)$. Phân tích các thuật toán số nguyên như thuật toán chia, thuật toán Euclide tìm ƯCLN, khai triển cơ số $b$, thuật toán cộng ($O(n)$) và nhân ($O(n^2)$) số nguyên nhị phân. Cuối cùng, chương khảo sát thuật toán đệ quy, so sánh chi phí tính toán giữa đệ quy và lặp qua bài toán tính giai thừa và số Fibonacci.
  • Chương II: Bài toán đếm: Cung cấp các công cụ tổ hợp xuất phát từ thế kỷ 17. Nội dung bao gồm quy tắc cộng, quy tắc nhân, nguyên lý bù trừ (áp dụng cho bài toán số mất thứ tự $D_n$), nguyên lý Dirichlet và Dirichlet tổng quát ($\lceil N/k \rceil$). Phân tích chỉnh hợp lặp ($n^k$), tổ hợp lặp ($C_{n+k-1}^k$ thông qua mô hình biểu diễn thanh đứng và ngôi sao), hoán vị lặp (ví dụ phân tích từ SUCCESS) và bài toán phân bố $n$ đồ vật vào $k$ hộp. Trình bày thuật toán sinh hoán vị theo thứ tự từ điển, sinh xâu nhị phân và sinh tổ hợp. Thiết lập và giải hệ thức truy hồi tuyến tính thuần nhất bậc $k$ với hệ số hằng số thông qua phương trình đặc trưng (áp dụng cho công thức hiển Fibonacci) và hệ thức truy hồi chia để trị $f(n) = a f(n/b) + g(n)$.
  • Chương III: Đồ thị: Khởi đầu từ bài toán 7 chiếc cầu Königsberg của Leonhard Euler (thế kỷ 18). Định nghĩa và phân loại: đơn đồ thị, đa đồ thị, giả đồ thị (có khuyên và cạnh bội), đồ thị có hướng và đa đồ thị có hướng. Nghiên cứu khái niệm bậc của đỉnh $\deg(v)$, đỉnh treo, đỉnh cô lập, định lý tổng bậc đỉnh $\sum \deg(v) = 2|E|$ và hệ quả số đỉnh bậc lẻ là số chẵn. Khảo sát các đơn đồ thị đặc biệt: đồ thị đầy đủ $K_n$, đồ thị vòng $C_n$, đồ thị bánh xe $W_n$, đồ thị lập phương $Q_n$, đồ thị phân đôi và phân đôi đầy đủ $K_{m,n}$. Mô tả đồ thị bằng ma trận liền kề và ma trận liên thuộc, điều kiện đồ thị đẳng cấu. Khảo sát tính liên thông, đường đi, chu trình (đơn, sơ cấp), đỉnh cắt (điểm khớp), cạnh cắt (cầu), định lý về số cạnh trong đơn đồ thị có $k$ thành phần liên thông, liên thông trong đồ thị có hướng (mạnh, yếu, một chiều) và định lý tính số đường đi độ dài $r$ bằng lũy thừa ma trận $A^r$.
                                                      (Mô hình hóa & Hệ thức truy hồi)
                                                           [Chương III: Đồ thị]
                                                      (Cấu trúc, Ma trận, Tính liên thông)

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

  • Lý thuyết nền tảng: Lý thuyết tiệm cận tính toán (Big-O), định lý số học về thuật toán chia và thuật toán Euclide, nguyên lý bù trừ và nguyên lý Dirichlet, lý thuyết đồ thị Euler và các cấu trúc tổ hợp cơ bản.
  • Nguyên lý cốt lõi: Nguyên lý bảo toàn bậc trong đồ thị, nguyên lý quy nạp trong giải hệ thức truy hồi, nguyên lý đếm đối ngẫu và kỹ thuật phân rã không gian tìm kiếm trong thuật toán chia để trị.
  • Khuôn mẫu mô hình hóa: Chuyển đổi bài toán thực tế thành đồ thị (đồ thị cạnh tranh sinh thái, đồ thị ảnh hưởng, đồ thị ưu tiên câu lệnh, cấu trúc mạng liên kết).

Kỹ năng phát triển

  • Kỹ năng kỹ thuật: Đọc và viết giải thuật bằng giả mã chuẩn mực; tính toán ma trận liền kề và ma trận liên thuộc; thao tác lũy thừa ma trận để xác định số đường đi; giải phương trình đặc trưng tìm nghiệm dãy số.
  • Kỹ năng phân tích: Đánh giá số phép tính sơ cấp (so sánh, dịch bit, cộng, nhân) để xác định cấp độ phức tạp thời gian; phân tích cấu trúc đồ thị tìm bất biến đẳng cấu, điểm khớp và cầu; chứng minh tính liên thông qua bậc đỉnh.
  • Kỹ năng thực hành: Ứng dụng mô hình toán học giải quyết bài toán lập lịch, cấu hình mạng LAN và thiết kế kiến trúc trao đổi thông tin trong máy tính xử lý song song.

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

Giáo trình được thiết kế theo phương pháp diễn giải toán học kết hợp với mô tả quy trình tin học:

  1. Tiếp cận diễn dịch: Mỗi chủ đề bắt đầu bằng định nghĩa hình thức chính xác, theo sau là các mệnh đề, định lý có chứng minh chặt chẽ (như chứng minh định lý tổng bậc đỉnh, chứng minh công thức tổ hợp lặp qua xâu nhị phân, định lý giới hạn số cạnh $n - k \le m \le \frac{(n-k)(n-k+1)}{2}$).
  2. Minh họa quy trình: Sau phần định nghĩa lý thuyết, giáo trình đưa ra các thủ tục giả mã rõ ràng (procedure max, procedure tìm kiếm nhị phân, procedure ƯCLN, procedure Hoán vị liền sau, procedure Tổ hợp liền sau) giúp người học hình dung các bước chuyển đổi từ toán học sang mã lệnh thực thi.

Hệ thống ví dụ được xây dựng với dữ liệu số cụ thể (ví dụ: tìm số 19 trong dãy 16 phần tử, tìm ƯCLN của 414 và 662, tìm hoán vị liền sau của dãy 4736521, kiểm tra tính đẳng cấu của đồ thị cụ thể qua ma trận).

Phần cuối mỗi chương cung cấp danh mục bài tập tự luận đa dạng:

  • Chương I: 25 bài tập yêu cầu xác định bậc Big-O, chứng minh bất đẳng thức tiệm cận, thiết kế thuật toán tìm kiếm tam phân, phép trừ nhị phân và các hàm đệ quy.
  • Chương II: Các bài tập đếm nghiệm nguyên phương trình $x_1+\dots+x_5=21$, đếm ký tự trong từ MISSISSIPI, phân bố báo vào ngăn tủ, thiết lập hệ thức truy hồi phân chia mặt phẳng bởi $n$ đường thẳng.
  • Chương III: Các bài tập vẽ đồ thị từ ma trận, tìm ma trận liền kề của $K_n, C_n, W_n, K_{m,n}, Q_n$, chứng minh giới hạn cạnh $e \le v^2/4$ cho đồ thị phân đôi, kiểm tra đẳng cấu và vẽ mạng lưới 16 bộ xử lý.

Phương pháp tự học tối ưu đối với tài liệu này là: đọc kỹ các bước chứng minh mệnh đề, lần lượt chạy từng bước biến nhớ (dry-run) theo các đoạn giả mã mẫu, sau đó giải quyết toàn bộ hệ thống bài tập đánh giá cuối mỗi chương.

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

Giáo trình Cấu trúc rời rạc tích hợp sâu các bài toán tin học hiện đại vào hệ thống lý thuyết toán học cổ điển:

Khía cạnh Nội dung lý thuyết toán Ứng dụng tin học tương ứng
Phân tích thuật toán Ký hiệu Big-O (Bachmann) Đánh giá độ phức tạp thời gian/không gian của các giải thuật cơ sở.
Tối ưu hóa tính toán Công thức đa thức Horner Giảm số phép tính từ $\frac{n(n+3)}{2}$ xuống $2n$ phép toán sơ cấp.
Kỹ thuật lặp vs. Đệ quy Dãy Fibonacci, giai thừa So sánh chi phí: lặp tốn $n-1$ phép cộng, đệ quy tốn $f_{n+1}-1$ phép cộng.
Thuật toán chia để trị Hệ thức $f(n) = a f(n/b) + g(n)$ Thuật toán nhân nhanh số nguyên $2n$ bit, thuật toán tìm kiếm nhị phân.
Cấu trúc mạng LAN Đồ thị $K_{1,n}$, $C_n$, $W_n$ Mô hình hóa mạng hình sao, mạng vòng tròn và mạng hỗn hợp.
Xử lý song song Đồ thị siêu khối $Q_m$, mạng lưới $n=m^2$ Cấu hình liên kết đa bộ xử lý $2^m$ nút cân bằng kết nối trực tiếp/gián tiếp.

Tài liệu còn đề cập đến nhiều bài toán ứng dụng thực tế phong phú như:

  • Mô hình đồ thị "lấn tổ" phân tích sự cạnh tranh giữa các loài trong hệ sinh thái.
  • Đồ thị có hướng biểu diễn mức độ ảnh hưởng trong nhóm người hoặc kết quả thi đấu thể thao vòng tròn.
  • Đồ thị ưu tiên trước sau để kiểm soát thứ tự thực thi đồng thời các câu lệnh trong trình biên dịch.
  • Bài toán chia bài 52 quân, bài toán gán nhãn giảng đường, mã vùng điện thoại 9 chữ số và bài toán Tháp Hà Nội ($2^n-1$ bước).

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

  • Sinh viên đại học: Phù hợp cho sinh viên năm thứ nhất và năm thứ hai chuyên ngành Công nghệ Thông tin, Kỹ thuật Phần mềm, Hệ thống Thông tin và Khoa học Máy tính đang theo học các học phần Toán rời rạc, Cấu trúc rời rạc hoặc Lý thuyết đồ thị.
  • Kiến thức tiên quyết (Prerequisites): Người học cần nắm vững kiến thức toán học phổ thông, đại số sơ cấp, các phép toán tập hợp cơ bản, khái niệm hàm số và tư duy lập trình căn bản (hiểu các cấu trúc điều khiển for, while, if-then).
  • Giảng viên: Có thể sử dụng giáo trình làm tài liệu giảng dạy chính khóa hoặc tài liệu tham khảo để biên soạn đề cương bài giảng, thiết kế câu hỏi kiểm tra đánh giá, xây dựng bài tập thực hành thuật toán và phân tích độ phức tạp.
  • Người tự học và nghiên cứu: Dành cho lập trình viên muốn củng cố nền tảng toán học cho thuật toán, nâng cao tư duy phân tích giải thuật, phục vụ việc học các môn chuyên sâu như Cấu trúc dữ liệu và giải thuật, Thiết kế và phân tích thuật toán, Trí tuệ nhân tạo hoặc Mạng máy tính.

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 phục vụ trực tiếp cho sinh viên đại học ngành Công nghệ Thông tin đang học phần Cấu trúc rời rạc và Lý thuyết đồ thị, đồng thời là tài liệu tham khảo nền tảng cho lập trình viên cần củng cố lý thuyết giải thuật.

2. Cần chuẩn bị kiến thức nền nào trước khi tiếp cận giáo trình?

Người học chỉ cần kiến thức toán học sơ cấp (đại số, lượng giác, tập hợp) và hiểu biết cơ bản về logic lập trình (vòng lặp, rẽ nhánh, biến số). Không bắt buộc phải thành thạo một ngôn ngữ lập trình cụ thể vì giáo trình sử dụng giả mã trung gian.

3. Giáo trình lựa chọn cách trình bày thuật toán như thế nào?

Giáo trình kết hợp ngôn ngữ tự nhiên, ký hiệu toán học và giả mã (pseudocode). Cách làm này tránh sự phụ thuộc vào cú pháp gò bó của từng ngôn ngữ lập trình cụ thể, giúp người học tập trung vào bản chất logic của từng bước thực hiện thuật toán.

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

Người học nên đọc kỹ định nghĩa và các bước chứng minh định lý; vẽ lại các mô hình đồ thị mẫu; tự chạy tay các đoạn giả mã với từng bước biến đổi giá trị biến; sau đó hoàn thành toàn bộ hệ thống bài tập tự luận ở cuối mỗi chương.

5. Giáo trình có cung cấp các ví dụ thực tế không?

Có. Giáo trình tích hợp nhiều ví dụ thực tế như bài toán Tháp Hà Nội, bài toán chia bài, bài toán xếp lịch thi, cấu trúc topo mạng cục bộ (LAN), bài toán phân chia kênh truyền hình và kiến trúc mạng siêu khối trong xử lý song song.

Kết luận (150 từ)

Giáo trình Cấu trúc rời rạc của ThS. Nguyễn Thị Liệu là tài liệu học thuật hoàn chỉnh, chuẩn hóa các kiến thức cơ sở về thuật toán, kỹ thuật đếm tổ hợp và lý thuyết đồ thị phục vụ trực tiếp cho khối ngành Công nghệ Thông tin. Tài liệu duy trì tính logic xuyên suốt từ việc thiết lập mô hình toán học, mô tả giải thuật bằng giả mã, đánh giá độ phức tạp tính toán đến việc ứng dụng vào các hệ thống tính toán hiện đại.

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

  1. Nắm vững phương pháp phân tích độ phức tạp tiệm cận và thuật toán đệ quy ở Chương I.
  2. Làm chủ các kỹ thuật đếm, sinh tổ hợp và giải hệ thức truy hồi ở Chương II.
  3. Vận dụng cấu trúc ma trận, tính liên thông và các đồ thị đặc biệt để giải quyết các bài toán mạng và tối ưu hóa ở Chương III.