データ構造とアルゴリズム 平成20年度　前期　2年生必修　 水曜日　３－４時限

データ構造とは？ データ構造(data structure) データをコンピュータで効率的に扱うため，データを組織化して格納する際の形式 データ構造とは？　　 データ構造(data structure) データをコンピュータで効率的に扱うため，データを組織化して格納する際の形式 各種の型を持った変数を，様々な方法で結びつけたもの 基本的なデータ構造 リスト(list) スタック(stack) キュー（queue） 木(tree) etc. リスト 青木　177 小田　158 金子　167 佐藤　174 渡辺　170

抽象データ型(abstract data type, ADT) 数学モデルとそれに対する様々な操作を組み合わせたもの データが持つべき性質とデータに施せる操作を表わすものであり，“データ”および“操作”がどのように実現されているかは規定しない

抽象 具体的実現 ベクトル x, y (1,2) , (3,-1) ベクトルの大きさ | x | ベクトルの内積 x ･ y 「抽象」と「具体的実現」の例： 抽象 具体的実現 ベクトル x, y (1,2) , (3,-1) ベクトルの大きさ | x | ベクトルの内積 x ･ y 1×3+2×(-1)

参考）データ型(data type) あるプログラミング言語で扱うデータの性格や数値の表現範囲などを規定するもの C言語の基本データ型 整数型 int型 long int型 short int型　etc. 浮動小数点数型 float型 double型 long double型 文字型 char型 etc. 基本的なデータ型を組み合わせて，新たなデータ型を定義できる 組み合わせを作る規則は，プログラミング言語によって異なる

アルゴリズム(algorithm)とは？ 与えられた問題を解くための、機械的操作(命令)からなる有限の手続き． どのような値が入力されたときでも，有限個の命令を実行後，必ず停止する． 　（無限ループに入らない．）

アルゴリズムの選択基準 開発時間の短かさ デバッグの容易さ プログラムコードの小ささ データのサイズの小ささ 実行時間の短かさ

実行時間を決める要素 入力 コンパイラが出力するオブジェクトコードの質 機械命令（マシン語）の性質と速さ アルゴリズムの計算量（使用するアルゴリズムによって実行時間が大幅に変化する) 一般的に、実行時間は入力データ数　n　の関数 　　　　実行時間：　T(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　⇒　より正確な解析

例 n2, 2.5n2 , 100+5n+2n2 ⇒ O(n2) n3 , 5n2+4n3 ⇒ O(n3) 一般に T1(n)+T2(n) = O(max (f(n), g(n)) ) T1(n)T2(n) = O( f(n) g(n) ) 定数オーダー(constant order) O(1) 計算量がデータ数nによらず一定

大きいオメガ（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が成立する

計算量の評価に使用される関数 n の整数乗 （1, n, n2, n3, …) log n 2n 増加率 小 大 1 　log n n n log n n2 n3 … nk 2n

増加率の影響 2n n3/2 5n2 100n

プログラムの設計手順 要求定義および仕様記述 概要設計 詳細設計 コーディング(coding) テストとデバッギング(debugging) プログラムの機能を仕様として記述 概要設計 仕様を実現するための作業をモジュールに分解し、 　 モジュールの機能と、相互関係を決定 詳細設計 モジュールの実現法と接続法を詳細に記述 コーディング(coding) テストとデバッギング(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 （小さな）虫 この作業を支援するソフトウェアのことをデバッガ(debugger)という．デバッガの使い方は，演習Iで．

関数（function）とは？ 引数と呼ばれるデータを受け取り，処理を実行し，結果を返すもの 引数（parameter） y S f(x) H x L

関数が値を返すとは？　　 ある関数を呼び出して計算した値を、呼び出し元の変数に代入すること。

関数が値を返すとは？ 関数 関数triangle float triangle(int L, int H){ を呼び出す 関数が値を返すとは？　　 関数 float triangle(int L, int H){ 三角形の面積を計算； 　　return 計算結果； } 関数triangle を呼び出す メインプログラム 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++　　クラス C 基本データ型 整数型 浮動小数点数型 文字型 列挙型 ポインタ 配列 構造体 etc. データ型 データ構造 抽象データ型

ひとやすみ

図式プログラミング言語(p.20) 流れ図、フローチャート(flow chart) アルゴリズムやプログラムを視覚的に分かりやすくするための手段として 図が用いられる 流れ図、フローチャート(flow chart) PAD (problem analysis diagram)

フローチャート 計算の各ステップを一つのブロックで表現 各ブロック間の制御の流れを矢印つきの枝で結んだもの 開始 n ← 1 sum ← 0 計算の各ステップを一つのブロックで表現 各ブロック間の制御の流れを矢印つきの枝で結んだもの 右図は1から10までの整数の和を求める処理の例 n<=10？ No Yes sum　←　sum + n n　← n + 1 和を表示 終了

フローチャートで使用される記号※ 開始、終了の端子 処理 条件分岐 if文やfor文、while文を表現するとき使用 for文 箱の中の文字は、ループカウンタ変数名と 初期値、終了条件、増分 左の例は　for( i = 1; i <= 10; i++) i : 1, 10, 1

問題１．次のうち、計算量が一番大きいものはどれか O(1), O(n), O(n2), O(n log n) 本日の問題 問題１．次のうち、計算量が一番大きいものはどれか 　　　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)