掃一掃
關(guān)注中圖網(wǎng)
官方微博
本類五星書更多>
-
>
全國(guó)計(jì)算機(jī)等級(jí)考試最新真考題庫(kù)模擬考場(chǎng)及詳解·二級(jí)MSOffice高級(jí)應(yīng)用
-
>
決戰(zhàn)行測(cè)5000題(言語(yǔ)理解與表達(dá))
-
>
軟件性能測(cè)試.分析與調(diào)優(yōu)實(shí)踐之路
-
>
第一行代碼Android
-
>
JAVA持續(xù)交付
-
>
EXCEL最強(qiáng)教科書(完全版)(全彩印刷)
-
>
深度學(xué)習(xí)
中圖價(jià):¥17.8
加入購(gòu)物車
計(jì)算復(fù)雜性理論導(dǎo)引 版權(quán)信息
- ISBN：9787560659299
- 條形碼：9787560659299 ; 978-7-5606-5929-9
- 裝幀：一般膠版紙
- 冊(cè)數(shù)：暫無
- 重量：暫無
- 所屬分類：>
計(jì)算復(fù)雜性理論導(dǎo)引 內(nèi)容簡(jiǎn)介
本書介紹了計(jì)算復(fù)雜性理論的一些基礎(chǔ)知識(shí)，如計(jì)算模型Turing 機(jī)、復(fù)雜性的度量與本質(zhì)關(guān)系、P等不等于NP問題、空間復(fù)雜性等，還選擇了一些適合密碼學(xué)及信息安全專業(yè)學(xué)習(xí)的高級(jí)專題，如隨機(jī)化算法、電路復(fù)雜性、交互式證明等進(jìn)行了介紹。 本書的編寫盡量少使用計(jì)算機(jī)專業(yè)術(shù)語(yǔ)，涉及的計(jì)算問題相對(duì)集中，避免學(xué)生因相關(guān)數(shù)學(xué)知識(shí)儲(chǔ)備不夠而造成困惑。對(duì)較難的定理證明，給出直觀分析以增進(jìn)學(xué)生的理解和消化。設(shè)置了合適數(shù)量和難度的習(xí)題，習(xí)題中的知識(shí)點(diǎn)也非常重要，通過給出適當(dāng)提示，引導(dǎo)學(xué)生完成。 本書可作為密碼學(xué)、信息安全及相關(guān)專業(yè)的“計(jì)算復(fù)雜性理論”課程的教材。
計(jì)算復(fù)雜性理論導(dǎo)引 目錄
緒論 計(jì)算復(fù)雜性理論簡(jiǎn)介 1
0.1 計(jì)算復(fù)雜性理論的首要問題 1
0.2 計(jì)算復(fù)雜性理論與算法理論的區(qū)別 1
0.3 計(jì)算理論及其組成 1
0.4 計(jì)算復(fù)雜性理論與密碼學(xué)的關(guān)系 2
第1章 計(jì)算模型——Turing機(jī) 3
1.1 常用術(shù)語(yǔ)和記號(hào) 3
1.2 Turing機(jī) 4
1.2.1 Turing機(jī)的基本模型 4
1.2.2 TM的形式化定義 5
1.2.3 TM的格局 5
1.2.4 TM舉例 6
1.2.5 描述TM的不同方式 7
1.3 TM的穩(wěn)健性 8
1.4 ChurchTuring命題 9
1.5 非確定性TM 10
1.6 通用TM 12
習(xí)題 12
第2章 計(jì)算任務(wù)與復(fù)雜性 13
2.1 關(guān)心的計(jì)算任務(wù)：判定語(yǔ)言 13
2.2 復(fù)雜性的度量 14
2.2.1 大O小o記號(hào) 15
2.2.2 時(shí)間/空間復(fù)雜性的定義 15
2.2.3 兩個(gè)事實(shí) 17
2.2.4 采用大O記號(hào)的合理性——帶壓縮定理和線性加速定理 17
2.2.5 帶數(shù)目的減少對(duì)時(shí)間復(fù)雜度和空間復(fù)雜度的影響 19
2.2.6 DTM與NDTM的時(shí)間復(fù)雜性關(guān)系 20
2.3 復(fù)雜性類 20
2.3.1 復(fù)雜性類的概念 20
2.3.2 TIME和SPACE之間的平凡(trivial)關(guān)系 21
習(xí)題 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 世紀(jì)難題 P =? NP 27
3.2.4 NP的等價(jià)定義 28
3.3 coNP與coNP=? NP 29
習(xí)題 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
習(xí)題 44
第5章 關(guān)于P和NP的更多知識(shí) 46
5.1 查找與判定：NPC問題的自歸約特性 46
5.1.1 SAT的自歸約特性 46
5.1.2 CLIQUE的自歸約特性 47
5.1.3 NPC問題都滿足自歸約特性 48
5.2 NPI語(yǔ)言 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——相對(duì)化 54
習(xí)題 56
第6章 對(duì)角化方法 57
6.1 對(duì)角化方法與不可判定問題的存在性 57
6.1.1 可數(shù)集與對(duì)角化方法 57
6.1.2 不可判定問題的存在性 58
6.1.3 停機(jī)問題不可判定 60
6.2 分層定理 62
6.2.1 空間、時(shí)間可構(gòu)造函數(shù) 62
6.2.2 分層定理 63
6.2.3 非確定性時(shí)間分層定理 66
6.3 定理A的證明 67
6.4 Ladner定理的證明 69
6.5 復(fù)雜性理論常用證明方法總結(jié) 70
習(xí)題 70
第7章 空間復(fù)雜性 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
習(xí)題 85
第8章 隨機(jī)化算法與隨機(jī)化復(fù)雜性類 87
8.1 隨機(jī)化算法實(shí)例 87
8.1.1 通信復(fù)雜性 87
8.1.2 多項(xiàng)式恒等測(cè)試 89
8.2 概率圖靈機(jī) 91
8.3 隨機(jī)化復(fù)雜性類 92
8.3.1 單邊錯(cuò)復(fù)雜性類：RP和coRP 92
8.3.2 雙邊錯(cuò)復(fù)雜性類：BPP 94
8.3.3 零邊錯(cuò)復(fù)雜性類：ZPP 96
8.3.4 PP 97
8.4 隨機(jī)化復(fù)雜性類與其他復(fù)雜性類之間的關(guān)系 99
8.5 素?cái)?shù)問題PRIME 101
8.5.1 PRIME∈NP 102
8.5.2 PRIME∈coRP 104
8.5.3 PRIME∈P 105
習(xí)題 106
第9章 密碼學(xué)與復(fù)雜性理論 107
9.1 單向函數(shù) 107
9.2 偽隨機(jī)發(fā)生器 109
9.3 信息論安全與計(jì)算安全 110
第10章 電路復(fù)雜性 111
10.1 布爾電路 111
10.2 電路復(fù)雜性與P/poly復(fù)雜性類 113
10.3 P/poly復(fù)雜性類 115
10.4 一致布爾電路 117
10.5 并行計(jì)算與Nick復(fù)雜性類 118
10.6 BPPP/poly 120
習(xí)題 121
第11章 多項(xiàng)式分層 123
11.1 定義與實(shí)例 123
11.2 PH的內(nèi)部結(jié)構(gòu) 124
11.3 交錯(cuò)式TM與PH的等價(jià)定義 125
11.4 PH坍塌 127
習(xí)題 129
第12章 交互式證明 130
12.1 IP 131
12.2 公開/保密的隨機(jī)性 133
12.3 IP=PSPACE 135
12.4 零知識(shí)證明 141
12.5 概率可驗(yàn)證明(PCP) 143
參考文獻(xiàn) 145
展開全部
書友推薦
- >
姑媽的寶刀
- >
朝聞道
- >
推拿
- >
莉莉和章魚
- >
苦雨齋序跋文-周作人自編集
- >
小考拉的故事-套裝共3冊(cè)
- >
唐代進(jìn)士錄
- >
隨園食單
本類暢銷
