離散構造

  [ GB10914,GB10924 ]
Discrete Structures
対象:1学年 開設学期:秋AB 曜日・時限:金3・4 単位数:2単位
担当教員:1,2クラス: 亀山幸義,海野広志, 3,4クラス: 長谷部浩二

概要

離散構造は記号により表現される概念の総称であり,論理,集合,関数,グラフ,代数系などを指す.離散構造の中から,コンピュータサイエンスを支える数学的概念として特に重要なものを取り上げ,基礎的な事項を学ぶ.取り上げる題材は,論理と証明,集合と関数,関係とグラフ,帰納法と帰納的定義などである.なお,講義内容に対する理解を深めるため,授業中に演習を行う.

学習・教育目標

コンピュータサイエンスにおいて必要とされる離散数学の基礎的な用語と概念を理解する.また,これを題材として,論理的思考,抽象化と形式化の手法,厳密な推論方法を理解する.

キーワード

記号論理,集合,関数,関係,グラフ,帰納的定義.

Keywords

Symbolic Logic, Set, Function, Relation, Graph, Inductive Definition.

時間割

講義内容
2週論理: 命題,論理記号,真理値表とその応用,限量子など.
2週集合と関数: 集合の構成法,集合の演算,包含関係,集合に関する推論,定義域・値域,単射・全射,合成関数,部分関数など.
2週関係とグラフ:二項関係,関係の性質,順序,同値関係,有向グラフ,無向グラフなど.
2週帰納: 帰納的定義,様々なデータ構造,帰納法を使った証明など.
2週情報科学における離散構造の応用,その他の話題.

教材

授業の情報はウェブページに掲載する。

参考書籍

離散数学入門 (守屋悦朗 著,サイエンス社,2005年)
Discrete Structures, Logic, and Computability, 2ndEdition (James L. Hein, Jones and BartlettPublishers, 2002)
独習 コンピュータ科学基礎I 離散構造 (Hein著,神林訳,翔泳社, 2011年) [上記の本の翻訳]
情報基礎数学(佐藤泰介ら著,昭晃堂,2007年)

成績評価

出席,演習,期末試験により評価する.

教員メールアドレス

亀山: kamの後に@cs.tsukuba.ac.jp
長谷部: hasebeの後に@cs.tsukuba.ac.jp
海野: uhiroの後に@cs.tsukuba.ac.jp

講義のWebページ

1,2クラス:http://logic.cs.tsukuba.ac.jp/~kam/discrete/
3,4クラス:学習管理システム(manaba)上に開設する.

オフィスアワー

初回の授業において連絡する.