アンダースタンディング コンピュテーション 単純な機械から不可能なプログラムまで

Rubyでコンピュータサイエンスの基礎である計算理論とコンパイラ理論を学ぶ書籍!

このような方におすすめ

職業エンジニア。学生。本職の研究者が初学者啓蒙の教科書として利用。
  • 著者Tom Stuart/笹田 耕一/笹井 崇司
  • 定価3,456 (本体3,200 円+税)
  • B5変 336頁 2014/09発行
  • ISBN978-4-87311-697-6
  • 定価
  • ポイント0
  • 数量

※本体価格は変更される場合があります。
※通常2〜3日以内で発送いたします。

  • 概要
  • 主要目次
  • 詳細目次

本書は、Rubyでコンピュータサイエンスの計算理論とコンパイラ理論を学ぶための書籍です。計算理論とは、「計算可能な手続きとは何か」を学ぶ領域です。チューリング機械やラムダ計算などを用いて「計算を組み立てる部品」を定義し、その部品の組み合わせでアルゴリズムを組み立てる方法と、組み立てたアルゴリズムを操作する方法を学びます。コンパイラ理論は、プログラミング言語の処理系の基礎理論です。


    
目次

日本語版まえがき
はじめに

1章 Rubyひとめぐり
1.1 対話型 Rubyシェル
1.2 値
1.2.1 基本データ
1.2.2 データ構造
1.2.3 Proc
1.3 制御フロー
1.4 オブジェクトとメソッド
1.5 クラスとモジュール
1.6 その他の機能
1.6.1 ローカル変数と代入
1.6.2 文字列の式展開
1.6.3 オブジェクトのインスペクト
1.6.4 文字列のプリント
1.6.5 可変長引数のメソッド
1.6.6 ブロック
1.6.7 Enumerable
1.6.8 Struct
1.6.9 モンキーパッチング
1.6.10 定数の定義
1.6.11 定数の削除

第I部 プログラムと機械
2章 プログラムの意味
2.1 「意味」の意味
2.2 構文
2.3 操作的意味論
2.3.1 スモールステップ意味論
2.3.2 ビッグステップ意味論
2.4 表示的意味論
2.4.1 式
2.4.2 文
2.4.3 応用
2.5 実際の形式意味論
2.5.1 形式
2.5.2 意味の理解
2.5.3 その他のスタイル
2.6 パーサの実装

3章 最も単純なコンピュータ
3.1 決定性有限オートマトン
3.1.1 状態、規則、入力
3.1.2 出力
3.1.3 決定性
3.1.4 シミュレーション
3.2 非決定性有限オートマトン
3.2.1 非決定性
3.2.2 自由移動
3.3 正規表現
3.3.1 構文
3.3.2 意味論
3.3.3 パース
3.4 等価性

4章 能力を高める
4.1 決定性プッシュダウン・オートマトン
4.1.1 ストレージ
4.1.2 規則
4.1.3 決定性
4.1.4 シミュレーション
4.2 非決定性プッシュダウン・オートマトン
4.2.1 シミュレーション
4.2.2 非等価性
4.3 プッシュダウン・オートマトンによるパース
4.3.1 字句解析
4.3.2 構文解析
4.3.3 実用性
4.4 どれだけ能力があるか

5章 究極の機械
5.1 決定性チューリングマシン
5.1.1 ストレージ
5.1.2 規則
5.1.3 決定性
5.1.4 シミュレーション
5.2 非決定性チューリングマシン
5.3 最大の能力
5.3.1 内部ストレージ
5.3.2 サブルーチン
5.3.3 複数のテープ
5.3.4 多次元のテープ
5.4 汎用機械
5.4.1 エンコード
5.4.2 シミュレーション

第II部 計算と計算可能性
6章 無からのプログラミング
6.1 ラムダ計算をまねる
6.1.1 Procの利用
6.1.2 問題
6.1.3 数
6.1.4 ブール値
6.1.5 述語
6.1.6 ペア
6.1.7 数値演算
6.1.8 リスト
6.1.9 文字列
6.1.10 解答
6.1.11 高度なプログラミングテクニック
6.2 ラムダ計算の実装
6.2.1 構文
6.2.2 意味論
6.2.3 パース

7章 至るところにある万能性
7.1 ラムダ計算
7.2 部分再帰関数
7.3 SKIコンビネータ計算
7.4 Iota
7.5 タグシステム
7.6 循環タグシステム
7.7 コンウェイのライフゲーム
7.8 ルール 110
7.9 ウルフラムの 2,3チューリングマシン

8章 不可能なプログラム
8.1 厳然たる事実
8.1.1 万能システムはアルゴリズムを実行できる
8.1.2 プログラムはチューリングマシンの代わりになる
8.1.3 コードはデータである
8.1.4 万能システムは永久にループできる
8.1.5 プログラムは自己参照できる
8.2 決定可能性
8.3 停止性問題
8.3.1 停止性チェッカーの構築
8.3.2 決してうまくいかない
8.4 その他の決定不能な問題
8.5 残念なこと
8.6 なぜ起こるのか
8.7 計算不能性に対処する

9章 おもちゃの国のプログラミング
9.1 抽象解釈
9.1.1 ルート計画
9.1.2 抽象化:符号の掛け算
9.1.3 安全と近似:符号の足し算
9.2 静的意味論
9.2.1 実装
9.2.2 利点と制限
9.3 応用

あとがき
監訳者あとがき