離散数学

科目名
Course Title
授業コード 単位数 配当年次 開講期間
Term
科目分類 ナンバリング
コード
曜日
コマ
教室 担当教員氏名
Instructor
離散数学
Discrete Mathematics
B200180001 2 2 前期授業 専門科目 BEPRI2207-J1 月3 A5-122 宇野 裕之

オフィスアワー

(宇野) 月 16:15~17:15

授業目標

現代のコンピュータ・サイエンスを理解する上では不可欠な素養である離散数学であるが,その内容は広範であるにもかかわらず他の基本的な数学分野とは異なり初年時から時間をかけて取り扱われることがない.そこで本講義では,離散数学がカバーするトピックの中から,あらゆる対象の数学的な議論に不可欠な集合と論理から始め,高年次で選択する専門分野にかかわらす共通に必要性が高い重要なトピックを中心に,基礎的な概念を理解し習得することを目指す.

教科書

指定しません.

参考書

・松原良太ほか.離散数学.オーム社 (2010).
他の参考書は講義中にも紹介予定.

授業時間外の学習(準備学習等について)

予習よりも毎回の講義の復習に十分な時間を費やしてください.

授業の概要

おもに情報工学分野で講義されるあらゆる科目において必要となる離散数学の基礎的事項について講義する.まず,数学を記述し議論するための言語である集合と論理から始め,写像や関係,グラフなどの離散構造を説明する.さらに命題論理,述語論理,数学的帰納法と再帰的定義などを講義する.レポートや小テストを実施することがある.

授業計画

(1) 集合と写像(関数)
(2) 命題と論理
(3) 関係
(4) 再帰と帰納法
(5) 数え上げ
*** [復習]
(6) グラフの定義
(7) グラフの基本的性質と特別なグラフ
(8) グラフの連結性と周遊性
(9) 木と有向木(CSへの応用)
(10) 木と距離の最適化(最小全域木,最短路)
(11) グラフの平面性
*** [復習]
(12) 代数系
(13) ブール代数
(14) 離散確率

成績評価

より専門的な科目を理解し修得するうえで共通に必要な基礎的な概念を十分に理解することを最低限の目標とする.具体的には,命題,論理,集合,関係,写像,グラフなどであり,それに加えて基本的な証明ができることも必要である.それらを達成した場合に合格となる.