|
授業科目名
|
担当教官
|
|||||
|
計算モデルとアルゴリズム
|
宮本 泉
|
|||||
|
時間割番号
|
単位数
|
コース
|
履修年次
|
期別
|
曜日
|
時限
|
| 263305 | 2 | F | 3 | 前期 | 水 | III |
| ［概要と目標］ | ||||||
| 計算のモデルとして有限オートマトンを紹介し、計算出力の集合として正規言語による文字列の代数的計算法を学習する。簡単なオートマトンの構成、そのプログラミング、オートマトンと正規言語の間の変換ができるようになることを目標とする。これらのモデルでは計算不可能な例を学習する。やや一般的な文字列解析として文脈自由文法およびその計算法を学ぶ。文字列探索、コーディングについて効率的な方法の例を紹介する。 | ||||||
| ［必要知識・準備］ | ||||||
| 情報数学基礎、情報数学(集合、グラフ)。プログラミングの基礎 | ||||||
| ［評価基準］ | ||||||
| 期末試験。授業中、教官のだす質問に答えたとき評価を考慮することがある。 | ||||||
| ［教科書］ | ||||||
|
||||||
| ［参考書］ | ||||||
|
||||||
| ［講義項目］ | ||||||
| １．計算のモデル ２．有限オートマトン ３．有限オートマトンとプログラミング ４．非決定性有限オートマトン ５．等価なオートマトンの構成 ６．正規言語 ７．正規言語の代数法則 ８．正規言語からオートマトンへ ９．オートマトンから正規言語へ １０．計算可能性 １１．文脈自由文法 １２．文脈自由文法と正規言語 １３．文字列探索 １４．コーディングの基本 |
||||||