シラバスの詳細な内容を表示します。
→ 閉じる（シラバスの一覧にもどる）
| 開講年度 | 2018 年度 | |
|---|---|---|
| 開講区分 | 工学部情報工学科 ・専門教育 | |
| 受講対象学生 |
学部(学士課程) : 2年次 |
|
| 選択・必修 | 選択 選択科目 |
|
| 授業科目名 | オートマトン・形式言語理論 | |
| おーとまとん・けいしきげんごりろん | ||
| Automata and Formal Language Theory | ||
| 単位数 | 2 単位 | |
| 他学部・他研究科からの受講 |
|
|
| 市民開放授業 | 市民開放授業ではない | |
| 開講学期 |
後期 |
|
| 開講時間 |
火曜日 3, 4時限 |
|
| 開講場所 | ||
| 担当教員 | 太田 義勝 | |
| 授業の概要 | オートマトンとは電子回路（順序回路）とかコンピュータのもっとも単純な抽象的モデルである。またオートマトンは単に機械のモデルというだけでなく、計算機科学におけるいろいろな問題の理論的構造を表現したりシステムを形式化するのに用いられる。また、この理論は、言語処理などの形式言語理論、計算量理論、などの計算機科学のいろいろな分野の基礎理論である。 |
|---|---|
| 学習の目的 | |
| 学習の到達目標 | |
| ディプロマ・ポリシー |
|
| 授業の方法 | 講義 |
| 授業の特徴 | |
| 教科書 | 教科書：特に指定しない。 |
| 参考書 | 参考書： 言語理論とオートマトン（Hopcroft, Ullman著（野崎，木村訳），サイエンス社，1969） コンパイラの理論（大山口通夫，コロナ社，1989） |
| 成績評価方法と基準 | 出席は必要条件であり，2/3以上出席しなければならない．評価は，定期試験（100点）の点数で行い，60点以上を合格とする． |
| オフィスアワー | 授業終了後，教室又は情報工学科棟4階太田教員室で対応． 電子メールによる受付け可（E-mail:ohta@net.info.mie-u.ac.jp） |
| 受講要件 | |
| 予め履修が望ましい科目 | |
| 発展科目 | |
| 授業改善への工夫 | |
| その他 |
| キーワード | オートマトン，形式言語 |
|---|---|
| Key Word(s) | |
| 学習内容 | 第1回 概論 第2回 有限オートマトン，正規文法，正規表現 第3回 正規表現と有限オートマトンの関係，最簡形 第4回 有限オートマトンの等価性問題 第5回 プッシュダウンオートマトンと文脈自由（CF）文法 第6回 Chomsky標準形定理とGreibach標準形定理，ポンピング補題 第7回 プッシュダウンオートマトン（pda） 第8回 アルゴリズムと手続き，Postの対応問題 第9回 句構造文法とチューリング機械（１） 第10回 帰納的可算言語と帰納的言語 第11回 句構造文法とチューリング機械（２） 第12回 ２方向無限テープTM，２テープTM，決定性TMと非決定性TMの等価性 第13回 万能チューリング機械 第14回 停止問題 第15回 まとめ 第16回 定期試験 |
| 事前・事後学修の内容 |
| ナンバリングコード(試行) | EN-CMPS-2 |
|---|
※最初の2文字は開講主体、続く4文字は分野、最後の数字は開講レベルを表します。 ナンバリングコード一覧表はこちら