情報数学Ⅰ

科目基礎情報

学校 豊田工業高等専門学校 開講年度 平成31年度 (2019年度)
授業科目 情報数学Ⅰ
科目番号 34217 科目区分 専門 / 選択
授業形態 講義 単位の種別と単位数 学修単位: 2
開設学科 情報工学科 対象学年 4
開設期 後期 週時間数 2
教科書/教材 「オートマトン・言語理論の基礎」米田政明他、近代科学社 ISBN: 978-4764902978
担当教員 早坂 太一

到達目標

(ア)オートマトンの概念について説明できる。
(イ)形式言語の概念について説明できる。
(ウ)形式言語が制限の多さにしたがって分類されることを説明できる。
(エ)正規表現と有限オートマトンの関係を説明できる。

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
オートマトン有限オートマトン、プッシュダウンオートマトンおよびチューリング機械の概念について説明できる。有限オートマトンの概念について説明できる。有限オートマトンの概念について説明できない。
形式言語正規/句構造/文脈自由/文脈依存文法と正規/句構造/文脈自由/文脈依存言語の概念について説明できる。正規文法と正規言語の概念について説明できる。正規文法と正規言語の概念について説明できない。
オートマトンと形式文法の関係有限オートマトン、プッシュダウンオートマトンおよびチューリング機械と正規/句構造/文脈自由/文脈依存文法の関係について説明できる。有限オートマトンと正規文法の関係について説明できる。有限オートマトンと正規文法の関係について説明できない。

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

学習・教育到達度目標 A4, JABEE c, JABEE d, 本校教育目標 ②

教育方法等

概要:
コンピュータを数学的に取り扱うためのモデルである「オートマトン」、および自然言語やプログラミング言語のモデルである「形式言語」についての基礎理論を学ぶ。
授業の進め方と授業内容・方法:
座学で行う。また、教科書内容に沿ったパワーポイント資料を提供する。
注意点:
教科書の演習問題等を利用して、継続的に授業内容の予習・復習を行うこと。「情報科学」教育プログラムの選択必修科目である。

授業計画

授業内容・方法 週ごとの到達目標
後期
1週 シラバスの説明
オートマトン・言語理論とは(予習:教科書§1.1を読む、復習:第1章演習問題を解く)
オートマトンおよび形式言語の概念について説明できる。
2週 集合、写像(予習:教科書§1.2を読む、復習:第1章演習問題を解く) 集合および写像の概念について説明できる。
3週 有限オートマトン(1)(予習:教科書§2.1~§2.2を読む、復習:第2章演習問題を解く) 有限オートマトンの概念について説明できる。
4週 有限オートマトン(2)(予習:教科書§2.2~§2.4を読む、復習:第2章演習問題を解く) 有限オートマトンを状態遷移図で表すことができる。
5週 有限オートマトン(3)(予習:教科書§2.3~§2.7を読む、復習:第2章演習問題を解く) 決定性および非決定性オートマトンの概念について説明できる。
6週 プッシュダウンオートマトン(予習:教科書§3.1~§3.4を読む、復習:第3章演習問題を解く) プッシュダウンオートマトンの概念について説明できる。
7週 チューリング機械(予習:教科書§4.1~§4.3を読む、復習:第4章演習問題を解く) チューリング機械の概念について説明できる。
8週 中間試験 有限オートマトン、プッシュダウンオートマトンおよびチューリング機械の概念について説明できる。
9週 形式文法と形式言語(1)(予習:教科書§5.1~§5.2を読む、復習:第5章演習問題を解く) 形式文法および形式言語の概念について説明できる。
10週 形式文法と形式言語(2)(予習:教科書§5.2~§5.4を読む、復習:第5章演習問題を解く) 正規/文脈自由文法および正規/文脈自由言語の概念について説明できる。
11週 形式文法と形式言語(3)(予習:教科書§5.3~§5.6を読む、復習:第5章演習問題を解く) 句構造/文脈依存文法および句構造/文脈依存言語の概念について説明できる。
12週 オートマトンと形式文法(1)(予習:教科書§6.1~§6.2を読む、復習:第6章演習問題を解く) 正規文法と有限オートマトンとの関係について説明できる。
13週 オートマトンと形式文法(2)(予習:教科書§6.2~§6.4を読む、復習:第6章演習問題を解く) 有限オートマトン、プッシュダウンオートマトンおよびチューリング機械と正規/句構造/文脈自由/文脈依存文法との関係について説明できる。
14週 言語の階層構造(予習:教科書§7.1~§7.4を読む、復習:第7章演習問題を解く) 正規/句構造/文脈自由/文脈依存言語の性質について説明できる。
15週 総まとめ 形式文法の概念、およびそれとオートマトンとの関係について説明できる。
16週

評価割合

中間試験定期試験合計
総合評価割合4060100
専門的能力4060100