遺伝学・遺伝統計学関連の姉妹ブログ『ryamadaの遺伝学・遺伝統計学メモ』
京都大学大学院医学研究科ゲノム医学センター統計遺伝学分野のWiki
講義・スライド
医学生物学と数学とプログラミングの三重学習を狙う学習ツール
駆け足で読む○○シリーズ
ぱらぱらめくるシリーズ
カシオの計算機
オンライン整数列大辞典

駆け足で読む『計算理論の基礎』３巻構成とか、全体に関すること

駆け足で読むシリーズ 計算理論 オートマトン 有限オートマトン 形式言語 文脈自由文法 正規表現 複雑さ
  • 0 序論
    • 0.1 オートマトン、計算可能性、複雑さ
      • 『計算機の本質的な能力とその限界は何か？』が全体を束ねる問
      • それに答えるために３巻構成
        • (1) オートマトン
          • 計算・言語の数学的モデル
        • (2) 計算可能性
          • 解を求められる問題か、求められない問題か
        • (3) 複雑さ
          • 問題が簡単か、難しいか
    • 0.2 数学的概念や用語
      • 集合
        • 元、部分集合・真部分集合、重複集合、無限集合、空集合、ベン図
      • 列と組
        • 列(sequence)と組(tuple)、直積A \times B
      • 関数と関係
        • 関数、写像、定義域・値域
        • 引数、k-項関数、項数、二項関数
        • 前置記法、中置記法
        • 同値関係(反射律、対称律、推移律)
      • グラフ
        • ノード、エッジ、ラベル付けグラフ、部分グラフ、パス、連結、巡回、木、根、葉、有向グラフ、入次数・出次数、強連結
      • 文字列と言語
        • 文字、文字列、長さ、空列、逆順、部分文字列、連結、辞書式順序、言語
      • BOOLE論理
    • 0.3 定義、定理、証明
      • 定義definitionとは構成要素が何であり、構成要素でないものは何であるかを明確にして、ものや概念を規定する
      • 命題statementとは定義されたものや概念がある性質を持つことを述べたものであって、真偽を決することができるだけ十分に詳細に、また曖昧でないように記述されたもの
      • 証明proofとは命題が真であることを納得させる論理的な議論のこと
      • 定理theoremとは真であると証明された命題のこと
      • 補題lemmaとは重要な命題を証明するときにその補助となる命題のこと
      • 系corollaryとはある定理や証明を用いて、真であることを容易に示せる、他の命題のこと
    • 0.4 証明のタイプ

駆け足で読む『計算理論の基礎』目次

駆け足で読むシリーズ 計算理論 オートマトン 有限オートマトン 形式言語 文脈自由文法 正規表現 複雑さ

計算理論の基礎 [原著第2版] 1.オートマトンと言語

計算理論の基礎 [原著第2版] 1.オートマトンと言語

計算理論の基礎 [原著第2版] 2.計算可能性の理論

計算理論の基礎 [原著第2版] 2.計算可能性の理論

計算理論の基礎 [原著第2版] 3.複雑さの理論

計算理論の基礎 [原著第2版] 3.複雑さの理論

駆け足で読む『計算理論の基礎』第１巻：オートマトンと言語

駆け足で読むシリーズ 計算理論 オートマトン 有限オートマトン 形式言語 文脈自由文法 正規表現 複雑さ
  • 1 正規言語
    • 「計算機とは何か？」を理解するために計算をモデル化する
    • 計算機設計的な位置づけで「有限オートマトン」があり、文字列を読み取るという立場から正規表現がある
    • 1.1 有限オートマトン
      • 有限オートマトンの定義
        • ５個組Q,\Sigma,\delta,q_0,Fで決まる
          • Qは状態の有限集合
          • \Sigmaはアルファベットと呼ばれる有限集合
          • \delta:Q\times \Sigma \to Qは遷移関数
          • q_0 \in Qは開始状態
          • F \subset Qは最終状態の集合
      • 有限オートマトンが受理(認識する)する(最終状態として作る)文字列のすべての集合を、そのオートマトンの言語と言う
      • ある有限オートマトンで認識される言語を正規言語(regular language)という
      • 有限オートマトンの状態推移に確率的要素を加味するとマルコフ連鎖
      • 有限オートマトンとその言語の性質は、言語に成り立っている演算の性質として考えることができる
        • ２つの言語の和集合、２つの言語の積集合、１つの言語のアルファベットの列集合
      • 言語が定義する文字列かどうかを判定できること、ルールに従って判定できること、集合の内包表現の判定ができること、を目指しており、有限オートマトンはそのようなルールであり、それの機械上の実装が有限オートマトンを用いた計算機設計である
    • 1.2 非決定性
      • 既述の有限オートマトンでは文字列の並びに関して、想定するべき状態は１であった
      • 一つの文字列に対して想定するべき状態が複数になる可能性を許すと、その可能性(のすべて)を想定しながら読み進む必要がある
      • 並列処理に相当するとも言えるし、状態が分岐木になっているとも言える
      • 非決定性有限オートマトンの定義
        • ５個組Q,\Sigma,\delta,q_0,Fで決まる
          • Qは状態の有限集合
          • \Sigmaはアルファベットと呼ばれる有限集合
          • \delta:Q\times \Sigma_{\epsilon} \to P(Q)は遷移関数
          • q_0 \in Qは開始状態
          • F \subset Qは最終状態の集合
        • 前掲の有限オートマトンの定義から\deltaが変化した
        • \Sigma_{\epsilon}=\{\Sigma,\epsilon\}とし、ここで\epsilonは状態推移に関して「複数の可能性があるので、保留にしておく」意味合いである
        • P(Q)は集合Qのべき集合
      • 決定性有限オートマトンと非決定性有限オートマトンとは同じクラスの言語を認識する。このことを、決定性有限オートマトンと非決定性有限オートマトンが等価であると言う
    • 1.3 正規表現
    • 1.4 非正規言語
      • ある言語が正規でないことを証明すること
  • 2 文脈自由言語
    • 有限オートマトン〜正規表現では記述できない言語としての文脈自由言語
    • ヒトの言語の記述から発生
    • 再帰構造がある(名詞句と動詞句、名詞句内の動詞句、動詞句内の名詞句)
    • プログラミング言語の仕様記述・コンパイラ作成
    • 構文解析部(パーサー)
    • プッシュダウン・オートマトンが文脈自由言語に対応する
    • 2.1 文脈自由文法
      • 文脈自由文法の定義
        • ４個組V,\Sigma,R,S \in Vで決まる
          • Vは変数と呼ばれる有限集合
          • \Sigmaは終端記号と呼ばれるVと共通部分をもたない有限集合
          • Rは左辺が変数、右辺が変数と終端記号からなる文字列であるような変換規則の有限集合
          • Sは開始変数
      • 正規表現との違いは、推移関数でなく、変換規則と書かれている。後述のようにこの違いは、「スタック」を取り入れることに切り替えられる
    • 2.2 プッシュダウン・オートマトン
      • スタックと呼ばれる、情報を保持しておく装置が必要で、その保持した情報を取り出したり、保持領域に格納したりする作業が必要
      • プッシュダウンオートマトンの定義
        • ５個組Q,\Sigma,\Gamma,\delta,q_0,Fで決まる
          • Qは状態の集合
          • \Sigmaは入力アルファベットと呼ばれる集合
          • \Gammaはスタック・アルファベット
          • \delta:Q\times \Sigma_{\epsilon} \times \Gamma_{\epsilon} \to P(Q\ \Gamma_{\epsilon}は遷移関数
          • q_0 \in Qは開始状態
          • F \subset Qは最終状態の集合
    • 2.3 非文脈自由言語

駆け足で読む『計算理論の基礎』第２巻：計算可能性の理論

駆け足で読むシリーズ 計算理論 オートマトン 有限オートマトン 形式言語 文脈自由文法 正規表現 複雑さ
  • 第１巻より大幅に簡略して読む(勝手な都合)
  • 3 Church-Turing の提唱
    • 3.1 Turing 機械
      • 無限のメモリ・無限長のテープ
      • それでも解けない問題もある
    • 3.2 Turing 機械の変型
    • 3.3 アルゴリズムの定義
  • 4 判定可能性
    • 4.1 判定可能な言語
      • 言語クラス
        • 正規
        • 文脈自由
        • 判定可能
        • Turing 認識可能
    • 4.2 停止問題
  • 5 帰着可能性
    • 5.1 言語理論における判定不可能問題
    • 5.2 単純な判定不可能問題
    • 5.3 写像帰着可能性
  • 6 計算可能性の理論における先進的な話題
    • 6.1 再帰定理
    • 6.2 数理論理における判定可能性
    • 6.3 Turing 帰着可能性
    • 6.4 情報の定義

駆け足で読む『計算理論の基礎』第３巻：複雑さの理論

駆け足で読むシリーズ 計算理論 オートマトン 有限オートマトン 形式言語 文脈自由文法 正規表現 複雑さ
  • 7 時間の複雑さ
  • 8 領域の複雑さ
    • 8.1 Savitch の定理
    • 8.2 クラスPSPACE
    • 8.3 PSPACE 完全性
    • 8.4 クラスLとクラスNL
    • 8.5 NL完全性
    • 8.6 NLとcoNLの等価性
  • 9 問題の扱いにくさ
    • 9.1 階層定理
    • 9.2 相対化
    • 9.3 回路の複雑さ
  • 10 計算の複雑さの理論における先進的な話題