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