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

数理情報科学特論Ⅳ

このページを印刷する

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

↑このページのトップ