講義資料ページへ

情報数理学2005

情報数理学ノート

第1回オートマトンと正規言語 (ppt)

第2回オートマトンと正規言語の等価性 (ppt)

第3回プッシュダウンオートマトンと文脈自由文法 (ppt)

第4回PDAとCFLの等価性 (ppt)

第5回チューリングマシンと計算 (ppt)

第6回チユーリングマシンの符号化と計算不可能性 (ppt)

第7回時間限定チューリングマシンとクラスP (ppt)

第8回クラスNPと多項式時間帰着 (ppt)

第9回NP完全とNP困難 (ppt)

第10回PとNP完全問題との境界 (ppt)

第11回擬多項式時間アルゴリズムと 動的計画法 (ppt)

第12回緩和法と分枝限定法 (ppt)

第13回近似アルゴリズム (ppt)