文理学部シラバスTOP > 大学院博士前期課程 > 地球情報数理科学専攻 > 情報科学特別講究III
日本大学ロゴ

情報科学特別講究III

このページを印刷する

科目名 情報科学特別講究III
教員名 戸田誠之助
単位数    1 課程 前期課程 開講区分 文理学部
科目群 地球情報数理科学専攻
学期 前期 履修区分 必修
授業概要 講究全体を通して，アルゴリズム論全体を俯瞰し，専門的な文献を読み解く力を養う．特に，処理効率の解析手法，アルゴリズム設計技法と各種データ構造の効用を理解することを主な目標とする．
授業のねらい・到達目標 アルゴリズム設計技法と各種データ構造の効用が理解できる．

この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応しています。
授業の方法 教科書を事前に学習し，その内容をまとめた資料を作成し，授業時間に資料に基づいて発表する．アルゴリズム論に関する知識や数学的素養に応じて学習のペースを変えてもよい．教科書だけでは理解困難な事項については，別の文献を調査し，その調査結果を報告してもよい．教科書に記載されている演習問題を時間の許す限り解くことが望ましい．
本授業の事前・事後学習は,合わせて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%)
授業参画度は，毎回の発表用資料（レジメ，プレゼン資料等）をもとに評価します．
オフィスアワー 毎週水曜日１２：１０〜１３：００

↑このページのトップ