{"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\/hr\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","title":{"rendered":"Paradoxi o kompresiji podataka","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Paradoxi Zadatak kompresije podataka u svom najjednostavnijem obliku mo\u017ee se odnositi na brojeve i njihove oznake. Brojevi se mogu ozna\u010davati brojkama (\u201ejedanaest\u201c<\/i> za broj 11), matemati\u010dkim izrazima (\u201edva u dvadesetoj\u201c<\/i> za 1048576), string izrazima (\u201epet devetki\u201c<\/i> za 99999), vlastitim imenima (\u201ebroj zvijeri\u201c<\/i> za 666, \u201egodina Turingove smrti\u201c<\/i> za 1954.), ili proizvoljnim njihovim kombinacijama. Svaka oznaka koja omogu\u0107ava sugovorniku da jednozna\u010dno odredi o kojem broju se radi je prihvatljiva. O\u010dito je da je u\u010dinkovitije re\u0107i sugovorniku \u201efaktorijal osam\u201c<\/i> nego ekvivalentna oznaka \u201e\u010detrdeset tisu\u0107a trideset\u201c<\/i>. Ovdje se postavlja logi\u010dno pitanje: koja je oznaka za zadani broj najkra\u0107a?<\/p>\n

Filozof Bertrand Russell je 1908. godine objavio \u201eBerryjev paradoks\u201c<\/a><\/noindex>, koji se bavi pitanjem oznaka brojeva s suprotne strane: koji je najmanji broj za \u010diju oznaku nije dovoljno osamdeset slova?<\/b>
\nTakav broj mora postojati: od osamdeset ruskih slova i razmaka mo\u017ee se sastaviti samo 3480 oznaka, stoga se pomo\u0107u osamdeset slova mo\u017ee ozna\u010diti najvi\u0161e 3480 brojeva. To zna\u010di da nije mogu\u0107e ozna\u010diti neko broj, koje je ne ve\u0107e od 3480, na taj na\u010din.<\/p>\n

Dakle, toj broj \u0107e odgovarati oznaka \u201enajmanji broj za \u010diju oznaku nije dovoljno osamdeset slova\u201c<\/i>, koja sadr\u017ei samo 78 slova! S jedne strane, ovaj broj mora postojati; s druge strane, ako ovaj broj postoji, njegova oznaka mu ne odgovara. Paradoks!<\/a><\/noindex><\/p>\n

Najjednostavniji na\u010din da se odbaci ovaj paradoks je pozvati se na neformalnost usmenih oznaka. Ka\u017eu da, da su u oznakama dopu\u0161teni samo konkretno odre\u0111eni setovi izraza, tada \u201enajmanji broj za \u010diju oznaku nije dovoljno osamdeset slova\u201c<\/i> ne bi bila dopu\u0161tena oznaka, dok su prakti\u010dne korisne oznake poput \u201efaktorijal osam\u201c<\/i> ostale bile dopu\u0161tene.<\/p>\n

Postoje li formalni na\u010dini za opisivanje sekvenci (algoritama) radnji s brojevima? Ima, i u obilju \u2014 nazivaju se programskim jezicima. Umjesto usmenih oznaka koristit \u0107emo programe (na primjer, u Pythonu) koji ispisuju potrebne brojeve. Na primjer, za pet devetki odgovarat \u0107e program print(\"9\"*5)<\/code>. I dalje \u0107emo se zanimati za najkra\u0107i program za zadani broj. Du\u017eina takvog programa naziva se kolmogorovskom slo\u017eeno\u0161\u0107u<\/a><\/noindex> broja; to je teorijska granica do koje se zadani broj mo\u017ee komprimirati.<\/p>\n

Umjesto Berryjeva paradoksa sada mo\u017eemo razmotriti sli\u010dnu situaciju: koji je najmanji broj za \u010dije ispisivanje nije dovoljna kilobajtna programa?<\/b><\/p>\n

Razmi\u0161ljat \u0107emo na isti na\u010din kao prije: postoji 2561024 kilobajtnih tekstova, \u0161to zna\u010di da se kilobajtnih programa mo\u017ee koristiti za ispisivanje najvi\u0161e 2561024 brojeva. Dakle, neki broj, koji nije ve\u0107i od 2561024, ne mo\u017ee se na taj na\u010din ispisati.<\/p>\n

Ali napisat \u0107emo program na Pythonu koji generira sve mogu\u0107e kilobajtne tekstove, izvr\u0161ava ih, a ako ispisuju neki broj \u2014 taj broj dodaje u rje\u010dnik dostupnih. Nakon provjere svih 2561024 mogu\u0107nosti, koliko god vremena to trajalo \u2014 program tra\u017ei koji je najmanji broj koji nedostaje u rje\u010dniku, i ispisuje taj broj. \u010cini se o\u010ditim da \u0107e takav program stati u kilobajt koda \u2014 i ispisati onaj broj koji se ne mo\u017ee ispisati kilobajtnim programom!<\/p>\n

U \u010demu je sada zamka? Na neformalnost oznaka se vi\u0161e ne mo\u017ee svesti!<\/p>\n

Ako vas mu\u010di to \u0161to \u0107e na\u0161 program zahtijevati astronomski koli\u010dinu memorije za rad \u2014 rje\u010dnik (ili bitna polja) od 2561024 elemenata \u2014 to se sve mo\u017ee posti\u0107i i bez njega: za svako od 2561024 brojeva redom provjeravati svih 2561024 mogu\u0107ih programa, dok se ne na\u0111e odgovaraju\u0107i. Nije va\u017eno \u0161to \u0107e takvo pretra\u017eivanje trajati jako dugo: nakon provjere manje od (2561024)2 parova broja i programa, to \u0107e se zavr\u0161iti i na\u0107i onaj dragocjeni broj.<\/p>\n

Ili se mo\u017eda ne\u0107e zavr\u0161iti? Jer me\u0111u svim programima koji \u0107e biti isprobani naletit \u0107emo na while True: pass<\/code> (i njezine funkcionalne analoge) \u2014 i dalje provjere takvog programa ne\u0107emo mo\u0107i do\u0107i do kraja!<\/p>\n

Za razliku od Berryjeva paradoksa, gdje je zamka bila u neformalnosti oznaka, u drugom slu\u010daju imamo dobro maskiranu preformulaciju \"problema zaustavljanja\"<\/a><\/noindex>. Radi se o tome da se za program u kona\u010dnom vremenu ne mo\u017ee odrediti njegovo ispisivanje. Konkretno, kolmogorovska slo\u017eenost je neizra\u010dunljiva<\/a><\/noindex>: ne postoji algoritam koji bi omogu\u0107io da se za dano broj odredi duljina najkra\u0107eg programa koji ispisuje taj broj; \u0161to zna\u010di da rje\u0161enja za Berryjev problem tako\u0111er nema \u2014 prona\u0107i duljinu najkra\u0107eg verbalnog ozna\u010davanja za dano broj.
\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 kompresiji podataka | ProHoster","description":"Zadatak kompresije podataka u svojoj najjednostavnijoj formi mo\u017ee se odnositi na.","canonical_url":"https:\/\/prohoster.info\/hr\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"hr_HR","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\/hr\/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\/hr\/wp-json\/wp\/v2\/posts\/31157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/hr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/hr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/hr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/hr\/wp-json\/wp\/v2\/comments?post=31157"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/hr\/wp-json\/wp\/v2\/posts\/31157\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/hr\/wp-json\/wp\/v2\/media\/23125"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/hr\/wp-json\/wp\/v2\/media?parent=31157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/hr\/wp-json\/wp\/v2\/categories?post=31157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/hr\/wp-json\/wp\/v2\/tags?post=31157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}