2015年度 グラフとオートマトン理論 I118

シラバス

担当教員

東條 敏・佐野勝彦

佐野は前半の集合論とグラフ理論の部分を担当します．

目的

点とそれらを線で結んだ辺からなる構造をグラフという。また状態遷移を表すグラフの一種はオートマトンと呼ばれる。これらはプログラムのデータや振る舞い、計算過程を数学的に表現する重要な概念であり、アルゴリズム論やモデル検査、コンパイラ構成などの分野の基礎になっている。本科目は、グラフの基本概念と性質・アルゴリズム、およびオートマトンと形式言語の関係を理解をもって達成目標とする。

内容

講義の前半は、数学的基礎（特に集合）を振り返ったのち、グラフの基本概念、走査アルゴリズムや組合わせ的性質を紹介する。後半は、オートマトン（有限状態オートマトン・プッシュダウンオートマトン）と受理言語（正則・文脈自由言語）の関係、それらの性質と限界（閉包性・反復補題・Myhill-Nerode の定理）を議論する。

教科書

1. 「Automata and Computability」, Dexter Kozen著，Springer, 1997年．

参考書

1. 「How To Prove It: A Structured Approach (2nd Edition)」，D.J. Velleman著，Cambridge University Press，2006年．
2. 「グラフ理論入門」，R.J. ウィルソン著（西関 隆夫，西関 裕子訳）, 近代科学社，2001年．
3. 「オートマトン 言語理論 計算論I（第2版）」 ，J. ホップクロフト・R. モトワニ・J. ウルマン著（野崎・町田・高橋・山崎訳），サイエンス社，2003年．

集合と証明の入門書として [1]、また講義では扱わないより進んだグラフ理論の内容については [2] を推薦する。ただし、 [2] は集合論の知識を必要とする。

講義計画

1. 集合（1）（集合．関係）
2. 集合（2）（関数，逆関数，単射と全射）
3. グラフ（1）（無向グラフ，有向グラフ）
4. グラフ（2）（オイラーグラフ，ハミルトングラフ，木構造）
5. 正規文法と有限オートマトン（1）（有限列，決定性／非決定性有限オートマトン）
6. 正規文法と有限オートマトン（2）（サブセット構成，イプシロン遷移）
7. 演習と中間試験
8. 正規文法と有限オートマトン（3）（正規表現，有限オートマトンとの同棲性）
9. 正規文法と有限オートマトン（4）（反復補題，最小化）
10. 正規文法と有限オートマトン（5）（Myhill-Nerode の定理）
11. 文脈自由文法とプッシュダウンオートマトン（1）（文脈自由文法，文脈自由言語）
12. 文脈自由文法とプッシュダウンオートマトン（2）（チョムスキー標準形，反復補題）
13. 文脈自由文法とプッシュダウンオートマトン（3）（グライバッハ標準形，オートマトンの構成）
14. 文脈自由文法とプッシュダウンオートマトン（4）（受理の同等性）
15. 演習と試験

成績評価の方法

中間・期末試験の結果による．

講義時間・教室

火曜2時限，金曜日1時限・情報科学研究科，I2講

オフィスアワー

金曜日3時限・情報科学研究科I2講

授業の予定・記録・連絡

2015/04/24 (金)

• 第5回目はハミルトングラフの応用と木構造について説明しました．
  • 講義スライド（第5回）
• 13:30 からのOHではグラフ理論と集合論について演習を行いました．
  • 演習で行った問題を集めたスライド: 第3回OHスライド
  • 3頁目の演習問題の (2-7) は全射の仮定無しで証明できるので仮定を落としました．(2015/04/24)

2015/04/21 (火)

• 第4回目はオイラーグラフ・ハミルトングラフについて説明しました．
  • 講義スライド（第4回）

2015/04/17 (金)

• 第2回目の残りと無向グラフと有向グラフについて説明しました．
  • 講義スライド（第3回）
• 13:30 からのOH では第2回目と第3回目の内容について演習を行いました．
  • 演習で行った問題を集めたスライド: 第2回OHスライド

2015/04/14 (火)

• 特殊な関係（同値関係・順序・関数）について説明しました．
  • 講義スライド（第2回）
  • 一番最後の頁の演習問題の (2-7) は全射の仮定無しで証明できるので仮定を落としました．(2015/04/24)
• 授業の最後に, 先週のOHで解いた（解く予定だった）演習問題の解答をTAの野村君に配布してもらいました．

2015/04/10 (金)

• 集合・関係の基本的な概念について説明する予定です．
  • 講義スライド（第1回） 誤植訂正済 (2015/04/10)
• 13:30 からの OH ではTAの野村尚新君に演習をやってもらう予定です．
• 集合の部分についての参考書については次を挙げておきます．
  • 志賀浩二『集合への30講』朝倉書店, 1988.
  • 小野寛晰『情報代数』共立出版, 1994.
• 「集合と位相」といったタイトルの書籍の集合部分のみを参照するのもお勧めです。例えば：
  • 松坂和夫『集合・位相入門』岩波書店, 1968.

Katsuhiko SANO

Last Revised: 2015/04/24.