授業科目名 離散数理
履修期 秋 2単位 履修基準年度 1年
担当者 西関 隆夫(NISHIZEKI TAKAO)
授業目的 / Course Objectives
離散数学は、情報科学における数学的な概念を記述し議論する際に必要となる基礎知識である。集合、関数、関係、組合せ論、グラフ理論を中心に授業を行う。多くの具体的な応用例を題材にして、離散数学の考え方、証明法を講義する。また、証明法とアルゴリズム設計との関係についても言及する。
到達目標 / Attainment Objectives
-
授業時間外の学習 (準備学習等について) / Study Required Outside of Class (Preparation etc.)
この科目は、論理回路、データ構造とアルゴリズム、数理論理学、数理計画法、最適化理論など、情報科学の多様な科目の基礎となっている。とくに2年生のグラフ・ネットワーク理論と連続しているので、両方を取ることが望ましい。
授業計画 / Class Overall Plan
1.序論:集合論、組合せ論、グラフ理論
2.グラフ理論の用語と基礎的事項
3.最短路
4.最小木
5.オイラー閉路
6.平面グラフ
7.グラフの彩色
8.集合と濃度
9.包含と排除の理
10.順序、半順序、同値関係
11.同値関係と分割
12.順列、組合せ、母関数
13.差分方程式とその解法
14.差分方程式のアルゴリズム解析への応用
15.演習
教科書 / Textbook(s)
斎藤・西関・千葉『離散数学』(朝倉書店 1989)。
参考文献 References Books
-
授業方法 / Method of Instruction
講義形式で行う
学生による授業評価の方法 / Course Evaluation by Students
ネット利用(所定のフォーマット)
成績評価 / Evaluation Criteria/Method
レポート課題と定期試験
備考 / Note
-
検索キーワード / Keywords
離散数学/集合/関数/関係/グラフ理論/ネットワーク理論/アルゴリズム/