学部・大学院区分情報学部
時間割コード1001280
科目区分
専門科目(自然情報)関連専門科目(人社，CS)
科目名　【日本語】数理情報学演習６
科目名　【英語】Mathematical Informatics Exercise 6
コースナンバリングコード
担当教員　【日本語】柳浦　睦憲 ○ 大舘　陽太
担当教員　【英語】YAGIURA Mutsunori ○ OTACHI Yota
単位数1
開講期・開講時間帯春１期 火曜日 ４時限
Spring1 Tue 4
対象学年３年
3
授業形態演習
Lecture
開講系（学部）・開講専攻（大学院）
自然・数理情報
必修・選択
選択


授業の目的　【日本語】
数理情報学演習6では，数理情報学演習5に続く科目として，グラフ理論に関連するテーマの中から，数理情報学4で学ぶグラフ・ネットワークに関する基本的な問題に対するアルゴリズムに関連する話題を中心に，最短路，最小木，最大流，最小カットなどに関する演習を行う。計算手続きの動作を確認する基礎的な問題演習や，関連する性質の証明などに関する問題演習を行うことにより，これらの基本的な性質とアルゴリズムおよびその計算量と正当性に関する理解を深める。
授業の目的　【英語】
In this course, we do exercises on graph theoretic topics such as those taught in Mathematical Informatics 4, including shortest paths, minimum spanning trees, maximum flows, and minimum cuts.
到達目標　【日本語】
数理情報学演習6ではグラフ・ネットワークの基礎的な話題からいくつか代表的なものを選び，演習形式で学ぶ。グラフ理論は，通信，最適化など，情報学の諸分野における基礎をなす理論であり，多くの対象に幅広い応用を持つ。本演習では，グラフ・ネットワークに関するさまざまな基礎理論を学び，代表的な定理やアルゴリズムなどの基礎的な話題やその性質を修得することを目的とする。
到達目標　【英語】
授業の内容や構成
グラフ・ネットワークの定義や基本用語を説明したのち，ネットワーク最適化に関連する話題の中から，最短路，最小木，最大流，最小カットについて，それらに対する代表的なアルゴリズムおよびその基本性質について学ぶ。

1. ガイダンス
2. グラフ・ネットワークの定義と用語
3. 最短路
4. ダイクストラ法
5. 最小木
6. プリム法とクラスカル法
7. 最大流と最小カット
8. フォード・ファルカーソン法
9. 総括
履修条件・関連する科目
成績評価の方法と基準
演習への取り組み状況，発表や討論の適切さを総合的に評価する。
教科書・参考書
必ず数理情報学演習5も併せて履修すること。必要に応じて参考資料を配布する。
課外学習等（授業時間外学習の指示）
演習時間中に説明した内容に関連する課題を与える。
授業開講形態等
遠隔授業（オンデマンド型）で行う場合の追加措置