授業科目名				担当教員
言語とオートマトン				今宮　淳美
時間割番号	単位数	コース	履修年次	期別	曜日	時限
263605	2	G	2	前期	火	I
［概要］
記号を扱うコンピュータの論理モデルである有限オートマトン、形式言語、記号処理アルゴリズムについてである。この学問分野の結果や用語は、言語処理、ソフトウエア、人工知能、パターン認識などで使われてコンピュータ科学の重要な基礎科目である。<BR>カリキュラム中での位置付け：<a href="http:<BR>//www.cs.yamanashi.ac.jp/g/JABEE/curriculum/">Gコースのカリキュラム</a>
［具体的な達成目標］
離散系の仕組みと各種　アルゴリズムの理解：文字列パターンを表現および処理する　代数系としての，　有限オートマトン，正規表現，文脈自由文法について，文字列の　表現，各種アルゴリズムを理解し，応用問題に適用できること
［必要知識・準備］
高等学校での代数、大学1年前期の基礎代数　I、後期の基礎離散数学、データ構造と　アルゴリズム基礎　の知識を必要とする。
［評価方法・評価基準］
No 評価項目 割合 評価の観点 1 試験：定期試験  45  % （４）文字パターンの再帰記述，（５）文脈自由文法（６）パース木、文脈自由文法と正規表現７）文脈自由文法標準形  2 試験：中間試験  45  % （１）状態，有限オートマトン、状態機械のグラフ表現（２）決定性と非決定性オートマトン間の変換（３）正規表現と有限オートマトン間の変換  3 小テスト／レポート課題  10  % 理解の検証のためのクイズと演習
［教科書］
今宮　淳美, コンピュータ科学の基礎　Vol.2　−　文字列処理入門　第２版、, 山梨大学生協
［参考書］
(未登録)
［講義項目］
講義全体，状態，オートマトン<BR>　状態機械のグラフ表現<BR>　決定性と　非決定性<BR>　非決定性から決定性の変換<BR>　正規表現（１）<BR>　正規表現（２）<BR>　正規表現からオートマトンに変換<BR>　中間試験　<BR>　正規表現からオートマトンに変換<BR>　オートマトンから正規表現に変換<BR>　パターンの再帰記述，文脈自由文法<BR>　パース木，曖昧な文法<BR>　文法と正規表現，ＣＦＧの標準形<BR>　期末試験
［教育方法］
テキストに従い，より具体的に演習を通じて，各概念，　各種変換アルゴリズムの理解を図る．詳細な数学的論証よりは，演習問題による各種表現の変換等に関するアルゴリズムの理解を中心に講義する．<BR>演習はまず，講義で示す例題解答を参考に自分や周りの学生同士で解答を試みる努力が必要である．
［JABEEプログラムの学習・教育目標との対応］
《コンピュータ・メディア工学科 情報メディアコース》 (A) マルチメディア情報ネットワーク技術に習熟した情報処理技術者としての基盤となる基礎的素養及び基礎的スキルを修得する。 ◎
［その他］
(未登録)