誰にも見えないブログ

雑なメモ。まとまってない文章等

papa本第7回メモ

進捗

「2.4 VIEW SERIALIZABILITY」から読んだ

次回はp34のproofから読む。(今回読んだが時間不足&理解不足)

なお次回予定日(8/7)も中止なので、次回は(8/28)

書籍紹介

開始前に簡単な書籍の紹介。主にP,NP問題について書かれているもの。NP完全の説明はアルゴリズムデザインが最もわかりやすいらしい

アルゴリズムデザイン

アルゴリズムデザイン

複雑さの階層 (アルゴリズム・サイエンスシリーズ―数理技法編)

複雑さの階層 (アルゴリズム・サイエンスシリーズ―数理技法編)

Computational Complexity

Computational Complexity

  • 作者: Christos H. Papadimitriou
  • 出版社/メーカー: Addison Wesley
  • 発売日: 1993/11/30
  • メディア: ペーパーバック
  • 購入: 1人 クリック: 1回
  • この商品を含むブログを見る

議論、読書内容

  • FSR と VSRは別物?
    • VSR ⊆ FSRではないとする派閥があるらしい
    • Multi Versionを考えるときに重要なポイントになりそう。
  • dead stepが存在しないFSRがVSR
    • そもそもVSRにdead stepはあるか
    • epochベースならdeadが存在する
      • 読めないのでそれはdead stepと言わないのではないか?
  • 制御構文(条件分岐)が存在しないアプリならFSRで十分。あればVSRを使いたい。
  • free schema
    • loop unwound
    • ループのインライン展開のようなものか

en.wikipedia.org

  • P32:predicateを含めたinterpretation -> full interpretation
  • p33のlegalとpiの定義が難しい
    • 同じ値を読めば同じstepsが出てくる?
    • 読んだものでstepが一意に決まればlegal
    • Predicate Pの条件分岐をP以前のreadしたentitiyのドメインの直積で表現する
      • その決定表に適合した分岐をしていればlegal
    • 乱数は含められるのか
    • 未来から見れば全てdeterministic(名言)
  • legalとpredicateはちゃんとやったほうがいい
    • legalとView SerializeのProofを次回もう一度やり直す
    • 神林さんは本書のVSRのNP完全の証明に異議があるらしい
      • 近日ブログを書かれる予定
  • order theory
    • いきなりtotal orderが出てくると怪しい
    • partial orderでlinear extensionできるとtotal order
  • order theoryも進化しているらしい。

Partial Order Concepts in Applied Sciences (English Edition)

Partial Order Concepts in Applied Sciences (English Edition)

個人的にπがよくわかりませんでした。(要復習)