文理学部シラバスTOP > 文理学部 > 情報科学科 > 情報科学講究２
日本大学ロゴ

情報科学講究２

このページを印刷する

令和２年度以降入学者 情報科学講究２
令和元年度以前入学者 情報科学講究２
教員名 齋藤明
単位数    2 学年    3 開講区分 文理学部
科目群 情報科学科
学期 後期 履修区分 必修
授業の形態 対面授業
BlackBoard コースID：20224407
授業概要 グラフ理論に関する論文講読
授業のねらい・到達目標 「情報科学講究１」に引き続き、配布プリント及び論文の輪読を通して発想と論理の力を養う。
題材はグラフ理論から選ばれることが多くなる。受講者は４年次の卒業研究を進めるための基礎的な力をつけことができる。

この科目は文理学部(理学)のディプロマポリシー DP1-8及びカリキュラムポリシー CP1-8に対応している。
・経験や学修から得られた豊かな情報科学の知識と教養に基づいて，自己の倫理観を倫理的な課題に適用することができる。(A-1-3)
・世界諸国の歴史や政治，経済，文化，価値観，信条などの背景を理解し，国際社会が直面している問題を情報科学の視点から説明することができる。(A-2-3)
・仮説に基づく課題や問題を提示し，客観的な情報を基に，論理的・批判的に考察できる。(A-3-3)
・問題を分析し，複数の解決策を提示した上で，問題を解決することができる。(A-4-3)
・責任と役割を担い，新しい問題に取り組む意識を持ち，そのために必要な情報科学の知識・情報を収集することができる。(A-5-3)
・さまざまな人々とのコミニュケーションを通じて相互の意思伝達を自由かつ確実に行い，他者との良好な関係を確立することができる。(A-6-3)
・集団の活動において，より良い成果を上げるために，指導者として他者と協働し，作業を行うことができる。(A-7-3)
・学修状況を自己分析し，その成果を評価することができる。(A-8-3)
授業の方法 (1) 授業の形式：【講義・演習】
「情報科学講究１」と同じく、配付プリントの輪読とプログラム実習を行う。
また卒業研究の大まかなテーマに関する解説を行い、予備的な学習を進める。

(2) 対⾯授業に参加できない学⽣への代替⽅法、要件
対⾯授業に参加できない場合、以下の要件を満たす学⽣は、Zoom での参加を認める。
オンライン授業への参加を認める要件︓学部の⽅針に従う。
オンライン授業の⽅法︓Zoom で参加し、BlackBoard に配信する課題を提出する。
履修条件 学科内規による。
授業計画
1 補グラフ、グラフの演算に関する概念を英語で学ぶ。【対面】(A-3-3, A-5-3, A-6-3)
【事前学習】配布する英文プリントの16～18ページを読み、内容を理解する。 （2時間）
【事後学習】グラフの直積に関する問題を解く。 （2時間）
2 グラフの基本的な性質に関する総合演習を行う。【対面】(A-3-3, A-5-3, A-6-3)
【事前学習】２部グラフ、補グラフなどに関するプリント内の問題を解く。 （2時間）
【事後学習】自己補グラフに関する発展問題を解く。 （2時間）
3 補グラフ、グラフの演算に関する概念を英語で学ぶ。【対面】(A-3-3, A-5-3, A-6-3)
【事前学習】グラフの各種の不変量が補グラフ、直積などでどのように変化するのか調べる。 （2時間）
【事後学習】完全グラフの同形なグラフへの分解について調べる。 （2時間）
4 次数列の概念とHavel-Hakimiの定理を英語で学ぶ。【対面】(A-3-3, A-5-3, A-6-3)
【事前学習】英文プリントの22～26ページを読み、内容を理解する。 （2時間）
【事後学習】プリントにある次数列の判定問題を解く。 （2時間）
5 Erdos-Gallaiの定理とirregular graphの非存在性を学ぶ。【対面】(A-3-3, A-5-3, A-6-3)
【事前学習】英文プリントの26～28ページを読み、内容を理解する。 （2時間）
【事後学習】nearly-irregular graph の性質を調べる。 （2時間）
6 グラフの次数に関する総合演習を行う。【対面】(A-1-3, A-2-3, A-4-3, A-6-3, A-7-3, A-8-3)
【事前学習】プリントにあるやや複雑な次数列判定問題を解く。 （2時間）
【事後学習】2-switch の拡張を考える。 （2時間）
7 グラフのウォーク、道、閉路といった概念を英語で学ぶ。【対面】(A-3-3, A-5-3, A-6-3)
【事前学習】英文プリントの30～32ページを読み、内容を理解する。 （2時間）
【事後学習】プリントにある連結性に関する問題を解く。 （2時間）
8 隣接行列の概念とその性質を英語で学ぶ。【対面】(A-3-3, A-5-3, A-6-3)
【事前学習】英文プリントの32～35ページを読み、内容を理解する。 （2時間）
【事後学習】グラフを用いた行列のべき乗計算の練習をする。 （2時間）
9 グラフの連結性、２頂点間の距離と言った概念を英語で学ぶ。【対面】(A-3-3, A-5-3, A-6-3)
【事前学習】英文プリントの35～38ページを読み、内容を理解する。 （2時間）
【事後学習】プリントにある頂点の離心値に関する問題を解く。 （2時間）
10 グラフの直径、半径、中心といった概念を英語で学ぶ。【対面】(A-3-3, A-5-3, A-6-3)
【事前学習】英文プリントの38～41ページを読み、内容を理解する。 （2時間）
【事後学習】グラフから頂点、辺を除去した時の半径、直径の変化について考察する。 （2時間）
11 グラフの連結性に関する総合演習を行う。【対面】(A-3-3, A-5-3, A-6-3)
【事前学習】連結性に関するやや発展的な問題を解く。 （2時間）
【事後学習】2-連結グラフの性質に関するプリントの問題を解く。 （2時間）
12 多重グラフの概念とその性質を英語で学ぶ。【対面】(A-3-3, A-5-3, A-6-3)
【事前学習】英文プリントの45～46ページを読み、内容を理解する。 （2時間）
【事後学習】プリントの問題を通して、多重グラフと単純グラフの性質の違いを理解する。 （2時間）
13 有向グラフの概念とその性質を英語で学ぶ。【対面】(A-3-3, A-5-3, A-6-3)
【事前学習】英文プリントの47～50ページを読み、内容を理解する。 （2時間）
【事後学習】プリントにある問題を解くことにより、無向グラフと有向グラフの違いを理解する。 （2時間）
14 有向グラフのに関する連結性の概念を学ぶ。【対面】(A-3-3, A-5-3, A-6-3)
【事前学習】英文プリントの50～51ページを読み、内容を理解する。 （2時間）
【事後学習】有向グラフにおける連結性の定義にはいくつかあることを、プリントの問題を解くことを通して理解する。 （2時間）
15 多重グラフと有向グラフに関する総合演習を行う。【対面】(A-1-3, A-2-3, A-4-3, A-6-3, A-7-3, A-8-3)
【事前学習】プリントにある多重グラフの発展問題を解く。 （2時間）
【事後学習】プリントにある有向グラフの発展問題を解く。 （2時間）
その他
教科書 なし。
参考書 なし。
成績評価の方法及び基準 授業参画度:ディスカッションを通して測られる事前準備状況と議論の深度、および発表の質で評価する。(100%)
オフィスアワー 毎週⽕曜⽇ 12:20〜13:00 に研究室で⾏う。またメール（saitou.akira@nihon-u.ac.jp）での質疑応答も受け付ける。

↑このページのトップ