データ構造とアルゴリズム

データ構造とアルゴリズム
平成20年度前期 2年生必修
水曜日３－４時限
抽象データ型(abstract data type, ADT)

抽象データ型(abstract data type, ADT)
 数学モデルとそれに対する様々な操作を組み合わせたもの
 データが持つべき性質とデータに施せる操作を表わすもの
であり，“データ”および“操作”がどのように実現され
ているかは規定しない
「抽象」と「具体的実現」の例：
ベクトル
抽象
具体的実現
x, y
(1,2) , (3,-1)
ベクトルの大きさ | x |
ベクトルの内積 x ･ y
12  22
1×3+2×(-1)
参考）データ型(data type)


あるプログラミング言語で扱うデータの性格や数値の表現範囲などを
規定するもの
C言語の基本データ型
 整数型
 int型
 long int型
 short int型
etc.
 浮動小数点数型
 float型
 double型
 long double型
 文字型
 char型
etc.
 基本的なデータ型を組み合わせて，
新たなデータ型を定義できる
 組み合わせを作る規則は，プログラ
ミング言語によって異なる
アルゴリズム(algorithm)とは？


与えられた問題を解くための、機械的操作(命令)
からなる有限の手続き．
どのような値が入力されたときでも，有限個の命
令を実行後，必ず停止する．
（無限ループに入らない．）
アルゴリズムの選択基準





開発時間の短かさ
デバッグの容易さ
プログラムコードの小ささ
データのサイズの小ささ
実行時間の短かさ
実行時間を決める要素




入力
コンパイラが出力するオブジェクトコードの質
機械命令（マシン語）の性質と速さ
アルゴリズムの計算量（使用するアルゴリズムによって実行
時間が大幅に変化する)
一般的に、実行時間は入力データ数
実行時間： T(n)
n の関数
アルゴリズムの評価

アルゴリズムの性能はどのように評価する？
 プログラムを作成して，実行時間を計る？
× ハードウェアやコンパイラの性能によって
結果が異なる
× プログラムを書く人の技量に左右される
そこで、これらに左右されない

「計算量(computational complexity)」で評価
計算量

ある仮想的なコンピュータを使用してアルゴリズムを実行
した時，どれくらい時間がかかるかを，入力データの大き
さ（入力データ数） n の関数として大まかに表現したも
の
⇒時間計算量（time complexity）
cf.)


(space/memory complexity)
アルゴリズムの実行に必要な（メモリ等の）領域をn
の関数で表現
プログラムを作るときに，時間と空間のトレードオフ
を考える必要があることが多い．
計算量の指標と表記法


計算量の指標
 最悪の場合の計算量
 平均計算量
計算量の表記法
 O 記法
 Ω記法
 （Θ記法）
大きいオー（big-O notation）


関数の増加率の“上界”を表わす記法
⇒「これより大きくなることはない」
正定数c, n0 が存在し、 n ≧ n0 となる n に対して
T(n)≦c・ f (n)
が成立するなら
T(n)は O ( f (n) )
という。


( f (n) のオーダー )である
nが無限大に発散していくときの漸近的挙動を表現
上式を満たす中で、より小さなO ⇒ より正確な解析
大きいオメガ（Omega notation）


関数の増加率の“下界”を表わす記法
⇒これより小さくなることはない
ある正定数c が存在し、無限個の n に対して
T(n) ≧ c・ g (n)
が成立するなら
T(n)はΩ( g (n) ) (g (n) のオメガ)である
という。

上式を満たす中で、より大きなΩ
⇒
例 T(n)= n3+2n2 は Ω(n3)である
∵c=1とすればT(n) ≧ c・n3が成立する
より正確な解析
増加率の影響
2n
n3/2
5n2
3000
実行時間　T(n)　[秒]
2500
100n
2000
1500
1000
500
0
0
5
10
15
データ数　ｎ
20
25
プログラムの設計手順
1. 要求定義および仕様記述
 プログラムの機能を仕様として記述
2. 概要設計
 仕様を実現するための作業をモジュールに分解し、
モジュールの機能と、相互関係を決定
3. 詳細設計
 モジュールの実現法と接続法を詳細に記述
4. コーディング(coding)
5. テストとデバッギング(debugging)
モジュール



一つの独立した機能を果たすもの
Pascal では procedure や function
Cでは関数
給与計算
データの
読込
基本給の
計算
この例では各々の
がモジュール
加給の
計算
税金の
計算
手取りの
計算
明細書の
出力
分かり易いプログラムを作るには？
分かり易いプログラムを作るためのアプローチ方法
 トップダウン作成法
 全体から始め、いくつかのモジュールに分割する作業を
反復しつつ、徐々に具体化（段階的詳細化）
⇒ 構造化プログラミング

データ分析法（ボトムアップ作成法）
 基本となるデータ構造を定めたのちに、それに適用する
操作の制御構造を明らかにすることを通じてプログラム
を作成
段階的詳細化(stepwise refinement)
与えられた問題について，徐々に細部を詰めな
がら，プログラミング言語に置き換えていく
数学的モデルを考える
文章で書いたアルゴリズム
適切な抽象データ型を考える
疑似言語でプログラムを記述
与えられた整数ｍ（ただしｍ≧０）が
３の倍数か否か。
ｍから３を引く処理を繰り返し，
ｍ＝０になればｍは３の倍数である．
そうでない場合はｍは３の倍数ではない．
使用するプログラミング言語におけるデータ構造を決定
PASCAL，C言語などで記述
段階的詳細化(stepwise refinement)
/*
与えられたデータが，３の倍数かどうかを判定する疑似プログラム
*/
{
m が 0 以上の間次の処理を繰り返す{
if (m が 0 に等しい) {
与えられたデータは3の倍数であると出力する；
終了;
} else {
mから3を引いた値を計算し，新たなmの値とする;
}
}
数学的モデルを考える
文章で書いたアルゴリズム
適切な抽象データ型を考える
疑似言語でプログラムを記述
与えられたデータは3の倍数ではないと出力する；
終了;
}
使用するプログラミング言語におけるデータ構造を決定
PASCAL，C言語などで記述
まとめ


アルゴリズム：問題を解くための、機械的操作(命
令)からなる有限の手続き．必ず停止する．
データ構造：データをコンピュータで効率的に扱う
ため，データを組織化して格納する際の形式

計算量：アルゴリズムの評価尺度

O記法とΩ記法
デバッグ（debug）って何？




de分離、除去 (ex. defroster 霜とり装置)
bug （小さな）虫
プログラムの誤り（バグ, bug）を探して修正
する．
この作業を支援するソフトウェアのことをデ
バッガ(debugger)という．デバッガの使い方は，
演習Iで．
関数（function）とは？

引数と呼ばれるデータを受け取り，処理を実行
し，結果を返すもの
引数（parameter）
y  f ( x)
f ( x)  x  1
2
y
S  f ( L, H )
f ( L, H )  ( L  H ) / 2
S
f(x)
H
x
L
関数が値を返すとは？

ある関数を呼び出して計算した値を、
呼び出し元の変数に代入すること。
関数が値を返すとは？
関数triangle
を呼び出す
メインプログラム
関数
float triangle(int L, int H){
三角形の面積を計算；
return 計算結果；
}
S = triangle(L, H);
計算結果を
関数の呼び出し元に返す
よいプログラミングの習慣
（１）設計計画（仕様の記述、段階的詳細化、etc）
（２）カプセル化
（３）既存のものを再利用
（４）ツールを作る
カプセル化(encapsulation)

「データとそのデータに対する操作手続き」を
一つのまとまり（オブジェクト，object）にし，
用意された操作を利用しなければデータの参照や
変更ができないようにすること

独立性向上

再利用が容易
→
保守が容易
→
開発期間短縮
カプセル化の例
(成績データベース)
操作：データ追加
データ：B君，算数90，英語95
データの
追加
データ
データの
削除
(Name，Math，English)
データの
検索
抽象データ型
カプセル化の例
操作：データ検索
データ：A君
データの
追加
データの
削除
(成績データベース)
算数 85
英語 100
データの
検索
成績表
印刷
抽象データ型
データ
(Name，Math，English)
(
A， 85，
100)
(
B， 90，
95)
• データの検索速度を上げるには，この内部のデータ構造や
操作のアルゴリズムを見直せばよい
（印刷モジュールには影響しない）
各言語のもつデータ型
PASCAL
 単純型

データ型




整数型
実数型
論理型
文字型
順序型


データ構造
ポインタ型

構造型


抽象データ型

基本データ型



整数型
浮動小数点数型
文字型

列挙型

ポインタ
列挙型
部分範囲型


C
配列型
レコード型
集合型 etc.


配列
構造体
C++
クラス
etc.
図式プログラミング言語(p.20)

アルゴリズムやプログラムを視覚的に分かりや
すくするための手段として図が用いられる

流れ図、フローチャート(flow chart)

PAD (problem analysis diagram)
開始
フローチャート

計算の各ステップを一
つのブロックで表現
n←1
sum ← 0
n<=10？
Yes


各ブロック間の制御の
流れを矢印つきの枝で
結んだもの
右図は1から10までの
整数の和を求める処理
の例
sum ← sum + n
n ←n+1
和を表示
終了
No
フローチャートで使用される記号※
開始、終了の端子
処理
条件分岐
if文やfor文、while文を表現するとき使用
i : 1, 10, 1
for文
箱の中の文字は、ループカウンタ変数名と
初期値、終了条件、増分
左の例は for( i = 1; i <= 10; i++)
本日の問題
問題１．次のうち、計算量が一番大きいものはどれか
O(1), O(n), O(n2), O(n log n)
問題２．計算量が一番小さいものはどれか
O(log n), O(n3), O(n log n), O(n)
問題３．計算量の大きいものから順に並べなさい
O(n log n), O(n), O(1) , O(n3), O(log n)

Download Report