到達目標
・グラフ構造の名称や基本的な特性について理解できる．各グラフの描写ができる．
・グラフ，ネットワークが数理問題のモデル化ツールとして応用されることが説明できる．
・最短経路問題，木構築問題，彩色問題などに関する定理や解法を説明できる．
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| グラフ構造の名称や基本的な特性について説明できる．各グラフの描写ができる． | グラフ構造の名称や基本的な特性について説明できる． | グラフ構造の基本的な特性について説明できない． |
| グラフやネットワークを数理問題のモデル化ツールとして応用することができる． | グラフやネットワークが数理問題のモデル化ツールとして応用されることを説明できる． | 数理問題のモデル化という概念が説明できない． |
| 最短経路問題，木構築問題，彩色問題に関する定理，解法，計算コストを説明できる． | 最短経路問題，木構築問題，彩色問題に関する定理・解法を説明できる． | 最短経路問題，木構築問題，彩色問題の解法が説明できない． |
学科の到達目標項目との関係
学習・教育到達度目標 C
説明
閉じる
JABEE d-1
説明
閉じる
教育方法等
概要:
この講義の目標はソフトウエア開発やプログラミングにおいて，ソフトウエア化の対象となる実モデルや関係をグラフツールを用いて定式化，解析する能力や，その問題に最適なデータ構造とアルゴリズムの構築を行える能力の習得することである．
授業の進め方・方法:
プレゼンスライドと黒板板書の両方を使った講義形式でおこなう．
小セクションごとに演習問題を与える．
定期試験直前には総合的な演習を行う．
暗記ではなく論理の積み重ねで問題を考える習慣をつける．
成績評価方法：
定期試験2回の成績で行う．
中間試験(50%)，期末試験(50%)
合否判定：最終評価（または再試験の素点）≧60％を合格とする．
注意点:
基本的な離散数学・数論アルゴリズムの知識が必要である．
手続き型のプログラミング言語についての知識を習得していると望ましい．
講義は基本的にプロジェクタを利用して行う．
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 後期 |
| 3rdQ |
| 1週 |
グラフ理論概論基礎 1 |
グラフ理論における用語や定義を説明できる．
|
| 2週 |
グラフ理論概論基礎 2 |
同形の意味や除去，縮約等の操作を説明できる．
|
| 3週 |
グラフ理論概論基礎 3 |
グラフの形状やその特性について説明できる．
|
| 4週 |
パスとサイクル 1 |
歩道，小道，道，カット，橋の定義を説明できる．
|
| 5週 |
パスとサイクル 2 |
オイラーグラフの必要十分条件を説明できる.
|
| 6週 |
パスとサイクル 3 |
ハミルトン問題の困難性を説明できる.
|
| 7週 |
パスとサイクル 4 |
最短経路問題，郵便配達員問題の解を導出できる.
|
| 8週 |
中間試験 |
これまでの学習の理解度を深める．
|
| 4thQ |
| 9週 |
木構造 1 |
基本的な木構造の特性を説明できる．
|
| 10週 |
木構造 2 |
深さ優先探索木，幅優先探索木を構築できる．
|
| 11週 |
木構造 3 |
最小全域木問題の導出や電気回路解析ができる．
|
| 12週 |
平面グラフ 1 |
平面グラフの特性や，その応用例を説明できる．
|
| 13週 |
平面グラフ 2 |
平面グラフに関する様々な定理を説明できる．
|
| 14週 |
グラフの彩色 1 |
彩色問題の困難性やBrooksの定理を説明できる．
|
| 15週 |
グラフの彩色 2 |
面辺彩色の特性やVizingの定理を説明できる．
|
| 16週 |
期末試験 |
この講義の理解度・目標達成度を確認するため，試験を実施する．
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | ソフトウェア | アルゴリズムの概念を説明できる。 | 3 | |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 3 | |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 3 | |
| 整列、探索など、基本的なアルゴリズムについて説明できる。 | 3 | |
| 時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 3 | |
| 領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 3 | |
評価割合
| 試験 | 発表 | 相互評価 | 態度 | ポートフォリオ | その他 | 合計 |
| 総合評価割合 | 100 | 0 | 100 |
| 専門的能力 | 100 | 0 | 100 |