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

アルゴリズムとデータ構造1
2006年6月6日
担当：酒居敬一＠Ａ４６８([email protected])
ＴＡ：小糸啓介＠A310([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2006/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