《信息學進階》是2020年清華大學出版社出版的圖書，作者是宋新波 熊超 陳智敏 黃細光。全書共分為7 章，其內容涵蓋了高中信息學競賽的所有知識點。
基本介紹
- 中文名：信息學進階
- 作者：宋新波 、熊 超 、陳智敏、黃細光
- 出版社：清華大學出版社
- ISBN：9787302559931
內容簡介,圖書目錄,作者簡介,
內容簡介
《信息學進階》為創客教育系列叢書的高中第三冊，共分為7 章，涵蓋了高中信息學競賽的所有知識點。內容描述力求化繁為簡，深入淺出，針對每個重要的知識點配以經典實例進行精心剖析，結合清晰的代碼及生動的文字、畫龍點睛的註解，力求通俗易懂。 《信息學進階》由全國著名信息學國際金牌教練、NOI 鑽石教師宋新波老師主筆，NOI 金牌教師熊超等老師參與編寫，與創客教育教材國中第三冊《信息學初步》一脈相承，是國中版基礎上的深化與拓展，屬於發展性課程及研究性課程範疇，因而本書不再重複信息學基本知識，主要側重於算法、數據結構專題，假如你是一名初學者，強烈建議先閱讀《信息學初步》。 《信息學進階》為創客教育系列叢書高中第三冊，適合高中三年級學生閱讀使用。
圖書目錄
第１章 深度優先搜尋的最佳化 1
1.1 剪枝最佳化2
【知識講解】 2
【實踐鞏固】 5
1.2 疊代加深最佳化5
【知識講解】 5
【實踐鞏固】 9
第2 章 廣度搜尋的最佳化 11
2.1 雙向廣度優先搜尋 12
2.2 優先佇列廣度優先搜尋 13
2.3 Hash 判重 15
第3 章 動態規划進階 19
3.1 區間類動態規劃 20
3.2 樹形動態規劃 23
3.3 數位DP27
3.3.1 數位DP 的基本思想 27
3.3.2 數位DP 的套用29
3.4 狀態壓縮DP34
3.4.1 狀態壓縮DP 的基本思想 34
3.4.2 狀態壓縮DP 的套用 36
3.5 單調佇列最佳化 42
3.6 斜率最佳化動態規劃 46
3.6.1 知識講解 46
3.6.2 實踐鞏固 50
第4 章 圖論 51
4.1 圖的基本概念 52
4.1.1 圖的一些定義和概念52
4.1.2 圖的存儲結構 54
4.2 圖的遍歷 58
4.2.1 深度優先遍歷和廣度優先遍歷 58
4.2.2 一筆畫問題 60
4.3 短路徑算法 67
4.3.1 Bellman-Ford 算法的實現及運用 67
4.3.2 SPFA 算法的實現及運用70
4.3.3 Dijkstra 算法的實現及運用73
4.3.4 Floyd 算法的實現及運用75
4.4 圖的連通性 77
4.4.1 無向圖的割點與橋 77
4.4.2 無向圖的雙連通分量80
4.4.3 有向圖的強連通分量81
4.5 小生成樹 83
4.5.1 Prim 算法 83
4.5.2 Kruskal 算法 84
4.6 拓撲排序與關鍵路徑 86
4.6.1 AOV 網 86
4.6.2 拓撲排序算法的基本思想
與套用 87
4.6.3 關鍵路徑 89
第5 章 字元串算法 93
5.1 哈希和哈希表 94
5.2 KMP 算法 97
5.3 Trie 字典樹 104
5.3.1 Trie 字典樹的思想 104
5.3.2 Trie 字典樹的套用 106
第6 章 高級數據結構 111
6.1 並查集 112
6.2 樹狀數組 115
6.3 RMQ 118
6.4 快速冪與矩陣乘法 122
6.4.1 快速冪 122
6.4.2 矩陣乘法 124
6.4.3 LCA 126
6.5 線段樹131
6.5.1 線段樹的基本思想 131
6.5.2 線段樹的單點修改 133
6.5.3 線段樹的區間查詢 134
6.5.4 區間修改和標記 139
6.6 平衡樹144
6.6.1 二叉查找樹的基本思想與套用 144
6.6.2 Treap 的基本思想與套用 148
第7 章 數學基礎 153
7.1 GCD 與拓展GCD 154
7.1.1 公約數GCD 的求法 154
7.1.2 擴展歐幾里得算法的基本思想與套用 158
7.2 同餘定理 164
7.2.1 同餘定理概述 164
7.2.2 線性同餘方程的求解167
7.3 逆元問題 168
7.3.1 逆元問題的求解 168
7.3.2 逆元的套用 171
7.4 容斥原理 174
作者簡介
主編介紹
孫曉奎，中國教育信息化創客教育研究中心秘書長，《中國教育信息化》《基礎教育參考》編輯。
胡永躍，粵教版高中信息技術教材分冊主編，出版《中學創客教育叢書》《Arduino科技課堂寶典》等書籍。
陳明宏，廣東省特級教師，中山市國小、國中信息技術教材主編，粵教版高中信息技術教材分冊主編。
