{"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\/et\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","title":{"rendered":"Andmete kokkusurumise paradoksid","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Andmete Andmete kokkusurumise \u00fclesanne oma lihtsaimas vormis v\u00f5ib seonduda numbrite ja nende t\u00e4histustega. Numbrid saab t\u00e4histada numbritega (\u201e\u00fcheteistk\u00fcmme\u201c<\/i> 11 kohta), matemaatiliste avaldarvutustega (\u201ekaks kahek\u00fcmnendas\u201c<\/i> 1048576 kohta), stringiavaldusena (\u201eviis \u00fcheksandikku\u201c<\/i> 99999 kohta), omaduss\u00f5nadega (\u201eselle looma number\u201c<\/i> 666 kohta, \u201eTuringi surma aasta\u201c<\/i> 1954 kohta), v\u00f5i nende suvaliste kombinatsioonide kaudu. Sobib iga t\u00e4histus, mille alusel vestluskaaslane suudab \u00fcheselt m\u00e4\u00e4ratleda, millest numbrist jutt. On ilmne, et vestluskaaslasele on t\u00f5husam \u00f6elda \u201ekaheksa faktoriaal\u201c<\/i> kui sellele vastav t\u00e4histus \u201enelik\u00fcmmend tuhat kolmk\u00fcmmend\u201c<\/i>. Siin tekib loogiline k\u00fcsimus: milline t\u00e4histus on antud numbri jaoks k\u00f5ige l\u00fchem?<\/p>\n

Filosoof Bertrand Russell avaldas 1908. aastal \u201eBerry paradoksi\u201c<\/a><\/noindex>, mis k\u00e4sitleb numbri t\u00e4histamise k\u00fcsimust vastupidiselt: milline on v\u00e4ikseim number, mille t\u00e4histamiseks ei piisa kaheksast k\u00fcmnest t\u00e4hest?<\/b>
\nSelline number peab eksisteerima: kaheksast k\u00fcmnest vene t\u00e4hest ja t\u00fchikutest saab kokku vaid 3480 t\u00e4hist, seega saab kaheksast k\u00fcmnest t\u00e4hest t\u00e4histada mitte rohkem kui 3480 numbrit. Seega, mingit numbrit, mis ei ole suurem kui 3480, ei saa sel moel t\u00e4histada.<\/p>\n

Seega vastab sellele numbrile t\u00e4histus \u201ev\u00e4ikseim number, mille t\u00e4histamiseks ei piisa kaheksast k\u00fcmnest t\u00e4hest\u201c<\/i>, kus on kokku 78 t\u00e4hte! \u00dchest k\u00fcljest peab see number existeerima; teisest k\u00fcljest, kui see number eksisteerib, siis ei vasta selle t\u00e4histus sellele. Paradoks!<\/a><\/noindex><\/p>\n

Lihtsaim viis sellest paradoksist k\u00f5rvale hiilida on viidata s\u00f5naliste t\u00e4histuste mitteformaalusele. Nagu, kui t\u00e4histustes oleks aktsepteeritud vaid kindel ja m\u00e4\u00e4ratletud v\u00e4ljendite kogum, siis \u201ev\u00e4ikseim number, mille t\u00e4histamiseks ei piisa kaheksast k\u00fcmnest t\u00e4hest\u201c<\/i> ei oleks see kehtiv t\u00e4histus, samas kui praktiliselt kasulikud t\u00e4histused, nagu \u201ekaheksa faktoriaal\u201c<\/i> j\u00e4\u00e4ksid kehtivaks.<\/p>\n

Kas on olemas formaalseid viise numbritega tehtavate toimingute (algoritmi) j\u00e4rjekorra kirjeldamiseks? Jah, ja k\u00fcllaga - neid nimetatakse programmeerimiskeelteks. Kasutame s\u00f5naliste t\u00e4histuste asemel programme (n\u00e4iteks Pythonis), mis v\u00e4ljastavad vajalikud numbrid. N\u00e4iteks viis \u00fcheksandikku v\u00f5iks sobida programm print(\"9\"*5)<\/code>. J\u00e4tkuvalt huvitume k\u00f5ige l\u00fchemast programmist antud arvu jaoks. Sellise programmi pikkust nimetatakse kolmogorovi keerukuseks<\/a><\/noindex> arvule; see on teoreetiline piir, mille v\u00f5rra antud arvu saab kokku suruda.<\/p>\n

Berry paradoksi asemel v\u00f5ib n\u00fc\u00fcd kaaluda sarnast: milline on k\u00f5ige v\u00e4iksem number, mille v\u00e4ljundiks ei piisa kilobaidist programmist?<\/b><\/p>\n

Arutame nagu varem: eksisteerib 2561024 kilobaidi teksti, seega kilobaidiprogrammidega saab v\u00e4ljundiks saada mitte rohkem kui 2561024 numbrit. Seega mingit arvu, mis ei \u00fcleta 2561024, ei saa sellisel viisil v\u00e4ljundiks saada.<\/p>\n

Kuid kirjutame Pythonis programmi, mis genereerib k\u00f5ik v\u00f5imalikke kilobaidi texte, k\u00e4ivitab need ja kui need v\u00e4ljastavad mingi numbri - lisab selle numbri saavutuste s\u00f5nastikku. P\u00e4rast k\u00f5igi 2561024 variandi kontrollimist, kui kaua see ka ei v\u00f5taks - programm otsib, milline on see k\u00f5ige v\u00e4iksem number, mis puudub s\u00f5nastikust, ja v\u00e4ljastab selle numbri. Tundub ilmselge, et selline programm mahtuks kilobaidi koodi - ja v\u00e4ljastaks just selle numbri, mida ei saa kilobaidiprogrammi abil v\u00e4ljastada!<\/p>\n

Kus on n\u00fc\u00fcd n\u00f5ks? Mitteformaalsust nimelt ei saa enam kasuks tuua!<\/p>\n

Kui teid h\u00e4irib, et meie programm n\u00f5uab t\u00f6\u00f6ks astronoomilist hulka m\u00e4lu - s\u00f5nastik (v\u00f5i bitimassiiv) 2561024 elemendist - siis on v\u00f5imalik k\u00f5ik see ka ilma selleta teostada: igale 2561024 numbrile j\u00e4rjestikku j\u00e4rjestada k\u00f5iki 2561024 v\u00f5imalikke programme, kuni leitakse sobiv. Pole oluline, et selline l\u00e4bivaatamine kestab v\u00e4ga kaua: p\u00e4rast kontrollimist v\u00e4hem kui (2561024)2 paari numbri ja programmi vahel see ju l\u00f5puks l\u00f5peb ja leiab selle kauaoodatud numbri.<\/p>\n

V\u00f5i ei l\u00f5peta? Sest k\u00f5igi katsetatavate programmide seas satume me while True: pass<\/code> (ja tema funktsionaalsed analoogid) - ja edasi niisuguse programmi kontrollimisega ei saagi edasi minna!<\/p>\n

Erinevalt Berry paradoksist, kus n\u00f5ks oli mitteformaalsuses, on teises olukorras meil h\u00e4sti maskeeritud \u00fcmberformuleerimine \u00abpeatumisprobleemist\u00bb<\/a><\/noindex>. Asi on selles, et programmi p\u00f5hjal ei ole v\u00f5imalik selle v\u00e4ljundit l\u00f5pliku ajaga m\u00e4\u00e4rata. Eriti kolmogorovi keerukus on arvutamatu.<\/a><\/noindex>: ei ole olemas mingit algoritmi, mis v\u00f5imaldaks antud arvu jaoks leida k\u00f5ige l\u00fchema programmi pikkust, mis seda arvu v\u00e4ljastab; seega ei ole lahendust ka Berra \u00fclesandele \u2014 leida antud arvu jaoks k\u00f5ige l\u00fchema s\u00f5nalise t\u00e4histuse pikkust.
\n
Allikas: 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\udd47Andmete tihendamise paradokside | ProHoster","description":"Andmete tihendamise \u00fclesanne oma lihtsaimas vormis v\u00f5ib viidata.","canonical_url":"https:\/\/prohoster.info\/et\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"et_EE","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\/et\/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\/et\/wp-json\/wp\/v2\/posts\/31157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/comments?post=31157"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/posts\/31157\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/media\/23125"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/media?parent=31157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/categories?post=31157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/et\/wp-json\/wp\/v2\/tags?post=31157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}