計算理論基礎：有限自動機、正則語言與圖靈機 完整教材（依據 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 必有一個失守），這不影響分類；分類看的是最好情況下找不找得到夠好的演算法。
阅读文章 →CS3334 Project: Find the Most Frequent Duplicate
Given a list of integers, find the most frequent duplicate element. A "duplicate" is an element that appears more than once. Among all duplicates, return the one with the highest frequency. If two or more duplicates shar
阅读文章 →Chapter 2: Algorithm Analysis — Comprehensive Teaching Materials
Source: Data Structures and Algorithm Analysis in C++, 4th Edition, Mark Allen Weiss
阅读文章 →Data Structures Implementations in C++
This repository contains educational C++ implementations of various data structures for teaching purposes.
阅读文章 →LeetCode Problem Downloader
This Python script downloads all problems from LeetCode and generates: An Excel file (leetcode_problems.xlsx) containing problem metadata (ID, title, difficulty, category, etc.) Individual PDF files for each problem with
阅读文章 →