中圖網小程序
一鍵登錄
更方便
本類五星書更多>
-
>
全國計算機等級考試最新真考題庫模擬考場及詳解·二級MSOffice高級應用
-
>
決戰行測5000題(言語理解與表達)
-
>
軟件性能測試.分析與調優實踐之路
-
>
第一行代碼Android
-
>
JAVA持續交付
-
>
EXCEL最強教科書(完全版)(全彩印刷)
-
>
深度學習
計算理論導引-原書第3版 版權信息
- ISBN：9787111499718
- 條形碼：9787111499718 ; 978-7-111-49971-8
- 裝幀：一般膠版紙
- 冊數：暫無
- 重量：暫無
- 所屬分類：>
計算理論導引-原書第3版 本書特色
本書由計算理論領域的知名權威michaelsipser所撰寫。他以獨特的視角，系統地介紹了計算理論的三個主要內容：自動機與語言、可計算性理論和計算復雜性理論。作者以清新的筆觸、生動的語言給出了寬泛的數學原理，而沒有拘泥于某些低層次的細節。在證明之前，均有“證明思路”，幫助讀者理解數學形式下蘊涵的概念。本書可作為計算機專業高年級本科生和研究生的教材，也可作為教師和研究人員的參考書。
計算理論導引-原書第3版 內容簡介
本書由計算理論領域的知名權威MichaelSipser所撰寫。他以獨特的視角，系統地介紹了計算理論的三個主要內容：自動機與語言、可計算性理論和計算復雜性理論。作者以清新的筆觸、生動的語言給出了寬泛的數學原理，而沒有拘泥于某些低層次的細節。在證明之前，均有“證明思路”，幫助讀者理解數學形式下蘊涵的概念。本書可作為計算機專業高年級本科生和研究生的教材，也可作為教師和研究人員的參考書。
計算理論導引-原書第3版 目錄
introduction to the theory of computation,3e
出版者的話
譯者序
第3版前言
第2版前言
第1版前言
第0章緒論
0 1自動機、可計算性與復雜性
0 1 1計算復雜性理論
0 1 2可計算性理論
0 1 3自動機理論
0 2數學概念和術語
0 2 1集合
0 2 2序列和多元組
0 2 3函數和關系
0 2 4圖
0 2 5字符串和語言
0 2 6布爾邏輯
0 2 7數學名詞匯總
0 3定義、定理和證明
0 4證明的類型
0 4 1構造性證明
0 4 2反證法
0 4 3歸納法
練習
問題
習題選解
**部分自動機與語言
第1章正則語言
1 1有窮自動機
1 1 1有窮自動機的形式化定義
1 1 2有窮自動機舉例
1 1 3計算的形式化定義
1 1 4設計有窮自動機
1 1 5正則運算
1 2非確定性
1 2 1非確定型有窮自動機的形式化定義
1 2 2nfa與dfa的等價性
1 2 3在正則運算下的封閉性
1 3正則表達式
1 3 1正則表達式的形式化定義
1 3 2與有窮自動機的等價性
1 4非正則語言
練習
問題
習題選解
第2章上下文無關文法
2 1上下文無關文法概述
2 1 1上下文無關文法的形式化定義
2 1 2上下文無關文法舉例
2 1 3設計上下文無關文法
2 1 4歧義性
2 1 5喬姆斯基范式
2 2下推自動機
2 2 1下推自動機的形式化定義
2 2 2下推自動機舉例
2 2 3與上下文無關文法的等價性
2 3非上下文無關語言
2 4確定型上下文無關語言
2 4 1dcfl的性質
2 4 2確定型上下文無關文法
2 4 3dpda和dcfg的關系
2 4 4語法分析和lr(k)文法
練習
問題
習題選解
第二部分可計算性理論
第3章丘奇圖靈論題
3 1圖靈機
3 1 1圖靈機的形式化定義
3 1 2圖靈機的例子
3 2圖靈機的變形
3 2 1多帶圖靈機
3 2 2非確定型圖靈機
3 2 3枚舉器
3 2 4與其他模型的等價性
3 3算法的定義
3 3 1希爾伯特問題
3 3 2描述圖靈機的術語
練習
問題
習題選解
第4章可判定性
4 1可判定語言
4 1 1與正則語言相關的可判定性問題
4 1 2與上下文無關語言相關的可判定性問題
4 2不可判定性
4 2 1對角化方法
4 2 2不可判定語言
4 2 3一個圖靈不可識別語言
練習
問題
習題選解
第5章可歸約性
5 1語言理論中的不可判定問題
5 2一個簡單的不可判定問題
5 3映射可歸約性
5 3 1可計算函數
5 3 2映射可歸約性的形式化定義
練習
問題
習題選解
第6章可計算性理論的高級專題
6 1遞歸定理
6 1 1自引用
6 1 2遞歸定理的術語
6 1 3應用
6 2邏輯理論的可判定性
6 2 1一個可判定的理論
6 2 2一個不可判定的理論
6 3圖靈可歸約性
6 4信息的定義
6 4 1極小長度的描述
6 4 2定義的優化
6 4 3不可壓縮的串和隨機性
練習
問題
習題選解
第三部分復雜性理論
第7章時間復雜性
7 1度量復雜性
7 1 1大o和小o記法
7 1 2分析算法
7 1 3模型間的復雜性關系
7 2p類
7 2 1多項式時間
7 2 2p中的問題舉例
7 3np類
7 3 1np中的問題舉例
7 3 2p與np問題
7 4np完全性
7 4 1多項式時間可歸約性
7 4 2np完全性的定義
7 4 3庫克列文定理
7 5幾個np完全問題
7 5 1頂點覆蓋問題
7 5 2哈密頓路徑問題
7 5 3子集和問題
練習
問題
習題選解
第8章空間復雜性
8 1薩維奇定理
8 2pspace類
8 3pspace完全性
8 3 1tqbf問題
8 3 2博弈的必勝策略
8 3 3廣義地理學
8 4l類和nl類
8 5nl完全性
8 6nl等于conl
練習
問題
習題選解
第9章難解性
9 1層次定理
9 2相對化
9 3電路復雜性
練習
問題
習題選解
第10章復雜性理論高級專題
10 1近似算法
10 2概率算法
10 2 1bpp類
10 2 2素數性
10 2 3只讀一次的分支程序
10 3交錯式
10 3 1交錯式時間與交錯式空間
10 3 2多項式時間層次
10 4交互式證明系統
10 4 1圖的非同構
10 4 2模型的定義
10 4 3ip=pspace
10 5并行計算
10 5 1一致布爾電路
10 5 2nc類
10 5 3p完全性
10 6密碼學
10 6 1密鑰
10 6 2公鑰密碼系統
10 6 3單向函數
10 6 4天窗函數
練習
問題
習題選解
參考文獻
索引
展開全部
書友推薦
- >
我從未如此眷戀人間
- >
人文閱讀與收藏·良友文學叢書:一天的工作
- >
朝聞道
- >
【精裝繪本】畫給孩子的中國神話
- >
有舍有得是人生
- >
隨園食單
- >
二體千字文
- >
大紅狗在馬戲團-大紅狗克里弗-助人
本類暢銷
