Kolmogorov complexity (original) (raw)
Kolmogorovská složitost je pojem z oboru teoretické informatiky, přesněji z . Pro daná data se jí rozumí délka nejstručnějšího počítačového programu (v předem daném programovacím jazyce), který taková data dokáže vygenerovat. Přesná hodnota složitosti různých dat je určena tím, jaký programovací jazyk je zvolen, ovšem volba jazyka má jen omezený vliv. Tento přístup ke složitosti objektů (a tím také ke komprimaci dat) popsal v roce 1963 sovětský matematik Andrej Nikolajevič Kolmogorov, po kterém je koncept pojmenován. Souběžně s ním byli průkopníky této teorie a .
| Property | Value |
|---|---|
| dbo:abstract | En la teoria de la computació, la complexitat de Kolmogórov és una mesura de la quantitat de recursos computacionals necessaris per poder descriure una certa quantitat d'informació, deu el seu nom a Andréi Kolmogórov. La complexitat de Kolmogórov també es denomina complexitat descriptiva o complexitat de Kolmogoróv-Chaitin, complexitat estocàstica, o entropia algorítmica. Per poder definir la complexitat de Kolmogórov, primer s'ha d'especificar un llenguatge descriptiu per a les seqüències o cadenes. Aquest llenguatge pot basar-se en qualsevol llenguatge de programació com ara Lisp o Pascal. Si P és un programa que genera com sortides seqüències de tipus x, llavors P és una descripció del conjunt de x. La longitud de la descripció és la longitud de P com a seqüència de caràcters. Per determinar la longitud de P, ha d'adonar-se de les longituds de totes les subrutines emprades en P. La longitud de qualsevol nombre enter n que aparegui en el programa P és la quantitat de bits requerits per representar n, això és, log₂n. (ca) Kolmogorovská složitost je pojem z oboru teoretické informatiky, přesněji z . Pro daná data se jí rozumí délka nejstručnějšího počítačového programu (v předem daném programovacím jazyce), který taková data dokáže vygenerovat. Přesná hodnota složitosti různých dat je určena tím, jaký programovací jazyk je zvolen, ovšem volba jazyka má jen omezený vliv. Tento přístup ke složitosti objektů (a tím také ke komprimaci dat) popsal v roce 1963 sovětský matematik Andrej Nikolajevič Kolmogorov, po kterém je koncept pojmenován. Souběžně s ním byli průkopníky této teorie a . (cs) تعقيد كولموغروف في نظرية المعلومات الخوارزمية (وهو حقل فرعي من علوم الكمبيوتر والرياضيات)، تعقيد كولموغروف كائن، مثل قطعة من النص، هو طول أقصر برنامج كمبيوتر (بلغة برمجة محددة سلفا) التي تنتج الكائن والإخراج. (ar) 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 somit eine beste Komprimierung der Zeichenkette an, ohne dass Information verloren geht. Wenn die Kolmogorow-Komplexität einer Zeichenkette mindestens so groß ist wie die Zeichenkette selbst, dann bezeichnet man die Zeichenkette als unkomprimierbar, zufällig oder auch strukturlos. Je näher die Kolmogorow-Komplexität an der Länge der Zeichenkette liegt, desto 'zufälliger' ist die Zeichenkette (und desto mehr Information enthält sie). Das Prinzip der Kolmogorow-Komplexität wurde unabhängig im Jahre 1964 von Ray Solomonoff, im Jahre 1965 von Andrei Kolmogorow und 1969 von Gregory Chaitin entwickelt, und hat Bezüge zur Shannonschen Informationstheorie. Die Kolmogorow-Komplexität wird manchmal auch Algorithmische Komplexität oder Beschreibungskomplexität genannt, darf aber nicht mit der Zeit- oder Raumkomplexität von Algorithmen verwechselt werden. Etwas präziser ist die Bezeichnung Algorithmischer Informationsgehalt, die auch die Verbindung zu dem Begriff des Informationsgehalts nach Shannon herstellt. Ein verwandter, aber deutlich abzugrenzender Ansatz ist die Algorithmische Tiefe, die sich auf den Aufwand bezieht, der betrieben werden muss, um eine bestimmte Nachricht zu erzeugen oder zu entschlüsseln. Die Algorithmische Informationstheorie von Gregory Chaitin präzisiert den Ansatz Kolmogorows in Bezug auf das Maschinenmodell. Jorma Rissanen beschreibt mit der Minimum Description Length ein ähnliches Konzept, das aber auf Komprimierung der Daten aufbaut. (de) En la teoría de la computación, la complejidad de Kolmogórov es el tamaño o cantidad de información del programa de computadora más corto que produce cierto resultado. Debe su nombre a Andréi Kolmogórov. La complejidad de Kolmogórov también se denomina complejidad descriptiva o complejidad de Kolmogoróv-Chaitin, complejidad estocástica, o entropía algorítmica. Para definir la complejidad de Kolmogórov, primero debe especificarse un lenguaje descriptivo para las secuencias o cadenas. Tal lenguaje puede basarse en cualquier lenguaje de programación como Lisp o Pascal. Si P es un programa que genera como salidas secuencias de tipo x, entonces P es una descripción del conjunto de x. La longitud de la descripción es la longitud de P como secuencia de caracteres. Para determinar la longitud de P, debe darse cuenta de las longitudes de todas las subrutinas empleadas en P. La longitud de cualquier número entero n que aparezca en el programa P es la cantidad de bits requeridos para representar n, esto es, log2n. (es) In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as algorithmic complexity, Solomonoff–Kolmogorov–Chaitin complexity, program-size complexity, descriptive complexity, or algorithmic entropy. It is named after Andrey Kolmogorov, who first published on the subject in 1963 and is a generalization of classical information theory. The notion of Kolmogorov complexity can be used to state and prove impossibility results akin to Cantor's diagonal argument, Gödel's incompleteness theorem, and Turing's halting problem.In particular, no program P computing a lower bound for each text's Kolmogorov complexity can return a value essentially larger than P's own length (see section ); hence no single program can compute the exact Kolmogorov complexity for infinitely many texts. (en) Dalam (subbidang dari ilmu komputer dan matematika), Kompleksitas Kolmogorov dari sebuah objek (misalnya sepotong teks), adalah panjang dari program komputer terpendek (dalam bahasa pemrograman yang telah ditentukan) yang menghasilkan objek sebagai keluaran. Kompleksitas ini adalah ukuran dari sumber daya yang dibutuhkan untuk menentukan objek, dan juga dikenal sebagai kompleksitas deskriptif Kolmogorov - , entropi algoritmik, atau kompleksitas ukuran program. Istilah ini dinamai sesuai Andrey Kolmogorov, yang pertama kali menerbitkan tulisan terkait subjek ini pada tahun 1963. Gagasan tentang kompleksitas Kolmogorov dapat digunakan untuk menyatakan dan sama dengan , Teorema ketidaklengkapan Gödel, dan . Secara khusus, tidak ada satu pun program P yang bisa menghitung batas bawah untuk setiap kompleksitas Kolmogorov teks yang dapat mengembalikan nilai yang pada dasarnya lebih besar dari panjang P sendiri; karenanya tidak ada satu program pun yang dapat menghitung kompleksitas Kolmogorov secara tepat untuk banyak teks yang tak terhingga. (in) En informatique théorique et en mathématiques, plus précisément en théorie de l'information, la complexité de Kolmogorov, ou complexité aléatoire, ou complexité algorithmique d'un objet — nombre, image numérique, chaîne de caractères — est la taille du plus petit algorithme (dans un certain langage de programmation fixé) qui engendre cet objet. Elle est nommée d'après le mathématicien Andreï Kolmogorov, qui publia sur le sujet dès 1963. Elle est aussi parfois nommée complexité de Kolmogorov-Solomonoff[réf. nécessaire][Par qui ?]. Cette quantité peut être vue comme une évaluation d'une forme de complexité de l'objet. (fr) Nella , la complessità di Kolmogorov (dal nome del matematico russo A. N. Kolmogorov) di un oggetto (assumendo che possa essere rappresentato come una sequenza di bit, per esempio un pezzo di testo), è la lunghezza del più breve programma informatico (in un dato linguaggio di programmazione) che produca l'oggetto come output. Una definizione alternativa è: la quantità di informazione contenuta in una data sequenza x espressa come la lunghezza del più breve programma che stampa x e si arresta. (it) 알고리즘 정보이론에서 콜모고로프 복잡도는 유한한 길이를 가진 데이터 열의 복잡성을 나타내는 지표 중 하나로서, 출력결과가 그 데이터에 일치하는 프로그램의 길이의 최솟값을 정의한다. 1963년 이것을 주제로 하여 발표한 안드레이 콜모고로프의 이름을 따서 지었으나 이보다 먼저 레이 솔로모노프(Ray Solomonoff)에 의해 제시된 바 있다. (ko) コルモゴロフ複雑性（コルモゴロフふくざつせい、英語: -shortKolmogorov complexity）とは、計算機科学において有限長のデータ列の複雑さを表す指標のひとつで、出力結果がそのデータに一致するプログラムの長さの最小値として定義される。コルモゴロフ複雑度、コルモゴロフ＝チャイティン複雑性 (Kolmogorov-Chaitin complexity) とも呼ばれる。 コルモゴロフ複雑性の概念は一見すると単純なものであるが、チューリングの停止問題やゲーデルの不完全性定理と関連する深遠な内容をもつ。コルモゴロフ複雑性やその他の文字列やデータ構造の複雑性の計量を研究する計算機科学の分野はアルゴリズム情報理論と呼ばれており、1960 年代末にアンドレイ・コルモゴロフ、レイ・ソロモノフ、グレゴリー・チャイティンによって創始された。 (ja) Złożoność Kołmogorowa – długość najkrótszego programu, który generuje dany łańcuch. Nazwa pojęcia pochodzi od nazwiska Andrieja Kołmogorowa. Rozwinięcie dziesiętne liczby pi, choć nieskończone, ma bardzo niską złożoność Kołmogorowa, ponieważ istnieje bardzo prosty program, który generuje dowolną liczbę jej cyfr. Złożoność Kołmogorowa jest różna dla różnych komputerów (ściślej – maszyn Turinga lub obiektów izomorficznych z nimi). Ze względu na nierozstrzygalność problemu stopu nie może istnieć algorytm obliczający złożoność Kołmogorowa z gwarancją sukcesu. (pl) De Kolmogorov-complexiteit of algoritmische complexiteit (ook bekend als de beschrijvende complexiteit, Kolmogorov-Chaitin-complexiteit, stochastische complexiteit, algoritmische entropie of programmagrootte complexiteit) is de mate waarin een model of systeem in wiskundige of algoritmische termen beschreven kan worden. Dit is het beginsel van de minimale beschrijvingslengte (Minimum Description Length Principle, MDL-principe), de lengte van het kortste computerprogramma om een datastructuur te genereren. Dit onderdeel van de (een deelgebied van de informatica), is genoemd naar de Russische wiskundige Andrej Kolmogorov. Neem bijvoorbeeld de volgende twee strings beide met lengte 64, elk bestaand uit alleen kleine letters, cijfers en spaties: abababababababababababababababababababababababababababababababab4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf De eerste string laat een korte beschrijving in de Nederlandse taal toe, namelijk "ab 32 keer". Deze beschrijving bestaat uit 10 tekens. De tweede string heeft geen onmiddellijk opvallende eenvoudige beschrijving (gebruikmakend van dezelfde tekenset), anders dan de gehele string zelf, die uit 64 tekens bestaat. Meer formeel gesproken is de complexiteit van een string de lengte van de kortste beschrijving van deze string in enige gegeven . De gevoeligheid van de complexiteit ten opzichte van de keuze van de beschrijvingstaal is van belang. Aangetoond kan worden dat de Kolmogorov-complexiteit van een willekeurige string niet veel groter kan zijn dan de lengte van deze string zelf. Strings waarvan de Kolmogorov-complexiteit klein is in verhouding tot de grootte van de string worden niet als complex beschouwd. De notie van Kolmogorov-complexiteit gaat verrassend diep en kan worden gebruikt om onmogelijkheidsresultaten, die verwant zijn aan onvolledigheidsstellingen van Gödel en stopprobleem van Turing te stellen en te bewijzen. (nl) A complexidade de Kolmogorov é uma teoria da informação e da aleatoriedade, profunda e sofisticada, que trata da quantidade de informação de objetos individuais, medida através do tamanho de sua menor descrição algorítmica. Ela é uma noção moderna de aleatoriedade, e refere-se a um conceito pontual de aleatoriedade, ao invés de uma aleatoriedade média como o faz a teoria das probabilidades. Ela é um ramo derivado da teoria da informação de Claude Shannon, embora hoje possa ser considerada uma área de pesquisa madura e autônoma. Complexidade de Kolmogorov define uma nova teoria da informação, chamada teoria algorítmica da informação (por tratar com algoritmos). A Máquina de Turing é usada como mecanismo para descrever os objetos (para definir os algoritmos). (pt) В алгоритмической теории информации колмогоровская сложность объекта (такого, как текст) есть мера вычислительных ресурсов, необходимых для точного определения этого объекта. Колмогоровская сложность также известна как описательная сложность, сложность Колмогорова — Хайтина, стохастическая сложность, алгоритмическая энтропия или алгоритмическая сложность. Выражает возможность фрактального описания. К примеру, рассмотрим две строки длиной 64 символа, содержащие только символы в нижнем регистре и цифры: abababababababababababababababababababababababababababababababab4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf Первая строка имеет простое описание на естественном языке, а именно ab 32 раза, состоящее из 10 символов. Вторая строка не имеет очевидного простого описания с использованием того же набора символов, кроме собственно самой этой строки, длина которой составляет 64 символа. Более формально, сложность строки — это длина описания этой строки на некотором универсальном . Способность сложности к изменению относительно выбора языка описания обсуждается ниже. Колмогоровская сложность любой строки не может быть более, чем на несколько байт больше, чем длина самой этой строки, так как программа может выглядеть как одна команда "напечатать строку", где строка указана в явном виде. Строки, чья колмогоровская сложность слабо зависит от размера самой строки, не считаются сложными. (ru) Kolmogorovkomplexiteten av ett objekt, såsom en textsträng, är ett mått på beräkningsresurserna som krävs för att specificera objektet eller med andra ord ett mått på hur kaotiskt objektet är. Det tillhör området och är döpt efter Andrej Kolmogorov, som publicerade artiklar under 60-talet om ämnet . Vi betraktar följande två strängar: 101010101010101010101010101010101010101010111000110100011111100001001010001001010000 Det är lätt att se vilken av dessa som är mer kaotisk. Den första strängen kan kort beskrivas som "10" skrivet 21 gånger. Den andra strängen blir däremot svårare att beskriva och har därmed högre Kolmogorovkomplexitet än den första. Som det formellt beskrivs nedan, mäter Kolmogorovkomplexiteten den minsta mängden resurser som behövs för att beskriva ett objekt. Men komplexiteten kan inte beräknas utan endast approximeras uppifrån. (sv) Складність та ентропія конструктивних об'єктів, відома як колмогоровська складність, складність Колмогорова, стохастична складність в алгоритмічній теорії інформації, складність об'єкту(або тексту) -- є міра обчислювальних ресурсів, що необхідні для того, щоб точно визначити цей об'єкт.Висловлює можливість фрактального опису.Наприклад, розглянемо два рядки довжиною 64 символу, що містять тільки символи в нижньому регістрі і цифри: abababababababababababababababababababababababababababababababab4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf Перший рядок має простий опис природною мовою, а саме ab 32 рази, що складається з 10 символів. Другий рядок не має очевидного простого опису з використанням того ж набору символів, крім власне самої цього рядка, довжина якої становить 64 символу. Більш формально, складність рядкa - це довжина опису цього рядка на деякій універсальній мові опису. Здатність складності до зміни стосовно вибору мови опису обговорюється нижче. Можна показати, що колмогорівська складність будь-якого рядка не може бути більшою кількох байт, ніж довжина самого цього рядка. Рядки, колгомівська складність яких слабко залежить від розміру самого рядка, не вважаються складними. (uk) 在算法信息论（计算机科学和数学的一个分支）中，一个对象比如一段文字的柯氏复杂性（亦作柯尔莫哥洛夫复杂性、描述复杂性、柯尔莫哥洛夫-复杂度、随机复杂度，或算法熵）是衡量描述这个对象所需要的信息量的一个尺度。柯氏复杂性是由安德雷·柯尔莫哥洛夫于1963年发现，所以用他的名字命名。 以下面的两个长度为64的字符串为例。 01010101010101010101010101010101010101010101010101010101010101011100100001100001110111101110110011111010010000100101011110010110 第一个字符串可以用中文简短地描述为“重复32个‘01’”。第二个字符串没有明显的简短描述。 一个字符串的柯氏复杂性（或者，区别如后）是这个字符串的最短描述的长度。换言之，一个字符串的柯氏复杂性是能够输出且仅输出这个字符串的最短计算机／图灵机程序的长度。 这样的定义导致在使用不同的描述语言或者不同的图灵机的时候柯氏复杂性不一样。所以在讨论柯氏复杂性的时候，通常都事先固定一个通用图灵机作为参照。可以证明在使用做参照的时候，对任意的图灵机，都存在一个仅决定于和的常数使得对所有的字符串相对于的柯氏复杂性（或者）和相对于的柯氏复杂性（或者）都满足 。根据这点，通常确定了一个参照图灵机后就用和表示柯氏复杂性（省略）。 不难证明，任何字符串的柯氏复杂度都不会比字符串自身的长度超过太多。类似与上文中的0101字符串，它的柯氏复杂度和字符串的长度关系不大，因此并不复杂。 與康托尔的对角论证法、哥德尔不完备定理和图灵的停机问题類似，柯氏复杂度的概念可以用于阐述和证明不可能性。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Mandelpart2_red.png?width=300 |
| dbo:wikiPageExternalLink | https://tromp.github.io/cl/cl.html http://www.csse.monash.edu.au/~dld/MML.html http://www.idsia.ch/~juergen/kolmogorov.html https://archive.org/details/introductiontoth00sips https://archive.org/details/courseinmathemat0000bell http://homepages.cwi.nl/~paulv/kolmogorov.html https://web.archive.org/web/20150215210504/http:/www.cs.umaine.edu/~chaitin/ https://web.archive.org/web/20180321163508/http:/kolmogorov.com/ http://www.idsia.ch/~juergen/ray.html http://www.csse.monash.edu.au/~dld http://www.csse.monash.edu.au/~dld/Occam.html |
| dbo:wikiPageID | 1635 (xsd:integer) |
| dbo:wikiPageLength | 41196 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124800985 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Bayesian_probability dbr:Proof_of_impossibility dbr:Q.E.D. dbr:Big-O_notation dbr:Algorithmic_information_theory dbr:Algorithmic_probability dbc:Algorithmic_information_theory dbr:List_of_important_publications_in_theoretical_computer_science dbr:Descriptive_complexity_theory dbr:Incompressible_string dbr:Interpreter_(computing) dbr:Levenshtein_distance dbr:Computable_function dbr:Mathematics dbr:Matthew_effect_(sociology) dbr:Measure_theory dbr:Entropy_(information_theory) dbr:Full_employment_theorem dbr:Grammar_induction dbr:Mutual_information dbr:Andrey_Kolmogorov dbr:Berry_paradox dbr:Leonid_Levin dbr:Lower_bound dbr:Blum_axioms dbc:Measures_of_complexity dbr:Complexity dbr:Computation dbr:Computer_program dbr:Computer_science dbr:String_(computer_science) dbr:Turing_complete dbr:Markov_information_source dbr:Data_compression dbr:Data_structure dbr:Gödel_numbering dbr:Ming_Li dbr:ASCII dbr:Algorithmically_random_sequence dbc:Information_theory dbr:Pascal_(programming_language) dbr:Berry's_paradox dbr:Formal_system dbr:Kolmogorov_structure_function dbr:Proof_by_contradiction dbr:Probability dbr:Randomness dbr:Gregory_Chaitin dbr:Gödel's_incompleteness_theorem dbr:Halting_problem dbr:Java_(programming_language) dbr:Sample_entropy dbc:Computational_complexity_theory dbc:Computability_theory dbr:Bit dbr:Code_golf dbr:Ray_Solomonoff dbr:Axiomatic_system dbc:Descriptive_complexity dbr:Marcus_Hutter dbr:Pigeonhole_principle dbr:Solomonoff's_theory_of_inductive_inference dbr:Natural_number dbr:Cantor's_diagonal_argument dbr:Chaitin's_constant dbr:Self-extracting_archive dbr:Chris_Wallace_(computer_scientist) dbr:Martingale_(probability_theory) dbr:Turing_machine dbr:Uniform_distribution_(discrete) dbr:Universal_Turing_machine dbr:Up_to dbr:Programming_language dbr:Multiple_discovery dbr:Lisp_programming_language dbr:Turing_degree dbr:Indirect_argument dbr:Inductive_inference dbr:Juergen_Schmidhuber dbr:File:Mandelpart2_red.png dbr:File:Kolmogorov_complexity_and_computable_lower_bounds_svg.svg dbr:Self-delimiting_program |
| dbp:wikiPageUsesTemplate | dbt:Compression_Methods dbt:Cite_book dbt:Cite_journal dbt:Cite_web dbt:Color dbt:Expand_section dbt:Main dbt:Reflist dbt:Rp dbt:See_also dbt:Short_description dbt:Slink dbt:Val dbt:Isbn dbt:Mathematical_logic |
| dcterms:subject | dbc:Algorithmic_information_theory dbc:Measures_of_complexity dbc:Information_theory dbc:Computational_complexity_theory dbc:Computability_theory dbc:Descriptive_complexity |
| gold:hypernym | dbr:Length |
| rdf:type | owl:Thing yago:WikicatMeasuresOfComplexity yago:Abstraction100002137 yago:Act100030358 yago:Action100037396 yago:Choice100161243 yago:Decision100162632 yago:Event100029378 yago:Maneuver100168237 yago:Measure100174412 yago:Move100165942 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity dbo:Album |
| rdfs:comment | Kolmogorovská složitost je pojem z oboru teoretické informatiky, přesněji z . Pro daná data se jí rozumí délka nejstručnějšího počítačového programu (v předem daném programovacím jazyce), který taková data dokáže vygenerovat. Přesná hodnota složitosti různých dat je určena tím, jaký programovací jazyk je zvolen, ovšem volba jazyka má jen omezený vliv. Tento přístup ke složitosti objektů (a tím také ke komprimaci dat) popsal v roce 1963 sovětský matematik Andrej Nikolajevič Kolmogorov, po kterém je koncept pojmenován. Souběžně s ním byli průkopníky této teorie a . (cs) تعقيد كولموغروف في نظرية المعلومات الخوارزمية (وهو حقل فرعي من علوم الكمبيوتر والرياضيات)، تعقيد كولموغروف كائن، مثل قطعة من النص، هو طول أقصر برنامج كمبيوتر (بلغة برمجة محددة سلفا) التي تنتج الكائن والإخراج. (ar) En informatique théorique et en mathématiques, plus précisément en théorie de l'information, la complexité de Kolmogorov, ou complexité aléatoire, ou complexité algorithmique d'un objet — nombre, image numérique, chaîne de caractères — est la taille du plus petit algorithme (dans un certain langage de programmation fixé) qui engendre cet objet. Elle est nommée d'après le mathématicien Andreï Kolmogorov, qui publia sur le sujet dès 1963. Elle est aussi parfois nommée complexité de Kolmogorov-Solomonoff[réf. nécessaire][Par qui ?]. Cette quantité peut être vue comme une évaluation d'une forme de complexité de l'objet. (fr) Nella , la complessità di Kolmogorov (dal nome del matematico russo A. N. Kolmogorov) di un oggetto (assumendo che possa essere rappresentato come una sequenza di bit, per esempio un pezzo di testo), è la lunghezza del più breve programma informatico (in un dato linguaggio di programmazione) che produca l'oggetto come output. Una definizione alternativa è: la quantità di informazione contenuta in una data sequenza x espressa come la lunghezza del più breve programma che stampa x e si arresta. (it) 알고리즘 정보이론에서 콜모고로프 복잡도는 유한한 길이를 가진 데이터 열의 복잡성을 나타내는 지표 중 하나로서, 출력결과가 그 데이터에 일치하는 프로그램의 길이의 최솟값을 정의한다. 1963년 이것을 주제로 하여 발표한 안드레이 콜모고로프의 이름을 따서 지었으나 이보다 먼저 레이 솔로모노프(Ray Solomonoff)에 의해 제시된 바 있다. (ko) コルモゴロフ複雑性（コルモゴロフふくざつせい、英語: -shortKolmogorov complexity）とは、計算機科学において有限長のデータ列の複雑さを表す指標のひとつで、出力結果がそのデータに一致するプログラムの長さの最小値として定義される。コルモゴロフ複雑度、コルモゴロフ＝チャイティン複雑性 (Kolmogorov-Chaitin complexity) とも呼ばれる。 コルモゴロフ複雑性の概念は一見すると単純なものであるが、チューリングの停止問題やゲーデルの不完全性定理と関連する深遠な内容をもつ。コルモゴロフ複雑性やその他の文字列やデータ構造の複雑性の計量を研究する計算機科学の分野はアルゴリズム情報理論と呼ばれており、1960 年代末にアンドレイ・コルモゴロフ、レイ・ソロモノフ、グレゴリー・チャイティンによって創始された。 (ja) Złożoność Kołmogorowa – długość najkrótszego programu, który generuje dany łańcuch. Nazwa pojęcia pochodzi od nazwiska Andrieja Kołmogorowa. Rozwinięcie dziesiętne liczby pi, choć nieskończone, ma bardzo niską złożoność Kołmogorowa, ponieważ istnieje bardzo prosty program, który generuje dowolną liczbę jej cyfr. Złożoność Kołmogorowa jest różna dla różnych komputerów (ściślej – maszyn Turinga lub obiektów izomorficznych z nimi). Ze względu na nierozstrzygalność problemu stopu nie może istnieć algorytm obliczający złożoność Kołmogorowa z gwarancją sukcesu. (pl) En la teoria de la computació, la complexitat de Kolmogórov és una mesura de la quantitat de recursos computacionals necessaris per poder descriure una certa quantitat d'informació, deu el seu nom a Andréi Kolmogórov. La complexitat de Kolmogórov també es denomina complexitat descriptiva o complexitat de Kolmogoróv-Chaitin, complexitat estocàstica, o entropia algorítmica. (ca) 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 somit eine beste Komprimierung der Zeichenkette an, ohne dass Information verloren geht. Das Prinzip der Kolmogorow-Komplexität wurde unabhängig im Jahre 1964 von Ray Solomonoff, im Jahre 1965 von Andrei Kolmogorow und 1969 von Gregory Chaitin entwickelt, und hat Bezüge zur Shannonschen Informationstheorie. (de) En la teoría de la computación, la complejidad de Kolmogórov es el tamaño o cantidad de información del programa de computadora más corto que produce cierto resultado. Debe su nombre a Andréi Kolmogórov. La complejidad de Kolmogórov también se denomina complejidad descriptiva o complejidad de Kolmogoróv-Chaitin, complejidad estocástica, o entropía algorítmica. (es) In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as algorithmic complexity, Solomonoff–Kolmogorov–Chaitin complexity, program-size complexity, descriptive complexity, or algorithmic entropy. It is named after Andrey Kolmogorov, who first published on the subject in 1963 and is a generalization of classical information theory. (en) Dalam (subbidang dari ilmu komputer dan matematika), Kompleksitas Kolmogorov dari sebuah objek (misalnya sepotong teks), adalah panjang dari program komputer terpendek (dalam bahasa pemrograman yang telah ditentukan) yang menghasilkan objek sebagai keluaran. Kompleksitas ini adalah ukuran dari sumber daya yang dibutuhkan untuk menentukan objek, dan juga dikenal sebagai kompleksitas deskriptif Kolmogorov - , entropi algoritmik, atau kompleksitas ukuran program. Istilah ini dinamai sesuai Andrey Kolmogorov, yang pertama kali menerbitkan tulisan terkait subjek ini pada tahun 1963. (in) De Kolmogorov-complexiteit of algoritmische complexiteit (ook bekend als de beschrijvende complexiteit, Kolmogorov-Chaitin-complexiteit, stochastische complexiteit, algoritmische entropie of programmagrootte complexiteit) is de mate waarin een model of systeem in wiskundige of algoritmische termen beschreven kan worden. Dit is het beginsel van de minimale beschrijvingslengte (Minimum Description Length Principle, MDL-principe), de lengte van het kortste computerprogramma om een datastructuur te genereren. Dit onderdeel van de (een deelgebied van de informatica), is genoemd naar de Russische wiskundige Andrej Kolmogorov. (nl) A complexidade de Kolmogorov é uma teoria da informação e da aleatoriedade, profunda e sofisticada, que trata da quantidade de informação de objetos individuais, medida através do tamanho de sua menor descrição algorítmica. Ela é uma noção moderna de aleatoriedade, e refere-se a um conceito pontual de aleatoriedade, ao invés de uma aleatoriedade média como o faz a teoria das probabilidades. Ela é um ramo derivado da teoria da informação de Claude Shannon, embora hoje possa ser considerada uma área de pesquisa madura e autônoma. (pt) В алгоритмической теории информации колмогоровская сложность объекта (такого, как текст) есть мера вычислительных ресурсов, необходимых для точного определения этого объекта. Колмогоровская сложность также известна как описательная сложность, сложность Колмогорова — Хайтина, стохастическая сложность, алгоритмическая энтропия или алгоритмическая сложность. Выражает возможность фрактального описания. К примеру, рассмотрим две строки длиной 64 символа, содержащие только символы в нижнем регистре и цифры: (ru) Kolmogorovkomplexiteten av ett objekt, såsom en textsträng, är ett mått på beräkningsresurserna som krävs för att specificera objektet eller med andra ord ett mått på hur kaotiskt objektet är. Det tillhör området och är döpt efter Andrej Kolmogorov, som publicerade artiklar under 60-talet om ämnet . Vi betraktar följande två strängar: 101010101010101010101010101010101010101010111000110100011111100001001010001001010000 (sv) Складність та ентропія конструктивних об'єктів, відома як колмогоровська складність, складність Колмогорова, стохастична складність в алгоритмічній теорії інформації, складність об'єкту(або тексту) -- є міра обчислювальних ресурсів, що необхідні для того, щоб точно визначити цей об'єкт.Висловлює можливість фрактального опису.Наприклад, розглянемо два рядки довжиною 64 символу, що містять тільки символи в нижньому регістрі і цифри: abababababababababababababababababababababababababababababababab4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf (uk) 在算法信息论（计算机科学和数学的一个分支）中，一个对象比如一段文字的柯氏复杂性（亦作柯尔莫哥洛夫复杂性、描述复杂性、柯尔莫哥洛夫-复杂度、随机复杂度，或算法熵）是衡量描述这个对象所需要的信息量的一个尺度。柯氏复杂性是由安德雷·柯尔莫哥洛夫于1963年发现，所以用他的名字命名。 以下面的两个长度为64的字符串为例。 01010101010101010101010101010101010101010101010101010101010101011100100001100001110111101110110011111010010000100101011110010110 第一个字符串可以用中文简短地描述为“重复32个‘01’”。第二个字符串没有明显的简短描述。 一个字符串的柯氏复杂性（或者，区别如后）是这个字符串的最短描述的长度。换言之，一个字符串的柯氏复杂性是能够输出且仅输出这个字符串的最短计算机／图灵机程序的长度。 这样的定义导致在使用不同的描述语言或者不同的图灵机的时候柯氏复杂性不一样。所以在讨论柯氏复杂性的时候，通常都事先固定一个通用图灵机作为参照。可以证明在使用做参照的时候，对任意的图灵机，都存在一个仅决定于和的常数使得对所有的字符串相对于的柯氏复杂性（或者）和相对于的柯氏复杂性（或者）都满足 。根据这点，通常确定了一个参照图灵机后就用和表示柯氏复杂性（省略）。 (zh) |
| rdfs:label | تعقيد كولموغروف (ar) Complexitat de Kolmogórov (ca) Kolmogorovská složitost (cs) Kolmogorow-Komplexität (de) Complejidad de Kolmogórov (es) Kompleksitas Kolmogorov (in) Complexité de Kolmogorov (fr) Complessità di Kolmogorov (it) Kolmogorov complexity (en) 콜모고로프 복잡도 (ko) コルモゴロフ複雑性 (ja) Kolmogorov-complexiteit (nl) Complexidade de Kolmogorov (pt) Złożoność Kołmogorowa (pl) Колмогоровская сложность (ru) Kolmogorovkomplexitet (sv) Колмогоровська складність (uk) 柯氏复杂性 (zh) |
| rdfs:seeAlso | dbr:Algorithmic_randomness |
| owl:sameAs | freebase:Kolmogorov complexity yago-res:Kolmogorov complexity wikidata:Kolmogorov complexity dbpedia-ar:Kolmogorov complexity dbpedia-ca:Kolmogorov complexity dbpedia-cs:Kolmogorov complexity dbpedia-de:Kolmogorov complexity dbpedia-es:Kolmogorov complexity dbpedia-et:Kolmogorov complexity dbpedia-fa:Kolmogorov complexity dbpedia-fr:Kolmogorov complexity dbpedia-gl:Kolmogorov complexity dbpedia-he:Kolmogorov complexity dbpedia-id:Kolmogorov complexity dbpedia-it:Kolmogorov complexity dbpedia-ja:Kolmogorov complexity dbpedia-ko:Kolmogorov complexity dbpedia-nl:Kolmogorov complexity dbpedia-pl:Kolmogorov complexity dbpedia-pt:Kolmogorov complexity dbpedia-ru:Kolmogorov complexity dbpedia-sv:Kolmogorov complexity dbpedia-tr:Kolmogorov complexity dbpedia-uk:Kolmogorov complexity dbpedia-zh:Kolmogorov complexity https://global.dbpedia.org/id/Tsac |
| prov:wasDerivedFrom | wikipedia-en:Kolmogorov_complexity?oldid=1124800985&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Kolmogorov_complexity_and_computable_lower_bounds_svg.svg wiki-commons:Special:FilePath/Mandelpart2_red.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Kolmogorov_complexity |
| is dbo:knownFor of | dbr:Paul_Vitányi dbr:Peter_Gacs dbr:Gregory_Chaitin dbr:Jean-Louis_Dessalles |
| is dbo:wikiPageRedirects of | dbr:Conditional_Kolmogorov_complexity dbr:Algorithmic_entropy dbr:Chaitin's_incompleteness_theorem dbr:Chaitin-Kolmogorov_randomness dbr:Kolmogorov_Complexity dbr:Kolmogorov_randomness dbr:Kolgomorov_complexity dbr:Chaitin_Complexity dbr:Chaitin–Kolmogorov_randomness dbr:Conditional_complexity dbr:Program-size_complexity dbr:Algorithmic_complexity_theory dbr:Compressibility_(computer_science) dbr:K-complexity dbr:Kolmogorov-Chaitin_complexity dbr:Kolmogorov-Chaitin_randomness dbr:Kolmogorov/Chaitin_complexity dbr:Kolmogorov–Chaitin_complexity dbr:Kolmogorov–Chaitin_randomness dbr:Stochastic_complexity |
| is dbo:wikiPageWikiLink of | dbr:Bekenstein_bound dbr:Proof_of_impossibility dbr:Entropic_vector dbr:Entropy_compression dbr:List_of_computer_scientists dbr:Multiverse dbr:No_free_lunch_in_search_and_optimization dbr:Normalized_compression_distance dbr:Time_series dbr:Progress_in_artificial_intelligence dbr:Bernhard_Schölkopf dbr:Algorithmic_information_theory dbr:Algorithmic_probability dbr:Alignment-free_sequence_analysis dbr:List_of_important_publications_in_theoretical_computer_science dbr:Paul_Vitányi dbr:Per_Martin-Löf dbr:Peter_Gacs dbr:Universality_probability dbr:University_of_Chicago dbr:Vahe_Gurzadyan dbr:Incompressibility_method dbr:Incompressible_string dbr:Inductive_logic_programming dbr:Inductive_probability dbr:Information_and_Computation dbr:Information_distance dbr:Information_panspermia dbr:List_of_multiple_discoveries dbr:Invariance_theorem dbr:Nothing-up-my-sleeve_number dbr:Complexity_measure dbr:Computability_theory dbr:Computable_function dbr:Conditional_Kolmogorov_complexity dbr:Analogy dbr:Mathematical_beauty dbr:General_semantics dbr:Low-complexity_art dbr:Timeline_of_mathematical_logic dbr:Entropy_(information_theory) dbr:Grammar_induction dbr:Mutual_information dbr:Content_similarity_detection dbr:Statistical_inference dbr:Andrey_Kolmogorov dbr:Lossless_compression dbr:Complexity dbr:Computer_science dbr:Busy_beaver dbr:Active_networking dbr:Turing_test dbr:Data_compression dbr:Gödel_numbering dbr:K-trivial_set dbr:Landauer's_principle dbr:Language_identification dbr:Logical_depth dbr:Ming_Li dbr:Algorithmically_random_sequence dbr:Executable_compression dbr:Bremermann's_limit dbr:No_free_lunch_theorem dbr:Kolmogorov_structure_function dbr:Lempel–Ziv_complexity dbr:List_of_Russian_mathematicians dbr:List_of_Russian_scientists dbr:Algorithmic_entropy dbr:Regular_language dbr:Gregory_Chaitin dbr:Gödel's_incompleteness_theorems dbr:Halting_problem dbr:Heilbronn_triangle_problem dbr:Jean-Louis_Dessalles dbr:Hutter_Prize dbr:Margolus–Levitin_theorem dbr:Straight-line_grammar dbr:Speed_prior dbr:Sample_entropy dbr:Chaitin's_incompleteness_theorem dbr:Chaitin-Kolmogorov_randomness dbr:Binary_combinatory_logic dbr:Code_golf dbr:Cognitive_complexity dbr:Effective_complexity dbr:Effective_dimension dbr:Ray_Solomonoff dbr:CMB_cold_spot dbr:Solomonoff's_theory_of_inductive_inference dbr:Indian_Statistical_Institute dbr:Inductive_reasoning dbr:Information_theory dbr:Instruction_set_architecture dbr:Algorithmic_complexity dbr:Kolmogorov_Complexity dbr:Kolmogorov_randomness dbr:Kolmogorov–Zurbenko_filter dbr:Minimum_description_length dbr:Minimum_message_length dbr:Chain_rule_for_Kolmogorov_complexity dbr:Chaitin's_constant dbr:Self-extracting_archive dbr:Wojciech_H._Zurek dbr:Shellsort dbr:Undecidable_problem dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:List_of_undecidable_problems dbr:Occam's_razor dbr:Specified_complexity dbr:Kolgomorov_complexity dbr:Symbolic_regression dbr:Simplicity_theory dbr:Sophistication_(complexity_theory) dbr:List_of_Russian_people dbr:Structural_information_theory dbr:Random_sequence dbr:Randomness_test dbr:Chaitin_Complexity dbr:Chaitin–Kolmogorov_randomness dbr:Conditional_complexity dbr:Program-size_complexity dbr:Algorithmic_complexity_theory dbr:Compressibility_(computer_science) dbr:K-complexity dbr:Kolmogorov-Chaitin_complexity dbr:Kolmogorov-Chaitin_randomness dbr:Kolmogorov/Chaitin_complexity dbr:Kolmogorov–Chaitin_complexity dbr:Kolmogorov–Chaitin_randomness dbr:Stochastic_complexity |
| is dbp:knownFor of | dbr:Paul_Vitányi dbr:Gregory_Chaitin dbr:Jean-Louis_Dessalles |
| is rdfs:seeAlso of | dbr:Per_Martin-Löf |
| is foaf:primaryTopic of | wikipedia-en:Kolmogorov_complexity |
