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

アルゴリズムとデータ構造1
2009年6月8日
担当：酒居敬一＠Ａ４６８([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2009/index.html
テキスト
『アルゴリズムとデータ構造』，
石畑清著(岩波書店)
参考書
『アルゴリズムとデータ構造』，
平田富夫著（森北出版）．
『アルゴリズムとデータ構造入門』，
東野勝治，臼田昭司著（森北出版）．
『ハッカーのたのしみ』，
H.S.ウォーレンＪｒ著，滝沢徹，鈴木貢，
赤池英夫，葛毅，藤波順久，玉井浩訳（星雲社）
『プログラミング言語Ｃ』，
B.W.カーニハン，D.M.リッチー著，
石田晴久訳（共立出版）．
講義計画
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
アルゴリズムとデータ構造入門（６月８日３時限）
アルゴリズムとデータ構造基礎（６月１１日３時限）
メモリとデータ構造（６月１５日３時限）
プログラムとアルゴリズム（６月１８日３時限）
配列（６月１８日５時限）
※
連結リスト（６月２２日３時限）
スタック（６月２５日３時限）
待ち行列（６月２９日３時限）
二分木（７月２日３時限）
•
第１章の演習（７月２日５時限）
※
探索（７月６日３時限）
ハッシュ（７月９日３時限）
ソート（７月１３日３時限）
再帰的アルゴリズム（７月１６日３時限）
•
第２章の演習（７月１６日５時限）
※
くり返し処理と再帰的処理（７月２３日３時限）
•
第３章の演習（７月２７日３時限）
［クォータ末試験］（７月３０日３時限）
成績評価
• クオータ末試験および演習を総合的に
評価する．
• 試験や演習で持ち込めるもの
– 教科書・ノート・配布資料
• 再試験はしない．
本講義の位置づけ
1. プログラムの勉強(技術的な知識)
 計算機言語(第1、第2)、実験１
 背景は、表現方法としてのプログラミング言語
2. アルゴリズムとデータ構造(抽象的な知識)
 計算機システムの基礎
 数学と計算法（計算機はΣや∫を知らない）
3. 計算機のしくみの勉強(低水準の知識)
 情報システム工学実験2、計算機アーキテクチャ
 コーディング対象を知る
4. システム設計の勉強(高水準の知識)
 ソフトウェア工学、オペレーティングシステム
アルゴリズム＋データ構造＝プログラム
(このように書くのは簡単)
アルゴリズムとデータ構造
この間があまりにも遠いのが現実
具体化
間を埋めるもの→想像力
想像力を増やす→経験を積む
経験を積むには→楽しさが必要
楽しさって何？
抽象化
書いたとおり動くのが救い
プログラム(Java, C,…)
プログラムとは？
• アルゴリズムとデータ構造を表現したもの
– 表現方法にはいっぱいある
• プログラミング言語の数だけ
– 構造体やレコードといったデータ構造
– 連接や条件文や繰り返し文といった制御構造
• 計算機に仕事をさせる指示・手続き
– 計算機は指示通りに動くように作られている
• 動かない場合も稀にある…
（教科書２ページ）
アルゴリズムとデータ構造入門
• アルゴリズムとデータ構造の役割
– データとは？
– 処理とは？
– 構造とは？
• なぜ、アルゴリズムとデータ構造について
学習するのか
データとは？
• 現象や性質を何らかの枠組みに従って形
式化したもの
– 身長、体重、座高、視力
– 家族構成、居住地、居住形態
– CDに記録されている音
処理とは？
• 物事をさばいて始末をつけること。
– 対象を分析する
– 準備する
• スケジュールをたてる、データを整理する、など
– 仕事する
• 決められた手順でこなす
– 後片付けする
「段取り八分仕事二分」
構造とは？
• 全体を形づくっている種々の材料による各
部分の組み合わせ。作りや仕組み。
• さまざまな要素が相互に関連し合って作り
上げている総体。また、各要素の相互関係。
• 階層的な構造
わかりやすい文書やプログラム
データ構造
• ひとつまたは複数のデータを編成し保持す
る構造のこと
• データ構造どうしは関連している
• 計算機のメモリには構造らしい構造がない
– 設計が必要だけど、その基礎がデータ構造
• 例：このｐｐｔ原稿(?)
– タイトル(アルゴリズムとデータ構造１)
• 見出し
– 箇条書きの内容
アルゴリズム
• アルゴリズムは必ず問題を解決するもの
– いつかは停止しないといけない
• ひとつまたは複数のデータを操作し目的の
結果を得るための一連の処理手順
• 例: 交差点を渡りたい(＝問題)
– 信号があるか？
– 信号がないならば、どうするか？
なぜ学習するか？
• すばやくコーディングするため
• 美しいコードを書くため
• わかりやすいコードにするため
• どのように表現するか、どのように処理し
目的を達成するか、を理解する
すばやくコーディングする
• よく知られたものを使う
– 探せばどこかに実装が存在する
– 既存のものを使えばデバグの手間が省ける
– 定番と呼ばれる書籍の存在
• 全体をよく考えて、既存のものが使えるよ
うにする
– そのために勉強する！
美しいコード
• 洗練されたコードは美しい
– 適切なアルゴリズム
– 適切なデータ構造
• コーディング規則の外側に美しさがある
– 人間が読み書きするものであることを肝に銘じて
– きちゃないコードは読む気がするか？
わかりやすいコード
• 構造がわかりやすい
– よくしられたデータ構造
– よくしられたアルゴリズム
– これらの再帰的な組み合わせ
• 構造がプログラミング言語の自然なデータ
型や制御文に合っている
• プログラムの共有ができる
– 3日後の自分は他人と同じ
• 記憶力のいい人は1ヶ月くらいは平気？
抽象的 vs. 具体的
• ptrで指される領域からvalueを線形探索
• for(i = n; i; i--, ptr++)
if(*ptr == value) break;
•
mov eax,value
mov edx,ptr
mov ecx,n
0: cmp eax,[edx]
je 1f
lea edx,[edx+4]
loop 0b
1:

Download Report