離散構造   [ GB10914,GB10924 ] Discrete Structures
対象：1学年	開設学期：第3学期	曜日・時限：金3・4	単位数：2単位
担当教員：1,2クラス: 亀山幸義, 3,4クラス: 長谷部浩二

概要

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

学習・教育目標

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

キーワード

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

Keywords

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

時間割

週	講義内容
１．５週	論理： 命題，論理記号，真理値表, 基本的な証明技法，限量子 など。
１．５週	集合： 集合の構成法，集合の演算，包含関係，集合に関する推論 など。
１．５週	関数： 定義域・値域，単射・全射，合成関数，部分関数 など。
１．５週	関係： 二項関係，関係の性質，順序、同値関係 など
１．５週	グラフと木： 有向グラフ，無向グラフ，木 など
１．５週	帰納： 帰納的定義，様々なデータ構造，帰納法を使った証明 など
１週	その他：コンピュータサイエンスにおける離散構造　など

教材

講義ノートを Web上に公開する．

参考書籍

離散数学入門 （守屋悦朗 著、サイエンス社、2005年）
工学基礎：　離散数学とその応用（徳山豪 著、数理工学社、2002年）
情報基礎数学 (佐藤泰介ら著、昭晃堂、2007年）
Discrete Structures, Logic, and Computability, 2ndEdition (James L. Hein, Jones and BartlettPublishers, 2002)

成績評価

出席，演習，期末試験により評価する．

教員メールアドレス

亀山: kamの後にアットマーク，その後にｃｓ．ｔｓｕｋｕｂａ．ａｃ．ｊｐ

講義のWebページ

http://logic.cs.tsukuba.ac.jp/~kam/discrete/

オフィスアワー

亀山: 金11:00〜12:00, 総合研究棟B-1008