{"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\/hu\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","title":{"rendered":"Adatcs\u00f6kkent\u00e9s paradoxonjai","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Adatcs\u00f6kkent\u00e9s Az adatok t\u00f6m\u00f6r\u00edt\u00e9s\u00e9nek feladata legegyszer\u0171bb form\u00e1j\u00e1ban a sz\u00e1mokra \u00e9s jel\u00f6l\u00e9s\u00fckre vonatkozhat. A sz\u00e1mokat sz\u00e1mmal lehet jel\u00f6lni (tizenegy<\/i> a 11-es sz\u00e1m sz\u00e1m\u00e1ra), matematikai kifejez\u00e9sekkel (kett\u0151 a huszadikon<\/i> 1048576-ra), sz\u00f6veges kifejez\u00e9sekkel (\u00f6t kilences<\/i> a 99999-re), tulajdonnevekkel (a fenevad sz\u00e1ma<\/i> a 666-ra, Turing hal\u00e1l\u00e1nak \u00e9ve<\/i> 1954-re), vagy b\u00e1rmilyen v\u00e9letlenszer\u0171 kombin\u00e1ci\u00f3jukkal. B\u00e1rmilyen jel\u00f6l\u00e9s \u00e9rv\u00e9nyes, amellyel a besz\u00e9lget\u0151partner egy\u00e9rtelm\u0171en meg tudja hat\u00e1rozni, hogy melyik sz\u00e1mr\u00f3l van sz\u00f3. Nyilv\u00e1nval\u00f3, hogy elmondani a besz\u00e9lget\u0151partnernek a nyolc faktori\u00e1lisa<\/i> hat\u00e9konyabb, mint az ekvivalens jel\u00f6l\u00e9s negyven ezer h\u00e1romsz\u00e1zh\u00fasz.<\/i>Itt felmer\u00fcl a logikus k\u00e9rd\u00e9s: mi a legr\u00f6videbb jel\u00f6l\u00e9s a megadott sz\u00e1mra?<\/p>\n

Bertrand Russell filoz\u00f3fus 1908-ban publik\u00e1lta a Berry-paradoxont<\/a><\/noindex>, amely a sz\u00e1mok jel\u00f6l\u00e9s\u00e9nek k\u00e9rd\u00e9s\u00e9t a m\u00e1sik oldalr\u00f3l \u00e9rinti: melyik a legkisebb sz\u00e1m, amely megjel\u00f6l\u00e9s\u00e9hez nem elegend\u0151 nyolcvan bet\u0171?<\/b>
\nOlyan sz\u00e1mnak kell l\u00e9teznie: nyolcvan orosz bet\u0171 \u00e9s sz\u00f3k\u00f6z felhaszn\u00e1l\u00e1s\u00e1val csak 3480 jel\u00f6l\u00e9st lehet l\u00e9trehozni, teh\u00e1t nyolcvan bet\u0171 felhaszn\u00e1l\u00e1s\u00e1val legfeljebb 3480 sz\u00e1m jel\u00f6lhet\u0151. Ez\u00e9rt egy olyan sz\u00e1m, amely nem nagyobb mint 3480, \u00edgy nem jel\u00f6lhet\u0151.<\/p>\n

Ez\u00e9rt ennek a sz\u00e1mnak a jel\u00f6l\u00e9se a legkisebb sz\u00e1m, amely megjel\u00f6l\u00e9s\u00e9hez nem elegend\u0151 nyolcvan bet\u0171<\/i>, amelyben mind\u00f6ssze 78 bet\u0171 tal\u00e1lhat\u00f3! Egyr\u00e9szt ennek a sz\u00e1mnak l\u00e9teznie kell; m\u00e1sr\u00e9szt, ha ez a sz\u00e1m l\u00e9tezik, akkor a jel\u00f6l\u00e9se nem felel meg neki. Paradoxon!<\/a><\/noindex><\/p>\n

A legegyszer\u0171bb m\u00f3dja, hogy elhessegetj\u00fck ezt a paradoxont, ha a sz\u00f3beli jel\u00f6l\u00e9sek inform\u00e1lis volt\u00e1ra hivatkozunk. Mondv\u00e1n, ha csak konkr\u00e9tan meghat\u00e1rozott kifejez\u00e9sek lenn\u00e9nek megengedettek a jel\u00f6l\u00e9sekben, akkor a legkisebb sz\u00e1m, amely megjel\u00f6l\u00e9s\u00e9hez nem elegend\u0151 nyolcvan bet\u0171<\/i> nem lenne elfogadhat\u00f3 jel\u00f6l\u00e9s, m\u00edg a gyakorlatilag hasznos jel\u00f6l\u00e9sek, mint a nyolc faktori\u00e1lisa<\/i> maradn\u00e1nak elfogadhat\u00f3knak.<\/p>\n

Vannak-e form\u00e1lis m\u00f3dszerek a sz\u00e1mokkal kapcsolatos tev\u00e9kenys\u00e9gek (algoritmusok) le\u00edr\u00e1s\u00e1ra? Igen, \u00e9s b\u0151s\u00e9gesen \u2014 \u0151ket programoz\u00e1si nyelveknek h\u00edvj\u00e1k. Helyett\u00fck a sz\u00f3beli jel\u00f6l\u00e9seknek programokat haszn\u00e1ljunk (p\u00e9ld\u00e1ul Pythonban), amelyek a sz\u00fcks\u00e9ges sz\u00e1mokat kiadj\u00e1k. P\u00e9ld\u00e1ul, az \u00f6t kilenseshez megfelel\u0151 lesz a program print(\"9\"*5)<\/code>. Tov\u00e1bbra is \u00e9rdekel minket a legr\u00f6videbb program a megadott sz\u00e1mhoz. Az ilyen program hossz\u00e1t Kolmogorov-komplexit\u00e1snak<\/a><\/noindex> nevezik; ez a elm\u00e9leti hat\u00e1r, ameddig a megadott sz\u00e1mot t\u00f6m\u00f6r\u00edteni lehet.<\/p>\n

A Berry-paradoxon helyett most hasonl\u00f3 lehet\u0151s\u00e9get vizsg\u00e1lhatunk: mi a legkisebb sz\u00e1m, amelynek ki\u00edr\u00e1s\u00e1hoz nem elegend\u0151 egy kilobytes program?<\/b><\/p>\n

A k\u00f6vetkez\u0151 m\u00f3don \u00e9rvel\u00fcnk, mint eddig: l\u00e9tezik 2561024 kilob\u00e1jtos sz\u00f6veg, teh\u00e1t kilob\u00e1jtos programokkal legfeljebb 2561024 sz\u00e1mot lehet ki\u00edrni. Ez\u00e9rt van egy olyan sz\u00e1m, amelyet legfeljebb 2561024-tel ilyen m\u00f3don nem lehet ki\u00edrni.<\/p>\n

De \u00edrjunk egy Python programot, amely gener\u00e1lja az \u00f6sszes lehets\u00e9ges kilob\u00e1jt sz\u00f6veget, futtatja \u0151ket, \u00e9s ha valamelyik sz\u00e1mot ki\u00edr, akkor ezt a sz\u00e1mot hozz\u00e1adja a megval\u00f3s\u00edthat\u00f3 sz\u00e1mok sz\u00f3t\u00e1r\u00e1hoz. Minden 2561024 lehet\u0151s\u00e9g ellen\u0151rz\u00e9se ut\u00e1n, b\u00e1rmennyi id\u0151t is vesz ig\u00e9nybe, a program keresi a legkisebb sz\u00e1mot, amely hi\u00e1nyzik a sz\u00f3t\u00e1rb\u00f3l, \u00e9s ezt a sz\u00e1mot ki\u00edrja. Nyilv\u00e1nval\u00f3nak t\u0171nik, hogy egy ilyen program belef\u00e9r a kilob\u00e1jtnyi k\u00f3dba \u2014 \u00e9s ki\u00edrja azt a sz\u00e1mot, amelyet nem lehet ki\u00edrni kilob\u00e1jt program seg\u00edts\u00e9g\u00e9vel!<\/p>\n

De hol a csapda? A jel\u00f6l\u00e9sek inform\u00e1liss\u00e1ga m\u00e1r nem \u00edrhat\u00f3 r\u00e1!<\/p>\n

Ha az zavarja, hogy a programunk \u00f3ri\u00e1si mennyis\u00e9g\u0171 mem\u00f3ri\u00e1t ig\u00e9nyel a m\u0171k\u00f6d\u00e9s\u00e9hez \u2014 egy 2561024 elem\u0171 sz\u00f3t\u00e1r (vagy bitminta) \u2014 akkor mindezt meg lehet val\u00f3s\u00edtani n\u00e9lk\u00fcle is: minden 2561024 sz\u00e1mot egyenk\u00e9nt sorra kell venni, \u00e9s kipr\u00f3b\u00e1lni az \u00f6sszes 2561024 lehets\u00e9ges programot, am\u00edg meg nem tal\u00e1ljuk a megfelel\u0151t. Nem sz\u00e1m\u00edt, hogy ez a fajta keres\u00e9s milyen hossz\u00fa ideig tart: a sz\u00e1m \u00e9s a program p\u00e1rok kevesebb mint (2561024)2 ellen\u0151rz\u00e9se ut\u00e1n a program befejez\u0151dik, \u00e9s megtal\u00e1lja azt az \u00e1h\u00edtott sz\u00e1mot.<\/p>\n

Vagy m\u00e9gsem? Hiszen a kipr\u00f3b\u00e1lt programok k\u00f6z\u00f6tt ott lesz while True: pass<\/code> (\u00e9s funkcion\u00e1lis anal\u00f3gjai) \u2014 \u00e9s a program ellen\u0151rz\u00e9s\u00e9nek tov\u00e1bbi r\u00e9sze m\u00e1r nem folytat\u00f3dik!<\/p>\n

A Berry-paradoxonhoz k\u00e9pest, ahol a csapda a jel\u00f6l\u00e9sek inform\u00e1liss\u00e1g\u00e1ban rejlett, a m\u00e1sodik esetben j\u00f3l \u00e1lc\u00e1zott \u00e1tkonstru\u00e1l\u00e1sa van a a \"meg\u00e1ll\u00e1si probl\u00e9ma\"-nak.<\/a><\/noindex>A l\u00e9nyeg az, hogy egy program kimenet\u00e9t korl\u00e1tozott id\u0151 alatt nem lehet meghat\u00e1rozni. K\u00fcl\u00f6n\u00f6sen a Kolmogorov-komplexit\u00e1s nem sz\u00e1m\u00edthat\u00f3 ki.<\/a><\/noindex>: nincs olyan algoritmus, amely lehet\u0151v\u00e9 tenn\u00e9, hogy egy adott sz\u00e1mhoz megtal\u00e1ljuk a legk\u00f6zelebbi program hossza, ami ezt a sz\u00e1mot produk\u00e1lja; ez\u00e9rt a Berry-probl\u00e9ma megold\u00e1sa is lehetetlen \u2014 egy adott sz\u00e1mhoz tal\u00e1ljuk meg a legr\u00f6videbb sz\u00f3belileg kifejezett hosszot.
\n
Forr\u00e1s: 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\udd47Adatkompresszi\u00f3val kapcsolatos paradoxonok | ProHoster","description":"Az adatkompresszi\u00f3 probl\u00e9m\u00e1ja legegyszer\u0171bb form\u00e1j\u00e1ban.","canonical_url":"https:\/\/prohoster.info\/hu\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"hu_HU","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\/hu\/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\/hu\/wp-json\/wp\/v2\/posts\/31157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/comments?post=31157"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/posts\/31157\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/media\/23125"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/media?parent=31157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/categories?post=31157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/tags?post=31157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}