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


授業の目的　【日本語】
Goals of the Course(JPN)
数理情報学演習6では，数理情報学演習5に続く科目として，グラフ理論に関連するテーマの中から，数理情報学4で学ぶグラフ・ネットワークに関する基本的な問題に対するアルゴリズムに関連する話題を中心に，最短路，最小木，最大流，最小カットなどに関する演習を行う。計算手続きの動作を確認する基礎的な問題演習や，関連する性質の証明などに関する問題演習を行うことにより，これらの基本的な性質とアルゴリズムおよびその計算量と正当性に関する理解を深める。
授業の目的　【英語】
Goals of the Course
Learn topics related to graphs and networks, which includes shortest path, minimum spanning tree, maximum flow, minimum cut, and so on via exercises. This class is connected with Mathematical Informatics 4.
到達目標　【日本語】
Objectives of the Course(JPN)
数理情報学演習6ではグラフ・ネットワークの基礎的な話題からいくつか代表的なものを選び，演習形式で学ぶ。グラフ理論は，通信，最適化など，情報学の諸分野における基礎をなす理論であり，多くの対象に幅広い応用を持つ。本演習では，グラフ・ネットワークに関するさまざまな基礎理論を学び，代表的な定理やアルゴリズムなどの基礎的な話題やその性質を修得することを目的とする。
到達目標　【英語】
Objectives of the Course
授業の内容や構成
Course Content / Plan
グラフ・ネットワークの定義や基本用語を説明したのち，ネットワーク最適化に関連する話題の中から，最短路，最小木，最大流，最小カットについて，それらに対する代表的なアルゴリズムおよびその基本性質について学ぶ。

1. ガイダンス
2. グラフ・ネットワークの定義と用語
3. 最短路
4. ダイクストラ法
5. 最小木
6. プリム法とクラスカル法
7. 最大流と最小カット
8. フォード・ファルカーソン法
9. 総括
履修条件・関連する科目
Course Prerequisites and Related Courses
必ず数理情報学３，４並びに数理情報学演習５も併せて履修すること。
成績評価の方法と基準
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)