鍛鍊問題解決力！演算法與資料結構應用全圖解

監修者的話
前言
本書的結構
本書的使用方式

第1章 演算法是什麼？
1.1 何謂演算法
1.2 演算法的例子（1）：深度優先搜尋和廣度優先搜尋
1.3 演算法的例子（2）：匹配
1.4 演算法的編寫方法
1.5 學習演算法的意義

第2章 計算複雜度和量級表示法
2.1 計算複雜度是什麼？
2.2 計算複雜度的量級表示法
2.3 求解計算複雜度之例（1）：偶數的列舉
2.4 求解計算複雜度之例（2）：最接近點對問題
2.5 計算複雜度的使用方法
2.6 關於計算複雜度的補充解說
2.7 朗道的大O表示法的詳細說明（*）
2.8 總結

第3章 設計技法（1）：全域搜尋
3.1 學習全域搜尋的意義
3.2 全域搜尋（1）：線性搜尋法
3.3 線性搜尋法的應用
3.4 全域搜尋（2）：數對的全域搜尋
3.5 全域搜尋（3）：組合的全域搜尋（*）
3.6 總結

第4章 設計技法（2）：遞迴與分治法
4.1 遞迴是什麼？
4.2 遞迴例（1）：歐幾里得的輾轉相除法
4.3 遞迴例（2）：費波那契數列
4.4 記錄化並一窺動態規畫法
4.5 遞迴例（3）：使用遞迴函數的全域搜尋
4.6 分治法
4.7 總結

第5章 設計技法（3）：動態規畫法
5.1 動態規畫法是什麼？
5.2 動態規畫法的例題
5.3 與動態規畫法相關的各種概念
5.4 動態規畫法的例子（1）：背包問題
5.5 動態規畫法的例子（2）：編輯距離
5.6 動態規畫法的例子（3）：區間分割方式的最適化
5.7 總結

第6章 設計技法（4）：二元搜尋法
6.1 陣列的二元搜尋
6.2 C++的std::lower_bound()
6.3 廣義化的二元搜尋法
6.4 更廣義化的二元搜尋法（*）
6.5 應用例（1）：猜年齡遊戲
6.6 應用例（2）：std::lower_bound()的活用例
6.7 應用例（3）：將最適化問題變成判定性問題
6.8 應用例（4）：求中位數
6.9 總結

第7章 設計技法（5）：貪婪法
7.1 貪婪法是什麼？
7.2 貪婪法未必能推導出最佳解
7.3 貪婪法模式（1）：更換也不變差
7.4 貪婪法模式（2）：現在越好，未來就越好
7.5 總結

第8章 資料結構（1）：陣列、鏈接串列、雜湊表
8.1 學習資料結構的意義
8.2 陣列
8.3 鏈接串列
8.4 鏈接串列的插入操作與刪除操作
8.5 陣列與鏈接串列的比較
8.6 雜湊表
8.7 總結

第9章 資料結構（2）：堆疊與佇列
9.1 堆疊與佇列的概念
9.2 堆疊與佇列的動作及實現
9.3 總結

第10章 資料結構（3）：圖與樹
10.1 圖
10.2 使用圖的公式化實例
10.3 圖的實現
10.4 加權圖的實現
10.5 樹
10.6 有序樹和二元樹
10.7 使用二元樹的資料結構例（1）：堆積
10.8 使用二元樹的資料結構例（２）：二元搜尋樹
10.9 總結

第11章 資料結構（4）：Union-Find
11.1 Union-Find是什麼？
11.2 Union-Find 的工作原理
11.3 巧妙減少Union-Find的計算複雜度
11.4 Union-Find的特殊設計之一：union by size
11.5 Union-Find的特殊設計之二：路徑壓縮
11.6 Union-Find 的實現
11.7 Union-Find的應用：圖中連通成分的個數
11.8 總結

第12章 排序
12.1 排序是什麼？
12.2 排序演算法的良莠程度
12.3 排序（1）：插入排序
12.4 排序（2）：合併排序
12.5 排序（3）：快速排序
12.6 排序（4）：堆積排序
12.7 排序的計算複雜度下限
12.8 排序（5）：箱排序
12.9 總結

第13章 圖（1）：圖搜尋
13.1 學習圖搜尋的意義
13.2 深度優先搜尋與廣度優先搜尋
13.3 使用遞迴函數的深度優先搜尋
13.4 「行進順序」和「回歸順序」
13.5 作爲最短路線演算法的廣度優先搜尋
13.6 深度優先搜尋和廣度優先搜尋的計算複雜度
13.7 圖搜尋例（1）：求s-t路徑
13.8 圖搜尋例（2）：二部圖判定
13.9 圖搜尋例（3）：拓撲排序
13.10 圖搜尋例（4）：樹上的動態規畫法（*）
13.11 總結

第14章 圖（2）：最短路線問題
14.1 最短路線問題是什麼？
14.2 最短路線問題的整理
14.3 鬆弛
14.4 DAG上的最短路線問題：動態規畫法
14.5 單一起點最短路線問題：貝爾曼．福特法
14.6 單一起點最短路線問題：戴克斯特拉法
14.7 全點對間最短路線問題：弗洛伊德．瓦歇爾法
14.8 參考：勢能和差分約束系統（*）
14.9 總結

第15章 圖（3）：最小生成樹問題
15.1 最小生成樹問題是什麼？
15.2 克魯斯卡法
15.3 克魯斯卡法的實現
15.4 生成樹的結構
15.5 克魯斯卡法的正確性（*）
15.6 總結

第16章 圖（4）：網路流
16.1 學習網路流的意義
16.2 圖的連通度
16.3 最大流問題和最小切割問題
16.4 福特．富爾克森法的實現
16.5 應用例（1）：二部匹配
16.6 應用例（2）：點連通度
16.7 應用例（3）：項目選擇問題
16.8 總結

第17章 P與NP
17.1 衡量問題難度的方法
17.2 P與NP
17.3 P≠NP預測
17.4 NP完全
17.5 多項式時間歸約的範例
17.6 NP困難
17.7 停機問題
17.8 總結

第18章 難題對策
18.1 與NP困難問題的對峙
18.2 以特殊案例解決的情況
18.3 貪婪法
18.4 局部搜尋和退火法
18.5 分支定界法
18.6 整數規畫問題的公式化
18.7 近似演算法
18.8 總結

參考書目
後記

 

大槻兼資
1988年生。2014年東京大學研究所資訊理工學系碩士課程修畢。取得碩士學位（資訊理工學）。目前任職於NTT DATA Mathematical Systems Inc.。並在《Software Design》雜誌連載〈解謎鍛鍊演算法能力〉。另外還有在Qiita等推動解說演算法相關主題的啟蒙運動。對於程式設計競賽，目前也作為興趣的一環而持續參加中。

秋葉拓哉
1988年生。2015年東京大學研究所資訊理工學系研究科博士課程修畢。取得博士學位（資訊理工學）。目前為Preferred Networks股份公司的執行委員。從事機器學習系統、大規模並聯分散式機器學習的研究開發。著有《挑戰程式設計競賽第2版》Mynavi出版（2002）等。學生時代著迷於程式設計競賽，在日本國內大賽獲得多次優勝，並有出席國際大賽超過10次以上的經驗。