掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
全國計算機等級考試最新真考題庫模擬考場及詳解·二級MSOffice高級應用
-
>
決戰行測5000題(言語理解與表達)
-
>
軟件性能測試.分析與調優實踐之路
-
>
第一行代碼Android
-
>
JAVA持續交付
-
>
EXCEL最強教科書(完全版)(全彩印刷)
-
>
深度學習
計算復雜性理論導引 版權信息
- ISBN：9787560659299
- 條形碼：9787560659299 ; 978-7-5606-5929-9
- 裝幀：一般膠版紙
- 冊數：暫無
- 重量：暫無
- 所屬分類：>
計算復雜性理論導引 內容簡介
本書介紹了計算復雜性理論的一些基礎知識，如計算模型Turing 機、復雜性的度量與本質關系、P等不等于NP問題、空間復雜性等，還選擇了一些適合密碼學及信息安全專業學習的高級專題，如隨機化算法、電路復雜性、交互式證明等進行了介紹。 本書的編寫盡量少使用計算機專業術語，涉及的計算問題相對集中，避免學生因相關數學知識儲備不夠而造成困惑。對較難的定理證明，給出直觀分析以增進學生的理解和消化。設置了合適數量和難度的習題，習題中的知識點也非常重要，通過給出適當提示，引導學生完成。 本書可作為密碼學、信息安全及相關專業的“計算復雜性理論”課程的教材。
計算復雜性理論導引 目錄
緒論 計算復雜性理論簡介 1
0.1 計算復雜性理論的首要問題 1
0.2 計算復雜性理論與算法理論的區別 1
0.3 計算理論及其組成 1
0.4 計算復雜性理論與密碼學的關系 2
第1章 計算模型——Turing機 3
1.1 常用術語和記號 3
1.2 Turing機 4
1.2.1 Turing機的基本模型 4
1.2.2 TM的形式化定義 5
1.2.3 TM的格局 5
1.2.4 TM舉例 6
1.2.5 描述TM的不同方式 7
1.3 TM的穩健性 8
1.4 ChurchTuring命題 9
1.5 非確定性TM 10
1.6 通用TM 12
習題 12
第2章 計算任務與復雜性 13
2.1 關心的計算任務：判定語言 13
2.2 復雜性的度量 14
2.2.1 大O小o記號 15
2.2.2 時間/空間復雜性的定義 15
2.2.3 兩個事實 17
2.2.4 采用大O記號的合理性——帶壓縮定理和線性加速定理 17
2.2.5 帶數目的減少對時間復雜度和空間復雜度的影響 19
2.2.6 DTM與NDTM的時間復雜性關系 20
2.3 復雜性類 20
2.3.1 復雜性類的概念 20
2.3.2 TIME和SPACE之間的平凡(trivial)關系 21
習題 21
第3章 P與NP 23
3.1 P 類 23
3.1.1 P的定義 23
3.1.2 P的重要性 23
3.1.3 P中的問題 24
3.2 NP 類 25
3.2.1 NP的定義 25
3.2.2 NP中的問題 26
3.2.3 世紀難題 P =? NP 27
3.2.4 NP的等價定義 28
3.3 coNP與coNP=? NP 29
習題 31
第4章 歸約與NP完全性 32
4.1 歷史背景 32
4.2 歸約 32
4.2.1 Cook歸約 32
4.2.2 Karp歸約 33
4.2.3 Levin歸約 34
4.3 NP完全性 35
4.4 CookLevin定理 36
4.5 更多NP完全問題 40
4.6 其他NPC問題 43
習題 44
第5章 關于P和NP的更多知識 46
5.1 查找與判定：NPC問題的自歸約特性 46
5.1.1 SAT的自歸約特性 46
5.1.2 CLIQUE的自歸約特性 47
5.1.3 NPC問題都滿足自歸約特性 48
5.2 NPI語言 49
5.3 P vs NP 50
5.3.1 哈密爾頓回路vs 歐拉回路 50
5.3.2 三色vs四色 51
5.3.3 3SAT vs 2SAT 51
5.4 Oracle TM——相對化 54
習題 56
第6章 對角化方法 57
6.1 對角化方法與不可判定問題的存在性 57
6.1.1 可數集與對角化方法 57
6.1.2 不可判定問題的存在性 58
6.1.3 停機問題不可判定 60
6.2 分層定理 62
6.2.1 空間、時間可構造函數 62
6.2.2 分層定理 63
6.2.3 非確定性時間分層定理 66
6.3 定理A的證明 67
6.4 Ladner定理的證明 69
6.5 復雜性理論常用證明方法總結 70
習題 70
第7章 空間復雜性 72
7.1 PSPACE類 72
7.1.1 Savitch定理 72
7.1.2 PSPACE完全性 74
7.1.3 定理B的證明 76
7.2 L和NL類 77
7.2.1 空間有界的TM 77
7.2.2 L和NL 78
7.2.3 NL完全性 80
7.2.4 NL=coNL 83
習題 85
第8章 隨機化算法與隨機化復雜性類 87
8.1 隨機化算法實例 87
8.1.1 通信復雜性 87
8.1.2 多項式恒等測試 89
8.2 概率圖靈機 91
8.3 隨機化復雜性類 92
8.3.1 單邊錯復雜性類：RP和coRP 92
8.3.2 雙邊錯復雜性類：BPP 94
8.3.3 零邊錯復雜性類：ZPP 96
8.3.4 PP 97
8.4 隨機化復雜性類與其他復雜性類之間的關系 99
8.5 素數問題PRIME 101
8.5.1 PRIME∈NP 102
8.5.2 PRIME∈coRP 104
8.5.3 PRIME∈P 105
習題 106
第9章 密碼學與復雜性理論 107
9.1 單向函數 107
9.2 偽隨機發生器 109
9.3 信息論安全與計算安全 110
第10章 電路復雜性 111
10.1 布爾電路 111
10.2 電路復雜性與P/poly復雜性類 113
10.3 P/poly復雜性類 115
10.4 一致布爾電路 117
10.5 并行計算與Nick復雜性類 118
10.6 BPPP/poly 120
習題 121
第11章 多項式分層 123
11.1 定義與實例 123
11.2 PH的內部結構 124
11.3 交錯式TM與PH的等價定義 125
11.4 PH坍塌 127
習題 129
第12章 交互式證明 130
12.1 IP 131
12.2 公開/保密的隨機性 133
12.3 IP=PSPACE 135
12.4 零知識證明 141
12.5 概率可驗證明(PCP) 143
參考文獻 145
展開全部
書友推薦
- >
詩經-先民的歌唱
- >
唐代進士錄
- >
羅曼·羅蘭讀書隨筆-精裝
- >
大紅狗在馬戲團-大紅狗克里弗-助人
- >
史學評論
- >
推拿
- >
山海經
- >
姑媽的寶刀
本類暢銷
