言語理論

科目基礎情報

学校	岐阜工業高等専門学校	開講年度	2017
授業科目	言語理論
科目番号	0228	科目区分	専門 / 選択
授業形態	講義	単位の種別と単位数	学修単位: 1
開設学科	電気情報工学科	対象学年	5
開設期	後期	週時間数	1
教科書/教材	オートマトン・言語と計算理論(岩間一雄・コロナ社)
担当教員	出口 利憲

到達目標

以下の各項目を到達目標とする
(1) 計算機のモデルを理解する。
(2) 形式文法を理解する。
(3) 計算機のモデルと形式文法の関係を理解する。
(4) 抽象的思考ができる。

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
評価項目1	有限オートマトン,プッシュダウ ンオートマトン,チューリング機 械に関する問題を正確(80%)に 解くことができる	有限オートマトン,プッシュダウ ンオートマトン,チューリング機 械に関する問題をほぼ正確(60%)に 解くことができる	有限オートマトン,プッシュダウ ンオートマトン,チューリング機 械に関する問題を解くことができない
評価項目2	正規表現,文脈自由文法に関する 問題を正確(80%)に解くことが できる	正規表現,文脈自由文法に関する 問題をほぼ正確(60%)に解くこ とができる	正規表現,文脈自由文法に関する 問題を解くことができない
評価項目3	オートマトンと形式文法の関係に 関する問題を正確(80%)に解く ことができる	オートマトンと形式文法の関係に 関する問題をほぼ正確(60%)に 解くことができる	オートマトンと形式文法の関係に 関する問題を解くことができない
	オートマトン,チューリング機械,形式文法についての証明に関する問題を正確(80%)に解くことができる	オートマトン,チューリング機械,形式文法についての証明に関する問題をほぼ正確(60%)に解くことができる	オートマトン,チューリング機械,形式文法についての証明に関する問題を解くことができない

教育方法等

概要:

計算機科学の基礎となる形式言語とオート マトンの考え方を理解する。

授業の進め方・方法:

教科書に沿って授業をすすめるが,教科書の内容から離れることもあるので講義に集中すること。

注意点:

演習には積極的に取り組み,指定された課題を提出すること。
なお,教室外学修の内容は演習課題および試験問題を通じて成績評価に含まれる。
学習教育・目標：(D-4(3))１００%
JABEE 基準1(1)：(d)

授業計画

		週	授業内容	週ごとの到達目標
後期
	3rdQ
		1週	言語とは (AL のレベル C)	言語とは，を理解する (教室外学修)形式言語の演習
		2週	形式言語 (AL のレベル C)	形式言語を理解する (教室外学修)形式言語の演習
		3週	正規表現 (AL のレベル C)	正規表現を理解する (教室外学修)正規表現の演習
		4週	有限オートマトン (AL のレベル B)	有限オートマトンを理解する (教室外学修)有限オートマトンの演習
		5週	非決定性有限オートマトン(AL のレベル C)	直積を理解する 非決定性有限オートマトンを理解する (教室外学修)有限オートマトンの演習
		6週	有限オートマトンと正規表現 (AL のレベル C)	有限オートマトンと正規表現の関係を理解する (教室外学修)有限オートマトンの演習
		7週	文脈自由文法 (AL のレベル C)	文脈自由文法を理解する (教室外学修)文脈自由文法の演習
		8週	中間試験	(教室外学修)文脈自由文法の演習
	4thQ
		9週	文脈自由文法の標準形 (AL のレベル C)	文脈自由文法の標準形を理解する (教室外学修)文脈自由文法の演習
		10週	プッシュダウンオートマトン (AL のレベル C)	プシュダウントートマトンを理解する (教室外学修)プッシュダウンオートマトンの演習
		11週	状態数1のプッシュダウンオートマトン (AL のレベル C)	状態数を１にできることを理解する (教室外学修)プッシュダウンオートマトンの演習
		12週	プッシュダウンオートマトンと文脈自由文法 (AL のレベル C)	プッシュダウンオートマトンと文脈自由文法の関係を理解する (教室外学修)プッシュダウンオートマトンの演習
		13週	チューリング機械 (AL のレベル C)	チューリング機械を理解する (教室外学修)チューリング機械の演習
		14週	チューリング機械の停止性 (AL のレベル C)	チューリング機械の停止性を覚える (教室外学修)チューリング機械の演習
		15週	NP 完全問題	NP完全問題を覚える
		16週

モデルコアカリキュラムの学習内容と到達目標

分類		分野	学習内容	学習内容の到達目標	到達レベル	授業週
専門的能力	分野別の専門工学	情報系分野	システムプログラム	形式言語の概念について説明できる。	2
				オートマトンの概念について説明できる。	2

評価割合

	試験	課題	合計
総合評価割合	80	20	100
得点	80	20	100