離散数学Ⅱ -Discrete Mathematics 2-

担当教員・研究室 配当年次 学期 種別 単位数 授業形態 開講年度 ナンバリングコード
柳 信一 324研究室
3・4年 前期 選択 2 単位
講義（遠隔オ）
2021 SSI212
アクティブラーニング
いいえ
授業概要
離散数学の一分野であるグラフ理論は，頂点集合と頂点同士を結ぶ辺集合により定義されるグラフという数学モデルの性質を論じる分野であり，グラフを抽象的な幾何学図形として表現することにより，実世界のさまざまな問題との関連を確認することができる。例えば，スケジュール作成，ネットワーク設計，経路探索など，幅広い分野の問題にグラフ理論が適用されており，コンピュータとの関連も深いことから，情報技術者が習得すべき分野の一つとなっている。
本講義では、主に具体例を通して，グラフ理論の諸問題に対するアルゴリズムを理解することを目的とする。
授業における学修の到達目標
数理的思考に基づく現実的なグラフ問題の解法を修得する。
授業計画
回数 授業、事前・事後学習 時間
1 事前学習 教科書の該当部分をよく読み，理解できない部分を自分なりに調べる。 2
授業 グラフの基礎
事後学習 教科書の該当部分とノートを読み返し，内容を確認する。 2
2 事前学習 教科書の該当部分をよく読み，理解できない部分を自分なりに調べる。 2
授業 最小全域木とクラスカルのアルゴリズム
事後学習 教科書の該当部分とノートを読み返し，内容を確認する。 2
3 事前学習 教科書の該当部分をよく読み，理解できない部分を自分なりに調べる。 2
授業 プリムのアルゴリズムと最小シュタイナー木問題
事後学習 教科書の該当部分とノートを読み返し，内容を確認する。 2
4 事前学習 教科書の該当部分をよく読み，理解できない部分を自分なりに調べる。 2
授業 プリムのアルゴリズム演習
事後学習 教科書の該当部分とノートを読み返し，内容を確認する。 2
5 事前学習 教科書の該当部分をよく読み，理解できない部分を自分なりに調べる。 2
授業 最短経路問題
事後学習 教科書の該当部分とノートを読み返し，内容を確認する。 2
6 事前学習 教科書の該当部分をよく読み，理解できない部分を自分なりに調べる。 2
授業 最短経路問題のアルゴリズム
事後学習 教科書の該当部分とノートを読み返し，内容を確認する。 2
7 事前学習 教科書の該当部分をよく読み，理解できない部分を自分なりに調べる。 2
授業 ダイクストラのアルゴリズム
事後学習 教科書の該当部分とノートを読み返し，内容を確認する。 2
8 事前学習 教科書の該当部分をよく読み，理解できない部分を自分なりに調べる。 2
授業 ダイクストラのアルゴリズム演習
事後学習 教科書の該当部分とノートを読み返し，内容を確認する。 2
9 事前学習 教科書の該当部分をよく読み，理解できない部分を自分なりに調べる。 2
授業 オイラー回路とハミルトン閉路
事後学習 教科書の該当部分とノートを読み返し，内容を確認する。 2
10 事前学習 教科書の該当部分をよく読み，理解できない部分を自分なりに調べる。 2
授業 グラフの彩色
事後学習 教科書の該当部分とノートを読み返し，内容を確認する。 2
11 事前学習 教科書の該当部分をよく読み，理解できない部分を自分なりに調べる。 2
授業 最大流問題
事後学習 教科書の該当部分とノートを読み返し，内容を確認する。 2
12 事前学習 教科書の該当部分をよく読み，理解できない部分を自分なりに調べる。 2
授業 フォードファルカーソン法
事後学習 教科書の該当部分とノートを読み返し，内容を確認する。 2
13 事前学習 教科書の該当部分をよく読み，理解できない部分を自分なりに調べる。 2
授業 フォードファルカーソン法演習
事後学習 教科書の該当部分とノートを読み返し，内容を確認する。 2
14 事前学習 教科書の該当部分をよく読み，理解できない部分を自分なりに調べる。 2
授業 最大フロー・最小カットの定理
事後学習 教科書の該当部分とノートを読み返し，内容を確認する。 2
15 事前学習 教科書の該当部分をよく読み，理解できない部分を自分なりに調べる。 2
授業 マッチング
事後学習 教科書の該当部分とノートを読み返し，内容を確認する。 2
成績評価の方法およびその基準
次項の項目及び割合で標準評価基準に基づき総合評価する。

■ 試験（100％）□ 小テスト（　　 ％）　□ レポート（　　 ％）　□ 演習課題（　　 ％）
□ その他 [ ]
課題(試験やレポート等)に対するフィードバック方法
添削して返却する。
教科書
  • 書名:グラフ理論入門 基本とアルゴリズム ,　著者名:宮崎修一 ,　出版社:森北出版 ,　備考:電子書籍不可
参考書・Webサイト
なし
単位習得が望ましい科目
離散数学Ｉ
備考
なし
担当教員の実務経験
実務経験なし
close閉じる