離散数学（Discrete Mathematics）[1F01]

＜授業のねらい及び具体的な達成目標＞

離散数学は情報工学の基礎をなす数学である。本講義では、離散数学の中でも重要な学問であるグラフ理論について、数多くの例題を交えながら平易に解説を行う。理論に偏ることなく、アルゴリズムや応用についても十分な解説を行う予定である。

＜授業計画及び準備学習＞

以下の内容について解説する。いずれの内容についても、現実の問題への応用例を挙げて、常に応用を意識するようにする。

1. グラフとは
2. グラフ理論における基本的な用語
3. 次数と近傍
4. 次数列
5. グラフの道と閉路
6. グラフの連結性
7. 連結度と辺連結度
8. 最短経路問題
9. 木
10. グラフの全域木
11. ネットワークフロー (1)
12. ネットワークフロー (2)
13. グラフの平面性
14. マッチング
15. 学習成果の確認（試験）

＜成績評価方法及び水準＞

毎回宿題を課す。宿題の提出状況を最大20点、提出された宿題の質を最大10点、期末試験の成績を最大70点として計算する。この合計値が60点以上であった者を合格とする。

＜教科書＞

「情報科学のためのグラフ理論」 加納幹雄著（朝倉書店）

＜参考書＞

「離散構造」 根上生也著（共立出版）

＜オフィスアワー＞

質問は講義時間中に受け付ける。またメールによる質問も随時受け付ける。メールアドレスは授業初回に公開する。

＜学生へのメッセージ＞

宿題は60分以内で程度を目安とし、期末試験では宿題の発展問題を出題する。すなわち毎回の宿題を解いていけば、それが自然に試験勉強につながるように配慮する。宿題をおろそかにせず、頑張って解いて欲しい。また毎回の授業の前に教科書の対応するところを読んでおくこと。

このページの著作権は学校法人工学院大学が有しています。 Copyright(c)2010 Kogakuin University. All Rights Reserved.