担当：酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造1 2009年6月8日 担当：酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2009/index.html

テキスト 　　　『アルゴリズムとデータ構造』， 石畑清 著(岩波書店) 参考書 　　　『アルゴリズムとデータ構造』， 平田富夫 著（森北出版）． 『アルゴリズムとデータ構造入門』， 東野勝治，臼田昭司 著（森北出版）． 『ハッカーのたのしみ』， H.S.ウォーレン Ｊｒ 著，滝沢徹，鈴木貢， 赤池英夫，葛毅，藤波順久，玉井浩訳（星雲社） 『プログラミング言語Ｃ』， B.W.カーニハン，D.M.リッチー 著， 石田晴久 訳（共立出版）．

講義計画 アルゴリズムとデータ構造入門（６月８日３時限） アルゴリズムとデータ構造基礎（６月１１日３時限） メモリとデータ構造（６月１５日３時限） プログラムとアルゴリズム（６月１８日３時限） 配列（６月１８日５時限） ※ 連結リスト（６月２２日３時限） スタック（６月２５日３時限） 待ち行列（６月２９日３時限） 二分木（７月２日３時限） 第１章の演習（７月２日５時限）　 ※ 探索（７月６日３時限） ハッシュ（７月９日３時限） ソート（７月１３日３時限） 再帰的アルゴリズム（７月１６日３時限） 第２章の演習（７月１６日５時限） ※ くり返し処理と再帰的処理（７月２３日３時限） 第３章の演習（７月２７日３時限） ［クォータ末試験］（７月３０日３時限）

成績評価 クオータ末試験および演習を総合的に 評価する． 試験や演習で持ち込めるもの 教科書・ノート・配布資料 再試験はしない．

本講義の位置づけ プログラムの勉強(技術的な知識) アルゴリズムとデータ構造(抽象的な知識) 計算機のしくみの勉強(低水準の知識) 計算機言語(第1、第2)、実験１ 背景は、表現方法としてのプログラミング言語 アルゴリズムとデータ構造(抽象的な知識) 計算機システムの基礎 数学と計算法（計算機はΣや∫を知らない） 計算機のしくみの勉強(低水準の知識) 情報システム工学実験2、計算機アーキテクチャ コーディング対象を知る システム設計の勉強(高水準の知識) ソフトウェア工学、オペレーティングシステム

アルゴリズム＋データ構造＝プログラム (このように書くのは簡単) アルゴリズムとデータ構造 具体化 抽象化 この間があまりにも遠いのが現実 　　　　間を埋めるもの→想像力 　　　　　　想像力を増やす→経験を積む 　　　　　　　　経験を積むには→楽しさが必要 　　　　　　　　　　楽しさって何？ 　　　　　　　　　　　　　　書いたとおり動くのが救い プログラム(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: