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

Presentation on theme: "データ構造とアルゴリズム 平成20年度　前期　2年生必修　 水曜日　３－４時限."— Presentation transcript:

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

2 授業の目標 代表的なデータの構造（配列、線形リスト、スタック、キュー、木）、および、データの操作の基本である、並べ替え、検索等のアルゴリズムを学ぶことで、良いプログラムを書くための基礎を養う 教科書：茨木俊秀，“Cによるアルゴリズムとデータ構造，” 　　 　　 昭晃堂，ISBN: ．　生協にて販売 参考書：近藤嘉雪，“定本Cプログラマのためのアルゴリズムとデータ構造，” 　　 ソフトバンク，ISBN: ．

3 成績評価 2/3回（10回）以上の出席を満たさない場合は期末試験を受験できない（学内履修規定）
レポート(30%)および期末試験(70%)を総合評価 レポートと試験の合計得点を100点満点に換算 優：80点以上 良：70点以上～80点未満 可：60点以上～70点未満

4 授業予定 第1週 4/16 導入：データの型、データ構造 第2週 4/23 抽象データ型、計算量、ポインタと配列 第3週 5/07
リスト：配列による実現とポインタによる実現 第4週 5/14 スタックとキュー：スタックの実現、再帰、キューの実現 第5週 5/21 木構造：木と２分木、木のなぞり、木の実現 第6週 5/28 集合と辞書：集合の用語と操作、辞書とハッシュ表 第7週 6/04 順序つき集合の処理：優先度つき待ち行列、ヒープ、探索木：２分探索木 第8週 6/11 整列（１）：バブルソート、挿入ソート、選択ソート 第9週 6/25 整列（２）：バケットソート、基数ソート、ヒープソート 第10週 7/02 整列（３）：クイックソート、シェルソート 第11週 7/09 整列データの処理：整列配列の併合、２分探索 第12週 7/16 演習（ヒープソート） 第13週 7/23 分割統治法、演習（マージソート） 第14週 7/30 学期末試験

5 講義範囲 第１章 アルゴリズムとその計算量 （ほぼ全部) 第２章 基本的なデータ構造 （ほぼ全部） 第３章 順序つき集合の処理 （ほぼ全部）
第１章　アルゴリズムとその計算量　　（ほぼ全部) 第２章　基本的なデータ構造　　　　　　（ほぼ全部） 第３章　順序つき集合の処理　　　　　　（ほぼ全部） 第４章　整列のアルゴリズム　　　　　（4.6節を除く） 第５章　アルゴリズムの設計　　　　　（5.1、5.2節）

6 参考）IT関連の資格 出典： 情報処理技術者試験センター 試験の概要
出典：　情報処理技術者試験センター 　試験の概要

7 参考）基本情報技術者試験 出題分野 コンピュータ科学基礎 コンピュータシステム システムの開発と運用 ネットワーク技術 データベース技術
１ 情報の基礎理論 １－１ 数値表現・データ表現に関すること（基数変換，数値表現，文字表現，数値計算（演算方式と精度，近似解法と方程式ほか），確率と統計，最適化問題 など） １－２ 情報と理論に関すること（論理演算，符号理論，述語論理，状態遷移，計算量，情報量，BNF，ポーランド表記法，集合 など） ２ データ構造とアルゴリズム ２－１ データ構造に関すること（2 分木，リスト，スタック，キュー など） ２－２ アルゴリズムに関すること（整列，探索，再帰，グラフ，文字列処理，流れ図 など） コンピュータシステム システムの開発と運用 ネットワーク技術 データベース技術 セキュリティと標準化 情報化と経営

8 オフィスアワーと連絡先 質問は、水12:00－12:50 に受付ける 居室：情報棟4階 9-409
質問は、水12:00－12:50　に受付ける 居室：情報棟4階　9-409　 事前にメールで予約すること メールのマナーを守る 学籍番号、氏名を明記 返信が受信できるようにする

9 データ構造とアルゴリズム 第1回　 データの型、データ構造

10 「プログラミング」 問題を分析し，何をするプログラムを書くか決定する．プログラムの仕様を決める．
どのようなアルゴリズム，データ構造を使用すればよいかを決定する． プログラミング言語を用いてプログラムを書く． 設計したとおりにプログラムが動作するかテストする． （マニュアルの作成やプログラムの性能評価を行う．)

11 例：身長順の名簿が作りたい 50音順に並んでいるデータを身長順に並べ替えるプログラムを作ろう 入力：50音順の名簿（5名分）
出力：身長順の名簿 青木 177 小田 158 金子 167 佐藤 174 渡辺 170 青木 177 佐藤 174 渡辺 170 金子 167 小田 158

12 １名分のデータをまとめて管理できると便利だな
例：身長順の名簿が作りたい プログラム内でデータをどう表すか？ 　　　⇒データ型，データ構造の決定 名前は文字列で表現しよう 身長は整数型？実数型？ １名分のデータをまとめて管理できると便利だな 青木 177 小田 158 金子 167 佐藤 174 渡辺 170 5名分のデータの集合をどう表わそう？

13 例：身長順の名簿が作りたい どういう手順で処理し，欲しい結果を求めるか？ ⇒アルゴリズムの決定 青木 177 小田 158 金子 167
　　　⇒アルゴリズムの決定 アルゴリズムAは， メモリをあまり使わないが，処理が遅い 青木 177 小田 158 金子 167 佐藤 174 渡辺 170 アルゴリズムBは， メモリを大量に使用するが， 処理が高速 このデータを処理するには どの方法が適している？

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

15 アルゴリズムと手続き ※ ［ ］ ［ ］ コンピュータにかけて実行できるように手続きを詳細にしたもの ⇒ プログラム(program)
アルゴリズムと手続き　　※ ［　　　　　　　］ 操作の系列を並べたもの 有限ステップで停止するとは限らない コンピュータにかけて実行できるように手続きを詳細にしたもの ⇒　プログラム(program) ［　　　　　　　］ 必ず有限ステップで停止する

16 アルゴリズムと手続き ※ 手続き（procedure） コンピュータにかけて実行できるように手続きを詳細にしたもの
アルゴリズムと手続き　　※ 手続き（procedure） 操作の系列を並べたもの 有限ステップで停止するとは限らない コンピュータにかけて実行できるように手続きを詳細にしたもの ⇒　プログラム(program) アルゴリズム 必ず有限ステップで停止する

17 問題（problem） すべてのアルゴリズムは、ある問題を解くという目的で書かれる 「ある正整数mが３の倍数であるかどうかを求める」
出力： ３の倍数かどうかの判定メッセージ １つの問題は無数の問題例(problem instances)から成る。 　　例えば上記は、mを指定することによって定まる無数の問題例の集合である。

18 与えられた整数m（ただしｍ≧０）が３の倍数か否か。
計算手順 Step A1：もしｍ＝０ならば Step A4 へ。 Step A2：ｍから３を減ずる。 Step A3：Step A1 へ。 Step A4：「ｍは３の倍数である」と出力する。 Step A5：計算を停止する。 ｍが3の倍数でないとき， この手順では処理が停止しない．

19 与えられた整数ｍ（ただしｍ≧０）が３の倍数か否か。
アルゴリズム (algorithm) Step B1：もしｍ＝０ならば Step B4 へ。 　　　　　　また，ｍ＜０ならば Step B6 へ。 Step B2：ｍから３を減ずる。 Step B3：Step B1 へ。 Step B4：「ｍは３の倍数である」と出力する。 Step B5：計算を停止する。 Step B6：「ｍは３の倍数ではない」と出力する。 Step B7：計算を停止する。

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

21 スタック（STACK） 後入れ先出しリスト In, Out a 4 a 3 a 2 a 1

22 待ち行列（QUEUE） 先入れ先出しリスト Out a 1 a 2 a 3 a 4 a 5 In

23 本日の問題 問題１． スタックの身近な例を１つ挙げて説明せよ。 問題２． 待ち行列の身近な例を１つ挙げて説明せよ。
問題１．　スタックの身近な例を１つ挙げて説明せよ。 問題２．　待ち行列の身近な例を１つ挙げて説明せよ。 問題３．　構造を持つデータ群（データ構造）の身近な例を 　　　　　　１つ挙げて説明せよ。