|
授業科目名
|
担当教員
|
|||||
|
オートマトンと言語
|
鈴木 良弥
|
|||||
|
時間割番号
|
単位数
|
コース
|
履修年次
|
期別
|
曜日
|
時限
|
| 263222 | 2 | F | 2 | 前期 | 水 | I |
| ［概要］ | ||||||
| 本科目は情報科学における基礎をなし，ソフトウェア作成においても基礎的な知識として重要なものである．グラフ理論，有限オートマトン，形式言語理論，計算論を学び，ソフトウェア作成などに役立てる． | ||||||
| ［具体的な達成目標］ | ||||||
| 簡単な数式などから構文木を書くことが出来る． 状態遷移図から正規表現へ，正規表現から状態遷移図に変換できる． 字句パターンを正規表現で表現できる． 正規表現から状態数最小の有限オートマトンを構成できる． プッシュダウンオートマトンの動作を理解できる． |
||||||
| ［必要知識・準備］ | ||||||
| 特になし． | ||||||
| ［評価方法・評価基準］ | ||||||
| 以下を総合して判定する． ・演習問題 ・中間試験（進度により行わないことがある） ・期末試験 |
||||||
| ［教科書］ | ||||||
| ［参考書］ | ||||||
| (未登録) | ||||||
| ［講義項目］ | ||||||
| １．数学的準備 （集合と写像，記号理論），帰納的表現 ２．形式言語 ３．離散グラフ ４．木グラフ ５．有限オートマトン１ ６．有限オートマトン２ ７．正規表現１ ８．正規表現２ ９．中間試験 １０．有限オートマトンの最小化 １１．プッシュダウンオートマトン １２．チューリング機械 １３．形式言語理論 １４．文脈自由文法 |
||||||
| ［教育方法］ | ||||||
| 講義中に毎回簡単な演習を行う． 授業資料をWebで公開する． 小テストの解答例をWebで公開する． 中間試験，期末試験の解答例をWebで公開する． なるべく他の授業との関連を説明する． |
||||||
| ［JABEEプログラムの学習・教育目標との対応］ | ||||||
| 教育目標Ｂ：グラフ理論、有限オートマトンなど、計算機の内部処理やプログラミングに必要な知識を習得させる. 教育目標Ｃ：言語のモデル化手法を理解させる. 教育目標Ｇ：ハードウェアの基礎となるフリップフロップなどの順序回路について理解させる. |
||||||
| ［その他］ | ||||||
| (未登録) | ||||||