離散数学Ⅱ

科目区分	専門教育科目（情報）	対象学年(以上)	1年
科目名称	離散数学Ⅱ	単位数	2.00単位
講義題目	コンピュータのための数学(グラフと論理)	曜日・時限	月曜2限
担当教員	太田　淳	開講時期	2019年度後期
到達目標	情報科学の基礎となる重要な数学的概念である「グラフ」、「論理」、「数え挙げ」についての基礎を理解し、簡単な応用問題を解くことができること。
授業概要	離散数学Iに引き続き、情報数学の基礎となる数学的概念について解説する。まず、データなどの接続関係を表すことができ情報を取り扱う上で有用な概念であるグラフについて、その定義、性質、応用などを解説する。ついで数理論理学について解説する。最後にアルゴリズムの解析の手法として、漸化式の解法、数え挙げについて解説する。
授業計画	第1回グラフの基本的概念第2回グラフの連結性第3回木第4回グラフと行列第5回平面グラフ第6回グラフの彩色第7回二部グラフとマッチング第8回グラフ上の巡回第9回最短路問題第10回最大流問題第11回命題論理第12回述語論理第13回時相論理第14回関数の漸近的性質，漸化式の解法第15回数え挙げ定期試験
授業外学習	前回までの授業内容は理解しているものとして進めていきますので、復習をしっかりしておいてください。また、毎回宿題として演習問題を出します。
履修上の注意	関連科目：離散数学I、アルゴリズムとデータ構造I, II 受講要件：とくに定めない
成績評価の方法	評価基準：グラフ、数理論理学、漸化式、数え上げについて理解し、応用問題を解くことができること。評価方法：試験(80％)、演習(10%)、積極的な授業参加度(10%)を総合して評価する。
教科書	プリントを配布する。
参考書	守屋悦郎：“コンピュータサイエンスのための離散数学”，Information & Computing 61，サイエンス社，1992