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

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

by Tom Stuart, 笹田 耕一, 笹井 崇司
Released September 2014
Publisher(s): O'Reilly Japan, Inc.
ISBN: 9784873116976

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

本書は計算理論をRubyでわかりやすく紹介する書籍です。コンピュータサイエンスの主要なテーマである「計算とは何か」という問いに対して、難しい数学の知識を利用をせず、Rubyを使って実際にプログラムを作りながら解説します。さらに、なぜこれらのアイデアが大切なのか、そしてそのアイデアは我々の日常的なプログラミングにどう関係していくのかを解き明かしていきます。日本語版ではまつもとゆきひろさんによる「日本語版まえがき」を収録。プログラミングの根底にある理論を学ぶことで、より広く深くプログラミングを考えたいプログラマ必携の一冊です。

Table of contents

  1. 日本語版まえがき
  2. はじめに (1/2)
  3. はじめに (2/2)
  4. 1章 Rubyひとめぐり
    1. 1.1 対話型 Rubyシェル
    2. 1.2 値
      1. 1.2.1 基本データ
      2. 1.2.2 データ構造
      3. 1.2.3 Proc
    3. 1.3 制御フロー
    4. 1.4 オブジェクトとメソッド
    5. 1.5 クラスとモジュール
    6. 1.6 その他の機能
      1. 1.6.1 ローカル変数と代入
      2. 1.6.2 文字列の式展開
      3. 1.6.3 オブジェクトのインスペクト
      4. 1.6.4 文字列のプリント
      5. 1.6.5 可変長引数のメソッド
      6. 1.6.6 ブロック
      7. 1.6.7 Enumerable
      8. 1.6.8 Struct
      9. 1.6.9 モンキーパッチング
      10. 1.6.10 定数の定義
      11. 1.6.11 定数の削除
  5. 第I部 プログラムと機械
  6. 2章 プログラムの意味
    1. 2.1 「意味」の意味
    2. 2.2 構文
    3. 2.3 操作的意味論
      1. 2.3.1 スモールステップ意味論
      2. 2.3.2 ビッグステップ意味論 (1/2)
      3. 2.3.2 ビッグステップ意味論 (2/2)
    4. 2.4 表示的意味論
      1. 2.4.1 式
      2. 2.4.2 文
      3. 2.4.3 応用
    5. 2.5 実際の形式意味論
      1. 2.5.1 形式
      2. 2.5.2 意味の理解
      3. 2.5.3 その他のスタイル
    6. 2.6 パーサの実装
  7. 3章 最も単純なコンピュータ
    1. 3.1 決定性有限オートマトン
      1. 3.1.1 状態、規則、入力
      2. 3.1.2 出力
      3. 3.1.3 決定性
      4. 3.1.4 シミュレーション
    2. 3.2 非決定性有限オートマトン
      1. 3.2.1 非決定性
      2. 3.2.2 自由移動
    3. 3.3 正規表現
      1. 3.3.1 構文
      2. 3.3.2 意味論 (1/2)
      3. 3.3.2 意味論 (2/2)
      4. 3.3.3 パース
    4. 3.4 等価性 (1/3)
    5. 3.4 等価性 (2/3)
    6. 3.4 等価性 (3/3)
  8. 4章 能力を高める
    1. 4.1 決定性プッシュダウン・オートマトン
      1. 4.1.1 ストレージ
      2. 4.1.2 規則
      3. 4.1.3 決定性
      4. 4.1.4 シミュレーション (1/2)
      5. 4.1.4 シミュレーション (2/2)
    2. 4.2 非決定性プッシュダウン・オートマトン
      1. 4.2.1 シミュレーション
      2. 4.2.2 非等価性
    3. 4.3 プッシュダウン・オートマトンによるパース
      1. 4.3.1 字句解析
      2. 4.3.2 構文解析
      3. 4.3.3 実用性
    4. 4.4 どれだけ能力があるか
  9. 5章 究極の機械
    1. 5.1 決定性チューリングマシン
      1. 5.1.1 ストレージ
      2. 5.1.2 規則
      3. 5.1.3 決定性
      4. 5.1.4 シミュレーション
    2. 5.2 非決定性チューリングマシン
    3. 5.3 最大の能力
      1. 5.3.1 内部ストレージ
      2. 5.3.2 サブルーチン
      3. 5.3.3 複数のテープ
      4. 5.3.4 多次元のテープ
    4. 5.4 汎用機械
      1. 5.4.1 エンコード
      2. 5.4.2 シミュレーション
  10. 第II部 訇算と訇算可能性
  11. 6章 無からのプログラミング
    1. 6.1 ラムダ訇算をまねる
      1. 6.1.1 Procの利用
      2. 6.1.2 問題
      3. 6.1.3 数
      4. 6.1.4 ブール値
      5. 6.1.5 述語
      6. 6.1.6 ペア
      7. 6.1.7 数値演算
      8. 6.1.8 リスト
      9. 6.1.9 文字列
      10. 6.1.10 解答
      11. 6.1.11 高度なプログラミングテクニック (1/2)
      12. 6.1.11 高度なプログラミングテクニック (2/2)
    2. 6.2 ラムダ訇算の実装
      1. 6.2.1 構文
      2. 6.2.2 意味論
      3. 6.2.3 パース
  12. 7章 至るところにある万能性
    1. 7.1 ラムダ訇算
    2. 7.2 部分再帰関数 (1/2)
    3. 7.2 部分再帰関数 (2/2)
    4. 7.3 SKIコンビネータ訇算 (1/2)
    5. 7.3 SKIコンビネータ訇算 (2/2)
    6. 7.4 Iota
    7. 7.5 タグシステム (1/2)
    8. 7.5 タグシステム (2/2)
    9. 7.6 循環タグシステム (1/2)
    10. 7.6 循環タグシステム (2/2)
    11. 7.7 コンウェイのライフゲーム
    12. 7.8 ルール 110
    13. 7.9 ウルフラムの 2,3チューリングマシン
  13. 8章 不可能なプログラム
    1. 8.1 厳然たる事実
      1. 8.1.1 万能システムはアルゴリズムを実行できる
      2. 8.1.2 プログラムはチューリングマシンの代わりになる
      3. 8.1.3 コードはデータである
      4. 8.1.4 万能システムは永久にループできる (1/2)
      5. 8.1.4 万能システムは永久にループできる (2/2)
      6. 8.1.5 プログラムは自己参照できる
    2. 8.2 決定可能性
    3. 8.3 停止性問題
      1. 8.3.1 停止性チェッカーの構築
      2. 8.3.2 決してうまくいかない
    4. 8.4 その他の決定不能な問題
    5. 8.5 残念なこと
    6. 8.6 なぜ起こるのか
    7. 8.7 訇算不能性に対処する
  14. 9章 おもちゃの国のプログラミング
    1. 9.1 抽象解釈
      1. 9.1.1 ルート訇画
      2. 9.1.2 抽象化：符号の掛け算
      3. 9.1.3 安全と近似：符号の足し算
    2. 9.2 静的意味論
      1. 9.2.1 実装
      2. 9.2.2 利点と制限
    3. 9.3 応用
  15. あとがき
  16. 監訳者あとがき
  17. 索引 (1/2)
  18. 索引 (2/2)

Product information

  • Title: アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで
  • Author(s): Tom Stuart, 笹田 耕一, 笹井 崇司
  • Release date: September 2014
  • Publisher(s): O'Reilly Japan, Inc.
  • ISBN: 9784873116976

You might also like

book

ハイパフォーマンス ブラウザネットワーキング ―ネットワークアプリケーションのためのパフォーマンス最適化

by Ilya Grigorik, 和田 祐一郎／株式会社プログラミングシステム社

現代のアプリケーションエンジニアは、UIやデータ処理、開発言語、プラットフォームの仕様や癖だけでなく、サーバやネットワークについても、上から下まで、表から裏まで広く知ることを求められます。本書は「ブラウザ」に関連し、インターネットで使用されるさまざまなネットワーク技術をまとめたものです。HTTP/2.0やWebRTCなどの最新技術、WebSocketやXMLHttpRequestなどのブラウザAPI、そしてそれらの土台となるTCPやUDPやトランスポート層についてまでを幅広くカバーします。また改善前後の性能・速さを可能な限り具体化し、それぞれの場面においてのパフォーマンス改善幅を示します。

book

Pythonによるデータ分析入門 第2版 ―NumPy、pandasを使ったデータ処理

by Wes McKinney, 瀬戸山 雅人, 小林 儀匡, 滝口 開資

NumPy、SciPy、pandas、Matplotlib、Jupyterをはじめ、高機能で使いやすい数学・科学計算用ライブラリが充実しているPythonは、科学計算、統計解析、機械学習のみならず、金融や経済分野でも広く利用されています。本書はPythonの代表的なデータ分析ツール、pandasの開発者Wes McKinneyによる、データ分析を行うための基本を網羅しています。すべてのサンプルコードはダウンロード可能で、Jupyter Notebookで対話的に試し、実際に手を動かしながら知識を確実なものにすることが可能です。Python 3に対応した待望の改訂版です。

book

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック

by Dustin Boswell, Trevor Foucher, 角 征典

美しいコードを見ると感動する。優れたコードは見た瞬間に何をしているかが伝わってくる。そういうコードは使うのが楽しいし、自分のコードもそうあるべきだと思わせてくれる。本書の目的は、君のコードを良くすることだ。（本書「はじめに」より） コードは理解しやすくなければならない。本書はこの原則を日々のコーディングの様々な場面に当てはめる方法を紹介します。名前の付け方、コメントの書き方など表面上の改善について。コードを動かすための制御フロー、論理式、変数などループとロジックについて。またコードを再構成するための方法。さらにテストの書き方などについて、楽しいイラストと共に説明しています。日本語版ではRubyやgroongaのコミッタとしても著名な須藤功平氏による解説を収録。

book

レガシーコードからの脱却 ―ソフトウェアの寿命を延ばし価値を高める9つのプラクティス

by David Scott Bernstein, 吉羽 龍太郎, 永瀬 美穂, 原田 騎郎, 有野 雅士

レガシーコードとは、バグを多く含み、壊れやすく拡張が難しいコードを指します。このようなコードの保守と管理には多大な労力がつぎ込まれることになります。しかも一度作ってしまったレガシーコードの質を上げるには、初めから質の高いコードを作るよりも膨大なコストがかかります。 本書では、ソフトウェア開発において、初めからレガシーコードを作りださないためのプラクティスを9つ挙げて解説します。プロダクトオーナーは目的を語り、やり方は開発者に任せること、小さなバッチで開発を進めること、継続的に統合すること、チームメンバーで協力することなど、日々の開発に取り入れる考え方と具体的な実践について各章で分かりやすく解説します。 信頼性や拡張性が高いソフトウェアをリリースしたい開発者、運用管理者、マネージャに必携の一冊です。