離散数学の基礎勉強会

概要

離散数学(特にオートマトンと形式言語)について学びます。

メンバー

  • 小町
  • 立花
  • 平田
  • 大和田
  • 北川
  • 宮崎
  • 堺澤
  • 叶内

スケジュール

次回は2015年度以降の開催を予定しています。

過去ログ

  • 2014/07/18(金)14:00-15:30 2章演習残り全て
  • 2014/07/11(金)14:30-17:30 2章演習の2.1から2.8まで
  • 2014/07/04(金)13:00-16:30 2章本文
  • 2014/06/20(金)14:00-16:00 1章演習の1.22から1.30まで
  • 2014/06/13(金)14:00-16:00 1章演習の1.17から1.21まで
  • 2014/05/30(金)14:00-16:00 1章演習の1.7から1.16まで
  • 2014/05/09(金)14:00-16:00 本文1.4から1章演習の1.1から1.6まで
  • 2014/05/02(金)14:00-16:00 本文1.2.2から1.3まで
  • 2014/04/25(金)14:00-16:00 本文1章の最初から1.2.1まで
  • 2014/04/18(金)14:00-16:00 キックオフ、0章の本文と演習

分担

本文

  1. 正規言語(堺澤)
    1. 有限オートマトン(堺澤)
      1. 有限オートマトンの正式な定義(張)
      2. 有限オートマトンの例(張)
      3. 計算の正式な定義(叶内)
      4. 有限オートマトンの設計(叶内)
      5. 正規演算(平田)
    2. 非決定性(立花)
      1. 非決定性有限オートマトンの正式な定義(立花)
      2. NFAとDFAの等価性(宮崎)
      3. 正規演算の閉包性(大和田)
    3. 正規表現(北川)
      1. 正規表現の正式な定義(北川)
      2. 有限オートマトンとの等価性(塘)
    4. 非正規言語(寅)
      1. 正規言語に対するポンピング補題(寅)
  2. 文脈自由言語(堺澤)
    1. 文脈自由文法(堺澤)
      1. 文脈自由文法の正式な定義(塘)
      2. 文脈自由文法の例(塘)
      3. 文脈自由文法の設計(叶内)
      4. 曖昧さ(立花)
      5. Chomsky標準形(大和田)
    2. プッシュダウン・オートマトン(宮崎)
      1. プッシュダウン・オートマトンの正式な定義(宮崎)
      2. プッシュダウン・オートマトンの例(張)
      3. 文脈自由文法との等価性(北川)
    3. 非文脈自由言語(平田)
      1. 文脈自由言語に対するポンピング補題(寅)

演習問題

ホワイトボードに書くのに時間がかかる場合、資料をコピーして配布するか、Cyboze などに上げてください。

以下の順番でローテーション

第1章

  1. 寅 1.1, 1.11, 1.21
  2. 塘 1.2, 1.12, 1.22
  3. 宮崎 1.3, 1.13, 1.23
  4. 堺澤 1.4, 1.14, 1.24
  5. 北川 1.5, 1.15, 1.25
  6. 大和田 1.6, 1.16, 1.26
  7. 平田 1.7, 1.17, 1.27
  8. 叶内 1.8, 1.18, 1.28
  9. 張 1.9, 1.19, 1.29
  10. 立花 1.10, 1.20, 1.30

第2章
  1. 叶内
  2. 北川
  3. 立花
  4. 北川
  5. 平田
  6. 大和田
  7. 立花
  8. 叶内
  9. 平田
  10. 大和田
  11. 堺澤
  12. 宮崎
Comments