授業科目名				担当教員
オートマトンと言語				鈴木 良弥
時間割番号	単位数	コース	履修年次	期別	曜日	時限
263222	2	F	2	前期	水	I
［概要］
本科目は情報科学における基礎をなし，ソフトウェア作成においても基礎的な知識として重要なものである．グラフ理論，有限オートマトン，形式言語理論，計算論を学び，ソフトウェア作成などに役立てる．
［具体的な達成目標］
簡単な数式などから構文木を書くことが出来る．<BR>状態遷移図から正規表現へ，正規表現から状態遷移図に変換できる．<BR>字句パターンを正規表現で表現できる．<BR>正規表現から状態数最小の有限オートマトンを構成できる．<BR>プッシュダウンオートマトンの動作を理解できる．
［必要知識・準備］
特になし．
［評価方法・評価基準］
No 評価項目 割合 評価の観点 1 試験：期末期  57  % 授業理解力  2 試験：中間期  30  % 授業理解力  3 小テスト／レポート  13  % 自発的勉学
［教科書］
形式言語と有限オートマトン入門　　例題を中心とした情報の離散数学, コロナ社, ISBN:4339023396
［参考書］
(未登録)
［講義項目］
１．数学的準備　（集合と写像，記号理論），帰納的表現<BR>　　　２．形式言語<BR>　　　３．離散グラフ<BR>　　　４．木グラフ<BR>　　　５．有限オートマトン１<BR>　　　６．有限オートマトン２<BR>　　　７．正規表現１<BR>　　　８．正規表現２<BR>　　　９．前半のまとめ，および中間試験<BR>　　１０．有限オートマトンの最小化<BR>　　１１．プッシュダウンオートマトン<BR>　　１２．チューリング機械<BR>　　１３．形式言語理論<BR>　　１４．文脈自由文法<BR>　　１５．まとめ，および期末試験
［教育方法］
講義中に毎回簡単な演習を行う．<BR>授業資料と授業音声をWebで公開する．<BR>演習問題の解答例をWebで公開する．<BR>中間試験，期末試験の解答例をWebで公開する．<BR>他の授業との関連を説明する．
［JABEEプログラムの学習・教育目標との対応］
《コンピュータ・メディア工学科 コンピュータサイエンスコース》 (B)種々の型と構造をもつ情報の表現手法及び処理手法についての基本的な知識と技術を習得する． ◎ (C)問題を形式的にモデル化し，そのモデルを基に問題解決する知識と技術を習得する． ◎ (G)ハードウェアとソフトウェアを融合した情報機器を設計・実現できる知識と技術を習得する． ○
［その他］
(未登録)