グラフ・ネットワーク理論

授業目的
グラフ理論とネットワーク理論から,基礎的かつ重要な話題を選んで,数学的な基本事項を理解し,代表的なアルゴリズムを学ぶ.これらは情報科学のあらゆる分野で必要とされる基礎知識であるので,本講義を通じて理解を深めておくことが求められる.
到達目標
グラフやネットワークを用いた問題の定式化ができるようになる.基本的なグラフやネットワークの用語を理解する.グラフに関する基本的な最適化問題とその解法を理解する.
授業計画
第1回グラフと関連する概念
第2回グラフを歩く
【授業外学修】以降,資料をLUNAにあげるので,復習すること
第3回木とグラフの探索
【授業外学修】復習問題
第4回迷路を解こう
【授業外学修】復習問題
第5回グラフ上の最適化問題
【授業外学修】疑似コード作成
第6回グラフ彩色と4色問題
【授業外学修】復習問題
第7回平面グラフと幾何学
【授業外学修】復習問題
第8回中間試験もしくは中間レポートの作成
【授業外学修】復習問題
第9回最小全域木とそのアルゴリズム
【授業外学修】復習問題
第10回動的計画法と最短路
【授業外学修】復習問題
第11回ダイクストラアルゴリズムとデータ構造
【授業外学修】復習問題
第12回グラフのカットとフロー
【授業外学修】復習問題
第13回フローとマッチング
【授業外学修】復習問題
第14回グラフ問題と線形代数・線形計画法
【授業外学修】復習問題
第15回定期試験もしくは期末レポート
【授業外学修】なし
**こちらの内容は2023年4月10日を基準としたものです.最新のシラバス情報,詳細は大学提供のシラバス情報照会ページシラバス情報照会ページで確認してください**