BÀI MÔ TẢ THƯ MỤC VÀ TỔNG QUAN HỌC THUẬT: GIÁO TRÌNH MẬT MÃ VÀ ĐỘ PHỨC TẠP THUẬT TOÁN

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

Mật mã và độ phức tạp thuật toán (tên tiếng Anh: Complexity and Cryptography) là học phần chuyên ngành thuộc chương trình đào tạo đại học và sau đại học của Khoa Toán - Tin, Trường Đại học Bách khoa Hà Nội (FaMI-HUST). Tài liệu bài giảng được biên soạn năm 2024 bởi TS. Ngô Thị Hiền và TS. Nguyễn Đình Hân. Trong cấu trúc đào tạo ngành Toán - Tin và Khoa học Máy tính, học phần đóng vai trò cầu nối giữa toán học rời rạc, lý thuyết tính toán hình thức và an toàn thông tin hiện đại.

Mục tiêu học tập của giáo trình là trang bị cho người học nền tảng toán học về mô hình tính toán, bản chất của thuật toán, cơ chế xác định độ phức tạp tính toán và giới hạn của các hệ thống tự động hóa. Thông qua Chủ đề 1: "Thuật toán và máy Turing", người học được rèn luyện khả năng hình thức hóa các bài toán thực tiễn thành bài toán quyết định trên ngôn ngữ hình thức, phân tích hoạt động của máy Turing tất định và không tất định, đồng thời xác định ranh giới giữa bài toán giải được và bài toán không thể giải được bằng thuật toán.

Giáo trình tiếp cận theo phương pháp tiên đề và hình thức hóa toán học chặt chẽ. Cấu trúc nội dung đi từ việc đặt vấn đề trực giác trong thực tiễn, phân loại bài toán, xây dựng công cụ ngôn ngữ hình thức, đến việc thiết lập định nghĩa giải tích cho máy Turing và phân tích các bài toán bất khả giải kinh điển. Điểm đặc thù của tài liệu là tính nhất quán trong ký hiệu toán học, tính quy chuẩn trong biểu diễn cấu hình và việc sử dụng cây tính toán để mô hình hóa tính toán không tất định.

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

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

Cấu trúc Chủ đề 1 của học phần tập trung vào ba phần nội dung trọng tâm:

  1. Thuật toán và cách tiếp cận bài toán:

    • Phân loại bài toán thành bài toán quyết định (decision problem) và bài toán tìm kiếm (search problem), trong đó bài toán tối ưu (optimization problem) là trường hợp riêng (minh họa qua bài toán xếp ba lô MAX-KNAPSACK).
    • Phương tiện diễn tả bài toán từ dạng phi hình thức (informal glossaries, thesauri) đến dạng hình thức (XML schemas, first-order/modal logic, data models).
    • Cơ sở ngôn ngữ hình thức: bảng chữ cái $\Sigma$, từ $\omega$, vị nhóm tự do $\Sigma^*$, từ rỗng $\varepsilon$, độ dài từ $|\omega|$, và ngôn ngữ đặc trưng của bài toán quyết định $L(\Pi) = {\langle d \rangle \mid d \in D_\Pi \ & \ Q_\Pi = \text{TRUE}}$.
    • Khái niệm trực giác về thuật toán, Bài toán thứ mười của Hilbert (1900) về phương trình Diophantine, Luận đề Church-Turing (1936) và chứng minh của Yuri Matiyasevich (1970).

  2. Mô hình máy Turing:

    • Máy Turing tất định (Deterministic Turing Machine - DTM): Định nghĩa bộ năm $(K, \Sigma, \delta, s, H)$, cấu hình máy $K \times \triangleright\Sigma^* \times (\Sigma^*(\Sigma - {\sqcup}) \cup {\varepsilon})$, và quan hệ chuyển cấu hình $\vdash_M$.
    • Các máy Turing cơ bản ($M_a$, $L$, $R$) và quy tắc kết hợp các máy Turing.
    • Máy Turing đoán nhận ngôn ngữ: Ngôn ngữ đoán nhận được theo Turing (Turing-recognizable), máy quyết định (decider), và ngôn ngữ khẳng định được (Turing-decidable).
    • Máy Turing tính hàm: Hàm tính được theo Turing (Turing-computable).
    • Máy Turing không tất định (Nondeterministic Turing Machine - NTM): Định nghĩa bộ năm $(K, \Sigma, \Delta, s, H)$, cấu trúc cây tính toán $T_N(\omega)$, và Định lý về sự tương đương giữa máy Turing không tất định và máy Turing tất định một băng.

  3. Bài toán giải được và không giải được:

    • Phân tích các bài toán không khẳng định được (undecidable): Bài toán chấp nhận đối với máy Turing ($A_{TM}$), Bài toán dừng ($HALT_{TM}$), và Bài toán tương ứng Post ($PCP$).
[Bài toán thực tế / Ngôn ngữ tự nhiên]
[Mô hình hóa toán học & Ngôn ngữ hình thức L(Π)]
[Mô hình tính toán: Máy Turing (DTM / NTM)]
[Bài toán giải được]   [Bài toán không giải được]
(Turing-decidable)     (ATM, HALT_TM, PCP)

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

  • Đại số ngôn ngữ hình thức: Xây dựng cấu trúc vị nhóm tự do $\Sigma^$ trên bảng chữ cái $\ hữu hạn, quy tắc ghép từ, phân tích từ theo tập con $X \subseteq \Sigma^$, và hàm mã hóa dữ kiện $e(d) = \langle d \rangle$.
  • Mô hình hóa trạng thái và chuyển trạng thái: Thiết lập hàm chuyển $\delta: (K - H) \times \Sigma \to K \times (\Sigma \cup {\leftarrow, \rightarrow})$ đối với DTM và quan hệ chuyển đa trị $\Delta \subseteq ((K - H) \times \Sigma) \times (K \times (\Sigma \cup {\leftarrow, \rightarrow}))$ đối với NTM.
  • Lý thuyết quyết định và đoán nhận: Phân định sự khác biệt toán học giữa việc đoán nhận ngôn ngữ (máy có thể lặp vô hạn trên từ không thuộc ngôn ngữ) và việc khẳng định ngôn ngữ (máy luôn dừng ở trạng thái chấp nhận $y$ hoặc bác bỏ $n$).
  • Lý thuyết bất khả giải: Xây dựng nền tảng chứng minh tính không tồn tại của thuật toán đối với các bài toán dừng và bài toán tương ứng Post.

Kỹ năng phát triển

  • Kỹ năng kỹ thuật: Thiết kế bảng hàm chuyển và đồ thị chuyển trạng thái cho máy Turing để thực hiện các thao tác xử lý xâu: tìm dấu cách, kiểm tra tính cân xứng (từ đối xứng/palindrome), so sánh hai số nhị phân, nhân hai số nguyên $f(0^i 1 0^k) = 0^{ik}$, và nhận dạng các ngôn ngữ $L = {0^i 1^i}$ hay $L = {a^n b^n c^n}$.
  • Kỹ năng phân tích: Chuyển đổi yêu cầu từ ngôn ngữ tự nhiên sang dạng thức bài toán quyết định toán học; mô phỏng từng bước chuyển cấu hình $(\vdash_M)$; phân tích nhánh chấp nhận trên cây tính toán $T_N(\omega)$.
  • Năng lực học thuật: Chứng minh tính khẳng định được của một ngôn ngữ hoặc hàm số; nhận diện ranh giới tính toán để tránh việc tìm kiếm thuật toán cho các bài toán không quyết định được.

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

Tài liệu sử dụng phương pháp giảng dạy diễn dịch hình thức. Quá trình tiếp cận đi từ việc nêu hiện tượng thực tiễn (sự chênh lệch giữa giải thuật lý thuyết và tính khả thi trong thực tế), phân tích ví dụ cụ thể, sau đó đưa ra định nghĩa toán học chính xác và các định lý chứng minh.

[Hiện tượng thực tiễn / Nghịch lý tính toán]
[Hình thức hóa: Định nghĩa bộ 5 & Cấu hình]
[Ví dụ thiết kế: Bảng chuyển trạng thái & Đồ thị]
[Thực hành truy vết: Dãy chuyển cấu hình ⊢M]
[Định lý giới hạn: Tính không giải được]

Hệ thống ví dụ và nghiên cứu tình huống trong giáo trình gồm:

  • Bài toán xếp ba lô (MAX-KNAPSACK): Mô hình hóa mối liên hệ giữa bài toán tìm kiếm tối ưu hóa và bài toán quyết định với ngưỡng chặn $B$.
  • Bài toán thứ mười của Hilbert: Minh chứng lịch sử cho nhu cầu cần một định nghĩa hình thức chính xác về thuật toán (công trình của Church, Turing và Matiyasevich).
  • Thuật toán không tất định kiểm tra hợp số: Thiết kế máy $N$ lựa chọn hai số nguyên $p, q > 1$ ở dạng nhị phân, nhân hai số và so sánh với $n$.
  • Các bài toán $A_{TM}$, $HALT_{TM}$, $PCP$: Hệ thống các bài toán làm mẫu chuẩn cho việc chứng minh tính không giải được.

Phương pháp đánh giá kết quả học tập dựa trên việc người học thực hiện các bài tập:

  • Xây dựng bảng hàm chuyển $\delta$ cho các máy Turing cụ thể (Bài tập 1.1 đến 1.3).
  • Phân tích và dự đoán hoạt động của các máy Turing được biểu diễn dưới dạng đồ thị chuyển (Câu đố 1.1, Bài tập 1.4).
  • Viết quy trình lặp và giải thuật máy Turing đoán nhận các ngôn ngữ phi ngữ cảnh (Bài tập 1.5, 1.6) và hàm số (Bài tập 1.7).

Về phương pháp tự học, tài liệu định hướng người học theo dõi chi tiết chuỗi chuyển cấu hình $C_0 \vdash_M C_1 \vdash_M \dots \vdash_M C_n$, tự vẽ lại đồ thị trạng thái, và kiểm tra các trạng thái biên của băng vào có chứa ký hiệu trái nhất $\triangleright$ và ký tự trống $\sqcup$.

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

Nội dung giáo trình được biên soạn năm 2024 bởi các giảng viên Khoa Toán - Tin, Đại học Bách khoa Hà Nội, phản ánh các đặc điểm học thuật cập nhật:

  • Chuẩn hóa ký hiệu mô hình toán học: Hệ thống hóa định nghĩa cấu hình máy Turing dưới dạng tích Descartes của tập trạng thái và các xâu trên bảng chữ cái: $K \times \triangleright\Sigma^* \times (\Sigma^*(\Sigma - {\sqcup}) \cup {\varepsilon})$, giúp loại bỏ các nhập nhằng về vị trí đầu đọc và biên của băng vào.
  • Tiếp cận mô hình hóa dữ liệu đa tầng: Phân loại rõ các phương tiện diễn tả bài toán từ phi hình thức đến các chuẩn mô tả dữ liệu hiện đại như XML Schemas, Mô hình dữ liệu UML/STEP, và Logic mô-đun/logic bậc nhất.
  • Liên kết trực tiếp với mật mã học và độ phức tạp: Việc đưa mô hình máy Turing không tất định (NTM) cùng ví dụ kiểm tra hợp số vào nội dung nền tảng tạo tiền đề trực tiếp cho việc định nghĩa các lớp độ phức tạp $P$, $NP$, cũng như các bài toán phân tích thừa số nguyên – nền tảng của mật mã khóa công khai.
  • Phân loại rõ ràng các cấp độ ngôn ngữ: Làm rõ ranh giới toán học giữa ngôn ngữ đoán nhận được (Turing-recognizable) và ngôn ngữ khẳng định được (Turing-decidable) thông qua tính chất dừng của máy quyết định (decider).

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

Giáo trình được thiết kế phục vụ các nhóm đối tượng:

  • Sinh viên đại học: Sinh viên từ năm thứ ba thuộc các ngành Toán - Tin, Khoa học Máy tính, Kỹ thuật Phần mềm và An toàn Thông tin có học phần Mật mã và độ phức tạp thuật toán trong chương trình đào tạo.
  • Học viên cao học và nghiên cứu sinh: Người học sau đại học chuyên ngành Toán ứng dụng, Khoa học máy tính cần hệ thống lại lý thuyết mô hình tính toán hình thức và lý thuyết độ phức tạp.
  • Yêu cầu kiến thức tiên quyết (Prerequisites):
    • Toán rời rạc: Lý thuyết tập hợp, quan hệ, logic mệnh đề, logic vị từ, vị nhóm và lý thuyết đồ thị.
    • Cấu trúc dữ liệu và giải thuật: Khái niệm cơ bản về độ phức tạp thời gian, thuật toán tìm kiếm và tối ưu.
    • Ngôn ngữ hình thức và Automata: Khái niệm về otomat hữu hạn, biểu thức chính quy và văn phạm phi ngữ cảnh.
  • Giảng viên và nhà nghiên cứu: Tài liệu cung cấp khung bài giảng chuẩn 51 trang slide cho Chủ đề 1, tích hợp sẵn hệ thống định nghĩa, ví dụ minh họa, đồ thị chuyển và bài tập thực hành phục vụ công tác giảng dạy và ra đề thi.

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

1. Giáo trình này phù hợp với ai?

Tài liệu phù hợp cho sinh viên đại học từ năm thứ 3 trở lên, học viên cao học chuyên ngành Toán - Tin, Khoa học Máy tính, An toàn Thông tin và các giảng viên giảng dạy môn Lý thuyết tính toán, Mật mã học và Độ phức tạp thuật toán.

2. Cần kiến thức nền nào để học?

Người học cần hoàn thành các học phần Toán rời rạc, Cơ sở lý thuyết máy tính (hoặc Lý thuyết Ô-tô-mát và Ngôn ngữ hình thức), Đại số đại cương (khái niệm vị nhóm) và Cấu trúc dữ liệu & Giải thuật cơ bản.

3. Điểm khác biệt với giáo trình khác?

Giáo trình của FaMI-HUST tập trung sâu vào tính chặt chẽ của giải tích mô hình tính toán (định nghĩa cấu hình qua tích Descartes, phân tích chi tiết bước chuyển $\vdash_M$), đồng thời định hướng nội dung trực tiếp phục vụ lý thuyết mật mã và phân tích độ phức tạp, thay vì chỉ dừng lại ở lý thuyết ô-tô-mát thuần túy.

4. Làm sao để tự học hiệu quả?

Người học cần viết tường minh các bảng hàm chuyển trạng thái $\delta$, tự mô phỏng dãy biến đổi cấu hình từng bước cho các ví dụ mẫu ($0^i1^i$, $0^i10^k \to 0^{ik}$), và vẽ lại các đồ thị chuyển trạng thái để hiểu rõ cơ chế điều khiển đầu đọc/ghi trên băng.

5. Có tài liệu bổ trợ nào kèm theo?

Bài giảng đi kèm hệ thống câu đố phân tích đồ thị (Câu đố 1.1), các bài toán kiểm tra tính khẳng định được (Bài tập 1.5, 1.6), và phần đối sánh với các tài liệu tham khảo chuẩn mực trong lý thuyết tính toán (như tài liệu [5] được trích dẫn trong slide bài giảng về hàm chuyển có trạng thái dừng tại chỗ $S$).

Kết luận

Chủ đề 1 "Thuật toán và máy Turing" trong giáo trình Mật mã và độ phức tạp thuật toán của Khoa Toán - Tin, Trường Đại học Bách khoa Hà Nội (2024) cung cấp cơ sở toán học hình thức về bản chất của thuật toán và các giới hạn tính toán.

Lộ trình tiếp cận kiến thức đề xuất:

  1. Nắm vững cách hình thức hóa bài toán và ngôn ngữ đặc trưng $L(\Pi)$.
  2. Thiết kế và truy vết máy Turing tất định (DTM) trên các ngôn ngữ mẫu.
  3. Nghiên cứu mô hình máy Turing không tất định (NTM) và cây tính toán.
  4. Phân tích các bài toán không giải được ($A_{TM}, HALT_{TM}, PCP$) để hiểu rõ giới hạn của thuật toán trước khi chuyển sang các chủ đề về độ phức tạp và mật mã học.

Tài nguyên bổ sung cho người học bao gồm các chuyên khảo về Lý thuyết độ phức tạp tính toán (Computational Complexity) và Cơ sở lý thuyết mật mã (Foundations of Cryptography).