【学習メモ】 入門 コンピュータ科学 ITを支える技術と理論の基礎知識

第0章 序章

• アルゴリズム
  • 作業をどの様に遂行するかを定めた手順の集合
  • ある特定の型のすべての値についての問題をどの様に解くか
  • ある作業を行うマシンが構成できる場合、その問題はアルゴリズムとして解けるし、アルゴリズムが存在しないなら、その問題の解はマシンの能力を超えたとこにある（計算可能性）
    • ゲーデルの不完全性定理
• プログラム
  • アルゴリズムの表現の1つ
• プログラミング
  • プログラムをマシンが理解できる形にして挿入するプロセス
• 抽象化
  • あるものの外面的な性質と内面的な構造の詳細を区別することを意味する

第1章 データストレージ

ビットとその格納

• ビット（bit）
  • 情報を0と1に符号化したもの
  • あくまで記号に過ぎない
  • 処理するアプリケーションによって意味づけされる
    • ビット自体は意味を持たない
• ゲート（gate）
  • ブール演算の結果出力を生じる装置
• フリップフロップ（flipflop）
  • 値を保持することができる回路
    • Set 側を1にすると、常に1を出力するようになる
    • Reset側を1にすると値は0にリセットされる
• ストリーム（stream）
  • ビットの長い列

メインメモリ

• フリップフロップのような記録回路を大量に保持している
• セル（cell）
  • メモリの構成単位
  • 典型的には8ビット、1byte である
• ビット列自体に意味はないが、メモリセル中のビットを横に並べた時に、左端をhigh-order end、右端をlow-order endという
• 左端のビットはhigh-order bit、右端のビットはlow-order bit と呼ばれる
• アドレス（address）
  • 各セルに付与されている一意な名前
  • 全て数値（0始まり）
  • 順序付けされている
• 構成要素
  • 実際にビットを保持する回路
  • セルにデータを書き込む回路
  • セルからデータを読み取る回路
• ランダムアクセス（random access）
  • 任意のセルに瞬時にアクセスできるということ
    • シークする必要がない
  • ランダムアクセスメモリ（RAM）
    • ランダムアクセスできることから名がついた
• 動的メモリ（dynamic memory）
  • 揮発性の高いメモリ

マスストレージ

• 揮発性が少ない
• 容量が大きい（傾向にある）
• 低価格（傾向にある）
• マシンと記録媒体を分離できる
• オンライン（online）
  • 機器が接続されており、使用可能であること
• オフライン（offline）
  • 機器が接続されておらず、使用できないこと
• メインメモリに比べて遅い
• フォーマット（format）
  • 初期化

磁気ディスク

• 何層にも重なっており、その分のディスクとヘッドがある
• トラック（truck）
  • ヘッドが辿っていく円状の領域
• シリンダ（cylinder）
  • 今からアクセスするトラックの集合
• セクタ（sector）
  • ビット列を記録する円弧状の領域
  • 全てのセクタは同じ数のビットを持つことができる
    • 外周に近いトラック上のセクタは中心に近いトラック上のセクタに比べてデータの密度が小さくなる
      • 密度の小さい外周のトラックをゾーンビットレコーディング（zoned-bit recording）という手法で活用している
        • 隣接する複数のトラックをゾーンとし、ゾーン中のトラックは全て同じ数のセクタを持つ
        • 外側のゾーンと内側のゾーンのセクタ数を異なっていても、ゾーンとしてアクセスを提供することで密度の差による回転数のばらつきを抑える手法
• ディスクシステムの性能評価
  • 尺度
    • シーク時間（seek time）
      • ヘッドをあるトラックから他のトラックへ移動するのに要する時間
    • レイテンシ時間（latency）
      • ヘッドが求めるトラックと重なってから求めるデータの箇所が回ってくるまでの時間
      • おおよそディスクが半周するのにかかる時間となる
    • アクセス時間（access time）
      • シーク時間とレイテンシ時間の和
    • 転送レート（transfer rate）
      • ディスクとコンピュータ間の単位時間辺りのデータ転送量

光学システム

• 光学技術を応用したマスストレージ
• 反射材とその保護膜で構成されている
• 情報は反射材の表面に変調を生み出すことによって記録される
• レーザー光線を用いて回転する表面の不規則性を検知して情報を読み取る
• 円状であるため内側と外側のデータに密度の差が存在する
  • 読み込んでいるレーザー光線の位置によって回転数を制御している
  • コンピュータでの使用では、回転数が速すぎるため、転送速度を調整することによって対応している
• 長い連続したデータを扱うときに性能を発揮する
• ランダムアクセスでは磁気ディスクのアプローチの方が優れている

フラッシュドライブ

• 電気的な信号をストレージ媒体に直接送ることでビットを格納する
  • シリコン半導体の中に電気が格納され、回路の性質が変化する
    • これらの格納域は格納した電気を何年にもわたって保持できる

ファイルの格納と取り出し

• ファイル（file）
  • 情報を概念的にグループ化したもの
• 物理レコード（physical record）
  • ストレージの物理的な性質に合わせたデータのブロック
• 論理レコード（logical record）
  • 情報の性質に合わせたデータのブロック
  • フィールド（field）
    • 論理レコード中の情報の概念的な情報単位
  • キーフィールド（key field）
    • 論理レコードを一意に特定できるフィールド
    • キー（key）
      • キーフィールドの値
• 論理レコードのサイズと物理レコードのサイズが一致することはほとんど無い
  • 物理レコード1つに収まるか、複数の物理レコードに跨るか
• 物理レコードから論理レコードを復元する方法
  • 物理レコードを保持するのに十分なサイズのメモリ空間を確保する
    • 物理レコードの倍数分のサイズが必要になる
      • このサイズがブロックサイズ（block size）となる
    • このように使用されるメモリ領域をバッファと呼ぶ
  • 物理レコードをメモリ上に展開する
  • 整えて、論理レコードを構築する
• バッファ（buffer）
  • ある機器から他の機器へデータを転送するプロセスにおいて、データを一時的に保持するのに使用される領域

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

• テキストの表現
  • ASCII
    • ANSIが採用した
    • 7ビット（1バイト）パターンを使用してアルファベット、句読点、0から9までの数字、制御文字を表現する
  • Unicode
    • 16ビット（2バイト）パターンを使用する
• 数値の表現
  • 2進記法（binary notation）
    • テキストで数値を格納するより効率が良い
  • 2の補数表現記法（2s complement）
    • 整数を表現する
  • 浮動小数点記法（floating point）
    • 実数を表現する
    • 無理数や循環小数、大きな数などは丸められることがある
• 画像を表現する
  • ピクセル（pixel, picture element（画素）の略）
    • 画像上の点の集まり
  • ビットマップ（bit map）
    • 画像全体を符号化したピクセルの集合
    • 符号化
      • 白黒
        • 0と1の1ビットで表現できる
      • グレースケール
        • 複数ビット（通常8ビット）を用いて濃淡も表現できる
      • RGB
        • 光の三原色に対応して（赤、緑、青）の3つの色要素として表現される
        • 各色の要素の強さに1バイトを用いるため、1ピクセルを表現するのに3バイト必要になる
      • 輝度とクロミナンス
        • 構成要素
          • 明るさ
          • 青色クロミナンス
            • ピクセルの青色光との差分
          • 赤色クロミナンス
            • ピクセルの赤色光との差分
        • カラーテレビ発祥の表現のため、グレースケールに変換することができる
          • その場合、明るさだけが用いられる
    • ビットマップ画像処理は画像を任意の大きさに拡大縮小することが難しい
  • 幾何学構造での表現
    • 画像を幾何学構造の集合として表現する
    • 特定のピクセルパターンを再生するのではなく、幾何学構造をどのように表示するかを決めるだけで表示できる
• 音声を表現する
  • 一定の間隔で音波の振幅を標本採取して得た値を数列として記録する手法
    • 電話通信で使用されてきた
  • 電子楽器デジタルインターフェース（Musical Instrument Digital Interface, MIDI）
    • どの楽器がどの音をどれだけの時間発生させるかを符号化する
    • シンセサイザーを用いて音楽を直接生成する
    • 演奏するシンセサイザーによって音が全く異なる

整数を格納する

• エクセス記法
  • 0を1000 として、正の数を1001 、負の数を0111 と数え上げていく記法

データ圧縮

• データ圧縮（data compression）
  • 基本的な情報は保ったままデータのサイズを縮小する手法
• データ圧縮はロスなし（lossless）とロスあり（lossy）に分けられる
  • ロスあり技法の方がロスなし技法よりも圧縮率が高いことが多い
• ランレングス符号化（run-length encoding）
  • 圧縮されるデータの要素の列を、繰り返す要素とその数を示す符号へ置き換える
  • AAABBBBCCCCCCD →A3B4C6D （1個の場合に数字を省略するかは手法による）
  • ロスなし圧縮である
  • 圧縮されるデータが同じ値の長い列である場合に効率的
• 頻度依存符号化（frequency-dependent encoding）
  • 表現するデータ項目のビットパターンを反比例させる手法
  • ハフマンコード（ハフマン符号化）（Huffmann code）が有名
    • 現在使用されている頻度依存符号化の殆どがハフマンコード
  • AAABBBBCCCCCCD
    • 頻度はC, B, A, Dの順
      • Cを1、Bを10、Aを110、Dを111とする
      • 110110110101010100000000111
• 相対符号化（relative encoding）・差分符号化（differential encoding）
  • 連続するデータ単位の差分を用いて符号化が行われる
    • 直前の単位との関係も含めて符号化が行われる
  • ロスあり、ロスなしどちらも対応する
• 辞書式符号化（dictionary encoding）
  • 辞書とは、圧縮されるメッセージが構成される構築ブロックの集合
  • メッセージそのものが辞書への参照として符号化される
  • 適合型辞書式符号化（adaptive dictionary encoding）
    • 符号化のプロセスで辞書を変更できる
    • LZW符号化（Lempel-Ziv-Welch encoding）が有名
      • メッセージが構築される基本構築ブロックを含む辞書からはじめる
      • メッセージ中により大きな単位が見つかるとそれを辞書に追加する
      • 符号化が進む毎に辞書が成長していく
      • 復号化するときに大きな辞書は不要で初期の基本的な辞書のみで良い
        • 復号化していく最中に符号化時と同様に辞書に追加していく
        • 大きな構築ブロックは小さな構築ブロックによって構築されているため、大きな構築ブロックは基本的な辞書、またそれに途中で追加されてきた構築ブロックによって復号化できる

画像を圧縮する

• GIF（graphic interchange format）
  • ロスあり圧縮
  • まずピクセルあたり256色を割り当てる
  • 色をパレットと呼ばれる辞書に割り当てる
  • 画像中の各ピクセルは、そのピクセルの色を表現するパレット中の256色のエントリを示す1バイトとして表現される
• JPEG
  • ロスあり、ロスなしどちらも対応
  • 圧縮率によって複数の戦略を使用する
  • デフォルトの圧縮手法
    • 人間の視覚が色の変化より明るさの変化に敏感であることを利用する
    • 画像を輝度と色度に分割する
    • 2x2ピクセルの正方形の色度の平均を求め、そのブロックの色とする
      • これにより、輝度を保ったまま1/4に圧縮できる
    • 画像を8x8のピクセルブロックへ分割し、離散余弦変換（discrete cosine transform）を用いて変換する
      • 他のブロックと相対的にどうかというデータに変換される
      • ある程度の値以下の場合0となる
    • 更にランレングス符号化や相対符号化などの手法を適用する
  • JPEGでは目に見える劣化なしに1/10から1/30程度へ圧縮できる

音声とビデオを圧縮する

• MPEG
  • 前のフレームとの差分のみを保持することで圧縮する
• MP3
  • 人間の耳が認識できない音を消す
    • 継時マスキング（temporal masking）
      • 大きな音の直後の柔らかな音を感知できない性質
    • 周波数マスキング（frequency masking）
      • ある周波数の音が、近い周波数のより柔らかな音を覆い隠す性質
• 音声やビデオの圧縮システムでは、実時間でのデータ通信に必要な送信速度によって判断されることが多い
• ビット毎秒（bit per second）によって計測される
  • よく使用される単位はKbps、Mbps、Gbpsなど
  • MPEGでは40Mbpsほど、MP3では64Kbpsほど必要となる

通信エラー

• パリティビット（parity bit）
  • 奇数パリティ（odd parity）
    • ビット全体の1の数を奇数個にするようパリティビットを立てること
  • 偶数パリティ（even parity）
    • ビット全体の1の数を偶数個にするようパリティビットを立てること
  • コンピュータのメインメモリでは当たり前に使用されている
    • なので実際のメモリセルでは9ビットのパターンとして格納されている
      • 取り出す際には専用の回路を用いて検査し、エラーが無ければ8ビットパターンを返す
      • エラーがあれば警告する
  • 複数のエラーが発生した時にエラーを検出できない
    • 数の偶奇が変わらない
• チェックバイト（check byte）
  • パターン中に散在する特定のビットの集まりに対するパリティビット
    • 8ビットおきにグループ化しそれぞれにパリティビットを設定するなど
  • チェックバイトの概念よりチェックサム（check sum）や巡回冗長検査（cyclic redundancy check, CRC）として知られるエラー検出方法が考案された

エラー訂正符号

• パリティビットはエラー検出は可能だが、訂正する情報を提供するものではない
• エラーが訂正可能な符号が設計可能である
• ハミング距離（Hamming distance）
  • パターン中で異なるビットの数
  • 各誤り訂正コードに等しいハミング距離をもたせる
  • 復号化する際にそれぞれのコードを比較する
  • ハミング距離が1以下のコードが正しい記号である

第2章 データ操作

• 中央演算処理装置（central processing unit, CPU）
  • コンピュータ内でデータの操作を行う
  • 構成要素
    • 算術論理ユニット（arithmetic logic unit, ALU）
      • 加算減算などのデータの演算を実行する
    • 制御ユニット（control unit）
      • マシンの実行を制御する
    • レジスタユニット（register unit）
      • レジスタのデータを格納したり読み出したりする
    • レジスタ（register）
      • 小容量だが高速なデータ格納用セル
      • 汎用レジスタ（general-purpose register）
        • CPUによって行われる計算の一時的な保管場所
      • 専用レジスタ（special-purpose register）
    • バス（bus）
      • CPUとメモリ間の転送路
    • キャッシュメモリ（cache memory）
      • メインメモリに対するキャッシュ
      • メインメモリの一部を転写している
• プログラム内蔵方式（stored-program concept）
  • データとプログラムをメインメモリ上に配置し、データだけでなくプログラムも書き換えられるようにしたもの

マシン語

• マシン語（machine language）
  • 符号化の体系を含む命令の集合
  • プログラム内蔵方式を適用するため、CPUはビットパターンに符号化された命令を認識できる必要がある
• 縮小命令セットコンピュータ（reduced instruction set computer, RISC）
  • 命令数を少なくし、複雑なタスクは簡単な命令を複数組み合わせて実行するモデル
• 複合命令セットコンピュータ（complex instruction set computer, CISC）
  • 特定の複雑なタスクを一命令で実行する専用命令を多く実装するモデル
• マシン命令
  • データ転送命令
    • データをある場所から他の場所へ移動する命令群
    • メインメモリからデータを読み取るときはload命令 、格納するときはstore 命令と呼ぶ
    • CPUとメインメモリの外側にある危機との通信を行う命令はI/O命令と呼ぶ
  • 算術・論理命令
    • 算術演算や論理演算、値を操作する演算を行う命令群
  • 制御命令
    • プログラムの流れや実行の順序を変える命令群
    • 条件ジャンプ（conditional jump）命令や無条件ジャンプ（unconditional jump）命令などがある
• オペコード（op-code, operation code）
  • どの命令かを表す部分
• オペランド（operand）
  • 命令で使用する値の部分
  • 命令の引数
• 権限レベル（privilege level）
  • 特権モード（privileged mode）
    • 全ての命令を実行できる
    • 特権命令（privileged instruction）
      • 特権モードの時のみ実行できる命令
  • 非特権モード（non-privileged mode）
    • 実行できる命令が制限される
• 命令の実行順序はメモリに格納された順序である
• 命令レジスタ（instruction register）
  • 実行される命令を保持する
• プログラムカウンタ（program counter）
  • 次に実行される命令のアドレスを持つ
• マシンサイクル（machine cycle）
  • CPUが計算を実行するステップ
  • fetch
    • プログラムカウンタが指す命令を取り出す
    • 命令を命令レジスタに格納する
    • プログラムカウンタをインクリメントする
  • decode
    • 命令レジスタの命令をオペコードとオペランドに分ける
  • execute
    • 指定のオペコードに対応する回路を起動する
    • オペランドを入力して結果を取得する
• クロック（clock）
  • 各機器が協調して動作するためのタイミングを取る回路
• 論理演算
  • マスキング（masking）
    • 論理演算を用いて、必要な部分にのみビットを立てることで、該当箇所のみを複写する技法
    • AND演算によるマスキング
      • ビットを立てた部分を複写できる
      • それ以外の箇所は0
    • OR演算によるマスキング
      • ビットを立てた部分を複写できる
      • それ以外の箇所は1
    • XOR演算によるマスキング
      • ビット列の補数を形成できる
  • 循環シフト（circular shift）・ローテーション（rotation）
    • シフトさせてはみ出たビットを反対側の空いたところにセットする
  • 論理シフト（logical shift）
    • シフトして空いたところに0をセットする
    • 左にシフトすると2倍に、右にシフトすると半分の値になる
  • 算術シフト（arithmetic shift）
    • シフトして空いたところに0をセットする
    • 右シフト時は符号を変えないように元の値をセットする
• コントローラ（controller）
  • コンピュータと他の機器の通信を制御する中継機器
  • ポート（port）を介して接続している
  • バスに接続しているため、CPUはバスを通じてコントローラと通信する
  • メモリマップドI/O（memory mapped I/O）
    • メインメモリとコントローラでアドレス空間を共有する手法
    • メインメモリと同じオペコード、LOADとSTOREを使用して機器と通信を行う
    • 特定のアドレスが各コントローラを参照するように紐づけ、該当のアドレスへのアクセスが来た時に、メインメモリを無視しコントローラへアクセスする
  • ダイレクトメモリアクセス（direct memory access, DMA）
    • CPUがバスを使用していないタイミングでコントローラとメインメモリが直接通信を行う手法
    • CPUを介せず直接通信ができるので性能が向上する
    • 処理の流れ
      • CPUがコントローラに読み出し命令を送信
      • コントローラが読み取り演算を実行し、メインメモリから直接読み取る
        • CPUはI/O待ちが無いので、別の処理を実行できる
    • バス上で実行される通信が複雑になるデメリットがある
      • CPUとコントローラがバスのアクセスで競合する
        • フォン・ノイマン・ボトルネック（Von neumann bottleneck）として知られる
• ハンドシェーキング（hand shaking）
  • コンピュータと外部機器間で調整を行うためにステータスワード（status word）などを用いて双方向で対話すること
• パラレル通信（parallel communication）
  • 複数の線上で同時に信号を送ること
  • データを高速に転送できる
  • 順序決定や制御など、複雑な通信経路が必要
• シリアル通信（serial communication）
  • 1本の線を用いて次々に信号を送ること
  • 通信経路が単純
• 電話回線を用いた通信
  • モデム（modem, modulator-demodulator）
    • 送信するビットパターンを音声に変換し、電話回線を用いてシリアルに転送する
    • 受け取った音声をビットパターンに再変換する
  • DSL（digital subscriber line）
    • 通常の音声通話で使用されるより高い周波数帯域をデジタルデータ転送に使用し、音声通話での使用との効率化を図る
• 帯域幅（bandwidth）
  • 転送できる容量が大きいということ
  • ある転送経路が高帯域（broadband）を持つということは、転送速度が速く、同時に多くの情報を運べるということである
• スループット（throughput）
  • 与えられた時間内にどれだけのタスクをこなせるか
• パイプライン化（pipelining）
  • マシンサイクルのステップを重複させること
    • execute中に命令のfetchも同時に行うなど
  • 実行速度を上げることなくスループットを高められる
• 並列処理（parallel processing）
  • SISD（single-instruction stream, single-data stream）
    • 単一の命令によって単一のプロセッサが単一のデータを処理すること
  • MIMD（multiple-instruction stream, multiple-data stream）
    • 複数の命令によって複数のプロセッサが異なるデータを並行して処理すること
    • バスを用いて通信する場合、バスがボトルネックになりやすい
  • SIMD（single-instruction stream, multiple-data stream）
    • 単一の命令によって複数のプロセッサが単一のデータを処理すること
    • あるデータソースに対して、同期を取りながら複数プロセッサで処理する
    • データサイズが大きいものに対し、同じような処理を繰り返す際に有用

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

オペレーティングシステム（operating system）

• コンピュータ全体の動作を管理する
• ジョブ（job）
  • プログラムの実行単位
• バッチ処理（batch processing）
  • 関連するジョブを1つのまとまり（バッチ）として実行すること
  • 初期のオペレーティングシステムはバッチ処理を管理するシステムだった
  • ジョブキュー（job queue）
    • バッチのジョブを溜めておく所
    • 優先度付きの先入れ先出し（first-in, first-out）である
• 対話型処理（interactive processing）
  • ジョブ中にユーザの介入を受け入れる事ができる処理環境
• リアルタイム処理（realtime processing）
  • 動作が瞬時に実行されなければならない処理環境
  • 指定の締切までに必ずジョブを完了させなければならない
  • 複数ユーザが同時に使用する環境において、実装には留意が必要
    • タイムシェアリング（time-sharing）
      • 複数のユーザに同時にサービスを提供する機能
      • マルチプログラミング（multiprogramming）
        • いわゆる並行処理
        • コンピュータの実行時間を細かく区切り、複数のジョブを高速に切り替えることで、同時に実行していると見せかけること
        • 初期の実装では30人程度のユーザのリアルタイム処理が可能だった
    • マルチタスキング（multitasking）
      • 同時に複数の作業を行うこと
• オペレーティングシステムは、プログラムを一度に1つずつ取り出して実行する単純なプログラムから、タイムシェアリングを調整し、マシンのマスストレージ装置内にプログラムやデータファイルを保持し、ユーザからの要求に直接応答する複雑なシステムへと成長した

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

• アプリケーションソフトウェア（application software）
  • マシンを利用して作業を行うためのプログラムから構成される
• システムソフトウェア（system software）
  • コンピュータシステム一般に共通する作業を実行する
  • アプリケーションソフトウェアが必要とするインフラストラクチャを提供する
  • ユーティリティソフトウェア（utility software）
    • コンピュータの利用に必要であるが、オペレーティングシステムには含まれないソフトウェア
    • オペレーティングシステムの機能を拡張する
  • オペレーティングシステム
    • ユーザインターフェース（user interface）
      • ユーザと対話する部分
      • シェル（shell）
        • テキストメッセージを用いる対話環境
      • グラフィカルユーザインターフェース（graphical user interface, GUI）
        • リッチな動きや装飾を持つ対話環境
        • ウィンドウマネージャ（window manager）
          • ウィンドウとそれを利用するアプリケーションの割当とその情報の保持を行う
    • カーネル（kernel）
      • コンピュータの最も基本的な機能を実行するためのシステムソフトウェアが含まれる
      • ファイルマネージャ（file manager）
        • マスストレージに格納されている全てのファイルの情報を保持している
          • 場所やアクセス権限、作成日時など
            • Linuxではinode
        • パス（path）
          • 特定のファイルが存在する場所
      • デバイスドライバ（device driver）
        • 接続されている周辺機器を操作するため、コントローラ（場合によっては直接外部機器）と通信する
      • メモリマネージャ（memory manager）
        • 各プロセスに対するメモリの割り付けを行う
        • ページング（paging）
          • メインメモリの一部をマスストレージに移すことで、実際の容量以上のメモリ領域があるかのように見せること
            • 仮想メモリ（virtual memory）と呼ぶ
          • ページ（page）
            • 保存されるデータを数KB単位で均等に分割したもの
            • メインメモリとマスストレージ間では、ページ単位でデータが交換される
      • スケジューラ（scheduler）
        • プロセスの実行を調整する
      • ディスパッチャ（dispatcher）
        • スケジュールされたプロセスの実行を管理する
        • プロセス実行のための時間をタイムスライス（time slice）という短いセグメント（通常はμ秒単位）に分割し、プロセスを1つのタイムスライス分だけ実行する
          • コンテキストスイッチ（context switch）
            • あるプロセスから別のプロセスに変更する手続き

オペレーティングシステムの起動

• ブートストラップ（boot strapping）・ブースティング（booting）
  • オペレーティングシステム起動の手続き
  • コンピュータに電源が入るたびに実行される
  • CPUは起動される度に特定のアドレスからプログラムカウンタが始まるように設計されている
    • メインメモリは揮発性なので、電源が入る度にメインメモリにプログラムをロードする必要がある
  • 読み取り専用メモリ（read-only memory, ROM）
    • 揮発しないため、電源がなくても起動時に必要なプログラムを格納しておくことができる
    • CPUのプログラムカウンタは起動時にこの領域を指している事が多い
  • ブートローダ（boot loader）
    • 設定に従って特定の場所に格納されているオペレーティングシステムをメインメモリにロードし、プログラムカウンタにそのアドレスをセットする
    • ROMに格納されていることが多い
  • ファームウェア更新（firmware update）
    • オペレーティングシステムの実際のファイルはマスストレージに格納されているので、ファームウェア更新の際はマスストレージにあるファイルの更新と整合性チェックを行うことで、起動中でも更新処理が可能
      • メインメモリにロードされているオペレーティングシステムには影響が無い

オペレーティングシステムにおけるプログラム実行の調整

• プロセス（process）
  • オペレーティングシステムの制御下で動作しているプログラム
  • プロセス状態（process state）
    • プロセスの状態
    • 以下の要素が含まれる
      • プログラムカウンタの値
      • CPUレジスタの値
      • 使用しているメモリセルの値

プロセス管理

• プロセス実行の調整はカーネル中のスケジューラとディスパッチャによって行われる
• プロセステーブル（process table）
  • スケジューラが持つプロセス情報の一覧
  • メインメモリに保持している
  • プロセス実行が要求される度にスケジューラはプロセステーブルに新たなエントリを作成する
    • プロセスに割り付けられたメモリ領域、プロセスの優先順位、プロセス状態などの情報が含まれている
• プロセスが続行可能な状態であれば準備完了（ready）、 ストレージ操作の完了や他のプロセスからのメッセージ到着といった外部イベント発生を待っている時は待機中（waiting）になる
• マルチプログラミングにおけるプロセス切り替えの流れ
  • ディスパッチャはスケジュールされたプロセスにタイムスライスを割り当て、プロセスを実行する
  • 同時にタイマー回路を起動し、タイムスライスの消費を確認する
  • タイマーは作動（タイムスライスを消費）すると、割り込み（interrupt）シグナルを発生させる
  • CPUが割り込みシグナルをキャッチし、現在のマシンサイクルを終了させ、プロセスの情報を保存する
  • CPUから割り込みハンドラ（interrupt handler）へ処理が委譲される
    • ディスパッチャの一部であり、メインメモリの決められた場所に格納されている
    • ディスパッチャが割り込みシグナルに対してどのように対応するかが記述されている
  • ディスパッチャは、プロセステーブルの準備完了プロセスの中で、最も優先順位の高いプロセスを選択し、プロセスを起動する
• マルチプログラミングを用いることで、I/O待ちの時間に別のプロセスを実行することができるなど、マシン全体の効率が向上する

プロセス間競合の調整

• セマフォ（semaphore）
  • あるリソースが何かに獲得されているかを示すフラグ
    • セット（set）で獲得され、クリア（clear）で開放される
    • セットフラグ（値1）ではリソースは何かに格納されている
    • クリアフラグ（値0）ではリソースは利用可能である
    • 競合状態
      • 2つのプロセスがセマフォの状態を確認後、獲得しようとする
      • プロセスAがセマフォの状態を参照する
      • セマフォはクリアフラグを示す
      • プロセスAが割り込まれる
      • プロセスBがセマフォの状態を参照する
      • セマフォはクリアフラグを示す
      • プロセスBがセマフォをセットする
      • プロセスAに処理が戻る
      • プロセスAは既にセマフォの確認が完了している
      • プロセスAがセマフォをセットする
    • 対策
      • 割り込みが発生しないようにする
        • 割り込み不能命令と割り込み可能命令を使用する
        • テストアンドセット（test-and-set）命令を使用する
          • フラグの値の取り出し、値の確認、フラグのセットを1命令で行う
• 相互排除（mutual exclusion）
  • 同時に1つのプロセスしか実行できないようにすること
• クリティカル領域（critical region）
  • 相互排除である命令の区間
• デッドロック（dead lock）
  • 2つ以上のプロセスがそれぞれ他社に割り付けられたリソースの獲得を待ち合って処理が進められない状態
    • 注意：すでにプロセステーブルが満杯でスケジューラが新たなプロセスを登録できないにも関わらずプロセスが部分作業を実行させるためにforkしようとしている場合、どのプロセスも処理を続行できず、デッドロックしてしまう
  • デッドロックの条件 1. 共有不能なリソースをめぐって競合がある 2. 必要なリソースを分割して要求できる - 処理を続行するのに獲得する必要があるリソースが複数存在している 3. 一度リソースを割り当てられた場合、それを強制的に開放することができない
  • デッドロック条件のうち、1つでも取り除くことができればデッドロックしない
    • 1と2の条件を取り除く技法は、デッドロック回避手法として知られる
      • 1について
        • 共有不能なリソースを共有可能にする
          • スプーリング（spooling）を用いる
            • 何かを用いてキューイングしたり、ストレージなどにバッファするなど、都合の良いときまで出力データを保持しておく技法
      • 2について
        • 一度に全ての必要な資源を要求するようにする
    • 3の条件を取り除く技法は、デッドロックの検出と修正として知られる
      • デッドロックが発生した場合それを検出し、割り当てたリソースを強制的に開放する
        • プロセステーブルが満杯でデッドロックした場合、オペレーティングシステムもしくはスーパーユーザがプロセスをkillする事によって解消できる

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

ネットワークの基礎

• ネットワークトポロジーに基づいた分類
  • バス型
    • バスと呼ばれる共通の通信経路に全てのマシンが接続される
    • ハブ（hub）を用いて各コンピュータを連結している
      • 極めて短いバスである
    • 標準であるイーサネットが採用されている
  • スター型
    • 1台のマシンが中心となって、他のすべてのマシンが接続されている
    • 通信手段に電波を用いて、アクセスポイント（accecc point, AP）と呼ばれるセントラルマシンが中心点となって周辺の全ての通信を調整する無線ネットワークで採用されている
• プロトコル（protocol）
  • 動作を決定する規則
  • プロトコル標準の開発は、他の機器と互換性あるネットワークを構築するために無くてはならないプロセス
• CSMA/CD（carrier sense, multiple access with collision detection）
  • バス型ネットワークにおけるメッセージを送信する権利を制御するプロトコル
  • バス上におけるメッセージ衝突を検出し、衝突しないよう制御する
  • 衝突検出の流れ
    • 全てのメッセージはバス上の全てのマシンへ一斉に送信される
    • 各マシンは全てのメッセージを監視しているが、その中で自分宛のメッセージのみ取り出し、他のメッセージは無視する
    • メッセージを送信する際は、バスが静かになるまで待ち、メッセージがバス上に無いタイミングを見計らって送信を開始する
    • 他のマシンが同時に通信を始めたなら、両マシンで衝突を検出し、それぞれランダムに選んだ短時間の休止をはさんで再度送信を試みる
  • スター型ネットワークとは相容れない
    • メッセージが必ずアクセスポイントを経由するため、他のマシンからのメッセージは自身が送出したメッセージによって打ち消されてしまう
    • 他のマシンからの信号が、障害物や距離などが原因で妨害されてしまう可能性がある
• CSMA/CA（carrier sense, multiple access with collision avoidance）
  • スター型ネットワークを採用している無線ネットワークにて使用している
  • メッセージの衝突を回避する手法を採用している
    • もし衝突が発生した場合は再送信する
  • WIFI
    • CSMA/CAの中でもIEEE 802.11で定義されているプロトコル
  • 基本的なアプローチは、送信する機会を待っているマシンを優先するという考えに基づく
  • 衝突回避の流れ
    • 全てのメッセージはバス上の全てのマシンへ一斉に送信される
    • 各マシンは全てのメッセージを監視しているが、その中で自分宛のメッセージのみ取り出し、他のメッセージは無視する
    • メッセージ送信の際は、通信チャネルが空いていたとしてもすぐに送信せず、少し待って他のマシンが使用しないことを確認してから送信を始める
    • もし待っている間にチャネルが使用されてしまった場合、再送信する前にランダムに選択した時間待つ
    • ランダムに選択した待ち時間が終了したならば、待つこと無く空いているチャネルに送信する
  • 送信開始を待たされているマシンが無いことを確認してから送信する形となる

ネットワークの接続

• 性質が同じネットワークの接続（ネットワークの拡張）
  • リピータ（repeater）
    • 2つのバスを連結する
    • メッセージを考慮せず、全てをもう一方へ転送する
  • ブリッジ（bridge）
    • 2つのバスを連結する
    • メッセージに付加されている送信先を見て、もう一方へのメッセージである時に限って転送する
      • 同じ側にある時は転送しない
    • リピータよりも効率の良いシステムを構築できる
  • スイッチ（switch）
    • 複数のバスを連結できる
    • メッセージの送信先アドレスを考慮し、他のバスに宛てられたメッセージのみ転送する
    • 転送される各メッセージは、適切なバスだけに転送される
      • 各バスのトラフィックを最小限に抑える
• 性質の異なるネットワークの接続
  • ネットワークのネットワークを構築する形となる
    • インターネット（internet）として知られる
    • 各ネットワークは、それぞれ独自性を保ちながら自立したネットワークとして機能し続ける
  • ルータ（router）
    • メッセージ転送専用のコンピュータ
    • ネットワークを接続し、インターネットを構築する
      • 各ネットワークの内部的性質を保ったまま接続する必要がある
    • メッセージ転送のために、転送表（forwarding table）を持つ
  • ゲートウェイ（gateway）
    • あるネットワークとインターネットを結ぶ結節点
    • 大体ルータだが、それ以上の意味を含むこともある

ネットワーク通信手法

• プロセス間通信（interprocess communication）
  • ネットワークを利用したプロセス間の通信
  • クライアントサーバ（client server）モデル
    • クライアント（client）
      • 他のプロセスに要求を出す
    • サーバ（server）
      • クライアントからの要求に応える
  • ピアツーピア（peer-to-peer, P2P）モデル
    • 双方向通信によってサービスを享受しながら提供する側にもなる
    • 中央集権的仕組みが存在しない

分散システム

• 分散システム（distributed system）
  • 異なるコンピュータ上でプロセスとして実行されるソフトウェア群から構成されるシステム
  • 高い可用性（high-availability）を求められすシステムで使用される
  • 負荷分散（load-balancing）システムとしても利用される
  • クラスタコンピューティング（cluster computing）
    • 多くの独立したコンピュータを密接に結合して大規模な作業を行う
  • グリッドコンピューティング（grid computing）
    • クラスタほど密接には結合していない、緩く結びついたマシンによって大規模な作業を行う
    • コンピュータの余剰となった計算能力を使用する事が多い
  • クラウドコンピューティング（cloud computing）
    • ネットワーク上で共用される極めて大きなコンピュータを要望に応じて割り当てる方式の分散システム
    • 場所やエネルギーを気にすること無く、コンピュータリソースを柔軟に利用することができる

インターネット

• インターネット事業者（internet service provider, ISP）
  • インターネットを構築し、保守している
• エンドシステム（end system）・ホスト（host）
  • 末端に存在する、個々のユーザがISPに接続するための装置
• IPアドレス（IP address）
  • システム内の各コンピュータに割り当てられた一意のアドレス
  • Internet Corporation for Assigned Names and Numbers（ICANN）
    • インターネットの運営を調整する非営利団体
    • ISPへ連続したIPアドレスのブロックを提供する
• ドメイン（domain）
  • マシンに対するアドレスのより分かりやすい表現
  • ICANNから委託を受けたレジストラ（registrar）によって管理される
  • トップレベルドメイン（top-level domain, TLD）
    • example.comの.com などの接尾辞で示されるドメインの分類
  • サブドメイン（subdomain）
    • ドメイン中の名前の個別の分類
    • 例：sub.example.com
• ドメインネームシステム（domain name system, DNS）
  • メッセージはIPアドレスによって転送されるため、ドメインは最終的にIPアドレスに変換される必要がある
  • DNSルックアップ（dns lookup）
    • DNSを用いて変換を行うプロセス
  • ネームサーバ（name server）
    • ドメインをIPアドレスに変換するサーバ

インターネットアプリケーション

• 電子メール（electronic mail, email）
  • インターネットのユーザ間でメッセージを転送するシステム
  • SMTP（simple mail transfer protocol）
    • メールサーバへ新しいメールを送信する時に使用するプロトコル
  • POP3（post office protocol version 3）
    • メールを使用しているコンピュータにダウンロードする
      • ダウンロードしたらメールは消える
  • IMAP（internet mail access protocol）
    • メールサーバ上でメールや関連するファイルを保存する
      • 保存してもメールは消えない
• ファイル転送プロトコル（file transfer protocol）
  • ファイルを転送するクライアントサーバプロトコル
• telnet
  • 遠隔地にあるコンピュータにアクセスするためのプロトコル
  • 暗号化されていない
• セキュアシェル（secure shell, SSH）
  • 遠隔地にあるコンピュータにアクセスするためのプロトコル
  • 暗号化されている
• VoIP（voice over internet protocol）
  • インターネットインフラストラクチャを用いて音声通話を提供する
  • P2Pモデルで音声データを転送する

ワールドワイドウェブ

• ハイパーテキスト（hypertext）
  • ハイパーリンク（hyper link）と呼ばれるリンクにより、他のドキュメントを参照するテキストドキュメント
  • 現在では画像、音声、ビデオを含むように拡張されたため、ハイパーメディア（hyper media）とよばれる
• ワールドワイドウェブ（world wide web, WWW）
  • 関連する情報が編み合わさったインターネット上のウェッブ
  • WWW上のハイパードキュメントはウェブページと呼ばれる
  • 関連するウェブページの集まりはウェブサイトと呼ばれる
• ブラウザ（browser）
  • ウェブの主なクライアント
• ウェブサーバ（web server）
  • クライアントの要求に従ってドキュメントへのアクセスを提供する
• ハイパーテキスト転送プロトコル（hypertext transfer protocol）
  • ハイパーテキストドキュメントを転送するプロトコル
• ユニフォームリソースロケータ（uniform resource locator, URL）
  • WWW上のリソースの一意なアドレス
  • ブラウザが適切なサーバに接続して目的のドキュメントを要求するために必要な情報を全て含んでいる
• ハイパーテキストマークアップ言語（hypertext markup language, HTML）
  • ドキュメントをどのように表示し、リソースがどのように加えれれているか、ドキュメント中のどの項目が他のドキュメントへのリンクになっているかを示すタグ（tag）の体系
• eXtensible Markup Language（XML）
  • データをテキストファイルとして表現する表記体系を設計するための標準スタイル
• CGI（common gateway interface）
  • サーバ内に格納されているプログラムの実行をクライアントから要求できるようにする仕組み

インターネットプロトコル

• アプリケーション層（application layer）
  • メッセージを生成する
    • 送り先のアドレスを指定する
  • 受け取ったメッセージを処理する
• トランスポート層（transport layer）
  • アプリケーション層から受け取ったメッセージをパケット（packet）の形にする
    • 長いメッセージを小さなセグメントへと分割する
    • 分割したセグメントが到着地で再構成できるよう一連の番号を振る
    • 各セグメントは個別の単位としてインターネット中にて転送される
      • セグメントが長いと他のセグメントの流れを阻害してしまう
    • 各パケットはネットワーク上の様々な経路を別々にたどる可能性もある
  • ネットワーク層から受け取ったパケットを元のメッセージに再構成し、アプリケーション層へ渡す
    • どのアプリケーションへ渡すかは各アプリケーションにポート番号を割り当て、メッセージのアドレスに付加することによって決定する
• ネットワーク層（network layer）
  • トランスポート層やリンク層から受け取ったパケットをどの方向へ飛ばすかを決定する
    • ルータの転送表に基づいてパケットの転送先を決定する
  • パケットが最終的な宛先に届いている事を認識した場合、トランスポート層へ渡す
• リンク層（link layer）
  • ネットワーク層から受け取ったパケットを発送する
    • 具体的な通信技術の詳細を扱う
      • イーサネットであればCSMA/CD、WiFiであればCSMA/CAなど
  • 発送されたパケットはもう一方の端のリンク層で受け取られる
    • 受け取ったパケットはネットワーク層へ渡す
• パケットの転送途中では、ネットワーク層とリンク層だけが転送に関わる
• TCP/IPプロトコルスイート
  • 各層において選択できるプロトコル群
  • トランスポート層におけるプロトコル
    • 伝送制御プロトコル（transmission control protocol, TCP）
      • メッセージ送信前に接続を確立する
      • メッセージを受信したこと知らせる事によってメッセージの全てのパケットを受け取ったことを示す
      • フロー制御（flow control）を行っている
        • 送信側の転送レートを下げることで、受信側のトランスポート層がパンクするのを防ぐ
      • 輻輳制御（congestion control）を行っている
        • 送信側の転送レートを調整して、送信側と受信側の間の混雑を緩和させる
    • ユーザデータグラムプロトコル（user datagram protocol, UDP）
      • メッセージ送信前に接続を確立しない
      • メッセージを受信したこと知らせない
  • ネットワーク層におけるプロトコル
    • IP（internet protocol）
      • 転送（forwarding）と経路制御（routing）を行う
        • パケットにホップカウンタ（hop counter）あるいは生存期間（time to live, TTL）を付加し、転送される回数の上限を定める
          • 転送されるたびに1つ繰り下げ、0になったら転送を辞める
            • パケットがインターネット上を無限に巡回するのを防ぐ
          • 64で十分であると認められている

ネットワークセキュリティ

• ネットワークにおける攻撃
  • サービス拒否攻撃（denial of service, DoS）
    • 多量のメッセージを送りつけることによりコンピュータを高負荷にする攻撃手法
• ファイアウォール（firewall）
  • ネットワーク中のある点を通過するデータにフィルタを掛ける
  • スパムフィルタ（spam filter）
    • ファイアウォールの中でも迷惑メールを阻止するのに特化したもの
• プロキシサーバ（proxy server）
  • サーバの有害な行為からクライアントを守るため、クライアントとサーバの仲介を行う
    • クライアントの内部的な情報を知られないようにする
    • サーバから送られるメッセージをフィルタリングする
• 暗号化
  • FTPS
    • FTPの暗号化版
  • HTTPS
    • HTTPの暗号化版
    • セキュアソケットレイヤ（secure socket layer, SSL）
      • クライアントとサーバ間の接続を暗号化する

第5章 アルゴリズム

アルゴリズムの概念

アルゴリズムの形式的定義

• アルゴリズムとは、停止するプロセスを定義する曖昧さがなく実行可能なステップの順序集合である
  • ステップ間に順序が存在する
  • 実行可能なステップから構成されている
  • ステップが曖昧であってはならない
    • 各ステップの動作を一意にかつ完全に決定できなければならない
  • 最終的に必ず停止しなければならない
• プログラム（program）
  • コンピュータアプリケーションのために設計されたアルゴリズムの形式的な表現
    • 停止しないものもあるため、厳密な定義のアルゴリズムではない
• プロセス（process）
  • プログラムで表現されたアルゴリズムの実行
• 基本命令（primitive）
  • アルゴリズムを表現する、厳密に定義された構築ブロック
  • 基本命令の集合と、基本命令をどのように組み合わせてより複雑なアイデアを表現するかの規則の集合によってプログラミング言語（programming language）が成り立っている

アルゴリズムの発見

• 問題解決の技法
  • 問題解決の段階 1. 問題を理解する 2. 問題を解く計画を考案する 3. 計画を実行する 4. 解の正確さと、それが他の問題を解くためのツールとなり得るかどうか評価する
  • プログラム開発における問題解決の段階 1. 問題を理解する 2. アルゴリズム的な手続きによって、どのように問題が解けるかのアイデアを得る 3. アルゴリズムを定式化して、プログラムとして表現する 4. プログラムの正確さと、それが他の問題を解くためのツールとなり得るかどうかを評価する
• 段階的詳細化（stepwise refinement）
  • 与えられた問題をいくつかの部分問題として考え、段階を追って完全な解に迫る

アルゴリズムの構造

• 繰り返し構造（iterative structure）
  • 逐次探索（sequential search）
    • ある要素がリストの中に存在するかどうかを逐次的に探索する
  • 繰り返し構造・ループ（loop）
    • 制御プロセスと繰り返し部分からなる繰り返し構造
    • 停止条件（terminatiuon condition）
      • 一連の処理を停止する条件
      • ループでは条件に一致した場合に繰り返し部分が実行されるので、ループの制御プロセスにおける条件は停止条件の否定である
  • 再起構造（recursion）
    • 実行している手続きの部分的な要素について、実行している手続き自身を複製し、処理を委譲することで、部分作業として命令の集合を繰り返す構造
    • 基底の場合
      • 再帰的手続きにおける停止条件
      • 最終的な成否を判定する

アルゴリズムの効率性と正当性

アルゴリズムの効率性

• ビッグシータ記法（big-thete notation）
  • アルゴリズムの効率性を比較するための、必要となる計算の量を近似的に表したことを示す記法

アルゴリズムの正当性

• アルゴリズム正当性の証明
  • 前提条件（precondition）が満たされていると仮定して始める
  • 表明（assertion）を評価することで正当性の証明をすすめる
    • 命令の実行前に成立するべき命題
  • プログラムの終わりに設定された表明が仕様が要求する出力に対応していればプログラムは正しいと結論付けられる
  • ループ不変条件（loo[ invariant）
    • 繰り返しの中で必ず真である条件
    • ループにおける制御条件は必ず真である

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

• 識別子（identifier）
  • プログラムの要素の記述的な名前
• 第1世代プログラミング言語
  • マシン語
• 第2世代プログラミング言語
  • マシン語を抽象化したもの
  • アセンブラ（assembler）
    • ニーモニック表現をマシン語の命令に変換するプログラム
  • アセンブリ言語（assembly language）
    • ニーモニックシステムで表現されたプログラム
• 第3世代プログラミング言語
  • アセンブリ言語をさらに抽象化したもの
  • 基本命令が高レベル
    • 大きなステップを表現できる
  • マシン独立（machine independent）
    • 特定のマシンに依存しない
• トランスレータ（tlanslator）
  • 高レベルなプログラムをマシン語へ変換するプログラム
• コンパイラ（compiler）
  • 将来の実行のために前もってマシン語に変換しておく
• インタプリタ（interpreter）
  • 命令を変換しながら高レベル形式のプログラムを実行する

プログラミングパラダイム

• プログラミングパラダイム（programming paradigm）
  • プログラミングのプロセスにどのようにアプローチするかという方法論
  • 手続き型パラダイム（procedural paradigm）・命令形パラダイム（imperative paradigm）
    • 問題を解決するアルゴリズムを発見した上で、そのアルゴリズムを一連の命令列として表現するプログラミングプロセス
  • 宣言型パラダイム（declarative paradigm）
    • 問題を解決するアルゴリズムではなく、解くべき問題を記述するプログラミングプロセス
      • 問題を解決するのにすでに確立されている汎用問題解決アルゴリズムを適用する
    • 論理プログラミング（logic programming）
      • 数学の形式論理を宣言型パラダイムに適用し、論理的な計算を行うプログラミング手法
  • 関数型パラダイム（functional paradigm）
    • プログラムを入力を受け取り出力を生じる、数学における関数として扱い、複数の関数を入れ子にし組み合わせることによって問題を解決するプログラミングプロセス
  • オブジェクト指向パラダイム（object-oriented paradigm）
    • オブジェクト指向プログラミングをベースとしたプログラミングプロセス
    • ソフトウェアシステムをオブジェクト（object）の集合として扱い、各オブジェクトはそれ自身や他のオブジェクトからの要求によって何らかの動作を実行し、それらの相互作用によって問題を解決する
    • メソッド（method）
      • 様々なイベント発生に対して、オブジェクトがどのように振る舞うべきかを記述した手続きの集合
    • クラス（class）
      • データとその振る舞いを持ったデータ型
      • インスタンス（instance）
        • クラスから生成された実体
• 構造化プログラミング（structured programming）
  • 言語の制御文を適切にすることを組み込んだ設計方法論
    • 理解が容易で仕様に忠実なプログラムを生産することを目的としている
• イベント駆動型（event-driven）
  • 明示的な要求ではなく、イベントによって手続きが発火されるシステム

プログラミング言語の実装

• 翻訳（translation）
  • プログラムをある言語から別の言語へ変換すること
  • 元の形式のプログラムをソースプログラム（sourcer program）と呼ぶ
  • 翻訳のプロセス
    • 字句解析
      • 字句解析器（lexicial analyzer）を用いる
      • ソースプログラムからトークン（token）を解釈し、抽出する
        • トークン（token）
          • 意味を構成できる最小の単位
      • プロセスにおいてすべてのコメントは読み飛ばす
    • 構文解析
      • 構文解析器（parser）を用いて、字句解析によって抽出したトークン列をプログラムの構文に基づいて解析する
      • プログラムの文法構造を識別子、各構成要素の役割を認識する
      • 固定フォーマット言語（fixed-format language）
        • プログラムの分を印字されるページの特定の位置に書かなければいけないフォーマット
        • 構文解析のプロセスを単純化するために使用されていた
      • フリーフォーマット言語（free-format language）
        • 文をどこに書くかについて、特に決まりがないフォーマット
        • 人の視点から見て読みやすくなるようにプログラムを記述できる
        • キーワード・予約語（reserved word）
          • ここの句や文の終わりを識別するための語
      • 文法（grammer）
        • プログラミング言語の構文を定義する規則の集合
      • 構文木（parse tree）
        • プログラムの文法構造の構文解析器による解釈の表現
        • 1つの文字列からは1つの決定的な構文木を生成する
          • 曖昧な文法（ambiguous grammar）
            • 構文解析において判断できない曖昧さを含んだ文法
      • 記号表（symbol table）
        • 宣言されている情報を記録した表
    • コード生成
      • コード生成器（code generator）を用いて、構文解析器が認識した構文を実装したマシン語の命令を構成する
      • コード最適化（code optimization）も行う
• 強い性的型付け（strongly typed）
  • 解析時の暗黙的な型変換を許さない、強い型整合性を求める型システム
• 弱い静的型付け（weakly typed）
  • 解析時に都合の良いように型判定を行うもの
• 型の上位変換（type promotion）
  • より上位の型に対する暗黙的な型変換
• 実行時コンパイル（just-in-time compilation, JIT）
  • 実行する直前に翻訳する

宣言型プログラミング

• 論理推論
  • 導出（resolution）
    • ある命題から、結論を導く演繹推論原理
  • 推論規則（inference rule）
    • 命題の集合から結論を導ける手法
  • 導出節（resolvent）
    • 命題から導出された命題
    • 元の命題の論理的帰結である
      • 元の命題が真であれば導出節も真である
    • 節形式（clause-form）
      • 命題の基本構成要素がORのみで結合されたもの
      • 任意の命題は節形式で表現できる
  • 矛盾（inconsistent）
    • ある命題の集合に対して、すべてを真とすることが不可能であること
    • 導出規則を繰り返し適用することで空節を得られる場合、元の命題の集合は矛盾している
  • 単一化（unification）
    • 変数に値を割り当てて導出を可能にすること
    • このプロセスにより、一般的な命題の推論システムを特定のアプリケーションに適用することが可能になる
• 論理プログラミング
  • 述語（predicate）
    • 引数についての事実

第7章 ソフトウェア工学

• 他の高工業製品での保守段階が修理のプロセスであるのに対して、ソフトウェアの保守段階は修正と更新が多い
  • ソフトウェアに変更を行うにはそのソフトウェアの理解が必要であり、ソフトウェアの理解は適切に設計され文書が残っていたとしても困難な作業である
    • 既存のパッケージの変更より、作り直したほうが容易である（多くの場合正しい）口実の元、廃棄されることが多い
  • ソフトウェアの開発段階で若干の労を厭わないことが、変更の段階で大きな助けとなる

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

• 要求分析
  • どのようなサービスを提供するかを特定し、サービス提供に関しての条件を識別し、かつ外部世界とどのように相互作用するかを定義するプロセス
  • 利害関係者（stakeholder）からの入力が重要
  • ソフトウェア要求仕様書（software requirements specification）
    • ソフトウェアユーザの求めるものが何であるかを収集して分析するとともに、プロジェクトの利害関係者間での要望、必要性、費用、実現可能性等のトレードオフについて交渉したうえで、完成したソフトウェアが持たなければならない機能とサービスを特定し、最終的な要求をまとめたもの
  • コミュニケーション不足と要求仕様の頻繁な変更が失敗の要因になる
• 設計
  • 要求分析で得た解決すべき問題の解放を構成する
    • 解放にはソフトウェアシステムの内部構造も含まれる
  • プログラムに変換できうる情報を持つ、できるだけ詳細なソフトウェアシステム構造を構成する
• 実装
  • 実際にソフトウェアシステムを使用できるように開発・構築する
• テスト
  • ソフトウェアの品質を保証するためのすべてのプロセス

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

• ウェーターフォールモデル（waterfall model）
  • 一方通行的な開発モデル
  • 次のステップは、前のステップが完了してから行われる
• プロトタイピング（prototyping）
  • プロトタイプと呼ばれるシステムの不完全な版を構築して評価する
• インクリメンタルモデル（incremental model）
  • プロトタイピングを繰り返し、システムを段階的に拡充していく開発モデル
  • 進化型プロトタイピング（evolutionary prototyping）
    • プロトタイピングを繰り返すことで、完全版を構築すること
• 反復モデル（iterative model）
  • プロトタイピングを繰り返し、各版を詳細にしていく開発モデル
  • スローアウェイプロトタイピング（throwaway prototyping）
    • 最終設計を実装するにあたって、一から設計をやり直すためにプロトタイプを捨てること
    • ラピッドプロトタイピング（rapid prototyping）
      • ユーザの要求分析において仕様を明確にするために、デモンストレーションのためのプロトタイプを高速に開発すること
• アジャイルメソッド（agile method）
  • エクストリームプログラミング（extreme programming, XP）
    • 要求分析や設計よりも、速く機能を開発することに重点を置いている
    • 個人ではなくチームとしてどれだけの成果物を生むかを重視している

ソフトウェアにおけるモジュール

• モジュール性（modularity）
  • モジュール（module）
    • ソフトウェアの動作の一部を受け持つ管理可能な単位
  • ソフトウェアをモジュールとして分割すること、またされていること
  • 何がモジュールを構成するかが、ソフトウェア設計プロセスの最初の目標を決定する
  • 将来の更新時に若干のモジュールだけに変更を加えればよいようにすることで、変更作業を行う技術者がパッケージ全体に取り組む代わりに、システムの特定の部分にだけ集中して変更を加えれば良いようにするのが良い
• 結合度（coupling）
  • ある機能に関連するモジュールがどれだけ独立しているかを示す指標
  • 制御結合（control coupling）
    • 実行制御をあるモジュールから別のモジュールへ渡すときに発生
  • データ結合（data coupling）
    • モジュール間でのデータの共有度
    • データ形式の変更はどちらのモジュールにも波及する
  • オブジェクト指向パラダイムではオブジェクト間のデータ結合を最小にできる
  • 大域データ（global data）
    • システム中のすべてのモジュールで自動的に利用可能になるデータ
    • 大域データに依存したモジュールに変更を加える場合、そのモジュールが他のモジュールとどのように相互作用しているかを見極めることは難しい
• 凝集度（cohesion）
  • モジュールの内部要素の関連の強さを示す指標
  • 論理的凝集（logical cohesion）
    • モジュール内の構成要素が論理的に類似の動作を行うため、同じモジュールに配置されている場合
    • 凝集度は低い
  • 機能的凝集（functional cohesion）
    • モジュール内のすべての要素がある1つの動作を実行することでまとまっている場合
    • 凝集度は高い
  • オブジェクト指向設計では、すべてのオブジェクトは論理的凝集である
    • オブジェクト内のメソッドは緩やかに関連する動作を実行しているに過ぎない
• 低い結合度と高い凝集度を目指す
  • （メモ者体感だと）凝集度が高くなるにつれ、結合度は低くなる印象
• 情報隠蔽（information hiding）
  • 情報をソフトウェアシステムの特定の部分に制限すること
  • 2つの目標を持つ
    • 設計目標
      • 他のモジュールがモジュールの内部情報にアクセスしなくても良いように設計する
      • 凝集度の最大化、結合度の最小化
    • 実装目標
      • モジュールの境界が明確になるようにする
      • 局所変数の利用、カプセル化の適用、よく定義された制御構造

ソフトウェア開発ツール

• データフロー図（dataflow diagram）
  • システム中をデータがどのように流れるかを解析することで得られる情報を表現する手段
• データディクショナリ（data dictionary）
  • ソフトウェアシステム全体を通して出現するデータ項目の辞書
  • ステークホルダと開発者の間でのコミュニケーションを改善することを目的とする
  • システムに統一性をもたせることを目的とする
• 統一モデリング言語（unified modeling language, UML）
  • オブジェクト指向パラダイムに基づいて開発されたツール群
  • ユースケース図（use case diagram）
    • ソフトウェアシステムを外部から見た時の振る舞いを表す図
    • ユースケース（use case）
      • システムとユーザとの対話
    • アクタ（actor）
      • ユースケースを利用する者
  • クラス図（class diagram）
    • ソフトウェアシステムの内部的なオブジェクト指向設計を表現する図
    • 関連（associate）
      • クラス間の関連を表す表記体系
    • 多重度（multiplicity）
      • 1つのクラスのいくつのインスタンスがもう一方のクラスのインスタンスと関連しているか
      • 一対一関係（one-to-one relationship）
        • 両クラスのインスタンスが必ず1つずつ関連すること
      • 一対多関係（one-to-many relationship）
        • 1つのクラスのインスタンスに対して、別のクラスの複数のインスタンスが関連すること
      • 多対多関係（many-to-many relationship）
        • あるクラスの複数のインスタンスが別のクラスの複数のインスタンスと関連すること
  • 相互作用図（interaction diagram）
    • 実行時に発生するイベントの流れを表現する動的な図
    • シーケンス図（sequence diagram）
      • システムの構成要素間のコミュニケーションを表す図
      • 時系列は上から下へと遷移する
      • 生存線（life line）
        • システム構成要素から縦に引かれている線
      • システム構成要素間のコミュニケーションは生存線を結ぶラベル付きの矢印で示される
      • フレーム（frame）
        • 特定のシーケンスを表すブロック
      • 相互作用フラグメント（interaction fragment）
        • 1つの図の中で別のシーケンスを表現するのに使用される
        • loop
          • ループを表す
        • alt
          • 分岐を表す
  • CRC（class-responsibility-collaboration）カード
    • オブジェクトの記述を書いておく索引カード
    • 構造化ウォークスルー（structured walkthrough）
      • システム中のオブジェクト毎にカードを作成し、チームの各メンバががカードを保持し、カードに記された役割を演じることで、システムのシミュレーションを理論実験として行うこと
• デザインパターン（design pattern）
  • ソフトウェアの設計において繰り返し現れる問題を解くための開発前モデル

品質保証

ソフトウェアテスト

• プログラムのあり得る経路すべてをテストすることは不可能
• グラスボックステスト（glass-box testing）
  • テストがソフトウェアの内部的構造に基づいて設計されているもの
  • パレートの原理（pareto principle）
    • ソフトウェアのエラーが固まって現れる傾向に基づき、そのようなモジュールに対して集中してテストを行うことで、すべてのモジュールに対して均等にテストを行うよりも多くのエラーを発見すること
    • 集中した部分に努力を傾注することによって結果を急速に向上できる
  • 基礎パステスト（basis path testing）
    • ソフトウェア中の各命令が少なくとも1回は実行されるようにテストデータの集合を作成すること
• ブラックボックステスト（black-box testing）
  • ソフトウェアの内部的構造に依存しないテスト
    • ユーザ視点で実行される
  • 境界値分析法（boundary value analysis）
    • データ範囲の境界に近いデータでテストすること
  • ベータテスト（beta testing）
    • ソフトウェアの予備版を潜在的な一部のユーザに配布し、現状のソフトウェアがどのように動作するかを得るもの
  • アルファテスト（alpha testing）
    • ベータテストを開発者の側で行うもの

ドキュメンテーション

• ユーザドキュメンテーション（user documentation）
  • ユーザ側が読むことを期待したドキュメント
  • ソフトウェアの機能の説明、操作方法など
  • マーケティングツールでもある
• システムドキュメンテーション（system documentation）
  • ソフトウェアの内部構造を記述している
  • 保守作業に資するためのもの
  • 構成要素
    • プログラムのソースコード
    • 設計文書と、その意思決定にまつわる記録

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

• システムと人間のユーザとの間のコミュニケーションエラーは最小化されなければいけない
  • システムのインターフェースがユーザにとって便利なように設計しなければならない
• エルゴノミクス（ergonomics）
  • 人間の生理機能と調和するシステム設計
• コグネティクス（cognetics）
  • 人間の精神的機能と調和するシステム設計
  • 習慣の形成による、本来の機能の喪失に注意する
  • 人間は同時に7つの事柄しか扱うことができない (George A. Miller., 1956)
    • 人間の記憶に頼るのではなく、すべての関連情報を提示するように設計することが重要
• GOMSモデル
  • ユーザ目標（goal）
  • 操作（operator）
  • 方法（method）
  • 選択規則（selection rule）
  • インターフェースを使用する人間の動作を基本ステップの並びとして分析する方法論
  • 作業を実行するのに要した時間によって比較する

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

• 知的財産法（intellectual property law）
  • ソフトウェアにおける所有権を定めた法
  • 著作権と特許法に基づく
• ソフトウェアライセンス（software license）
  • ソフトウェアにおける開発者の権利
• 製造物責任
  • 製品についての責任を限定する免責条項
  • 製造物によって生じた事故に対する過失を認められた場合、免責条項が認められることはほとんどない

第8章 データ抽象

• 配列（homogeneous array）
  • 全ての構成要素が同じデータ型である直列のブロック
• 構造体（structure）
  • 名前付けされた異なるデータ型で構成されているブロック
  • 構成要素（component）
    • 構造体の各項目

基本データ構造

リスト（list）

• 一列に並べられた要素の集合
• 頭部（head）
  • 先頭の要素
• 尾部（tail）
  • 先頭を除いた残りのリスト
• スタック（stack）
  • 頭部でだけ要素の挿入や削除を行うことがデータ構造
  • トップ（top）
    • スタックの頂点
    • ここでのみ操作を行える
  • ボトム（bottom）
    • スタックの底部
    • 一番最後に操作できる対象となる要素
  • プッシュ（push）
    • スタックのトップに要素を挿入する
  • ポップ（pop）
    • スタックのトップから要素を取り除く
  • 後入れ先出し（last-in, first-out, LIFO）構造
    • 最後に追加したものを最初に取り出す方針のデータ構造
• キュー（queue）
  • 要素の取得をリストの先頭から、要素の追加をリストの末尾へ行うデータ構造
  • 先入れ先出し（first-in, first-out, FIFO）
    • 最初に追加したものを最初に取り出す方針のデータ構造

木（tree）

• 階層構造を持ったデータ構造
• 親（parent）
  • 直近の上位の要素
• 子（child）
  • 直近の下位の要素
• 各要素は0（最上位の要素）~1個の親を持ち、0個以上の子を持つ
• 根（root）
  • 木の最上位の要素
  • 木の頂点
• 節点（node）
  • 木の各要素
• 葉（leaf）・終端節点（terminal node）
  • 最下位の要素
  • 子を持たない
• 深さ（depth）
  • 根から葉までの最長経路の節点数
  • 親子関係の総階層数
• 二分木（binary tree）
  • 各親節点が2個より大きい子を持たない木
• 部分木（subtree）
  • 木の中の任意の節点に注目した時に、その節点を頂点とした木構造
• 枝（branch）
  • 親要素から見た部分木である子要素

データ構造の概念

• ポインタ（pointer）
  • あるデータを指し示す情報
  • 命令ポインタ（instruction pointer）
    • プログラムカウンタのこと
• ガベージコレクション（garbage collection）
  • 使用していないメモリ領域を将来の使用のために回収して解放する機構
  • メモリリーク（memory leak）
    • 回収に失敗し、使用していないメモリ領域が解放されないままになっている状態

データ型の拡張

• ユーザ定義データ型（user-defined data type）
  • 基本データ型を用いて新たにユーザが定義したデータ型
• 抽象データ型（abstract data type）
  • データの構造と、その演算の定義を持つデータ型

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

• 即値アドレッシング（immediate addressing）
  • オペランドにデータ自体が含まれている
• 直接アドレッシング（direct addressing）
  • オペランドにデータのアドレスが含まれている
• 関節アドレッシング（indirect addressing）
  • オペランドにデータのアドレスを格納している場所へのアドレスが含まれている

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

• データベース（database）
  • 様々な視点から情報にアクセスできるようにデータ項目が内部的に連結されている
• フラットファイル（flat file）
  • 伝統的なファイルシステム
  • 1つの視点だけから情報を表現している
• スキーマ（schema）
  • データベースの全体構造
  • サブスキーマ（subschema）
    • 特定のユーザに取って必要な部分の構造

データベース管理システム（database management system, DBMS）

• クライアントからの要求に従って、実際のデータベースを操作するシステム
• 実際のデータベースを抽象化する
  • データがどのようなデータベースに格納されているかを気にする必要がない
• データベースへのアクセスを制御する
• データの独立性（data independence）
  • 外部のソフトウェアを変更すること無く、データベースの構成を変更できる性質
    • 全体のスキーマと変更を要求しているクライアントへのサブスキーマのみ変更すれば良く、それ以外のサブスキーマを変更する必要がない
• データベースモデル（database model）
  • データベースの概念的外観
• データベース管理システムは、データベースの概念的外観に基づいて記述された命令を、実際のデータベースストレージシステムで必要な動作へと翻訳する

関係モデル

• 属性（attribution）
  • あるデータにおいて、同じ項として扱われる情報の集合
• タプル（tuple）
  • 関連している属性の組
• 関係（relation）
  • 属性の関連とそこから生じるタプルの集合に意味を見出したもの

SQL（structured query language）言語

• データベース管理システムに対して関係を問い合わせるための言語
• 求める関係を宣言型の文として記述する
• データベース管理システムは指定された関係を、関係演算を用いて演算し、結果を返答する
• 関係の構造の定義、関係の生成、関係の内容の変更も行う

オブジェクト指向データベース（object-oriented database）

• 関係を反映するように連結されたオブジェクトから構成されたデータベース
• 委託されたオブジェクトに恒久的な格納場所を提供する
  • 永続的（persistent）である

データベースの完全性

• データベース管理システムは各トランザクションの動作をログとして記録している
• コミット時点（commit point）
  • トランザクションの全てのステップがログに記録された時点
  • この時点でデータベース管理システムは、トランザクションの動作がデータベースに反映される事を保証する責任を引き受ける
• ロールバック（roll back）
  • 変更されたがコミットされていないデータを元に戻す
  • ロールバック時に変更を試みているデータをロックすることで、他のトランザクションから不整合なデータを見えないようにする
  • 波及ロールバック（cascading rollback）
    • ロールバックされるトランザクションの更新後のデータに基づいてコミットされているトランザクションについてもロールバックする必要があるため、ロールバック対象のトランザクションが波及的に増えていく問題
• トランザクションの状態の基づく問題
  • 不正確な合計問題（incorrect summary problem）
    • あるトランザクションが変更を実行している最中に、別のトランザクションがその内容を用いて集約演算を行う場合に、実行順序によって結果が異なってしまう問題
  • 遺失更新問題（lost update problem）
    • トランザクションが同時に行われた際に、両方が同じ初期値に基づいて演算しているため、片方のトランザクションがもう一方のトランザクションの結果を無視して結果を反映させてしまう問題
  • データベース管理システムではこれらの問題を解決するために、新しいトランザクションをそれ以前に生成されたトランザクションが完了するまで待ち行列（キュー）に入れることでトランザクションを一度に1つずつ実行して完了させるようにしている
    • データベース管理システムは、トランザクション間のタイムシェアリングを管理するスケジューラを含んでいる
• ロックプロトコル（locking protocol）
  • 共有ロック（shared lock）
    • 他のトランザクションに対しての共有ロックも許可する
  • 排他ロック（exclusive lock）
    • 項目を変更するため、データへの参照を占有化するロック
    • 排他ロックが設定されているデータに対しては他のロックを設定できない
    • 共有ロックが設定されているデータに対して排他ロックを設定できない
  • 負荷待機プロトコル（wound-wait protocol）
    • 古いトランザクションに対してロックの優先権を与え、新しいトランザクションは古いトランザクションが完了するまでロールバックさせられ続ける
      • ロールバックしていく内に古いトランザクションとなり、優先権が与えられる

ファイル構造

• 順編成ファイル（sequential file）
  • 情報が1つの長い列として扱われるファイル
  • ファイルの順序を保存するようにマスストレージに記録する必要がある
  • 読み込む際は現れる順に処理すれば良い
  • ファイル終端記号（end-of-file, EOF）
    • 順編成ファイルの終わりを示す記号
      • センチネル（sentinel, 番兵）レコードを置く
      • ファイルシステムを用いて終端を識別する
• 索引ファイル（indexed file）
  • 求める論理レコードがどこに格納されているかを示すエントリのリストを含むファイル
  • 必要時にアクセスが容易になるように、処理の開始前にメインメモリに転送される
  • 索引は階層構造もしくは木構造であることが多い
• ハッシュファイル（hash file）
  • ハッシュ法（hashing）を用いて作成された、ストレージのエントリへの高速なアクセスを提供するファイル

データマイニング

• データの集合に対して特定のパターンを発見し、様々な特徴付けを行う
• データウェアハウス（data warehouse）
  • 静的なデータの集合
• クラスタ分析（cluster analysis）
  • グループ化を可能とするようなデータ項目の性質を見つける試み
• 相関分析（association analysis）
  • データグループ間の連結を発見しようとする試み
• 外れ値分析（outlier analysis）
  • データの標準に宛ては非ないデータを見つける試み
  • 逸脱を見つけることで、通常では起こり得ない異常動作を検知できる
• 時系列パターン分析（sequential pattern analysis）
  • 時間とともに変換する振る舞いパターンを見つける試み
  • 将来の予測を立てる

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

• データベースアプリケーションは、保持者にとってもデータの対象者にとっても利益があるが、プライバシーが失われることも確かである
  • 情報が不正確であった時の不利益はより絶大である
• データベース技術において、プライバシーを考慮することは最優先事項である

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

• 画像処理（image processing）
  • 画像の中のピクセルを解析して、画像を解釈するためのパターンを識別すること
• 2Dグラフィックス（2D graphics）
  • 2次元図形をピクセルパターンに変換し、画像を生成する
• 3Dグラフィックス（3D graphics）
  • 3次元図形をピクセルパターンに変換し、画像を生成する
  • 3Dグラフィックスを用いた画像の生成ステップ
    • モデリング（modeling）
      • 画像化される場面の作成、符号化、保存、操作
    • レンダリング（rendering）
      • 画像の生成
      • 解析幾何学を応用し、場面内の物体を投影面（projection plan）と呼ばれる平面に投影する
        • 投射投影（perspective projection）を用いる
          • 視点（view point）または投影中心（center of projection）と呼ばれる1つの点から延びる投影線（projector）に沿って物体を投影する
        • 平行投影（parallel projection）
          • 投影面から平行に延びる投影線に沿って物体を投影する
        • 画像ウィンドウ（image window）
          • 投影面の中の最終的に画像となるエリアの境界線
      • 画像ウィンドウに投影される部分が確定した後、最終的な画像に含まれるピクセルの見え方を計算する
      • 各ピクセルの色が確定した後、結果をフレームバッファ（frame buffer）にビットマップ表現として格納する

モデリング

• シーン（scene）
  • 3Dグラフィックスのにおける、舞台でのセット
• オブジェクト（object）
  • 大道具、小道具
• 3Dグラフィックスシーンはデジタルに符号化されたモデルとして構築されたオブジェクトから構成されている

オブジェクトのモデリング

• 形状表現
  • 3Dグラフィックスのオブジェクトは、平面パッチ（plannar patch）と呼ばれる小さな多角形の集合、ポリゴンメッシュ（polygon mesh）により形成される
    • デジタイズ（digitizing）
      • 3次元空間内での連続的な曲線に点を打ち、それをポリゴンメッシュの頂点とすること
    • 手続きモデル（procedural model）
      • 自動的に目的の形状を作り出すプログラム
      • 似ているものの細部が異なる複数の複雑なオブジェクトを効率よく作成できる
      • パーティクルシステム（particle system）
        • 粒子の巨大な集合としてオブジェクトの基礎構造をシミュレートする
        • 例： 水を大量の小さい丸い粒子の集合として表現するなど
  • ベジェ曲線（bezier curve）
    • 少数の制御点だけで3次元空間内の曲線線分を定義できる
      • 制御点の2点は曲線線分の両端を定義する
      • 他の点は曲線をどのように曲げるかを定義する
    • ベジェ曲面（Bezier surface）
      • ベジェ曲線の3次元的表現
  • フラクタル（fractal）
    • 自己相似性を有した図形
      • 一部分と全体の形状が似た形である
• 表面特性
  • テクスチャマッピング（texture mapping）
    • オブジェクトの表面に定義済みの画像を貼り付ける
      • レンダリングプロセスでオブジェクト上の1点をどのように表示するかを問われた際に、テクスチャの対応する点の外観を使用する

シーン全体のモデリング

• シーングラフ（scene graph）
  • シーン中での位置、サイズ、向き度の情報をまとめたもの
    • 光源を表す特別なオブジェクトやカメラを表す特別なオブジェクトも含まれる
      • 位置、向き、カメラの焦点の属性なども記録される
  • シャッターを押した時に画像の表示に影響を与える全てのオブジェクトの情報を持つ

レンダリング

• シーングラフに含まれるオブジェクトがどのように表示されるかを決定するプロセス

光と表面の相互作用

• 物体の見え方は物体が反射する光によって決まるため、オブジェクトの外観を決める作業は、究極的には光の振る舞いをシミュレートする作業になる
• 反射（reflection）
  • 法線（normal）
    • 物体の表面に対して垂直な線
  • 入射角（incidence angle）
    • 光線の法線からの相対的な角度
  • 反射した光が向かう角度は入射角と同じである
  • 鏡面光（specular light）
    • 入射角と反射角が同じ光
    • 表面が非常に滑らかである
    • 表面との接触時間が僅かなので、光源の色を保つことが多い
    • 多くの光を反射するため輝いて見える
  • 拡散光（diffuse light）
    • 反射光が拡散する光
    • 表面が滑らかでなく、一度反射した光が別の表面にぶつかることで光が拡散する
    • 表面との接触時間が長いので、素材の光の吸収の影響を受け、物体の色に近くなることが多い
    • 反射する光が鏡面光に比べて少ないため、鈍く見える
  • 環境光（ambient light）
    • 特定の光源や向きを持たない光
  • 異方性表面（anisotropic surface）
    • 向きによって輝いたり鈍くなったりする表面
  • 等方性表面（isotropic surface）
    • 反射のパターンが一様な表面
• 屈折（refraction）
  • 透明な物体の表面を通過する時に向きが変わる現象
  • 屈折率
    • どの程度光線を曲げるかの比率
    • 素材の密度と関係している
      • 密度が高い素材は屈折率が高い
    • 屈折率がより高い素材に光線が入っていくと、光線は法線の方向へ曲がる
• エイリアシング（aliasing）
  • 描こうとしている画像の中のパターンと画像を構成するピクセルの密度が噛み合わない時に発生する

レンダリングパイプライン（rendering pipeline）

• シーングラフから画像を作り出すプロセス
  • ほとんどの対話型ビデオゲームが採用
• 不透明なオブジェクトを処理する
  • 屈折は問題にならない
• オブジェクト間の相互作用を無視するため、鏡や影については考慮しない
• ステップ
  • カメラから見えるオブジェクトを含む領域を確定させる
    • 視体積（view volume）と呼ぶ
      • 投影中心とそこから画像ウィンドウの4つの角の方向へ向かう直線によって定義される四角錐の中の空間
  • 視体積を確定させた後、視体積に含まれないオブジェクトやオブジェクトの一部をレンダリングの対象から外す
    • この手順を行うため、シーングラフは木構造となっている
  • クリッピング（clipping）を行う
    • 各オブジェクトの視体積の外にはみ出す部分を切り取る処理
  • 最終的な画像のピクセル位置に対応付けられる平面パッチ状の点を確定する
    • 最終的な画像に含まれるのはこれらの点だけである
    • オブジェクトの細部がピクセルとピクセルの間に入ってしまった場合、ピクセルによって表現できないため、最終的な画像には含まれない
    • 走査変換（scan conversion）・ラスタライズ（rasterization）
      • シーン内の点とピクセル位置を対応付ける処理
      • 投影中心から画面ウィンドウのピクセル位置を結ぶ直線を延ばし、投影線と平面パッチが重なり合う点を突き止める
      • 隠面除去（hidden-surface removal）
        • 別の平面パッチに隠されているなど、最終的な画像では隠されてしまうようなシーン内の点を突き止めて取り除く処理
        • バックフェースカリング（back face culling）
          • 隠面除去のうち、オブジェクトの背面を表すポリゴンメッシュの平面パッチを取り除く処理
      • 画家のアルゴリズム（painter’s algorithm）
        • シーンに含まれるオブジェクトをカメラから遠い順に並べ、遠いオブジェクトから走査変換していき、近くのオブジェクトの走査変換結果によって古い結果を上書きする
      • Zバッファ（z-buffer）
        • 一番近いオブジェクトのピクセルをバッファする
          • 初期値はレンダリングを試みているオブジェクトまでの最大距離
  • シェーディング（shading）
    • 問題の点からカメラに投射される光の特徴を計算すること
    • フラットシェーディング（flat shading）
      • 個々の平面パッチの表面を平らだとする手法
    • 平面パッチの頂点に向きの情報を利用する手法
      • 法線ベクトル（normal vector）
        • 個々の頂点に、元の表面の向きの情報を付与する
      • グーローシェーディング（Gouraud shading）
        • 向き情報を色情報に変換し、色情報を補間する
      • フォンシェーディング（Phong shading）
        • 問題の点の向きが推定できるまで向き情報を補間してから、色情報に変換する
        • 表面の向きの変換に敏感であるため、平面パッチ内部の鏡面光を適切に検出できる傾向にある
    • バンプマッピング（bump mapping）
      • 表面の明確な向きに対し小さなバリエーションを加え、表面を凸凹に見せる

レンダリングパイプラインのハードウェア

• レンダリングパイプラインの処理を実行する電子回路が直接実装されている
• グラフィックカード（graphics card）・グラフィックアダプタ（graphics adapter）
  • レンダリング処理を行う専門のチップ
  • 専用コントローラとしてコンピュータのバスに接続される
• グラフィックスハードウェアを用いることで、ソフトウェアはシーングラフを供給するだけで良くなる
  • ハードウェアはパイプラインのステップを実行し、結果をフレームバッファにセットする
• OpenGL（open graphics library）
  • アプリケーションとグラフィックスハードウェアの仲介をする標準ソフトウェアインターフェース

ライティングモデル

• ローカルライティングモデル（local lighting model）
  • パイプラインが個々のオブジェクトを個別にレンダリングする手法
• グローバルライティングモデル（global lighting model）
  • オブジェクト間の相互作用を考慮に入れレンダリングを行う手法
  • レイトレーシング（ray tracing）
    • 光線を逆に辿って光源を見つけるプロセス
    • ステップ
      • レンダリングされるピクセルを選択する
      • 該当のピクセルと投影中心を結ぶ直線を特定し、画像ウィンドウを貫く形で延長する
      • 直線をトレースし、オブジェクトと接触する箇所を特定する
      • オブジェクトが光源であれば、そのピクセルは光源上の点としてレンダリングされる
      • オブジェクトが光源でなければ、表面の特性を評価し、反射された入射光をトレースし、オブジェクトの評価とさらなる入射光の探索を繰り返す
    • 透明なオブジェクトに対する光線をトレースする場合、屈折を考慮する
    • レイトレーシングは入射光を逆向きに辿っていく特性上、鏡面光しかトレースできない欠点がある
    • 分散トレーシング（distributed ray tracing）
      • 反射を起こした点から微妙に異なる向きに延びる複数の光線をトレースすることで、鏡面光以外のトレースを可能にする
    • 終了条件
      • 指定の回数の探索が終了する、吸収率の高い表面に遭遇するなど
  • ラジオシティ（radio-sity）
    • 平面パッチ間で放出され合う光エネルギー全体を考慮した領域的なアプローチ
    • 個々のオブジェクトの外観は、他のオブジェクトから受ける光エネルギーを考慮して決定される
    • フォームファクタ（form factor）
      • 他のオブジェクトから放出された光によって受ける影響の度合いを決定するパラメータ
    • ラジオシティでは色滲み（color bleeding）が表現できる

第11章 人工知能

知能とマシン

• エージェント（agent）
  • 環境からの刺激に反応する装置
  • 手続き的知識（procedural knowledge）
    • エージェントがどのように学ぶかという知識
    • 誤った行為には罰を、正しい行為には報償を得ることで適切な動作を学ぶ
  • 宣言的知識（declarative knowledge）
    • エージェントが何を学ぶかという知識
    • エージェントが持つ知識の事実を繰り返し拡張したり変更することで、将来発生する事象への合理的反応を決定する
  • エージェントの基本
    • 受け取った情報の認識・理解
    • 目標達成のための計画・実行
• チューリングテスト（Turing test）
  • 質問者（人間）が、相手が人間かマシンであるかを告げられずに対話を行う
  • 質問者が、対話相手が人間かマシンかを区別できなければ、そのマシンは知的に振る舞ったとする

認識

画像理解

• 画像理解のためのステップ
  • 画像処理（image processing）
    • エッジ強調
      • 数理技法を適用して画像中の領域の協会を検出する
    • 領域発見
      • 画像中の明るさ、色、質感といった共通の性質を特定する
    • 平滑化
      • 画像中のノイズなどを取り除く
      • 適用しすぎると重要な情報が失われる
  • 画像分析（image analysis）
    • 抽出された要素が何を表すかを決定する
    • その画像が何であるかの仮定をし、構成要素を、別の構成要素と関連付けていく
      • 人間が行っているプロセスである

言語処理

• 言語処理のステップ
  • 構文解析（syntax analysis）
    • 文法を元に、文をそれを構成する文法的要素として解析する
  • 意味解析（semantic analysis）
    • 文の各単語の意味的役割を特定する
  • 文脈解析（contextual analysis）
    • 文脈を元に意味を決定する
• 情報検索（information retrieval）
  • トピックに関連するドキュメントを特定する
• 情報抽出（information extraction）
  • 文書から情報を抽出し、利用できるような形式にする
  • 意味ネット（semantic net）
    • データ項目の関連を示す連結データ構造

推論

• プロダクションシステム（production system）
  • 推論における問題を共通となる性質に抽象化したもの
  • 状態の集合
    • 状態（state）
      • アプリケーションの環境で発生する状況
    • 出発状態（start state, initial state）
      • 初期状態
    • 目標状態（goal state）
      • 求める状態
  • プロダクションの集合
    • プロダクション（production）
      • 状態遷移を行うために実行される操作
      • 前提条件が関連付けられていて、それを満たしていなければ実行できない
  • 制御システム（control system）
    • 出発状態から目標状態まで移動して問題を解決するための論理
    • 問題空間（problem space）
      • プロダクションシステム内の全ての状態、プロダクション、前提条件の集合
      • 状態グラフ（state graph）という有向グラフの形式で概念化されることが多い
• 探索木（search tree）
  • 各状態グラフにおける状態と遷移を木構造として表現したもの
  • 節は状態、枝は遷移を表す
  • ヒューリスティック（heuristic）
    • 成功に導きそうな状態から先にアプローチする手法
    • 関連する状態に到達した時、そこから解にたどり着くまでの仕事量が合理的に予測できる必要がある
    • 計算が容易である必要がある

人工知能の研究領域

• メタ推論（meta-reasoning）
  • 推論のための推論
  • 閉世界仮説（closed world assumption）
    • 利用可能な情報から明示的に導き出せない命題は全て偽であると仮定する考え方
• 学習
  • 模倣（imitation）
    • 作業ステップの手本を直接記録させる
    • エージェントには何も任されていない
  • 教師あり学習（supervised training）
    • 一連の例を示して正しい反応を識別できるようにし、エージェントはそれを一般化することで未知の場面に適用できるように学習する
    • 一連の例示を訓練セット（training set）と呼ぶ
  • 強化学習（learning by reinforcement）
    • エージェントは判断のための一般的な規則のみ与えられ、自身による試行錯誤での成功と失敗を繰り返し、その結果から学習する
• 遺伝的アルゴリズム（genetic algorithm）
  • ランダムな振る舞いに再生産理論のシミュレーションと自然淘汰による進化プロセスを組み合わせて解を発見する
  • 各試行は染色体（chromosomo）と呼ぶ
  • 染色体の構成要素は遺伝子（gene）と呼ぶ
  • ステップ
    • ランダムな染色体集合を生成する
    • その集合から2つの染色体（親）を取り出して子を生成する
      • 親は回と導くと思われる可能性が最も高くなるように確率的かつランダムに選択される
      • 子は稀に突然変異を起こす
  • ステップを繰り返す事により最適でなくとも優れた解を発見できる可能性がある

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

• 生物の神経ネットワークを模倣するコンピュータによる処理モデル
• ニューロン（neuron）
  • 神経細胞中のニューロンを模倣した、有効な入力が閾値（threshold value）を超えたかどうかに従って1か0を出力するソフトウェアユニット
  • 有効な入力
    • 実際の入力に対して重み（weight）を乗じた値の和
      • 重みは正負ともに取り得る
        • 正の重みは興奮、負の重みは鎮静に寄与する
• 教師あり学習によってそれぞれの重みを学習する
• 連想記憶（associative memory）
  • 現在の情報に関連する情報を高速に検索できる

ロボット工学（robotics）

• 知的な振る舞いを行う物理的で自律的なエージェントの研究
• 反応型ロボット
  • その時その時で、周りの情報から自身の行動を決定する

第12章 計算の理論

関数とその計算

• 関数（function）
  • 可能な入力値の集合と可能な出力値の集合の間に、各入力に対して1つの出力が割り当てられるように対応付けを行うこと
  • 関数を計算する（computing the function）
    • ある関数に与えられた入力を特定の出力に割り当てるプロセス
  • コンピュータ科学における根本的な作業とは、解決したい問題の根底にある関数を計算する手段を発見すること
  • 入力値に基づいて出力値を決定的かつ段階的に求められない関数が存在する
    • 計算不能な関数
  • 計算可能（computable）
    • 入力値からアルゴリズムによって出力値が決定的に得られる関数

チューリングマシン（Turing machine）

• 読み書きヘッドによってテープ上の記号を読み取ったり書き込んだりできる制御ユニットから構成される仮想的なマシン
• テープは無限長の長さで、セルと呼ばれる単位で区切られている
  • 各セルは記号の有限な集合から1つを含むことができる
• チューリングマシンは有限な数の状態のいずれかにある
  • 出発状態から始まり、停止状態に到達すると終了する
• チューリングマシンのステップ
  • 現在のセルを観察する
  • セルに記号を1つ書き出す
  • 読み書きヘッドを1セル分左か右に動かすこともできる
  • 状態の変更とする
• 実行される動作はマシンの状態と現在のセルの内容に基づいて制御ユニットの動作を決めるプログラムによって厳密に決定されている
• チューリング計算可能（Turing computable）
  • チューリングマシンで計算できる関数

チャーチ=チューリングの提唱（Church=Turing thesis）

• 計算可能な関数、チューリング計算可能な関数、ラムダ計算で計算可能な関数が同じであるという提唱

万能プログラミング言語（universal programming language）

• チューリング計算可能であるプログラミング言語

計算可能性

• 計算不能関数
  • チューリング計算可能ではない関数
  • 計算がコンピュータの能力を超えたところにある関数

停止問題（halting problem）

• あるプログラムが特定の条件で計算中であるか停止しているかを事前に予測するという問題
• 自己停止的（self-terminating）
  • 自分自身を入力として実行を開始し停止するプログラム
• 停止問題が解決不能であることの証明
  • 符号化したプログラムを入力とし、それが自己停止的なプログラムであれば1を、自己停止的でないプログラムであれば0を出力する関数が計算可能であると仮定し、それを停止関数（halting function）とする
  • 停止関数の出力が1であれば停止せず、0であれば停止する処理を加えた関数Fを定義する
  • 関数F自身を符号化したものを入力として関数Fを実行する
  • もし関数F自身を符号化したものが自己停止的である場合、停止関数は1を出力するため、関数Fは停止せず、計算可能ではない
  • もし関数F自身を符号化したものが自己停止的でない場合、停止関数は0を出力するため、関数Fは停止する
  • 両者を同時に満たすことはできないため、この仮定は間違っている
  • よって停止関数は計算可能ではない
• 解決不能問題（unsolvable problem）
  • いかなるアルゴリズムシステムをもってしても解決不可能な問題

問題の複雑さ

問題の複雑さの計測

• コンピュータで解ける問題において、その解はアルゴリズムとして定式化可能である
  • アルゴリズムを解くために必要な計算が多いものほど複雑であるとする
    • ある問題を解く最も単純なアルゴリズムにおける複雑さを、その問題の複雑さとして考える
• 時間計算量（time complexity）
  • 問題を解決するためのアルゴリズムをマシンが実行する際に必要となる時間
    • アルゴリズムを解くの命令のステップ数に比例する
• ある問題における複雑さは、その問題を解く最良の解法の時間計算量となる
• ビッグオー記法（big O notation）
  • f(n)がnについての関数であり、Θ(f(n))のアルゴリズムで解けるなら、その関数の計算量をO(f(n))であるとする

多項式問題と非多項式問題

• 多項式問題（polynominal problem）
  • 関数f(n)が多項式であるか、他の多項式により（上に）有界であるときに、O(f(n))に含まれるような問題
    • （上に）有界であるとは、任意のnにおける値を比較した時、大部分においてより大きい値であること
  • 全ての多項式問題の集合をPとする（クラスP）
• クラスPの外側にある問題は、控えめな大きさの入力においても極端に長い実行時間がかかるという特徴を持つ
• 理論的には解決可能であるが、Pではない問題がとても大きな時間計算量を持つという事実は、実践的な検知から解決不能であると結論付けざるを得ない
  • 扱いにくい（intractable）問題と呼ぶ

NP問題

• 巡回セールスマン問題（travelling salesman problem）
  • ある経路の中で、与えられている総距離を超えない経路を求める問題
• 非決定性アルゴリズム（nondeterministic algorithm）
  • 曖昧な命令を含んでいる、再現性が乏しいアルゴリズム
    • ランダムな値を使用することで、1回で解を得られる可能性がある
  • 巡回セールスマン問題は非決定性アルゴリズムでは多項式時間で解ける
• 非決定的多項式問題（nondeterministic polynominal problem）・NP問題（NP problem）
  • 非決定性アルゴリズムによって多項式時間で解くことのできる問題
    • 答えとなる値を用意できれば、多項式時間で解くことができる
      • 解かどうかは多項式時間で証明可能であるということ
  • 全てのP問題はNP問題である
  • 全てのNP問題がP問題であるかは未解決である
    • P≠NP予想
  • NP完全問題（NP-complete problem）
    • NP問題かつ、その問題が多項式時間で解けるアルゴリズムが発見された場合、それを変形することで他の全てのNP問題が解ける性質を持つ問題

公開鍵暗号

• 暗号化鍵（encrypting key）として知られる値のセットを用いてメッセージを暗号化し、復号鍵（decrypting key）として知られる別の値のセットを用いて復号する
• 暗号化鍵を知っている人はメッセージを暗号化することはできるが、復号することはできない
• 復号可能なのは復号鍵を持っている人だけ
• 安全に暗号化鍵を公開できる
  • この様な声質を持つ暗号システムを公開鍵暗号（public-key encryption）システムと呼ぶ
    • 暗号化鍵は公開鍵（public key）、復号鍵は秘密鍵（private key）と対応する
• RSAアルゴリズム（RSA algorithm）
  • $p$とqが素数であり$m$が$0$と$pq$の間の数であれば、任意の$k$について次の式が成り立つ
    • $1 = m^{k(p-1)(q-1)} \pmod {pq}$
  • 鍵選出のプロセス
    • 異なる素数$p$と$q$を選びその積を$n$とする
    • 別の2つの正の整数$e$と$d$を、ある正の整数$k$について$e \times d = k(p-1)(q-1) + 1$となるように選ぶ
    • この様にして選んだ$p,q,n,e,d$のうち、$e$と$n$が暗号化鍵となり、$d$と$n$は復号鍵である
  • メッセージ暗号化のプロセス
    • 送信するメッセージがビットパターンに符号化されており、パターンの値を2進表現で解釈すると$n$より小さいと仮定する
      • $n$より大きい場合はメッセージを小さな部分に分割しそれぞれ暗号化する
    • メッセージの2進表現を$m$とする
    • 暗号化されたメッセージは$c = m^e \pmod n$の2進表現となる
  • メッセージ復号化のプロセス

    • 暗号化されたメッセージ$c$を複合するには、$c ^ d \pmod n$を計算すれば良い

    • 証明

        $c^d \pmod n = m^{e \times d} \pmod n$
      
        $= m^{k(p - 1)(q - 1) + 1} \pmod n$
      
        $= m \times m^{k(p - 1)(q - 1)} \pmod n$
      
        $= m \times 1 \pmod n$
      
        $= m$