山梨大学電子シラバス>検索結果一覧>授業データ



授業科目名
担当教官
言語とオートマトン
今宮 淳美
時間割番号
単位数
コース
履修年次
期別
曜日
時限
263605 2 G 2 前期 I
[概要]
記号を扱うコンピュータの論理モデルである有限オートマトン、形式言語、記号処理アルゴリズムについてである。この学問分野の結果や用語は、言語処理、ソフトウエア、人工知能、パターン認識などで使われてコンピュータ科学の重要な基礎科目である。
カリキュラム中での位置付け:Gコースのカリキュラム
[具体的な達成目標]
システムの状態遷移,有限オートマトン,正規表現,文脈自由文法,文脈自由言語の理解とそれら概念間の関係を理解する.
[必要知識・準備]
高等学校での代数、大学1年前期の基礎代数 I、後期の情報数学基礎、データ構造とアルゴリズム基礎 の知識を必要とする。
[評価基準]
中間試験(50%)及び定期試験(50%)で評価する.
[教科書]
  1. 今宮 淳美, コンピュータ科学の基礎 Vol.2 − 文字列処理入門 第2版、, 山梨大学生協
[参考書]
(未登録)
[講義項目]
 講義全体,状態,オートマトン
 状態機械のグラフ表現
 決定性と 非決定性
 非決定性から決定性の変換
 正規表現(1)
 正規表現(2)
 正規表現からオートマトンに変換
 中間試験 
 正規表現からオートマトンに変換
 オートマトンから正規表現に変換
 パターンの再帰記述,文脈自由文法
 パース木,曖昧な文法
 文法と正規表現,CFGの標準形
 期末試験
[教育方法]
テキストに従い,より具体的に演習を通じて, 各概念, 各種変換アルゴリズムの理解を図る.詳細な数学的論証よりは,演習問題による各種変換等に関するアルゴリズムの理解を中心に講義する.
[JABEEプログラムの学習・教育目標との対応]
情報処理技術者としての基礎的素養及び基礎的スキルの修得:離散系の理解;オートマトンのグラフ表現,正規表現に関する各種変換アルゴリズムの理解,文脈自由文法による言語生成
人間の知性・感性を知り応用するための知性・感性情報工学における基礎的技術:言語の生成と処理
[その他]
(未登録)