close
1.

図書

図書
G.J.チャイティン著 ; 黒川利明訳
出版情報: 府中 : エスアイビー・アクセス , 東京 : 星雲社 (発売), 2001.6  158p ; 20cm
所蔵情報: loading…
2.

図書

図書
ツォイクマン・トーマス, 湊真一, 大久保好章共著
出版情報: 東京 : コロナ社, 2009.4  x, 222p ; 21cm
所蔵情報: loading…
3.

図書

図書
G.ミルバーン [著] ; 林一訳
出版情報: 東京 : 岩波書店, 2003.1  xvii, 248p ; 20cm
所蔵情報: loading…
4.

図書

図書
Dewdney, Alexander Keewatin ; 足立, 暁生(1936-)
出版情報: 東京 : 東京電機大学出版局, 1993.2  x, 155p ; 21cm
シリーズ名: チューリングオムニバス : コンピュータサイエンスへの旅 / A. K. デュードニー著 ; 足立暁生訳 ; 第2巻
所蔵情報: loading…
5.

図書

図書
James L. Hein著 ; 神林靖訳
出版情報: [東京] : 翔泳社, 2012.4  x, 213p ; 23cm
シリーズ名: 独習コンピュータ科学基礎 ; 3
所蔵情報: loading…
6.

図書

図書
足立暁生, 西野哲朗著
出版情報: 東京 : 朝倉書店, 1988.8  vii, 172p ; 22cm
所蔵情報: loading…
7.

図書

図書
笠井琢美著
出版情報: 東京 : 近代科学社, 1987.4  iv, 236p ; 22cm
シリーズ名: コンピュータサイエンス大学講座 ; 17
所蔵情報: loading…
8.

図書

図書
G.J. チャイティン著 ; 黒川利明訳
出版情報: 府中 (東京都) : エスアイビー・アクセス , 東京 : 星雲社 (発売), 2001.9  141p ; 20cm
所蔵情報: loading…
9.

図書

図書
岩田茂樹著
出版情報: 東京 : 共立出版, 1995.5  iv, 96p ; 22cm
所蔵情報: loading…
10.

図書

東工大
目次DB

図書
東工大
目次DB
Michael Sipser著 ; 阿部正幸 [ほか] 訳
出版情報: 東京 : 共立出版, 2000.4  xvi, 483p ; 24cm
所蔵情報: loading…
目次情報: 続きを見る
目次 i
Preface to the Japanese Edition iii
翻訳にあたって xi
まえがき
第0章 序論 1
   0.1 オートマトン,計算可能性,複雑さ 1
   複雑さの理論 1
   計算可能性の理論 2
   オートマトン理論 3
   0.2 数学的概念や用語 4
   集合 4
   列と組 6
   関数と関係 8
   グラフ 11
   文字列と言語 15
   Boole論理 16
   数学的な語句の要約 18
   0.3 定義,定理,証明 19
   証明の発見 19
   0.4 証明のタイプ 23
   構成的証明 23
   背理法 24
   帰納法 25
   演習と問題 28
第1部:オートマトンと言語 31
第1章 正規言語 33
   1.1 有限オートマトン 33
   有限オートマトンの形式的な定義 37
   有限オートマトンの例 39
   計算の形式的な定義 43
   有限オートマトンの設計 44
   正規演算 47
   1.2 非決定性 51
   非決定性有限オートマトンの形式的な定義 57
   NFA と DFAの等価性 59
   正規演算の閉包性 64
   1.3 正規表現 68
   正規表現の形式的な定義 69
   有限オートマトンとの等価性 72
   1.4 非正規言語 84
   正規言語に対するポンピング補題 84
   演習と問題 91
第2章 文脈自由文法 99
   2.1 文脈自由文法 100
   文脈自由文法の形式的な定義 102
   文脈自由文法の例 104
   文脈自由文法の設計 105
   曖昧性 106
   Chomsky の標準形 108
   2.2 プッシュダウン・オートマトン 111
   プッシュダウン・オートマトンの形式的な定義 113
   プッシュダウン・オートマトンの例 114
   文脈自由文法との等価性 117
   2.3 非文脈自由言語 126
   文脈自由言語に対するポンピング補題 127
   演習と問題 132
第2部:計算可能性の理論 137
第3章 Church-Turing の提唱 139
   3.1 Turing 機械 139
   Turing 機械の形式的な定義 142
   Turing 機械の例 145
   3.2 Turing 機械の変型 151
   複数テープTuring機械 152
   非決定性Turing機械 154
   列挙装置 157
   他のモデルとの等価性 158
   3.3 アルゴリズムの定義 159
   Hilbertの問題 159
   Turing機械を記述するための用語 162
   演習と問題 164
第4章 判定可能性 169
   4.1 判定可能な言語 170
   正規言語に関連する判定可能問題 170
   文脈自由言語に関連する判定可能問題 174
   4.2 停止問題 178
   対角線論法 180
   停止問題の判定不可能性 185
   Turing認識不可能な言語 188
   演習と問題 189
第5章 帰着可能性 193
   5.1 言語理論における判定不可能問題 194
   計算履歴を用いた帰着 199
   5.2 単純な判定不可能問題 207
   5.3 写像帰着可能性 214
   計算可能な関数 215
   写像帰着可能性の形式的な定義 215
   演習と問題 220
第6章 計算可能性の理論における先進的な話題 223
   6.1 再帰定理 223
   自己参照 224
   再帰定理のための用語 228
   応用 228
   6.2 数理論理における判定可能性 231
   判定可能な理論 234
   判定不可能性の理論 237
   6.3 Turing帰着可能性 240
   6.4 情報の定義 242
   最小長記述 243
   定義の最適性 247
   圧縮不可能な文字とランダム性 248
   演習と問題 251
第3部:複雑さの理論 255
第7章 時間の複雑さ 257
   7.1 複雑さの測定 257
   big-O記法とsmall-o記法 259
   アルゴリズムの解析 261
   モデル間の複雑さの関係 265
   7.2 クラスP 268
   多項式時間 269
   Pに属する問題の例 271
   7.3 クラスNP 277
   NP に属する問題の例 282
   P vs.NP問題 285
   7.4 NP完全性 286
   多項式時間帰着可能性 287
   NP 完全性の定義 292
   Cook-Levinの定理 292
   7.5 他のNP完全問題 300
   頂点被覆問題 301
   Hamilton パス問題 302
   部分和問題 309
   演習と問題
第8章 領域の複雑さ 319
   8.1 Savitchの定理 322
   8.2 クラスPSPACE 325
   8.3 PSPACE完全 326
   TQBF問題 327
   ゲームの必勝法 332
   一般化された「しりとり」ゲーム 334
   8.4 クラスLとクラスNL 341
   8.5 NL完全性 344
   グラフ中の検索 346
   8.6 NLとcoNTの等価性 348
   演習と問題 351
第9章 問題の扱いにくさ 355
   9.1 階層定理 356
   指数領域完全性 365
   9.2 相対化 371
   対角線論法の限界 373
   9.3 回路の複雑さ 376
   演習と問題 386
第10章計算の複雑さの理論における先進的な話題 389
   10.1 近似アルゴリズム 389
   10.2 確率的アルゴリズム 392
   クラスBPP 392
   素数性 396
   一回読み出し分岐プログラム 402
   10.3 交替性 407
   交替性時間と交替性領域 408
   多項式時間階層 413
   10.4 対話証明系 414
   グラフの非同型性 415
   モデルの定義 416
   IPとPSPACEの等価性 417
   10.5 並列計算 430
   一様Boole回路 430
   クラスNC 432
   P完全性 435
   10.6 暗号 436
   秘密鍵 437
   分開鍵暗号系 438
   一方向性関数 439
   落し戸関数 441
   演習と問題 443
参考文献 445
欧文索引(対訳付) 453
和文索引(対訳付) 470
目次 i
Preface to the Japanese Edition iii
翻訳にあたって xi
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼