mrasu’s blog

読んだ物の内容など

入門 コンピュータ科学 5章 - 9章

「入門 コンピュータ科学」の5章から9章です。
アルゴリズムからDBまで

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

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


5章 アルゴリズム

5.1 アルゴリズムの概念

アルゴリズムとは、停止するプロセスを定義する曖昧さが無く実行可能なステップの順序集合である

つまり、
並列実行のように順序が入れ替わるものもアルゴリズムであり、
停止しないものはアルゴリズムではない。

アルゴリズムと表現は別物である。数式で表現しようと、言葉で表現しようとアルゴリズムは同一である

5.2 アルゴリズムの表現

アルゴリズムの表現に使用する言語は厳密に定義しなくてはならない

疑似コードで簡易に表すことが出来る。

5.3 アルゴリズムの発見

問題解決には

  1. 問題を理解する
  2. 問題を解く計画を考案する
  3. 計画を実行する
  4. 評価する

の段階があるが、順序良く起きるものではないし、閃きもある

問題解決のアプローチ法

  1. 逆から解く
  2. 既存の方法で解ける部分を探す
  3. 分割する

5.4 繰り返し構造

ループと停止条件
停止条件で停止するようにしないと死ぬ

5.5 再帰構造

再帰

5.6 効率性と正当性

ビッグシータ記法

6章 プログラミング言語

6.1 歴史的展望

機械語からアセンブリ言語(数値→ニーモニック)
高レベルでマシン独立な第3世代言語

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

  1. 手続型(命令型)
  2. 宣言型→論理プログラミング
  3. 関数型
  4. オブジェクト指向

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

ループとか分岐とか

6.3 手続きユニット

手続きと関数と引数

6.4 言語の実装

軸解析→[トークン]→構文解析→[構文木]→コード生成→[プログラム(バイトコードとか中間言語)]

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

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

並列はアニメーション、天気予報、航空管制、複雑系シミュレーション、コンピュータネットワーキング、データベース保守など、いろいろ使われる

6.7 宣言型プログラミング

7章 ソフトウェア工学

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

ソフトウェアと他の工学の分野との違い

  1. 汎用部分の少なさ
  2. メトリクスの欠如

これらが、費用超過・リリース遅延・顧客の不満となる。
ソフトウェア工学には機械工学における物理学のような、基盤が無い

研究レベルには

  1. 実践家 (当面応用できる技法の開発)
  2. 理論家 (将来の安定な技法になる基盤)

の2つがあるが、信頼性には問題があり続けている
また、コンピュータ支援ソフトウェア工学(CASE)という学問もある(成果の一つがIDE)

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

伝統的には、

  1. 要求分析
  2. 設計
  3. 実装
  4. テスト

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

  1. ウォーターフォール
  2. インクリメンタルモデル
  3. 反復モデル
  4. ラショナル統一プロセス(RUP)
  5. アジャイル

7.4 モジュール性

結合度、凝縮度、隠ぺい

7.5 ツール

データフロー図
UML

7.6 品質保証

品質管理方法

  1. 記録の保持
  2. レビュー
  3. テスト

7.7 ドキュメンテーション

  1. ユーザドキュメンテーション
  2. システムドキュメンテーション
  3. 技術文書

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

7.9 所有権と責任

8章 データ抽象

8.1 基本データ構造

リスト、スタック(LIFO)、キュー(FIFO)
木、根、部分木、葉、深さ

8.2 関連する概念

静的なデータ構造、動的なデータ構造
ポインタ

8.3 データ構造の実装

配列とメモリの関係について、配列のインデックスはメモリの位置に関係するが、コンパイラによる修正が必要

ex)
Sales[3] = 1;
← [Sales[0]のメモリ位置 + 3]にアクセスする必要がある
Sales[1, 2] = 1;
← [Sales[0]のメモリ位置 + Sales[0].length + 2]にアクセスする必要がある

これは、構造体も同じ

連続リスト(contiguous list)と連結リスト(linked list)

スタックのスタックポインタ
キューのヘッドポインタ・テールポインタと循環キュー(circular queue)

木ではポインタで子供を見るようにするのと、連続したメモリ上に割り当てる方法(配列で木を表現する奴)がある。
探索などの効率は連続で渡す方がいいが、疎なときは無駄が多い

8.4 ケーススタディ

木に対する、二分探索、深さ優先の順次実行、挿入

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

ユーザ定義型、抽象データ型

8.6 クラスとオブジェクト

クラスは抽象データ型の拡張

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

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

9.1 データベースの基礎

スキーマDBMS、データベースモデル

9.2 関係モデル

正規化、関係演算、SQL

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

RDBより良い点は、

  1. 同じパラダイムで開発できる
  2. 型などの拡張性
  3. メソッドも含めることが出来る

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

ロールバック、共有ロック、排他ロック、負傷待機プロトコル(wound-wait protocol)

9.5 伝統的ファイル構造

順編成ファイル(sequence file)(前から順番に記録されるファイル)
索引ファイル(indexed file)
ハッシュファイル

9.6 データマイニング