到達目標
(1)コンパイラの役割としくみの基礎を理解できる
(2)順序機械および有限オートマトンの基礎を理解できる
(3)正規言語,正規文法の基礎を理解できる
(4)字句解析系,形式言語理論の基礎を理解できる
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
評価項目1 | コンパイラの役割としくみの基礎をよく理解できる | コンパイラの役割としくみの基礎を理解できる | コンパイラの役割としくみの基礎を理解できない |
評価項目2 | 順序機械および有限オートマトンの基礎をよく理解できる | 順序機械および有限オートマトンの基礎を理解できる | 順序機械および有限オートマトンの基礎を理解できない |
評価項目3 | 正規言語,正規文法の基礎をよく理解できる | 正規言語,正規文法の基礎を理解できる | 正規言語,正規文法の基礎を理解できない |
評価項目4 | 字句解析系,形式言語理論の基礎をよく理解できる | 字句解析系,形式言語理論の基礎を理解できる | 字句解析系,形式言語理論の基礎を理解できない |
学科の到達目標項目との関係
学習・教育到達度目標 J2
説明
閉じる
学習・教育到達度目標 J4
説明
閉じる
学習・教育到達度目標 J5
説明
閉じる
教育方法等
概要:
この授業では,コンパイラのみならず情報科学の基礎をなす有限オートマトンを中心に,形式言語理論,字句解析系,構文解析系の概要を知ることを目的とする.有限オートマトンは,本来計算機を抽象化して得られる数学的モデルである.本科目では,順序機械、決定性有限オートマトン、非決定性有限オートマトンについて述べ、有限オートマトンを用いた字句解析系,形式言語理論の基礎を説明する.
本科目は,情報処理学会が策定したIPSJ-SE推奨カリキュラムの「形式言語と計算理論」の教育内容に準拠している(IEEE/ACM-CCSEカリキュラムにも対応).
授業の進め方・方法:
到達目標(1)~(3)の到達度を定期試験80%,課題レポート,小テスト20%の割合で評価し,60点以上を合格とする.なお,本科目は授業・自学ノートの提出とそのノートの内容が指定した水準以下の場合は期末試験の受験を認めず,成績評価は35点以下とする.また,授業・自学ノートの提出時までの欠課時数が1/3を越えた場合,欠課時数と出席停止の合計時数が1/2を越えた場合についても期末試験の受験資格を認めずに成績評価を35点以下とするので注意すること.再評価試験,卒業追認試験については,成績評価が36点以上の者について申請があった場合にのみ受験を認める.
注意点:
学修単位科目であり,1回の講義(90分)あたり180分以上の予習・復習をしているものとして講義・演習を進める.
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
前期 |
1stQ |
1週 |
1.序論(その1) コンパイラの概要と形式言語について概要を解説する.また,数学的基礎について概説する.
|
コンパイラの概要と形式言語について理解を解説する.また,数学的基礎について理解する.
|
2週 |
1.序論(その2) 数学的基礎について引き続き解説を行い,言語についての定義を示す.
|
数学的基礎について理解すると共に言語についての定義を理解する
|
3週 |
2.有限オートマトンと正規表現(その1) 離散時間システム,ミーリー型順序機械について解説を行う.
|
離散時間システム,ミーリー型順序機械について理解する.
|
4週 |
2.有限オートマトンと正規表現(その2) ミーリー型順序機械とその状態簡約,ムーア型順序機械について説明を行う.
|
ミーリー型順序機械とその状態簡約,ムーア型順序機械について理解する.
|
5週 |
2.有限オートマトンと正規表現(その3) 順序機械を発展させた有限オートマトンの概要について解説する.とくに状態遷移関数について説明する.
|
順序機械を発展させた有限オートマトンの概要について理解する.とくに状態遷移関数について理解する.
|
6週 |
2.有限オートマトンと正規表現(その4) チューリングマシンについて触れ,正規言語について解説する.
|
チューリングマシンについて触れ,正規言語について理解する.
|
7週 |
2.有限オートマトンと正規表現(その5) 有限オートマトンの等価性判定アルゴリズムについて解説を行う.
|
有限オートマトンの等価性判定アルゴリズムについて理解する.
|
8週 |
中間試験 第1週から第7週までの内容で中間試験を実施する
|
中間試験
|
2ndQ |
9週 |
2.有限オートマトンと正規表現(その6) 非決定性有限オートマトンの概要について説明する.
|
非決定性有限オートマトンの概要について理解する.
|
10週 |
2.有限オートマトンと正規表現(その7) 非決定性有限オートマトン,部分集合構成法について解説を行う.
|
非決定性有限オートマトン,部分集合構成法について理解する.
|
11週 |
2.有限オートマトンと正規表現(その8) 空動作を有する非決定性有限オートマトンについて解説を行う.
|
空動作を有する非決定性有限オートマトンについて理解する.
|
12週 |
2.有限オートマトンと正規表現(その9) 正規表現と空動作を有する非決定性有限オートマトン,正規言語と非正規言語について解説を行う.
|
正規表現と空動作を有する非決定性有限オートマトン,正規言語と非正規言語について理解する.
|
13週 |
2.有限オートマトンと正規表現(その10) 形式文法,構文,正規文法について概要を解説する.
|
形式文法,構文,正規文法について概要を理解する.
|
14週 |
3.文脈自由文法とlexの紹介 文脈自由文法,lexプログラムの書き方などを解説する.
|
文脈自由文法,lexプログラムの書き方などを理解する.
|
15週 |
期末試験 9~14回目の内容について期末試験を実施する.
|
期末試験
|
16週 |
試験の解答と解説 期末試験の解答と解説を行う.
|
期末試験の解答と解説を行う.未回答,正解できなかった問題について理解する.
|
モデルコアカリキュラムの学習内容と到達目標
分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
専門的能力 | 分野別の専門工学 | 情報系分野 | システムプログラム | 形式言語の概念について説明できる。 | 3 | |
オートマトンの概念について説明できる。 | 3 | |
コンパイラの役割と仕組みについて説明できる。 | 3 | |
形式言語が制限の多さにしたがって分類されることを説明できる。 | 3 | |
正規表現と有限オートマトンの関係を説明できる。 | 3 | |
評価割合
| 定期試験 | 発表 | 相互評価 | 課題レポート,小テスト | ポートフォリオ | その他 | 合計 |
総合評価割合 | 80 | 0 | 0 | 20 | 0 | 0 | 100 |
基礎的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
専門的能力 | 80 | 0 | 0 | 20 | 0 | 0 | 100 |
分野横断的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |