GB21601 オートマトンと形式言語

2.0 単位, 3・4 年次, 春AB 火5,6
亀山 幸義

授業概要

オートマトンと形式言語の基礎理論を学習する。取り上げる話題は、有限オートマトンと正規言語、プッシュダウンオートマトンと文脈自由言語、チューリング機械と決定可能性、チャーチの提唱などである。

備考

定員100名、定員を越える時は、授業ホームページ記載の方法で選抜するのでその指示に従うこと。
GC50201と同一。

授業形態

講義

学位プログラム・コンピテンスとの関係

・専門コンピテンス
2. ソフトウエアサイエンス分野の専門能力

授業の到達目標(学修成果)

計算モデルの表現手法として、オートマトンと形式言語に基づく方法を理解する。
有限オートマトンと正規言語、プッシュダウンオートマトンと文脈自由文法の対応関係を理解する。
チューリング機械と計算可能性、決定問題の概念を理解する。

キーワード

有限オートマトン, 正規言語, プッシュダウンオートマトン, 文脈自由言語, チューリング機械, 計算可能性, 決定問題

授業計画

履修条件

集合、関係、数学的帰納法など、離散数学(情報数学)の基礎的な知識を持っているか、自習する必要がある。

成績評価方法

今年度はオンライン授業のため、当初の成績評価方法から変更し、毎週の演習レポート70%程度、期末レポート30%程度で成績を評価する。

学修時間の割り当て及び授業外における学修方法

次回の授業範囲を予習し,専門用語の意味などを理解しておくこと。また、演習の後は、演習内容の復習をしておくこと。

教材・参考文献・配付資料等

オフィスアワー等(連絡先含む)

その他(受講生にのぞむことや受講上の注意点等)

講義資料等は manaba のこの授業のページ (https://manaba.tsukuba.ac.jp/ct/course_1322210) に置く。

なお、manabaがシステムダウンしたり過負荷のときは、バックアップの情報を http://www.cs.tsukuba.ac.jp/~kam/lecture/automaton2020/ に置くのでそちらを参照してほしい。

他の授業科目との関連

ティーチングフェロー(TF)・ティーチングアシスタント(TA)

TA1名有 (TAと教員の二人に届くメールアドレスとして automaton@logic.cs.tsukuba.ac.jp を用意している。)