La complexité de Kolmogorov (nommée d'après le mathématicien Andreï Kolmogorov), nommée aussi complexité aléatoire, ou complexité algorithmique, est une fonction permettant de quantifier la taille du plus petit algorithme nécessaire pour engendrer un nombre ou une suite quelconque de caractères.

PropertyValue
dbpedia-owl:abstract
  • La complexité de Kolmogorov (nommée d'après le mathématicien Andreï Kolmogorov), nommée aussi complexité aléatoire, ou complexité algorithmique, est une fonction permettant de quantifier la taille du plus petit algorithme nécessaire pour engendrer un nombre ou une suite quelconque de caractères. Cette quantité peut être vue comme une évaluation d'une forme de complexité de cette suite de caractères.
  • Kolmogorov karmaşıklığı (tanımsal karmaşıklık, Kolmogorov-Chaitin karmaşıklığı, stokastik karmaşıklık, algoritmik entropi veya program boyu karmaşıklığı olarak da bilinir), bilgisayar biliminde, bir metin parçası gibi bir nesneyi tanımlamak için kullanılması gereken bilgi işlemsel kaynakların ölçüsü.Örneğin aşağıdaki 100 karakter uzunluğundaki iki karakter katarı ele alınırsa:01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101011100100001100001110111101110110011111010010000100101011110010110001101111111010001100011011001110111Birinci karakter katarı Türkçe "'01'in 50 tekrarı" ifadesi ile kısaca ve tam olarak tanımlanabilir. İkinci karakter katarının bu şekilde tanımlanması mümkün değildir. Bu karakter katarını tanımlananın en kısa yolu kendisini yazmaktır.Daha şekilsel olarak söylemek gerekirse, bir karakter katarının karmaşıklığı sabit bir tanımlama dilinde o karakter katarının en kısa ifade edilişidir. Aşağıda tanımlama dilinin seçimi ile karmaşıklık arasındaki hassas ilişki ele alınmıştır. Bir karakter katarının Kolmogorov karmaşıklığının karakter katarının uzunluğundan daha büyük olamayacağı gösterilebilir. Kolmogorov karmaşıklıkları, kendi uzunluklarına kıyasla daha kısa olan karakter katarları karmaşık kabul edilmez.Kolmogorov karmaşıklığı kavramı şaşırtıcı ölçüde derin bir kavramdır. Bu kavram kullanılarak Gödel'in eksiklik teoremi ve Turing'in durma problemi ile ilgili imkânsızlık sonuçlarını ifade ve ispat için kullanılabilir.Algoritmik bilgi teorisi, bilgisayar bilimlerinin bir alt alanı olup karakter katarlarının (ve diğer veri yapılarının) Kolmogorov karmaşıklığı ve diğer türden karmaşıklarını incelenmesi ile ilgilidir. Bu çalışma alanı Andrey Kolmogorov, Ray Solomonoff ve Gregory Chaitin tarafından 1960larda kurulmuştur. Algoritmik bilgi veya Kolmogorov karmaşıklığının pek çok çeşitlemesi vardır. Bunlardan en yaygın olanı kendi kendini ayıran programlara dayanmaktadır ve Leonid Levin (1974) tarafından ortaya konmuştur.
  • En la teoría de la computación, la complejidad de Kolmogórov es una medida de la cantidad de recursos computacionales necesarios para describir una cierta cantidad de información, 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.
  • Złożoność Kołmogorowa – dla łańcucha symboli, skończonego lub nieskończonego, to 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 problem stopu nie może istnieć algorytm obliczający złożoność Kołmogorowa z gwarancją sukcesu.
  • 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 algoritmische informatietheorie (een deelgebied van de informatica), is genoemd naar 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 universele beschrijvingstaal. 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.
  • コルモゴロフ複雑性(コルモゴロフふくざつせい、英語: Kolmogorov complexity)とは、計算機科学において有限長のデータ列の複雑さを表す指標のひとつで、出力結果がそのデータに一致するプログラムの長さの最小値として定義される。コルモゴロフ複雑度、コルモゴロフ=チャイティン複雑性 (Kolmogorov-Chaitin complexity) とも呼ばれる。コルモゴロフ複雑性の概念は一見すると単純なものであるが、チューリングの停止問題やゲーデルの不完全性定理と関連する深遠な内容をもつ。コルモゴロフ複雑性やその他の文字列やデータ構造の複雑性の計量を研究する計算機科学の分野はアルゴリズム情報理論と呼ばれており、1960 年代末にアンドレイ・コルモゴロフ、レイ・ソロモノフ、グレゴリー・チャイティンによって創始された。
  • 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).
  • 알고리즘 정보이론에서 콜모고로프 복잡도는 유한한 길이의 데이터 열에 복잡성을 나타내는 지표중 하나로서, 출력결과가 그 데이터에 일치하는 프로그램의 길이의 최소값을 정의한다. 1963년 이것을 주제로 하여 발표한 안드레이 콜모고르프의 이름을 따서 지었다..
  • In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov–Chaitin complexity, algorithmic entropy, or program-size complexity) of an object, such as a piece of text, is a measure of the computability resources needed to specify the object. It is named after Andrey Kolmogorov, who first published on the subject in 1963.For example, consider the following two strings of 32 lowercase letters and digits:abababababababababababababababab4c1j5b2p0cv4w1x8rx2y39umgw5q85s7The first string has a short English-language description, namely "ab 16 times", which consists of 11 characters. The second one has no obvious simple description (using the same character set) other than writing down the string itself, which has 32 characters.More formally, the complexity of a string is the length of the shortest possible description of the string in some fixed universal description language (the sensitivity of complexity relative to the choice of description language is discussed below). It can be shown that the Kolmogorov complexity of any string cannot be more than a few bytes larger than the length of the string itself. Strings, like the abab example above, whose Kolmogorov complexity is small relative to the string's size are not considered to be complex.The notion of the Kolmogorov complexity can be used to state and prove impossibility results akin to Gödel's incompleteness theorem and Turing's halting problem.
  • В алгоритмической теории информации колмогоровская сложность объекта (такого, как текст) есть мера вычислительных ресурсов, необходимых для точного определения этого объекта.Колмогоровская сложность также известна как описательная сложность, сложность Колмогорова — Хайтина, стохастическая сложность, алгоритмическая энтропия или алгоритмическая сложность.Выражает возможность фрактального описания.К примеру, рассмотрим две строки длиной 64 символа, содержащие только символы в нижнем регистре и цифры:abababababababababababababababababababababababababababababababab4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzfПервая строка имеет простое описание на естественном языке, а именно ab 32 раза, состоящее из 10 символов. Вторая строка не имеет очевидного простого описания с использованием того же набора символов, кроме собственно самой этой строки, длина которой составляет 64 символа.Более формально, сложность строки — это длина описания этой строки на некотором универсальном языке описания. Способность сложности к изменению относительно выбора языка описания обсуждается ниже. Можно показать, что колмогоровская сложность любой строки не может быть более, чем на несколько байт больше, чем длина самой этой строки. Строки, чья колмогоровская сложность слабо зависит от размера самой строки, не считаются сложными.
  • 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 R. J. 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.
dbpedia-owl:wikiPageExternalLink
dbpedia-owl:wikiPageID
  • 228873 (xsd:integer)
dbpedia-owl:wikiPageLength
  • 7707 (xsd:integer)
dbpedia-owl:wikiPageOutDegree
  • 31 (xsd:integer)
dbpedia-owl:wikiPageRevisionID
  • 111069117 (xsd:integer)
dbpedia-owl:wikiPageWikiLink
prop-fr:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • La complexité de Kolmogorov (nommée d'après le mathématicien Andreï Kolmogorov), nommée aussi complexité aléatoire, ou complexité algorithmique, est une fonction permettant de quantifier la taille du plus petit algorithme nécessaire pour engendrer un nombre ou une suite quelconque de caractères.
  • コルモゴロフ複雑性(コルモゴロフふくざつせい、英語: Kolmogorov complexity)とは、計算機科学において有限長のデータ列の複雑さを表す指標のひとつで、出力結果がそのデータに一致するプログラムの長さの最小値として定義される。コルモゴロフ複雑度、コルモゴロフ=チャイティン複雑性 (Kolmogorov-Chaitin complexity) とも呼ばれる。コルモゴロフ複雑性の概念は一見すると単純なものであるが、チューリングの停止問題やゲーデルの不完全性定理と関連する深遠な内容をもつ。コルモゴロフ複雑性やその他の文字列やデータ構造の複雑性の計量を研究する計算機科学の分野はアルゴリズム情報理論と呼ばれており、1960 年代末にアンドレイ・コルモゴロフ、レイ・ソロモノフ、グレゴリー・チャイティンによって創始された。
  • 알고리즘 정보이론에서 콜모고로프 복잡도는 유한한 길이의 데이터 열에 복잡성을 나타내는 지표중 하나로서, 출력결과가 그 데이터에 일치하는 프로그램의 길이의 최소값을 정의한다. 1963년 이것을 주제로 하여 발표한 안드레이 콜모고르프의 이름을 따서 지었다..
  • 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.
  • 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.
  • In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov–Chaitin complexity, algorithmic entropy, or program-size complexity) of an object, such as a piece of text, is a measure of the computability resources needed to specify the object.
  • В алгоритмической теории информации колмогоровская сложность объекта (такого, как текст) есть мера вычислительных ресурсов, необходимых для точного определения этого объекта.Колмогоровская сложность также известна как описательная сложность, сложность Колмогорова — Хайтина, стохастическая сложность, алгоритмическая энтропия или алгоритмическая сложность.Выражает возможность фрактального описания.К примеру, рассмотрим две строки длиной 64 символа, содержащие только символы в нижнем регистре и цифры:abababababababababababababababababababababababababababababababab4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzfПервая строка имеет простое описание на естественном языке, а именно ab 32 раза, состоящее из 10 символов.
  • Kolmogorov karmaşıklığı (tanımsal karmaşıklık, Kolmogorov-Chaitin karmaşıklığı, stokastik karmaşıklık, algoritmik entropi veya program boyu karmaşıklığı olarak da bilinir), bilgisayar biliminde, bir metin parçası gibi bir nesneyi tanımlamak için kullanılması gereken bilgi işlemsel kaynakların ölçüsü.Örneğin aşağıdaki 100 karakter uzunluğundaki iki karakter katarı ele alınırsa:01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101011100100001100001110111101110110011111010010000100101011110010110001101111111010001100011011001110111Birinci karakter katarı Türkçe "'01'in 50 tekrarı" ifadesi ile kısaca ve tam olarak tanımlanabilir.
  • En la teoría de la computación, la complejidad de Kolmogórov es una medida de la cantidad de recursos computacionales necesarios para describir una cierta cantidad de información, 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.
  • Złożoność Kołmogorowa – dla łańcucha symboli, skończonego lub nieskończonego, to 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).
  • 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.
rdfs:label
  • Complexité de Kolmogorov
  • Complejidad de Kolmogórov
  • Complexidade de Kolmogorov
  • Kolmogorov complexity
  • Kolmogorov karmaşıklığı
  • Kolmogorov-complexiteit
  • Kolmogorow-Komplexität
  • Złożoność Kołmogorowa
  • Колмогоровская сложность
  • コルモゴロフ複雑性
  • 콜모고로프 복잡도
owl:sameAs
http://www.w3.org/ns/prov#wasDerivedFrom
foaf:isPrimaryTopicOf
is dbpedia-owl:wikiPageRedirects of
is dbpedia-owl:wikiPageWikiLink of
is foaf:primaryTopic of