NP問題#

• 第1章-計算複雜度基礎
  • 1.1-什麼是計算複雜度
  • 1.2-多項式時間與有效率演算法
  • 1.3-圖靈機與問題的模型化
• 第2章-P類問題
  • 2.1-P的定義與例子
  • 2.2-排序與搜尋的多項式演算法
  • 2.3-圖論中的P問題
• 第3章-NP類問題
  • 3.1-驗證與搜尋：NP的定義
  • 3.2-憑證與驗證器
  • 3.3-P是否等於NP
• 第4章-多項式化約
  • 4.1-化約的觀念
  • 4.2-NP-hard與NP-complete的定義
  • 4.3-Cook-Levin定理與SAT
• 第5章-經典NP-Complete問題
  • 5.1-3-SAT與布爾可滿足性
  • 5.2-子集合加總與背包問題
  • 5.3-圖著色與頂點覆蓋
  • 5.4-旅行銷售員與漢米爾頓迴路
• 第6章-化約的實作
  • 6.1-從3-SAT到子集合加總
  • 6.2-從子集合加總到分割與背包
  • 6.3-從3-SAT到圖著色的實例轉換
• 第7章-應對策略一：精確但加速
  • 7.1-分支限界法
  • 7.2-動態規劃救背包問題
  • 7.3-SAT求解器與DPLL
• 第8章-應對策略二：近似與啟發式
  • 8.1-近似演算法與近似比
  • 8.2-貪婪啟發式解TSP與著色
  • 8.3-局部搜尋與模擬退火
• 第9章-應對策略三：隨機與參數化
  • 9.1-隨機化演算法與BPP
  • 9.2-參數化複雜度與固定參數可解
  • 9.3-量子計算帶來的新視角
• 第10章-NP問題的實戰
  • 10.1-如何判斷一個新問題是否NP-hard
  • 10.2-工業界的NP-hard問題案例
  • 10.3-總結與進階閱讀