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

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

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

初めてのGraphQL ―Webサービスを作って学ぶ新世代API

by Eve Porcello, Alex Banks, 尾崎 沙耶, あんどうやすし

今日では多くのWebサービスがRESTアーキテクチャスタイルで実装されています。RESTは2000年にフィールディングの論文で提唱された後に爆発的に普及し洗練されてきました。一方で、本書で紹介するGraphQLは2015年にFacebookによって公開されたRESTとは異なるアプローチのアーキテクチャです。GraphQLの最大の特徴はクエリ言語を用いてデータを操作する点です。クエリ言語の表現力の高さによりクライアントは本当に必要なリクエストを送ることができます。本書ではGraphQLの概要とGraphQLを用いたWebサービスの開発方法を実装例に沿って紹介します。認証やファイルアップロードといった実践的なトピックまで踏み込んだGraphQLの実用的な入門書です。

book

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

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

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

book

実用 Go言語 ―システム開発の現場で知っておきたいアドバイス

by 渋川 よしき, 辻 大志郎, 真野 隼記

業務プログラミングの現場でも採用されるようになってきたGo言語。文法はシンプルで学びやすいという特徴を持っていますが、複雑な要件を実現するには、プログラミング言語が提供する構成要素（文法やライブラリ）をさまざまに組み合わせる必要があります。 本書は、そんなGoを使う上でのポイントを単なる文法詳解ではなく「よりGoらしく書くには」「実用的なアプリケーションを書くには」といった観点から紹介します。 構造体やインタフェースの使い方からJSON、CSVファイル、Excel、固定長ファイルの扱い方、またログやテスト、環境構築など現場に即した幅広いトピックについて、「Goらしいプログラムの書き方」をその背景と共に教えてくれる先輩のような書籍です。