到達目標
(1) グラフに関する基本用語を理解できる
(2) グラフに関する基本的な性質を理解できる
(3) 基本的なグラフアルゴリズムを理解できる
【教育目標】D
【キーワード】初等グラフ理論，一筆書き，最小全域木，最短経路問題
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| グラフに関する基本用語を理解できる | グラフに関する基本用語を使った説明ができる | グラフに関する基本用語を使用した説明を理解できる | グラフに関する基本用語を使用した説明を理解できない |
| グラフに関する基本的な性質を理解できる | グラフに関する基本的な性質について自ら証明できる | グラフに関する基本的な性質についての証明を理解できる | グラフに関する基本的な性質についての証明を理解できない |
| 基本的なグラフアルゴリズムを理解できる | 基本的なグラフアルゴリズムを自ら実装できる | 基本的なグラフアルゴリズムの原理を理解できる | 基本的なグラフアルゴリズムの原理を理解できない |
学科の到達目標項目との関係
教育方法等
概要:
グラフ理論およびグラフアルゴリズムの基礎を講義する。グラフに関する用語を説明した後、グラフの基本的な性質を明らかにする。その後、グラフ上の処理に関するアルゴリズムを紹介する。
授業の進め方・方法:
原則として講義形式で授業を進めるが、状況により実習を行うことがある。また、課題に関して受講者の前で説明してもらうことがある。
予習により不明点を明確にし、復習により毎回の授業の内容を理解し、宿題を行うこと。
注意点:
授業中に出す課題と試験により評価を行う。詳細は１回目の授業で説明する。
【事前学習】
授業で扱う内容について教科書の記載を確認すること。また、前回の授業で扱った内容について復習し、用語の意味を再確認しておくこと。
【評価方法・評価基準】
試験結果（70％）、課題（30％）で評価する。詳細は第１回目の授業で告知する。
グラフ理論とグラフアルゴリズムの基本的事項についての理解度とこれらについての論理的な説明能力を評価する。
総合成績60点以上を単位修得とする。
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
グラフ理論とグラフアルゴリズムの概要説明 |
本講義で学ぶ内容の概要を理解する
|
| 2週 |
グラフの基本用語および様々なグラフ |
グラフに関する基本用語および代表的なグラフの種類を理解する
|
| 3週 |
道と閉路 |
道と閉路に関する基本的な性質を理解する
|
| 4週 |
木 |
木に関する基本的な性質を理解する
|
| 5週 |
平面性 |
平面グラフの基本的な性質を理解する
|
| 6週 |
グラフ彩色 |
グラフ彩色に関する基本的な性質を理解する
|
| 7週 |
有向グラフ |
有向グラフに関する基本的な性質を理解する
|
| 8週 |
マッチング |
グラフ上のマッチング問題に関する基本的な性質を理解する
|
| 2ndQ |
| 9週 |
最小全域木を求めるアルゴリズム |
最小全域木を求めるアルゴリズムを理解する
|
| 10週 |
最短経路問題のためのアルゴリズム |
グラフ上の最短経路を求めるアルゴリズムを理解する
|
| 11週 |
最短経路問題の応用 |
最短経路問題の実社会への応用について理解する
|
| 12週 |
最大流問題のためのアルゴリズム |
最大流問題のためのアルゴリズムを理解する
|
| 13週 |
マッチング問題に対するアルゴリズム |
マッチング問題のためのアルゴリズムを理解する
|
| 14週 |
二部グラフ上のマッチング問題に対するアルゴリズム |
二部グラフ向けのマッチングアルゴリズムを理解する
|
| 15週 |
期末試験 |
|
| 16週 |
期末試験解説 |
本講義で扱った内容を振り返り、理解が足りなかった内容について理解する
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
評価割合
| 試験 | 課題 | 相互評価 | 態度 | ポートフォリオ | その他 | 合計 |
| 総合評価割合 | 70 | 30 | 0 | 0 | 0 | 0 | 100 |
| 基礎的能力 | 20 | 10 | 0 | 0 | 0 | 0 | 30 |
| 専門的能力 | 30 | 10 | 0 | 0 | 0 | 0 | 40 |
| 分野横断的能力 | 20 | 10 | 0 | 0 | 0 | 0 | 30 |