計算可能性・計算の複雑さ入門

所蔵情報QRコード

計算可能性・計算の複雑さ入門 / 渡辺治著

資料種別:: 図書[目次DB]
出版情報:: 東京 : 近代科学社, 1992.10
形態:: ix, 226p ; 22cm
シリーズ名:: アルゴリズム・シリーズ ; 3 <BN08210807>
著者名:: 渡辺, 治(1958-) <DA06761462>
ISBN:: 9784764902008 [4764902001]
書誌ID:: BN08210818

子書誌情報

フルテキスト

所蔵情報

他の版・巻

書誌詳細

注記:

参考文献: p193-194

タイトルのヨミ:

ケイサンカノウセイ・ケイサンノフクザツサニュウモン

著者名ヨミ:

ワタナベ, オサム

主題:

アルゴリズム; 数学基礎論

言語:

日本語

目次情報:

1. 問題点とアルゴリズム 1

1.1 問題とは、アルゴリズムとは、そして手に負えない問題とは 1

1.2 準備 8

2. 計算可能性入門 16

2.1 帰納的関数論概観 16

2.2 計算の基本要素 20

2.3 for-times計算可能性 32

2.4 計算不可能性の証明と対角線論法 43

2.5 計算不可能性な関数の例 51

3. 計算可能性の分析 59

3.1 関数から集合へ 59

3.2 枚挙可能集合 64

3.3 クラスRECとクラスRE 70

3.4 還元可能性と完全性 78

3.5 RE-完全集合の構造 86

4. 計算の複雑さ入門 96

4.1 計算の複雑さの理論概観 96

4.2 計算時間の計り方 99

4.3 階層定理 115

5. 代表的な計算量クラス 128

5.1 代表的な時間計算量クラス 128

5.2 クラスNP 135

5.3 計算量クラス間の関係 144

6. 多項式時間計算可能性の分析 152

6.1 多項式時間還元可能性 152

6.2 多項式時間還元可能性にもとづく完全性 163

6.3 NP-完全集合の構造 175

参考文献 193

演習問題の解答 195

索引 223

ひとこと

1:計算の複雑さの理論での用語 15

2:ソフトウェア・サイエンスのニつの顔 58

3:様々な還元可能性 95

4:クラスNPの定義 151

5:構造的解析はどこへ? 192

1. 問題点とアルゴリズム 1

1.1 問題とは、アルゴリズムとは、そして手に負えない問題とは 1

1.2 準備 8

2. 計算可能性入門 16

2.1 帰納的関数論概観 16

2.2 計算の基本要素 20

続きを見る

ブックレビュー

類似資料:

1 図書プログラミングによる計算可能性理論 Arbib, Michael A., 1940-, 甘利, 俊一(1936-), 金谷, 健一(1947-), 川端, 勉, Kfoury, A. J., Moll, Robert N. サイエンス社	7 図書計算可能性入門小林, 孝次郎(1939-) 近代科学社
2 図書計算の複雑さ小林, 孝次郎(1939-) 昭晃堂	8 図書計算論 : 計算可能性とラムダ計算高橋, 正子, 宝来, 正子近代科学社
3 図書計算可能性の理論 Sipser, Michael, 阿部, 正幸, 植田, 広樹, 太田, 和夫 (1954-), 田中, 圭介 (1969-), 藤岡, 淳, 渡辺, 治 (1958-), 田中, 圭介, 渡邊, 治共立出版	9 図書形式論理と計算可能性 = Formal logic and computability 東京大学工学教程編纂委員会, 蓮尾, 一郎, 浅田, 和之丸善出版
4 図書計算可能性の理論 Sipser, Michael, 阿部, 正幸, 植田, 広樹, 藤岡, 淳, 渡辺, 治(1958-), 太田, 和夫(1954-), 田中, 圭介(1969-) 共立出版	10 図書アルゴリズムと計算可能性五十嵐, 善英昭晃堂
5 図書計算論入門 : 計算の基本原理理解のために渡辺, 治(1958-), 米崎, 直樹(1950-), 渡辺, 治, 米崎, 直樹日本評論社	11 図書複雑さの理論 Sipser, Michael, 阿部, 正幸, 植田, 広樹, 太田, 和夫 (1954-), 田中, 圭介 (1969-), 藤岡, 淳, 渡辺, 治 (1958-), 田中, 圭介, 渡邊, 治共立出版
6 図書計算論入門 : 計算の基本原理理解のために渡辺, 治(1958-), 米崎, 直樹(1950-) 日本評論社	12 図書複雑さの理論 Sipser, Michael, 阿部, 正幸, 植田, 広樹, 藤岡, 淳, 渡辺, 治(1958-), 太田, 和夫(1954-), 田中, 圭介(1969-) 共立出版