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