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

\"Paradoxy \u00daloha komprese dat v jej\u00ed nejjednodu\u0161\u0161\u00ed podob\u011b m\u016f\u017ee souviset s \u010d\u00edsly a jejich ozna\u010den\u00edmi. \u010c\u00edsla lze ozna\u010dovat \u010d\u00edslovkami (\u201ejeden\u00e1ct\u201c<\/i> pro \u010d\u00edslo 11), matematick\u00fdmi v\u00fdrazy (\u201edva na dvac\u00e1tou\u201c<\/i> pro 1048576), \u0159et\u011bzcov\u00fdmi v\u00fdrazy (\u201ep\u011bt dev\u00edtek\u201c<\/i> pro 99999), vlastn\u00edmi jm\u00e9ny (\u201e\u010d\u00edslo \u0161elmy\u201c<\/i> pro 666, \u201erok smrti Turinga\u201c<\/i> pro 1954), nebo libovoln\u00fdmi jejich kombinacemi. Plat\u00ed jak\u00e9koli ozna\u010den\u00ed, podle n\u011bho\u017e m\u016f\u017ee protistrana jednozna\u010dn\u011b ur\u010dit, o jak\u00e9m \u010d\u00edsle je \u0159e\u010d. Je jasn\u00e9, \u017ee sd\u011blit protistran\u011b \u201efaktori\u00e1l osmi\u201c<\/i> je efektivn\u011bj\u0161\u00ed ne\u017e ekvivalentn\u00ed ozna\u010den\u00ed \u201e\u010dty\u0159icet tis\u00edc t\u0159i sta dvacet\u201c<\/i>. Zde vyvst\u00e1v\u00e1 logick\u00e1 ot\u00e1zka: kter\u00e9 ozna\u010den\u00ed pro dan\u00e9 \u010d\u00edslo je nejkrat\u0161\u00ed?<\/p>\n

Filozof Bertrand Russell publikoval v roce 1908 \u201eBerryho paradox\u201c<\/a><\/noindex>, kter\u00fd se t\u00fdk\u00e1 ozna\u010dov\u00e1n\u00ed \u010d\u00edsel z opa\u010dn\u00e9 strany: jak\u00e9 je to nejmen\u0161\u00ed \u010d\u00edslo, pro jeho\u017e ozna\u010den\u00ed nen\u00ed dostatek osmdes\u00e1ti p\u00edsmen?<\/b>
\nTakov\u00e9 \u010d\u00edslo mus\u00ed existovat: z osmdes\u00e1ti rusk\u00fdch p\u00edsmen a mezer lze vytvo\u0159it jen 3480 ozna\u010den\u00ed, tedy p\u0159i pou\u017eit\u00ed osmdes\u00e1ti p\u00edsmen lze ozna\u010dit maxim\u00e1ln\u011b 3480 \u010d\u00edsel. To znamen\u00e1, \u017ee n\u011bjak\u00e9 \u010d\u00edslo, kter\u00e9 nen\u00ed v\u011bt\u0161\u00ed ne\u017e 3480, nen\u00ed mo\u017en\u00e9 t\u00edmto zp\u016fsobem ozna\u010dit.<\/p>\n

To znamen\u00e1, \u017ee tomuto \u010d\u00edslu bude odpov\u00eddat ozna\u010den\u00ed \u201enejmen\u0161\u00ed \u010d\u00edslo, pro jeho\u017e ozna\u010den\u00ed nen\u00ed dostatek osmdes\u00e1ti p\u00edsmen\u201c<\/i>, ve kter\u00e9m je celkem 78 p\u00edsmen! Na jedn\u00e9 stran\u011b, toto \u010d\u00edslo mus\u00ed existovat; na druh\u00e9 stran\u011b, pokud toto \u010d\u00edslo existuje, pak mu neodpov\u00edd\u00e1 jeho ozna\u010den\u00ed. Paradox!<\/a><\/noindex><\/p>\n

Nejjednodu\u0161\u0161\u00ed zp\u016fsob, jak se tohoto paradoxu zbavit, je odk\u00e1zat na neform\u00e1lnost slovn\u00edch ozna\u010den\u00ed. Pr\u00fd, pokud by byla v ozna\u010den\u00edch povolena pouze konkr\u00e9tn\u011b definovan\u00e1 skupina v\u00fdraz\u016f, pak \u201enejmen\u0161\u00ed \u010d\u00edslo, pro jeho\u017e ozna\u010den\u00ed nen\u00ed dostatek osmdes\u00e1ti p\u00edsmen\u201c<\/i> by to nebylo p\u0159\u00edpustn\u00e9 ozna\u010den\u00ed, zat\u00edmco prakticky u\u017eite\u010dn\u00e1 ozna\u010den\u00ed typu \u201efaktori\u00e1l osmi\u201c<\/i> by z\u016fstala p\u0159\u00edpustn\u00e1.<\/p>\n

Existuj\u00ed form\u00e1ln\u00ed zp\u016fsoby popisu posloupnosti (algoritmu) \u010dinnost\u00ed s \u010d\u00edsly? Ano, a v hojn\u00e9m po\u010dtu \u2014 naz\u00fdvaj\u00ed se programovac\u00edmi jazyky. Budeme m\u00edsto slovn\u00edch ozna\u010den\u00ed pou\u017e\u00edvat programy (nap\u0159\u00edklad v Pythonu), kter\u00e9 vygeneruj\u00ed pot\u0159ebn\u00e1 \u010d\u00edsla. Nap\u0159\u00edklad pro p\u011bt dev\u00edtek se hod\u00ed program print(\"9\"*5)<\/code>. Budeme se op\u011bt zaj\u00edmat o nejkrat\u0161\u00ed program pro dan\u00e9 \u010d\u00edslo. D\u00e9lka takov\u00e9ho programu se naz\u00fdv\u00e1 kolmogorovsk\u00e1 slo\u017eitost<\/a><\/noindex> \u010d\u00edsla; to je teoretick\u00e1 hranice, do kter\u00e9 lze dan\u00e9 \u010d\u00edslo stla\u010dit.<\/p>\n

M\u00edsto Berryho paradoxu nyn\u00ed m\u016f\u017eeme zv\u00e1\u017eit analogick\u00e9: jak\u00e9 je nejmen\u0161\u00ed \u010d\u00edslo, pro jeho\u017e v\u00fdstup nen\u00ed dostate\u010dn\u00fd kilobajtov\u00fd program?<\/b><\/p>\n

Budeme uva\u017eovat stejn\u011b jako d\u0159\u00edve: existuje 2561024 kilobajtov\u00fdch text\u016f, co\u017e znamen\u00e1, \u017ee kilobajtov\u00fdmi programy nelze vyprodukovat v\u00edce ne\u017e 2561024 \u010d\u00edsel. To znamen\u00e1, \u017ee n\u011bjak\u00e9 \u010d\u00edslo, kter\u00e9 nen\u00ed v\u011bt\u0161\u00ed ne\u017e 2561024, nelze t\u00edmto zp\u016fsobem vyprodukovat.<\/p>\n

Ale napi\u0161eme program v Pythonu, kter\u00fd generuje v\u0161echny mo\u017en\u00e9 kilobajtov\u00e9 texty, spou\u0161t\u00ed je a pokud n\u011bkter\u00fd z nich vyprodukuje n\u011bjak\u00e9 \u010d\u00edslo, p\u0159id\u00e1 toto \u010d\u00edslo do slovn\u00edku dosa\u017eiteln\u00fdch. Po kontrole v\u0161ech 2561024 mo\u017enost\u00ed, bez ohledu na to, jak dlouho to zabere \u2014 program hled\u00e1, kter\u00e9 nejmen\u0161\u00ed \u010d\u00edslo chyb\u00ed ve slovn\u00edku, a vyprodukuje toto \u010d\u00edslo. Zd\u00e1 se b\u00fdt z\u0159ejm\u00e9, \u017ee takov\u00fd program se vejde do kilobajtu k\u00f3du \u2014 a vyprodukuje to \u010d\u00edslo, kter\u00e9 nen\u00ed mo\u017en\u00e9 vyprodukovat kilobajtov\u00fdm programem!<\/p>\n

Kde je tedy te\u010f h\u00e1\u010dek? Nen\u00ed mo\u017en\u00e9 to p\u0159ev\u00e9st na neform\u00e1lnost znak\u016f!<\/p>\n

Pokud v\u00e1s zm\u00e1tlo to, \u017ee n\u00e1\u0161 program bude vy\u017eadovat astronomick\u00e9 mno\u017estv\u00ed pam\u011bti pro pr\u00e1ci \u2014 slovn\u00edk (nebo bitov\u00e9 pole) o 2561024 elementech \u2014 pak lze to sam\u00e9 uskute\u010dnit i bez n\u011bj: pro ka\u017ed\u00e9 z 2561024 \u010d\u00edsel postupn\u011b proch\u00e1zet v\u0161echny 2561024 mo\u017en\u00e9 programy, dokud nenajdeme ten prav\u00fd. Nen\u00ed d\u016fle\u017eit\u00e9, \u017ee takov\u00fd prohled\u00e1vac\u00ed proces potrv\u00e1 velmi dlouho: po kontrole m\u00e9n\u011b ne\u017e (2561024)2 p\u00e1r\u016f \u010d\u00edsla a programu se p\u0159ece jen ukon\u010d\u00ed a najde to tajn\u00e9 \u010d\u00edslo.<\/p>\n

Nebo se neukon\u010d\u00ed? V\u017edy\u0165 mezi v\u0161emi programy, kter\u00e9 budou vyzkou\u0161eny, se objev\u00ed while True: pass<\/code> (a jej\u00ed funk\u010dn\u00ed analogy) \u2014 a d\u00e1l u\u017e s kontrolou takov\u00e9ho programu ni\u010demu nepom\u016f\u017eeme!<\/p>\n

Na rozd\u00edl od Berryho paradoxu, kde byl h\u00e1\u010dek v neform\u00e1lnosti znak\u016f, v druh\u00e9m p\u0159\u00edpad\u011b m\u00e1me dob\u0159e zamaskovanou p\u0159eformulaci \"probl\u00e9mu zastaven\u00ed\"<\/a><\/noindex>. Fakt je ten, \u017ee nen\u00ed mo\u017en\u00e9 v kone\u010dn\u00e9m \u010dase ur\u010dit v\u00fdstup programu. Zejm\u00e9na kolmogorovsk\u00e1 slo\u017eitost nen\u00ed v\u00fdpo\u010ditateln\u00e1.<\/a><\/noindex>: neexistuje \u017e\u00e1dn\u00fd algoritmus, kter\u00fd by umo\u017enil naj\u00edt d\u00e9lku nejkrat\u0161\u00edho programu, kter\u00fd toto \u010d\u00edslo vytiskne; proto neexistuje ani \u0159e\u0161en\u00ed pro \u00falohu Berry \u2014 naj\u00edt d\u00e9lku nejkrat\u0161\u00edho slovn\u00edho vyj\u00e1d\u0159en\u00ed pro dan\u00e9 \u010d\u00edslo.
\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\udd47Paradoxy o kompresi dat | ProHoster","description":"\u00daloha komprese dat v jej\u00ed nejjednodu\u0161\u0161\u00ed form\u011b se m\u016f\u017ee vztahovat na.","canonical_url":"https:\/\/prohoster.info\/cs\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"cs_CZ","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\/cs\/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\/cs\/wp-json\/wp\/v2\/posts\/31157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/comments?post=31157"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/posts\/31157\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/media\/23125"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/media?parent=31157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/categories?post=31157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/tags?post=31157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}