Ця стаття є сирим з іншої мови. Можливо, вона створена за допомогою машинного перекладу або перекладачем, який недостатньо володіє обома мовами. (лютий 2016) |
В іншому мовному розділі є повніша стаття Kolmogorov complexity(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою з англійської.
|
Ця стаття потребує додаткових для поліпшення її . (квітень 2017) |
Складність та ентропія конструктивних об'єктів
Складність та ентропія конструктивних об'єктів, відома як колмогоровська складність, складність Колмогорова, стохастична складність в алгоритмічній теорії інформації, складність об'єкту(або тексту) -- є міра обчислювальних ресурсів, що необхідні для того, щоб точно визначити цей об'єкт.
Висловлює можливість фрактального опису.
Наприклад, розглянемо два рядки довжиною 64 символу, що містять тільки символи в нижньому регістрі і цифри:
abababababababababababababababababababababababababababababababab 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf
Перший рядок має простий опис природною мовою, а саме ab 32 рази, що складається з 10 символів. Другий рядок не має очевидного простого опису з використанням того ж набору символів, крім власне самої цього рядка, довжина якої становить 64 символу.
Більш формально, складність рядка - це довжина опису цього рядка на деякій універсальній мові опису. Здатність складності до зміни стосовно вибору мови опису обговорюється нижче. Можна показати, що колмогорівська складність будь-якого рядка не може бути більшою кількох байт, ніж довжина самого цього рядка. Рядки, колгомівська складність яких слабко залежить від розміру самого рядка, не вважаються складними.
Визначення
Щоб визначити колгомівську складність, ми повинні спочатку задати мову опису рядків. Така мова опису може бути задана на будь-якій мові програмування, такій як 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.
- Вьюгин В.В. Колмогоровская сложность и алгоритмическая случайность.
Це незавершена стаття з інформатики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Cya stattya ye sirim perekladom z inshoyi movi Mozhlivo vona stvorena za dopomogoyu mashinnogo perekladu abo perekladachem yakij nedostatno volodiye oboma movami Bud laska dopomozhit polipshiti pereklad lyutij 2016 V inshomu movnomu rozdili ye povnisha stattya Kolmogorov complexity angl Vi mozhete dopomogti rozshirivshi potochnu stattyu za dopomogoyu perekladu z anglijskoyi Divitis avtoperekladenu versiyu statti z movi anglijska Perekladach povinen rozumiti sho vidpovidalnist za kincevij vmist statti u Vikipediyi nese same avtor redaguvan Onlajn pereklad nadayetsya lishe yak korisnij instrument pereglyadu vmistu zrozumiloyu movoyu Ne vikoristovujte nevichitanij i nevidkorigovanij mashinnij pereklad u stattyah ukrayinskoyi Vikipediyi Mashinnij pereklad Google ye korisnoyu vidpravnoyu tochkoyu dlya perekladu ale perekladacham neobhidno vipravlyati pomilki ta pidtverdzhuvati tochnist perekladu a ne prosto skopiyuvati mashinnij pereklad do ukrayinskoyi Vikipediyi Ne perekladajte tekst yakij vidayetsya nedostovirnim abo neyakisnim Yaksho mozhlivo perevirte tekst za posilannyami podanimi v inshomovnij statti Dokladni rekomendaciyi div Vikipediya Pereklad Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno kviten 2017 Skladnist ta entropiya konstruktivnih ob yektivSkladnist ta entropiya konstruktivnih ob yektiv vidoma yak kolmogorovska skladnist skladnist Kolmogorova stohastichna skladnist v algoritmichnij teoriyi informaciyi skladnist ob yektu abo tekstu ye mira obchislyuvalnih resursiv sho neobhidni dlya togo shob tochno viznachiti cej ob yekt Vislovlyuye mozhlivist fraktalnogo opisu Napriklad rozglyanemo dva ryadki dovzhinoyu 64 simvolu sho mistyat tilki simvoli v nizhnomu registri i cifri abababababababababababababababababababababababababababababababab 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf Pershij ryadok maye prostij opis prirodnoyu movoyu a same ab 32 razi sho skladayetsya z 10 simvoliv Drugij ryadok ne maye ochevidnogo prostogo opisu z vikoristannyam togo zh naboru simvoliv krim vlasne samoyi cogo ryadka dovzhina yakoyi stanovit 64 simvolu Bilsh formalno skladnist ryadka ce dovzhina opisu cogo ryadka na deyakij universalnij movi opisu Zdatnist skladnosti do zmini stosovno viboru movi opisu obgovoryuyetsya nizhche Mozhna pokazati sho kolmogorivska skladnist bud yakogo ryadka ne mozhe buti bilshoyu kilkoh bajt nizh dovzhina samogo cogo ryadka Ryadki kolgomivska skladnist yakih slabko zalezhit vid rozmiru samogo ryadka ne vvazhayutsya skladnimi ViznachennyaShob viznachiti kolgomivsku skladnist mi povinni spochatku zadati movu opisu ryadkiv Taka mova opisu mozhe buti zadana na bud yakij movi programuvannya takij yak Lisp Paskalya abo Java bajt kod Yaksho P programa rezultatom yakoyi ye ryadok h to P opis h Dovzhinoyu opisu ye dovzhina P yak ryadka U hodi viznachennya dovzhini P dovzhini pidprogram sho vikoristovuyutsya v P povinni buti obchisleni Dovzhina bud yakoyi ciloyi konstanti n yaka z yavlyayetsya v P ce kilkist bit potribnih dlya podannya n rivne grubo log2 n Mi mozhemo alternativno vibrati koduvannya dlya mashini Tyuringa de koduvannya funkciya sho vstanovlyuyetsya u vidpovidnist kozhnij mashini Tyuringa M bitovij ryadok lt M gt langle M rangle Yaksho M mashina Tyuringa yaka na vhid w daye na vihodi ryadok h to ob yednana ryadok langle M rangle zh ye opis dlya h Ce teoretichnij pidhid yakij ye bilsh vidpovidnim dlya pobudovi detalnih formalnih dokaziv i bazhanij u doslidnickij literaturi Dvijkove lyambda chislennya mozhe dati najbilsh proste viznachennya skladnosti U cij statti mi vikoristovuyemo neformalnij pidhid Bud ryadok s maye yak minimum odin opis tobto programu function GenerateFixedString return s Yaksho opis s d s minimalnoyi dovzhini tobto vikoristovuye najmenshu kilkist simvoliv to vono nazivayetsya minimalnim opisom s a dovzhina d s to est kolichestvo simvolov v etom opisanii kolmogovska skladnistkolmogovska skladnist s K s Simvolno K s d s Rozglyanemo yak vibir movi opisu vplivaye na znachennya K i pokazhemo sho efekt vid zmini movi opisu ye obmezhenim Teorema Yaksho K1 i K2 funkciyi skladnosti sho vidnosyatsya do mov opisu L1 i L2 to isnuye konstanta s zalezhna tilki vid mov L1 i L2 taka sho dlya bud yakogo s K1 s K2 s lt c DzherelaVereshagin N K Kurs kolmogorovskoj slozhnosti Vereshagin N K Shen V A Kolmogorovskaya slozhnost i algoritmicheskaya sluchajnost MCNMO 2013 Vyugin V V Kolmogorovskaya slozhnost i algoritmicheskaya sluchajnost Ce nezavershena stattya z informatiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi