所蔵

所蔵件数は 1 件です。現在の予約件数は 0 件です。

所蔵場所	請求記号	資料コード	資料区分	帯出区分	状態
閲覧室	/007.1/ｼ/3	117328856	成人一般	可能

ページの先頭へ

資料詳細

タイトル	計算理論の基礎 3
タイトルカナ	ケイサン リロン ノ キソ
著者	Michael Sipser ／著, 田中 圭介 ／監訳, 藤岡 淳 ／監訳, 阿部 正幸 ／訳, 植田 広樹 ／訳, 太田 和夫 ／訳, 田中 圭介 ／訳, 藤岡 淳 ／訳, 渡辺 治 ／訳
著者カナ	シプサ マイケル,タナカ ケイスケ,フジオカ アツシ,アベ マサユキ,ウエダ ヒロキ,オオタ カズオ,タナカ ケイスケ,フジオカ アツシ,ワタナベ オサム
巻の書名	複雑さの理論
出版者	共立出版
出版年	2023.5
ページ数	27p,p330～540 40p
大きさ	21cm
一般件名	オートマトン , 計算量理論
ISBN13桁	978-4-320-12563-6
言語	jpn
分類記号	007.1
内容紹介	計算の理論の主テーマである、オートマトンと言語の理論、計算可能性の理論、計算の複雑さの理論をまとめた、計算理論の教科書。新たな図などを加えた原著第3版を分冊にしたもの。3は複雑さの理論を収録。

ページの先頭へ

目次

7 時間の複雑さ

  7.1 複雑さの測定

  7.2 クラスP

  7.3 クラスNP

  7.4 NP完全性

  7.5 他のNP完全問題

8 領域の複雑さ

  8.1 Savitchの定理

  8.2 クラスPSPACE

  8.3 PSPACE完全性

  8.4 クラスLとクラスNL

  8.5 NL完全性

  8.6 NLとcoNLの等価性

9 問題の扱いにくさ

  9.1 階層定理

  9.2 相対化

  9.3 回路の複雑さ

10 計算の複雑さの理論における先進的な話題

  10.1 近似アルゴリズム

  10.2 確率的アルゴリズム

  10.3 交替性

  10.4 対話証明系

  10.5 並列計算

  10.6 暗号

ページの先頭へ