三重大学ウェブシラバス


シラバス表示

 シラバスの詳細な内容を表示します。

→ シラバスの一覧にもどる

科目の基本情報

開講年度 2017 年度
開講区分 工学部情報工学科 ・専門教育
受講対象学生 学部(学士課程) : 2年次
選択・必修 選択
選択科目
授業科目名 オートマトン・形式言語理論
おーとまとん・けいしきげんごりろん
Automata and Formal Language Theory
単位数 2 単位
他学部・他研究科からの受講
市民開放授業 市民開放授業ではない
開講学期

後期

開講時間 火曜日 3, 4時限
開講場所

担当教員 太田 義勝

学習の目的と方法

授業の概要 オートマトンとは電子回路(順序回路)とかコンピュータのもっとも単純な抽象的モデルである。またオートマトンは単に機械のモデルというだけでなく、計算機科学におけるいろいろな問題の理論的構造を表現したりシステムを形式化するのに用いられる。また、この理論は、言語処理などの形式言語理論、計算量理論、などの計算機科学のいろいろな分野の基礎理論である。
学習の目的
学習の到達目標
ディプロマ・ポリシー
○ 学科・コース等の教育目標
○ JABEE 関連項目

○ 全学の教育目標
感じる力
  •  感性
  •  共感
  •  倫理観
  •  モチベーション
  •  主体的学習力
  •  心身の健康に対する意識
考える力
  •  幅広い教養
  •  専門知識・技術
  •  論理的思考力
  •  課題探求力
  •  問題解決力
  •  批判的思考力
コミュニケーション力
  •  情報受発信力
  •  討論・対話力
  •  指導力・協調性
  •  社会人としての態度
  •  実践外国語力
生きる力
  •  感じる力、考える力、コミュニケーション力を総合した力

授業の方法 講義

授業の特徴

教科書 教科書:特に指定しない。
参考書 参考書:
言語理論とオートマトン(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回 句構造文法とチューリング機械(1)
第10回 帰納的可算言語と帰納的言語
第11回 句構造文法とチューリング機械(2)
第12回 2方向無限テープTM,2テープTM,決定性TMと非決定性TMの等価性
第13回 万能チューリング機械
第14回 停止問題
第15回 まとめ
第16回 定期試験
学習課題(予習・復習)
ナンバリングコード(試行) EN-CMPS-2

※最初の2文字は開講主体、続く4文字は分野、最後の数字は開講レベルを表します。 ナンバリングコード一覧表はこちら


Copyright (c) Mie University