到達目標
3年次で学んだ離散数学を基礎にグラフ理論について学び、グラフ理論がコンピュータとどのように結びついているのかを様々なアルゴリズムを通じて理解する。
1. グラフ理論の表現や考え方に慣れ、理論的な証明ができるようになること。
2. アルゴリズムを理解し、そのアルゴリズムを適用できるようになること。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | グラフ理論の表現や考え方を分かりやすく説明でき、応用問題においても理論的な証明を正確に行える。 | グラフ理論の表現や考え方を説明でき、基本問題において理論的な証明を行える。 | グラフ理論の表現や考え方が説明できない。基本問題において理論的な証明が行えない。 |
| 評価項目2 | アルゴリズムを分かりやすく説明でき、応用問題においてもアルゴリズムを正確に適用できる。 | アルゴリズムを説明し、基本的なアルゴリズムを適用できる。 | アルゴリズムを説明できない。基本的なアルゴリズムを適用できない。 |
学科の到達目標項目との関係
教育方法等
概要:
3年次で学んだ離散数学を基礎にグラフ理論について学び、グラフ理論がコンピュータとどのように結びついているのかを様々なアルゴリズムを通じて理解する。
授業の進め方・方法:
離散数学Ⅱでは情報科学の基礎理論の一つであるグラフ理論を学びます。実際にグラフを描きながら考えることが非常に重要です。グラフ理論特有の証明方法を積極的に修得してください。
注意点:
講義ノートの内容を見直し、講義に関係する例題・演習問題を解いておくこと。講義で示した次回予定の部分を予習しておくこと。
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
グラフの基礎(1) |
グラフを用いてパズルをモデル化し解ける。
グラフの和、結び、積、誘導部分グラフを説明できる。
|
| 2週 |
グラフの基礎(2) |
グラフと隣接行列の相互変換ができる。
|
| 3週 |
グラフの基礎(3) |
グラフの連結度と辺連結度を求められる。
|
| 4週 |
最短経路問題 |
ダイキストラ法を用いて最短経路問題を解ける。
|
| 5週 |
周遊問題(1) |
オイラー回路を求めたり、郵便配達人問題を解ける。
|
| 6週 |
周遊問題(2) |
ハミルトン閉路を求めたり、巡回セールスマン問題を説明できる。
|
| 7週 |
(中間試験) |
|
| 8週 |
木と全域木(1) |
木の中心と重心を求められる。
ケーリーの定理を説明でき、ラベル付けされた木の個数を求められる。
|
| 2ndQ |
| 9週 |
木と全域木(2) |
根付き木の同型判定を用いて判定できる。
欲張りアルゴリズムを用いて最小重み全域木を求められる。
|
| 10週 |
平面グラフ(1) |
オイラーの公式を説明でき、応用できる。
|
| 11週 |
平面グラフ(2) |
クラトフスキーの平面的グラフ判定定理を用いて判定できる。
|
| 12週 |
グラフの彩色 |
点彩色のブルックスの定理、辺彩色のビジングの定理を説明できる。
|
| 13週 |
ネットワークと流れ(1) |
入口、出口、容量、流量を説明できる。
|
| 14週 |
ネットワークと流れ(2) |
最大流・最小カット定理を説明できる。
|
| 15週 |
(期末試験) |
|
| 16週 |
総復習 |
|
評価割合
| 試験 | 課題 | 合計 |
| 総合評価割合 | 80 | 20 | 100 |
| 基礎的能力 | 0 | 0 | 0 |
| 専門的能力 | 80 | 20 | 100 |
| 分野横断的能力 | 0 | 0 | 0 |