講義内容

平田のホームページへ

離散数学I

  1. 集合論の基礎
  2. 集合演算
  3. 命題論理の基礎
  4. 重要な論理式とその略記法
  5. 述語論理の基礎
  6. 関係の基礎
  7. 半順序関係
  8. 半順序関係と論理式
  9. 同値関係
  10. 関数
  11. 有限集合と無限集合
  12. 可算無限と非可算無限
  13. 数学的帰納法
  14. ハノイの塔とその計算量
  15. 中間レポートの解答

オートマトンと言語理論

  1. 準備(形式言語・文法・オートマトン理論の概要)
  2. 決定性有限オートマトン(DFA)
  3. 非決定性有限オートマトン(NFA)
  4. DFAとNFAの等価性
  5. 正則言語族の閉包性(1)和・積・差
  6. 正則言語族の閉包性(2)連接・Kleene閉包
  7. Nerodeの定理
  8. Nerodeの定理の応用と反復補題
  9. 最小状態DFA
  10. DFAの状態最小化手順
  11. 正則表現と出力付きオートマトン
  12. 文脈自由言語の性質
  13. 文脈自由文法の標準形
  14. プッシュダウンオートマトン
  15. レポート解答

人工知能論理

  1. コンピュータサイエンスと命題論理：アルゴリズムの計算量と充足可能性問題
  2. 命題論理：モデル論と証明論
  3. 命題論理：完全性定理
  4. コンピュータサイエンスと一階述語論理：アルゴリズムの存在性と普遍妥当性問題
  5. 一階述語論理：モデル論と証明論
  6. 一階述語論理：完全性定理
  7. コンピュータサイエンスと一階述語論理：アルゴリズムにおけるループ構造や計算複雑性・計算可能性の階層と一階述語論理の限量子
  8. コンピュータサイエンスと一階述語論理：計算複雑性と一階述語論理の有限モデル論
  9. 論理型プログラム：人工知能のためのプログラム言語
  10. 論理型プログラムの計算原理：単一化アルゴリズム
  11. 論理型プログラムの計算原理：導出原理
  12. 論理型プログラムのモデル論：エルブランモデル
  13. 論理型プログラムのモデル論：不動点と順序数冪
  14. 論理型プログラムの導出完全性：導出の宣言的意味論と操作的意味論
  15. 論理型プログラムの応用：人工知能における知識表現