△離散システム（k）[2B12]

＜学位授与の方針＞

	1. 基礎知識の習得
◎	2. 専門分野知識の習得
○	3. 汎用的問題解決技能
	4. 道徳的態度と社会性

＜授業のねらい＞

離散的な構造を持つシステムに関する解析・設計・最適化の理論と技術について学ぶ。

＜受講にあたっての前提条件＞

集合・写像・ブール関数・グラフ理論に関する基礎的知識を必要とする。

＜具体的な到達目標＞

組み合わせ最適化問題に対して、分岐限定法・動的計画法・ヒューリスティックスを用いて解くことができる。
与えられた言語を受理する有限オートマトン、プッシュダウンオートマトンの設計ができる。
与えられた有限オートマトン、プッシュダウンオートマトンが受理する言語が求められる。
与えられた言語を生成する文脈自由文法、正規文法、正規表現の設計ができる。
与えられた文脈自由文法、正規文法、正規表現が生成する言語が求められる。

＜授業計画及び準備学習＞

１　離散システムとは
　　　離散的な構造を持つシステムの解析手法の概要を解説する。
　　　準備学習：集合・グラフ理論の復習を行う。
　２　分岐限定法
　　　組み合わせ最適化問題を解くための分枝限定法を解説する。
　　　準備学習：離散システムの概要の復習を行う。
　３　動的計画法
　　　組み合わせ最適化問題を解くための動的計画法を解説する。
　　　準備学習：分岐限定法の復習を行う。
　４　計算量の理論（１）
　　　オーダーの表記法および解析法を解説する。
　　　準備学習：動的計画法の復習を行う。
　５　計算量の理論（２）
　　　NP完全性の定義とその意味について解説する。
　　　準備学習：オーダーの表記法の復習を行う。
　６　ヒューリスティックアルゴリズム
　　　焼きなまし法などのヒューリステッィクアルゴリズムの概要を解説する。
　　　準備学習：NP完全性の復習を行う。
　７　有限オートマトン
　　　有限オートマトンの定義を示し、有限オートマトンが受理する言語について解説する。
　　　事前学習：ヒューリスティックアルゴリズムの復習を行う。
　８　有限オートマトンの構築
　　　与えられた言語を受理する有限オートマトンの設計法について解説する。
　　　事前学習：有限オートマトンの定義の復習を行う。
　９　正規表現
　　　正規表現の定義を示し、正規表現が表す言語について解説する。
　　　事前学習：有限オートマトン構築の復習を行う。
１０　プログラミング言語の正規表現
　　　プログラミング言語で使われる正規表現について解説する。
　　　事前学習：正規表現の復習を行う。
１１　形式文法とそのクラス
　　　形式文法の定義とそのクラスについて解説する。
　　　事前学習：プログラミング言語の正規表現の復習を行う。
１２　プッシュダウンオートマトン
　　　プッシュダウンオートマトンの定義を示し、プッシュダウンオートマトンが受理する言語について解説する。
　　　事前学習：形式文法の復習を行う。
１３　プッシュダウンオートマトンの性質
　　　プッシュダウンオートマトンと文脈自由言語の等価性について解説する。
　　　事前学習：プッシュダウンオートマトンの定義の復習を行う。　　
１４　学習成果の振り返り
　　　事前学習：前回までの総復習を行っておく。

＜成績評価方法＞

定期試験と毎回の出席者に講義中に行う小テストで行う。

・定期試験(A)：１００点満点で定期試験期間に行う。再試験・追試験は行わない。
・小テスト(B)：１−１３回目において毎回２０点満点で行い、合算する（２６０点満点）。

AとBを9:1の割合で評価した結果をA+,A,B,C,D,Fの６段階で評価し、D以上を合格とする。

＜教科書＞

指定教科書なし

＜参考書＞

Michael Sipser著　「計算理論の基礎　原著第２版　１　オートマトンと言語」　共立出版

＜オフィスアワー＞

木曜２限、新宿A-1572研究室で行う。
上記以外の時間を希望する場合はメールで事前にアポイントメントを取ること。
メールアドレス：jt13455@ns.kogakuin.ac.jp