文理学部シラバスTOP > 文理学部 > 総合 II 群 > 情報と数理
日本大学ロゴ

情報と数理

このページを印刷する

令和２年度以降入学者 情報と数理
教員名 齋藤明
単位数    2 学年 1～4 開講区分 文理学部
科目群 総合教育科目
学期 後期 履修区分
授業形態 対面授業
Blackboard ID 20233064
授業概要 駅にある路線図やコンピュータネットワークのように、点が線で結ばれたものをグラフとよぶ。グラフは情報科学の様々な局面で現れる重要な数路モデルである。この講義では、グラフに関する様々な話題を取り上げ解説する。あまり理論に深入りせず、工学的な応用に重点を置く。
授業のねらい・到達目標 ・グラフ理論の基礎的な諸概念と代表的なアルゴリズムを理解し、運用することができる。(A-3-1)
・グラフの基本的な概念を扱い、それを現実の問題に応用することができる。(A-3-1)
・最短路問題を解くことができるようになる。(A-4-1)
・ネットワークフローの問題を解くことができる。(A-5-1)

この科目は文理学部(学士(理学))のディプロマポリシーDP3及びカリキュラムポリシーCP3に対応している。
授業の形式 講義
授業の方法 (1) 授業の形式
板書とスライドにより基本事項を説明する。また適宜授業内課題を与える。さらに毎回の講義では授業外課題（宿題）も課す。演習問題プリント配布し、授業外課題はそのプロントの中から出題する。宿題は提出後２週間以内に採点し返却する。

(2) 対面授業に参加できない学生への代替方法
正当な理由で対⾯授業に参加できない場合、別途実施するオンライン授業（Zoom）への参加を認める。オンライン授業では事前に授業資料を渡し、対⾯授業とは別の時間枠で反転授業を⾏う。授業時間は受講者との協議の上で決めていく。
授業計画
1 グラフ理論への興味を持ってもらうため、パズルを２題ほど出題し、グラフを用いてそれらを解いてみる。(A-3-1)
【事前学習】インターネットなどで「グラフ」という言葉の使われ方を調べる。 （1時間）
【事後学習】演習問題プリントの1番（握手問題の発展）を解く。 （3時間）
【授業形態】対面授業
2 グラフの定義と基本的な用語を学ぶ。頂点、辺、同形といった概念を学習する。(A-3-1)
【事前学習】事前に公開される第２回講義資料を読み、分からないところを書き出しておく。 （1時間）
【事後学習】演習プリントの5番（グラフの位数）を解く、 （3時間）
【授業形態】対面授業
3 近傍と次数の概念を学ぶ。また握手定理とその証明を学ぶ。(A-3-1)
【事前学習】事前に公開される第３回講義資料を読み、分からないところを書き出しておく。 （1時間）
【事後学習】演習プリントの14番（次数列判定の計算問題）を解く。 （3時間）
【授業形態】対面授業
4 次数列の概念と、その判定方法である Havel-Hakimi の定理を学ぶ。(A-3-1)
【事前学習】事前に公開される第４回講義資料を読み、分からないところを書き出しておく。 （1時間）
【事後学習】演習プリントの15番（次数列の応用問題）を解く。 （3時間）
【授業形態】対面授業
5 道、閉路といった概念を学ぶ。またグラフの連結性の概念を学習し、連結グラフの性質を調べる。(A-4-1)
【事前学習】事前に公開される第５回講義資料を読み、分からないところを書き出しておく。 （1時間）
【事後学習】演習プリントの19番（連結性の概念）を解く。 （3時間）
【授業形態】対面授業
6 グラフの連結度、辺連結度の概念を学ぶ。特に連結度、辺連結度、最小次数に関する不等式を学習する。(A-4-1)
【事前学習】事前に公開される第６回講義資料を読み、分からないところを書き出しておく。 （1時間）
【事後学習】演習プリントの27番（連結度に関する問題）を解く。 （3時間）
【授業形態】対面授業
7 グラフの最短路問題と、その解法であるダイクストラ法を学ぶ。(A-4-1)
【事前学習】事前に公開される第７回講義資料を読み、分からないところを書き出しておく。 （1時間）
【事後学習】演習プリントの31番（ダイクストラ法の計算問題）を解く。 （3時間）
【授業形態】対面授業
8 第１回～第７回の内容に関する総合演習を行う。初めにテスト形式で演習を解いた後に、問題に対する解説を行う。
【事前学習】これまでに配布した演習の中で間違えたもの、理解不足を感じたものを解き直す。 （3時間）
【事後学習】講義の解説に従って、演習問題で間違えたもの、理解不足を感じたものを解き直す。 （1時間）
【授業形態】対面授業
9 木の定義を学び、その性質を調べる。またグラフの直径、半径、中心等の概念を学ぶ。(A-4-1)
【事前学習】事前に公開される第９回講義資料を読み、分からないところを書き出しておく。 （1時間）
【事後学習】演習プリントの34番（木とグラフの直径、半径に関する問題）を解く。 （3時間）
【授業形態】対面授業
10 探索木の概念を学び、深さ優先探索のアルゴリズムを学ぶ。(A-4-1)
【事前学習】事前に公開される第10回講義資料を読み、分からないところを書き出しておく。 （1時間）
【事後学習】演習プリントの34番（全域木を求める問題）を解く。 （3時間）
【授業形態】対面授業
11 ネットワークフローを学ぶ。特にネットワークの最大流と最小カットの定義を学習する。(A-5-1)
【事前学習】教科書 116～121 事前に公開される第11回講義資料を読み、分からないところを書き出しておく。を読み、理解できなかった部分をノートに書き出しておく。 （1時間）
【事後学習】演習プリントの34番（最大流を求める問題）を解く。 （3時間）
【授業形態】対面授業
12 最大流、最小カットを求めるアルゴリズムを学ぶ。(A-5-1)
【事前学習】事前に公開される第12回講義資料を読み、分からないところを書き出しておく。 （1時間）
【事後学習】演習プリントの35番（最大流を求める問題）を解く。 （3時間）
【授業形態】対面授業
13 グラフの平面性の概念を学び、オイラーの公式を学習する。(A-3-1)
【事前学習】事前に公開される第13回講義資料を読み、分からないところを書き出しておく。 （1時間）
【事後学習】演習プリントの35番（オイラーの公式）を解く。 （3時間）
【授業形態】対面授業
14 グラフの彩色を学ぶ。Brooks の定理とその証明に現れる彩色アルゴリズムの理解を目指す。(A-3-1)
【事前学習】事前に公開される第14回講義資料を読み、分からないところを書き出しておく。 （1時間）
【事後学習】演習プリントの37番（Brooksの定理）を解く。 （3時間）
【授業形態】対面授業
15 第9回～第14回の内容に関する総合演習を行う。初めにテスト形式で演習を解いた後に、問題に対する解説を行う。
【事前学習】これまでに配布した演習の中で間違えたもの、理解不足を感じたものを解き直す。 （2時間）
【事後学習】講義の解説に従って、演習問題で間違えたもの、理解不足を感じたものを解き直す。 （2時間）
【授業形態】対面授業
その他
教科書 使用しない
参考書 加納幹雄 『情報科学のためのグラフ理論』 朝倉書店 2001年 第1版
成績評価の方法及び基準 授業内テスト:第８、15回で実施する総合演習(70%)、毎回課す授業外演習の提出状況と内容(30%)
対面の総合演習に参加できなかった学生については、別途オンラインで総合演習を実施する。オンラインでの総合演習のの内容は、対面で行う総合演習の内容と異なる。
オフィスアワー 毎週火曜日 12:20～13:00 に研究室で行う。またメール（saitou.akira☆nihon-u.ac.jp）での質疑応答も受け付ける（☆は@に置き換えて下さい）。
備考 演習プリントは講義の進度や受講者の理解度に合わせて、作成する。そのため、上記の事後学習で指示した問題と実際に出題される問題の番号にずれが生じる可能性がある。事後学習で解くべき問題は毎回の講義で指示する。

↑このページのトップ