Kolmogorov complexity

Kolmogorov complexity
The complexity of an information object—such as a book or an image—informally defined as the length of the shortest program that produces that information object.

Wikipedia foundation.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Kolmogorov complexity — In algorithmic information theory (a subfield of computer science), the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object. It is named after Soviet Russian… …   Wikipedia

  • Chain rule for Kolmogorov complexity — The chain rule for Kolmogorov complexity is an analogue of the chain rule for information entropy, which states: H(X,Y) = H(X) + H(Y | X) That is, the combined randomness of two sequences X and Y is the sum of the randomness of X plus whatever… …   Wikipedia

  • Complexity — For other uses, see Complexity (disambiguation). In general usage, complexity tends to be used to characterize something with many parts in intricate arrangement. The study of these complex linkages is the main goal of complex systems theory. In… …   Wikipedia

  • Complexity (disambiguation) — In general usage, complexity tends to be used to characterize something with many parts in intricate arrangement. Complexity may also refer to: Complex systems Complexity theory (disambiguation) Kolmogorov complexity Los Angeles Complexity, a… …   Wikipedia

  • Kolmogorov-Entropie — Die Kolmogorow Komplexität (nach Andrei Nikolajewitsch Kolmogorow) ist ein Maß für die Strukturiertheit einer Zeichenkette und ist durch die Länge des kürzesten Programms gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Programm gibt… …   Deutsch Wikipedia

  • Kolmogorov-Komplexität — Die Kolmogorow Komplexität (nach Andrei Nikolajewitsch Kolmogorow) ist ein Maß für die Strukturiertheit einer Zeichenkette und ist durch die Länge des kürzesten Programms gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Programm gibt… …   Deutsch Wikipedia

  • Kolmogorov structure function — (KSF) is used in the algorithmic theory of complexity for describing the structure of a string by use of models (programs) of increasing complexity …   Wikipedia

  • Andrey Kolmogorov — Infobox Scientist name = Andrey Kolmogorov birth date = birth date|1903|4|25 birth place = Tambov, Imperial Russia nationality = Russian death date = death date and age|1987|10|20|1903|4|25 death place = Moscow, USSR field = Mathematician work… …   Wikipedia

  • Specified complexity — Part of a series of articles on Intelligent design …   Wikipedia

  • Cognitive complexity — Psychology Cognitive psychology Perception …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”