Відкрити головне меню

Складність та ентропія конструктивних об'єктівРедагувати

Складність та ентропія конструктивних об'єктів , відома як колмоговська складність, складність колмогова, стохастична складність в алгоритмічній теорії інформації, складність об'єкту(або тексту) -- є міра обчислювальних ресурсів, що необхідні для того, щоб точно визначити цей об'єкт.
Висловлює можливість фрактального опису.
Наприклад, розглянемо два рядки довжиною 64 символу, що містять тільки символи в нижньому регістрі і цифри:

abababababababababababababababababababababababababababababababab
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf

Перший рядок має простий опис на природній мові, а саме ab 32 рази, що складається з 10 символів. Другий рядок не має очевидного простого опису з використанням того ж набору символів, крім власне самої цього рядка, довжина якої становить 64 символу.

Більш формально , складність рядкa - це довжина опису цього рядка на деякій універсальній мові опису . Здатність складності до зміни стосовно вибору мови опису обговорюється нижче. Можна показати , що колмогорівська складність будь-якого рядка не може бути більшою кількох байт , ніж довжина самого цього рядка. Рядки , колгомівська складність яких слабо залежить від розміру самої рядки, що не вважаються складними.

ВизначенняРедагувати

Щоб визначити колгомівську складність , ми повинні спочатку задати мову опису рядків. Така мова опису може бути задана на будь-якій мові програмування , такій як Lisp , Паскаля або Java- байт -код . Якщо P - програма , результатом якої є рядок х , то P - опис х . Довжиною опису є довжина P як рядка . У ході визначення довжини P довжини підпрограм , що використовуються в P , повинні бути обчислені . Довжина будь-якої цілої константи n , яка з'являється в P , це кількість біт , потрібних для подання n , рівне (грубо ) \ log2 n .

Ми можемо альтернативно вибрати кодування для машини Тюринга , де кодування - функція , що встановлюється у відповідність кожній машині Тюринга M бітовий рядок <M> \ Langle М \ rangle . Якщо М - машина Тьюринга , яка на вхід ω дає на виході рядок х , то об'єднана рядок \ Langle М \ rangle ж є опис для х . Це теоретичний підхід , який є більш відповідним для побудови детальних формальних доказів і бажаний у дослідницькій літературі . Двійкове лямбда -числення може дати найбільш просте визначення складності. У цій статті ми використовуємо неформальний підхід .

Будь рядок с має як мінімум один опис , тобто програму

function GenerateFixedString()
   return s

Якщо опис s, d(s) мінімальної довжини тобто використовує найменшу кількість символів, то воно називається мінімальним описом s, а довжина d(s), то есть количество символов в этом описании, — колмоговська складністьколмоговська складність s, K(s). Символьно
K(s)=|d(s)|.
Розглянемо, як вибір мови опису впливає на значення K і покажемо, що ефект від зміни мови опису є обмеженим. Теорема. Якщо К1 і К2 - функції складності,що відносяться до мов опису L1 i L2 то існує константа с (залежна тільки від мов L1 i L2) така, що
для будь якого s |К1(s)-К2(s)|<=c.

ДжерелаРедагувати

  • Верещагин Н. К. Курс колмогоровской сложности.
  • Верещагин Н.К., Шень В.А. Колмогоровская сложность и алгоритмическая случайность. — МЦНМО, 2013.
  • Вьюгин В.В. Колмогоровская сложность и алгоритмическая случайность.