到達目標
(ア)ダイクストラのアルゴリズムを使って、最短経路探索問題を解くことができる。
(イ)有向グラフの深さ探索における辺の分類ができる。
(ウ)最小木の概念がわかっており、最小木を求めることができる。
(エ)Ford-Fulkerson法を使って、ネットワーク流問題を解くことができる。
(オ)2部グラフにおける最大マッチング問題を、ネットワーク流問題に還元して解くことができる。
(カ)代表的なグラフの種類とその性質を知っている。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| ダイクストラのアルゴリズムを使って、応用課題に対する最短経路探索問題を解くことができる。 | ダイクストラのアルゴリズムを使って、例題に対する最短経路探索問題を解くことができる。 | ダイクストラのアルゴリズムを使って、例題に対する最短経路探索問題を解くことができない。 |
| 最小全域木の概念がわかっており、応用課題に対する最小全域木を求めることができる。 | 最小全域木の概念がわかっており、例題に対する最小全域木を求めることができる。 | 最小全域木の概念がわかっておらず、例題に対する最小全域木を求めることができない。 |
| Ford-Fulkerson法を使って、応用課題に対するネットワーク流問題を解くことができる。 | Ford-Fulkerson法を使って、例題に対するネットワーク流問題を解くことができる。 | Ford-Fulkerson法を使って、例題に対するネットワーク流問題を解くことができない。 |
学科の到達目標項目との関係
教育方法等
概要:
現代の情報化社会においては、大規模なコンピュータシステムを開発するためのソフトウェア技術が非常に重要な役割を果たしている。この技術の基盤となっているのが、情報数学をはじめとする計算機科学である。本講義では、「情報数学II A」に引き続き、効率的なシステム開発を行なう上で特に大切であると思われる数理的手法を取り上げ、わかりやすく解説する。そこでは、各種のグラフ構造およびそれらを利用した多様なグラフアルゴリズムを扱うテーマが中心になっている。
授業の進め方・方法:
授業の前半で、スライドを使って、基礎的な理論の説明をし、その後、後半の時間を使って、知識を確認し自分のものにするため、毎回演習を行なう。内容としては、各種のグラフ構造とそれらを利用した多様なグラフアルゴリズムを扱うテーマが中心になっている。
注意点:
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 後期 |
| 3rdQ |
| 1週 |
シラバスを用いた授業内容の説明、 最短経路探索問題とは、ダイクストラのアルゴリズム |
ダイクストラのアルゴリズムを使った最多経路探索アルゴリズムの処理手順を説明できる。
|
| 2週 |
グラフの連結性とは、関節点とは、関節点検出アルゴリズム |
関節点検出アルゴリズムの処理手順を説明できる。
|
| 3週 |
有向グラフにおける深さ優先探索、上昇辺・下降辺・交差辺とは |
有向グラフにおいて深さ優先探索を行った際の、辺の分類ができる。
|
| 4週 |
トポロジカルソートとは、有向グラフの深さ優先探索を利用したトポロジカルソートの実現 |
トポロジカルソートの処理手順を説明できる。
|
| 5週 |
強連結とは、強連結成分への分解アルゴリズム |
強連結成分への分解アルゴリズムの処理手順を説明できる。
|
| 6週 |
最小木(Minimum Spanning Tree)とは、最小木を求めるためのアルゴリズム－Prim法 |
Prim法を利用した最小木を求めるアルゴリズムの処理手順を説明できる。
|
| 7週 |
最小木を求めるためのアルゴリズム－Kruskal法 |
Kruskal法を利用した最小木を求めるアルゴリズムの処理手順を説明できる。
|
| 8週 |
動的計画法とは、最短経路探索問題におけるFloydのアルゴリズム |
動的計画法の概念と、Floyd法を使った最多経路探索アルゴリズムの処理手順を説明できる。
|
| 4thQ |
| 9週 |
ここまでの総復習 |
グラフの基本的な性質と、主なグラフアルゴリズムの処理手順を説明することができる。
|
| 10週 |
ネットワークとは、ネットワーク流問題とは、Ford-Fulkerson法 |
Ford-Fulkerson法を使った最大ネットワーク流の算出アルゴリズムの処理手順を説明できる。
|
| 11週 |
2部グラフとは、2部グラフにおける最大マッチング問題とその解法（Ford-Fulkerson法を利用） |
Ford-Fulkerson法を使った最大マッチング問題の解法アルゴリズムの処理手順を説明できる。
|
| 12週 |
割り当て問題とその解法（Ford-Fulkerson法を利用） |
Ford-Fulkerson法を使った割り当て問題の解法アルゴリズムの処理手順を説明できる。
|
| 13週 |
安定結婚問題とその解法 |
安定結婚問題の解法アルゴリズムの処理手順を説明できる。
|
| 14週 |
問題の難しさの計り方、クラスNP問題とは、ハミルトン閉路と巡回セールスマン問題 |
分枝限定法の概念と、それを利用した巡回セールスマン問題の処理手順を説明できる。
|
| 15週 |
次数、次数列、完全グラフ、平面グラフ、オイラーの公式、彩色問題、4色定理 |
次数・次数列・完全グラフ・平面グラフ・オイラーの公式・彩色問題の意味を説明できる。
|
| 16週 |
|
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
評価割合
| 中間試験 | 定期試験 | 合計 |
| 総合評価割合 | 40 | 60 | 100 |
| 専門的能力 | 40 | 60 | 100 |