2024年度/3T13230001 (市大)

【集中講義】計算理論 <後期>

計算とは何かを理解するために計算の数学的モデルについて述べる。有限状態オートマトンと正則言語をはじめ，非決定性有限オートマトン，プッシュダウンオートマトン，チューリングマシン，決定不能性と計算複雑性の講義を行う。

担当教員氏名

蔡 凱

科目ナンバリング

TNP102202 (市大)

授業管轄部署

工学部

授業形態

講義

開講キャンパス

遠隔用

開講区分

集中講義

配当年次

2年 (市大)

注意: 配当年次は学部・学科によって異なる場合があるので、UNIPAで確認してください。

単位数

2単位 (市大)

注意: 実際の単位数は学部・学科によって異なる場合があるので、必ずUNIPAで確認してください。

到達目標

計算とは何かを説明できる。特に，オートマトンと形式言語のコンセプトを説明できる。また，計算できるものと計算できないものがあり，計算機には根源的な限界があることを説明できる。

各授業回の説明

授業	授業内容	事前・事後の学習内容
第1回	計算理論の導入：計算とは何か・計算の数学モデル・計算理論の応用	授業後，学習内容を理解するために資料を復習すること。
第2回	形式言語：アルファベット，文字列，言語	授業前，前回の講義内容を復習すること。 授業後，学習内容を理解するために資料を復習すること。
第3回	有限状態オートマトン：定義と状態遷移図，オートマトンの形式言語	授業前，前回の講義内容を復習すること。 授業後，学習内容を理解するために資料を復習すること。
第4回	非決定性有限オートマトン： 定義とsubset construction	授業前，前回の講義内容を復習すること。 授業後，学習内容を理解するために資料を復習すること。
第5回	正則表現 ，正則言語	授業前，前回の講義内容を復習すること。 授業後，学習内容を理解するために資料を復習すること。
第6回	正則言語のpumping lemma	授業前，前回の講義内容を復習すること。 授業後，学習内容を理解するために資料を復習すること。
第7回	文脈自由文法，文脈自由言語，プッシュダウンオートマトン	授業前，前回の講義内容を復習すること。 授業後，学習内容を理解するために資料を復習すること。
第8回	文脈自由言語のpumping lemma	授業前，前回の講義内容を復習すること。 授業後，学習内容を理解するために資料を復習すること。
第9回	チューリングマシン：導入と定義	授業前，前回の講義内容を復習すること。 授業後，学習内容を理解するために資料を復習すること。
第10回	チューリング受理性言語，チューリング決定性言語	授業前，前回の講義内容を復習すること。 授業後，学習内容を理解するために資料を復習すること。
第11回	アルゴリズム，決定可能性	授業前，前回の講義内容を復習すること。 授業後，学習内容を理解するために資料を復習すること。
第12回	決定不能性：チューリングマシンの限界	授業前，前回の講義内容を復習すること。 授業後，学習内容を理解するために資料を復習すること。
第13回	計算複雑性	授業前，前回の講義内容を復習すること。 授業後，学習内容を理解するために資料を復習すること。
第14回	PとNP問題	授業前，前回の講義内容を復習すること。 授業後，学習内容を理解するために資料を復習すること。
第15回	NP完全問題	授業前，前回の講義内容を復習すること。 授業後，学習内容を理解するために資料を復習すること。
第16回	試験

成績評価方法

到達目標の達成度について評価のための試験を行う．総合100 点満点に対する 60 点以上を合格，60 点未満を不合格とする．

履修上の注意

情報数学の知識を前提とする。

教科書

なし

Loading...

参考文献

1. M. Sipser, "Introduction to the Theory of Computation", Course Technology, 2012. 2. J.E. Hopcroft, R. Motwani, J.D. Ullman, "Introduction to Automata Theory, Languages, and Computation", Addison Wesley, 2006.

オフィスアワー

- 外部公開シラバスのためデータがありません / Please use UNIPA syllabus -

教員への連絡方法（メールアドレス等）

- 外部公開シラバスのためデータがありません / Please use UNIPA syllabus -

その他

本年度は集中講義とします．