到達目標
(ア)グラフの表現方法とグラフの探索手順を説明することができる。
(イ)ダイクストラのアルゴリズムを使って、最短経路探索問題を解くことができる。
(ウ)最小木の概念がわかっており、最小木を求めることができる。
(エ)Ford-Fulkerson法を使って、ネットワーク流問題を解くことができる。
(オ)2部グラフにおける最大マッチング問題を、ネットワーク流問題に還元して解くことができる。
(カ)「集合と論理」について、基本的な概念を説明することができる。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | グラフの表現方法（行列表現とリスト表現）ならびにそれぞれの長所・短所を説明できる。また、グラフ探索アルゴリズム（幅優先・深さ優先）の流れを、データ構造の違いと関連づけて説明することができる。 | グラフの表現方法（行列表現とリスト表現）を説明できる。また、グラフ探索アルゴリズム（幅優先・深さ優先）の流れを説明することができる。 | グラフの表現方法（行列表現とリスト表現）を説明できない。また、グラフ探索アルゴリズム（幅優先・深さ優先）の流れを説明することもできない。 |
| 評価項目2 | 代表的な「グラフ構造」「ネットワーク構造」の種類と性質を説明できる。また、各種の「グラフアルゴリズム」「ネットワークアルゴリズム」を利用して、実践的な応用課題を解くことができる。 | 代表的な「グラフ構造」「ネットワーク構造」の種類と性質を説明できる。また、各種の「グラフアルゴリズム」「ネットワークアルゴリズム」を利用して、例題に示した演習課題を解くことができる。 | 代表的な「グラフ構造」「ネットワーク構造」の種類と性質を説明できる。また、各種の「グラフアルゴリズム」「ネットワークアルゴリズム」を利用して、例題に示した演習課題を解くことができない。 |
| 評価項目3 | 「集合と論理」に関する基本的な概念を理解し、応用課題を解くことができる。 | 「集合と論理」に関する基本的な概念を理解し、提示された例題を解くことができる。 | 「集合と論理」に関する基本的な概念を理解し、提示された例題を解くことができない。 |
学科の到達目標項目との関係
学習・教育到達度目標 A4 現実の問題や未知の問題に対して，問題の本質を数理的に捉え，コンピュータシステムを応用した問題解決方法を多角的視野から検討することができる．
JABEE d 当該分野において必要とされる専門的知識とそれらを応用する能力
本校教育目標 ① ものづくり能力
教育方法等
概要:
現代の情報化社会においては、大規模なコンピュータシステムを開発するためのソフトウェア技術が非常に重要な役割を果たしている。この技術の基盤となっているのが、離散数学をはじめとする計算機科学である。本講義では、まず、離散数学における中心的なテーマの一つであるグラフ理論に関して、各種グラフ構造とそれらを利用した多様なグラフアルゴリズムを紹介する。さらに、「集合と論理」に関して基本的な概念を説明する。なお、本授業は、企業において「情報システム開発」を担当していた者が、自らの実務経験を踏まえて、システム開発者の視点から、数理科学で得られた様々な知見を解説していく。
授業の進め方・方法:
授業の前半で、スライドを使って、基礎的な理論の説明をし、その後、後半の時間を使って、知識を確認し自分のものにするため、毎回演習を行なう。「情報科学」教育プログラムの選択必修科目である。
注意点:
選択必修の種別・旧カリ科目名
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
シラバスを用いた授業内容の説明、グラフとは、オイラーグラフの性質
（復習：オイラーグラフの性質を任意のグラフ構造で自分で確認してみる） |
グラフの定義を説明することができる。さらに、オイラーグラフの性質を説明することができる。
|
| 2週 |
グラフの表現方法（行列表現とリスト表現）
（演習課題の復習：返却された先回の演習課題を見直す。） |
グラフを表す２種類の方法を説明することができる。さらに、それぞれの特徴を示すことができる。
|
| 3週 |
グラフの探索（幅優先探索と深さ優先探索）
（演習課題の復習：返却された先回の演習課題を見直す。） |
２種類のグラフ探索アルゴリズムの動作の違いを説明することができる。
|
| 4週 |
最短経路探索問題とは、ダイクストラのアルゴリズム
（演習課題の復習：返却された先回の演習課題を見直す。） |
ダイクストラのアルゴリズムを使った最多経路探索アルゴリズムの処理手順を説明できる。
|
| 5週 |
グラフの連結性とは、関節点とは、関節点検出アルゴリズム
（演習課題の復習：返却された先回の演習課題を見直す。） |
関節点検出アルゴリズムの処理手順を説明できる。
|
| 6週 |
有向グラフにおける深さ優先探索、上昇辺・下降辺・交差辺とは
（演習課題の復習：返却された先回の演習課題を見直す。） |
有向グラフにおいて深さ優先探索を行った際の、辺の分類ができる。
|
| 7週 |
トポロジカルソートとは、有向グラフの深さ優先探索を利用したトポロジカルソートの実現
（演習課題の復習：返却された先回の演習課題を見直す。） |
トポロジカルソートの処理手順を説明できる。
|
| 8週 |
強連結とは、強連結成分への分解アルゴリズム
（演習課題の復習：返却された先回の演習課題を見直す。） |
強連結成分への分解アルゴリズムの処理手順を説明できる。
|
| 2ndQ |
| 9週 |
最小木(Minimum Spanning Tree)とは、最小木を求めるためのアルゴリズム－Prim法
（演習課題の復習：返却された先回の演習課題を見直す。） |
Prim法を利用した最小木を求めるアルゴリズムの処理手順を説明できる。
|
| 10週 |
最小木を求めるためのアルゴリズム－Kruskal法
（演習課題の復習：返却された先回の演習課題を見直す。） |
Kruskal法を利用した最小木を求めるアルゴリズムの処理手順を説明できる。
|
| 11週 |
全頂点ペア間の最短距離を求めるためのアルゴリズム－Floyd法
（演習課題の復習：返却された先回の演習課題を見直す。） |
Floyd法を利用した全頂点ペア間の最短路距離を求めるアルゴリズムの処理手順を説明できる。
|
| 12週 |
ネットワークとは、ネットワーク流問題とは、Ford-Fulkerson法
（演習課題の復習：返却された先回の演習課題を見直す。） |
Ford-Fulkerson法を使った最大ネットワーク流の算出アルゴリズムの処理手順を説明できる。
|
| 13週 |
2部グラフとは、2部グラフにおける最大マッチング問題とその解法（Ford-Fulkerson法を利用）
（演習課題の復習：返却された先回の演習課題を見直す。） |
Ford-Fulkerson法を利用した「2部グラフの最大マッチング問題」の解法アルゴリズムの処理手順を説明できる。
|
| 14週 |
安定結婚問題とその解法（Gale-Shapley法を利用）（演習課題の復習：返却された先回の演習課題を見直す。） |
Gale-Shapley法を使った安定結婚問題の解法アルゴリズムの処理手順を説明できる。
|
| 15週 |
グラフ理論の様々な話題：次数、次数列、完全グラフ、平面グラフ、オイラーの公式、彩色問題、4色定理
集合と論理：集合の概念と集合演算、論理代数と述語論理
（定期試験問題の復習：返却された答案を見直す。） |
次数・次数列・完全グラフ・平面グラフ・オイラーの公式・彩色問題の意味を説明できる。
集合に関する基本的な概念を理解し、集合演算を実行できる。論理代数と述語論理の基本的な概念を説明できる。
|
| 16週 |
|
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | 情報数学・情報理論 | 集合に関する基本的な概念を理解し、集合演算を実行できる。 | 4 | 前15 |
| 集合の間の関係(関数)に関する基本的な概念を説明できる。 | 4 | 前15 |
| 論理代数と述語論理に関する基本的な概念を説明できる。 | 4 | 前15 |
| 離散数学に関する知識をアルゴリズムの設計、解析に利用することができる。 | 4 | 前1,前2,前3,前4,前5,前6,前7,前8,前9,前10,前11,前12,前13,前14 |
評価割合
| 定期試験 | 合計 |
| 総合評価割合 | 100 | 100 |
| 専門的能力 | 100 | 100 |