検索したい科目／教員名／キーワードを入力し「検索開始｣ボタンをクリックしてください。
※教員名では姓と名の間に１文字スペースを入れずに、検索してください。
情報科学講究２
| 令和元年度以前入学者 | 情報科学講究２ | ||||
|---|---|---|---|---|---|
| 教員名 | 斎藤明 | ||||
| 単位数 | 2 | 学年 | 3 | 開講区分 | 文理学部 |
| 科目群 | 情報科学科 | ||||
| 学期 | 後期 | 履修区分 | 必修 | ||
| 授業の形態 | 同時双⽅向型授業（Zoomによるライブ中継） Blackboard ID：木曜３限→20203249 |
|---|---|
| 授業概要 | グラフ理論に関する論文講読 |
| 授業のねらい・到達目標 | 「情報科学講究１」に引き続き、配布プリント及び論文の輪読を通して発想と論理の力を養う。 題材はグラフ理論から選ばれることが多くなる。受講者は４年次の卒業研究を進めるための基礎的な力をつけことができる。 この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している。 |
| 授業の方法 | 「情報科学講究１」と同じく、配付プリントの輪読とプログラム実習を行う。 また卒業研究の大まかなテーマに関する解説を行い、予備的な学習を進める。 |
| 履修条件 | 学科内規による。 |
| 授業計画 | |
|---|---|
| 1 |
補グラフ、グラフの演算に関する概念を英語で学ぶ。
【事前学習】配布する英文プリントの16～18ページを読み、内容を理解する。 （2時間） 【事後学習】グラフの直積に関する問題を解く。 （2時間） |
| 2 |
グラフの基本的な性質に関する総合演習を行う。
【事前学習】２部グラフ、補グラフなどに関するプリント内の問題を解く。 （2時間） 【事後学習】自己補グラフに関する発展問題を解く。 （2時間） |
| 3 |
補グラフ、グラフの演算に関する概念を英語で学ぶ。
【事前学習】グラフの各種の不変量が補グラフ、直積などでどのように変化するのか調べる。 （2時間） 【事後学習】完全グラフの同形なグラフへの分解について調べる。 （2時間） |
| 4 |
次数列の概念とHavel-Hakimiの定理を英語で学ぶ。
【事前学習】英文プリントの22～26ページを読み、内容を理解する。 （2時間） 【事後学習】プリントにある次数列の判定問題を解く。 （2時間） |
| 5 |
Erdos-Gallaiの定理とirregular graphの非存在性を学ぶ。
【事前学習】英文プリントの26～28ページを読み、内容を理解する。 （2時間） 【事後学習】nearly-irregular graph の性質を調べる。 （2時間） |
| 6 |
グラフの次数に関する総合演習を行う。
【事前学習】プリントにあるやや複雑な次数列判定問題を解く。 （2時間） 【事後学習】2-switch の拡張を考える。 （2時間） |
| 7 |
グラフのウォーク、道、閉路といった概念を英語で学ぶ。
【事前学習】英文プリントの30～32ページを読み、内容を理解する。 （2時間） 【事後学習】プリントにある連結性に関する問題を解く。 （2時間） |
| 8 |
隣接行列の概念とその性質を英語で学ぶ。
【事前学習】英文プリントの32～35ページを読み、内容を理解する。 （2時間） 【事後学習】グラフを用いた行列のべき乗計算の練習をする。 （2時間） |
| 9 |
グラフの連結性、２頂点間の距離と言った概念を英語で学ぶ。
【事前学習】英文プリントの35～38ページを読み、内容を理解する。 （2時間） 【事後学習】プリントにある頂点の離心値に関する問題を解く。 （2時間） |
| 10 |
グラフの直径、半径、中心といった概念を英語で学ぶ。
【事前学習】英文プリントの38～41ページを読み、内容を理解する。 （2時間） 【事後学習】グラフから頂点、辺を除去した時の半径、直径の変化について考察する。 （2時間） |
| 11 |
グラフの連結性に関する総合演習を行う。
【事前学習】連結性に関するやや発展的な問題を解く。 （2時間） 【事後学習】2-連結グラフの性質に関するプリントの問題を解く。 （2時間） |
| 12 |
多重グラフの概念とその性質を英語で学ぶ。
【事前学習】英文プリントの45～46ページを読み、内容を理解する。 （2時間） 【事後学習】プリントの問題を通して、多重グラフと単純グラフの性質の違いを理解する。 （2時間） |
| 13 |
有向グラフの概念とその性質を英語で学ぶ。
【事前学習】英文プリントの47～50ページを読み、内容を理解する。 （2時間） 【事後学習】プリントにある問題を解くことにより、無向グラフと有向グラフの違いを理解する。 （2時間） |
| 14 |
有向グラフのに関する連結性の概念を学ぶ。
【事前学習】英文プリントの50～51ページを読み、内容を理解する。 （2時間） 【事後学習】有向グラフにおける連結性の定義にはいくつかあることを、プリントの問題を解くことを通して理解する。 （2時間） |
| 15 |
多重グラフと有向グラフに関する総合演習を行う。
【事前学習】プリントにある多重グラフの発展問題を解く。 （2時間） 【事後学習】プリントにある有向グラフの発展問題を解く。 （2時間） |
| その他 | |
|---|---|
| 教科書 | 教科書は使用しない。 |
| 参考書 | 使用しない |
| 成績評価の方法及び基準 | 授業参画度:ディスカッションを通して測られる事前準備状況と議論の深度、および発表の質で評価する。(100%) |
| オフィスアワー | 随時 Zoom によるオフィスアワーを設ける。参加希望者は電子メールにて希望日時を伝えアポイントを取ること。希望者にアクセス情報を伝える。 |