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


授業の目的　【日本語】
数理情報学演習5では，グラフ理論に関連するテーマの中から，数理情報学3で学ぶグラフに関する基本的な問題に対するアルゴリズム関連する話題を中心に，連結性，k辺連結性，k点連結性，強連結性，木とカット，深さ優先探索，幅優先探索，平面グラフ，双対グラフ，グラフ彩色などに関する演習を行う。計算手続きの動作を確認する基礎的な問題演習や，関連する性質の証明などに関する問題演習を行うことにより，これらの基本的な性質とアルゴリズムおよびその計算量と正当性に関する理解を深める。
授業の目的　【英語】
In this course, we do exercises on graph theoretic topics such as those taught in Mathematical Informatics 3, including connectivity, k-edge connectivity, k-vertex connectivity, strong connectivity, trees, cuts, depth-first search, breadth-first search, planar graphs, dual graphs, graph coloring.
到達目標　【日本語】
グラフ理論は，情報通信や最適化をはじめとする情報学の諸分野における基礎理論であり，通信網，電気回路，化学物質の構造など，様々な対象に幅広い応用を持つ。本講義では，数理情報学3で学ぶグラフに関する話題を中心に，グラフ理論における基礎的な問題を解決するアルゴリズムを，演習を通して理解を深めることを目的とする。
到達目標　【英語】
授業の内容や構成
グラフ理論を理解する上で必要となる，グラフの定義や基礎的な用語や応用について紹介したのち，グラフ理論において重要な話題である連結性，k辺連結性，k点連結性，強連結性，木とカット，深さ優先探索，幅優先探索，平面グラフ，双対グラフ，グラフ彩色について，それらの基本的な性質とアルゴリズムおよびその計算量と正当性について学び，演習を通して理解を深める。

1. ガイダンス
2. グラフの定義と基礎用語
3. 連結性，k辺連結性，k点連結性
4. 強連結性
5. 木とカット
6. 深さ優先探索，幅優先探索
7. 平面グラフ，双対グラフ
8. グラフ彩色
履修条件・関連する科目
成績評価の方法と基準
提出物50％, 演習への取り組み状況50％（演習への取り組み状況，プレゼンテーションや討論の適切さを総合的に評価する。）
教科書・参考書
必ず数理情報学演習6も併せて履修すること。必要に応じて参考資料を配布する。
課外学習等（授業時間外学習の指示）
演習時間中に説明した内容に関連する課題を与える。
授業開講形態等
遠隔授業（オンデマンド型）で行う場合の追加措置