| 授業科目名（和文） ［Course］ |
離散数学 |
| 授業科目名（英文） ［Course］ |
Discrete Mathematics |
| 学部（研究科） ［Faculty］ |
情報工学部 |
| 学科（専攻） ［Department］ |
情報通信工学科 |
| 担当教員（○：代表教員） [Principle Instructor(○) and Instructors] |
○小野 孝男 自室番号（2608）、電子メール（onotakao**c.oka-pu.ac.jp） ※利用の際は,** を @に置き換えてください |
| 単位数 ［Point(Credit)］ |
後期 2単位 |
| 対象学生 ［Eligible students］ |
情報工学部情報通信工学科 1年次生 |
| 授業概略と目標 ［Course description and Objects］ |
コンピュータサイエンスにおける基礎的な数学知識として，集合と数理論理学を確認する．また，応用上重要なモデルである「グラフ」の概略を理解するとともに，「計算」の概念としてのオートマトンと形式言語理論の基本的な枠組みについて学ぶ． |
| 到達目標 ［Learning Goal］ |
1. 集合とそれに基づく関係，関数の概念を理解する． 2. 数理論理学の基本的な知識を身につける. 3. グラフ理論の基礎として，各種のグラフやネットワークアルゴリズムを学ぶ． 4. オートマトンと形式言語理論の基礎を理解する． |
| 授業計画とスケジュール ［Course schedule］ |
1. 集合 ?講義全体の概要について簡単に触れるとともに，数学の基礎をなす集合についてその記法と演算を確認する． 2. 関係 ?集合を用いて「関係」の概念を定義し，その性質と「順序関係」，「同値関係」という概念を理解する． 3. 関数 ?集合を用いてより形式的に「関数」を定義する．また，離散数学における重要な性質である全射?単射?全単射と逆関数について論じる． 4. 命題論理 ?数理論理学におけるもっとも基礎的な分野である命題論理を学ぶ． 5. 述語論理 ?単純な例によって命題論理では日常的な表現ですら扱えないことを示し，発展的な論理体系の 1つである述語論理の基礎を学ぶ． 6. ブール代数 ?集合と命題論理の類似性から，抽象的な代数系である「ブール代数」を考えることでより統一的に理解できることを示す． 7. ブール表現と論理回路 ?現在のコンピュータのハードウェアは論理回路により論理演算を電気的に行っている．そこで，離散数学という立場から論理回路の基礎を学ぶ． 8. グラフの定義 ?「もの」と「もの」との関係を表す「グラフ」の概念を紹介し，その基本的な性質を理解する． 9. さまざまなグラフ ?理論上，あるいは応用上重要ないくつかのグラフについてその特徴を示す． 10. 木 ?「木」は非常に特殊なグラフであり，応用上も非常に重要である．そこで，木とその性質について理解するとともに，木やより一般のグラフについてすべての頂点を列挙する方法を知る． 11. 有向グラフとネットワーク ?辺に向きのあるグラフである有向グラフについて学ぶ．また，グラフの応用であるネットワークにおける基本的な問題である最短経路問題とそのアルゴリズムを理解する． 12. チューリング機械 ?コンピュータにおける「計算」を数学的に扱うモデルであるチューリング機械を学ぶ． 13. 有限オートマトンと正規表現 ?チューリング機械は非常に強力である反面扱いづらい点も多い．そこで，より簡略化したモデルである有限オートマトンと，対応する正規言語?正規表現について理解する． 14. 文脈自由文法とプッシュダウンオートマトン ?形式言語理論における「文法」を紹介し，その 1つの例として文脈自由文法を理解する．また，対応するオートマトンであるプッシュダウンオートマトンを学ぶ． 15. 講義のまとめ ?講義全体のまとめとして概略を簡単におさらいする． |
| 成績評価方法と基準 ［Grading policy (Evaluation)］ |
期末試験 (70 %) とレポート (30 %) により総合的に評価する． |
| 教科書 ［Textbook］ |
教科書：柴田正憲，浅田由良，「情報科学のための離散数学」，コロナ社 各回の講義内容の抜粋を資料として配布する． |
| 自主学習ガイド及び キーワード ［Self learning］ |
各回の授業終了時に次回の講義内容を予告するので，該当範囲に目を通しておくこと．また，各自で教科書の問題を解いて理解を深めるようにしてほしい． キーワード：離散数学，数理論理学，グラフ理論，計算可能性理論，形式言語理論 |
| 開講年度 ［Year of the course］ |
28 |