科目ナンバー

SE-IG3-8C31

履修条件・関連科目等

数理情報学1、数理情報学2で学ぶアルゴリズムとデータ構造の基礎知識があることが望ましい。

授業で使用する言語

日本語

授業で使用する言語（その他の言語）

授業の概要

グラフは、物と物の結びつきを表すデータ構造であり、インターネットなどの通信ネットワーク、道路や鉄道などの交通網、人と人とのつながりを表すソーシャルネットワークなどのような、現実に現れる様々なネットワークを抽象化した概念である。グラフを処理したり、グラフ上で定義される計算問題を解くためのアルゴリズムは、情報処理の多くの場面で必要とされる。本授業では、基礎的なグラフアルゴリズムについて学ぶ。また、グラフに関連した難しい問題に対するアプローチについて紹介する。

科目目的

効率的なグラフアルゴリズムと、それらを理解するために必要な離散数学・グラフ理論の基礎知識を身につける。

到達目標

情報処理の様々な場面で必要となる基本的なグラフアルゴリズムを理解し、自らプログラムしたり利用したりすることができるようになること。

授業計画と内容

第1回　グラフのデータ表現
第2回　探索アルゴリズム
第3回　強連結成分分解・2連結成分分解
第4回　オイラーグラフとオイラー閉路
第5回　最小全域木
第6回　最短路
第7回　マッチングの数理
第8回　二部グラフの最大マッチング、安定マッチング
第9回　最大フロー・最小カットの数理
第10回　最大フロー・最小カットアルゴリズム、最小費用フロー
第11回　難しい問題： 巡回セールスマン問題と配送計画問題
第12回　巡回セールスマン問題に対する構築型解法と近似解法
第13回　巡回セールスマン問題に対する改善型解法
第14回　全体のまとめと発展的な話題

授業時間外の学修の内容

指定したテキストやレジュメを事前に読み込むこと／授業終了後の課題提出

授業時間外の学修の内容（その他の内容等）

授業時間外の学修に必要な時間数／週

・毎週１回の授業が半期（前期または後期）または通年で完結するもの。１週間あたり４時間の学修を基本とします。
・毎週２回の授業が半期（前期または後期）で完結するもの。１週間あたり８時間の学修を基本とします。

成績評価の方法・基準

成績評価の方法・基準（備考）

課題や試験のフィードバック方法

授業時間内で講評・解説の時間を設ける／授業時間に限らず、manabaでフィードバックを行う

課題や試験のフィードバック方法（その他の内容等）

アクティブ・ラーニングの実施内容

実施しない

アクティブ・ラーニングの実施内容（その他の内容等）

授業におけるICTの活用方法

その他

授業におけるICTの活用方法（その他の内容等）

必要に応じて、manaba、Webexミーティング、Google共有ドライブを用いて双方向型の学び及び自主学習支援を実施する。具体的にはその都度指示する。

実務経験のある教員による授業

いいえ

【実務経験有の場合】実務経験の内容

【実務経験有の場合】実務経験に関連する授業内容

テキスト・参考文献等

テキスト：
講義の際にプリントを配布する。

参考書：
梅谷俊二：「しっかり学ぶ数理最適化 モデルからアルゴリズムまで」（講談社）
浅野孝夫：「グラフ・ネットワークアルゴリズムの基礎：数理とCプログラム」（近代科学社）
繁野麻衣子:「ネットワーク最適化とアルゴリズム」（朝倉書店）

その他特記事項

参考URL