株式会社サイエンス社 株式会社新世社 株式会社数理工学社
ホーム 会社案内 社員募集 ご意見・ご感想 リンク 当サイトの利用  



Computer Science Library 4

C言語による
「計算の理論」

鹿島 亮(東京工業大学准教授) 著

定価:2,268円(本体2,100円+税)
発行:サイエンス社
発行日:2008-10-10
ISBN 978-4-7819-1214-1 / A5判/224頁


<内容詳細>
計算の理論とはコンピュータの動作の普遍的な原理に関する数学である.本書はこの理論の本格的な内容を,仮想的なモデルではなく現実のC言語を使用してわかりやすく正確に説明する教科・参考書である.

<目次>
第1章 導入
  1.1 一番大切な定義
  1.2 自然数,表記の約束
  1.3 部分関数
  1.4 関数プログラム
  1.5 現実のC言語との相違
  1.6 再び,一番大切な定義
  1.7 計算の理論の概観
  第1章の章末問題

第2章 ジャンププログラム
  2.1 準備
  2.2 ジャンププログラム
  2.3 ジャンププログラムへの書換え
  2.4 特定形プログラム
  第2章の章末問題

第3章 万能関数
  3.1 自然数のペアのコード化
  3.2 自然数の有限列のコード化
  3.3 ジャンププログラムのコード化
  3.4 万能関数
  第3章の章末問題

第4章 計算可能・不可能の境界付近
  4.1 対角線論法
  4.2 停止問題の決定不可能性
  4.3 パラメータ定理
  4.4 再帰定理
  4.5 ライスの定理
  第4章の章末問題

第5章 原始帰納的関数
  5.1 原始帰納的関数とは
  5.2 原始帰納的関数の定義
  5.3 具体例
  5.4 while文のないプログラム
  5.5 限定反復プログラム
  5.6 限定反復プログラムから原始帰納的関数へ
  5.7 原始帰納的でない計算可能関数
  第5章の章末問題

第6章 帰納的部分関数
  6.1 準備
  6.2 帰納的部分関数,帰納的述語
  6.3 「計算可能」との同値性
  6.4 クリーネの標準形定理
  6.5 最小化に関する注意
  第6章の章末問題

第7章 半決定可能集合
  7.1 集合を扱うことについて
  7.2 集合を半決定するプログラム
  7.3 集合を枚挙するプログラム
  7.4 さまざまな同値な条件
  第7章の章末問題

第8章 計算不可能性の度合い
  8.1 量化の重なり具合による比較
  8.2 算術的階層
  8.3 万能述語,そして算術的階層が潰れないこと
  8.4 還元可能性による比較
  8.5 完全集合
  第8章の章末問題

第9章 チューリング機械
  9.1 チューリング機械とは
  9.2 正確な定義
  9.3 具体例
  9.4 自然数上の関数の計算可能性
  9.5 チューリング機械の変種
  9.6 万能チューリング機械
  9.7 計算不可能性:ビジービーバー関数,ポストの対応問題
  第9章の章末問題

第10章 P≠NP予想
  10.1 ハミルトン閉路問題
  10.2 多項式時間計算可能性
  10.3 非決定性チューリング機械
  10.4 P≠NP予想の正確な内容
  10.5 多項式時間還元可能性
  10.6 NP完全問題
  第10章の章末問題

第11章 ラムダ計算
  11.1 導入
  11.2 ラムダ項
  11.3 ベータ簡約
  11.4 チャーチ-ロッサーの定理
  11.5 簡約の標準的な順番と最左簡約
  11.6 自然数上の関数の計算と決定不可能問題
  11.7 型付きラムダ計算
  第11章の章末問題

付録A チューリング機械シミュレータ
付録B ラムダ計算の定理の詳細な証明
  B.1 チャーチ-ロッサーの定理
  B.2 簡約順番の標準化定理
  B.3 帰納的部分関数のラムダ項による計算

章末問題略解
参考文献
索引