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

数理情報科学特論Ⅳ

このページを印刷する

令和３年度以降入学者 数理情報科学特論Ⅳ
教員名 前澤俊一
単位数    2 課程 前期課程 開講区分 文理学部
科目群 地球情報数理科学専攻
学期 後期 履修区分 選択必修
授業形態 対面授業
授業概要 グラフ上の最適化問題を利用して，離散最適化問題における有用なアルゴリズムやその理論について学ぶ．
授業のねらい・到達目標 情報科学の基礎であるアルゴリズムを理解し，その正当性がきちんと示せることを目的とする．
また，解の最良性のみでなく，計算時間や近似の精度といった概念についても理解することを目指す．
授業の形式 講義、演習
授業の方法 配布資料の内容の講義を行い，その定着のためにいくつかの演習問題を解いてもらう．
授業計画
1 計算量のオーダーによる評価，NP-困難性について学ぶ
【事前学習】授業の事前配布資料を確認し，わからなかった箇所をメモしておく （2時間）
【事後学習】授業でわからなかった箇所を復習する （2時間）
【授業形態】対面授業
2 グラフの定義と基本概念について学ぶ
【事前学習】授業の事前配布資料を確認し，わからなかった箇所をメモしておく （2時間）
【事後学習】授業でわからなかった箇所を復習する （2時間）
【授業形態】対面授業
3 グラフの次数列と数列がグラフ的であるかの判定方法について学ぶ
【事前学習】授業の事前配布資料を確認し，わからなかった箇所をメモしておく （2時間）
【事後学習】授業でわからなかった箇所を復習する （2時間）
【授業形態】対面授業
4 深さ優先探索と幅優先探索について学ぶ
【事前学習】授業の事前配布資料を確認し，わからなかった箇所をメモしておく （2時間）
【事後学習】授業でわからなかった箇所を復習する （2時間）
【授業形態】対面授業
5 最小重み全域木を導入し，Kruskalのアルゴリズムを学ぶ
【事前学習】授業の事前配布資料を確認し，わからなかった箇所をメモしておく （2時間）
【事後学習】授業でわからなかった箇所を復習する （2時間）
【授業形態】対面授業
6 最短経路問題を導入し，Dijkstraのアルゴリズムを学ぶ
【事前学習】授業の事前配布資料を確認し，わからなかった箇所をメモしておく （2時間）
【事後学習】授業でわからなかった箇所を復習する （2時間）
【授業形態】対面授業
7 負の重みをもつ最短経路問題を導入し，Bellman-Fordのアルゴリズムを学ぶ
【事前学習】授業の事前配布資料を確認し，わからなかった箇所をメモしておく （2時間）
【事後学習】授業でわからなかった箇所を復習する （2時間）
【授業形態】対面授業
8 これまでの内容の復習レポートの作成を行う
【事前学習】これまでの授業資料を見直す （2時間）
【事後学習】レポートの作成を行う （2時間）
【授業形態】課題研究
9 2部グラフの最大マッチング問題を導入し，その最適解を求めるアルゴリズムを学ぶ
【事前学習】授業の事前配布資料を確認し，わからなかった箇所をメモしておく （2時間）
【事後学習】授業でわからなかった箇所を復習する （2時間）
【授業形態】対面授業
10 一般のグラフの最大マッチングを求めるEdmondsのアルゴリズムを学ぶ
【事前学習】授業の事前配布資料を確認し，わからなかった箇所をメモしておく （2時間）
【事後学習】授業でわからなかった箇所を復習する （2時間）
【授業形態】対面授業
11 最大流問題を導入し，最大流最小カット定理を学ぶ
【事前学習】授業の事前配布資料を確認し，わからなかった箇所をメモしておく （2時間）
【事後学習】授業でわからなかった箇所を復習する （2時間）
【授業形態】対面授業
12 ネットワークフローから最大流を求めるFord-Fullkersonのアルゴリズムを学ぶ
【事前学習】授業の事前配布資料を確認し，わからなかった箇所をメモしておく （2時間）
【事後学習】授業でわからなかった箇所を復習する （2時間）
【授業形態】対面授業
13 多項式時間帰着を導入し，いくつかのNP-困難問題について学ぶ
【事前学習】授業の事前配布資料を確認し，わからなかった箇所をメモしておく （2時間）
【事後学習】授業でわからなかった箇所を復習する （2時間）
【授業形態】対面授業
14 巡回セールスマン問題を導入し，その基本的な性質について学ぶ
【事前学習】授業の事前配布資料を確認し，わからなかった箇所をメモしておく （2時間）
【事後学習】授業でわからなかった箇所を復習する （2時間）
【授業形態】対面授業
15 これまでの内容の復習レポートの作成を行う
【事前学習】これまでの授業資料を見直す （2時間）
【事後学習】レポートの作成を行う （2時間）
【授業形態】課題研究
その他
教科書 使用しない
参考書 使用しない
成績評価の方法及び基準 レポート:第8回と第15回に出すレポート課題(100%)
オフィスアワー 毎週水曜日12時～13時

↑このページのトップ