複雑さ
7 時間の複雑さ 7.1 複雑さの測定 7.2 クラスP 7.3 クラスNP 7.4 NP完全性 7.5 他のNP完全問題 8 領域の複雑さ 8.1 Savitch の定理 8.2 クラスPSPACE 8.3 PSPACE 完全性 8.4 クラスLとクラスNL 8.5 NL完全性 8.6 NLとcoNLの等価性 9 問題の扱いにくさ 9.1 階…
第１巻より大幅に簡略して読む(勝手な都合) 3 Church-Turing の提唱 3.1 Turing 機械 無限のメモリ・無限長のテープ それでも解けない問題もある 3.2 Turing 機械の変型 3.3 アルゴリズムの定義 4 判定可能性 4.1 判定可能な言語 言語クラス 正規 文脈自由 …
1 正規言語 「計算機とは何か？」を理解するために計算をモデル化する 計算機設計的な位置づけで「有限オートマトン」があり、文字列を読み取るという立場から正規表現がある 1.1 有限オートマトン 有限オートマトンの定義 ５個組で決まる は状態の有限集合 …
計算理論の基礎 [原著第2版] 1.オートマトンと言語作者: Michael Sipser,太田和夫,田中圭介,阿部正幸,植田広樹,藤岡淳,渡辺治出版社/メーカー: 共立出版発売日: 2008/05/21メディア: 単行本購入: 6人 クリック: 68回この商品を含むブログ (30件) を見る計算…
0 序論 0.1 オートマトン、計算可能性、複雑さ 『計算機の本質的な能力とその限界は何か？』が全体を束ねる問 それに答えるために３巻構成 (1) オートマトン 計算・言語の数学的モデル (2) 計算可能性 解を求められる問題か、求められない問題か (3) 複雑さ …
