Giáo trình Trí tuệ nhân tạo (Artificial Intelligence) – Phạm Thọ Hoàn & Phạm Thị Anh Lê

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

Giáo trình Trí tuệ nhân tạo do nhóm tác giả Phạm Thọ Hoàn và Phạm Thị Anh Lê (Khoa Công nghệ thông tin, Trường Đại học Sư phạm Hà Nội) biên soạn năm 2011, là tài liệu giảng dạy học phần Trí tuệ nhân tạo trong chương trình đào tạo đại học và sau đại học ngành Tin học và Công nghệ thông tin. Giáo trình được xây dựng dựa trên sự kế thừa và tham khảo các nguồn học liệu từ Đại học Quốc gia Hà Nội, Đại học Bách khoa Hà Nội cùng các tài liệu học thuật quốc tế.

+-------------------------------------------------------------------------+
|                  CẤU TRÚC TỔNG THỂ CỦA GIÁO TRÌNH                       |
+-------------------------------------------------------------------------+
|  I. NỀN TẢNG & TÌM KIẾM KHÔNG GIAN TRẠNG THÁI (Chương 1 - 5)           |
|     - Nhập môn, lịch sử, các trường phái AI (Chương 1)                  |
|     - Tìm kiếm mù: BFS, DFS, DLS, IDS (Chương 2)                        |
|     - Tìm kiếm Heuristic: Best-First, Uniform, Greedy, A*, Beam (Ch. 3) |
|     - Tìm kiếm đối kháng: Minimax, Cắt tỉa Alpha-Beta (Chương 4)        |
|     - Bài toán thỏa mãn ràng buộc - CSP (Chương 5)                      |
+-------------------------------------------------------------------------+
|  II. BIỂU DIỄN TRI THỨC & LẬP LUẬN LOGIC (Chương 6 - 8)                 |
|     - Logic mệnh đề & Thuật toán phân giải (Chương 6)                   |
|     - Logic vị từ cấp một & Thuật giải đồng nhất (Chương 7)             |
|     - Lập trình Logic với ngôn ngữ SWI Prolog (Chương 8)                |
+-------------------------------------------------------------------------+
|  III. CÁC HƯỚNG MỞ RỘNG TRONG AI (Chương 9 - 10)                        |
|     - Lập luận với tri thức không chắc chắn (Chương 9)                  |
|     - Mạng nơ-ron nhân tạo và cơ chế học (Chương 10)                    |
+-------------------------------------------------------------------------+

Về mục tiêu đào tạo, giáo trình cung cấp hệ thống phương pháp luận toán học và thuật toán nhằm xây dựng các hệ thống có khả năng giải quyết vấn đề, lập luận tự động, học máy và biểu diễn tri thức. Cách tiếp cận của tài liệu dựa trên quan điểm thực chứng: đánh giá trí thông minh của máy tính dựa trên kết quả đầu ra và hành vi tương đương hoặc vượt trội con người, tương tự như nguyên lý khí động lực học của máy bay thay vì mô phỏng thuần túy cơ chế sinh học.

Cấu trúc giáo trình gồm 10 chương, đi từ các kỹ thuật tìm kiếm không gian trạng thái, tìm kiếm đối kháng và thỏa mãn ràng buộc, đến lập luận hình thức trên logic mệnh đề, logic vị từ cấp một, ngôn ngữ Prolog, và mở rộng sang mạng nơ-ron nhân tạo cùng xử lý tri thức không chắc chắn. Điểm đặc sắc của tài liệu là tính toán học chính xác, chuẩn hóa cách mô hình hóa bài toán qua 5 thành phần hình thức và cung cấp mã giả thuật toán chi tiết kèm theo các bảng diễn biến thực thi từng bước.

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

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

Nội dung học thuật của giáo trình được tổ chức tuần tự theo tiến trình phát triển từ giải thuật tìm kiếm đến suy diễn tự động:

[Chương 1: Tổng quan] 
[Chương 4: Tìm kiếm Trò chơi]                             [Chương 5: Bài toán CSP]
                        [Chương 6: Logic Mệnh đề]
                        [Chương 7: Logic Vị từ cấp 1]
                        [Chương 8: Lập trình Prolog]
[Chương 9: Tri thức không chắc chắn]                      [Chương 10: Mạng Nơ-ron]
  • Chương 1 – Giới thiệu: Khái quát định nghĩa AI, lịch sử từ mô hình nơ-ron nhị phân của Warren McCulloch và Walter Pitts (1943), hội thảo Dartmouth (1956) do John McCarthy đề xuất thuật ngữ AI và ngôn ngữ Lisp, phép thử Turing (Turing Test), chương trình Macsyma của Joel Moses, nghiên cứu giới hạn nơ-ron của Marvin Minsky và Seymour Papert, ngôn ngữ Prolog của Alain Colmerauer, đến các hệ chuyên gia y học MYCIN của Ted Shortliffe và DENDRAL. Phân tích bài toán cân bằng giữa tính biểu đạt của ngôn ngữ biểu diễn tri thức và độ phức tạp tính toán của thuật toán lập luận.
  • Chương 2 – Bài toán và phương pháp tìm kiếm lời giải: Mô hình hóa bài toán thông qua 5 thành phần hình thức (Trạng thái tổng quát, Trạng thái đầu, Trạng thái đích, Phép chuyển trạng thái, Chi phí). Trình bày thuật toán tìm kiếm tổng quát General_Search sử dụng mảng father[] để truy vết đường đi. Phân tích các giải thuật tìm kiếm mù: Tìm kiếm theo chiều rộng (BFS) sử dụng hàng đợi Queue, Tìm kiếm theo chiều sâu (DFS) sử dụng ngăn xếp Stack, Tìm kiếm sâu có giới hạn (DLS) và Tìm kiếm sâu dần (IDS).
  • Chương 3 – Các phương pháp tìm kiếm Heuristic: Định nghĩa hàm đánh giá Heuristic $h(n)$ làm thông tin phản hồi. Trình bày thuật toán Best-First Search dùng danh sách sắp xếp, các biến thể Uniform-Cost Search ($h(n) = g(n)$), Greedy Search ($h(n)$ ước lượng tới đích), giải thuật $A^*$ với $h(n) = f(n) + g(n)$ (trong đó $g(n)$ là chi phí thực từ gốc và $f(n)$ là hàm ước lượng dưới). Trình bày các giải thuật khác gồm Leo đồi (Hill-Climbing) kèm phân tích hiện tượng kẹt cực đại cục bộ, Tìm kiếm Beam với tham số độ rộng $k$, và Tìm kiếm Nhánh cận (Branch-and-Bound).
  • Chương 4 – Các giải thuật tìm kiếm lời giải cho trò chơi: Khảo sát trò chơi đối kháng hai người, thông tin hoàn hảo, tổng bằng không. Cài đặt thuật toán Minimax duyệt cây trò chơi với độ phức tạp $O(b^m)$. Xây dựng giải thuật Minimax giới hạn độ sâu kết hợp hàm đánh giá lợi thế tuyến tính có trọng số $eval(u) = \sum s_i w_i$. Trình bày thuật toán Cắt tỉa Alpha-Beta ($\alpha$-$\beta$) dùng hai tham số $\alpha$ (giá trị lớn nhất của Max) và $\beta$ (giá trị nhỏ nhất của Min) để loại bỏ các nhánh không cần thiết.
  • Chương 5 – Các phương pháp tìm kiếm lời giải thỏa mãn các ràng buộc (CSP): Định nghĩa bài toán có không gian nghiệm xác định bởi tập ràng buộc. Khảo sát giải thuật quay lui vét cạn (Backtracking), các kỹ thuật cải tiến giải thuật quay lui và giải thuật tối ưu địa phương.
  • Chương 6 & Chương 7 – Các phương pháp lập luận trên Logic mệnh đề và Logic vị từ cấp một: Cú pháp, ngữ nghĩa logic, khái niệm cơ sở tri thức ($KB$) và suy diễn câu truy vấn ($KB \models q$). Thuật toán chuyển đổi về dạng chuẩn hội (CNF), luật phân giải (Resolution Rule), câu Horn và quy tắc tam đoạn luận. Ở logic vị từ cấp một, giáo trình bổ sung thuật giải đồng nhất vị từ (Unification Algorithm), phân giải tổng quát, cùng các thuật toán suy diễn tiến (Forward Chaining) và suy diễn lùi (Backward Chaining) trên câu Horn.
  • Chương 8, 9 & 10 – Prolog, Tri thức không chắc chắn và Mạng nơ-ron: Cú pháp ngôn ngữ Prolog, môi trường SWI Prolog, cấu trúc sự kiện, luật và câu truy vấn. Cơ chế quay lui, toán tử cắt (!), phủ định giả định đóng (Negation as Failure), vị từ đệ quy và cấu trúc dữ liệu danh sách trong Prolog. Giới thiệu tổng quan các phương pháp xử lý tri thức không chắc chắn (Chương 9) và mô hình mạng nơ-ron nhân tạo cùng giải thuật học (Chương 10).

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

Giáo trình thiết lập hệ thống lý thuyết vững chắc bao gồm:

  • Lý thuyết không gian trạng thái: Biểu diễn bài toán dưới dạng đồ thị có hướng $G = (V, E)$, trong đó đỉnh là trạng thái và cung là phép chuyển trạng thái toán học.
  • Lý thuyết độ phức tạp thuật toán AI: Đánh giá hiệu năng giải thuật dựa trên 3 tham số hình thức: nhân tố nhánh ($b$), độ sâu nghiệm nông nhất ($d$), và độ sâu tối đa của cây tìm kiếm ($m$).
Thuật toán Cấu trúc dữ liệu chính Tính đầy đủ Độ phức tạp thời gian Độ phức tạp không gian Tính tối ưu
Tìm kiếm theo chiều rộng (BFS) Hàng đợi (Queue) Đầy đủ (với $b$ hữu hạn) $O(b^d)$ $O(b^d)$ Tối ưu (ít bước nhất)
Tìm kiếm theo chiều sâu (DFS) Ngăn xếp (Stack) Không đầy đủ (với $m = \infty$) $O(b^m)$ $O(b \cdot m)$ Không tối ưu
Tìm kiếm $A^*$ Danh sách ưu tiên (List) Đầy đủ Phụ thuộc Heuristic Phụ thuộc Heuristic Tối ưu (nếu $h(n)$ ước lượng dưới)
Minimax Đệ quy sâu (Call Stack) Đầy đủ (với cây hữu hạn) $O(b^m)$ $O(b \cdot m)$ Tối ưu theo lý thuyết
Cắt tỉa Alpha-Beta Đệ quy có cận $\alpha, \beta$ Đầy đủ Tối ưu hơn Minimax $O(b \cdot m)$ Tương đương Minimax
  • Lý thuyết lập luận logic hình thức: Nền tảng logic học toán học từ phép gán chân trị bảng biến thiên đến phương pháp chứng minh bằng phản chứng qua luật phân giải Robinson trong logic mệnh đề và logic vị từ cấp 1.

Kỹ năng phát triển

Người học tiếp thu và rèn luyện các nhóm kỹ năng chuyên môn:

  • Kỹ năng kỹ thuật (Technical Skills): Cài đặt các cấu trúc dữ liệu phức tạp trong duyệt cây và đồ thị; triển khai mã nguồn giải thuật tìm kiếm; lập trình khai báo (declarative programming) trên môi trường SWI Prolog với các cấu trúc vị từ đệ quy.
  • Kỹ năng phân tích (Analytical Skills): Định lượng và so sánh chi phí tính toán giữa các chiến lược tìm kiếm; phân tích tính chấp nhận được (admissibility) của hàm Heuristic; đánh giá hiệu quả cắt nhánh của thuật toán Alpha-Beta trên cây trò chơi.
  • Kỹ năng giải quyết vấn đề (Practical Competencies): Mô hình hóa các bài toán logic và trò chơi thực tế thành bài toán tìm kiếm 5 thành phần hoặc bài toán CSP chuẩn mực.

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

Giáo trình áp dụng phương pháp sư phạm diễn dịch kết hợp quy nạp, cấu trúc bài giảng đi từ việc phát biểu bài toán thực tế, mô hình hóa toán học, trừu tượng hóa thành thuật toán tổng quát, thể hiện bằng mã giả hình thức, và cuối cùng là giải thích diễn biến các biến thông qua bảng dữ liệu chi tiết.

+---------------------------+
| Bài toán thực tế / Ví dụ  |
+---------------------------+
| 5 thành phần của bài toán |
+---------------------------+
|   Thuật toán & Mã giả     |
+---------------------------+
| Bảng biến vết / Truy vết  |
+---------------------------+

Hệ thống case studies và bài tập mẫu trong giáo trình được chọn lọc từ các bài toán chuẩn mực kinh điển của ngành Trí tuệ nhân tạo:

  • Bài toán đong nước: Sử dụng 3 can dung tích 3 lít, 5 lít và 9 lít để đong chính xác 7 lít nước, mô tả chi tiết bằng bộ ba $(a, b, c)$ và so sánh hai phương án đường đi có chi phí 5 bước và 9 bước.
  • Bài toán 8-puzzle (Di chuyển 8 số trên bàn cờ $3 \times 3$): Phân tích không gian $8!$ trạng thái, biểu diễn bàn cờ bằng mảng hai chiều hoặc một chiều, thiết lập hàm Heuristic khoảng cách Manhattan.
  • Bài toán tìm đường đi: Xe robot di chuyển từ thành phố Arad đến Bucharest dựa trên cảm biến chỉ đường, áp dụng làm dữ liệu thử nghiệm cho Uniform Search, Greedy Search và $A^*$.
  • Trò chơi Dodgem trên bàn cờ $3 \times 3$: Minh họa quá trình sinh cây trò chơi đối kháng, xây dựng hàm đánh giá vị trí và điểm cản trực tiếp (+40/-40), cản gián tiếp (+30/-30).
  • Bài toán 8 quân hậu (8-Queens): Mô hình hóa bài toán CSP bằng mảng một chiều $HAU[1..8]$ với điều kiện ràng buộc không cùng hàng, cột và đường chéo ($i - HAU[i] \neq j - HAU[j]$ và $i + HAU[i] \neq j + HAU[j]$).
VÍ DỤ TRUY VẾT THUẬT TOÁN BFS TRÊN KHÔNG GIAN TRẠNG THÁI
-------------------------------------------------------------------------
Bước lặp    node        Queue (Hàng đợi)        Father (Mảng cha)
-------------------------------------------------------------------------
0           -           [S]                     Father[S] = empty
1           S           [A, B, C]               Father[A, B, C] = S
2           A           [B, C, D, E]            Father[D, E] = A
3           B           [C, D, E, G]            Father[G] = B
...         ...         ...                     ...
8           G           [F, H]                  Đích tìm thấy (G)
-------------------------------------------------------------------------
Truy vết nghiệm qua hàm path(G, father): G <-- B <-- S

Về phương pháp đánh giá, tài liệu định hướng kiểm tra năng lực người học thông qua: khả năng thiết kế hàm đánh giá $h(n)$ và $eval(u)$, chứng minh tính đúng đắn của quá trình phân giải logic, và thực hành lập trình giải quyết bài toán trên môi trường máy tính với SWI Prolog.

Để tự học hiệu quả, người học được khuyến nghị đọc kỹ mã giả, tự tay vẽ lại cây tìm kiếm và lập bảng chạy tay các biến node, Queue/Stack, Father trước khi chuyển đổi thuật toán sang ngôn ngữ lập trình thực tế.

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

Giáo trình Trí tuệ nhân tạo (2011) thể hiện sự chuyển dịch phương pháp luận học thuật theo giai đoạn phát triển hiện đại của AI:

  • Tính toán học và giải thuật chính xác: Thay vì tiếp cận AI theo hướng suy đoán hoặc mô phỏng sinh học trừu tượng, giáo trình định vị AI trên nền tảng toán học vững chắc, giải thuật cấu trúc dữ liệu chính xác và chuẩn mực độ phức tạp tính toán theo hướng phát triển của AI thế giới từ những năm 1990.
  • Chuẩn hóa cấu trúc không gian trạng thái: Mọi bài toán tìm kiếm đều được quy chuẩn hóa về mô hình 5 thành phần thống nhất, giúp sinh viên có một khung tư duy (framework) nhất quán khi tiếp cận bất kỳ bài toán tự động hóa nào.
  • Tích hợp công nghệ lập trình logic SWI Prolog: Giáo trình dành trọn vẹn Chương 8 để hướng dẫn môi trường lập trình SWI Prolog – một trong những môi trường lập trình logic tiêu chuẩn, cung cấp nền tảng thực hành cho các khái niệm suy diễn tự động.
  • Minh họa ứng dụng thực tế lịch sử: Tài liệu dẫn chứng các mốc phát triển công nghệ như hệ thống cờ vua chạy trên siêu máy tính GeneBlue (Deep Blue) thắng kiện tướng thế giới Garry Kasparov, các hệ chuyên gia y học MYCIN, hệ đoán nhận cấu trúc hóa học DENDRAL, và nguyên lý điều hướng của xe robot tự hành.
  • Bao quát đa dạng trường phái AI: Nội dung giáo trình kết hợp hài hòa giữa trường phái AI biểu tượng (Symbolic AI qua logic hình thức, Prolog, hệ chuyên gia) và mở đường cho trường phái AI kết nối (Connectionist AI qua Chương 10 về Mạng nơ-ron nhân tạo).

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

Giáo trình được biên soạn phục vụ các nhóm đối tượng cụ thể trong hệ thống giáo dục đại học:

+-------------------------------------------------------------------------+
|                         ĐỐI TƯỢNG SỬ DỤNG                               |
+------------------------------------+------------------------------------+
| Đối tượng                          | Mục đích & Điều kiện tiên quyết    |
+------------------------------------+------------------------------------+
| Sinh viên CNTT, Tin học,           | Học phần chuyên ngành cốt lõi      |
| Sư phạm Tin học (Năm 2, 3, 4)      | Tiên quyết: CSDL & Giải thuật,     |
|                                    | Toán rời rạc, Kỹ thuật lập trình   |
+------------------------------------+------------------------------------+
| Học viên Cao học / Sau đại học     | Nghiên cứu nền tảng mô hình hóa,   |
| ngành Khoa học máy tính            | lý thuyết suy diễn & lập luận      |
+------------------------------------+------------------------------------+
| Giảng viên đại học & cao đẳng      | Khung xây dựng đề cương bài giảng, |
|                                    | ngân hàng câu hỏi & bài tập mẫu    |
+------------------------------------+------------------------------------+
| Kỹ sư phần mềm & Người tự học      | Tài liệu tham khảo chuẩn mực về    |
|                                    | thuật toán tối ưu & lập trình logic|
+------------------------------------+------------------------------------+
  • Sinh viên đại học: Giáo trình là tài liệu học tập bắt buộc hoặc tham khảo chính cho sinh viên từ năm thứ hai đến năm thứ tư các ngành Công nghệ thông tin, Khoa học máy tính, Kỹ thuật phần mềm và Sư phạm Tin học.
  • Học viên cao học: Phù hợp cho các học viên chuyên ngành Khoa học máy tính cần củng cố cơ sở lý thuyết về giải thuật tìm kiếm không gian trạng thái và logic suy luận hình thức.
  • Kiến thức tiên quyết (Prerequisites): Người học cần hoàn thành các học phần Toán rời rạc (nắm vững lý thuyết đồ thị, logic mệnh đề), Cấu trúc dữ liệu và giải thuật (thành thạo ngăn xếp, hàng đợi, cây, đồ thị, đệ quy), cùng kỹ năng lập trình căn bản.
  • Giảng viên: Tài liệu cung cấp khung chương trình chuẩn gồm 10 chương, hệ thống mã giả chi tiết và các bảng truy vết biến số cụ thể, hỗ trợ xây dựng đề cương môn học, bài giảng lý thuyết và ngân hàng đề thi.
  • Tự học và nghiên cứu: Đóng vai trò là tài liệu tham khảo nền tảng cho các lập trình viên muốn nghiên cứu bản chất thuật toán tìm kiếm, lý thuyết trò chơi đối kháng và kỹ thuật biểu diễn tri thức.

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?

Giáo trình được thiết kế cho sinh viên đại học, học viên sau đại học chuyên ngành Công nghệ thông tin, Tin học, Sư phạm Tin học và các kỹ sư phần mềm cần tài liệu nền tảng về các thuật toán cốt lõi trong Trí tuệ nhân tạo.

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

Người học cần nắm chắc kiến thức Toán rời rạc (đặc biệt là Logic toán và Lý thuyết đồ thị), Cấu trúc dữ liệu và giải thuật (ngăn xếp Stack, hàng đợi Queue, cây, đồ thị, độ phức tạp thuật toán Big-O), cùng kỹ năng đọc hiểu mã giả và lập trình cơ bản.

3. Giáo trình này có điểm gì khác biệt so với các tài liệu AI khác?

Giáo trình tập trung sâu vào bản chất toán học và thuật toán với khung mô hình hóa 5 thành phần nhất quán. Giáo trình trình bày chi tiết thuật toán lập luận logic mệnh đề, logic vị từ cấp 1, kỹ thuật phân giải suy diễn, đồng thời có chương riêng hướng dẫn chi tiết lập trình logic trên môi trường SWI Prolog.

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 học tuần tự từ Chương 1 đến Chương 8; với mỗi thuật toán, cần tự giải các ví dụ mẫu (như đong nước, 8 số, Dodgem, 8 quân hậu) bằng cách lập bảng diễn biến các biến (Queue, Stack, Father, eval, $\alpha$, $\beta$) trên giấy trước khi cài đặt thuật toán trên máy tính.

5. Giáo trình có đề cập đến các công cụ hoặc môi trường thực hành cụ thể nào không?

Có. Giáo trình giới thiệu và hướng dẫn trực tiếp môi trường lập trình logic SWI Prolog (Chương 8), cùng các cấu trúc dữ liệu chuẩn để cài đặt mã giả của giải thuật tìm kiếm tổng quát và các biến thể tìm kiếm Heuristic.

Kết luận

Giáo trình Trí tuệ nhân tạo của tác giả Phạm Thọ Hoàn và Phạm Thị Anh Lê (2011) là một công trình học liệu hàn lâm chuẩn mực, cung cấp đầy đủ hệ thống phương pháp luận toán học và thuật toán nền tảng của ngành Trí tuệ nhân tạo. Giá trị cốt lõi của cuốn sách nằm ở phương pháp tiếp cận logic chặt chẽ, chuẩn hóa mô hình biểu diễn bài toán 5 thành phần và hệ thống giải thuật suy diễn hình thức chính xác.

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

  1. Tiếp cận lý thuyết không gian trạng thái và thuật toán tìm kiếm mù (Chương 1, 2).
  2. Phát triển lên các thuật toán tìm kiếm Heuristic, tìm kiếm trò chơi và thỏa mãn ràng buộc (Chương 3, 4, 5).
  3. Làm chủ lý thuyết lập luận logic mệnh đề, logic vị từ cấp 1 và thực hành trên SWI Prolog (Chương 6, 7, 8).
  4. Mở rộng nghiên cứu sang tri thức không chắc chắn và mạng nơ-ron nhân tạo (Chương 9, 10).

Tài liệu là nguồn tham khảo học thuật giá trị, đồng hành cùng các tài liệu chuyên ngành của Đại học Quốc gia Hà Nội và Đại học Bách khoa Hà Nội trong công tác đào tạo công nghệ thông tin bậc đại học và sau đại học.