{"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\/ro\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","title":{"rendered":"Paradoxuri despre comprimarea datelor","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"<p><img decoding=\"async\" alt=\"Paradoxuri despre comprimarea datelor\" src=\"\/wp-content\/uploads\/2019\/04\/d15fed5cc55334e6bb9bc3bbd7cbf50c.jpeg\" style=\"display:block;margin: 0 auto;\" \/> Problema comprim\u0103rii datelor, \u00een cea mai simpl\u0103 form\u0103, poate fi referitoare la numere \u0219i na\u0219terea lor. Numerele pot fi reprezentate prin numeraluri (<i>\"unzeci\"<\/i> pentru num\u0103rul 11), prin expresii matematice (<i>\"doi la puterea dou\u0103zeci\"<\/i> pentru 1048576), prin expresii textuale (<i>\"cinci nou\u0103\"<\/i> pentru 99999), prin nume proprii (<i>\"num\u0103rul fiarei\"<\/i> pentru 666, <i>\"anul mor\u021bii lui Turing\"<\/i> pentru 1954), sau prin combina\u021bii arbitrare ale acestora. Orice denumire este acceptabil\u0103 at\u00e2ta timp c\u00e2t interlocutorul poate identifica f\u0103r\u0103 echivoc despre ce num\u0103r este vorba. Este evident c\u0103 a spune interlocutorului <i>\"factorialul lui opt\"<\/i> este mai eficient dec\u00e2t o denumire echivalent\u0103 <i>\"patruzeci de mii trei sute dou\u0103zeci\"<\/i>. Aici apare \u00eentrebarea logic\u0103: care este cea mai scurt\u0103 denumire pentru un num\u0103r dat?<\/p>\n<p>Filozoful Bertrand Russell a publicat \u00een 1908 <noindex><a rel=\"nofollow\" href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9F%D0%B0%D1%80%D0%B0%D0%B4%D0%BE%D0%BA%D1%81_%D0%91%D0%B5%D1%80%D1%80%D0%B8\">\"paradoxul Berry\"<\/a><\/noindex>, care abordeaz\u0103 problema denumirii numerelor dintr-un unghi opus: <b>care este cel mai mic num\u0103r pentru care nu sunt suficiente optzeci de litere pentru a-l denumi?<\/b><br \/>\nUn astfel de num\u0103r trebuie s\u0103 existe: din cele optzeci de litere ruse\u0219ti \u0219i spa\u021biile se pot forma maxim 3480 de denumiri, a\u0219adar, folosind optzeci de litere, nu se pot denumi mai mult de 3480 de numere. Asta \u00eenseamn\u0103 c\u0103 un num\u0103r, nu mai mare de 3480, nu poate fi denumit astfel.<\/p>\n<p>Deci, acestui num\u0103r \u00eei va corespunde denumirea <i>\"cel mai mic num\u0103r pentru care nu sunt suficiente optzeci de litere\"<\/i>, care con\u021bine doar 78 de litere! Pe de o parte, acest num\u0103r trebuie s\u0103 existe; pe de alt\u0103 parte, dac\u0103 acest num\u0103r exist\u0103, denumirea sa nu \u00eei corespunde. Paradox!<noindex><a rel=\"nofollow\" name=\"habracut\"><\/a><\/noindex><\/p>\n<p>Cel mai simplu mod de a ignora acest paradox este s\u0103 facem referire la informalitatea denumirilor verbale. Se spune c\u0103, dac\u0103 \u00een denumiri ar fi admis un singur set definit de expresii, atunci <i>\"cel mai mic num\u0103r pentru care nu sunt suficiente optzeci de litere\"<\/i> nu ar fi o denumire acceptabil\u0103, \u00een timp ce denumirile practic utile de tipul <i>\"factorialul lui opt\"<\/i> ar r\u0103m\u00e2ne acceptabile.<\/p>\n<p>Exist\u0103 metode formale de a descrie secven\u021ba (algoritmul) ac\u021biunilor asupra numerelor? Da, \u0219i din bel\u0219ug \u2014 acestea se numesc limbaje de programare. Vom folosi \u00een loc de denumiri verbale programe (de exemplu, \u00een Python) care s\u0103 emit\u0103 numerele necesare. De exemplu, pentru cinci nou\u0103 se potrive\u0219te programul <code>print(\"9\"*5)<\/code>\u00cen continuare, ne vom interesa de cea mai scurt\u0103 program\u0103 pentru un num\u0103r dat. Lungimea unei astfel de programe se nume\u0219te <noindex><a rel=\"nofollow\" href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9A%D0%BE%D0%BB%D0%BC%D0%BE%D0%B3%D0%BE%D1%80%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C\">complexitate kolmogorov<\/a><\/noindex> a num\u0103rului; acesta este limitarea teoretic\u0103 p\u00e2n\u0103 la care un num\u0103r dat poate fi comprimat.<\/p>\n<p>\u00cen locul paradoxului Berry, acum putem considera un analog: <b>care este cel mai mic num\u0103r pentru a c\u0103rui afi\u0219are nu este suficient\u0103 o program\u0103 de un kilobyte?<\/b><\/p>\n<p>Vom ra\u021biona la fel ca \u00eenainte: exist\u0103 2561024 texte de un kilobyte, ceea ce \u00eenseamn\u0103 c\u0103 cu programele de un kilobyte pot fi generate nu mai mult de 2561024 numere. A\u0219adar, un anumit num\u0103r, nu mai mare dec\u00e2t 2561024, nu poate fi generat \u00een acest mod.<\/p>\n<p>Dar vom scrie un program \u00een Python care genereaz\u0103 toate textele posibile de un kilobyte, le execut\u0103, iar dac\u0103 acestea afi\u0219eaz\u0103 un num\u0103r, atunci adaug\u0103 acel num\u0103r \u00een dic\u021bionarul numeric. Dup\u0103 verificarea tuturor celor 2561024 posibilit\u0103\u021bi, indiferent de timpul necesar \u2014 programul caut\u0103 care este cel mai mic num\u0103r absent \u00een dic\u021bionar \u0219i \u00eel afi\u0219eaz\u0103. Se pare c\u0103 este evident c\u0103 o astfel de program\u0103 va \u00eenc\u0103pea \u00eentr-un kilobyte de cod \u2014 \u0219i va afi\u0219a exact acel num\u0103r care nu poate fi generat de o program\u0103 de un kilobyte!<\/p>\n<p>Dar care este capcana acum? Nu mai putem da vina pe informalitatea denumirilor!<\/p>\n<p>Dac\u0103 te \u00eengrijoreaz\u0103 faptul c\u0103 programul nostru va necesita o cantitate astronomic\u0103 de memorie pentru a func\u021biona \u2014 un dic\u021bionar (sau un tablou de bi\u021bi) cu 2561024 elemente \u2014 atunci totul poate fi realizat \u0219i f\u0103r\u0103 el: pentru fiecare dintre cele 2561024 numere, pe r\u00e2nd, s\u0103 \u00eencerc\u0103m toate cele 2561024 programe posibile p\u00e2n\u0103 c\u00e2nd g\u0103sim unul potrivit. Nu este important c\u0103 o astfel de \u00eencercare va dura foarte mult: dup\u0103 verificarea a mai pu\u021bin de (2561024)2 perechi de num\u0103r \u0219i program, ea se va \u00eencheia \u0219i va g\u0103si acel num\u0103r dorit.<\/p>\n<p>Sau nu se va \u00eencheia? C\u0103ci printre toate programele care vor fi testate, se va \u00eent\u00e2lni <code>while True: pass<\/code> (\u0219i omologii s\u0103i func\u021bionali) \u2014 iar verificarea unei astfel de programe nu va continua!<\/p>\n<p>Spre deosebire de paradoxul Berry, \u00een care capcana era \u00een informalitatea denumirilor, \u00een al doilea caz avem o reformulare bine camuflat\u0103 a <noindex><a rel=\"nofollow\" href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D0%BE%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8\">\u00abproblemei opririi\u00bb<\/a><\/noindex>. Ceea ce este important este c\u0103, \u00een functie de program, nu se poate determina rezultatul s\u0103u \u00eentr-un timp finit. \u00cen special, complexitatea kolmogorov <noindex><a rel=\"nofollow\" href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F\">nu este calculabil\u0103.<\/a><\/noindex>: nu exist\u0103 niciun algoritm care s\u0103 permit\u0103 pentru un num\u0103r dat g\u0103sirea lungimii celei mai scurte programe care produce acel num\u0103r; prin urmare, nu exist\u0103 solu\u021bie nici pentru problema Berry \u2014 de a g\u0103si pentru un num\u0103r dat lungimea celei mai scurte reprezent\u0103ri verbale.<br \/>\n<br \/>Sursa: <a content=\"nofollow\" rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/post\/446976\/\">habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"<p>\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 [&hellip;]<\/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<!-- All in One SEO 5.0.2.1 - aioseo.com -->\n\t<meta name=\"description\" content=\"\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.\" \/>\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Yuri Gagarin\"\/>\n\t<link rel=\"canonical\" href=\"https:\/\/prohoster.info\/ro\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh\" \/>\n\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.2.1\" \/>\n\t\t<meta property=\"og:locale\" content=\"ro_RO\" \/>\n\t\t<meta property=\"og:site_name\" content=\"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\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"\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\" \/>\n\t\t<meta property=\"og:description\" content=\"\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.\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/prohoster.info\/ro\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh\" \/>\n\t\t<meta property=\"og:image\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:secure_url\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:width\" content=\"350\" \/>\n\t\t<meta property=\"og:image:height\" content=\"350\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2019-10-31T18:39:48+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2019-10-31T18:39:48+00:00\" \/>\n\t\t<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<meta property=\"article:author\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"\ud83e\udd47Paradoxurile comprim\u0103rii datelor | ProHoster","description":"Problema comprim\u0103rii datelor \u00een forma sa cea mai simpl\u0103 poate fi asociat\u0103 cu.","canonical_url":"https:\/\/prohoster.info\/ro\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"ro_RO","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\/ro\/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\/ro\/wp-json\/wp\/v2\/posts\/31157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/comments?post=31157"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/posts\/31157\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/media\/23125"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/media?parent=31157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/categories?post=31157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/ro\/wp-json\/wp\/v2\/tags?post=31157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}