{"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\/sk\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","title":{"rendered":"Paradoxy o kompresii \u00fadajov","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Paradoxy \u00daloha kompresie d\u00e1t vo svojej najjednoduch\u0161ej forme sa m\u00f4\u017ee vz\u0165ahova\u0165 na \u010d\u00edsla a ich ozna\u010denia. \u010c\u00edsla m\u00f4\u017eeme ozna\u010dova\u0165 \u010d\u00edslovkami (\u201ejeden\u00e1s\u0165\u201c<\/i> pre \u010d\u00edslo 11), matematick\u00fdmi v\u00fdrazmi (\u201edva na dvadsiatej\u201c<\/i> pre 1048576), re\u0165azcov\u00fdmi v\u00fdrazmi (\u201ep\u00e4\u0165 deviatok\u201c<\/i> pre 99999), vlastn\u00fdmi menami (\u201e\u010d\u00edslo be\u0161tie\u201c<\/i> pre 666, \u201erok smrti Turinga\u201c<\/i> pre 1954), alebo \u013eubovo\u013en\u00fdmi ich kombin\u00e1ciami. Ak\u00e9ko\u013evek ozna\u010denie, ktor\u00fdm m\u00f4\u017ee rozhovorov\u00fd partner jednozna\u010dne ur\u010di\u0165, o akom \u010d\u00edsle je re\u010d, je vhodn\u00e9. Je zrejm\u00e9, \u017ee informova\u0165 niekoho o \u201efaktori\u00e1li \u00f4smej\u201c<\/i> je efekt\u00edvnej\u0161ie ne\u017e ekvivalentn\u00e9 ozna\u010denie \u201e\u0161tyridsa\u0165tis\u00edc tristo dvadsa\u0165\u201c<\/i>. Tu sa objavuje logick\u00e1 ot\u00e1zka: ak\u00e9 ozna\u010denie pre dan\u00e9 \u010d\u00edslo je najkrat\u0161ie?<\/p>\n

Filozof Bertrand Russell v roku 1908 publikoval \u201eBerryho paradox\u201c<\/a><\/noindex>, ktor\u00fd sa zaober\u00e1 ot\u00e1zkou ozna\u010den\u00ed \u010d\u00edsel z opa\u010dnej strany: ak\u00e9 je najmen\u0161ie \u010d\u00edslo, na jeho ozna\u010denie nie je dostato\u010dn\u00fdch osemdesiat p\u00edsmen?<\/b>
\nTak\u00e9 \u010d\u00edslo mus\u00ed existova\u0165: z osemdesiatich rusk\u00fdch p\u00edsmen a medzier je mo\u017en\u00e9 zostavi\u0165 iba 3480 ozna\u010den\u00ed, \u010do znamen\u00e1, \u017ee pri pou\u017eit\u00ed osemdesiatich p\u00edsmen je mo\u017en\u00e9 ozna\u010di\u0165 maxim\u00e1lne 3480 \u010d\u00edsel. To znamen\u00e1, \u017ee niektor\u00e9 \u010d\u00edslo, ktor\u00e9 nepresahuje 3480, nemo\u017eno takto ozna\u010di\u0165.<\/p>\n

To znamen\u00e1, tomuto \u010d\u00edslu bude zodpoveda\u0165 ozna\u010denie \u201enajmen\u0161ie \u010d\u00edslo, na jeho ozna\u010denie nie je dostato\u010dn\u00fdch osemdesiat p\u00edsmen\u201c<\/i>, v ktorom je len 78 p\u00edsmen! Z jednej strany, tak\u00e9 \u010d\u00edslo mus\u00ed existova\u0165; z druhej, ak to \u010d\u00edslo existuje, jeho ozna\u010denie mu nevyhovuje. Paradox!<\/a><\/noindex><\/p>\n

Najjednoduch\u0161\u00ed sp\u00f4sob, ako sa zbavi\u0165 tohto paradoxu, je odvola\u0165 sa na neform\u00e1lnos\u0165 slovn\u00fdch ozna\u010den\u00ed. Sn\u00e1\u010f, keby sa v ozna\u010deniach prip\u00fa\u0161\u0165al iba konkr\u00e9tne definovan\u00fd s\u00fabor v\u00fdrazov, tak \u201enajmen\u0161ie \u010d\u00edslo, na jeho ozna\u010denie nie je dostato\u010dn\u00fdch osemdesiat p\u00edsmen\u201c<\/i> nebolo by pr\u00edpustn\u00fdm ozna\u010den\u00edm, zatia\u013e \u010do prakticky u\u017eito\u010dn\u00e9 ozna\u010denia typu \u201efaktori\u00e1li \u00f4smej\u201c<\/i> by zostali pr\u00edpustn\u00e9.<\/p>\n

Existuj\u00fa form\u00e1lne sp\u00f4soby, ako op\u00edsa\u0165 postupnos\u0165 (algoritmus) \u010dinnost\u00ed s \u010d\u00edslami? \u00c1no, a hojne \u2014 naz\u00fdvaj\u00fa sa programovacie jazyky. Namiesto slovn\u00fdch ozna\u010den\u00ed budeme pou\u017e\u00edva\u0165 programy (napr\u00edklad v Pythone), ktor\u00e9 vypisuj\u00fa po\u017eadovan\u00e9 \u010d\u00edsla. Napr\u00edklad, pre p\u00e4\u0165 deviatok, zodpoved\u00e1 program print(\"9\"*5)<\/code>. Na\u010falej sa budeme zauj\u00edma\u0165 o najkrat\u0161\u00ed program pre dan\u00e9 \u010d\u00edslo. D\u013a\u017eku tak\u00e9ho programu naz\u00fdvame kolmogorovskou zlo\u017eitostou<\/a><\/noindex> \u010d\u00edsla; to je teoretick\u00e1 hranica, do ktorej je dan\u00e9 \u010d\u00edslo mo\u017en\u00e9 skomprimova\u0165.<\/p>\n

Namiesto Berryho paradoxu m\u00f4\u017eeme teraz zv\u00e1\u017ei\u0165 anal\u00f3giu: ak\u00e9 najmen\u0161ie \u010d\u00edslo je mo\u017en\u00e9 vyda\u0165, pre ktor\u00e9 nie je dostato\u010dn\u00fd kilobajtov\u00fd program?<\/b><\/p>\n

D\u00fafame, \u017ee si to bude pam\u00e4ta\u0165: existuje 2561024 kilobajtov\u00fdch textov, teda kilobajtov\u00fdmi programami je mo\u017en\u00e9 vyda\u0165 najviac 2561024 \u010d\u00edsel. Teda nejak\u00e9 \u010d\u00edslo, ktor\u00e9 nepresahuje 2561024, nie je mo\u017en\u00e9 touto cestou vyda\u0165.<\/p>\n

Ale nap\u00ed\u0161eme program na Python, ktor\u00fd generuje v\u0161etky mo\u017en\u00e9 kilobajtov\u00e9 texty, sp\u00fa\u0161\u0165a ich na vykonanie, a ak vyprodukuj\u00fa nejak\u00e9 \u010d\u00edslo - prid\u00e1 to \u010d\u00edslo do slovn\u00edka dosiahnute\u013en\u00fdch. Po kontrole v\u0161etk\u00fdch 2561024 mo\u017enost\u00ed, nech to trv\u00e1 akoko\u013evek dlho - program h\u013ead\u00e1, ak\u00e9 najmen\u0161ie \u010d\u00edslo ch\u00fdba v slovn\u00edku, a vyvedie toto \u010d\u00edslo. Zd\u00e1 sa, \u017ee tak\u00fd program sa vmest\u00ed do kilobajtu k\u00f3du - a vyvedie to ist\u00e9 \u010d\u00edslo, ktor\u00e9 nie je mo\u017en\u00e9 vyda\u0165 kilobajtov\u00fdm programom!<\/p>\n

Kde je teda h\u00e1\u010dik? Na neform\u00e1lnos\u0165 ozna\u010den\u00ed to u\u017e nie je mo\u017en\u00e9 zavesi\u0165!<\/p>\n

Ak v\u00e1s m\u00e4tie to, \u017ee n\u00e1\u0161 program bude vy\u017eadova\u0165 astronomick\u00e9 mno\u017estvo pam\u00e4te na pr\u00e1cu - slovn\u00edk (alebo bitov\u00e9 pole) z 2561024 prvkov - m\u00f4\u017ee sa to v\u0161etko uskuto\u010dni\u0165 aj bez neho: pre ka\u017ed\u00e9 z 2561024 \u010d\u00edsel postupne prech\u00e1dzajte v\u0161etk\u00fdmi 2561024 mo\u017en\u00fdmi programami, k\u00fdm sa nen\u00e1jde vhodn\u00fd. Nie je d\u00f4le\u017eit\u00e9, \u017ee tak\u00fdto preh\u013ead potrv\u00e1 ve\u013emi dlho: po kontrole menej ako (2561024)2 p\u00e1rov \u010d\u00edsla a programu sa predsa len ukon\u010d\u00ed a n\u00e1jde to vz\u00e1cne \u010d\u00edslo.<\/p>\n

Alebo sa neskon\u010d\u00ed? Ve\u010f medzi v\u0161etk\u00fdmi programami, ktor\u00e9 bud\u00fa vysk\u00fa\u0161an\u00e9, sa n\u00e1jde while True: pass<\/code> (a jej funk\u010dn\u00e9 anal\u00f3gy) - a \u010falej u\u017e testovanie tak\u00e9ho programu nep\u00f4jde!<\/p>\n

Na rozdiel od Berryho paradoxu, kde h\u00e1\u010dik spo\u010d\u00edval v neform\u00e1lnosti ozna\u010den\u00ed, v druhom pr\u00edpade m\u00e1me dobre zamaskovan\u00fa reformul\u00e1ciu \"probl\u00e9mu zastavenia\".<\/a><\/noindex>Ide o to, \u017ee z programu nie je mo\u017en\u00e9 za kone\u010dn\u00fd \u010das ur\u010di\u0165 jeho v\u00fdstup. Zvl\u00e1\u0161\u0165, kolmogorovsk\u00e1 zlo\u017eitost je nepo\u010d\u00edtate\u013en\u00e1.<\/a><\/noindex>: neexistuje \u017eiadny algoritmus, ktor\u00fd by umo\u017enil pre dan\u00e9 \u010d\u00edslo n\u00e1js\u0165 d\u013a\u017eku najkrat\u0161ieho programu, ktor\u00fd toto \u010d\u00edslo vypisuje; a teda neexistuje ani rie\u0161enie pre \u00falohu Berry \u2014 n\u00e1js\u0165 pre dan\u00e9 \u010d\u00edslo d\u013a\u017eku najkrat\u0161ieho slovn\u00e9ho ozna\u010denia.
\n
Zdroj: 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\udd47Paradoksy o kompresii d\u00e1t | ProHoster","description":"\u00daloha kompresie d\u00e1t v svojej najjednoduch\u0161ej forme m\u00f4\u017ee s\u00favisie\u0165 s.","canonical_url":"https:\/\/prohoster.info\/sk\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"sk_SK","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\/sk\/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\/sk\/wp-json\/wp\/v2\/posts\/31157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/comments?post=31157"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/posts\/31157\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/media\/23125"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/media?parent=31157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/categories?post=31157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/tags?post=31157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}