検索したい科目／教員名／キーワードを入力し「検索開始｣ボタンをクリックしてください。
※教員名では姓と名の間に１文字スペースを入れて、検索してください。
情報科学特別講究III
| 科目名 平成28年度以後入学者 |
情報科学特別講究III | ||||
|---|---|---|---|---|---|
| 教員名 | 戸田 誠之助 | ||||
| 単位数 | 1 | 課程 | 前期課程 | 開講区分 | 文理学部 |
| 学期 | 前期 | 履修区分 | 必修 | ||
| 授業テーマ | アルゴリズム論の専門的な知識を学ぶ． |
|---|---|
| 授業のねらい・到達目標 | 講究全体を通して，アルゴリズム論全体を俯瞰し，専門的な文献を読み解く力を養う．特に，処理効率の解析手法，アルゴリズム設計技法と各種データ構造の効用を理解することを主な目標とする． |
| 授業の方法 | 教科書を事前に学習し，その内容をまとめた資料を作成し，授業時間に資料に基づいて発表する．教科書に記載されている演習問題を時間の許す限り解くことが望ましい． |
| 履修条件 | 学部における授業等を通して，アルゴリズム論の基礎事項を修得していることが望ましい． |
| 事前学修・事後学修，授業計画コメント | アルゴリズム論に関する知識や数学的素養に応じて学習のペースを変えてもよい．教科書だけでは理解困難な事項については，別の文献を調査し，その調査結果を報告してもよい． |
| 授業計画 | |
|---|---|
| 1 | 赤黒木の定義と回転 |
| 2 | 赤黒木の挿入 |
| 3 | 赤黒木の削除 |
| 4 | 動的順位統計のための赤黒木の強化 |
| 5 | 区間データを扱うための赤黒木の強化 |
| 6 | 動的計画アルゴリズムの基礎 |
| 7 | 行列積問題の動的計画アルゴリズム |
| 8 | 動的計画アルゴリズムの基本構造とメモ法 |
| 9 | 最長共有部分列問題の動的計画アルゴリズム |
| 10 | 最適二分探索木の動的計画アルゴリズム |
| 11 | 貪欲アルゴリズムの具体例（行動選択問題） |
| 12 | 貪欲アルゴリズムの基本構造 |
| 13 | ハフマン符号の貪欲アルゴリズム |
| 14 | 貪欲アルゴリズムとマトロイド |
| 15 | スケジュール問題へのマトロイドの応用 |
| その他 | |
|---|---|
| 教科書 | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 『Introduction to Algorithms』 The MIT Press 2009年 第3版 |
| 成績評価の方法及び基準 | 授業参画度(100%) |
| オフィスアワー | 毎週水曜日１２：１０〜１３：００ |