[授業科目名] オートマトン・言語理論(2012B025) Automata and Language Theory [ 時間割名 ] オートマトン・言語理論(233090) [時間割担当] 佐藤秀樹 [ 実 施 期 ] 前期 [ 単 位 数 ] 2 選択 [曜日・時限] 火・3 [ 対象学生 ] 情報学部情報ＳＹ(5期) □■ 科目の概要 オートマトンは，機械が計算することの本質を理解するための計算機のモデルである。これに対して，言語理論は文法が自然 言語・プログラミング言語を始めとする言語を生成する仕組みを理解するための体系である。この両者は，形式言語を介して 密接な関係を持っている。この授業では，オートマトンに関して，最も単純なモデルである有限オートマトンから始り，それ を拡張したプッシュダウンオートマトン，オートマトンの一般形となるチューリング機械について学習する。また，言語理論 に関して，有限オートマトンに対応する正規文法，プッシュダウンオートマトンに対応する文脈自由文法，さらにそれらの文 法により生成される正規言語・文脈自由言語について学習する。この科目は，計算機科学および情報科学における基礎理論の 修得を目的とする。コンパイラ・テキスト検索・プロトコル検証・ＸＭＬ(Extended Markup Language)を始めとする計算機科 学の種々の応用は，この科目の学習内容を基としている。 □■ 授業の内容 □■ 学習到達目標 [1]形式言語 [2]集合 [3]写像とグラフ [4]有限オートマトンと状態遷移図 [5]非決定性有限オートマトン [6]非決定性有限オートマトンから等価な決定性有限オート マトンの構成法 [7]最簡形の決定性有限オートマンの構成法 [8]プッシュダウンオートマトン [9]チューリング機械 [10]言語の生成システムとしての形式文法 [11]形式文法の型と形式言語のクラス [12]正規文法（言語）と文脈自由文法（言語） [13]有限オートマトンから正規文法の構成法 [14]正規文法から有限オートマトンの構成法 [15]オートマトン・言語理論のまとめ [16]期末試験 [1]有限オートマトンに対する状態遷移図を構成できる。 [2]非決定性有限オートマトンから等価な決定性有限オート マトンを構成できる。 [3]最簡形の有限オートマンを構成できる。 [4]有限オートマトンから正規文法を構成できる。 [5]正規文法から有限オートマトンを構成できる。 □■ 成績評価の方法 小テスト，期末試験による総合評価 □■ 教科書 「オートマトン・形式言語理論」 ＜コロナ社＞ 広瀬貞樹 著 □■ 参考書 □■ 履修要件 Ｃ言語の文法の基本を習得し、プログラミングの素養を身につけていること、さらに、アルゴリズムとデータ構造１の単位を 修得していることが望ましい。 □■ 履修上の注意事項 C言語のプログラミングの能力を身につけておくこと、「プログラミング１」、「プログラミング２」、「プログラミング３」 および「アルゴリズムとデータ構造１ 」を必ず受講し、単位を取得しておくことが望ましい。 □■ 履修者の遵守事項 C言語のプログラミングの能力を身につけておくこと、「プログラミング１」、「プログラミング２」、「プログラミング３」 および「アルゴリズムとデータ構造１ 」を必ず受講し、単位を取得しておくことが望ましい。 □■ その他 (科目) □■ その他 (授業) □■ 備考 C言語のプログラミングの能力を身につけておくこと、「プログラミング１」、「プログラミング２」、「プログラミング３」 および「アルゴリズムとデータ構造１ 」を必ず受講し、単位を取得しておくことが望ましい。 ※ 授業時間外学習について 1単位は、45時間の学修を必要とする内容をもって構成することとなっています。本学では、授業の方法に応じ、授業時間内の 学修と授業時間外の学修を次のとおり定めています。 (1)講義及び演習(1単位科目) 授業時間内の学修30時間(毎週2時間)、授業時間外の学修15時間(毎週1時間) (2)講義及び演習(2単位科目) 授業時間内の学修30時間(毎週2時間)、授業時間外の学修60時間(毎週4時間) (3)設計(3単位科目) 授業時間内の学修60時間(毎週4時間)、授業時間外の学修75時間(毎週5時間) (4)実験、実習及び製図(1.5単位科目) 授業時間内の学修60時間(毎週4時間)、授業時間外の学修7.5時間(毎週0.5時間) [授業科目名] オートマトン・言語理論(2012B025) Automata and Language Theory [ 時間割名 ] オートマトン・言語理論(423080) [時間割担当] 佐藤秀樹 [ 実 施 期 ] 前期 [ 単 位 数 ] 2 選択 [曜日・時限] 木・2 [ 対象学生 ] 情報学部情報ＳＹ(5期) □■ 科目の概要 オートマトンは，機械が計算することの本質を理解するための計算機のモデルである。これに対して，言語理論は文法が自然 言語・プログラミング言語を始めとする言語を生成する仕組みを理解するための体系である。この両者は，形式言語を介して 密接な関係を持っている。この授業では，オートマトンに関して，最も単純なモデルである有限オートマトンから始り，それ を拡張したプッシュダウンオートマトン，オートマトンの一般形となるチューリング機械について学習する。また，言語理論 に関して，有限オートマトンに対応する正規文法，プッシュダウンオートマトンに対応する文脈自由文法，さらにそれらの文 法により生成される正規言語・文脈自由言語について学習する。この科目は，計算機科学および情報科学における基礎理論の 修得を目的とする。コンパイラ・テキスト検索・プロトコル検証・ＸＭＬ(Extended Markup Language)を始めとする計算機科 学の種々の応用は，この科目の学習内容を基としている。 □■ 授業の内容 □■ 学習到達目標 [1]形式言語 [2]集合 [3]写像とグラフ [4]有限オートマトンと状態遷移図 [5]非決定性有限オートマトン [6]非決定性有限オートマトンから等価な決定性有限オート マトンの構成法 [7]最簡形の決定性有限オートマンの構成法 [8]プッシュダウンオートマトン [9]チューリング機械 [10]言語の生成システムとしての形式文法 [11]形式文法の型と形式言語のクラス [12]正規文法（言語）と文脈自由文法（言語） [13]有限オートマトンから正規文法の構成法 [14]正規文法から有限オートマトンの構成法 [15]オートマトン・言語理論のまとめ [16]期末試験 [1]有限オートマトンに対する状態遷移図を構成できる。 [2]非決定性有限オートマトンから等価な決定性有限オート マトンを構成できる。 [3]最簡形の有限オートマンを構成できる。 [4]有限オートマトンから正規文法を構成できる。 [5]正規文法から有限オートマトンを構成できる。 □■ 成績評価の方法 小テスト，期末試験による総合評価 □■ 教科書 「オートマトン・形式言語理論」 ＜コロナ社＞ 広瀬貞樹 著 □■ 参考書 □■ 履修要件 Ｃ言語の文法の基本を習得し、プログラミングの素養を身につけていること、さらに、アルゴリズムとデータ構造１の単位を 修得していることが望ましい。 □■ 履修上の注意事項 C言語のプログラミングの能力を身につけておくこと、「プログラミング１」、「プログラミング２」、「プログラミング３」 および「アルゴリズムとデータ構造１ 」を必ず受講し、単位を取得しておくことが望ましい。 □■ 履修者の遵守事項 C言語のプログラミングの能力を身につけておくこと、「プログラミング１」、「プログラミング２」、「プログラミング３」 および「アルゴリズムとデータ構造１ 」を必ず受講し、単位を取得しておくことが望ましい。 □■ その他 (科目) □■ その他 (授業) □■ 備考 C言語のプログラミングの能力を身につけておくこと、「プログラミング１」、「プログラミング２」、「プログラミング３」 および「アルゴリズムとデータ構造１ 」を必ず受講し、単位を取得しておくことが望ましい。 ※ 授業時間外学習について 1単位は、45時間の学修を必要とする内容をもって構成することとなっています。本学では、授業の方法に応じ、授業時間内の 学修と授業時間外の学修を次のとおり定めています。 (1)講義及び演習(1単位科目) 授業時間内の学修30時間(毎週2時間)、授業時間外の学修15時間(毎週1時間) (2)講義及び演習(2単位科目) 授業時間内の学修30時間(毎週2時間)、授業時間外の学修60時間(毎週4時間) (3)設計(3単位科目) 授業時間内の学修60時間(毎週4時間)、授業時間外の学修75時間(毎週5時間) (4)実験、実習及び製図(1.5単位科目) 授業時間内の学修60時間(毎週4時間)、授業時間外の学修7.5時間(毎週0.5時間)
© Copyright 2024 ExpyDoc
