{"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":"Andmed surumise paradoksid","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Andmed Andmete tihendamine oma lihtsaimas vormis v\u00f5ib viidata numbritele ja nende t\u00e4histustele. Numbrid v\u00f5ivad olla t\u00e4histatud arvudena (\u00ab\u00fcheteistk\u00fcmne\u00bb<\/i> arvule 11), matemaatiliste v\u00e4ljendite (\u00abkaks kahek\u00fcmnendas\u00bb<\/i> arvule 1048576), stringi v\u00e4ljendite (\u00abviis \u00fcheksat\u00bb<\/i> arvule 99999), nimede (\u00abloomade number\u00bb<\/i> arvule 666, \u00abTuringi surmaasta\u00bb<\/i> arvule 1954), v\u00f5i nende meelevaldsete kombinatsioonide kaudu. Sobib iga t\u00e4histus, mille kaudu vestluspartner suudab \u00fcheselt m\u00f5ista, millest arvust jutt k\u00e4ib. Ilmselgelt on soovitada vestluspartnerile \u00abkaheksa faktoriaal\u00bb<\/i> efektiivsem kui ekvivalentne t\u00e4histus \u00abnelik\u00fcmmend tuhat kolmk\u00fcmmend\u00bb<\/i>. Siit tekib loogiline k\u00fcsimus: mis t\u00e4histus on antud arvu jaoks k\u00f5ige l\u00fchem?<\/p>\n

Filosoof Bertrand Russell avaldas 1908. aastal \u00abBerry paradoksi\u00bb<\/a><\/noindex>, mis k\u00e4sitleb numbrite t\u00e4histamise k\u00fcsimust vastupidiselt: mis on k\u00f5ige v\u00e4iksem number, mille t\u00e4histamiseks ei piisa kaheksak\u00fcmnest t\u00e4hest?<\/b>
\nSelline number peab eksisteerima: kaheksak\u00fcmnest vene t\u00e4hest ja t\u00fchikutest saab moodustada vaid 3480 t\u00e4histust, seega v\u00f5ib kaheksak\u00fcmne t\u00e4he abil t\u00e4histada mitte rohkem kui 3480 numbrit. Seega, mingit numbrit, mis on suurem kui 3480, ei saa sellisel viisil t\u00e4histada.<\/p>\n

Seega vastab sellele numbrile t\u00e4histus \u00abk\u00f5ige v\u00e4iksem number, mille t\u00e4histamiseks ei piisa kaheksak\u00fcmnest t\u00e4hest\u00bb<\/i>, kus on koguni 78 t\u00e4hte! \u00dchelt poolt peab see number eksisteerima; teiselt poolt, 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 mitteformaalsusele. Justkui, kui t\u00e4histustes lubataks ainult konkreetset m\u00e4\u00e4ratletud v\u00e4ljendite komplekti, siis \u00abk\u00f5ige v\u00e4iksem number, mille t\u00e4histamiseks ei piisa kaheksak\u00fcmnest t\u00e4hest\u00bb<\/i> ei oleks mitteaktsepteeritav t\u00e4histus, samas kui praktiliselt kasulikud t\u00e4histused nagu \u00abkaheksa faktoriaal\u00bb<\/i> p\u00fcsivad aktsepteeritavana.<\/p>\n

Kas on olemas formaalseid viise, kuidas kirjeldada tegevuste (algoritmi) j\u00e4rjestust arvudega? On, ja k\u00fcll ja k\u00fcll \u2014 neid nimetatakse programmeerimiskeelteks. Kasutame s\u00f5naliste t\u00e4histuste asemel programme (n\u00e4iteks Pythonis), mis genereerivad vajalikud numbrid. N\u00e4iteks, viie \u00fcheksa jaoks sobib programm print(\"9\"*5)<\/code>. J\u00e4tkame k\u00f5ige l\u00fchema programmi leidmist antud arvu jaoks. Selle programmi pikkust nimetatakse Kolmogorovi keerukuseks<\/a><\/noindex> arvule; see on teoreetiline piir, kuhu antud arv saab tihendatuna j\u00f5uda.<\/p>\n

Berry paradoksi asemel saab arutada sarnast: mis on k\u00f5ige v\u00e4iksem number, mille v\u00e4ljastamiseks ei piisa kilobaitidest programmist?<\/b><\/p>\n

J\u00e4tkame sama loogikaga: on olemas 2561024 kilobaitilist teksti, seega saavad kilobaitilised programmid genereerida mitte rohkem kui 2561024 numbrit. Seega, mingit numbrit, mis on suurem kui 2561024, ei saa sellisel viisil genereerida.<\/p>\n

Kuid kirjutame Pythonis programmi, mis genereerib k\u00f5ik v\u00f5imalikud kilobaitilised tekstid, k\u00e4ivitab need ning kui need annavad mingi arvu \u2014 lisab selle arvu saavutuste s\u00f5naraamatusse. P\u00e4rast k\u00f5ikide 2561024 v\u00f5imaluse kontrollimist, olgu see kui kaua see ka ei kesta \u2014 programm otsib, mis on k\u00f5ige v\u00e4iksem number, mis puudub s\u00f5naraamatust, ja v\u00e4ljastab selle numbri. Paistab ilmselge, et selline programm mahub kilobaiti koodi \u2014 ja v\u00e4ljastab just selle arvu, mida ei saa kilobaitide programmiga!<\/p>\n

Kus on n\u00fc\u00fcd konks? N\u00fc\u00fcd ei saa mitteformaalsust t\u00e4histustes selle alla kirjutada!<\/p>\n

Kui teid h\u00e4irib see, et meie programm vajab astronomilist hulka m\u00e4lu t\u00f6\u00f6ks \u2014 s\u00f5naraamat (v\u00f5i bitimassiiv) 2561024 elemendiga \u2014 siis v\u00f5ib k\u00f5ik \u00fclaltoodu teostada ka ilma selleta: iga\u00fche 2561024 numbri korral j\u00e4rjestikune \u00fcritamine k\u00f5iki 2561024 v\u00f5imalikke programme, kuni sobiv leitakse. Pole oluline, kui kaua selline proovimine kestab: p\u00e4rast kontrollimist v\u00e4hem kui (2561024)2 paari numbri ja programmi vahel, tuleb see ju l\u00f5pule ja leiab selle kuru arvu.<\/p>\n

V\u00f5i ei l\u00f5peta? L\u00f5ppude l\u00f5puks, k\u00f5ikide katsetatavate programmide seas satub kokku while True: pass<\/code> (ja tema funktsionaalsed analoogid) \u2014 ja edasi sellise programmi kontrollimine ei suju!<\/p>\n

Erinevalt Berry paradoksist, kus konks oli s\u00f5naliste t\u00e4histuste mitteformaalsuses, on teises olukorras tegemist h\u00e4sti maskeeritud \u00fcmbervormistamisega \u00abpeatumise probleem\u00bb<\/a><\/noindex>. T\u00f5de on, et programmi j\u00e4rgi ei ole v\u00f5imalik l\u00f5puni m\u00e4\u00e4rata selle v\u00e4ljundit. Eriti on Kolmogorovi keerukus arvutatav.<\/a><\/noindex>: ei ole mingit algoritmi, mis v\u00f5imaldaks antud arvu jaoks leida l\u00fchima programmi pikkust, mis seda arvu v\u00e4ljundab; see t\u00e4hendab, et ka Beri probleemile \u2014 leida antud arvu jaoks l\u00fchima s\u00f5nalise t\u00e4histuse pikkus \u2014 ei ole lahendust.
\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 kohta | ProHoster","description":"Andmete tihendamise \u00fclesanne oma k\u00f5ige lihtsamal kujul 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}]}}