入門コンピュータ科学(Computer Science An Overview)

• 本書の目標
  • コンピュータ科学の機能的な理解を確率することで、この分野を専攻しようとしている学生に学問的基礎を提供し、また他分野の学生が技術的な理解を深めることで、それぞれの専攻分野で十分に活躍できるようにすること

第0章: 序章

• コンピュータ科学とは何か
  • アルゴリズムの可能性についての研究が今日のコンピュータ科学として知られる分野の始まりであり、アルゴリズムの研究 = コンピュータ科学の核心
• コンピュータ科学の歴史
  • 古代の算盤にはじまり、中世から現代までの計算機械の発展とスマートフォンに至るまでの歴史について
  • オーガスタ・エイダ・バイロン
    • チャールズ・バベッジの設計したプログラム可能な階差機関を、様々な計算を実行させるためにどのようにプログラムすればよいかを示す論文を発表
    • 世界で最初のプログラムとされる
• コンピュータ科学を学ぶ基礎固め
  • 今日のコンピュータ科学 = アルゴリズムの科学
    • 範囲は広範で、様々な分野と密接な関係を持ち、コンピュータ科学と一言で言っても細かい専門分野では定義が異なることもある
  • 抽象化(abstraction)
    • あるものの外面的な性質と内面的な構造の詳細とを区別すること
      • 例: プログラムの実行過程を理解するために、プログラムの内部の詳細を知る必要はない
    • 抽象化レベルをつかうことで、内部構造の詳細に立ち入ることなく構成要素を使用できる

第1章: データストレージ

1.1 ビットとその符号

• ビット(bit)
  • 情報を0と1のパターンへ符号化したもの
  • ビットはあくまで「記号」であり、その意味は処理するアプリケーションに依存する
  • ビットの長い列をストリーム(stream)と呼ぶ
  • 長いビット列の表現を単純化するために16進数記法を使用することがある(hexadecimal notation)
    • 4ビットのパターンを1つの16進数記号に対応させる

    bit
    0000 0
    0001 1
    0010 2
    0011 3
    0100 4
    0101 5
    0110 6
    0111 7
    1000 8
    1001 9
    1010 A
    1011 B
    1100 C
    1101 D
    1110 E
    1111 F
    

1.2 メインメモリ

• コンピュータがデータを格納しておくため持っているビットの格納領域
• メモリセル(memory cell)
  • メモリの最小単位
  • 典型的なセルのサイズは8ビット(=1バイト)
  • 個々のセルを識別するために、各セルはアドレス(address)という一意な名前を持つ
  • アドレスをもとに任意の順序でセルにアクセスできることから、コンピュータのメインメモリはランダムアクセスメモリ(RAM)と呼ばれる

1.3 マスストレージ

• 以下の点でメインメモリよりも優れている
  1. 揮発性が少ない
  2. 大容量
  3. 低コスト
  4. 多くの場合、保存のためにマシンから記憶媒体を取り出しておける
• マスストレージの短所
  • ある程度機械的動作が必要なことが多く、すべての動作が電子的に行われるマシンのメインメモリに比べデータの入出力に遥かに時間がかかる
• 磁気システム
• 光学システム
  • 一般例) CD(compact disk)
• フラッシュドライブ
  • 電子的な信号をストレージ媒体に直接送ることで、シリコン半導体の小さな格納領域に電子が閉じ込められ、ビットを格納する
  • シリコン半導体の小さな格納領域は、捕獲した電子を何年にもわたって保持できるため、データのオフラインストレージとして適している
  • 繰り返しの利用で性能が劣化する点が短所だが、物理的な衝撃には強い
  • いわゆるUSBメモリやSDカードがフラッシュドライブの例
• 物理レコード(physical record)
  • 記憶装置の物理的な性質に合わせたデータブロックのこと
  • マスストレージ中に格納される大規模なファイルは、多くの物理レコードから構成される
• 論理レコード(logical record)
  • 表現する情報によって決定される自然な分割から発生するデータのブロックのこと
  • テキストドキュメントにおける段落やページ等
• バッファ(buffer)
  • ある装置から他の装置へデータを転送するプロセスでデータを一時的に保持するのに使用される領域

1.4 ビットパターンとしての情報を表現する

1.4.1 テキストを表現するる

• テキスト形式は通常、テキスト中の異なる記号(文字や句読点等)を一意なビットパターンへと割り当てることによって表現
• ASCII(American Standard Code for Information Interchange)
  • 多くの文字コード体系が出現したことで通信上の問題も発生したため、米国規格協会(ANSI)がASCIIを制定
  • 7ビットのパターンを使って128種類の異なる記号を表現(英語のアルファベット、句読点、0~9までの数字、行送りコード、改行文字、タブ等の制御文字)
  • 7ビットパターンの左端に1ビットの0を加えて8ビットパターンの記号へ拡張された
    • 8ビット化することでバイトサイズのメモリセルに綺麗に収まるようになった
    • 英語のアルファベット以外の記号や句読点を表現するのに(追加された1ビットに1を割り当てることで得られる)利用できる追加の128個のビットパターンを使用できるようになった
• Unicode
  • 拡張版のASCIIでは対応できない問題が発生したため、Unicodeが登場
    • 拡張版ASCIIではアジアや東ヨーロッパの言語の文字を表現するには不十分
    • 1つの文書内で複数言語を記述するテキストを扱えなかった
  • 世界中のハードウェアやソフトウェアの有力企業が協力して開発
  • 各記号を表現するのに一意な16ビットを使用することで、65536個(2^16)の異なるビットパターンからなる文字セットを提供
    • これにより、世界中のほとんどの言語の文字を表現できるようになった
• テキストファイル
  • ASCIIやUnicodeのような文字コードを使用してテキストを表現するファイル

1.4.2 数値を表現する

• 記録する情報が数値だけの場合、文字データとして格納するのは非効率
  • 例) 値25を格納する場合、ASCIIでは記号ごとに1バイトを使用するため、25を表現するために2バイトが必要
• 2進数表現を用いる場合、16ビットの中に0から65535までの任意の整数を格納できる
• 2の補数記法という方法が多く使われる
  • 正の整数のみならず、負の数も容易に表現できる
• 分数部分を持つ数を表現するには、浮動小数点記法を用いる

1.4.3 画像を表現する

• 画像を表現する1つの方法は画像をピクセル(pixel, picture element)と呼ばれる点の集まりと解釈すること。
• ビットマップ(bit map)
  • 各ピクセルの状態を符号化することで、画像全体を符号化されたピクセルの集まりとして表現する方法
  • ビットマップによる画像処理は、画像を任意の大きさに拡大縮小するのが難しい
    • 本質的には画像をおきくするにはピクセルを大きくするしかなく、そうすると画像の粒子が粗くなってしまう
• ビットマップのスケーリング問題を解消するために、画像を直線や曲線といった幾何学構造の集合で記述するアプローチがある
  • 今日のワードプロセッサシステムで利用される方法
    • TrueType: MicrosoftとAppleが開発
    • PostScript: Adobeが開発。文字だけでなく一般的な画像データを記述する手段も提供
      • コンピュータ支援設計(computer-aided design, CAD) システムでも採用

1.4.1 音声を表現する

• 音声情報をコンピュータに格納して加工するために符号化する最も一般的な方法は、一定の間隔で音波の振幅を標本採取して得た値を数列として記録するもの
  • 毎秒8000個の標本を採取する長距離電話通信で長年使用されてきた
  • 毎秒8000個の標本抽出では原音に忠実な録音には不十分であり、今日の音楽CDでは毎秒44100個の標本を採取する
    • 標本採取で得られたデータは16ビット(ステレオ録音では32ビット)で表現されるため、ステレオ録音の場合、毎秒100万ビット以上が必要になる
• 電子楽器デジタルインターフェース(Musical Instrument Digital Interface, MIDI)と呼ばれる符号化システムを使うことで、大規模な格納領域の確保を避けられる
  • 「どの楽器がどの音をどれだけの時間発生させるか」を符号化する
    • クラリネットが1音を2秒間演奏するとき、毎秒44100の標本採取では200万ビット以上必要だが、MIDIでは3バイトに符号化できる

1.5 2進数の体系

• 割愛

1.6 整数を格納する

• 計算装置で整数を表現するのに使われる代表的な2つのもの
  • 2の補数記法
  • エクセス記法

1.6.1 2の補数記法

• 今日のコンピュータで最も一般的な体系は2の補数(two's complement)記法
• 体系中の各値を表現するのに固定長のビット列を使用する
  • 今日の装置では、各値を32ビットのパターンで表現する2の補数体系が一般的
• 2の補数システムでは、最左端のビットがそのビットパターンを表現する値の符号を示し、最左端のビットを符号ビット(sign bit)と呼ぶ
  • 0の場合は正の数、1の場合は負の数

  011 3
  010 2
  001 1
  000 0
  111 -1
  110 -2
  101 -3
  100 -4
  

• 2の補数体系では、絶対値が同じ正の値と負の値のビットパターン間には、「互いに補」なパターンが存在する
  • ビットパターンを反転させ、1を加えることで補となるビットパターンを得る
  • 例) 3と-3
    • 3: 011
    • -3: 101
    • 3のビットパターンを反転させ、1を加えることで-3のビットパターンを得る
• 2の補数記法による加算
  • 2の補数記法で表現された値の加算では、最後の繰上げによって左端に生成される余分なビットを切り捨てる必要がある(最左端は符号ビット)
  • 2の補数記法では、符号付きの数のどのような組み合わせでも全く同じアルゴリズムで実行できるため、計算装置は加算を知っているだけで加算と減算の両方を実行できる

    // 4ビットパターンでの加算
     3 +  2 = 0011 + 0010 = 0101 = 5
    -3 + -2 = 1101 + 1110 = 11011 = -5(最左端の1は切り捨て)
     7 + -5 = 0111 + 1011 = 0010 = 2
    

• オーバーフローの問題
  • 計算の結果表現できる値の範囲外の値が生じてしまった時に発生する問題
  • 2の補数記法を用いて2つの正の値を加算するか、2つの負の値を加算する時に発生する
    • どちらの場合も、答の符号ビットを検査することで発見できる
      • 2つの正の値を加えて結果が負の値のビットパターンとなるか、2つの負の値を加えて結果が正の値のビットパターンとなるときにオーバーフローが発生

1.6.2 エクセス記法

• 2の補数と同様に、各値は同じ長さのビットパターンによって表現される
• エクセス記法ではまず使用するビットパターンの長さを決定し、そのビットパターンで最左端が1になるパターンを0を表現するものとする。それに続くパターン(1001,1010...1111)を正の値、それよりも前のパターン(0000,0001...0111)を負の値とする

  - 例) 4ビットのエクセス記法
      - 0000: -8
      - 0001: -7
      - 0010: -6
      - 0011: -5
      - 0100: -4
      - 0101: -3
      - 0110: -2
      - 0111: -1
      - 1000: 0
      - 1001: 1
      - 1010: 2
      - 1011: 3
      - 1100: 4
      - 1101: 5
      - 1110: 6
      - 1111: 7
  

• 2進数記法は、エクセス記法での解釈よりも値８だけ超過する
  • 例) 1100はエクセス記法では4を表すが、2進数記法では12を表す

1.7 小数を格納する

• 一般的に小数を表現するためには、浮動小数点(floating-point)記法を使用する

1.7,1 浮動小数点記法

• 符号ビット、指数フィールド(exponent field)、仮数フィールド(mantissa field)の3つの部分から構成される
  • 符号ビット: 0は正の数、1は負の数
  • 指数フィールド: 小数点位置を示すパターンが入る。正の場合には小数点を右に、負の場合には左に移動する
  • 仮数フィールド: 2進数で表現された小数

  // 例) 8ビットの浮動小数点記法
  ビットパターン: 01101011
  符号ビット: 0
  指数フィールド: 110(エクセス記法とする) = 2
  仮数フィールド: 1011
  
  最初に仮数フィールドを取り出し、左端に小数点を置く
  .1011
  
  指数フィールドが2であるため、小数点を右に2つ移動
  01101011 = 2 3/4
  

• 仮数フィールドは左端の1から記入する
  • この規則に従う表現を正規形(normalized form)と呼ぶ
  • 正規形に準拠することで、すべてのゼロではない値の表現は、仮数が1から始まることになる
  • 正規形を用いることにより、同じ値が複数の表現となる可能性がなくなる

1.7.2 打切り誤差

• 浮動小数展をビットパターンで表現しようとすると、仮数フィールドの場所が足りず最右端のビットを切り捨てることがある。このような切り捨てによって生じる誤差を打切り誤差(truncation error)あるいは丸め誤差(round-off error)と呼ぶ
• 打切り誤差(丸め誤差)とは、仮数フィールドの長さが十分ではないために格納されるべき値の一部が欠落してしまうこと
• 打切り誤差が生じる原因は、無限小数が原因でも発生する
• 浮動小数点表記で表現された数値を加えるときは、加算する順序によって結果が異なることがある
  • 極めて大きな数を極めて小さな数に加えると、小さな値は切り捨てられることがある。
  • 複数の値を計算するときには、小さな値同士から計算していくことで(少しでも大きな値とすることで)打切り誤差を最小限に抑えることができる
• 今日のコンピュータでは、単精度浮動小数点(single precision floating-point)と倍精度浮動小数点(double precision floating-point)が一般的
  • 単精度浮動小数点
    • 32ビットで、符号に1ビット、指数部に(エクセス記法で)8ビット、仮数部に23ビットを使用
    • 極めて大きな数(10^38)から極めて小さな数(10^-37)まで有効数字7桁で表現できる(=10進数の最初の7桁は正確に格納できるが、7桁を超える部分は打切り誤差が生じる)
  • 倍精度浮動小数点
    • 64ビットで、10進数で15桁の有効数字を持つ

1.8 データ圧縮

1.8.1 汎用データ圧縮技法

• データ圧縮技法は「ロスなし(lossless)」と「ロスあり(lossy)」の2つに分類される
  • ロスなし: 圧縮プロセスの際に情報が失われない
  • ロスあり: 圧縮の際に情報の一部が失われる可能性がある。ロスレスより圧縮率が高く、画像や音声等若干のエラーが許容される場面で使用されることが多い
• ランレングス符号化(run-length encoding)
  • ロスレス技法の1つ
  • データ要素の列を、繰り返す要素とそれが列中で出現する回数を示す符号へと置き換えるプロセス
• 頻度依存符号化(frequency-dependent encoding)
  • ロスレス技法の1つ
  • データ要素の出現頻度に基づいて符号を割り当てる
    • 表現するデータ項目のビットパターンの長さをその出現頻度に反比例させるシステム
    • 出現頻度が高い要素には短い符号を、低い要素には長い符号を割り当てる
  • ハフマン符号化(huffman encoding)が代表的
• 相対符号化(relative encoging)(差分符号化(differential encoding))
  • データ単位全体ではなく、連続すデータ単位の差を厳密に符号化するか近似的に符号化するかによって、ロス無しの形式でもロスありの形式でもどちらでも実装できる
• 辞書式符号化(dictionary encoding)
  • 辞書: 圧縮されるメッセージが構成される構築ブロックの集合を指す
  • ワードプロセッサでテキスト文書を圧縮するのに使用される
  • 適合型辞書式符号化(adaptive dictionary encoding)
    • 圧縮プロセス中に辞書を更新することで、データの特性に合わせて最適な圧縮を行う
    • LZW符号化(Lempel-Ziv-Welch encoding)が代表的
      • 圧縮時に動的に辞書を更新していく。復号化時も圧縮時と同じプロセスで復号化できるので、辞書の共有も不要

    // LZW符号化の例
    文字列: xyx xyx xyx xyx
    辞書: 1:x, 2:y, 3:' ', 4:xyx
    符号化: 12343434
    

1.8.2 画像を圧縮する

• GIF(Graphic Interchange Format)
  • 画像表現に特化した辞書式符号化体系
  • 色彩の数を制限し、ピクセルあたり256色を割り当てるようにすることで圧縮実現するアプローチ
  • 256色に制限されるため、ロスありの圧縮技法
• JPEG
  • Joint Photographic Experts Groupによって開発されたためJPEGと呼ばれる
  • JPEGの基本標準を用いた画像圧縮は、人間の視界の限界を利用して設計された一連のステップから構成される
    • 眼に見える品質劣化なしに通常カラー画像を少なくとも1/10まで圧縮できる

1.8.3 音声とビデオを圧縮する

• 音声とビデオを符号化し圧縮するために最も広く採用されている標準は、MPEG
  • ISO指導のものとに、Moving Picture Experts Groupによって開発されたためMPEGと呼ばれる
• MP3
  • 音声圧縮のシステムで最も有名
  • MPEG標準の1つとして開発された
  • 人間の聴覚の性質を利用し、人間の耳が認識できない詳細を削除する
  • 品質を保ちながら大幅な音声の圧縮を得るために使用される
• 実時間でのデータ通信に必要な通信速度単位を、通常ビット毎秒(bps)で表現する
  • 1bps = 1ビット毎秒
  • 1Kbps = 1000bps
  • 1Mbps = 100万bps
  • 1Gbps = 10億bps
• MPEG技法を用いると、40Mbps程度の送信速度を提供する通信経路でビデオ表現を実時間で実現できる

1.9 通信エラー

• 通信経路上での影響や物理的な影響によりビットパターンが想定外に変化してしまうことがあるため、それを検知し、場合によっては修正するための符号化技法が開発されてきた

1.9.1 パリティビット

• 「操作されるビットパターンがすべて奇数個の1からなるならば、偶数個の1が出現したならばエラーが発生したことになる」という原理に基づく

  // 例) 文字Aと文字FのASCIIコード
  A: 101000001 <- 8ビットで偶数個の1をもつため、パリティビットに1を追加
  F: 001000110 <- 8ビットで奇数個の1をもつため、パリティビットに0を追加
  => 偶数個の1を持つ場合にはエラーが発生したことになる
  

• 今日のコンピュータのメインメモリではパリティビットが使用されており、メモリセルは8ビットと思われているが実際には9ビットで構成されている
  • 8ビットのデータと1ビットのパリティビットからなる
  • 電子回路はデータ格納時に8ビットパターンに加えてパリティビットを含む9ビットパターンで格納し、取り出す際に9ビットパターンのパリティを検査してエラーが発生しているかどうかを判断する
  • エラーがない場合はパリティビットを除いた8ビットパターンを返すが、エラーが発生している場合はエラーを報告しつつ8ビットパターンを返す
• 2つのエラーが発生していた場合には変わらず奇数個の1を持つことになるため、エラーが検出されない
  • この問題に対処するためのエラー検出方法としてチェックサム(checksum)や巡回冗長検査(cyclic redundancy check, CRC)がある

1.9.2 エラー訂正符号

• ハミング距離(Hamming distance)
  • 2つのビットパターンの間の異なるビットの数
  • 2つのビットパターンが異なるビット数が1であれば、エラーが1ビットであると判断できる
  • 誤り訂正コードをもって、エラーが発生したビットを特定し、正しいビットに修正することができる

第2章: データ操作

• コンピュータがどのようにデータを操作し、プリンタやキーボードのような周辺機器とどのように通信するか
• コンピュータの基本的なアーキテクチャとマシン語によるコンピュータのプログラムについて

2.1 コンピュータアーキテクチャ

2.1.1 CPUの基本

• CPUの構成
  • 算術論理ユニット
    • データの演算を実行する回路を含むユニット
  • 制御ユニット
    • マシンの実行を調整する回路を含むユニット
  • レジスタユニット
    • CPU内で情報を一時的に格納するのに使われるレジスタと呼ばれるデータ格納用セルを含むユニット
    • レジスタには汎用レジスタと専用レジスタがある
      • 汎用レジスタ: プログラムの実行中に一時的にデータを格納するために使用
      • 専用レジスタ: 特定の目的のために使用
• バス(bus)
  • ビットパターンを転送するためにマシンのCPUとメインメモリを繋ぐ転送路
  • このバスを通じてCPUは適切なメインメモリのアドレスと指定したセルからデータを読み書きする
• メインメモリに格納されている2つの値の加算
  • 1. 加算される一方の値をメモリから取り出しレジスタに置く
  • 2. 加算されるもう一方の値をメモリから取り出しレジスタに置く
  • 3. 上記2つの値を格納したレジスタを入力にし、別のレジスタを出力の格納用として準備し加算を実行
  • 4. 結果をメモリに格納
  • 5. 停止

2.2 マシン語

• マシン語
  • コンピュータが直接理解できる言語
  • マシン語プログラムは、CPUが直接実行できるように、CPUの命令セットに従って記述される

2.1.1 命令の種類

• マシン命令は基本的な動作を行う命令さえあれば、それ以上に機能を追加しても利便性の向上には繋がるがマシンの能力を理論的には向上させない
  • 上記事実から2つのCPUアーキテクチャの設計思想が生まれた
    • 縮小命令セットコンピュータ(reduced instruction set computer: RISC)
    • 複合命令セットコンピュータ(complex instruction set computer: CISC)
• 縮小命令セットコンピュータ(reduced instruction set computer: RISC)
  • 最小限のマシン命令を実行するようにCPUを設計すれば良いという考え方に基づいたアーキテクチャ
  • 効率的かつ高速で、さらに製造も比較的安価に済むと主張されている
• 複合命令セットコンピュータ(complex instruction set computer: CISC)
  • CPUがその多くが冗長であっても多くの複雑な命令を実行できる方が好ましいという主張に基づくアーキテクチャ
  • 複雑なCPUのほうが、今日の複雑さを増すソフトウェアに容易に対処できると主張されている
• 技術の進歩に伴いCISCのCPUを製造するコストも飛躍的に減少し、今日ではほとんど全てのデスクトップとラップトップでCISCが採用されている(インテル社が製造するCISC)
• CISCは消費電力が多いという問題点も抱えており、モバイル端末や組み込みシステムではRISCが採用されることが多い
  • ARM社やQualcomm社、テキサス・インスツルメンツ社が製造するRISCが採用されることが多い
• マシン命令の3つのグループ
  1. データ転送グループ
     • データ転送というよりも複写(copy)や複製(clone)の働き
     • メモリから汎用レジスタへの読み込みは「ロード命令」、汎用レジスタからメモリへの書き込みは「ストア命令」と呼ばれる
     • CPUとメインメモリの外側にある装置との通信のための命令をI/O命令と呼ぶ
  2. 算術・論理演算グループ
     • 制御ユニットに算術論理ユニットでの動作を行わせるように伝える
     • AND, OR, XORなどを用いて、基本的な算術演算以上の演算を実行できる
  3. 制御グループ
     • プログラムの実行の流れを制御するための命令
     • プログラムの実行を開始するための命令を「ジャンプ命令」などを持つ
     • 符号化されたマシン命令は2つの部分から構成される
       • オペコード(op-code)フィールド: 基本演算のいずれが命令として要求されているかを示す
       • オペランド(operand)フィールド: オペコードによって指定される命令について詳細な情報を提供する
         • STORE演算のオペランドフィールドには、どのレジスタが格納されるデータを持ち、どのメモリセルでデータを受け取るかを行った情報を含む

2.3 プログラムの実行

• 実行の流れ
  1. コンピュータがメモリに格納されたプログラムの命令を必要に応じてメモリからCPUに複写することで実行する
  2. CPU内に複写された命令は解読後実行される
  3. 命令がメモリから取り出される順序はJUMP命令により変更されない限りメモリに格納された順序による
• 命令レジスタ(instruction register)
  • CPU内にあるレジスタの1つで、次に実行される命令を格納する
• プログラムカウンタ(program counter)
  • CPU内にあるレジスタの1つで、次に実行される命令のアドレスを格納する
  • プログラムカウンタは命令レジスタに格納された命令を実行した後に、次に実行される命令のアドレスを指す
• CPUのマシンサイクルによる命令実行
  • 取出し、解読、実行の3つのステップを繰り返すことでプログラムを実行する
  • この3つのステップをマシンサイクル(machine cycle)と呼ぶ

2.4 算術論理命令

2.5 他の装置との通信

2.5.1 コントローラの役割

• コンピュータと他の装置との間の通信は通常コントローラ(controller)と呼ばれる装置を介して行われる
  • コンピュータケースの中にある周辺機器とケーブルで繋がっているか、あるいはコンピュータの背後にあって外部機器を取り付けるポートと呼ばれるコネクタとケーブルで繋がっている
• もともとコントローラは特定の装置ごとに設計されていたが、ユニバーサルシリアルバス(universal serial bus: USB)やFireWireといった標準化が進み汎用化されている
• コンピュータと各コントローラの間の通信は、CPUとメインメモリを結ぶバスと同様にバス接続によって行われる

2.5.2 ダイレクトメモリアクセス

• コントローラはコンピュータのバスに接続されているため、CPUがバスを使用していないナノ秒単位の間隙でメインメモリと直接通信を行える。この機能をダイレクトメモリアクセス(direct memory access: DMA)と呼ぶ
• フォン・ノイマン・ボトルネック(von Neumann bottleneck)
  • DMAの使用により、CPUとコントローラがバスのアクセスで競合する可能性がある
  • この競合を解消するためにバス上の全ての動作をいかに調整するかが主要な設計問題となっている
  • CPUがバスを通じてメモリから命令を取り出すというフォン・ノイマン・アーキテクチャにちなみ、この問題をフォン・ノイマン・ボトルネックと呼ぶ

第3章: オペレーティングシステム

• オペレーティングシステムが何をどのように行うかを理解する
• オペレーティングシステム
  • コンピュータ全体の動作を管理するソフトウェア

3.1 オペレーティングシステムの歴史

• プログラムの準備をユーザーが自分で1つ1つ行っていた状態から、プログラムの準備を簡略化してジョブからジョブへの移行を円滑にするためのシステムとしてオペレーティングシステムが開発された
• バッチ処理(batch processing): 実行中ユーザの介入なしでジョブを1つのまとまり(バッチ)として実行すること
• タイムシェアリング(time-sharing): 複数のユーザに同時にサービスを提供できるようにする機能
• マルチプログラミング(mutiprogramming): タイムシェアリングを実装するための手段。コンピュータの実行時間を細かい感覚に分割し、各ジョブは一度に短い時間だけの実行となるようにし、ジョブを細かく実行・中断することで複数のジョブを同時に実行する
• マルチタスキング(multitasking): タイムシェアリングは複数のユーザが1台のコンピュータを利用することだが、マルチタスキングは1人のユーザが複数のアプリケーションを同時に実行できるようにすることを指す
• ロードバランシング(load balancing): さまざまなプロセッサに作業を動的に振り分けて全てのプロセッサが効率的に使われるようにすること
• スケーリング(scaling): プロセッサの数に合うように1つの作業を複数の部分作業に分割すること

3.2 オペレーティングシステムのアーキテクチャ

3.2.1 ソフトウェア

• ソフトウェアの2分類
  1. アプリケーションソフトウェア(application software)
     • マシンを利用して作業を行うためのプログラムから構成される
     • e.g.) 表計算ソフトウウェア、データベースシステム、会計システム等
  2. システムソフトウェア(system software)
     • コンピュータ一般に共通する作業を実行するもの
• システムソフトウェアの分類
  1. オペレーティングシステム
  2. ユーティリティソフトウェア(utility software)
     • 大部分はコンピュータの利用に必要な作業を実行するプログラムで、オペレーティングシステムに含まれないものから構成
     • e.g.) バックアップ、データ圧縮、データ復元、データ暗号化、データ整理、データ復元等
     • オペレーティングシステムに含めずユーティリティとすることで、カスタマイズが容易になる
     • アプリケーションソフトウェアとの境界は曖昧で、アプリケーションツールも「基本的なツール」となればユーティリティティソフトウェアまで進化したと言える

3.2.2 オペレーティングシステムの構成要素

• ユーザインターフェース(user interface): ユーザと対話するオペレーティングシステムの部分
• シェル(shell): キーボートとモニタスクリーンを使ってテキストメッセージによりユーザと対話するユーザインターフェース
• グラフィカルユーザインターフェース(graphical user interface, GUI): マウスやポインティングデバイスを使ってグラフィカルな画面を使ってユーザと対話するユーザインターフェース
• ウィンドウマネージャ(window manager)
  • ウィンドウと呼ばれるスクリーンの一部をアプリケーションに割り当て、どのウィンドウがどのアプリケーションに関連づけられているかの情報を保持するもの
  • 一般にGUIの”スタイル”と呼ばれるものの役割を担う
  • e.g.) KDE, Gnome
• カーネル(kernel)
  • オペレーティングシステムの内部部分
  • コンピュータの稼働にとっても最も基本的な機能をを実行するためのソフトウェアが含まれている e.g.) ファイルマネージャ(file manager): マシンのマスストレージの使用を調整する。ディレクトリやフォルダと呼ばれるファイルをまとめる機能などを提供
  • デバイスドライバ(device driver): カーネルを構成する要素の1つで、コンピュータの周辺機器と通信するためのソフトウェア
  • メモリマネージャ(memory manager): マシンがメインメモリを使用する際の調整を行う
    • ページング(paging): メモリマネージャがメインメモリとマスストレージの間でやり取りすることで実際にある以上のメモリ領域があるかのような仮想状態を作り出す機能
    • 仮想メモリ(virtual memory): ページ(メモリマネージャが仮想的に容易するデータ格納領域の単位)のやり取りによって生じる大きな架空のメモリ領域のこと

3.2.3 オペレーティングシステムを起動する

• ブートストラップ(bootstrap): コンピュータの電源が入るたびに実行され、マスストレージからオペレーティングシステムをメインメモリにロードするプログラム
• CPUは起動されるたびにメモリ内の前もって決められた特定のアドレスからプログラムカウンタを実行するように設計されており、そのアドレスがCPUがプログラムの実行を開始する場所になる
• コンピュータのメインメモリは揮発性があるため、CPUが最初のプログラムを見つける場所として、特別に揮発性ではないメモリセルから構成されているROM(Read-Only Memory)を使用する
• 汎用コンピュータではブートローダ(boot loader)と呼ばれるプログラムがROMに格納されており、マシン起動時にこのプログラムが最初に実行され、ブートストラッププログラムをメインメモリにロードする
  • ブートローダは、様々な場所からオペレーティングシステムをメモリにロードできる(ネットワークを通じて離れた場所にあるマシンからも可能)
• ブート(boot)する: オペレーティングシステムを開始させるプロセス全体のこと
• ファームウェア
  • オペレーティングシステムが機能する前に、ブートローダが入出力動作を実行する前に使用される
  • ブートプロセスが実際に開始する前にユーザーと対話したり、ブートの途中でエラーを報告したりする際に使用される
  • PCではBIOS(Basic Input/Output System)やEFI(Extensible Firmware Interface)がファームウェアとして使用される

3.3 マシンの動作を調整する

• オペレーティングシステム(OS)がどのようにアプリケーションソフトウェア、ユーティリティソフトウェア、システムソフトウェアの実行を調整するか

3.3.1 プロセスの概念

• OSにおいて最も基本的な概念はプログラムとプログラムが実行する活動を区別すること
  • プログラム: 命令の静的な集合
  • プログラムの実行する活動: 時間の経過とともにその状態が変化する動的な活動
• プロセス(process)
  • OSの制御下でプログラムを実行する動作のこと
  • プロセス状態と呼ばれる状態には、実行されているプログラムの現在位置のみならず、他のCPUレジスタや関連するメモリセルの値が含まれている(= 特定の時点でのマシンのスナップショット)
  • OSが各プロセスが干渉し合わないように、また反対に必要に応じてプロセス間で情報を交換できるようにプロセスを管理するのがOSの役割

3.3.2 プロセス管理

• カーネル中のスケジューラで、プロセスを管理する
  • スケジューラは全てのプロセスの状態の把握のため、プロセステーブル(process table)と呼ばれる情報のブロックをメインメモリ中に保持する
  • プロセステーブルは、割り当てられたメモリ領域やプロセスの優先順位、プロセスの状態(準備完了か待機中か)などの情報をを含む
• ディスパッチャが、スケジューラによって選択されたプロセスを実行する
  • ディスパッチャもカーネル中の機能
  • ディスパッチャは、プロセスの状態を変更し、CPUのレジスタをプロセスの状態に合わせて設定し、プロセスの実行を開始する
  • 時間をタイムスライスと呼ばれる短いセグメントに分割し、CPUが1度に1つのタイムスライス分だけプロセスを実行するようにする
• マルチプログラミングを用いることによって、マシン全体の効率が向上する
  • マルチプログラミングを用いることで常に何かしらの処理を行っている状態とすることで、操作が止まる時間がなくなり、結果として効率が向上する
    • I/O要求などであるプロセスが待機している間でも、その時間を使って他のプロセスの処理を実行できるので逐次実行よりも効率性がアップする

3.4 プロセス間の競合を調整する

3.4.1 セマフォ(semaphore)

• プロセス間での競合を調整するための手法で、割込みが発生しないように適切に制御された機構
• セマフォは、プロセスがリソースを使用する際に他のプロセスがそのリソースを使用しないようにする
  • 方法1: (あるリソースが使用できるかどうかの)検査からプロセスのセットする動作が完了するまで割込みが発生しないようにする
  • 方法2: 検査からプロセスのセットまでを1つの命令として行う

3.4.2 デッドロック(dead lock)

• 2つ以上のプロセスが、それぞれ他者に割り付けられた資源を待って処理が進められない状態のこと
• デッドロックの発生する3つの条件(全て揃った時に発生)
  1. 共有不能な資源を巡って競合がある
  2. 資源は部分的に要求できる。つまり、ある資源を先に受け取ったプロセスは、後に追加の要求を出せる
  3. 一旦資源を割り当てられたならば、強制的に取り上げることはできない

3.5 セキュリティ

3.5.1 外部からの攻撃

• スーパーユーザ(superuser)/システム管理者(administrator): システム全体を管理するための特権を持つユーザで、通常のユーザに許可されていない様々な操作/監視を行うことができる
• 監査ソフトウェア(auding software)と呼ばれる補助ソフトウェアを用いて、コンピュータシステム内でのプロセスの動作を記録・分析する
  • 不正な誤ったパスワードによるログイン処理の実行やユーザの過去の動作と適合しない動作などを監視する
  • スニッフィングソフトウェア(sniffing software)の検出なども行う
    • コンピュータシステムに潜み正規のユーザの動作の記録を取り、のちに侵入を試みるものに報告するソフトウェアで、不正なログイン等に使用される

3.5.2 内部からの攻撃

• 不正な行動からシステムを保護するため、マルチプログラミング用のCPUでは2つの権限レベルのいずれかで動作するように設計されている
  1. 特権モード(privileged mode): スーパーユーザがシステム全体を管理するための特権を持つモードで、全てのマシン命令を実行できる
     • 特権モードだけ実行できる命令を「特権命令」と呼ぶ
  2. 非特権モード(nonprivileged mode): 一般ユーザがシステムを利用するためのモードで、実行できる命令が制限される

第4章: ネットワークとインターネット

• コンピュータがどのように連結され情報や資源を共有するか
• ネットワークの構成と運用、ネットワークの応用、セキュリティについて

4.1 ネットワークの基礎

4.1.1 ネットワークの分類

• エリア分類でのネットワーク
  1. ローカルエリアネットワーク(local area network: LAN)
     • 1つの建物やキャンパス内で使用されるネットワーク
     • 通常、1つの建物内のコンピュータを接続するために使用される
  2. メトロポリタンエリアネットワーク(metropolitan area network)
     • 都市内の広い地域をカバーするネットワークで中規模なネットワーク
  3. ワイドエリアネットワーク(wide area network: WAN)
     • 都市や国家、あるいは世界中の広い地域をカバーするネットワーク
     • 通常、異なる地域にあるコンピュータを接続するために使用される
• ネットワークのパブリックレベルによるネットワーク
  1. 開放型ネットワーク(open network)
     • ネットワークの内部構成と動作がパブリックドメインな設計になっているもの
  2. 閉鎖型ネットワーク(closed network)
     • 特定の個人や企業が所有し制御する技術に基づいているもの
     • プロプライエタリネットワーク(proprietary network)とも呼ばれる
• ネットワークトポロジー
  • ネットワークにマシンが接続されるパターン
  1. バス型トポロジ(bus topology)
     • マシンがバスと呼ばれる共通の通信経路に全てのマシンが接続されているパターン
     • マシンはケーブルを通じてデータを送受信する
  2. スター型トポロジ(star topology)
     • ハブと呼ばれる中央の装置に全てのマシンが接続されているパターン
     • マシンはハブを通じてデータを送受信する

4.1.2 プロトコル

• プロトコル(protocol)
  • ネットワーク上でコンピュータが通信するための規則や手順
  • プロトコルは、通信の開始、終了、エラーの検出、データの送信、データの受信、データの解釈などの手順を規定する
  • プロトコル標準を開発し適用することで、異なる製造業者間で作られたものでも互換性を持たせることができる
• イーサネット
  • バストポロジーを用いてLANを実装する標準で、PCを接続する最も一般的な方法

第5章: アルゴリズム

選択ソートやマージソートなどの個別具体なアルゴリズムについてではなく、アルゴリズムの概念や疑似コードを用いた表現方法、繰り返し構造と再帰構造についての解説がメイン。 アルゴリズムを用いた問題解決の技法やアルゴリズムの効率性・正当性についても解説。

第6章: プログラミング言語

• プログラミング言語とはなにか、言語に共通するもの・異なるものは何か

6.1 歴史的展望

• マシン語(第一世代言語)にはじまり、第二世代言語としてのアセンブリ言語、アセンブリ言語よりも開発を容易にした第三世代言語の出現など。
  • 第一世代言語: マシン語。機械語とも呼ばれる。コンピュータが直接理解できる言語
  • 第二世代言語: アセンブリ言語。マシン語に対応する人間が理解しやすい言語。基本命令はマシン語と本質的には同じで、構文が人間にとって理解しやすいように変換されている
  • 第三世代言語: 基本命令が高レベル(大きなステップを表現できること)であること、マシン独立(特定のマシンの性質に依存しないこと)であること。e.g.) FORTRAN, COBOL, BASIC, C, C++, Java, Python, Ruby, Perl, PHP, JavaScript, Swift, Kotlin, Go, Rust, Scala, Clojure, R, MATLAB, SQL, HTML, CSS, XML, JSON, YAML, Markdown, etc.
• プログラミング言語を分類するアプローチは、世代で行うよりも、プログラミングのプロセスにどのようにアプローチするかという方法論である「プログラミングパラダイム」によって行うほうが適切

6.2 伝統的なプログラミング概念

• 宣言文、命令文、コメントからなるプログラムの3分類から、変数やデータ型などについて。

6.3 手続きユニット

• 命令の集合である手続きや関数などについて。

6.4 言語の実装

• 高レベル言語で書かれたプログラムをマシンで実行可能な形式に変換するプロセスについて。
• ある言語から別の言語への変換プロセス = 翻訳(translation)
• 翻訳のプロセス: 字句解析->構文解析->コード生成(厳密にこの順序で行われるわけではない)
  • 字句解析(lexical analysis): プログラムをトークン(プログラムの構成要素)に分割する
  • 構文解析(syntax analysis): トークンをプログラムの構文構造に変換する
  • コード生成(code generation): 構文解析されたプログラムをマシン語に変換する。プログラムをより効率的に実行するように変換する最適化(optimization)も含まれる

6.5 オブジェクト指向プログラミング

• オブジェクト指向言語に備わる特徴について。
  • クラス(class): オブジェクトの設計。テンプレート
    • インスタンス変数(instance variable): クラスとして定義されたオブジェクトの中にある変数
    • メソッド(method): クラスとして定義されたオブジェクトの中にある手続き
  • インスタンス(instance): クラスから構成されたオブジェクト
  • ポリモーフィズム(polymorphism): 同じメソッド名を持つ異なるクラスのメソッドが異なる動作をすること
  • カプセル化(encapsulation): クラスの内部データを隠蔽し、外部からのアクセスを制限すること

6.6 並行動作のプログラミング

• 複数の駆動を同時に実行することを並列処理(parallel processing)あるいは並行処理(concurrent processing)とよぶ

6.7 宣言型のプログラミング

第7章: ソフトウェア工学

• 大規模で複雑なソフトウェアシステムを開発する際に直面する問題についての分野はソフトウェア工学と呼ばれる
  • この分野の目標は、効率的で信頼性の高いソフトウェア製品へと繋がるソフトウェア開発プロセスを導く原理を発見すること

7.1 ソフトウェア工学という学問

• ソフトウェアと他分野の製品との相違を特定することがソフトウェア工学という分野を前進させる第一歩
• ソフトウェアとその他分野の相違点の1つは汎用的な既製部品からシステムをどの程度構成できるかであるが、ソフトウェアの構成要素は汎用的な部品としては使用が難しいという特徴がある
• メトリクス(metrics)と呼ばれる定量的な技法の欠如も、ソフトウェア工学と他の工学分野を分ける違いの1つ
  • ソフトウェアの”複雑さ”の計測は難しい
• ソフトウェア工学の研究は「理論」と「実践」の両面で進んでいるが、特に「理論」的な面での研究は遅々として進んでいない

7.2 ソフトウェアライフサイクル

• ソフトウェア工学における根本概念 = ソフトウェアライフサイクル
• 他の工業製品での保守段階は修理のプロセスで、ソフトウェアの保守段階は修正と更新を含む
• 伝統的なソフトウェア開発のライフサイクルの主なステップ
  1. 要求分析
  2. 設計
  3. 実装
  4. テスト
• 要求分析: 解決すべき問題を特定する
• 設計: 問題の解法を構成する
• 実装: 設計をプログラムに変換する
• テスト: 伝統的にはソフトウェア製品が要求仕様書と一致していることを確認すること。しかし現代ではこのフェーズはそれぞれ各フェーズに組み込まれていると考えられている(「要求分析と確認」「設計と検証」「実装とテスト」)

7.3 ソフトウェア工学の方法論

• 略

7.4 モジュール性

• 何がモジュールを構成するかが最初のソフトウェア設計プロセスの目標を決定するため、パラダイムごとのモジュールの区別は重要
  • 命令型: 手続きの形で出現する
  • オブジェクト指向: オブジェクトを基本モジュールの構成要素として使用する
• モジュール化されたシステムを設計する際の目標は、モジュール間の独立性を最大にすること
• モジュール間の結合度
  • 制御結合(control coupling): 手続き呼び出しのように、実行制御を1つのモジュールから他のモジュールへ渡す時に発生する
  • データ結合(data coupling): モジュール間でのデータの共有度を示す
• 各モジュール内の結合度を最大化することも重要(凝集度(cohesion))
  • 凝集度は内部的な結合度、つまりモジュールの内部要素の関連の強さを表す
    • 論理的凝集(logical cohesion): モジュール内の構成要素が論理的に類似の動作を行うという理由で同じモジュールに配置されること
    • 機能的凝集(functional cohesion): モジュール内の全てての要素がある1つの動作を実行することでまとまっていること
    • オブジェクト指向設計ではすべてのオブジェクトは論理的凝集にすぎないが、オブジェクト内の各メソッドは機能的に凝集した1つのタスクだけを実行するような設計とする
• モジュールは低い結合度を目指すことに加え、高い凝集度を目指す必要がある
• 優れたモジュールかの設計の基礎は情報隠蔽の概念であり、モジュールの動作が他のモジュールに不必要に依存したり不必要に影響を及ぼしたりしないようにすること
• 情報隠蔽の2つの目標
  1. 設計目標: モジュールは、他のモジュールがその内部情報にアクセスしなくても良いように設計しなければならない
  2. 実装目標: モジュールの境界が明確になるように実装しなければならない
• コンポーネント: 定義によりソフトウェアの再利用可能なユニットのこと

7.5 ツール

ソフトウェア開発の分析と設計段階を通して使用されるモデル化の技法と表記法の体系について解説する

• データフロー図(data flow diagram): データの流れを解析することで得られる情報を表現する手段
• データディクショナリ(data dictionary): システムソフトウェア全体を通して出現するデータ項目について情報を蓄える中心的な貯蔵庫の役割を果たす
  • 目的の1つは利害関係者と利害関係者の要求を要求仕様へと変換するソフトウェア技術者との間のコミュニケーションを改善すること
  • もう1つの目標はシステムに統一性を持たせること
• ユースケース図(use case diagram): ユーザーの視点から提案されたシステムのイメージを把握するためのもの
• クラス図(class diagram): システムの構造を表現するためのもの
• オブジェクト指向プログラミングでは汎化の実装に「継承」を用いることができるが、現代では「継承はクラス感に強い結合をもたらす」という考えから継承は避けられることが多い
  • 継承は実装される汎化が不変な場合に限って使用するべきである
• デザインパターン: ソフトウェア設計において繰り返し現れる問題を解くための開発前モデルのこと
  • デザインパターンの目標は、設計問題への解を単に発見するだけではなく、ソフトウェアライフサイクルの後半での柔軟性を提供する高品質な解を発見すること

7.6 品質保証

• ソフトウェア工学におけるパレートの原理: 集中した部分に努力を傾注することによって結果を急速に向上させされる
  • ソフトウェア中のテストは固まって現れる傾向にあるため、モジュールを均等にテストするよりも、問題のあるモジュールを特定して集中的にテストすることでより多くのエラーを発見できる
• ブラックボックステスト
  • ソフトウェアの内部構造についての知識にテストが依存しないテストのこと
  • 境界値分析法(boundary value analysis)
    • ブラックボックステストの1種で、データの範囲を特定してその範囲の境界に近いデータでソフトウェアをテストするもの

7.7 ドキュメンテーション

• ソフトウェアのドキュメンテーションの3分類
  1. ユーザドキュメンテーション
     • ソフトウェアの機能を説明してどのように使用するかを記述すること
  2. システムドキュメンテーション
     • ソフトウェアの内部構造を記述することで、ソフトウェアライフサイクルの後半での保守作業に資するためのもの
  3. 技術文書
     • ソフトウェアをどのようにインストールしてサービスするかを記述するもの

7.8 ヒューマンマシンインターフェース

• 人間の精神は同時に7つの事柄しか扱うことができない(ジョージミラーによる研究結果)
  • インターフェースはユーザに何かを判断するように求めるときは、人間の記憶に頼るのではなくすべての関連情報を提示するように設計することが重要

7.9 ソフトウェアの所有権と責任

略

第8章: データ抽象

• データ構造として知られている、「コンピュータのメインメモリのセル単位以外のデータの配置をどのようにシミュレートできるか」という問題について解説
• 言語の基本構造以外のデータ構造を構成し操作する技法を学ぶことで、伝統的なデータ構造からオブジェクト指向パラダイムへの移行を理解する

8.1 基本データ構造

• 配列: 同じ構成要素からなるブロック
• 構造体: 異なる型のデータ項目からなるブロック
• リスト: 一列に並べられた要素の集まり
  • ほとんどのデータの集まりはリストとみなされる(e.g. テキスト=記号のリスト、画像=ピクセルのリスト、音声=音声データのリスト)
  • リストにアクセスする方法に制限を加えることで、スタックとキューとして知られる2つのデータ構造を作成することができる
• スタック: データを追加するときは常にリストの先頭に追加し、データを取り出すときは常にリストの先頭から取り出す(= last-in, first-out: LIFO)
• キュー: データを追加するときは常にリストの末尾に追加し、データを取り出すときは常にリストの先頭から取り出す(= first-in, first-out: FIFO)
• 木(tree): 階層的に要素が構成される

8.2 関連する概念

• 抽象化
  • データ構造により、実際のデータ格納領域の詳細の煩わしさから解放し、データがより利用しやすい形式で格納されているかのように情報にアクセスできるようになる(= 抽象化ツールである)
• 静的構造と動的構造
  • 抽象データ構造を構成する際の重要な区別は、シミュレートする構造が静的か動的か
  • 静的なデータ構造は動的なものよりも管理が容易で、動的なものは設計を誤ると大規模な構造の再編成が必要になるなど複雑さを持つ
• ポインタ
  • ポインタはメモリのアドレスを保持する変数であり、そのアドレスはメモリ上の特定のデータを指し示すために使用される
  • 現代の多くのプログラミング言語ではポインタを基本データ型として組み込むことで、関連するデータ項目を連結した精巧なデータネットワークをマシンメモリ中に設計できる

8.3 データ構造の実装

• 配列: メモリ上の連続したセルにデータを格納する。1つのメモリセルで収まらないようなデータ(営業部門の1週間ごとの売上記録等)は2次元配列として扱い、静的に必要な領域を確保して格納する
• 構造体
  1. 各構成要素が必要とするメモリセルの数が固定であるならば、連続したブロックの中に構造体を格納する
  2. 各構成要素が必要とするメモリセルの数が可変であるならば、ポインタを使用して各構成要素をメモリ上の別の場所に格納し、ポインタを使って連結する
• リスト
  • 連続リスト(contiguous list): リスト全体を1つの大きなメモリブロックの連続したメモリセルに順序よく格納するリスト。静的なリストの場合は効率良いが、削除や挿入のコストが高い
  • 連結リスト(linked list): リストの各要素が次の要素へのポインタを持つリスト(格納したいデータ+ポインタ)。挿入や削除が容易
• スタック
  • 最大のサイズのスタックを保持するのに十分なメモリブロックを確保する
  • 最初の要素を底として確保したブロックの一方の端に置き、確保されたもう一方の端に向かってスタックを成長させていく
  • スタックでは先頭の位置が値の追加・削除により変化するため、スタックポインタ(stack pointer)として知られるメモリセル中に先頭の位置を示すアドレスを格納しておく
• キュー
  • 予想される最大サイズのキューを保持するのに十分な大きさの連続したセルのブロックを確保する
  • キューではスタックと異なりデータ構造の両端で操作を行うため、ポインタ用のメモリセルが2つ必要
    • ヘッドポインタ(head pointer): キューの先頭を示す
    • テールポインタ(tail pointer): キューの末尾を示す
  • キューは挿入と削除を繰り返すとポインタの位置がメモリ中をどんどん移動してしまうため、確保したメモリブロックの最後尾に達した場合は、先頭に戻って再利用するようにする(循環キュー: circular queue)
• 二分木
  • 通常連結リストに類似した連結構造を用いるが、連結リストが2つの構成要素(データ、次の要素へのポインタ)からなっているのに対し、二分木は3つの構成要素(データ、左の子へのポインタ、右の子へのポインタ)からなる
  • 連続リストのように木全体に対して1つの連続したメモリセルのブロックを使用する方法も存在する
    • この方法では、木のレベルごとに連続して配置するため、任意の節点の親節点や兄弟節点を発見するのに効率的
    • 二分木がほぼ均整が取れていてメモリが満杯のとき、メモリ空間の使用効率が良い

8.4 ケーススタディ

• 略

8.5 データ型をカスタマイズする

• ユーザー定義のデータ型(user-defined data type)
  • 基本データ型を構築ブロックとして用いて追加のデータ型としてプログラマが定義したもの
  • インスタンスを構成するテンプレート
• 完全なデータ型の構成要素
  1. 前もって定義された格納システム(整数形の場合は2の補数体系、実数型の場合は浮動小数点系のような)
  2. 前もって定義された演算の集合(加算や減算のようなもの)
• 抽象データ型(abstract data type)
  • 演算の定義を含むユーザー定義のデータ型

8.6 クラスとオブジェクト

• オブジェクト指向におけるクラスは、多くの点で抽象データ型の記述であるが、クラスは抽象データ型を拡張したものといえる
• 抽象データ型にできずクラスでできること
  • 継承: クラスは他のクラスから性質を継承できる
  • カプセル化: インスタンスの内部的な性質を誤用から守る
  • 手続きのグループ化: 関連する手続きをグループ化することにも利用できる。ひいては手続きだけからなるクラスもあり得る

8.7 マシン語におけるポインタ

• 略

第9章: データベースシステム

9.1 データベースの基礎

• フラットファイル(flat file): 1つの視点だけから情報を表現している(1次元的)
• データベース(database): 複数の視点から情報を表現している(多次元的)
• データベースの研究は、データベース中の情報を意思決定プロセスに応用できる技術の開発へと焦点を当ててきたほか、Webサイトを支える基盤技術としても重要な役割を果たしている
• データベース中の情報へのアクセスを制御することは、情報を共有することと同じくらい重要な機能
• スキーマ(schema): データベースの全体構造の記述であり、データベースソフトウェアがデータベースを保守するのに使用する
• サブスキーマ(subschema): 特定のユーザーにとって必要な部分だけの記述
• データベース管理システム(database management system: DBMS): データベースの構造を管理し、データベースへのアクセスを制御するソフトウェア
  • アプリケーションソフトウェアとDBMSで作業を二分する利点
    1. 抽象化: データベースの物理的な構造をアプリケーションソフトウェアから隠すことで、DBに関する処理を抽象化して扱える
    2. データの独立性: データベースの物理的な構造が変更されてもアプリケーションソフトウェアは変更されない
• データベースモデル: データベースの概念的外観のこと
  • DBMSはデータベースの内部構造を隠蔽し、データベースのユーザには情報が扱いやすい形式でデータベース中に格納されているかのように見せることを可能にする
  • DBMSではデータベースの概念的外観に沿って記述された命令を、実際のストレージシステムで必要な動作へと翻訳するルーチンを含む
• より良いデータベースモデルの探求は、複雑なデータシステムを容易に概念かして情報の要求を端的に表現するとともに、効率的なデータベース管理システムを生成できるようにすること

9.2 関係モデル

• 略

9.3 オブジェクト指向データベース

• 略

9.4 データベースの完全性を保つ

• コミット時点(commit point)
  • トランザクションのすべてのステップがログに記録された時点
  • 必要に迫られたときにトランザクションを再構成するために必要な情報が揃う時点
• ロールバック(rollback)
  • トランザクションの途中でエラーが発生した場合、トランザクションを開始前の状態に戻すこと
  • 例えば誤動作した時点での未完了(コミットされていない)トランザクションをロールバックすることでデータベースを回復する
• DBMSは複数のトランザクションが要求された場合、新しいトランザクションをそれ以前に生成されたトランザクションが完了するまで待ち行列(キュー)に入れることで、トランザクションを1つずつ実行して完了させる
• ロックプロトコル(locking protocol)
  • 不正確な合計問題や遺失更新問題のような異常からシステムを魔持つために組み込まれた制御機構
  1. 共有ロック(shared lock): 他のトランザクションがデータを読むことを許可するが、データを書き込むことは許可しない
  2. 排他ロック(exclusive lock): 他のトランザクションがデータを読むことも書き込むことも許可しない
• デッドロック(dead lock)
  • 2つ以上のトランザクションがお互いにロックを解放することを待ち続ける状態
  • 負傷待機プロトコル(wound-wait protocol)
    • デッドロックを避けるためのプロトコルの1つ
    • 古いトランザクションから優先的に処理し、新しいトランザクションは古いトランザクションがロックを解放するまで待つことで、順に処理していくプロトコル

9.5 伝統的ファイル構造

9.5.1 順編成ファイル

• 初めから終わりまで情報が1つの長い列になっているかのように順番にアクセスされるファイル
• 音声ファイル、ビデオファイル、プログラムファイル、テキスト文書ファイルなど
• 表計算ソフトウェアアプリケーションなども保存されると情報は符号化され手順編成ファイルの形式で格納される

9.5.2 索引ファイル

• ファイル中のレコードを不規則な順序で検索しなければならないような場合に使用されるファイル
• 書籍中にトピックの場所を見つけるのに索引を用いるのと同じようにしてファイルの索引を使用するもの
• ファイル索引の仕組み
  • ファイルの索引はファイル中のキーとそのキーを持つレコードがどこに格納されているかを示すエントリーのリストに含む
  • 特定のレコードを探すには索引中のキーを特定した上でそのキーに関連する場所に格納されている情報のブロックを取り出す
• 有名な例は、ほとんどのオペレーティングシステムでファイル格納領域を構成するのに使用されている階層的ディレクトリシステム
  • この視点から見ると、ファイルシステム全体も単なる1つの大きな索引ファイルとみなせる

9.5.3 ハッシュファイル

• 索引システムと同じようにキーの値を使ってレコードの場所を特定できるが、ハッシュ法では索引中のキーを探る代わりにキーから直接レコードの場所を特定する
• ハッシュシステムの仕組み
  • ハッシュ法ではデータ格納空間をバケット(bucket)と呼ばれる複数のセッションに分割する
  • 各セッションは複数のレコードを保持できる
  • キーの値をバケットの位置に変換するハッシュ関数を使用して、レコードをバケットに配置する
  • データを取り出すにはハッシュ関数をレコードの識別キーに適用して取り出すバケットを特定する。そこからバケット内のレコードを検索する
• ハッシュファイル: マスストレージ中のストレージ構造にハッシュ法を適用したファイルのこと
• ハッシュテーブル: メインメモリ中のストレージ構造に適用したもの
• クラスタリング(clustering)
  • ハッシュ関数が不均衡にキーをバケットに割り当てるような現象
  • この現象が起こると、1つのバケットに不釣り合いな数のレコードが格納される場合が発生する
• 衝突(collision)
  • 複数のキーを同じ値に割り当ててしまうこと
• 負荷率(load factor)
  • ファイルの総レコード容量に対して格納されるレコード数の比率のこと
  • この率が50%未満であればハッシュファイルは効率よく実行できるとされる
  • 75%を超えるとシステムの性能は一般的に低下するため、ハッシュストレージシステムを再構成する
    • クラスタリングが発生し、バケットが満杯になり、オーバーフローも発生しやすくなる

9.6 データマイニング

• データマイニングはデータの集合にパターンを発見する技法から構成され、一見無関係に思える分野にも応用されている
  • 市場調査、在庫管理、品質管理、DNAの分子構造の中に組み込まれている遺伝子の機能の特定など多岐にわたる
• データベースでは格納されている事実を単に取り出すだけだが、データマイニングではデータの中に隠れたパターンを識別しようとする行為を指す
• データマイニングではデータベース上のオンライン操作ではなく、データウェアハウス(data warehouse)と呼ばれる静的なデータの集合上で実施される
• データマイニングの形式
  1. クラス記述
     • 与えられたデータ項目のグループを特徴づける性質を特定すること
     • 例) 小型車を購入する人々の性格を"特定"するのに使用
  2. クラス分類
     • 2つのグループへ分割する性質を特定する行為
     • 例) 新車を購入する顧客と中古車を購入する顧客を区別する性質を"発見"するのに使用
  3. クラスタ分析
     • グループ化を可能とするようなデータ項目の性質を発見する試み
     • 例) 特定の映画を見た4歳~80歳の人々について、年齢別にグループ化する性質を"発見"するのに使用
  4. 相関分析(association analysis)
     • データグループ間の連結を発見しようとする試み
     • 例) ある商品を購入する人々が別の商品も購入する傾向があるかを"発見"するのに使用
  5. 外れ値分析(outlier analysis)
     • 標準に当てはまらないデータエントリの特定を試みる
     • 例) クレジットカードの不正利用の検知
  6. 時系列パターン(sequential pattern analysis)
     • データの時間的な変化を分析する
     • 例) 株式市場のような経済システムなどにおける傾向を発見するのに使用
• 成功するデータマイニングは、収集したデータの中にパターンを見つける以上の子を包含していることを認識する必要がある
  • 知的な判断により、発見されたパターンが有意味なものであるか偶然であるかを決定しなければならない

9.7 データベース技術の社会的影響

• 略

第10章: コンピュータグラフィックス

• コンピュータグラフィックスはコンピュータ科学の一分野で、視覚表現を生成し操作するためにコンピュータ技術を応用するもの
• 従来コンピュータグラフィックスはテキストの表示からグラフや図の構成、GUIの開発、3Dモデリング、アニメーション、映画製作、ゲーム開発など多岐にわたっていたが、近年では3Dグラフィックスと呼ばれる分野で使用されるようになっている

10.1 コンピュータグラフィックスの範囲

• 2Dグラフィックス: 2次元図形(円、矩形、文字等)をピクセルパターンに変換して画像を作ることを主とする
• 画像処理: 画像の中のピクセルを解析し、画像を拡張、理解するためにに使えるパターンを識別することを主とする
• 3Dグラフィックス
  • 3次元画像を図形に変換
  • 従来の写真は現実世界を撮影するが、3Dグラフィックスは仮想世界を写真化する
  • 3Dグラフィックスの画像作成のステップ
    1. 写真化されるシーンの作成、符号化、保存、操作
    2. 画像の作成

10.2 3Dグラフィックスの概要

• 3Dグラフィックスを使って画像を作るための3ステップ
  1. モデリング
     • デジタル符号化されたデータとアルゴリズムから構築
  2. レンダリング
     • カメラが風景をフィルムに投影するように、解析幾何学を応用してシーン内の物体を投影面と呼ばれる平面に投影する
  3. 表示

10章は以下略

第11章: 人工知能

• 人工知能とは、自動マシン=人間の手を借りずに複雑な作業をこなす機械を構築する方法を探るコンピュータ科学の分野

11.1 知能とマシン

• エージェント(agent)
  • 環境からの刺激に反応する装置
  • ほとんどのエージェントは環境からデータを受け取るセンサと環境に働きかけるアクチュエータを持つ
• エージェントの反応のレベルによって人工知能研究を分類できる
  • 反射動作: 最も単純な反応で、入力データに対して前もって決められた反応を返す
  • 目標駆動型のふるまい: エージェントの反応あるいは一連の反応が注意深く立案された動作あるいは現在の状況にそって最適な動作を選択する
    • 手続き的知識(procedural knowledge): ある状況に対して「どのように」学ぶかを開発する形式
    • 宣言的知識(declarative knowledge): ある状況に対して「何を」学ぶかを開発する形式
• エージェントの開発では、環境から受け取ったデータを理解し、学習プロセスを通じて新しい反応のパターンを開発し、自身の能力を最大化できるエージェントを開発することが目標
• 人工知能分野を研究する2つの道筋
  1. 工学
     • 知的な振る舞いを示すシステムの開発を試みる
     • 基本的な目的が特定の実行目標を達成する製品を生み出すことであり、実行指向のアプローチ
  2. 理論
     • 動物、とりわけ人間の知性の計算的な理解を得ることを試みる
     • 基本的な目的が知性の理解を拡げることであり、シミュレーション指向のアプローチ

11.2 認識

• 認識研究の中でもとりわけ画像と言語の理解を探究することは困難であるとみなされている
• 画像を理解する作業の2ステップ
  1. 画像処理(image processing): 画像の特徴を識別するプロセス
  2. 画像分析(image analysis): 画像処理の結果得られた特徴が何を意味しているかを理解するプロセス
• 自然言語処理の3ステップ
  1. 構文解析(syntax analysis): 文章の構造を解析する
  2. 意味解析(semantic analysis): 文の各単語の意味的役割を特定する作業
  3. 文脈解析(context analysis): 文の意味を理解するために文脈を考慮する作業
• 文書全体に関する自然言語処理の研究分野
  1. 情報検索(information retrieval): データベースやインターネット上の情報を検索するための技術
  2. 情報抽出(information extraction): 文書から特定の情報を抽出する技術

11.3 推論

• 略

11.4 その他の研究領域

• どの程度人間が介入ルカのレベルによって、コンピュータ学習を分類するアプローチがある
  1. 模倣(imitation): 人間の行動を模倣する。この段階ではエージェントには何も任せられていない
  2. 教師あり学習(supervised learning): 人間が一連の例を示してエージェントが正しい反応を識別できるようにし、エージェントがそれらの例示を一般化する
  3. 強化学習(reinforcement learning): エージェントは判断のための一般的な規則を与えられ、自ら試行錯誤する。時間をかけて振る舞いを改善するため、自律的に行動できるようになる

11.5 人工ニューラルネットワーク

• 人間精神と同じレベルで認識したり推論したりすることはむずかしいため、自然現象を見倣ったアプローチが注目されるようになった。そのアプローチの1つが人工ニューラルネットワーク
• 人工ニューラルネットワークは、人間の脳の神経細胞のモデルを模倣したもので、脳の神経細胞のネットワークを模倣して情報処理を行う
• 人工ニュートラルネットワークでは、問題を解くための重みづけを人が行うのではなく、教師あり学習によって適切な重みの値を自ら学んでいくことに重要な特徴がある

11.6 ロボット工学

• ロボット工学(robotics)は、知的な振る舞いをする物理的で自律的なエージェントを研究すること
• 現在のロボットは未だ人間への依存性を何かしら持っており、この人間への依存性を克服することが現在の研究の目標となっている
• 人間への依存性を克服するためのアプローチ
  1. 対象物とその位置を含む環境についての詳細な記録を保持し、それによって正確な行動計画を立てるロボットを構築すること
  2. 反応型ロボットを開発すること
     • 複雑な記録を保持し行動計画を詳細に立案するのではなく、そのときどきで外界とやり取りを行う単純な規則を適用しようとするもの
     • ロボット掃除機のルンバで採用されるアプローチ

11.7 社会的影響を考える

• 略

第12章: 計算の理論

12.1 関数とその計算

• 数学における関数(function)とは、可能な入力値の集合と出力値の集合の間に、各入力に1つの出力が割り当てられるように対応付を行うこと
• コンピュータ科学の根本的な作業とは、解決したい問題の根底にある関数を計算する手段を発見すること
• 驚くべき数学上の発見は、入力値に基づいて出力を決定的かつ段階的に求めることが出来ないほど複雑な関数が存在するということ
  • 入力アルゴリズムによって決定的に出力値を得られる関数を計算可能(computable)という ↔︎ そうでない関数を計算不可能(uncomputable)という
• 計算可能な問題を研究することは、コンピュータの究極の能力を研究することにつながる

12.2 チューリングマシン

• チューリングマシン(turning machine): 読み書きヘッドによってテープ上の記号を読み取ったり書き込んだりできる制御ユニットから構成されるマシン
• チューリングマシンにより計算できる関数を、チューリング計算可能(Turing computable)という
  • 今日では、計算可能な関数とチューリング計算可能な関数は同じものと考えられている

12.3 万能プログラミング言語

• 万能プログラミング言語(universal programming language)
  • 全てのチューリング計算可能(= 全ての計算可能な関数)を計算するプログラムを表現するのに十分な機能を備えた単純なプログラミング言語のこと

12.4 計算不能関数

• 計算不能関数 = その計算がコンピュータの能力を超えたところにある関数
• 停止問題(halting problem): あるプログラムが与えられた入力に対して停止するかどうかを判定する問題
  • この問題は計算不能であることが証明されている
  • 「特定の停止問題を解くマシンを構築することはできるかもしれないが、任意の停止問題を解くのに使用できる唯一のマシンを構築することはできない」

12.5 問題の複雑さ

• アルゴリズムの複雑をどのように計測すれば良いか？
  • マシンの視点に立った複雑さをよりよく反映した解釈とはアルゴリズムを実行する際に実行しなければならないステップ数を数えること
    • 複雑さ(compexity) = 解を表現するプログラムの大きさではなく、最終的には解を実行する時にマシンが要する時間にかかるもの
    • 問題を解くどの方法でも時間がかかるときに、その問題は複雑であると考える( = 時間計算量(time complexity)

NP問題

• 非決定性アルゴリズム(nondeterministic algorithm)
  • 意思決定をプログラムを実行する機構の創造性に委ねている命令群のことを非決定的といい、そのような命令を含む「アルゴリズム」を非決定性アルゴリズムという
• 非決定性アルゴリズムによって他公式時間で解くことのできる問題 = 非決定的多項式問題(nondeterministic polynomial problem: NP問題)
  • NP問題は多項式時間で解くことができる問題の集合
  • NP問題の中には多項式時間で解くことができない問題も含まれる

12.6 公開鍵暗号

• 因数分解には効率の良い解法が見つかっていないが、それを暗号分野に応用してメッセージの暗号化と復号に広く使用されるようになった
• RSAアルゴリズム(RSA algorithm)
  • 暗号化鍵(encrypting key)と復号鍵(decrypting key)として知られる別の値のセットを用いてメッセージを復号する手段
  • 暗号化鍵を知っている人は目セージを暗号化することはできるが、メッセージを複合化することはできない。メッセージを復号化できるのは復号化鍵を保持している人のみ
  • この性質のため、システムの安全性を脅かすことなく暗号化鍵を広く配布できる
• 公開鍵暗号(public-key encryption)
  • RSAアルゴリズムを用いて、システムの安全性を傷つけることなくメッセージを暗号化する鍵を公開情報にできる仕組み
  • 暗号化鍵は公開鍵(public key)として知られ、復号鍵は秘密鍵(secret key)として知られる
• 今日までRSA暗号によって暗号化されたメッセージを復号化鍵なしに効率的に復号する方法は発見されておらず、そのためRSAアルゴリズムに基づいた公開鍵暗号システムはインターネット通信上でプライバシーを守るために広く使用されている