字典樹（Trie）— 完整教材
雜湊表把字串整條折成一個數，查詢是期望 (O(1)) 或 (O(L))（(L) 是字串長），但「所有以 ca 開頭的鍵」「最長的符合前綴」要不是掃全表，就是另外建索引。字典樹把這個前綴結構直接做成樹。KMP 教材提到的 Aho–Corasick、模糊搜尋教材裡的 Trie+編輯距離，都從這一棵樹出發。
記事を読む →練習題完全詳解 不可判定性 · NP 完備 · DPLL · 2SAT · 機率圖靈機 · 單純形法 · TSP 5CCS2FC2 Foundations of Computing II — 測驗題逐題解析
(A) L 是 NP-hard： 。NP-hard 的意思是「至少跟 NP 裡的每一個問題一樣難」。NP 裡的每個問題都是可判定的（頂多用指數時間暴力搜尋所有證書即可判定）；而 L 連「可判定」都做不到，也就是說任何 NP 問題若能解，也遠遠碰不到 L 的難度天花板——L 嚴格難於 NP 中的一切問題，因此是 NP-hard。反過來想更清楚：如果 L 竟然「不比某個 NP 問題難」，那 L 的難度就被一個可判定問題罩住，與 L 不可判定
記事を読む →第一部分：選擇題（第 1–10 題，共 50 分）
Cook–Levin 定理（1971/1973）的內容是：SAT 是 NP-complete。也就是說： 它是歷史上第一個被證明為 NP-complete 的問題，也是後續所有 NP-completeness 歸約鏈的起點。
記事を読む →第一部分：選擇題（第 1–10 題，共 50 分）
本題考三個核心性質的定義。設演算法 A 針對判定問題 X： 課程定義：X 可判定 存在 sound + complete + terminating 的演算法；X 遞迴可枚舉 存在 sound + complete 的演算法（不要求終止），即擁有「半判定程序」。
記事を読む →計算理論基礎：有限自動機、正則語言與圖靈機 完整教材（依據 5CCS2FC2 Foundations of Computing II 第一週內容編寫）
計算理論研究的核心問題是：「什麼問題可以被機器解決？需要多強的機器？」為了精確回答，我們先把「問題」形式化為語言（language），把「機器」形式化為各種自動機（automata）。
記事を読む →計算的極限 不可判定性與 Entscheidungsproblem 學習教材 5CCS2FC2 Foundations of Computing II — Week 10 白話講義
二十世紀初，德國大數學家希爾伯特（David Hilbert）有一個宏偉的夢想：把整個數學「機械化」。他相信數學裡的每一個問題都有答案，而且我們應該能找到一套固定的程序（演算法），只要照著步驟做，就能判斷任何數學敘述是真是假。1928 年，他和學生阿克曼（Wilhelm Ackermann）正式提出了著名的判定問題（Entscheidungsproblem，德文「決定問題」的意思），並稱之為「數理邏輯的核心問題」。
記事を読む →計算的極限:不可判定性 完整教材(依據 5CCS2FC2 Foundations of Computing II 第十週內容編寫) 通用圖靈機、對角線論證、停機問題與 Entscheidungsproblem
這是「演算法」這個非形式概念與「圖靈機」這個數學模型之間的橋樑:凡是直覺上「可以機械化計算」的東西,圖靈機都做得到。因此,圖靈機做不到的事,任何演算法都做不到——本週要探索的正是這條界線。
記事を読む →計算極限之外:可計算枚舉性與映射歸約 完整教材(依據 5CCS2FC2 Foundations of Computing II 第十一週內容編寫) 半可判定性、交錯模擬、co-C.E. 與映射歸約
亦即:模擬M(w);只要模擬停了(不論M接受或拒絕),halt^-都接受。若M(w)不停機,halt^-也跟著永遠跑下去——沒關係,C.E. 允許!
記事を読む →複雜度類 NP 專題 從「驗證 vs. 求解」談起,並詳述百萬美元問題 P vs NP
複雜度類 就是把這個直覺數學化的產物。它收集了所有「答案容易驗證」的判定問題。本講的主角——百萬美元問題 P vs NP——問的正是
記事を読む →P 與 NP：百萬美元問題 完整教材(依據 5CCS2FC2 Foundations of Computing II 第二週內容編寫)
要比較演算法的效率,我們關心的不是在某台電腦上跑幾秒,而是執行步數隨輸入大小n成長的速度。漸進符號就是描述「成長速度」的語言。
記事を読む →數學歸納法:代入法
分析遞迴演算法時,我們常先猜出一個封閉式解,再用數學歸納法(proof by induction)驗證它正確。歸納法也常被稱為代入法(method of substitution)。
記事を読む →圖論演算法導論 完整教材(依據 5CCS2FC2 Foundations of Computing II 第四週內容編寫) BFS / DFS、最小生成樹、拓撲排序與強連通元件
BFS 從根頂點出發,一層一層向外擴展:先走訪所有距離為 1 的鄰居,再走訪距離為 2 的,以此類推。它的核心資料結構是佇列(Queue,先進先出 FIFO)。
記事を読む →SAT 求解導論 完整教材(依據 5CCS2FC2 Foundations of Computing II 第五週內容編寫) 受限 SAT、2-SAT 與蘊涵圖、DPLL 與貪婪局部搜尋
只需證明關鍵一步 (把任意長子句壓到至多 3 個文字);其餘(k+1)-Sat k-Sat同理。核心技巧是子句拆分 + 引入新變數。
記事を読む →近似演算法與旅行推銷員問題 完整教材(依據 5CCS2FC2 Foundations of Computing II 第七週內容編寫) 最佳化問題、近似比、2OPT 演算法與不可近似性
複雜度理論(P、NP)是以判定問題為主角;但現實世界更常面對最佳化問題。兩者關係密切:一個最佳化問題通常都有對應的判定版本(「是否存在成本 D的解?」)。
記事を読む →線性規劃與整數規劃 完整教材(依據 5CCS2FC2 Foundations of Computing II 第八週內容編寫) 線性規劃、單純形法、整數規劃與分枝定界
最後一列最負係數為-3(在y行)→ 樞軸行為y。列商:15/2, 5/2, 7/2,最小為5/2 → 樞軸列為第 2 列,樞軸值=2。
記事を読む →機率圖靈機與隨機複雜度類 完整教材(依據 5CCS2FC2 Foundations of Computing II 第九週內容編寫) 機率與期望值、機率圖靈機、BPP 與 ZPP
任何可以附加在單次計算上的數值性質,都成為一個隨機變數: 於是可以討論期望執行時間 ——這正是定義 ZPP 所需的概念。
記事を読む →疑難點專題教材：兩種歸約、停機問題的「Terminating」 與三個考試作答模板 針對 Week 2 定義 5.2（多項式歸約）、Week 10 第 6 節（停機問題）、 Week 11（映射歸約）、Exercises 第二部分 Q1／Q3／Q11 編寫
注意這些定義裡的量詞都是「存在」。一個問題永遠都有爛演算法（例如永遠回答 No 的機器：sound 或 complete 必有一個失守），這不影響分類；分類看的是最好情況下找不找得到夠好的演算法。
記事を読む →