データ構造とアルゴリズム
平成20年度 前期 2年生必修
水曜日 3-4時限
1
授業の目標
代表的なデータの構造(配列、線形リスト、スタック、キュー、木)
、および、データの操作の基本である、並べ替え、検索等のア
ルゴリズムを学ぶことで、良いプログラムを書くための基礎を養
う
教科書:茨木俊秀,“Cによるアルゴリズムとデータ構造,”
昭晃堂,ISBN:4785631171. 生協にて販売
参考書:近藤嘉雪,“定本Cプログラマのためのアルゴリズムとデータ
構造,”
ソフトバンク,ISBN:4797304952.
2
成績評価



2/3回(10回)以上の出席を満たさない場合は期末試験を受験
できない(学内履修規定)
レポート(30%)および期末試験(70%)を総合評価
レポートと試験の合計得点を100点満点に換算
 優:80点以上
 良:70点以上~80点未満
 可:60点以上~70点未満
3
授業予定
第1週
4/16
導入:データの型、データ構造
第2週
4/23
抽象データ型、計算量、ポインタと配列
第3週
5/07
リスト:配列による実現とポインタによる実現
第4週
5/14
スタックとキュー:スタックの実現、再帰、キューの実現
第5週
5/21
木構造:木と2分木、木のなぞり、木の実現
第6週
5/28
集合と辞書:集合の用語と操作、辞書とハッシュ表
第7週
6/04
順序つき集合の処理:優先度つき待ち行列、ヒープ、探索木:2分探索木
第8週
6/11
整列(1):バブルソート、挿入ソート、選択ソート
第9週
6/25
整列(2):バケットソート、基数ソート、ヒープソート
第10週
7/02
整列(3):クイックソート、シェルソート
第11週
7/09
整列データの処理:整列配列の併合、2分探索
第12週
7/16
演習(ヒープソート)
第13週
7/23
分割統治法、演習(マージソート)
第14週
7/30
学期末試験
4
講義範囲
第1章 アルゴリズムとその計算量
(ほぼ全部)
第2章 基本的なデータ構造
(ほぼ全部)
第3章 順序つき集合の処理
(ほぼ全部)
第4章 整列のアルゴリズム
(4.6節を除く)
第5章 アルゴリズムの設計
(5.1、5.2節)
5
オフィスアワーと連絡先

質問は、水12:00-12:50 に受付ける

居室:情報棟4階 9-409

連絡先:[email protected]

事前にメールで予約すること

メールのマナーを守る

学籍番号、氏名を明記

返信が受信できるようにする
8
データ構造とアルゴリズム
第1回
データの型、データ構造
9
「プログラミング」
1.
2.
3.
4.
5.
問題を分析し,何をするプログラムを書くか決定する.
プログラムの仕様を決める.
どのようなアルゴリズム,データ構造を使用すればよ
いかを決定する.
プログラミング言語を用いてプログラムを書く.
設計したとおりにプログラムが動作するかテストする.
(マニュアルの作成やプログラムの性能評価を行う.)
10
例:身長順の名簿が作りたい

50音順に並んでいるデータを身長順に並べ替える
プログラムを作ろう
 入力:50音順の名簿(5名分)
 出力:身長順の名簿
青木
小田
177
158
青木
佐藤
177
174
金子
佐藤
渡辺
167
174
170
渡辺
金子
小田
170
167
158
11
例:身長順の名簿が作りたい

プログラム内でデータをどう表すか?
⇒データ型,データ構造の決定
名前は文字列で
表現しよう
身長は整数型?
実数型?
青木
小田
177
158
金子
佐藤
渡辺
167
174
170
1名分のデータをま
とめて管理できると
便利だな
5名分のデータの集合
をどう表わそう?
12
例:身長順の名簿が作りたい

どういう手順で処理し,欲しい結果を求めるか?
⇒アルゴリズムの決定
アルゴリズムAは,
メモリをあまり使わないが,処
理が遅い
青木
小田
177
158
金子
佐藤
渡辺
167
174
170
アルゴリズムBは,
メモリを大量に使用するが,
処理が高速
このデータを処理するには
どの方法が適している?
13
アルゴリズム(algorithm)とは?


与えられた問題を解くための、機械的操作(命令)から
なる有限の手続き.
どのような値が入力されたときでも,有限個の命令を
実行後,必ず停止する.
(無限ループに入らない.)
14
アルゴリズムと手続き
[
※
]
操作の系列を並べたもの
有限ステップで停止するとは限らない
コンピュータにかけて実行
できるように手続きを詳細
にしたもの
⇒ プログラム(program)
[
]
必ず有限ステップで停止する
15
問題(problem)


すべてのアルゴリズムは、ある問題を解くという目的で書かれ
る
「ある正整数mが3の倍数であるかどうかを求める」
入力:正整数 m
出力: 3の倍数かどうかの判定メッセージ
1つの問題は無数の問題例(problem instances)から成る。
例えば上記は、mを指定することによって定まる無数の問題
例の集合である。
17
与えられた整数m(ただしm≧0)が3の倍数か否か。
計算手順
Step A1:もしm=0ならば Step A4 へ。
Step A2:mから3を減ずる。
Step A3:Step A1 へ。
Step A4:「mは3の倍数である」と出力する。
Step A5:計算を停止する。

mが3の倍数でないとき,
この手順では処理が停止しない.
18
与えられた整数m(ただしm≧0)が3の倍数か否か。
アルゴリズム (algorithm)
Step B1:もしm=0ならば Step B4 へ。
また,m<0ならば Step B6 へ。
Step B2:mから3を減ずる。
Step B3:Step B1 へ。
Step B4:「mは3の倍数である」と出力する。
Step B5:計算を停止する。
Step B6:「mは3の倍数ではない」と出力する。
Step B7:計算を停止する。

19
スタック(STACK)
後入れ先出しリスト
In, Out
a4
a3
a2
a1
21
待ち行列(QUEUE)
Out
先入れ先出しリスト
a1 a2 a3 a4 a5
In
22
本日の問題
問題1. スタックの身近な例を1つ挙げて説明せよ。
問題2. 待ち行列の身近な例を1つ挙げて説明せよ。
問題3. 構造を持つデータ群(データ構造)の身近な例を
1つ挙げて説明せよ。
23
ダウンロード

PPT for 20080416