{"id":31157,"date":"2019-10-31T21:39:48","date_gmt":"2019-10-31T18:39:48","guid":{"rendered":"https:\/\/prohoster.info\/blog\/paradoksy-o-szhatii-dannyh\/"},"modified":"2019-10-31T21:39:48","modified_gmt":"2019-10-31T18:39:48","slug":"paradoksy-o-szhatii-dannyh","status":"publish","type":"post","link":"https:\/\/prohoster.info\/sl\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","title":{"rendered":"Paradoksi kompresije podatkov","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Paradoksi Naloga kompresije podatkov v svoji najpreprostej\u0161i obliki se lahko nana\u0161a na \u0161tevilke in njihove ozna\u010dbe. \u0160tevilke je mogo\u010de ozna\u010devati s \u0161tevil\u010dnimi vrednostmi (\u201eenajst\u201c<\/i> za \u0161tevilko 11), matemati\u010dnimi izrazi (\u201edva na dvajset\u201c<\/i> za 1048576), niznimi izrazi (\u201epet devetk\u201c<\/i> za 99999), lastnimi imeni (\u201e\u0161tevilo zveri\u201c<\/i> za 666, \u201eleto smrti Turinga\u201c<\/i> za 1954), ali poljubnimi njih kombinacijami. Ustrezna je katera koli oznaka, s katero lahko sogovornik nedvoumno dolo\u010di, o kateri \u0161tevilki govorimo. O\u010ditno je, da je bolj u\u010dinkovito sporo\u010diti sogovorniku \u201efaktorial osem\u201c<\/i> kot ekvivalentno oznako \u201e\u0161tirideset tiso\u010d trideset\u201c<\/i>. Tukaj se pojavi logi\u010dno vpra\u0161anje: katera oznaka za dano \u0161tevilko je najkraj\u0161a?<\/p>\n

Filozof Bertrand Russell je leta 1908 objavil \u201eBerryjev paradoks\u201c<\/a><\/noindex>, ki se dotika vpra\u0161anja ozna\u010devanja \u0161tevil z druge strani: katero je najmanj\u0161e \u0161tevilo, za katerega ni dovolj osemdeset \u010drk za njegovo ozna\u010devanje?<\/b>
\nTak\u0161no \u0161tevilo mora obstajati: iz osemdesetih ruskih \u010drk in presledkov je mogo\u010de sestaviti le 3480 oznak, kar pomeni, da je mogo\u010de s pomo\u010djo osemdesetih \u010drk ozna\u010diti najve\u010d 3480 \u0161tevil. To pomeni, da nekega \u0161tevila, ki ni ve\u010dje od 3480, na ta na\u010din ozna\u010diti ni mogo\u010de.<\/p>\n

To pomeni, da bo temu \u0161tevilu ustrezala oznaka \u201enajmanj\u0161e \u0161tevilo, za ozna\u010devanje katerega ni dovolj osemdeset \u010drk\u201c<\/i>, v kateri je skupaj 78 \u010drk! Po eni strani mora to \u0161tevilo obstajati; po drugi strani, \u010de to \u0161tevilo obstaja, njegova oznaka zanj ne ustreza. Paradoks!<\/a><\/noindex><\/p>\n

Najenostavnej\u0161i na\u010din, da se odmaknemo od tega paradoksa, je, da se sklicujemo na neformalnost besednih ozna\u010db. Pravi, da \u010de bi v ozna\u010dbah bil dovoljen le konkretno dolo\u010den nabor izrazov, potem \u201enajmanj\u0161e \u0161tevilo, za ozna\u010devanje katerega ni dovolj osemdeset \u010drk\u201c<\/i> ne bi bilo dopustne oznake, medtem ko bi prakti\u010dno uporabne oznake, kot so \u201efaktorial osem\u201c<\/i> ostale dopustne.<\/p>\n

Ali obstajajo formalni na\u010dini opisovanja zaporedja (algoritma) dejanj nad \u0161tevilkami? Da, in v obilju \u2014 imenujejo se programski jeziki. Uporabimo lahko namesto besednih oznak programe (na primer v Pythonu), ki izpi\u0161ejo \u017eeleno \u0161tevilko. Na primer, za pet devetk bo ustrezal program print(\"9\"*5)<\/code>\u0160e vedno nas zanima najkraj\u0161i program za dano \u0161tevilo. Dol\u017eina takega programa se imenuje Kolmogorovska kompleksnost<\/a><\/noindex> \u0161tevilke; to je teoreti\u010dna meja, do katere je dano \u0161tevilo mogo\u010de stisniti.<\/p>\n

Namesto Berryjevega paradoksa lahko razmislimo o podobnem: katero je najmanj\u0161e \u0161tevilo, za katerega ni dovolj kilobajtnega programa?<\/b><\/p>\n

Razmi\u0161ljali bomo tako kot prej: obstaja 2561024 kilobajtnih besedil, kar pomeni, da s kilobajtni programi ne moremo izpisati ve\u010d kot 2561024 \u0161tevil. Torej ni mogo\u010de na noben na\u010din zapisati nekega \u0161tevila, ki je manj\u0161e od 2561024.<\/p>\n

Toda napi\u0161imo Python program, ki generira vse mo\u017ene kilobajtne tekste, jih za\u017eene, in \u010de izpi\u0161ejo neko \u0161tevilo \u2014 to \u0161tevilo doda v slovar dosegljivih \u0161tevil. Po preverjanju vseh 2561024 mo\u017enosti, kolikor \u010dasa \u017ee bo trajalo \u2014 program poi\u0161\u010de, katero je najmanj\u0161e \u0161tevilo, ki manjka v slovarju, in izpi\u0161e to \u0161tevilo. Zdi se o\u010ditno, da bo tak program ma\u0161iral v kilobajt kodiranja \u2014 in izpisal to\u010dno tisto \u0161tevilo, ki ga ni mogo\u010de izpisati s kilobajtno programsko kodo!<\/p>\n

Kje pa je zdaj zvija\u010da? Z neformalnostjo oznak tega ne moremo ve\u010d odpraviti!<\/p>\n

\u010ce vas zmoti, da bo na\u0161 program potreboval astronomsko koli\u010dino pomnilnika za delovanje \u2014 slovar (ali bitno polje) z 2561024 elementi \u2014 lahko vse to dose\u017eemo tudi brez njega: za vsako od 2561024 \u0161tevil po vrsti preizkusimo vse 2561024 mo\u017ene programe, dokler ne najdemo ustreznega. Ni va\u017eno, da bo to preizku\u0161anje trajalo zelo dolgo: po preverjanju manj kot (2561024)2 parov \u0161tevila in programa se bo namre\u010d zaklju\u010dilo in na\u0161lo to za\u017eeleno \u0161tevilo.<\/p>\n

Ali pa se ne bo zavr\u0161ilo? Saj med vsemi programi, ki bodo preizku\u0161eni, naletimo na while True: pass<\/code> (in njene funkcionalne analoge) \u2014 in nadaljnje preverjanje takega programa se ne bo zgodilo!<\/p>\n

Za razliko od Berryjevega paradoksa, kjer je bil trik v neformalnosti oznak, imamo v drugem primeru dobro prikrito preoblikovanje \"problema ustavitve\"<\/a><\/noindex>. Gre namre\u010d za to, da po programu ni mogo\u010de v kon\u010dnem \u010dasu dolo\u010diti njegovega izhoda. \u0160e posebej, Kolmogorovska kompleksnost je neizra\u010dunljiva.<\/a><\/noindex>: ne obstaja noben algoritem, ki bi omogo\u010dil najti dol\u017eino najkraj\u0161ega programa, ki izpisuje dano \u0161tevilo; torej tudi ni re\u0161itve za Berryjev problem \u2014 najti dol\u017eino najkraj\u0161ega besednega ozna\u010devalca za dano \u0161tevilo.
\n
Izvor: habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"

\u0417\u0430\u0434\u0430\u0447\u0430 \u0441\u0436\u0430\u0442\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u0432 \u0441\u0432\u043e\u0435\u0439 \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0435\u0439 \u0444\u043e\u0440\u043c\u0435 \u043c\u043e\u0436\u0435\u0442 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u044c\u0441\u044f \u043a \u0447\u0438\u0441\u043b\u0430\u043c \u0438 \u0438\u0445 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c. \u0427\u0438\u0441\u043b\u0430 \u043c\u043e\u0436\u043d\u043e \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0430\u0442\u044c \u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 (\u00ab\u043e\u0434\u0438\u043d\u043d\u0430\u0434\u0446\u0430\u0442\u044c\u00bb \u0434\u043b\u044f \u0447\u0438\u0441\u043b\u0430 11), \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u043c\u0438 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044f\u043c\u0438 (\u00ab\u0434\u0432\u0430 \u0432 \u0434\u0432\u0430\u0434\u0446\u0430\u0442\u043e\u0439\u00bb \u0434\u043b\u044f 1048576), \u0441\u0442\u0440\u043e\u043a\u043e\u0432\u044b\u043c\u0438 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044f\u043c\u0438 (\u00ab\u043f\u044f\u0442\u044c \u0434\u0435\u0432\u044f\u0442\u043e\u043a\u00bb \u0434\u043b\u044f 99999), \u0438\u043c\u0435\u043d\u0430\u043c\u0438 \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u043c\u0438 (\u00ab\u0447\u0438\u0441\u043b\u043e \u0437\u0432\u0435\u0440\u044f\u00bb \u0434\u043b\u044f 666, \u00ab\u0433\u043e\u0434 \u0441\u043c\u0435\u0440\u0442\u0438 \u0422\u044c\u044e\u0440\u0438\u043d\u0433\u0430\u00bb \u0434\u043b\u044f 1954), \u0438\u043b\u0438 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u044b\u043c\u0438 \u0438\u0445 \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0446\u0438\u044f\u043c\u0438. \u0413\u043e\u0434\u0438\u0442\u0441\u044f \u043b\u044e\u0431\u043e\u0435 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u043f\u043e \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":23125,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-31157","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"\ud83e\udd47Paradoksi o stiskanju podatkov | ProHoster","description":"Problematika stiskanja podatkov se v svoji najosnovnej\u0161i obliki lahko nana\u0161a na.","canonical_url":"https:\/\/prohoster.info\/sl\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"sl_SI","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u041f\u0430\u0440\u0430\u0434\u043e\u043a\u0441\u044b \u043e \u0441\u0436\u0430\u0442\u0438\u0438 \u0434\u0430\u043d\u043d\u044b\u0445 | ProHoster","og:description":"\u0417\u0430\u0434\u0430\u0447\u0430 \u0441\u0436\u0430\u0442\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u0432 \u0441\u0432\u043e\u0435\u0439 \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0435\u0439 \u0444\u043e\u0440\u043c\u0435 \u043c\u043e\u0436\u0435\u0442 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u044c\u0441\u044f \u043a.","og:url":"https:\/\/prohoster.info\/sl\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T18:39:48+00:00","article:modified_time":"2019-10-31T18:39:48+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"31157","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-21 04:46:21","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 03:21:33","updated":"2026-01-21 04:46:21","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/posts\/31157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/comments?post=31157"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/posts\/31157\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/media\/23125"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/media?parent=31157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/categories?post=31157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/sl\/wp-json\/wp\/v2\/tags?post=31157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}