△離散システム（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