| 授業方針・テーマ |
大量の情報を効率的に処理するため開発された基本的なアルゴリズムやデータ構造と、そのようなアルゴリズムの設計や解析を行なうための基本的な方法について紹介する。 |
習得できる知識・能力や授業の
目的・到達目標 |
・基本的なデータ構造やアルゴリズムを知る。
・アルゴリズムの解析法を学ぶ。
|
授業計画・内容
授業方法 |
（授業計画）
第01回 イントロダクション
第02回 アルゴリズムとは何か
第03回 挿入ソートと計算モデル
第04回 アルゴリズムの解析と設計
第05回 漸近記法
第06回 標準的な記法と一般的な関数
第07回 分割統治法
第08回 講義まとめ（1）
第09回 確率的解析と乱択アルゴリズム
第10回 ヒープソート
第11回 優先度付きキュー
第12回 クイックソート
第13回 クイックソートの解析
第14回 線形時間ソート
第15回 講義まとめ（2）
（授業方法）
教科書を元に各アルゴリズムを解説し、擬似コードを書いたり手順を図示したりして動作を理解する。 |
| 授業外学習 |
中間試験および期末試験は教科書の練習問題・章末問題の類題を出すので、毎回の授業範囲の問題を解いておくこと。
（オプション）Aizu Online Judge サーバで各アルゴリズムの演習を解く。 |
| テキスト・参考書等 |
（教科書）
コルメン他『アルゴリズムイントロダクション第3版第1巻: 基礎・ソート・データ構造・数学（世界標準MIT教科書）』（近代科学社 2012）
（参考書）
大槻「問題解決力を鍛える!アルゴリズムとデータ構造」(講談社 2020)
渡部「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」 (マイナビ 2015) |
| 成績評価方法 |
演習課題（30%）および中間試験（30%）期末試験（40%）によって評価する。 |
質問受付方法
(オフィスアワー等) |
授業時間後に質問を受け付ける他、居室が日野キャンパスにあるため、メールによる問い合わせを前提とする。 |
特記事項
(他の授業科目との関連性) |
（関連科目）
データ構造とアルゴリズムII、データ構造とアルゴリズム演習（情報科学科クラス指定科目） |
| 備考 |
|
シラバス照会