Yabu.log

ITなどの雑記

computer science

Transaction,Concurrency ControlとAntichain

グラフのトポロジカルソート可/不可のみでアノマリーの検査やSerializabilityの判断をするのではなく、Order Theoryの知見をConcurrency Conntrolに活用しようという動きがあるらしい。そしてantichainというorder theoryの概念がわからなかったのでそのメモ…

NPクラスのNondeterministic polynominal algorithmについて

4部作その3。組合せ最適化のページ(p422~423)の理解メモです。100回くらい同じページを読んだ結果、本書の記述だけだと不十分に感じたの類書を参考にしています。 組合せ最適化 第2版 (理論とアルゴリズム)作者: B.コルテ,J.フィーゲン,浅野孝夫,浅野泰仁,小…

PとNPについて

4部作その2。組み合わせ最適化第二版のp419~421の理解メモです。前回の決定問題の知識を前提に記事を書いています。 yuyubu.hatenablog.com 組合せ最適化 第2版 (理論とアルゴリズム)作者: B.コルテ,J.フィーゲン,浅野孝夫,浅野泰仁,小野孝男,平田富夫出版社…

NP問題における決定問題とはなにか

アルゴリズムの話をする際に良く出てくるPやNP、NP完全というものを一度きちんと勉強しておきたいと思いブログを書いていましたが、長くなりすぎたため4部作にしました(本記事はpart1)。本記事では下準備としてNP問題であるための条件「決定問題」というもの…