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

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

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

＜授業計画＞

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

1. グラフとは
2. グラフ理論における基本的な用語
3. 次数と近傍
4. グラフの連結性
5. 連結度と辺連結度
6. 最短経路問題
7. 木
8. グラフの全域木
9. ネットワークフロー (1)
10. ネットワークフロー (2)
11. グラフの平面性
12. マッチング

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

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

＜教科書＞

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

＜参考書＞

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

＜オフィスアワー＞

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

＜学生へのメッセージ＞

宿題は15分でできる程度を目安とし、期末試験では宿題の発展問題を出題する。すなわち毎回の宿題を解いていけば、それが自然に試験勉強につながるように配慮する。宿題をおろそかにせず、頑張って解いて欲しい。

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