情報数学ⅡB

科目基礎情報

学校 豊田工業高等専門学校 開講年度 平成30年度 (2018年度)
授業科目 情報数学ⅡB
科目番号 34223 科目区分 専門 / 選択
授業形態 講義 単位の種別と単位数 履修単位: 1
開設学科 情報工学科 対象学年 4
開設期 後期 週時間数 2
教科書/教材 特に指定しない/教材用プリント配布
担当教員 稲垣 宏

到達目標

(ア)ダイクストラのアルゴリズムを使って、最短経路探索問題を解くことができる。
(イ)有向グラフの深さ探索における辺の分類ができる。
(ウ)最小木の概念がわかっており、最小木を求めることができる。
(エ)Ford-Fulkerson法を使って、ネットワーク流問題を解くことができる。
(オ)2部グラフにおける最大マッチング問題を、ネットワーク流問題に還元して解くことができる。
(カ)代表的なグラフの種類とその性質を知っている。

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
ダイクストラのアルゴリズムを使って、応用課題に対する最短経路探索問題を解くことができる。また、有向グラフの深さ探索における辺の分類をするアルゴリズムが説明できる。ダイクストラのアルゴリズムを使って、例題に対する最短経路探索問題を解くことができる。また、有向グラフの深さ探索における辺の分類ができる。ダイクストラのアルゴリズムを使って、例題に対する最短経路探索問題を解くことができない。有向グラフの深さ探索における辺の分類ができない。
代表的なグラフの種類と性質を、データ構造を含めて説明できる。また、最小全域木の概念がわかっており、応用課題に対する最小全域木を求めることができる。代表的なグラフの種類と性質を説明できる。また、最小全域木の概念がわかっており、例題に対する最小全域木を求めることができる。代表的なグラフの種類と性質を説明することができない。さらに、最小全域木の概念がわかっておらず、例題に対する最小全域木を求めることができない。
Ford-Fulkerson法を使って、応用課題に対するネットワーク流問題(2部グラフの最大マッチング問題を含む)を解くことができる。Ford-Fulkerson法を使って、例題に対するネットワーク流問題(2部グラフの最大マッチング問題を含む)を解くことができる。Ford-Fulkerson法を使って、例題に対するネットワーク流問題(2部グラフの最大マッチング問題を含む)を解くことができない。

学科の到達目標項目との関係

学習・教育到達度目標 A4, JABEE d, 本校教育目標 ②

教育方法等

概要:
現代の情報化社会においては、大規模なコンピュータシステムを開発するためのソフトウェア技術が非常に重要な役割を果たしている。この技術の基盤となっているのが、情報数学をはじめとする計算機科学である。本講義では、「情報数学II A」に引き続き、効率的なシステム開発を行なう上で特に大切であると思われる数理的手法を取り上げ、わかりやすく解説する。そこでは、各種のグラフ構造およびそれらを利用した多様なグラフアルゴリズムを扱うテーマが中心になっている。
授業の進め方と授業内容・方法:
授業の前半で、スライドを使って、基礎的な理論の説明をし、その後、後半の時間を使って、知識を確認し自分のものにするため、毎回演習を行なう。内容としては、各種のグラフ構造とそれらを利用した多様なグラフアルゴリズムを扱うテーマが中心になっている。
注意点:

授業計画

授業内容・方法 週ごとの到達目標
後期
1週 シラバスを用いた授業内容の説明、 最短経路探索問題とは、ダイクストラのアルゴリズム ダイクストラのアルゴリズムを使った最多経路探索アルゴリズムの処理手順を説明できる。
2週 グラフの連結性とは、関節点とは、関節点検出アルゴリズム 関節点検出アルゴリズムの処理手順を説明できる。
3週 有向グラフにおける深さ優先探索、上昇辺・下降辺・交差辺とは 有向グラフにおいて深さ優先探索を行った際の、辺の分類ができる。
4週 トポロジカルソートとは、有向グラフの深さ優先探索を利用したトポロジカルソートの実現 トポロジカルソートの処理手順を説明できる。
5週 強連結とは、強連結成分への分解アルゴリズム 強連結成分への分解アルゴリズムの処理手順を説明できる。
6週 最小木(Minimum Spanning Tree)とは、最小木を求めるためのアルゴリズム-Prim法 Prim法を利用した最小木を求めるアルゴリズムの処理手順を説明できる。
7週 最小木を求めるためのアルゴリズム-Kruskal法 Kruskal法を利用した最小木を求めるアルゴリズムの処理手順を説明できる。
8週 動的計画法とは、最短経路探索問題におけるFloydのアルゴリズム 動的計画法の概念と、Floyd法を使った最多経路探索アルゴリズムの処理手順を説明できる。
9週 ここまでの総復習 グラフの基本的な性質と、主なグラフアルゴリズムの処理手順を説明することができる。
10週 ネットワークとは、ネットワーク流問題とは、Ford-Fulkerson法 Ford-Fulkerson法を使った最大ネットワーク流の算出アルゴリズムの処理手順を説明できる。
11週 2部グラフとは、2部グラフにおける最大マッチング問題とその解法(Ford-Fulkerson法を利用) Ford-Fulkerson法を使った最大マッチング問題の解法アルゴリズムの処理手順を説明できる。
12週 割り当て問題とその解法(Ford-Fulkerson法を利用) Ford-Fulkerson法を使った割り当て問題の解法アルゴリズムの処理手順を説明できる。
13週 安定結婚問題とその解法 安定結婚問題の解法アルゴリズムの処理手順を説明できる。
14週 問題の難しさの計り方、クラスNP問題とは、ハミルトン閉路と巡回セールスマン問題 分枝限定法の概念と、それを利用した巡回セールスマン問題の処理手順を説明できる。
15週 次数、次数列、完全グラフ、平面グラフ、オイラーの公式、彩色問題、4色定理 次数・次数列・完全グラフ・平面グラフ・オイラーの公式・彩色問題の意味を説明できる。
16週

評価割合

中間試験定期試験合計
総合評価割合4060100
専門的能力4060100