akkun_choi pedia
mindia › akkun_choi pedia › 単語

コルモゴロフ複雑性

akkun_choi · 2009-08-27 更新 · 1 ポイント · 履歴(4)
第 1 版(2009-08-28 00:42:00 · akkun_choi)を表示しています。 最新版に戻る

「ランダムっぽい」というのを計る指標はないかとググったら、これがひっかかった。

対象と同じものを出力するプログラムのうち最小のものが、その対象のコルモゴロフ複雑性となる。

例えば、
「010101010101010101010101010101010101010101010101」は
「print "010101010101010101010101010101010101010101010101"」としてプログラムを記述できるが元のデータより長くなる。
「print "01" x 24」とすれば元のデータより少ないデータ量で記述できる。なので、複雑性はたかだか「print "01" x 24」の文字数分となる

履歴

タグ