| dbpprop:abstract
|
- In algorithmic information theory (a subfield of computer science), the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov-Chaitin complexity, stochastic complexity, algorithmic entropy, or program-size complexity) of an object such as a piece of text is a measure of the computational resources needed to specify the object. For example, consider the following two strings of length 64, each containing only lowercase letters, numbers, and spaces: abababababababababababababababababababababababababababababababab 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf The first string admits a short English language description, namely "ab 32 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 64 characters. More formally, the complexity of a string is the length of the string's shortest description 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 too much larger than the length of the string itself. Strings whose Kolmogorov complexity is small relative to the string's size are not considered to be complex. The notion of Kolmogorov complexity is surprisingly deep and can be used to state and prove impossibility results akin to Gödel's incompleteness theorem and Turing's halting problem.
- Die Kolmogorow-Komplexität 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, ohne dass Information verlorengeht. Wenn die Kolmogorow-Komplexität einer Zeichenkette mindestens so groß ist wie die Zeichenkette selber, 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.
- La complexité de Kolmogorov, nommée aussi complexité aléatoire, ou complexité algorithmique, est une fonction (plus précisément un ensemble de fonctions) permettant d'évaluer la complexité de calcul d'un nombre ou d'une suite.
- コルモゴロフ複雑性（コルモゴロフふくざつせい, Kolmogorov complexity）とは、計算機科学において有限長のデータ列の複雑さを表す指標のひとつで、出力結果がそのデータに一致するプログラムの長さの最小値として定義される。 コルモゴロフ複雑度、コルモゴロフ＝チャイティン複雑性 (Kolmogorov-Chaitin complexity) とも呼ばれる。 コルモゴロフ複雑性の概念は一見すると単純なものであるが、テューリングの停止問題やゲーデルの不完全性定理と関連する深遠な内容をもつ。 コルモゴロフ複雑性やその他の文字列やデータ構造の複雑性の計量を研究する計算機科学の分野はアルゴリズム情報理論と呼ばれており、1960 年代末にアンドレイ・コルモゴロフ、レイ・ソロモノフ、グレゴリー・チャイティンによって創始された。
- In de algoritmische informatietheorie (een deelgebied van de informatica), is de Kolmogorov-complexiteit (ook bekend staand als de beschrijvende complexiteit, de Kolmogorov-Chaitin-complexiteit, stochastische complexiteit, algoritmische entropie of programmagrootte complexiteit) van een object, zoals een stuk tekst een maat van de berekeningsmiddelen die nodig zijn om het object te specificeren. Neem bijvoorbeeld de volgende twee strings beide met lengte 64, elk bestaand uit alleen kleine letters, cijfers en spaties: abababababababababababababababababababababababababababababababab 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf 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 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.
- Złożoność Kołmogorowa łańcucha symboli skończonego lub nieskończonego to długość najkrótszego programu, który generuje dany łańcuch. Np. rozwinięcie dziesiętne liczby pi, choć jest 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. Nazwa pochodzi od Andrieja Kołmogorowa.
- 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 E. 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).
- В дальнейшем, мы будем измерять длины всех объектов в битах. Для определения сложности мы начнём с элементарных замечаний. Начнём с описания бинарной последовательности (строки). Описание бинарной последовательности s — это просто программа, написанная как строка бит, которая производит последовательность s как результат. Принимая во внимание все возможные программы, которые генерируют последовательность s и выбирая кратчайшую, мы получим минимальное описание последовательности s, обозначаемое как d(s). (Если существует более одной программы одинаковой длины, выберем в качестве d первую из них в лексикографическом порядке. ) Колмогоровская сложность s, записывается K(s), и <math>K(s) = |d(s)|. </math> Другими словами, K(s) — это длина минимального описания s.
- В информатике, алгоритмическая теория информации — это область знаний, которая пытается уловить суть сложности используя инструменты из теоретической информатики. Главная идея — это определить сложность строки как длину кратчайшей программы, которая выводит заданную строку. Строки, которые могут выводиться короткими программами рассматриваются, как не очень сложные. Эта нотация удивительно глубока и может быть использована для постановки и доказательства невозможности некоторых результатов, таким-же образом как это делает теорема Гёделя о неполноте и проблема зависания Тьюринга. Эта область была разработана Андреем Колмогоровым, Рэем Соломоновым и Грегори Хайтиным в конце 1960-х годов. Существуют несколько вариантов Колмогоровской сложности или алгоритмической информации. Наиболее широко используемая базируется на саморазграничивающих программах и в в основном следует Леониду Левину (1974). Для формализации данного выше определения сложности определим какие типы программ являются допустимыми. К счастью это не имеет особого значения: как мы увидим позже, любой может выбрать особую нотацию для машины Тьюринга, или программы на языке LISP, или программы на языке Pascal, или в байткоде виртуальной машины Java. Принцип минимальной длины сообщения (МДС) статистического и индуктивного вывода и машинного обучения был разработан Кристофером Уоллесом и D.M. Boulton в 1968 году. МДС — байесовская вероятность (она включает предыдущие мнения) и информационно-теоретическая. Она имеет желаемые свойства статистической инвариантности (вывод трансформируется с репараметризацией, например, таким-же образом как осуществляется перевод из полярных координат в декартовы), статистическую согласованность (даже для очень сложных проблем, МДС будет сходиться к любой низлежащей модели) и эффективность (модель МДС будет сходиться к любой истинной низлежащей модели так быстро как возможно). Кристофер Уоллес и D.L. Dowe показали формальную связь между МДС и алгоритмической теорией информации (или Колмогоровской сложностью) в 1999 году.
- 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: Birinci 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 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.
- 在计算机科学中，一个对象比如一段文字的柯氏复杂性（柯尔莫哥洛夫复杂性, 描述复杂性, Kolmogorov-Chaitin complexity, stochastic complexity, 算法熵）是衡量描述这个对象所需要的信息量的一个尺度。 以下面的两个长度为64的字符串为例。 第一个字符串可以用中文简短地描述为“重复32个‘01’”。第二个字符串没有明显的简短描述。 一个字符串<math>s</math>的柯氏复杂性（<math>C(s)</math>或者<math>K(s)</math>，区别如后）是这个字符串的最短描述的长度。换言之，一个字符串<math>s</math>的柯氏复杂性是能够输出且仅输出这个字符串的最短计算机／图灵机程序的长度。 这样的定义导致在使用不同的描述语言或者不同的图灵机的时候柯氏复杂性不一样。所以在讨论柯氏复杂性的时候，通常都事先固定一个通用图灵机<math>U</math>作为参照。可以证明在使用<math>U</math>做参照的时候，对任意的图灵机<math>M</math>，都存在一个仅决定于<math>U</math>和<math>M</math>的常数<math>c_M</math>使得对所有的字符串<math>s</math>相对于<math>U</math>的柯氏复杂性<math>C_U</math>（或者<math>K_U</math>）和相对于<math>M</math>的柯氏复杂性<math>C_M</math>（或者<math>K_M</math>）都满足 <math>C_U(s)\leq C_M(s)+c_M</math>。 根据这点，通常确定了一个参照图灵机后就用<math>C</math>和<math>K</math>表示柯氏复杂性（省略<math>U</math>）。
|
| rdfs:comment
|
- In algorithmic information theory (a subfield of computer science), the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov-Chaitin complexity, stochastic complexity, algorithmic entropy, or program-size complexity) of an object such as a piece of text is a measure of the computational resources needed to specify the object.
- Die Kolmogorow-Komplexität 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, ohne dass Information verlorengeht. Wenn die Kolmogorow-Komplexität einer Zeichenkette mindestens so groß ist wie die Zeichenkette selber, dann bezeichnet man die Zeichenkette als unkomprimierbar, zufällig oder auch strukturlos.
- La complexité de Kolmogorov, nommée aussi complexité aléatoire, ou complexité algorithmique, est une fonction (plus précisément un ensemble de fonctions) permettant d'évaluer la complexité de calcul d'un nombre ou d'une suite.
- In de algoritmische informatietheorie (een deelgebied van de informatica), is de Kolmogorov-complexiteit (ook bekend staand als de beschrijvende complexiteit, de Kolmogorov-Chaitin-complexiteit, stochastische complexiteit, algoritmische entropie of programmagrootte complexiteit) van een object, zoals een stuk tekst een maat van de berekeningsmiddelen die nodig zijn om het object te specificeren.
- Złożoność Kołmogorowa łańcucha symboli skończonego lub nieskończonego to długość najkrótszego programu, który generuje dany łańcuch. Np. rozwinięcie dziesiętne liczby pi, choć jest 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).
- 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 E.
- В дальнейшем, мы будем измерять длины всех объектов в битах. Для определения сложности мы начнём с элементарных замечаний. Начнём с описания бинарной последовательности (строки).
- В информатике, алгоритмическая теория информации — это область знаний, которая пытается уловить суть сложности используя инструменты из теоретической информатики.
- 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ü.
|
![[RDF Data]](/statics/sw-cube.png)
