学部・大学院区分
Undergraduate / Graduate		情報学部
時間割コード
Registration Code		1001270
科目区分
Course Category
専門科目(自然情報)，関連専門科目(人社，CS)
科目名　【日本語】
Course Title		数理情報学演習５
科目名　【英語】
Course Title		Mathematical Informatics Exercise 5
コースナンバリングコード
Course Numbering Code		SIS-11-3027-J
担当教員　【日本語】
Instructor		加藤　晃太郎 ○
担当教員　【英語】
Instructor		KATO Kohtaro ○
単位数
Credits		1
開講期・開講時間帯
Term / Day / Period		春１期 火曜日 ３時限
Spring1 Tue 3
対象学年
Year		３年
3
授業形態
Course style		演習
Seminar
開講系（学部）・開講専攻（大学院）
Subject
情報学部・自然・数理情報
必修・選択
Required / Selected
選択


授業の目的　【日本語】
Goals of the Course(JPN)
数理情報学演習5では，グラフ理論に関連するテーマの中から，数理情報学3-4で学ぶグラフに関する基本的な問題に対するアルゴリズム関連する話題を中心に，連結性，k辺連結性，k点連結性，強連結性，木とカット，深さ優先探索，幅優先探索，平面グラフ，双対グラフ，グラフ彩色などに関する演習を行う。計算手続きの動作を確認する基礎的な問題演習や，関連する性質の証明などに関する問題演習を行うことにより，これらの基本的な性質とアルゴリズムおよびその計算量と正当性に関する理解を深める.
授業の目的　【英語】
Goals of the Course
Learn topics related to graph theory, which includes graph algorithms, connectivity, trees, cuts, tree, planar graphs, dual graphs, coloring via exercises. This class is connected with Mathematical Informatics 3-4.
到達目標　【日本語】
Objectives of the Course(JPN)
グラフ理論は，情報通信や最適化をはじめとする情報学の諸分野における基礎理論であり，通信網，電気回路，化学物質の構造など，様々な対象に幅広い応用を持つ。本講義では，数理情報学3-4で学ぶグラフに関する話題を中心に，グラフ理論における基礎的な問題を解決するアルゴリズムを，演習を通して理解を深めることを目的とする。
到達目標　【英語】
Objectives of the Course
授業の内容や構成
Course Content / Plan
グラフ理論を理解する上で必要となる，グラフの定義や基礎的な用語や応用について紹介したのち，グラフ理論において重要な話題である連結性，k辺連結性，k点連結性，強連結性，木とカット，深さ優先探索，幅優先探索，平面グラフ，双対グラフ，グラフ彩色について，それらの基本的な性質とアルゴリズムおよびその計算量と正当性について学び，演習を通して理解を深める。

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