contents memorandum はてな

目次とメモを置いとく場

『入門コンピュータ科学―― ITを支える技術と理論の基礎知識』(J. Glenn Brookshear[著] 神林靖,長尾高弘[訳] KADOKAWA 2014//2012//1985)

原題:Computer Science: An overview (11th edition)
著者:J. Glenn Brookshear(1944-) 計算理論。Marquette University 数学統計計算機科学科 名誉教授。
訳者:神林 靖[かんばやし・やすし] (1958-) 日本工業大学 情報工学科 准教授。計算理論、分散システム。
訳者:長尾 高弘[ながお・たかひろ] (1960-) ㈱ロングテール社長。翻訳。詩作。
NDC:007 情報科学
NDC:549.8 固体電子工学:半導体素子,セレン,ゲルマニウム,シリコン




【目次】
コロフォン [004]
まえがき(J.G.B.) [005-010]
  読者対象 
  第11版で加えたもの 
  本書の構成 
  先生方へのメッセージ 
  教科書としての特徴 
  学生へのメッセージ 
  謝辞 
訳者まえがき(2013年10月 訳者代表 神林靖) [011-012]
目次 [013-022]


第0章 序章 023
0.1 アルゴリズムの役割 024
0.2 計算の歴史 026
0.3 アルゴリズムの科学 030
0.4 抽象化 032
0.5 本書の構成 032
0.6 社会的影響 034

社会問題 036
参考文献 037


第1章 データストレージ 039
1.1 ビットとその格納 040
  1.1.1 プール演算
  1.1.2 ゲートとフリップフロップ
  1.1.3 16進記法
1.2 メインメモリ 046
  1.2.1 メモリ構成
  1.2.2 メモリ容量を計る
1.3 マスストレージ 048
  1.3.1 磁気システム 
  1.3.2 光学システム
  1.3.3 フラッシュドライブ 
  1.3.4 ファイルの格納と取出し
1.4 ビットパターンとして情報を表現する 054
  1.4.1 テキストを表現する 
  1.4.2 数値を表現する
  1.4.3 画像を表現する
  1.4.4 音声を表現する
1.5 2進数の体系 060
  1.5.1 2進記法
  1.5.2 2進加算
  1.5.3 2進法による小数(分数)
1.6 整数を格納する 065
  1.6.1 2の補数記法
  1.6.2 エクセス記法
1.7 小数を格納する 070
  1.7.1 浮動小数点記法
  1.7.2 打切り誤差
1.8 データ圧縮 074
  1.8.1 汎用データ圧縮技法 
  1.8.2 画像を圧縮する
  1.8.3 音声とビデオを圧縮する
1.9 通信エラー 079
  1.9.1 パリティビット
  1.9.2 エラー訂正符号

演習問題 083
社会問題 087
参考文献 088


第2章 データ操作 089
2.1 コンピュータアーキテクチャ 090
  2.1.1 CPUの基本
  2.1.2 コンピュータの概念
2.2 マシン語 093
  2.2.1 命令の種類
2.3 プログラムの実行 098
  2.3.1 プログラム実行の例
  2.3.2 データとしてのプログラム
2.4 算術論理命令 105
  2.4.1 論理演算
  2.4.2 ローテーションとシフト演算
  2.4.3 算術演算
2.5 他の装置との通信 109
  2.5.1 コントローラの役割
  2.5.2 ダイレクトメモリアクセス
  2.5.3 ハンドシェーキング
  2.5.4 よく使用される通信経路
  2.5.5 通信速度
2.6 他のアーキテクチャ 113
  2.6.1 パイプライン
  2.6.2 マルチプロセッサマシン 

演習問題 115
社会問題 120
参考文献 121


第3章 オペレーティングシステム 123
3.1 オペレーティングシステムの歴史 124
3.2 オペレーティングシステムアーキテクチャ 128
  3.2.1 ソフトウェア
  3.2.2 オペレーティングシステムの構成要素
  3.2.3 オペレーティングシステムを起動する
3.3 マシンの動作を調整する 135
  3.3.1 プロセスの概念
  3.3.2 プロセス管理
3.4 プロセス間の競合を調整する 138
  3.4.1 セマフォ
  3.4.2 デッドロック
3.5 セキュリティ 143
  3.5.1 外部からの攻撃
  3.5.2 内部からの攻撃

演習問題 145
社会問題 148
参考文献 149


第4章 ネットワークとインターネット 151
4.1 ネットワークの基礎 152
  4.1.1 ネットワークの分類
  4.1.2 プロトコル
  4.1.3 ネットワークを組み合わせる
  4.1.4 通信を処理する手法
  4.1.5 分散システム
4.2 インターネット 161
  4.2.1 インターネットアーキテクチャ
  4.2.2 インターネットアドレッシング
  4.2.3 インターネットアプリケーション
4.3 ワールドワイドウェブ 170
  4.3.1 ウェブの実装
  4.3.2 HTML
  4.3.3 XML
  4.3.4 クライアントサイドアクティビティとサーバサイドアクティビティ
4.4 インターネットプロトコル 178
  4.4.1 インターネットソフトウェアの階層的アプローチ 
  4.4.2 TCP/IPプロトコルスイート
4.5セキュリティ 184
  4.5.1 攻撃の形式
  4.5.2 保護と予防
  4.5.3 暗号
  4.5.4 ネットワークセキュリティへの法的アプローチ

演習問題 192
社会問題 194
参考文献 195


第5章 アルゴリズム 197
5.1 アルゴリズムの概念 198
  5.1.1 インフォーマルな復習
  5.1.2 アルゴリズムの形式的定義 
  5.1.3 アルゴリズムの抽象的性質
5.2 アルゴリズムの表現 201
  5.2.1 基本命令
  5.2.2 擬似コード
5.3 アルゴリズムの発見 208
  5.3.1 問題解決の技法
  5.3.2 足がかりを得る
5.4 繰返し構造 214
  5.4.1 逐次探索のアルゴリズム
  5.4.2 ループ制御
  5.4.3 挿入法による整列アルゴリズム
5.5 再帰構造 223
  5.5.1 二分探索アルゴリズム
  5.5.2 再帰制御
5.6 効率性と正当性 230
  5.6.1 アルゴリズムの効率性
  5.6.2 ソフトウェアの検証

演習問題 239
社会問題 243
参考文献 244


第6章 プログラミング言語 245
6.1 歴史的展望 246
  6.1.1 初期世代
  6.1.2 マシン独立
  6.1.3 プログラミングパラダイム
6.2 伝統的なプログラミング概念 254
  6.2.1 変数とデータ型
  6.2.2 データ構造
  6.2.3 定数とリテラル
  6.2.4 代入文
  6.2.5 制御文
  6.2.6 コメント
6.3 手続きユニット 265
  6.3.1 手続き
  6.3.2 引数
  6.3.3 関数
6.4 言語の実装 272
  6.4.1 翻訳プロセス
  6.4.2 ソフトウェア開発パッケージ
6.5 オブジェクト指向プログラミング 280
  6.5.1 クラスとオブジェクト
  6.5.2 コンストラク
  6.5.3 追加の機能
6.6 並行動作のプログラミング 286
6.7 宣言型プログラミング 288
  6.7.1 論理推論
  6.7.2 Prolog

演習問題 294
社会問題 298
参考文献 299


第7章 ソフトウェア工学 301
7.1 ソフトウェア工学という学問 302
7.2 ソフトウェアライフサイクル 304
  7.2.1 サイクル全体
  7.2.2 伝統的な開発フェーズ
7.3 ソフトウェア工学の方法論 308
7.4 モジュール性 310
  7.4.1 モジュールによる実装
  7.4.2 結合度
  7.4.3 凝集度
  7.4.4 情報隠蔽
  7.4.5 コンポーネント
7.5 ツール 317
  7.5.1 伝統的な技法
  7.5.2 統一モデリング言語
  7.5.3 デザインパターン
7.6 品質保証 324
  7.6.1 品質保証の範囲
  7.6.2 ソフトウェアテスト
7.7 ドキュメンテーション 327
7.8 ヒューマンマシンインタフェース 329
7.9 ソフトウェアの所有権と責任 332

演習問題 333
社会問題 336
参考文献 337


第8章 データ抽象 339
8.1 基本データ構造 340
  8.1.1 配列
  8.1.2 リスト、スタック、キュー
  8.1.3 木
8.2 関連する概念 343
  8.2.1 抽象化再訪
  8.2.2 静的構造と動的構造
  8.2.3 ポインタ
8.3 データ構造の実装 345
  8.3.1 配列と構造体を格納する
  8.3.2 リストを格納する
  8.3.3 スタックとキューを格納する
  8.3.4 二分木を格納する
  8.3.5 データ構造を操作する
8.4 ケーススタディ 358
8.5 データ型をカスタマイズする 363
  8.5.1 ユーザ定義のデータ型
  8.5.2 抽象データ型
8.6 クラスとオブジェクト 366
8.7 マシン語におけるポインタ 368

演習問題 370
社会問題 374
参考文献 375


第9章 データベースシステム 377
9.1 データベースの基礎 378
  9.1.1 データベースの重要性 
  9.1.2 スキーマの役割 
  9.1.3 データベースの管理システム 
  9.1.4 データベースモデル
9.2 関係モデル 382
  9.2.1 関係設計の問題点
  9.2.2 関係演算
  9.2.3 SQL
9.3 オブジェクト指向データベース 392
9.4 データベースの完全性を保つ 394
  9.4.1 コミットとロールバックプロトコル
  9.4.2 ロック法
9.5 伝統的ファイル構造 398
  9.5.1 順編成ファイル
  9.5.2 索引ファイル
  9.5.3 ハッシュファイル
9.6 データマイニング 405
9.7 データベース技術の社会的影響 407

演習問題 409
社会問題 413
参考文献 414


第10章 コンピュータグラフィックス 415
10.1 コンピュータグラフィックスの範囲 416
10.2 3Dグラフィックスの概要 417
10.3 モデリング 419
  10.3.1 個別オブジェクトのモデリング
  10.3.2 シーン全体のモデリング
10.4 レンダリング 427
  10.4.1 光と表面の相互作用
  10.4.2 クリッピング、走査変換、隠面消去
  10.4.3 シェーディング
  10.4.4 レンダリングパイプラインのハードウェア
10.5 グローバルライティングの処理 436
  10.5.1 レイトレーシング
  10.5.2 ラジオシティ
10.6 アニメーション 439
  10.6.1 アニメーションの基礎
  10.6.2 運動学と動力学
  10.6.3 アニメーションのプロセス 

演習問題 443
社会問題 445
参考文献 446


第11章 人工知能 447
11.1 知能とマシン 448
  11.1.1 知的エージェント
  11.1.2 研究方法
  11.1.3 チューリングテスト
11.2 認識 452
  11.2.1 画像理解
  11.2.2 言語処理
11.3 推論 458
  11.3.1 プロダクションシステム
  11.3.2 探索木
  11.3.3 ヒューリスティック
11.4 その他の研究領域 468
  11.4.1 知識の表現と操作
  11.4.2 学習
  11.4.3 遺伝的アルゴリズム
11.5 人工ニューラルネットワーク 473
  11.5.1 基本的性質
  11.5.2 人工ニューラルネットワークを訓練する
  11.5.3 連想記憶
11.6 ロボット工学 480
11.7 社会的影響を考える 482

演習問題 484
社会問題 488
参考文献 490


第12章 計算の理論 491
12.1 関数とその計算 492
12.2 チューリングマシン 494
  12.2.1 チューリングマシンの基礎 494
  12.2.2 チャーチ=チューリングマシンの提唱 497
12.3 万能プログラミング言語 497
  12.3.1 Bare Bones言語
  12.3.2 Bare Bones によるプログラミング
  12.3.3 Bare Bones 言語の万能性
12.4 計算不能関数 503
  12.4.1 停止問題
  12.4.2 停止問題の解決不能
12.5 問題の複雑さ 508
  12.5.1 問題の複雑さを計測する
  12.5.2 多項式問題対非多項式問題
  12.5.3 NP問題
12.6 公開鍵暗号 515
  12.6.1 剩余記法
  12.6.2 RSA 公開鍵暗号

演習問題 519
社会問題 522
参考文献 523


付録A ASCII 525
付録B 2の補数表現を扱う回路 527
付録C 単純なマシン語 531
  マシンアーキテクチャ/マシンの言語
付録D 高レベルプログラミング言語 533
  Ada/C/C++C#FortranJava
付録E 繰返し構造と再帰構造の同等性 535
付録F 練習問題解答 537


著者・訳者紹介 [577]
索引 [578-607]
奥付 [608]





【抜き書き】


□pp. 482-484 

◆11.7 社会的影響を考える

  人工知能の進歩が人類にとって潜在的に利益になることは疑いない。そしてその潜在的利益に熱狂するのは容易である。しかしながら危険も潜んでいることを忘れてはならない。技術が派生する効果には、利益になることもあれば破壊的なこともある。その差異は単なる視点の違いのこともあるし、社会的地位の違いによることもある。つまりだれかの利益は、だれか他の人々の損失につながることがあるのだ。したがってここで立ち止まって、進歩する技術について、別の視点から眺めることは有益だろう。
  技術の進歩を人類への貢献として見る視点がある。技術とは、平凡で退屈な日々の営みから人類を解放し、より喜びに満ちた生活様式への道を拓くというわけである。しかしこの同じ現象を、人々から職を奪い取り、富を権力者へ集める災いであると見る視点もある。実際これは、インドの献身的な人道主義者マハトマ・ガンディーのメッセージである。彼は、大規模な織物工業を小作人の紡ぎ車で置き換えるべきだと繰り返し主張していた。このように彼は、少数しか雇用しない中央集権的大量生産システムを分散型の生産システムで置き換えることにより、社会的利益は拡大すると主張したのだった。
  歴史は、富と権力の偏在に端を発する革命に満ちている。今日の先進技術が貧富の差を固定化するのであれば、破滅的な結果をもたらすかもしれない。
  しかし高度に知的なマシンを構築することによる結果は、社会の単なる階級闘争よりもより微妙でより根本的である。これは、人類の自己イメージの革新を突く問題なのだ。19世紀にチャールズ・ダーウィンの進化理論と人類が劣った生命体から進化したという考えは、社会を震撼させた。人間精神に匹敵する知的能力をもつマシンが活躍するような事態に直面したときに、社会はどのように反応するだろうか。
  かつて技術の進歩は緩慢であったので、知性に対する概念を変化させることでわれわれの自己イメージを保つことができた。古代の人々が 19 世紀の機械装置を見たならば、超自然な知性をもつと解釈しただろうが、現代人はそのようなマシンに知性を感じることはない。しかしマシンが真に人間の知性に挑戦するようになったら、あるいはむしろ、われわれが適応する以上の速さでマシンの能力が進歩してしまったならば、人間社会はどのように反応するだろうか。
  人間の知性に挑戦するマシンにどのように人々が反応するかは、20世紀半ばにIQテストが導入されたとき社会がどのように反応したかを考えることでヒントを得られる。IQテストは、子供の知的レベルを特定するものと考えられたのだ。アメリカ合衆国で子供たちは、IQテストの結果によって分別されて、それに応じた教育機関へと送られた、つまりテストの成績のよかった子供たちにはすぐれた教育機会が開かれたのだが、成績の悪かった子供たちは、特別支援学校へ送られてしまった。端的にいうと、個人の知性を計る尺度が与えられると社会は、その尺度上で低いほうの人々の能力を無視する傾向にある。それではマシンの“知的な”能力が人間のそれに匹敵するようになったとき、社会はどのようにその状況に対処するだろうか。社会は、マシンの知性より劣る”ように見える人々を切り捨てるだろうか。もしそうするならば、社会の構成員にとってどのような結果になるだろうか。人間の尊厳とは、マシンとどのように比較されるかによって条件づけられてしまってよいのだろうか。
  特定の分野で人類の知的能力が、マシンによって脅かされる事例をすでに見た。今日コンピュータは、チェスのチャンピオンを負かすまでになっている。エキスパートシステムは医診断の助言を与えるまでになっているし、投資ポートフォリオを管理する単純なプログラムは、投資の専門家よりパフォーマンスがすぐれていたりする。このようなシステムは、個人の自己イメージにどのような影響を与えるだろうか。マシンの能力が個人の能力を多くの分野で凌駕し始めたとき、自隊心にどのような影響がでるだろうか。
  マシンが知性をもつと言っても、人間のそれとは根本的に異なると主張する人々も多い。なぜなら人間は生物であり、マシンは機械だからである。つまりマシンは、人間の意思決定プロセスを再生産することはできないというわけだ。マシンも人間と同じ決定に達するかもしれないが、そのような決定は、人間によるものと同じには立っていないというわけだ。それでは、どの程度異なる種類の知性が存在するのだろうか、そして人間以外の知能が提案した決定に従うことは倫理的だろうか。
 『コンピュータ・パワー:人工知能と人間の理性』の中でジョセフ・ワイゼンバウムは、人工知能の無間な適用に対して、次のような反対の主張をしている。

 コンピュータには、司法的決定を下すことや、精神医学上の判断を下すこともできる。それらは、もっとも我慢強い人間がするより、はるかに複雑な方法で硬貨を投げ、その裏表により決定を下せる。論点は、コンピュータにこういった仕事をさせる“べきではない”ということである。ある場合に、コンピュータが正しい決定を下すこともあろうが、それは常に、かつ必然的に、人間が喜んで受け入れるべきではない根拠によっている。
 「コンピュータと精神」についての多くの論争が行われた。ここで私が結論することは、真の論点は技術的なものではなく、また数学的なものでもなく、倫理的なものなのだということである。それは、何々が、「できるか」といった問によって答が得られる性質のものではない。コンピュータを応用する上の制限は、究極的には、何をなすべきかという観点からのみ述べることができる。
 これから生じるもっとも初等的な見識は、今日、コンピュータに思慮分別を与えることは不可能であるから、コンピュータに思慮分別を必要とする作業を与えるべきではないということである。
 
秋葉忠利 訳、「コンピュータ・パワー 人工知能と人間の理性」、サイマル出版会、1979年


  読者は、この節がコンピュータ科学というよりも空想科学ではないかと思うかもしれない。しかしながら”コンピュータが社会を乗っ取ったらどうなるか”という疑問に対して、そんなことは起きっこないという態度で考えることを拒否していたのは、そう遠い昔の話ではない。しかし多くの点で、その日は到来してしまっている。コンピュータ化されたデータベースが、劣悪な信用情報を報告したら、犯罪歴があると、あるいは当座預金口座が借越しになっていると報告したら、コンピュータの出力とあなたの主張とどちらを人々は信用するだろうか。航空管制システムが動作して、霧のかかった滑走路の位置を誤って示したら、航空機はどこに着陸するだろうか。さまざまな政治的決定にどのように世論が反応するかを予測するのにコンピュータが使われるようになったとしたら、どの決定を政治家は採用するだろうか。読者は、“コンピュータがダウンしているので対応できません”と事務員が言うのを、何回くらい聞いたことがあるだろうか。そのとき責任は、だれに(何に)あるのだろうか。われわれは、すでにコンピュータに取り囲まれた社会に住んでいるのではないだろうか。



□pp. 11-12

訳者まえがき

  本書は、J. Glenn Brookshear による Computer Science: An Overview 第11版の翻訳です。本書は、きわめてオーソドックスなコンピュータ科学の教科書であり、文字通り全米のほとんどの大学で初学年向けコンピュータ科学の教科書として採用されています。〔……〕1985年に初版が出版されてから現在改訂第11版と版を重ねていることからも、そのベストセラー振りがうかがえます。
  本書は一見してわかるように、〔……〕入門書のお手本のように進んでいきます。まったくオーソドックス過ぎて特徴のないのが特徴といえます。あえて特徴といえば、オートマトンと言語理論の章がないところでしょう。
 〔……〕全体で600ページほどの分量があり、これだけ学べば、情報系の学生でも十分という知識を網羅しています。かつて訳者は、博士課程の学生であったときに本書(第4版あたり)を代理で講義した経験があり、いずれ日本語にしたいと考えていました。訳出の機会を与えてくれた株式会社KADOKAWA鈴木亮平編集長にはお礼のことばもありません。 
  本書はまた、実務に携わっているプログラマやSEが、他分野の最新のコンピュータ科学の動向を学ぶのにも最適です。〔……〕訳者もコンピュータグラフィックスの章は、とても興味深く読みました。そのようにコンピュータグラフィックスは詳しくありませんので、株式会社ロングテール代表の長尾高弘氏に参加していただきました。的確な翻訳ですので、訳者が勉強になったように、読者のみなさんにも興味深く読んでいただけると思います。
  本書の特徴は、コンピュータ科学が抽象化ツールの階層構造になっているという視点で統一的に記述されているところにあり、単に多くのアイデアの羅列に陥ることを避けています。本書の内容を理解するのに予備知識は必要なく、プログラミングの教科書と併用すれば大学一年生用の教科書として最適であると考えています。
  完全に一般教養の教科書とするには少しレベルが高いかもしれませんが〔……〕。また、社会的問題や個別のコンピュータ技術が社会に与える影響についても議論している点は、類書にない特徴です。これも大学初学年の教科書として執筆されている故と思います。米国の大学では、日本のようにコンピュータリテラシの授業がないので、社会的影響を考えることがコンピュータ科学入門の一環になっているのです。社会学の授業としても成立するような深い議論が交わされていることもあり、驚かされます。本書を学びながら、そのような正解のない問題にも思いを馳せていただければ幸いです。
  訳出にあたっては、できる限り原文に忠実な日本語となるように務めましたが、日本語として自然になるように書き改めたところもあります。若干英語が古風で長いところがありましたので、日本語では短くわけたところもあります。いくつかの疑問点についてはメールで問い合わせをして、場合によっては原著を修正して訳出した箇所もあります。〔……〕