| 学部・大学院区分 | | 情報学部 | | | 時間割コード | | 1001070 | | | 科目区分 | | | | | 科目名 【日本語】 | | 数理情報学３ | | | 科目名 【英語】 | | Mathematical Informatics 3 | | | コースナンバリングコード | | | | | 担当教員 【日本語】 | | 大舘 陽太 ○
柳浦 睦憲
小野 廣隆 | | | 担当教員 【英語】 | | OTACHI Yota ○
YAGIURA Mutsunori
ONO Hirotaka | | | 単位数 | | 1 | | | 開講期・開講時間帯 | | 春１期 木曜日 ３時限
Spring1 Thu 3 | | | 対象学年 | | ３年
3 | | | 授業形態 | | 講義
Lecture | | | 開講系（学部）・開講専攻（大学院） | | | | | 必修・選択 | | | |
| 授業の目的 【日本語】 | | | 数理情報学3では，グラフ理論に関連するテーマの中から，とくにグラフに関する基本的な問題に対するアルゴリズムに関連する話題を取り上げる。グラフは通信網，電気回路，化学物質の構造など，さまざまな対象に応用を持つ。本科目では，連結性，k辺連結性，k点連結性，強連結性，木とカット，深さ優先探索，幅優先探索，平面グラフ，双対グラフ，グラフ彩色について，それらの基本的な性質とアルゴリズムおよびその計算量と正当性について学ぶ。 |
| | | 授業の目的 【英語】 | | | In Mathematical Informatics 3, we will focus on topics related to graph theory, especially algorithm regarding basic problems related to graphs. Graphs are applicable to various objects, such as communication networks, electrical circuits, and chemical structures. In this lecture, you will learn about the basic properties of connectivity, k-edge connectivity, k-point connectivity, strong-connectivity, trees and cut, depth-first search, breadth-first search, plane graph, dual graph, and graph coloring, you will also learn about algorithm as well as its computational complexity and correctness. |
| | | 到達目標 【日本語】 | | | グラフ理論は，情報通信や最適化をはじめとする情報学の諸分野における基礎理論であり，通信網，電気回路，化学物質の構造など，様々な対象に幅広い応用を持つ。本講義では，グラフに関するさまざまな基本概念を学び，グラフ理論における基礎的な問題を解決するアルゴリズムを修得することを目的とする。 |
| | | 到達目標 【英語】 | | | | | 授業の内容や構成 | | グラフ理論を理解する上で必要となる，グラフの定義や基礎的な用語や応用について紹介したのち，グラフ理論において重要な話題である連結性，k辺連結性，k点連結性，強連結性，木とカット，深さ優先探索，幅優先探索，平面グラフ，双対グラフ，グラフ彩色について，それらの基本的な性質とアルゴリズムおよびその計算量と正当性について学ぶ。
1. ガイダンス
2. グラフの定義と基礎用語
3. 連結性
4. k辺連結性
5. k点連結性
6. 強連結性
7. 木とカット
8. 深さ優先探索
9. 幅優先探索
10. 平面グラフ
11. 双対グラフ
12. グラフ彩色
13. 総括 | |
| | | 履修条件・関連する科目 | | | | | 成績評価の方法と基準 | | | 講義中に与える演習課題の評価40％，期末試験60％，合計100点満点で60点以上を合格とする。 | |
| | | 教科書・参考書 | | | 必ず数理情報学4も併せて履修すること。参考資料は必要に応じて配布する。 | |
| | | 課外学習等（授業時間外学習の指示） | | | 講義において説明した理論を理解するために課題を与える。 | |
| | | 授業開講形態等 | | | | | 遠隔授業（オンデマンド型）で行う場合の追加措置 | | | |
|