業務のモデル化
業務のモデル化
システム開発を始めるにあたり、システム化しようとしている業務の流れ(ビジネスプロセス)や、取り扱う情報(データクラス)の関係を図解する作業のこと。
●DFD (Data Flow Diagram:データフロー図)
データの流れに着目して、対象業務を分析する時に使う図解手法。
データの流れ(データフロー)とデータを処理するプロセスを図にすることで、業務内容を確認しやすいというメリットがある。
ただし、処理のタイミングなど時間的な表現はできない。
●E・R図 (Entity Relationship Diagram)
データの構造を実体(エンティティ)と実体同士の関係(リレーションシップ)の2つの概念で表現したもので、データ間の関連分析に用いられる。
●状態遷移図
時間の経過や制御信号などの状態を変化させるきっかけと、変化に伴って実行する動作を記述する時に使う。
リアルタイム性のあるシステムの分析や設計に便利。業務の変化や画面遷移などを表すのに用いられる。
システム開発の概要
<システム開発の流れ>
●要件定義
非機能要件
要件定義では、システムに必要な機能を定義する機能要件の他に、非機能要件も定義する。業務要件の実現に必要な品質要件、技術要件、運用・操作要件などを明確にする。例えば、システム開発で用いるプログラミング言語に合わせた開発基準の作成など。
●システム設計
1、ソフトウェア要件定義(外部設計)
入力画面など、システムの見た目の部分を設計したり、システムに必要なデータ項目を洗い出してデータ構造を決定するなど、論理データの設計を行う。
2、ソフトウェア方式設計(内部設計)
前段階で決まった要件を元に、盛り込む機能や処理の流れを決めるといった、内部の仕組みを設計する。
3、ソフトウェア詳細設計(詳細設計)
プログラムの構造を設計する。
アルゴリズムの実行時間
<実行時間を表すO記法>
オーダ
どれくらい計算に時間がかかるかを表す
O記法
オーダによってアルゴリズムを表す記述方法。
O記法では、データの個数をnとし、それに対する計算量をO(n)で表す。
O(n)は、データの個数が2倍、3倍になると、計算量も2倍、3倍になると言うこと。O(n^2)は、データの個数が2倍、3倍になると、計算量は4倍、9倍になると言うことを表す。
O記法では、大量のデータを扱う場合を考えるため定数や係数は無視する。
<探索アルゴリズムの実行時間>
ハッシュ探索法では、衝突が起きない限り、原則1回の比較でデータを見つけることができるため、データ個数にかかわらず0(1)となる。
線形探索法は、最大でデータ個数の分だけ比較することになるため、データが多い場合には最も遅いアルゴリズムとなる。
・ハッシュ探索法のオーダ:O(1)
・2分探索法のオーダ:O(log2n)
・線形探索法のオーダ:O(n)
<整列アルゴリズムの実行時間>
交換法(バブルソート)、挿入法、選択法の実行時間(オーダ)は全てO(n^2)となる。
整列アルゴリズム
●交換法(バブルソート)
隣同士のデータの大小を比較して、大小の順番が逆であれば交換していくアルゴリズム。
データ比較回数は、n(n-1)/2回
●選択法
未整列のデータから最小値(最大値)を探して順に並べていくアルゴリズム。まず、先頭から順にデータの値を比べていき、最小値を探す。最小値が見つかったら、1番目のデータと入れ替える。次に、残りのデータから最小値を探し、2番目のデータと入れ替える。これを繰り返す。
データ比較回数はn(n-1)/2回
●挿入法
未整列データから1つずつデータを取り出して、すでに整列済みのデータ列の適切な場所に挿入していくアルゴリズム。
シェルソートは挿入法を改良したもので、ある一定期間おきに取り出したデータから成る部分列をそれぞれ整列し、さらに間隔を詰めて同じ操作を行うアルゴリズム。最後に間隔が1になるまで繰り返してデータを並び替える。部分的に整列しておくことで、挿入の後に整列済みの要素をずらす作業を減らすことができ、処理が速くなる。
まず基準となる値を決め、それよりも小さい値のグループと大きい値のグループに分ける。次に、それぞれのグループの中で同じ処理を繰り返して、分割できなくなるまで繰り返すことで、データを並び替えていくアルゴリズム。
未整列のデータをヒープに構成した後、ヒープの根から最小値または最大値を取り出して整列済みの部分列に移すことを繰り返してデータを整列するアルゴリズム。
探索アルゴリズム
●線形探索法
先頭から順番に目的のデータと比較し、一致するデータを探すアルゴリズム。
整列されていない状態で目的のデータを探索するには向いているが、大量のデータを探索するには不向き。
線形探索法では、 n個のデータの中から目的のデータを見つけるまでに、最小で1回、最大でn回、データの比較を行う必要がある。したがって、平均比較回数は(n+1)/2回となる。
番兵
線形探索法で配列構造のデータを探索する場合、探索する前にあらかじめ最後のデータの後ろに目的のデータを入れておくこと
●2分探索法
あらかじめデータが大きい順もしくは小さい順に整列されている場合に使う。まずデータを2等分し、探索範囲の中央の値と探索データを比較する。探索データの方が小さければ、目的データの場所を前半に絞り込む。これを繰り返す。
平均比較回数はlog2n
●ハッシュ探索法
データ格納場所のアドレス値を、あらかじめ関数を使った計算で決めておくアルゴリズム。
格納先を決めるために用いられる関数をハッシュ関数、ハッシュ関数によって求められるアドレス値をハッシュ値と言う。データを探索する際には、ハッシュ関数を計算してハッシュ値を求めることで、格納場所を割り出す。衝突が発生しない限り、必ず1回でデータを見つけることができる。
衝突が起こった場合には、配列の各要素をリスト構造にして、新しい場所にデータを格納する。
一様分布
ハッシュ探索法において、衝突の確率が最も低くなるのは、ハッシュ値が一様分布にある時である。一様分布とは、サイコロの目の出る確率など、全ての事象が起こる確率が等しい現象である。