|
授業科目： 離散構造 （２単位） Discrete Structures |
対象： １学年 | |
|---|---|---|
| 第３学期 | 曜・時： 金４・５ | 担当教官: 亀山幸義，満保雅浩 |
週別授業計画
教材：
講義ノートを Web上に公開する．
概要：
離散構造は，記号により表現される概念の総称であり， 論理，集合，関数，グラフ，代数系などを指す． 離散構造の中から， コンピュータサイエンスを支える数学的概念として特に重要なものを取り上げ， 基礎的な事項を学ぶ． 取り上げる題材は， 論理と証明， 集合と関数， 関係とグラフ, 帰納法と帰納的定義などである． なお，講義内容に対する理解を深めるため， 授業中に演習を行う．
学習・教育目標：
コンピュータサイエンスにおいて必要とされる離散数学の 基礎的な用語と概念を理解する． また，これを題材として，論理的思考，抽象化と形式化の手法， 厳密な推論方法を理解する．
授業計画：
| 週 | 講義内容 |
|---|---|
| 第1-2週 | 論理： 命題，論理記号，真理値表, 基本的な証明技法，限量子 など |
| 第3-4週 | 集合： 集合の構成方法，集合の演算，包含関係，集合に関する推論 など |
| 第5週 | 関数： 定義域・値域，単射・全射，部分関数 など |
| 第6週 | 関係： 二項関係，関係の性質，関係の演算 など |
| 第7-8週 | グラフと木： 有向グラフ，無向グラフ，木 など |
| 第9-10週 | 帰納： 帰納的定義，様々なデータ構造，帰納法を使った証明 など |
参考書等：
コンピュータサイエンスのための離散数学 （守屋悦朗著，サイエンス社）
Discrete Structures, Logic, and Computability,
2nd Edition (James L. Hein, Jones and Bartlett Publishers)
予備知識・前提条件：
特になし
オフィスアワー：
亀山: 金11:00〜12:30, 総合研究棟B-1008
満保: 金11:00〜12:30, F棟833号室
成績評価：
出席，授業中に実施する演習， 中間試験，学期末試験により評価する．
講義のホームページ：
http://logic.cs.tsukuba.ac.jp/~kam/discrete/
教官メールアドレス：
亀山: kamの後にアットマーク，その後に ｃｓ．ｔｓｕｋｕｂａ．ａｃ．ｊｐ
満保: mamboの後にアットマーク，以後，亀山と同一