情報科学講究２

科目名	情報科学講究２
教員名	齋藤明
単位数	2	学年	3	開講区分	文理学部
科目群	情報科学科
学期	後期	履修区分	必修

授業概要	グラフ理論に関する論文講読
授業のねらい・到達目標	「情報科学講究１」に引き続き、配布プリント及び論文の輪読を通して発想と論理の力を養う。題材はグラフ理論から選ばれることが多くなる。受講者は４年次の卒業研究を進めるための基礎的な力をつけことができる。。この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応しています。
授業の方法	「情報科学講究１」と同じく、配付プリントの輪読とプログラム実習を行う。また卒業研究の大まかなテーマに関する解説を行い、予備的な学習を進める。本授業の事前・事後学習は，各２時間の学習を目安とする。
履修条件	学科内規による。

授業計画
1	補グラフ、グラフの演算に関する概念を英語で学ぶ。 [事前学習] 配布する英文プリントの16～18ページを読んでおく。 [事後学習] Section 1.1 Exercise 13～17を解く。
2	グラフの基本的な性質に関する総合演習を行う。 [事前学習] Section 1.1 Exercise 18～20を解く。 [事後学習] Section 1.1 Exercise 23～24を解く。
3	補グラフ、グラフの演算に関する概念を英語で学ぶ。 [事前学習] 英文プリントの16～18ページを読んでおく。 [事後学習] Section 1.1 Exercise 13～17を解く。
4	次数列の概念とHavel-Hakimiの定理を英語で学ぶ。 [事前学習] 英文プリントの22～26ページを読んでおく。 [事後学習] Section 1.2 Exercise 1～3を解く。
5	Erdos-Gallaiの定理とirregular graphの非存在性を学ぶ。 [事前学習] 英文プリントの26～28ページを読んでおく。 [事後学習] Section 1.2 Exercise 4～7を解く。
6	グラフの次数に関する総合演習を行う。 [事前学習] Section 1.2 Exercise 8～9を解く。 [事後学習] Section 1.2 Exercise 14～15を解く。
7	グラフのウォーク、道、閉路といった概念を英語で学ぶ。 [事前学習] 英文プリントの30～32ページを読んでおく。 [事後学習] Section 1.3 Exercise 1～3を解く。
8	隣接行列の概念とその性質を英語で学ぶ。 [事前学習] 英文プリントの32～35ページを読んでおく。 [事後学習] Section 1.3 Exercise 4～8を解く。
9	グラフの連結性、２頂点間の距離と言った概念を英語で学ぶ。 [事前学習] 英文プリントの35～38ページを読んでおく。 [事後学習] Section 1.3 Exercise 9～17を解く。
10	グラフの直径、半径、中心といった概念を英語で学ぶ。 [事前学習] 英文プリントの38～41ページを読んでおく。 [事後学習] Section 1.3 Exercise 18～23を解く。
11	グラフの連結性に関する総合演習を行う。 [事前学習] Section 1.3 Exercise 24～31を解く。 [事後学習] Section 1.3 Exercise 37～38を解く。
12	多重グラフの概念とその性質を英語で学ぶ。 [事前学習] 英文プリントの45～46ページを読んでおく。 [事後学習] Section 1.4 Exercise 1～4を解く。
13	有向グラフの概念とその性質を英語で学ぶ。 [事前学習] 英文プリントの47～50ページを読んでおく。 [事後学習] Section 1.4 Exercise 5～11を解く。
14	有向グラフのに関する連結性の概念を学ぶ。 [事前学習] 英文プリントの50～51ページを読んでおく。 [事後学習] Section 1.4 Exercise 12～14を解く。
15	多重グラフと有向グラフに関する総合演習を行う。 [事前学習] Section 1.3 Exercise 25～16を解く。 [事後学習] Section 1.3 Exercise 18～19を解く。

その他
教科書	教科書は使用しない。
参考書	使用しない
成績評価の方法及び基準	授業参画度(100%) 授業参画度は、ディスカッションを通して測られる事前準備状況と議論の深度、および発表の質で評価される。
オフィスアワー	毎週金曜日の 12:10～13:00 をオフィスアワーとする。可能であれば電子メールにてアポイントを取ること。電子メールアドレスは授業初回に伝える。アポイントを取らずに来室することも可能だが、アポイントを取ってきた人がいる場合にはそちらを優先する。