理工学部Faculty of Science and Engineering
COS300XG(計算科学 / Computational science 300)言語の数理Formal Languages
金沢 誠Makoto KANAZAWA
授業コードなどClass code etc
学部・研究科Faculty/Graduate school | 理工学部Faculty of Science and Engineering |
添付ファイル名Attached documents | |
年度Year | 2021 |
授業コードClass code | H9068 |
旧授業コードPrevious Class code | |
旧科目名Previous Class title | |
開講時期Term | 春学期授業/Spring |
曜日・時限Day/Period | 木3/Thu.3 |
科目種別Class Type | |
キャンパスCampus | 小金井 |
教室名称Classroom name | |
配当年次Grade | |
単位数Credit(s) | |
備考(履修条件等)Notes | |
他学部公開科目Open Program | |
他学部公開(履修条件等)Open Program (Notes) | |
グローバル・オープン科目Global Open Program | |
成績優秀者の他学部科目履修制度対象Interdepartmental class taking system for Academic Achievers | |
成績優秀者の他学部科目履修(履修条件等)Interdepartmental class taking system for Academic Achievers (Notes) | |
実務経験のある教員による授業科目Class taught by instructors with practical experience | |
SDGsCPSDGs CP | |
アーバンデザインCPUrban Design CP | |
ダイバーシティCPDiversity CP | |
未来教室CPLearning for the Future CP | |
カーボンニュートラルCPCarbon Neutral CP | |
千代田コンソ単位互換提供(他大学向け)Chiyoda Campus Consortium | |
カテゴリー<理工学部>Category |
創生科学科 学科専門科目 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
Students learn theories of string and tree languages.
From the discrete structures (DS) area of the standard computer science curriculum J07-CS, the course covers part of the following topics:
DS6: automata and regular expressions
DS7: overview of the theory of computation
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的(何を学ぶか)Outline and objectives
有限オートマトンと文脈自由文法の理論について学ぶ.
カリキュラム標準コンピュータ科学J07-CSのうち,離散構造(DS)エリアからから次のトピックの一部をカバーする。
DS6: オートマトンと正規表現
DS7: 計算論概論
到達目標Goal
・正規言語のいろいろな特徴付けについて理解する.
・文脈自由文法の概念について理解する.
・木オートマトンについて理解する.
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか(該当授業科目と学位授与方針に明示された学習成果との関連)Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」と「DP2」と「DP4」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)(学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. )
板書を中心とした講義と定期的な課題による。授業の冒頭部分で提出された課題の正答と,実際の間違いの例について解説する。
アクティブラーニング(グループディスカッション、ディベート等)の実施Active learning in class (Group discussion, Debate.etc.)
なし / No
フィールドワーク(学外での実習等)の実施Fieldwork in class
なし / No
授業計画Schedule
※各回の授業形態は予定です。教員の指示に従ってください。
1:有限オートマトン
決定性有限オートマトン(DFA)とその表現,認識可能言語の閉包性
2:Myhill-Nerodeの定理
Myhill-Nerode関係,Myhill-Nerodeの定理とその応用
3:Myhill-Nerode関係と最小DFA
左商による最小DFAの構成,DFAの最小化
4:正規表現と有限オートマトンの等価性(1)
正規表現,認識可能な言語が正規言語であることの証明
5:正規表現と有限オートマトンの等価性(2)
左商を表す正規表現の計算
6:正規表現と有限オートマトンの等価性(3)
正規表現の簡略化,左商を表す既簡略の正規表現の個数の有限性
7:有限モノイドによる認識(1)
モノイド,DFAの遷移モノイド
8:有限モノイドによる認識(2)
有限モノイドによる認識可能言語の特徴づけ,syntactic monoid
9:文脈自由文法
文脈自由文法に関する基本概念,ラベル付き順序木,構文解析木
10:文脈自由言語と正規言語
有限モノイドからの文脈自由文法の構成,文脈自由言語の閉包性
11:有限木オートマトン(1)
木オートマトン,認識可能な木言語
12:有限木オートマトン(2)
認識可能な木言語に対するMyhill-Nerodeの定理
13:文脈自由文法と正規木文法
文脈自由言語と認識可能な木言語の関係
14:文脈自由言語と正規木言語の性質
Chomsky-Schützenbergerの定理
授業時間外の学習(準備学習・復習・宿題等)Work to be done outside of class (preparation, etc.)
【本授業の準備・復習等の授業時間外学習は、4時間を標準とする】授業中に示された演習問題を解く。
テキスト(教科書)Textbooks
教科書は使用しない。講義ノートを配布する。
参考書References
特に指定しない。
成績評価の方法と基準Grading criteria
定期的に課す演習問題(40%)と期末レポート(60%)の成績で評価する。
学生の意見等からの気づきChanges following student comments
特になし。
その他の重要事項Others
事前に履修すべき科目:離散構造,離散解析