情報工学特論Ⅰ

科目基礎情報

学校	大島商船高等専門学校	開講年度	令和05年度 (2023年度)
授業科目	情報工学特論Ⅰ
科目番号	0105	科目区分	専門 / 選択
授業形態	授業	単位の種別と単位数	履修単位: 1
開設学科	情報工学科	対象学年	5
開設期	前期	週時間数	2
教科書/教材	教科書：J. ホップクロフト他，オートマトン 言語理論 計算論Ⅰ，サイエンス社，2003. 参考書：米田政明他，オートマトン・言語理論の基礎，近代科学社，2003.　藤原暁宏，はじめて学ぶオートマトンと言語理論，森北出版社，2015.
担当教員	高橋 芳明

到達目標

以下５つの目標を立てる．
(1) 非決定性有限オートマトンと決定性有限オートマトンを理解し，前者から後者への変換方法を修得する．
(2) 正規表現と有限オートマトンの関係を理解し，それらの変換方法を修得する．
(3) 有限オートマトンの最小化アルゴリズムを理解し，最小化の手法を修得する．
(4) プッシュダウン・オートマトンとその特性を理解する．
(5) チョムスキー階層を認識し，計算モデルにより言語の受理能力に差異があることを理解する．

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
評価項目1	非決定性有限オートマトンと決定性有限オートマトンを詳細に理解し，前者から後者への変換ができる．	非決定性有限オートマトンと決定性有限オートマトンを理解し，前者から後者への変換ができる．	非決定性有限オートマトンと決定性有限オートマトンを理解し，前者から後者への変換ができない．
評価項目2	正規表現と有限オートマトンの関係を詳細に理解し，それらの変換ができる．	正規表現と有限オートマトンの関係を理解し，それらの変換ができる．	正規表現と有限オートマトンの関係を理解し，それらの変換ができない．
評価項目3	プッシュダウン・オートマトンとその特性を詳細に理解している．	プッシュダウン・オートマトンとその特性を理解している．	プッシュダウン・オートマトンとその特性を理解できない．
評価項目4	チョムスキー階層を認識し，計算モデルにより言語の受理能力に差異があることを詳細に理解している．	チョムスキー階層を認識し，計算モデルにより言語の受理能力に差異があることを理解している．	チョムスキー階層を認識し，計算モデルにより言語の受理能力に差異があることを理解できない．

学科の到達目標項目との関係

JABEE J(05) （基礎的かつ複合的な工学専門知識（設計・システム系，情報・論理系，材料・バイオ 系，力学系，社会技術系の科目群）を修得し，具体的な工学問題の解決に応用できる）

本校 (1)-a （豊かな教養と国際感覚を身につけた，視野の広い技術者を養成する。）

情報 (4)-a （豊富な情報技術をもとにした視野の広い応用能力の養成）

教育方法等

概要:

オートマトン理論を学ぶことは，計算機の計算の原理を理解することに繋がる．AI 技術，機械学習技術が益々発展していく高度情報社会の中で，上手く高度な情報技術を使いこなすためにも，計算の原理に関連する計算の限界や計算複雑さの理論を認識した上で，情報技術を扱うことが求められる．その基礎的理論を固めるための一つの科目に位置づけられるオートマトン理論には，いくつか必ず修得すべき重要項目があり，部分集合構成法，正規表現から有限オートマトンへの変換，有限オートマトンの最小化はその代表格である．本講義では，それらの重要項目の修得を目指し，さらには「計算とは何か？」について考え，オートマトンという計算モデルを考察することにより，その答えを各自が導き出すことを目標とする．

授業の進め方・方法:

教室での講義を中心に授業を実施する．

注意点:

適宜，黒板に記した内容のノートを取ること．

授業の属性・履修上の区分

遠隔授業対応

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	オートマトン理論の概要，数学的準備	オートマトン理論の概要を理解する．
		2週	有限オートマトン	決定性有限オートマトンと非決定性有限オートマトンを理解し，説明できる．
		3週	決定性有限オートマトンと非決定性有限オートマトンの等価性	決定性有限オートマトンと非決定性有限オートマトンの等価性を理解し，部分集合構成法が説明できる．
		4週	ε-動作を含む有限オートマトン	ε-動作を含む有限オートマトンを理解し，ε-遷移の除去が説明できる．
		5週	正規表現と正規言語	正規表現と有限オートマトンの関係を理解し，相互の変換を説明できる．
		6週	正規言語の性質	正規言語に対する反復補題を理解する．
		7週	前半のまとめ	前半の授業内容を説明できる．
		8週	中間試験
	2ndQ
		9週	有限オートマトンの最小化	有限オートマトンの最小化アルゴリズムを理解し，説明できる．
		10週	形式文法	形式文法と正規文法を理解し，説明できる．
		11週	文脈自由文法	文脈自由文法と構文木を理解し，説明できる．
		12週	プッシュダウン・オートマトン	プッシュダウン・オートマトンを理解し，プッシュダウン・オートマトンの限界を説明できる．
		13週	チョムスキー階層とチューリング機械	チョムスキー階層を理解し，チューリング機械を説明できる．
		14週	オートマトンと形式文法の関係	オートマトンと形式文法の関係を理解し，説明できる．
		15週	後半のまとめ	後半の授業内容を説明できる．
		16週	期末試験

評価割合

	試験	提出物	合計
総合評価割合	70	30	100
基礎的能力	0	0	0
専門的能力	70	30	100
分野横断的能力	0	0	0