授業概要
|
|
| |
計算機科学において、考える対象を抽象的に集合として扱い、さらにその集合のようその間の関係(例えばお互いに近くにあるかどうかなど)を抽象化して得られる構造を考えると便利な場合がある。このようにして得られる概念が「グラフ」であり、グラフ理論ではこの構造の様々な性質を調べていく。 この講義では、グラフ理論の基礎的な概念の講義を行う。
|
|
|
|
学習到達目標
|
|
| |
グラフ理論の基礎的な概念を学ぶとともに、それらを計算機の上でどのように扱えばよいのかについて理解する。
|
|
|
|
キーワード
|
|
|
|
授業計画
|
|
| |
第1回 グラフとパズル (事前学習:教科書で該当部分について調べておく,事後学習:授業内容の復習と理解)
第2回 グラフの定義 (事前学習:教科書で該当部分について調べておく,事後学習:授業内容の復習と理解)
第3回 次数と握手定理 (事前学習:教科書で該当部分について調べておく,事後学習:授業内容の復習と理解)
第4回 各種グラフとグラフの演算 (事前学習:教科書で該当部分について調べておく,事後学習:授業内容の復習と理解)
第5回 グラフのコンピュータ表現 (事前学習:教科書で該当部分について調べておく,事後学習:授業内容の復習と理解)
第6回 小道、道、回路、閉路、成分 (事前学習:教科書で該当部分について調べておく,事後学習:授業内容の復習と理解)
第7回 グラフの連結度と辺連結度 (事前学習:教科書で該当部分について調べておく,事後学習:授業内容の復習と理解)
第8回 最短経路問題 (事前学習:教科書で該当部分について調べておく,事後学習:授業内容の復習と理解)
第9回 オイラー回路と郵便配達人問題 (事前学習:教科書で該当部分について調べておく,事後学習:授業内容の復習と理解)
第10回 ハミルトン閉路と巡回セールスマン問題 (事前学習:教科書で該当部分について調べておく,事後学習:授業内容の復習と理解)
第11回 木の定義と基本的な性質 (事前学習:教科書で該当部分について調べておく,事後学習:授業内容の復習と理解)
第12回 木の中心と重心 (事前学習:教科書で該当部分について調べておく,事後学習:授業内容の復習と理解)
第13回 ラベル木の数え上げ (事前学習:教科書で該当部分について調べておく,事後学習:授業内容の復習と理解)
第14回 根付き木と木の同型判定 (事前学習:教科書で該当部分について調べておく,事後学習:授業内容の復習と理解)
第15回 全域木と深さ優先探索全域木 (事前学習:教科書で該当部分について調べておく,事後学習:授業内容の復習と理解)
|
|
|
|
教科書
|
|
|
|
参考書
|
|
|
|
成績評価基準
|
|
| |
S (90点以上)
|
A (80点以上90点未満)
|
B (70点以上80点未満)
|
C (60点以上70点未満)
|
F (60点未満)
|
|
グラフ理論に関する基礎的事項の理解と視野の拡張について、十分に達成し、傑出した水準に達している。
|
グラフ理論に関する基礎的事項の理解と視野の拡張について、達成度が優れている。
|
グラフ理論に関する基礎的事項の理解と視野の拡張について、達成度が良好である。
|
グラフ理論に関する基礎的事項の理解と視野の拡張について、達成している。
|
グラフ理論に関する基礎的事項の理解と視野の拡張について、達成していないので単位が認定されない。
|
|
|
|
成績評価 の方法
|
|
| |
授業内容の理解を問う期末試験を行う。また授業外レポートも課す
|
|
|
|
成績評価割合 (%)
|
|
| |
定期試験(期末試験)
|
授業内試験等
|
宿題・授業外レポート
|
授業態度・授業への参加度
|
受講者の発表(プレゼン)
|
教員独自項目※
|
|
70
|
|
30
|
|
|
|
|
|
|
※成績評価 割合の教員独自項目
|
|
|
|
実務経験のある教員等による授業科目
|
|
|
|
備考
|
|
| |
学習時間のうちアクティブラーニング的活動の占める割合:0%
全て対面(オンラインで中継)
|
|
|