第１章
　

　ソフトウェアの設計
　
　
　本章では、ソフトウェアを作成する際に考慮すべきソフトウェアの設計・評価に必要な事項について説明する。
　
１．１　ソフトウェア・ライフサイクル
　
　ソフトウェアは以下のような手順で作成され維持管理される。このような手順のことをソフトウェアの一生という意味でソフトウェア・ライフサイクルと呼ぶ。
　　①問題の提示／発生
　　　　一般に問題は厳密に定義されるのではなく、自由度を持っている
　　②問題の定式化、仕様記述
　　　　問題を明確に仕様として記述する（外部仕様）
　　　　（入力データ、処理内容、出力データ）
　　③問題のモデル化
　　　　数学的モデル　　　　数値処理：連立一次方程式、微分方程式
　　　　　　　　　　　　　　記号処理：形式文法、lambda 算法
　　　　既存の解法－ライブラリの利用
　　④プログラムの概要設計
　　　　モジュール分割、モジュールの機能と相互関係
　　⑤プログラムの詳細設計　　　　データ構造＋アルゴリズム
　　　　モジュールの実現法と接続法（内部仕様）
　　　　　　　　図式プログラミング言語－流れ図(Flow Chart)
　　　　　　　　　　　　　　　　　　　　PAD(Problem Analysis Diagram)
　　⑥コーディング
　　　　プログラム言語の選択、プログラミング
　　⑦テストとデバッグ
　　　　テストデータによるプログラムのテスト、バグの検出、バグの除去
　　⑧プログラムの評価
　　　　パフォーマンス（処理速度、必要メモリ、応答時間）の測定
　　⑨プログラムの保守
　　　　文書化：外部仕様、内部仕様、テストデータ、修正のヒント
　
問 1.1.1　プログラミング言語にはどのようなものがあるか。それぞれどのような特徴を持ち、どのような分野で利用されているか。
問 1.1.2　図式プログラミング言語にはどのようなものがあるか。それぞれどのような特徴があるか。
問 1.1.3　プログラムの性能を評価するためのツールにはどのようなものがあるか調べよ。
　
１．２　アルゴリズムとデータ構造
　
　プログラムの基本はアルゴリズムとデータ構造である。
○アルゴリズム
　与えられた問題を解くための機械的操作からなる有限の手続き
　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　どんな入力に対しても無限ループに入らない
　　　　　　　　　　　加減乗除、条件分岐命令など
　・手続き：演算子の一般化－プログラマが独自の操作を定義
○データ構造
　与えられた問題で使用されるデータの表現
　・データ型：変数の取りうる値の集合
　・セル：データ型を形成する基本ブロック－変数の集まり
○カプセル化
　封じ込めによる実装の変更が容易
　●アルゴリズムのカプセル化＝手続き
　　入力・出力の関係を満足すればよい
　　異なるアルゴリズムの採用
　　　　　　　　　　　　　　　変更が容易、自由度が大きい
　　チェックルーチンの追加
　●データ型のカプセル化＝抽象データ型（Abstract Data Type, ADT）
　　型の定義とデータに対する操作をプログラムの一角に封じ込める
　　　　　　　　　　　　　　　　　　　∥
　　　　　　　　　　　　　　　　　アクセス関数
　　異なるデータ型の実装
　　　　　　　　　　　　　　　 変更が容易、自由度が大きい
　　異なるアルゴリズムの採用
　
例題1.2.1　集合の操作を行う集合データ型について、どのような実現方法が考えられるか。
　・データ型の実装方法としては、リスト、配列、ビットベクトルなどが可能
　・アクセス関数としては、和集合、積集合、補集合が考えられる
　　s１とs２の和集合　　　　　　　　　　　s=UNION(s１, s２)
　　s１とs２の積集合　　　　　　　　　　　s=INTERSECTION(s１, s２)
　　s１ の全体集合 U に対する補集合　　　s=COMPLEMENT(s１, U)
　
問 1.2.1　データ型にはどのような種類があるか。計算機自体の持つデータ型とプログラミング言語の持つデータ型にはどのような違いがあるか。
問 1.2.2　演算子にはどのような種類があるか。プログラミング言語の持つ演算子と計算機自体の持つ演算子（命令）にはどのような違いがあるか。
問 1.2.3　論理演算に関して、データ型の実装方法およびアクセス関数を考えよ。
　
１．３　実行時間および評価
　
○プログラムの実行時間
　実行時間は、使用する計算機に依存するが、採用するアルゴリズムにも大きく依存する。
　・計算機に依存する要素
　　(a) 機械命令の性質と速さ
　　(b) コンパイラが出力する目的プログラム（オブジェクト）の質
　・アルゴリズムに依存する要素
　　(a) 入力データの量
　　(b) アルゴリズムの計算量
○アルゴリズムの評価
　・計算量
　　(a) 時間量：アルゴリズムのステップ数
　　(b) 領域量：計算の途中経過を保持するのに必要な記憶領域の広さ
　・計算量の種類
　　(a) 最悪計算量：問題の例の中で計算量が最大となるものの計算量
　　(b) 平均計算量：問題例の生起確率に基づいて重み付けした計算量の平均値
○時間量の上界値と下界値
　Ｔ(n)：入力データの大きさ n に対する時間量
　・時間量の上界値（オーダー）
　　Ｔ(n)＝Ｏ(f(n))　　 ∃c>0,∃N０>0, T(N)≦cf(N) (N≧N０)
　・時間量の下界値（オメガ）
　　Ｔ(n)＝Ω(f(n))　　 ∃c, T(N)≧cf(N) (無限個の N に対して)







　

Ｔ(n)
10３秒で解ける大きさ
10４秒で解ける大きさ
改善率

100n　5n２ n３/2　2ｎ
　
　　　　 10　　　　 14　　　　 12　　　　 10
　
　　　　100　　　　 45　　　　 27　　　　 13
　
　10.0　 3.2　 2.3　 1.3
　
　　　　　　　多項式時間：　Ｏ(nｋ)（kは定数）など
　・オーダー
　　　　　　　非多項式時間：Ｏ(kｎ)、Ｏ(nｌｏｇｎ) など
○領域量の上界値と下界値
　Ｍ(n)：入力データの大きさ n に対する領域量
　上界値：Ｍ(n)＝Ｏ(f(n))、下界値：Ｍ(n)＝Ω(f(n))
　
問 1.3.1　使用している計算機について、機械命令の種類と演算性能を調べよ。
問 1.3.2　使用しているコンパイラについて、最適化の種類、指定方法を調べよ。
問 1.3.3　時間量の上界値がＯ(n２)、Ｏ(n１．５)、Ｏ(nlogn) のアルゴリズムについて、その改善率を比較せよ。