＊＊＊＊＊＊＊

科目名平成28年度入学者	＊＊＊＊＊＊＊
科目名平成27年度以前入学者	情報科学講究２
教員名	斎藤　明
単位数	2	学年	3	開講区分	文理学部
科目群	情報科学科
学期	後期	履修区分	必修

授業テーマ	グラフ理論に関する論文講読
授業のねらい・到達目標	「情報科学講究１」に引き続き、教科書及び論文の輪読を通して発想と論理の力を養う。題材はグラフ理論から選ばれることが多くなる。受講者は４年次の卒業研究を進めるための基礎的な力をつける。
授業の方法	「情報科学講究１」と同じく、教科書及びプリントの輪読とプログラム実習を行う。また卒業研究の大まかなテーマに関する解説を行い、予備的な学習を進める。
履修条件	本科目には履修条件がある。詳細は学部要覧の情報システム解析学科のページに記載されているので、参照すること。
事前学修・事後学修，授業計画コメント	事前学修：プリントを配るので、ゼミで扱う部分の前もって読んでおくこと。事後学修：毎回のゼミで、関連する話題を挙げるので、その話題に関して自ら問題を設定し解いてみる。問題自体を自ら作成することで、４年次の研究に必要な創造力を養う。

授業計画
1	「大体わかりの数学」：着想を理論につなげるための論理的思考の大切さを認識する。 [準備] 配布プリントの119～134ページを読んでおくこと。
2	「証明するということ」：証明を構築する技術を学ぶ。 [準備] 配布プリントの135～148ページを読んでおくこと。
3	１回目のプログラム課題：辺の発生確率を与えてグラフをランダムに作成するプログラムを作成する。 [準備] ポインタ操作について学修しておくこと。
4	グラフ理論（１）：グラフの定義を学ぶ。 [準備] 新たに配布するプリント（英文）の1～18ページを読んでおくこと。
5	グラフ理論（２）：次数列の概念や次数列の判定方法を学ぶ。 [準備] 配布プリント（英文）の22～28ページを読んでおくこと。
6	グラフ理論（３）：オイラーグラフの定義とその性質を学ぶ。 [準備] 配布プリント（英文）の107～114ページを読んでおくこと。
7	２回目のプログラム課題：１回目のプログラム課題で作成したグラフ上で、深さ優先探索を行うプログラムを作成する。 [準備] 再帰呼び出しについて復習しておくこと。
8	グラフ理論（４）：2-連結グラフとその性質を学ぶ。 [準備] 配布プリント（英文）の89～96ページを読んでおくこと。
9	グラフ理論（５）：木の定義とその性質を学ぶ。 [準備] 配布プリント（英文）の61～68ページを読んでおくこと。
10	グラフ理論（６）：木の数え上げの理論を学ぶ。またグラフの半径や直径、中心など、距離に関係する諸概念を学ぶ。 [準備] 配布プリント（英文）の30～45ページを読んでおくこと。
11	３回目のプログラム課題：１回目のプログラムで作成してグラフ上で、幅優先探索を行うプログラムを作成する。 [準備] スタックとキューについて復習しておくこと。
12	グラフ理論（７）：平面的グラフの概念とオイラーの公式を学ぶ。 [準備] 配布プリント（英文）の221～234ページを読んでおくこと。
13	卒業研究に向けて（１）：情報システム解析研究１から始まる卒業研究に向けて、テーマと解読にあたる論文の紹介を行う。 [準備] これまで学んできたテーマを自分なりに簡単にまとめておくこと。レポート用紙数枚でかまわない。
14	卒業研究に向けて（２）：前回に引き続き、情報システム解析研究１から始まる卒業研究に向けて、テーマと解読にあたる論文の紹介を行う。 [準備] 前回のゼミの内容を受けて、まとめておいたテーマの内容に適宜修正を加えてみよう。
15	まとめ：これまでに学んだ内容のまとめを行う。また卒業研究の題材について議論する。 [準備]:前２回分のゼミの内容を簡単にまとめ、自分が選ぶテーマを考えておくこと。

その他
教科書	なし
参考書	なし
成績評価の方法及び基準	平常点(50%)、レポート(50%)
オフィスアワー	毎週金曜日の 12:10～13:00 をオフィスアワーとする。可能であれば電子メールにてアポイントを取ること。電子メールアドレスは授業初回に伝える。アポイントを取らずに来室することも可能だが、アポイントを取ってきた人がいる場合にはそちらを優先する。