Toán Rời Rạc

Toán rời rạc là toán học về các cấu trúc đếm được, tách biệt — nền tảng mà ngành khoa học máy tính được xây dựng trên đó. File này bao gồm logic mệnh đề và logic vị từ, kỹ thuật chứng minh, tập hợp, quan hệ, hàm, nền tảng lý thuyết đồ thị, và hệ thức truy hồi

• Ở các chương trước, chúng ta đã làm việc với toán liên tục: giải tích (chương 3), phân bố xác suất (chương 5), và tối ưu hóa trên các tham số thực (chương 6). Nhưng máy tính về cơ bản là các cỗ máy rời rạc. Chúng lưu trữ bit (0 hoặc 1), xử lý số nguyên, tuân theo logic rẽ nhánh, và vận hành trên các cấu trúc dữ liệu hữu hạn. Toán rời rạc cung cấp ngôn ngữ hình thức để suy luận về những cấu trúc này.

• Mọi thứ trong chương này đều dựa trên toán rời rạc: cổng logic của bộ xử lý là đại số Boolean, thuật toán lập lịch cần chứng minh tính đúng đắn, quản lý bộ nhớ sử dụng phép toán tập hợp, và phân tích thuật toán yêu cầu các hệ thức truy hồi.

Logic Mệnh Đề

• Logic mệnh đề là đại số của các phát biểu đúng/sai. Một mệnh đề là một phát biểu hoặc đúng (T) hoặc sai (F), không bao giờ cả hai. "Trời đang mưa" là một mệnh đề. "Mấy giờ rồi?" không phải (nó là câu hỏi, không phải phát biểu có giá trị chân lý).

• Các mệnh đề có thể được kết hợp bằng các liên từ logic:

  • AND (hội, \(p \wedge q\)): chỉ đúng khi cả \(p\) và \(q\) đều đúng.
  • OR (tuyển, \(p \vee q\)): đúng khi có ít nhất một trong \(p\) hoặc \(q\) đúng.
  • NOT (phủ định, \(\neg p\)): đảo ngược giá trị chân lý.
  • IMPLIES (kéo theo, \(p \to q\)): chỉ sai khi \(p\) đúng và \(q\) sai. "Nếu trời mưa thì mặt đất ướt" chỉ bị vi phạm khi trời mưa mà mặt đất khô.
  • IFF (tương đương, \(p \leftrightarrow q\)): đúng khi cả hai có cùng giá trị chân lý.

• Một bảng chân lý liệt kê đầy đủ tất cả tổ hợp đầu vào có thể và kết quả đầu ra. Với \(n\) mệnh đề, bảng có \(2^n\) hàng. Đây là cách chúng ta kiểm tra các tương đương logic:

\(p\)	\(q\)	\(p \wedge q\)	\(p \vee q\)	\(p \to q\)
T	T	T	T	T
T	F	F	T	F
F	T	F	T	T
F	F	F	F	T

• Hàng kéo theo khi \(p\) sai đáng chú ý: \(F \to q\) luôn đúng, bất kể \(q\) là gì. Đây gọi là chân lý rỗng (vacuous truth). "Nếu lợn biết bay thì tôi là vua nước Anh" là đúng về mặt logic vì tiền đề sai. Điều này có vẻ phản trực giác nhưng rất cần thiết cho suy luận toán học.

• Các tương đương logic là những đồng nhất thức đúng với mọi giá trị chân lý:

  • Luật De Morgan: \(\neg(p \wedge q) \equiv \neg p \vee \neg q\) và \(\neg(p \vee q) \equiv \neg p \wedge \neg q\). Để phủ định một phép hội, phủ định từng phần và chuyển sang phép tuyển (và ngược lại). Những luật này xuất hiện trực tiếp trong lập trình: !(a && b) tương đương với (!a || !b).

  • Phản đảo (Contrapositive): \(p \to q \equiv \neg q \to \neg p\). "Nếu trời mưa thì mặt đất ướt" tương đương với "nếu mặt đất không ướt thì trời không mưa." Đây là một kỹ thuật chứng minh mạnh mẽ.

  • Phủ định kép: \(\neg(\neg p) \equiv p\).

  • Phân phối: \(p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)\).

• Một công thức luôn đúng (với mọi bộ gán chân lý) được gọi là hằng đúng (tautology). Một công thức luôn sai là mâu thuẫn (contradiction). Một công thức lúc đúng lúc sai là ngẫu nhiên (contingent). Ví dụ, \(p \vee \neg p\) là hằng đúng và \(p \wedge \neg p\) là mâu thuẫn.

Logic Vị Từ và Lượng Từ

• Logic mệnh đề không thể diễn đạt các phát biểu về tất cả hoặc một số phần tử của một tập hợp. "Mọi số nguyên tố lớn hơn 2 đều lẻ" đòi hỏi logic vị từ, mở rộng logic mệnh đề với biến, vị từ và lượng từ.

• Một vị từ là một phát biểu phụ thuộc vào một biến: \(P(x)\) = "\(x\) là số chẵn." Nó trở thành một mệnh đề khi \(x\) được gán một giá trị cụ thể: \(P(4)\) đúng, \(P(7)\) sai.

• Lượng từ diễn tả phạm vi:

  • Lượng từ phổ dụng (\(\forall\)): "với mọi." \(\forall x \, P(x)\) có nghĩa là "\(P(x)\) đúng với mọi \(x\) trong miền."
  • Lượng từ tồn tại (\(\exists\)): "tồn tại." \(\exists x \, P(x)\) có nghĩa là "có ít nhất một \(x\) để \(P(x)\) đúng."

• Phủ định lượng từ sẽ đảo chúng: \(\neg(\forall x \, P(x)) \equiv \exists x \, \neg P(x)\). "Không phải ai cũng qua" có nghĩa là "có người trượt." Và \(\neg(\exists x \, P(x)) \equiv \forall x \, \neg P(x)\). "Không có thuật toán hoàn hảo" có nghĩa là "mọi thuật toán đều có khiếm khuyết."

• Lượng từ lồng nhau diễn tả các quan hệ phức tạp. \(\forall x \, \exists y \, (y > x)\) có nghĩa là "với mọi số, đều có số lớn hơn nó" (đúng với số nguyên). Thứ tự quan trọng: \(\exists y \, \forall x \, (y > x)\) có nghĩa là "có một số lớn hơn tất cả các số khác" (sai với số nguyên).

• Logic vị từ là ngôn ngữ của đặc tả hình thức. Khi chúng ta nói một thuật toán là "đúng đắn," chúng ta muốn nói \(\forall \text{đầu vào} \, x, \, \text{đầu_ra}(x) = \text{đầu_ra_mong_đợi}(x)\). Khi chúng ta nói nó "kết thúc," chúng ta muốn nói \(\forall x \, \exists t \, \text{dừng}(x, t)\).

Kỹ Thuật Chứng Minh

• Một chứng minh là một lập luận logic thiết lập chân lý của một phát biểu một cách chắc chắn. Không giống như bằng chứng thực nghiệm (cho thấy một điều gì đó hoạt động với các trường hợp đã kiểm tra), một chứng minh đảm bảo nó hoạt động cho mọi trường hợp. Đây là tiêu chuẩn của sự đúng đắn trong khoa học máy tính.

• Chứng minh trực tiếp: giả định giả thuyết, suy ra kết luận qua các bước logic. Để chứng minh "nếu \(n\) chẵn thì \(n^2\) chẵn": giả sử \(n = 2k\) với \(k\) là số nguyên nào đó, thì \(n^2 = 4k^2 = 2(2k^2)\), là số chẵn.

• Chứng minh phản chứng: giả sử phát biểu là sai và suy ra mâu thuẫn. Để chứng minh \(\sqrt{2}\) là vô tỷ: giả sử \(\sqrt{2} = a/b\) (tối giản). Khi đó \(2 = a^2/b^2\), nên \(a^2 = 2b^2\), nghĩa là \(a^2\) chẵn, vậy \(a\) chẵn, đặt \(a = 2c\). Khi đó \(4c^2 = 2b^2\), nên \(b^2 = 2c^2\), nghĩa là \(b\) cũng chẵn. Nhưng chúng ta đã nói \(a/b\) là tối giản — mâu thuẫn.

• Chứng minh quy nạp: chứng minh một phát biểu cho mọi số tự nhiên bằng cách chỉ ra: (1) trường hợp cơ sở đúng (thường là \(n = 0\) hoặc \(n = 1\)), và (2) bước quy nạp: nếu phát biểu đúng với \(n = k\) (giả thuyết quy nạp), thì nó đúng với \(n = k + 1\).

• Ví dụ, chứng minh \(\sum_{i=1}^{n} i = \frac{n(n+1)}{2}\):

  • Cơ sở: \(n = 1\): \(1 = \frac{1 \cdot 2}{2} = 1\). Đúng.
  • Bước quy nạp: giả sử \(\sum_{i=1}^{k} i = \frac{k(k+1)}{2}\). Khi đó \(\sum_{i=1}^{k+1} i = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}\). Đây chính là công thức với \(n = k+1\). Xong.

• Quy nạp là công cụ chủ lực để chứng minh tính đúng đắn của các thuật toán đệ quy và cấu trúc dữ liệu. Mọi thuật toán đệ quy đều có một chứng minh quy nạp ngầm về tính đúng đắn: trường hợp cơ sở là điều kiện dừng, và bước quy nạp là lời gọi đệ quy.

• Quy nạp mạnh giả sử phát biểu đúng với mọi giá trị đến \(k\) (không chỉ \(k\)), sau đó chứng minh nó đúng với \(k + 1\). Điều này hữu ích khi đệ quy phụ thuộc vào nhiều hơn chỉ giá trị trước đó.

• Nguyên lý chuồng bồ câu: nếu \(n+1\) vật được đặt vào \(n\) hộp, thì có ít nhất một hộp chứa hai vật. Đơn giản nhưng mạnh mẽ đáng ngạc nhiên. Nó chứng minh rằng trong bất kỳ nhóm 13 người nào, có ít nhất hai người cùng tháng sinh. Trong mạng máy tính, nó chứng minh rằng xung đột băm là không thể tránh khỏi khi có nhiều phần tử hơn số lượng bucket.

Tập Hợp

• Một tập hợp là một bộ sưu tập không có thứ tự các phần tử phân biệt. Tập hợp là cấu trúc dữ liệu nguyên thủy nhất trong toán học, và chúng làm nền tảng cho mọi thứ từ hệ thống kiểu đến truy vấn cơ sở dữ liệu.

• Các phép toán tập hợp (liên hệ với chương 5 nơi chúng ta đã dùng chúng cho xác suất):

  • Hợp \(A \cup B\): các phần tử thuộc \(A\) hoặc \(B\) hoặc cả hai.
  • Giao \(A \cap B\): các phần tử thuộc cả \(A\) và \(B\).
  • Phần bù \(\bar{A}\): các phần tử không thuộc \(A\) (so với một tập vũ trụ).
  • Hiệu \(A \setminus B\): các phần tử thuộc \(A\) nhưng không thuộc \(B\).
  • Tích Descartes \(A \times B\): tất cả các cặp có thứ tự \((a, b)\) với \(a \in A, b \in B\).

• Tập lũy thừa \(\mathcal{P}(A)\) là tập hợp tất cả các tập con của \(A\). Nếu \(|A| = n\), thì \(|\mathcal{P}(A)| = 2^n\). Với \(A = \{1, 2\}\): \(\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}\).

• Lực lượng (Cardinality) đo kích thước tập hợp. Tập hợp hữu hạn có lực lượng là số nguyên. Tập hợp vô hạn có nhiều kích cỡ khác nhau: các số tự nhiên \(\mathbb{N}\) và số hữu tỷ \(\mathbb{Q}\) là vô hạn đếm được (có thể liệt kê), trong khi số thực \(\mathbb{R}\) là vô hạn không đếm được (không thể liệt kê, được chứng minh bằng lập luận đường chéo của Cantor). Sự khác biệt này rất quan trọng trong lý thuyết tính toán: có vô hạn không đếm được các hàm nhưng chỉ có vô hạn đếm được các chương trình, vì vậy hầu hết các hàm là không tính toán được.

Quan Hệ

• Một quan hệ \(R\) trên tập \(A\) là một tập con của \(A \times A\): một tập các cặp có thứ tự xác định phần tử nào có liên quan. Ví dụ, \(\leq\) trên số nguyên là tập \(\{(a, b) : a \leq b\}\).

• Các tính chất quan trọng của quan hệ:

  • Phản xạ: mọi phần tử đều có quan hệ với chính nó. \(a R a\) với mọi \(a\). Ví dụ: \(\leq\) (mọi số đều \(\leq\) chính nó).
  • Đối xứng: nếu \(a R b\) thì \(b R a\). Ví dụ: "là anh chị em của."
  • Phản đối xứng: nếu \(a R b\) và \(b R a\) thì \(a = b\). Ví dụ: \(\leq\).
  • Bắc cầu: nếu \(a R b\) và \(b R c\) thì \(a R c\). Ví dụ: \(<\), \(\leq\), "là tổ tiên của."

• Một quan hệ tương đương là phản xạ, đối xứng và bắc cầu. Nó phân hoạch tập hợp thành các lớp tương đương nơi mọi phần tử trong một lớp có quan hệ với nhau nhưng không với các phần tử trong lớp khác. Số học modulo là một quan hệ tương đương: \(a \equiv b \pmod{n}\) phân hoạch các số nguyên thành \(n\) lớp. Tương đương kiểu trong ngôn ngữ lập trình là một quan hệ tương đương.

• Một thứ tự bộ phận (partial order) là phản xạ, phản đối xứng và bắc cầu. Nó định nghĩa một cấu trúc "nhỏ hơn hoặc bằng" có thể khiến một số phần tử không so sánh được. Các thư mục trong hệ thống file tạo thành một thứ tự bộ phận (cha-con), nhưng các thư mục cùng cấp thì không so sánh được. Một thứ tự toàn phần là thứ tự bộ phận mà mọi cặp đều so sánh được (như \(\leq\) trên số nguyên).

• Thứ tự bộ phận rất cần thiết trong đồng thời: quan hệ "xảy ra trước" trên các sự kiện là một thứ tự bộ phận. Các sự kiện không được sắp xếp bởi "xảy ra trước" là đồng thời và có thể thực thi theo bất kỳ thứ tự tương đối nào.

Hàm

• Một hàm \(f: A \to B\) ánh xạ mỗi phần tử của \(A\) (miền xác định) đến đúng một phần tử của \(B\) (miền giá trị). Hàm là mô hình toán học của tính toán tất định: với một đầu vào, có đúng một đầu ra.

• Đơn ánh (Injective): các đầu vào khác nhau luôn cho đầu ra khác nhau. \(f(a) = f(b) \implies a = b\). Nén không mất dữ liệu là đơn ánh: các đầu vào khác nhau phải nén thành đầu ra khác nhau (nếu không bạn không thể giải nén duy nhất).

• Toàn ánh (Surjective): mọi phần tử của \(B\) đều được chạm tới bởi một phần tử nào đó của \(A\). Tập ảnh bằng miền giá trị. Một hàm băm ánh xạ chuỗi thành các băm 256-bit không phải là toàn ánh nếu có ít chuỗi hơn số băm có thể có.

• Song ánh (Bijective): vừa đơn ánh vừa toàn ánh. Một tương ứng một-một hoàn hảo giữa \(A\) và \(B\). Các song ánh có hàm ngược. Mã hóa phải là song ánh: mỗi bản rõ ánh xạ đến một bản mã duy nhất, và hàm giải mã là hàm ngược.

• Hợp thành \((g \circ f)(x) = g(f(x))\): áp dụng \(f\) trước, sau đó \(g\). Hợp thành hàm có tính kết hợp (chương 2: giống như phép nhân ma trận có tính kết hợp). Các pipeline trong phần mềm là hợp thành hàm: dữ liệu chảy qua một chuỗi các phép biến đổi.

Nền Tảng Lý Thuyết Đồ Thị

• Chúng ta đã đề cập đồ thị một cách sâu rộng trong chương 12 (mạng nơ-ron đồ thị), bao gồm ma trận kề, các loại đồ thị, Laplacian và lý thuyết phổ. Ở đây chúng ta tập trung vào các tính chất thuật toán và cấu trúc liên quan đến khoa học máy tính.

• Một cây là một đồ thị liên thông không có chu trình. Tương đương, nó có \(n\) đỉnh và \(n-1\) cạnh. Cây là cấu trúc của hệ thống file, tài liệu XML/HTML, quy trình ra quyết định và phân rã đệ quy. Một cây có gốc có một đỉnh gốc được chỉ định; mọi đỉnh khác có đúng một cha.

• Một cây bao trùm của đồ thị \(G\) là một cây bao gồm tất cả các đỉnh của \(G\) sử dụng một tập con các cạnh của nó. Cây bao trùm nhỏ nhất (MST) tối thiểu hóa tổng trọng số cạnh. Thuật toán Kruskal (sắp xếp cạnh, tham lam thêm cạnh nhẹ nhất không tạo chu trình) và thuật toán Prim (phát triển cây từ một đỉnh bắt đầu, luôn thêm cạnh nhẹ nhất đến một đỉnh mới) đều tìm MST trong \(O(|E| \log |V|)\).

• Tính phẳng (Planarity): một đồ thị là phẳng nếu có thể vẽ nó trên mặt phẳng mà không có cạnh nào cắt nhau. Theo công thức Euler, với đồ thị phẳng liên thông: \(|V| - |E| + |F| = 2\), trong đó \(|F|\) là số mặt (miền, bao gồm cả mặt ngoài). Điều này suy ra \(|E| \leq 3|V| - 6\) cho đồ thị phẳng, nên đồ thị phẳng là thưa thớt. Định tuyến bảng mạch và tô màu bản đồ khai thác tính phẳng.

• Tô màu đồ thị gán màu cho các đỉnh sao cho không có hai đỉnh kề nào cùng màu. Số màu tối thiểu cần thiết là sắc số \(\chi(G)\). Định lý bốn màu phát biểu rằng \(\chi(G) \leq 4\) cho mọi đồ thị phẳng. Trong khoa học máy tính, tô màu đồ thị mô hình hóa việc cấp phát thanh ghi (gán biến cho thanh ghi CPU sao cho các biến sống đồng thời nhận thanh ghi khác nhau) và lập lịch (gán tác vụ vào khe thời gian sao cho các tác vụ xung đột không chồng lấn).

• Đường đi Euler thăm mỗi cạnh đúng một lần. Chúng tồn tại khi và chỉ khi đồ thị có đúng 0 hoặc 2 đỉnh có bậc lẻ. Đường đi Hamilton thăm mỗi đỉnh đúng một lần. Xác định xem đường đi Hamilton có tồn tại hay không là bài toán NP-đầy đủ — một trong những bài toán khó kinh điển trong khoa học máy tính. Sự tương phản này (Euler: đa thức, Hamilton: NP-đầy đủ) minh họa cách các bài toán nghe có vẻ giống nhau có thể có độ phức tạp tính toán rất khác nhau.

Hệ Thức Truy Hồi

• Một hệ thức truy hồi định nghĩa một dãy số trong đó mỗi số hạng phụ thuộc vào các số hạng trước đó. Chúng phát sinh tự nhiên từ các thuật toán đệ quy.

• Ví dụ đơn giản nhất: \(T(n) = T(n-1) + 1\) với \(T(0) = 0\). Khai triển: \(T(n) = T(n-1) + 1 = T(n-2) + 2 = \cdots = n\). Đây là \(O(n)\), độ phức tạp thời gian của một vòng lặp đơn giản.

• Merge sort cho \(T(n) = 2T(n/2) + O(n)\): chia mảng làm đôi (hai bài toán con kích thước \(n/2\)), sắp xếp đệ quy từng nửa, sau đó trộn (công việc \(O(n)\)). Nghiệm là \(T(n) = O(n \log n)\).

• Định lý Master giải các hệ thức truy hồi dạng \(T(n) = aT(n/b) + O(n^d)\):

  • Nếu \(d > \log_b a\): \(T(n) = O(n^d)\) (công việc ở mỗi mức chiếm ưu thế)
  • Nếu \(d = \log_b a\): \(T(n) = O(n^d \log n)\) (công việc cân bằng giữa các mức)
  • Nếu \(d < \log_b a\): \(T(n) = O(n^{\log_b a})\) (số lượng bài toán con chiếm ưu thế)

• Với merge sort: \(a = 2, b = 2, d = 1\). Vì \(d = \log_2 2 = 1\), chúng ta ở trường hợp cân bằng: \(T(n) = O(n \log n)\).

• Hệ thức truy hồi Fibonacci \(F(n) = F(n-1) + F(n-2)\) với \(F(0) = 0, F(1) = 1\) có nghiệm dạng đóng \(F(n) = \frac{\phi^n - \psi^n}{\sqrt{5}}\) trong đó \(\phi = \frac{1+\sqrt{5}}{2}\) (tỷ lệ vàng) và \(\psi = \frac{1-\sqrt{5}}{2}\). Điều này cho thấy dãy Fibonacci tăng theo cấp số nhân \(O(\phi^n)\), đó là lý do tại sao Fibonacci đệ quy ngây thơ chậm theo cấp số nhân.

• Tổ hợp (hoán vị, tổ hợp, định lý nhị thức và nguyên lý bù trừ) được đề cập trong chương 5 (xác suất). Các kỹ thuật đếm này rất cần thiết cho phân tích thuật toán (có bao nhiêu đầu vào có thể? bao nhiêu phép so sánh?), nhưng chúng ta sẽ không lặp lại ở đây.

Tính Toán Được

• Không phải mọi thứ đều có thể tính toán được. Đây là một trong những kết quả sâu sắc nhất trong toàn bộ toán học, và nó đặt ra giới hạn nền tảng của những gì máy tính có thể làm.

• Một máy Turing là một mô hình tính toán trừu tượng: một băng vô hạn các ô (mỗi ô chứa một ký hiệu), một đầu đọc/ghi, và một tập hữu hạn các trạng thái với các quy tắc chuyển tiếp. Mặc dù đơn giản, máy Turing có thể tính toán bất cứ thứ gì mà bất kỳ máy tính thực nào cũng có thể. Đây là luận đề Church-Turing: mọi hàm tính toán được một cách hiệu quả đều có thể được tính bằng máy Turing.

• Mọi ngôn ngữ lập trình (Python, C, Haskell) đều là Turing-đầy đủ: nó có thể mô phỏng máy Turing và do đó tính toán bất cứ thứ gì có thể tính toán. Sự khác biệt giữa các ngôn ngữ nằm ở sự tiện lợi, tốc độ và an toàn, chứ không phải ở những gì chúng có thể tính toán về mặt nền tảng.

• Bài toán dừng (halting problem) hỏi: với một chương trình và một đầu vào, liệu chương trình có dừng lại hay không, hay sẽ chạy mãi mãi? Turing đã chứng minh (1936) rằng không có thuật toán nào có thể giải quyết điều này một cách tổng quát. Chứng minh bằng phản chứng: giả sử tồn tại bộ phát hiện dừng \(H(P, x)\). Xây dựng một chương trình \(D\) chạy \(H(D, D)\) và làm ngược lại với những gì \(H\) nói. Nếu \(H\) nói \(D\) dừng, \(D\) lặp vô hạn. Nếu \(H\) nói \(D\) lặp, \(D\) dừng. Mâu thuẫn.

• Đây không phải là giới hạn của công nghệ hiện tại; nó là một bất khả thi về mặt toán học. Không có lượng tính toán, sự thông minh hay AI nào có thể giải được bài toán dừng một cách tổng quát. Nó là phiên bản của khoa học máy tính cho định lý bất toàn của Gödel.

• Hệ quả thực tế: bạn không thể viết một bộ phát hiện deadlock hoàn hảo, một máy quét virus hoàn hảo, hay một trình biên dịch tối ưu hóa hoàn hảo. Mỗi thứ trong số này đều đòi hỏi giải bài toán dừng (hoặc một bài toán không giải được tương đương) một cách tổng quát. Các công cụ thực tế sử dụng heuristic và xấp xỉ hoạt động tốt trong các trường hợp phổ biến nhưng không thể đảm bảo tính đúng đắn cho mọi đầu vào.

• Một bài toán được gọi là giải được (decidable) nếu tồn tại một thuật toán luôn kết thúc với câu trả lời đúng/sai chính xác. Nó là không giải được (undecidable) nếu không có thuật toán như vậy tồn tại. Bài toán dừng là không giải được. Kiểm tra số nguyên tố là giải được. Kiểm tra kiểu trong hầu hết các ngôn ngữ lập trình là giải được (theo thiết kế).

Lý Thuyết Độ Phức Tạp

• Ngay cả trong số các bài toán có thể tính toán, một số khó hơn nhiều so với những bài toán khác. Lý thuyết độ phức tạp phân loại các bài toán dựa trên tài nguyên (thời gian, không gian) cần thiết để giải chúng khi đầu vào tăng lên.

• P (Thời gian Đa thức): các bài toán giải được trong thời gian \(O(n^k)\) với hằng số \(k\) nào đó. Sắp xếp (\(O(n \log n)\)), đường đi ngắn nhất (\(O(|V|^2)\)), nhân ma trận (\(O(n^3)\)). Đây được coi là "hiệu quả" hay "dễ giải."

• NP (Thời gian Đa thức Không tất định): các bài toán mà một giải pháp được đề xuất có thể được kiểm tra trong thời gian đa thức, ngay cả khi việc tìm giải pháp có thể mất thời gian mũ. Ví dụ, với một đường đi Hamilton được tuyên bố, bạn có thể kiểm tra nó trong \(O(n)\) bằng cách kiểm tra từng cạnh. Nhưng tìm một cái có thể đòi hỏi thử số lượng mũ các khả năng.

• Mọi bài toán trong P đều nằm trong NP (nếu bạn có thể giải nó nhanh chóng, bạn chắc chắn có thể kiểm tra một giải pháp nhanh chóng). Câu hỏi trung tâm là liệu \(P = NP\): có phải mọi bài toán mà giải pháp có thể được kiểm tra nhanh chóng cũng có thể giải được nhanh chóng? Đây là bài toán mở quan trọng nhất trong khoa học máy tính, với giải thưởng Clay Millennium trị giá 1 triệu đô la.

• Hầu hết các chuyên gia tin rằng \(P \neq NP\), nghĩa là một số bài toán về cơ bản khó giải hơn là khó kiểm tra. Nếu \(P = NP\), mật mã học sẽ sụp đổ (phá mã hóa thuộc NP), và tối ưu hóa, lập lịch, thiết kế thuốc sẽ trở nên tầm thường.

• NP-đầy đủ là các bài toán khó nhất trong NP. Một bài toán là NP-đầy đủ nếu: (1) nó thuộc NP, và (2) mọi bài toán NP khác có thể được quy đổi về nó trong thời gian đa thức. Nếu bạn có thể giải bất kỳ bài toán NP-đầy đủ nào một cách hiệu quả, bạn có thể giải tất cả chúng (và \(P = NP\)).

• Một phép quy đổi biến đổi một bài toán thành một bài toán khác. Nếu bài toán A quy đổi về bài toán B, thì B ít nhất cũng khó bằng A. Cook (1971) đã chỉ ra rằng SAT (Bài toán thỏa mãn Boolean: với một công thức logic, có tồn tại gán biến làm nó đúng không?) là NP-đầy đủ. Karp (1972) đã chỉ ra 21 bài toán kinh điển khác là NP-đầy đủ bằng cách quy đổi SAT về từng bài toán.

• Các bài toán NP-đầy đủ nổi tiếng:

  • Bài toán Người du lịch (TSP): tìm đường đi ngắn nhất thăm tất cả các thành phố đúng một lần.
  • Tô màu đồ thị: tô màu các đỉnh với \(k\) màu sao cho không có hai đỉnh kề nào cùng màu (\(k \geq 3\)).
  • Tổng tập con (Subset sum): với một tập số nguyên, có tồn tại tập con có tổng bằng giá trị mục tiêu không?
  • Bài toán thỏa mãn Boolean (SAT): có tồn tại gán chân lý thỏa mãn một công thức logic không?
  • Đường đi Hamilton (đã đề cập ở trên trong lý thuyết đồ thị).

• Khi bạn gặp một bài toán NP-đầy đủ trong thực tế, bạn không giải nó một cách chính xác cho các đầu vào lớn. Thay vào đó, bạn sử dụng: thuật toán xấp xỉ (tìm giải pháp trong một hệ số đảm bảo của tối ưu), heuristic (tham lam, tìm kiếm địa phương, luyện kim mô phỏng), hoặc bộ giải cho trường hợp đặc biệt (nhiều bài toán NP-đầy đủ dễ với các đầu vào bị ràng buộc). Các bộ giải SAT hiện đại, ví dụ, thường xuyên giải các thể hiện với hàng triệu biến, bất chấp độ phức tạp mũ trong trường hợp xấu nhất, bằng cách khai thác cấu trúc trong các thể hiện thực tế.

• NP-khó là các bài toán khó ít nhất bằng NP-đầy đủ nhưng có thể không thuộc NP (giải pháp của chúng thậm chí có thể không kiểm tra được trong thời gian đa thức). Các phiên bản tối ưu hóa của bài toán NP-đầy đủ thường là NP-khó: "tìm đường đi TSP ngắn nhất" là NP-khó, trong khi "có đường đi TSP ngắn hơn \(k\) không?" là NP-đầy đủ.

Bài Tập Lập Trình (dùng CoLab hoặc notebook)

1. Xây dựng một bộ sinh bảng chân lý. Với một biểu thức logic, liệt kê tất cả các tổ hợp đầu vào và tính đầu ra.

   import itertools
   
   def truth_table(n_vars, expr_fn):
       """Generate truth table for a boolean function of n_vars variables."""
       headers = [f"p{i}" for i in range(n_vars)]
       print(" | ".join(headers + ["result"]))
       print("-" * (len(headers) * 4 + 10))
       for vals in itertools.product([False, True], repeat=n_vars):
           result = expr_fn(*vals)
           row = [str(v)[0] for v in vals] + [str(result)[0]]
           print(" | ".join(f"{r:>2}" for r in row))
   
   # De Morgan's law: NOT(p AND q) == (NOT p) OR (NOT q)
   print("De Morgan's Law verification:")
   truth_table(2, lambda p, q: (not (p and q)) == ((not p) or (not q)))
   

2. Chứng minh công thức tổng bằng quy nạp — xác minh bằng số liệu cho nhiều giá trị, sau đó hiện thực nghiệm dạng đóng.

   import jax.numpy as jnp
   
   # Verify sum formula: sum(1..n) = n(n+1)/2
   for n in [1, 5, 10, 100, 1000, 10000]:
       brute = sum(range(1, n + 1))
       formula = n * (n + 1) // 2
       print(f"n={n:5d}  sum={brute:>10d}  formula={formula:>10d}  match={brute == formula}")
   

3. Giải hệ thức truy hồi merge sort bằng Định lý Master và xác minh bằng thực nghiệm bằng cách đếm số phép toán.

   import jax.numpy as jnp
   
   def merge_sort_ops(n):
       """Count comparisons in merge sort (recurrence: T(n) = 2T(n/2) + n)."""
       if n <= 1:
           return 0
       half = n // 2
       return merge_sort_ops(half) + merge_sort_ops(n - half) + n
   
   for n in [8, 64, 512, 4096, 32768]:
       ops = merge_sort_ops(n)
       predicted = n * jnp.log2(n)
       ratio = ops / predicted
       print(f"n={n:5d}  ops={ops:>10d}  n log n={int(predicted):>10d}  ratio={ratio:.3f}")