アルゴリズムとデータ構造1 2005年6月10日酒居敬一([email protected]) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG2005/index.html 連絡先 酒居 居室: A468 メイル: [email protected] TA(福家君) メイル: [email protected] テキスト『アルゴリズムとデータ構造』，石畑清著(岩波書店) 参考書『Javaで学ぶアルゴリズムとデータ構造』， Robert Lafore著，岩谷宏訳（ソフトバンク）『Javaによるプログラミング入門』，権藤克彦著（サイエンス社，2000）『Javaによるオブジェクト指向プログラミング入門』，越田一郎（培風館）『プログラミング作法』， Brian Kernighan, Rob Pike著（アスキー）講義計画 1. アルゴリズムとデータ構造入門 2. アルゴリズムとデータ構造基礎［演習１］アルゴリズムとデータ構造の概念，オブジェクト指向の概念 3. アルゴリズムとデータ構造概要１ 4. アルゴリズムとデータ構造概要２ 5. 配列［演習２］配列のような基本的なデータ構造 6. スタック 7. 待ち行列 8. 連結リスト［中間試験］データ構造やアルゴリズムや計算量の概念，線形なデータ構造とアルゴリズム 9. 二分木 10. ハッシュ 11. ソート［演習３］二分木，ハッシュ 12. 探索 13. 再帰的アルゴリズム 14. くり返し処理と再帰的処理［演習４］全体の復習，検索や再帰 15. ［クォータ末試験］(7月30日の予定）専門科目演習日程 • 場所はA101 • 火曜か金曜の5時限目 • 演習日(予定) 6月14日、6月24日、7月5日、7月15日、7月26日 • 教科書（岩波のやつ）を必ず持ってくること。成績評価 • 計100点．60点以上を合格とする． – 演習課題40点（各10点×４回） – （演習の1回を充てる）中間試験30点 – クォータ末試験30点 • 試験や演習で持ち込めるもの – 教科書・ノート・配布資料 • 再試験はしない．本講義の位置づけ 計算機言語(第1と第2)、情報システム工学実験１ 表面的には書き方(コーディング)の演習 背景には表現方法としてのプログラミング言語を習得 情報システム工学実験2 コーディングだけではやっていけない なぜか？本授業で説明プログラムとは？ • アルゴリズムとデータ構造を表現したもの – 表現方法にはいっぱいある • プログラミング言語の数だけ – 構造体やレコードといったデータ構造 – 条件文や繰り返し文といった制御構造アルゴリズムとデータ構造入門 • アルゴリズムとデータ構造の役割 – データとは？ – 処理とは？ – 構造とは？ • なぜ、アルゴリズムとデータ構造について学習するのかデータとは？ • 現象や性質を何らかの枠組みに従って形式化したもの – 身長、体重、座高、視力 – 家族構成、居住地、居住形態 – CDに記録されている音処理とは？ • 物事をさばいて始末をつけること。 – 対象を分析する – 準備する • スケジュールをたてる、データを整理する、など – 仕事する • 決められた手順でこなす – 後片付けする「段取り八分仕事二分」構造とは？ • 全体を形づくっている種々の材料による各部分の組み合わせ。作りや仕組み。 • さまざまな要素が相互に関連し合って作り上げている総体。また、各要素の相互関係。 • 階層的な構造わかりやすい文書やプログラムデータ構造 • ひとつまたは複数のデータを編成し保持する構造のこと • データ構造どうしは関連している • 例：このｐｐｔ原稿(?) – タイトル(アルゴリズムとデータ構造１) • 見出し – 箇条書きの内容アルゴリズム • アルゴリズムは必ず問題を解決するもの – いつかは停止しないといけない • ひとつまたは複数のデータを操作し目的の結果を得るための一連の処理手順 • 例: 交差点を渡りたい(＝問題) – 信号があるか？ – 信号がないならば、どうするか？なぜ学習するか？ • すばやくコーディングするため • 美しいコードを書くため • わかりやすいコードにするため • どのように表現するか、どのように処理し目的を達成するか、を理解するすばやくコーディングする • よくしられたものを使う – さがせばどこかに実装が存在する – あるものを使えばデバグの手間がはぶける • 全体をよく考えて、よく知られたものが使えるようにする – そのために勉強する！美しいコード • 洗練されたコードは美しい – 適切なアルゴリズム – 適切なデータ構造 • コーディング規則の外側に美しさがある – 人間が読み書きするものであることを肝に銘じて – きちゃないコードは読む気がするか？わかりやすいコード • 構造がわかりやすい – よくしられたデータ構造 – よくしられたアルゴリズム – これらの再帰的な組み合わせ • 構造がプログラミング言語の自然なデータ型や制御文に合っている • プログラムの共有ができる – 3日後の自分は他人と同じ