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

  • Môn học và vị trí trong chương trình đào tạo: Giáo trình Toán rời rạc được biên soạn năm 2003 phục vụ giảng dạy bậc đại học và sau đại học tại Đại học Huế (gồm các Khoa Công nghệ Thông tin, Toán - Cơ - Tin học, Vật lý thuộc Trường Đại học Khoa học và Khoa Toán, Tin học thuộc Trường Đại học Sư phạm). Học phần cung cấp hệ thống công cụ toán học nền tảng cho ngành Công nghệ Thông tin, Toán - Tin, Vật lý - Tin và các khối ngành kỹ thuật.
  • Mục tiêu học tập (Learning outcomes):
    • Trang bị phương pháp mô hình hóa các bài toán rời rạc bằng công cụ tập hợp, dãy, hàm, quan hệ, hoán vị, đồ thị, cây và mạng.
    • Phân tích và đánh giá độ phức tạp tính toán (thời gian và không gian) của thuật toán bằng ký hiệu $O$ lớn ($Big-O$).
    • Nắm vững các kỹ thuật đếm tổ hợp nâng cao, phương pháp sinh cấu hình tổ hợp và giải hệ thức truy hồi.
    • Vận dụng lý thuyết đồ thị để giải quyết các bài toán tối ưu mạng, cấu trúc liên thông và thiết kế mạch logic bằng đại số Boole.
  • Cấu trúc và cách tiếp cận: Giáo trình gồm Lời nói đầu, Mục lục, 4 phần với 8 chương chính, Danh mục tài liệu tham khảo (trang 134) và Phần phụ lục (trang 158). Tài liệu tiếp cận kết hợp giữa chứng minh toán học hình thức và mô tả giải thuật bằng mã giả (pseudocode) độc lập với ngôn ngữ lập trình.
  • Điểm đặc sắc của giáo trình: Các định lý, mệnh đề đều đi kèm chứng minh chi tiết (lược bỏ các chứng minh quá phức tạp). Nội dung lý thuyết đồ thị chiếm dung lượng lớn nhất (5 chương trên tổng số 8 chương), gắn liền với các mô hình mạng máy tính và xử lý song song.

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

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

Giáo trình phân chia thành 4 phần gồm 8 chương:

  • 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ơ bản (Input, Output, Tính dừng, Tính xác định, Tính hiệu quả, Tính phổ dụng); thuật toán tìm kiếm tuyến tính $O(n)$, tìm kiếm nhị phân $O(\log_2 n)$; độ phức tạp tính toán và ký hiệu $Big-O$ do Paul Bachmann đề xuất năm 1892; thuật toán chia và thuật toán Euclide tìm ƯCLN; biểu diễn số nguyên cơ số $b$; thuật toán đệ quy và so sánh hiệu quả giữa đệ quy với lặp qua bài toán Fibonacci và Tháp Hà Nội ($2^{64}-1$ bước chuyển).
  • Chương II: Bài toán đếm: Trình bày quy tắc cộng, quy tắc nhân, nguyên lý bù trừ (ứng dụng tính số mất thứ tự $D_n$); nguyên lý Dirichlet và Dirichlet tổng quát (với hàm trần $\lceil x \rceil$, hàm sàn $\lfloor x \rfloor$); lý thuyết Ramsey; chỉnh hợp lặp $n^k$, tổ hợp lặp $C_{n+k-1}^k$ qua mô hình thanh đứng và ngôi sao; hoán vị lặp $\frac{n!}{n_1!n_2!...n_k!}$; phân bố đồ vật vào hộp; thuật toán sinh hoán vị theo thứ tự từ điển, sinh xâu nhị phân, sinh tổ hợp; giải hệ thức truy hồi tuyến tính thuần nhất bậc $k$ bằng phương trình đặc trưng; quan hệ chia để trị và ước lượng độ phức tạp thuật toán.
  • Chương III: Đồ thị: Định nghĩa đơn đồ thị, đa đồ thị, giả đồ thị vô hướng và có hướng; bậc của đỉnh $\deg(v)$, định lý tổng bậc đỉnh $\sum \deg(v) = 2|E|$, hệ quả số đỉnh bậc lẻ là số chẵn; 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 $K_{m,n}$; biểu diễn đồ thị bằng ma trận liền kề, ma trận liên thuộc; khái niệm đẳng cấu đồ thị và bất biến đẳng cấu; đồ thị con, đồ thị bù; đường đi, chu trình sơ cấp; tính liên thông, thành phần liên thông, đỉnh cắt (điểm khớp), cạnh cắt (cầu); bất đẳng thức số cạnh $n-k \le m \le \frac{(n-k)(n-k+1)}{2}$; liên thông mạnh, liên thông yếu, liên thông một chiều trong đồ thị có hướng.
  • Chương IV: Đồ thị Euler và Đồ thị Hamilton: Đường đi Euler, chu trình Euler xuất phát từ bài toán 7 chiếc cầu Konigsberg của Leonhard Euler; đường đi và chu trình Hamilton.
  • Chương V: Một số bài toán tối ưu trên đồ thị: Đồ thị có trọng số, bài toán tìm đường đi ngắn nhất, bài toán luồng cực đại trong mạng, bài toán người du lịch (TSP).
  • Chương VI: Cây: Định nghĩa và tính chất của cây; cây khung và bài toán tìm cây khung nhỏ nhất; các phép duyệt cây nhị phân.
  • Chương VII: Đồ thị phẳng và tô màu đồ thị: Tiêu chuẩn đồ thị phẳng, đồ thị không phẳng; bài toán tô màu đồ thị và bản đồ.
  • Chương VIII: Đại số Boole: Khái niệm đại số Boole; phương pháp cực tiểu hoá các mạch logic.

Progression logic: Cung cấp công cụ thuật toán và đánh giá độ phức tạp $\rightarrow$ Kỹ thuật đếm và mô hình đệ quy/truy hồi $\rightarrow$ Cấu trúc dữ liệu đồ thị từ tĩnh đến tối ưu hóa $\rightarrow$ Cấu trúc đại số Boole ứng dụng trong phần cứng mạch logic.

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

  • Fundamental theories: Lý thuyết thuật toán và độ phức tạp tiệm cận; lý thuyết tổ hợp cổ điển và tổ hợp suy rộng; lý thuyết đồ thị và cây; lý thuyết đại số Boole.
  • Core principles: Nguyên lý Dirichlet và Dirichlet tổng quát; nguyên lý bù trừ (Inclusion-Exclusion Principle); nguyên lý quy nạp toán học; nguyên lý chia để trị (Divide-and-Conquer).
  • Essential frameworks: Khung phân loại độ phức tạp thuật toán (hằng số $O(1)$, lôgarit $O(\log n)$, tuyến tính $O(n)$, $O(n\log n)$, đa thức $O(n^b)$, hàm mũ $O(b^n)$, giai thừa $O(n!)$); khung biểu diễn đồ thị qua đại số ma trận.

Kỹ năng phát triển

  • Technical skills: Kỹ năng viết mã giả thuật toán; chuyển đổi và tính toán số học trên các cơ số $b$; thiết lập ma trận liền kề và ma trận liên thuộc.
  • Analytical skills: Kỹ năng phân tích thời gian thực thi thuật toán; chứng minh tính liên thông và tính đẳng cấu đồ thị; giải phương trình đặc trưng tìm công thức tổng quát của dãy số truy hồi.
  • Practical competencies: Kỹ năng mô hình hóa các bài toán thực tế thành bài toán đồ thị (mạng giao thông, xếp lịch thi đấu, phân chia kênh sóng truyền hình, mạng kết nối vi xử lý).

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

  • Pedagogical approach: Kết hợp giữa phương pháp tiên đề hóa toán học chặt chẽ và phương pháp mô tả giải thuật ứng dụng. Mỗi chủ đề bắt đầu từ định nghĩa chuẩn xác, chứng minh định lý toán học, tiếp nối bằng các ví dụ số học minh họa và mô tả giải thuật dưới dạng mã giả trung gian.
  • Bài tập và case studies:
    • Case studies lịch sử và thực tiễn: Bài toán 7 chiếc cầu Konigsberg của Leonhard Euler; trò chơi Tháp Hà Nội 64 đĩa; bài toán số mất thứ tự $D_n$ trong phân phối thư ngẫu nhiên; bài toán 6 người bạn/thù trong lý thuyết Ramsey.
    • Hệ thống bài tập cuối mỗi chương được phân cấp từ mức độ cơ bản đến nâng cao, bám sát các định lý và thuật toán đã học.
  • Practical exercises:
    • Tính toán độ phức tạp của các hàm đa thức và hàm điều hòa $H_n = 1 + \frac{1}{2} + ... + \frac{1}{n} = O(\log n)$.
    • Xây dựng thuật toán đệ quy và thuật toán lặp (tìm kiếm tam phân, tính luỹ thừa $a^{2^n}$, đếm số bit 1 trong xâu nhị phân).
    • Bài tập đếm cấu hình tổ hợp thực tế: Đếm số xâu tạo từ chữ cái SUCCESS và MISSISSIPI, phân chia 5 quân bài từ cỗ bài 52 quân cho 4 người chơi, bài toán chia 40 số báo vào 4 ngăn tủ.
    • Giải hệ thức truy hồi trong bài toán kinh tế (lãi suất kép $P_n = (1{,}11)P_{n-1}$) và chuỗi Fibonacci $f_n = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n$.
  • Assessment methods: Đánh giá thông qua năng lực chứng minh định lý toán học, kỹ năng phân tích độ phức tạp $Big-O$, khả năng thiết lập hệ thức truy hồi và kỹ năng viết mã giả thuật toán.
  • Self-study guidelines: Người học cần theo dõi tuần tự các chương; tự thực hiện lại các bước chứng minh; chuyển đổi mã giả sang ngôn ngữ lập trình thực tế (như Pascal, C, Fortran) và giải toàn bộ bài tập cuối chương.

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

  • Bối cảnh biên soạn và cập nhật: Giáo trình được hoàn thành vào mùa Thu năm 2003 tại Đại học Huế nhằm chuẩn hóa tài liệu giảng dạy học phần Toán rời rạc. Nội dung khắc phục việc phụ thuộc vào một ngôn ngữ lập trình cụ thể bằng cách sử dụng mã giả chuẩn hóa, tạo bước đệm trực tiếp giữa mô tả toán học và cài đặt phần mềm.
  • Tích hợp các xu hướng tính toán hiện đại:
    • Xử lý song song: Phân tích kiến trúc kết nối các bộ vi xử lý trong máy tính đa xử lý bằng các mô hình đồ thị: mảng 1 chiều, mạng lưới 2 chiều $m \times m$, và mạng siêu khối $2^m$ tương ứng với đồ thị lập phương $Q_m$.
    • Thuật toán chia để trị hiện đại: Ước lượng độ phức tạp phép nhân nhanh hai số nguyên $n$-bit đạt $O(n^{\log_2 3}) \approx O(n^{1{,}6})$ so với thuật toán nhân thông thường $O(n^2)$.
  • Ứng dụng thực tiễn trong công nghệ và đời sống:
    • Mạng cục bộ (LAN): Mô hình hóa cấu trúc mạng hình sao bằng đồ thị phân đôi đầy đủ $K_{1,n}$, cấu trúc vòng tròn bằng đồ thị vòng $C_n$, và cấu trúc hỗn hợp bằng đồ thị bánh xe $W_n$.
    • Mô hình sinh thái và xã hội: Đồ thị lấn tổ mô tả cạnh tranh loài trong sinh thái học; đồ thị ảnh hưởng phân tích tương tác nhóm; đồ thị ưu tiên trước sau quản lý tiến trình thực thi lệnh máy tính.
    • Hệ thống viễn thông và mã hóa: Ứng dụng nguyên lý Dirichlet tính toán số lượng mã vùng điện thoại; bài toán tô màu đồ thị ứng dụng trong phân chia kênh tần số phát thanh - truyền hình.

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

  • Sinh viên đại học và cao đẳng: Sinh viên thuộc các ngành Công nghệ Thông tin, Toán - Tin, Vật lý - Tin và một số ngành kỹ thuật cần nắm vững toán học rời rạc phục vụ lập trình và cấu trúc dữ liệu.
  • Học viên sau đại học và học sinh chuyên:
    • Học viên cao học ngành Phương pháp giảng dạy Toán.
    • Thí sinh ôn thi tuyển sinh đầu vào cao học ngành Công nghệ Thông tin.
    • Học sinh các lớp chuyên Toán, chuyên Tin tại các trường trung học phổ thông chuyên.
  • Prerequisites (Kiến thức tiên quyết): Kiến thức toán học phổ thông vững chắc (đại số sơ cấp, quy nạp toán học, số học chia hết, tổ hợp căn bản) và tư duy logic lập trình cơ bản.
  • Giảng viên và nhà nghiên cứu: Giảng viên sử dụng làm tài liệu giảng dạy chính khóa, xây dựng giáo án và bài tập; các kỹ sư phần mềm sử dụng làm tài liệu tra cứu các cấu trúc toán học rời rạc.

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

1. Giáo trình này phù hợp với ai?
Giáo trình phục vụ trực tiếp cho sinh viên các ngành Công nghệ Thông tin, Toán - Tin, Vật lý - Tin; học viên cao học ngành Phương pháp giảng dạy Toán; thí sinh thi cao học CNTT; học sinh chuyên Toán, chuyên Tin và giảng viên giảng dạy học phần Toán rời rạc.

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ó nền tảng về toán học đại cương (tập hợp, ánh xạ, số học cơ bản như phép chia có dư, ước chung lớn nhất) và các khái niệm logic điều khiển cơ bản trong lập trình.

3. Điểm khác biệt của giáo trình này so với các tài liệu khác là gì?
Giáo trình cân đối giữa chứng minh toán học hình thức và biểu diễn thuật toán qua mã giả trung gian; dành dung lượng chuyên sâu cho Lý thuyết đồ thị và ứng dụng (5/8 chương); đồng thời tích hợp các mô hình tính toán hiện đại như mạng xử lý song song và cấu trúc mạng LAN.

4. Làm thế nào để tự học giáo trình này hiệu quả?
Người học nên học tuần tự theo tiến trình 8 chương, tự cài đặt lại các thuật toán mã giả sang một ngôn ngữ lập trình cụ thể, và giải tuần tự hệ thống bài tập phân cấp ở cuối mỗi chương.

5. Giáo trình có tài liệu bổ trợ nào đi kèm không?
Giáo trình có phần Tài liệu tham khảo (trang 134) và Phần phụ lục (trang 158) cung cấp các nội dung bổ trợ và tài liệu mở rộng cho việc tra cứu.

Kết luận

  • Giá trị học thuật cốt lõi: Giáo trình Toán rời rạc hệ thống hóa chính xác, cô đọng các tri thức nền tảng về thuật toán, kỹ thuật đếm tổ hợp, lý thuyết đồ thị và đại số Boole; thiết lập mối liên kết chặt chẽ giữa toán học lý thuyết và khoa học máy tính ứng dụng.
  • Lộ trình học tập đề xuất: Tiếp cận từ công cụ phân tích thuật toán (Chương I) $\rightarrow$ Nắm vững các nguyên lý đếm và hệ thức truy hồi (Chương II) $\rightarrow$ Khảo sát toàn diện cấu trúc đồ thị, cây và các bài toán tối ưu (Chương III đến Chương VII) $\rightarrow$ Nghiên cứu đại số Boole và cực tiểu hóa mạch logic (Chương VIII).
  • Tài nguyên bổ sung: Khai thác phần Phụ lục và Danh mục tài liệu tham khảo ở cuối sách để mở rộng các phương pháp chứng minh và kỹ thuật giải thuật nâng cao.