{"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\/pl\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","title":{"rendered":"Paradoksy kompresji danych","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Paradoksy Zadanie kompresji danych w swojej najprostszej formie mo\u017ce odnosi\u0107 si\u0119 do liczb i ich oznacze\u0144. Liczby mog\u0105 by\u0107 oznaczane liczebnikami (\"jedena\u015bcie\"<\/i> dla liczby 11), wyra\u017ceniami matematycznymi (\"dwa do dwudziestej\"<\/i> dla 1048576), wyra\u017ceniami tekstowymi (\"pi\u0119\u0107 dziewi\u0105tek\"<\/i> dla 99999), nazwami w\u0142asnymi (\"liczba bestii\"<\/i> dla 666, \"rok \u015bmierci Turinga\"<\/i> dla 1954), lub dowolnymi ich kombinacjami. Odpowiednie jest ka\u017cde oznaczenie, za pomoc\u0105 kt\u00f3rego rozm\u00f3wca b\u0119dzie w stanie jednoznacznie okre\u015bli\u0107, o kt\u00f3rej liczbie mowa. Oczywiste jest, \u017ce poinformowanie rozm\u00f3wcy \"silnia o\u015bmiu\"<\/i> jest skuteczniejsze ni\u017c r\u00f3wnowa\u017cne oznaczenie \"czterdzie\u015bci tysi\u0119cy trzysta dwadzie\u015bcia\"<\/i>. Tutaj pojawia si\u0119 logiczne pytanie: jakie oznaczenie dla danego liczby jest najkr\u00f3tsze?<\/p>\n

Filozof Bertrand Russell w 1908 roku opublikowa\u0142 \"paradoks Berry'ego\"<\/a><\/noindex>, kt\u00f3ry porusza kwesti\u0119 oznacze\u0144 liczb z przeciwnej strony: jak\u0105 jest najmniejsza liczba, dla oznaczenia kt\u00f3rej nie wystarczy osiemdziesi\u0119ciu liter?<\/b>
\nTaka liczba musi istnie\u0107: z osiemdziesi\u0119ciu rosyjskich liter i spacji mo\u017cna stworzy\u0107 tylko 3480 oznacze\u0144, wi\u0119c przy u\u017cyciu osiemdziesi\u0119ciu liter mo\u017cna oznaczy\u0107 nie wi\u0119cej ni\u017c 3480 liczb. Oznacza to, \u017ce pewna liczba, nie wi\u0119ksza ni\u017c 3480, nie mo\u017ce by\u0107 w ten spos\u00f3b oznaczona.<\/p>\n

Oznacza to, \u017ce tej liczbie b\u0119dzie odpowiada\u0107 oznaczenie \"najmniejsza liczba, dla oznaczenia kt\u00f3rej nie wystarczy osiemdziesi\u0119ciu liter\"<\/i>, kt\u00f3re sk\u0142ada si\u0119 tylko z 78 liter! Z jednej strony, ta liczba musi istnie\u0107; z drugiej, je\u015bli ta liczba istnieje, to jej oznaczenie nie odpowiada jej. Paradoks!<\/a><\/noindex><\/p>\n

Najprostszy spos\u00f3b, aby zbagatelizowa\u0107 ten paradoks, to odwo\u0142a\u0107 si\u0119 do nieformalno\u015bci s\u0142ownych oznacze\u0144. M\u00f3wi\u0105c, \u017ce gdyby w oznaczeniach dopuszczany by\u0142 jedynie okre\u015blony zestaw wyra\u017ce\u0144, to \"najmniejsza liczba, dla oznaczenia kt\u00f3rej nie wystarczy osiemdziesi\u0119ciu liter\"<\/i> nie by\u0142oby dozwolonym oznaczeniem, podczas gdy praktycznie u\u017cyteczne oznaczenia takie jak \"silnia o\u015bmiu\"<\/i> pozosta\u0142yby dozwolone.<\/p>\n

Czy istniej\u0105 formalne sposoby opisu sekwencji (algorytmu) dzia\u0142a\u0144 na liczbach? Tak, i jest ich wiele \u2014 nazywa si\u0119 je j\u0119zykami programowania. Zamiast s\u0142ownych oznacze\u0144 u\u017cyjemy program\u00f3w (na przyk\u0142ad w Pythonie), kt\u00f3re wy\u015bwietlaj\u0105 odpowiednie liczby. Na przyk\u0142ad, dla pi\u0119ciu dziewi\u0105tek, odpowiedni b\u0119dzie program print(\"9\"*5)<\/code>. Nadal b\u0119dziemy si\u0119 interesowa\u0107 najkr\u00f3tszym programem dla danego liczby. D\u0142ugo\u015b\u0107 takiego programu nazywa si\u0119 z\u0142o\u017cono\u015bci\u0105 Kolmogorowa<\/a><\/noindex> liczby; to teoretyczna granica, do kt\u00f3rej dan\u0105 liczb\u0119 mo\u017cna skompresowa\u0107.<\/p>\n

Zamiast paradoksu Berry'ego mo\u017cemy teraz rozwa\u017cy\u0107 analogiczny: jak\u0105 najmniejsz\u0105 liczb\u0119 mo\u017cna uzyska\u0107 z programu o wielko\u015bci mniejszej ni\u017c jeden kilobajt?<\/b><\/p>\n

Rozwa\u017cania prowadzi\u0107 b\u0119dziemy tak samo, jak poprzednio: istnieje 2561024 kilobajtowych tekst\u00f3w, co oznacza, \u017ce za pomoc\u0105 program\u00f3w o wielko\u015bci jednego kilobajta mo\u017cna uzyska\u0107 najwy\u017cej 2561024 liczb. Zatem istnieje pewna liczba, kt\u00f3ra nie jest wi\u0119ksza ni\u017c 2561024, kt\u00f3rej nie mo\u017cna uzyska\u0107 w ten spos\u00f3b.<\/p>\n

Ale napiszemy program w Pythonie, kt\u00f3ry generuje wszystkie mo\u017cliwe teksty o wielko\u015bci jednego kilobajta, uruchamia je, a je\u015bli kt\u00f3re\u015b z nich generuje jak\u0105\u015b liczb\u0119 - dodaje t\u0119 liczb\u0119 do s\u0142ownika osi\u0105galnych. Po sprawdzeniu wszystkich 2561024 mo\u017cliwo\u015bci, niewa\u017cne ile to zajmie - program wyszukuje, kt\u00f3ra najmniejsza liczba brakuje w s\u0142owniku i zwraca t\u0119 liczb\u0119. Wydaje si\u0119 oczywiste, \u017ce taki program zmie\u015bci si\u0119 w jednym kilobajcie kodu - i zwr\u00f3ci t\u0119 liczb\u0119, kt\u00f3rej nie mo\u017cna uzyska\u0107 programem o wielko\u015bci jednego kilobajta!<\/p>\n

Gdzie wi\u0119c tkwi haczyk teraz? Nie mo\u017cna ju\u017c go zrzuci\u0107 na nieformalno\u015b\u0107 oznacze\u0144!<\/p>\n

Je\u015bli martwi Was to, \u017ce nasz program wymaga\u0142by astronomicznej ilo\u015bci pami\u0119ci do dzia\u0142ania - s\u0142ownik (lub tablica bitowa) z 2561024 elementami - mo\u017cna to wszystko zrealizowa\u0107 bez niego: dla ka\u017cdego z 2561024 liczb po kolei przeszukiwa\u0107 wszystkie 2561024 mo\u017cliwe programy, a\u017c znajdzie si\u0119 odpowiedni. Nie wa\u017cne, \u017ce takie przeszukiwanie zajmie bardzo du\u017co czasu: po sprawdzeniu mniej ni\u017c (2561024)2 par liczby i programu musi si\u0119 zako\u0144czy\u0107 i znale\u017a\u0107 t\u0119 wymarzon\u0105 liczb\u0119.<\/p>\n

Czy jednak si\u0119 zako\u0144czy? Wszak w\u015br\u00f3d wszystkich program\u00f3w, kt\u00f3re b\u0119d\u0105 sprawdzane, znajdzie si\u0119 while True: pass<\/code> (i jej funkcjonalne odpowiedniki) - i dalej sprawdzenie takiego programu nie p\u00f3jdzie ju\u017c naprz\u00f3d!<\/p>\n

W przeciwie\u0144stwie do paradoksu Berry'ego, gdzie haczyk tkwi\u0142 w nieformalno\u015bci oznacze\u0144, w drugim przypadku mamy do czynienia z dobrze zamaskowan\u0105 przekszta\u0142ceniem \"problemu zatrzymania\"<\/a><\/noindex>. Istot\u0105 sprawy jest to, \u017ce z programu nie mo\u017cna w ko\u0144cu okre\u015bli\u0107 jego wyniku w sko\u0144czonym czasie. W szczeg\u00f3lno\u015bci, z\u0142o\u017cono\u015b\u0107 Kolmogorowa jest nieobliczalna<\/a><\/noindex>Nie ma takiego algorytmu, kt\u00f3ry pozwala\u0142by dla podanej liczby znale\u017a\u0107 d\u0142ugo\u015b\u0107 najkr\u00f3tszego programu, kt\u00f3ry t\u0119 liczb\u0119 wy\u015bwietla; a zatem nie ma te\u017c rozwi\u0105zania dla problemu Berry'ego \u2014 znale\u017a\u0107 dla podanej liczby d\u0142ugo\u015b\u0107 najkr\u00f3tszego s\u0142ownego oznaczenia.
\n
\u0179r\u00f3d\u0142o: 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\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 dotycz\u0105ce kompresji danych | ProHoster","description":"Zadanie kompresji danych w swojej najprostszej formie mo\u017ce odnosi\u0107 si\u0119 do.","canonical_url":"https:\/\/prohoster.info\/pl\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"pl_PL","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\/pl\/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\/pl\/wp-json\/wp\/v2\/posts\/31157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/comments?post=31157"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/posts\/31157\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/media\/23125"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/media?parent=31157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/categories?post=31157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/tags?post=31157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}