|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ コルモゴロフ ： [こるもごろふ] (n) Kolmogorov, (n) Kolmogorov ・ 複 ： [ふく] 1. (n,pref) double 2. compound ・ 複雑 ： [ふくざつ] 1. (adj-na,n) complexity 2. complication ・ 雑 ： [ざつ] 1. (adj-na,n) rough 2. crude
コルモゴロフ複雑性（コルモゴロフふくざつせい、）とは、計算機科学において有限長のデータ列の複雑さを表す指標のひとつで、出力結果がそのデータに一致するプログラムの長さの最小値として定義される。コルモゴロフ複雑度、コルモゴロフ＝チャイティン複雑性 () とも呼ばれる。 コルモゴロフ複雑性の概念は一見すると単純なものであるが、チューリングの停止問題やゲーデルの不完全性定理と関連する深遠な内容をもつ。コルモゴロフ複雑性やその他の文字列やデータ構造の複雑性の計量を研究する計算機科学の分野はアルゴリズム情報理論と呼ばれており、1960 年代末にアンドレイ・コルモゴロフ、レイ・ソロモノフ、グレゴリー・チャイティンによって創始された。 ==定義== 厳密には、ある有限長の文字列 ''x'' として表されるデータ列のある万能計算機 ''u'' におけるコルモゴロフ複雑性は以下の式で定義される: : ここで、''p'' は計算機 ''u'' のためのプログラムであり、''u''(''p'') はそれを実行したときに出力される文字列である。''l''(''p'') はプログラムの長さを表す。ただし、プログラムは入力をもたず、つねに決まった出力を返すようなものとする。 ここで万能計算機とは万能チューリングマシンと同等の能力をもつ計算機を意味し、例えば C など通常のプログラム言語を解釈し実行するような処理系だと考えてよい。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「コルモゴロフ複雑性」の詳細全文を読む スポンサード リンク
|