{"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\/lv\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","title":{"rendered":"Datu saspie\u0161anas paradoksi","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Datu Datu saspie\u0161anas uzdevums sav\u0101 visvienk\u0101r\u0161\u0101kaj\u0101 form\u0101 var attiekties uz skait\u013ciem un to apz\u012bm\u0113jumiem. Skait\u013cus var apz\u012bm\u0113t ar cipariem (\u201evienspadsmit\u201d<\/i> numuram 11), matem\u0101tisk\u0101m izteiksm\u0113m (\u201edivi divdesmitaj\u0101\u201d<\/i> numuram 1048576), virknes izteiksm\u0113m (\u201epiecas dev\u012btniekus\u201d<\/i> numuram 99999), \u012bpa\u0161v\u0101rdiem (\u201ebeasts skaits\u201d<\/i> numuram 666, \u201eTj\u016bringa n\u0101ves gads\u201d<\/i> numuram 1954), vai ar nejau\u0161u to kombin\u0101ciju. Der jebk\u0101ds apz\u012bm\u0113jums, ar kuru sarunbiedrs var viennoz\u012bm\u012bgi noteikt, par kuru skaitli ir runa. Ac\u012bmredzami, ka sazin\u0101ties ar sarunbiedru par \u201easto\u0146u faktori\u0101lu\u201d<\/i> efekt\u012bv\u0101k nek\u0101 ar ekvivalentu apz\u012bm\u0113jumu \u201e\u010detrdesmit t\u016bksto\u0161i tr\u012bsdesmit\u201d<\/i>. \u0160eit rodas lo\u0123isks jaut\u0101jums: k\u0101ds apz\u012bm\u0113jums dotajam skaitlim ir \u012bs\u0101kais?<\/p>\n

Filozofs Bertrands Rasels 1908. gad\u0101 public\u0113ja \u201eBerija paradoksu\u201d<\/a><\/noindex>, kur\u0101 tiek apspriests apz\u012bm\u0113jumu jaut\u0101jums no pret\u0113j\u0101s puses: k\u0101ds ir viss maz\u0101kais skaitlis, kam apz\u012bm\u0113\u0161anai nepietiek ar asto\u0146desmit burtiem?<\/b>
\n\u0160\u0101dam skaitlim ir j\u0101n\u0101k eksist\u0113t: no asto\u0146desmit krievu burtiem un atstarp\u0113m var izveidot tikai 3480 apz\u012bm\u0113jumus, l\u012bdz ar to, izmantojot asto\u0146desmit burtus, nav iesp\u0113jams apz\u012bm\u0113t vair\u0101k par 3480 skait\u013ciem. T\u0101tad skaitli, kas ir ne liel\u0101ks par 3480, apz\u012bm\u0113t \u0161\u0101d\u0101 veid\u0101 nav iesp\u0113jams.<\/p>\n

T\u0101d\u0113j\u0101di \u0161im skaitlim atbilst apz\u012bm\u0113jums \u201eviss maz\u0101kais skaitlis, kam apz\u012bm\u0113\u0161anai nepietiek ar asto\u0146desmit burtiem\u201d<\/i>, kur\u0101 ir tikai 78 burti! No vienas puses, \u0161im skaitlim ir j\u0101past\u0101v; no otras puses, ja \u0161is skaitlis past\u0101v, tad t\u0101 apz\u012bm\u0113jums tam neatbilst. Paradoks!<\/a><\/noindex><\/p>\n

Vienk\u0101r\u0161\u0101kais veids, k\u0101 atrauties no \u0161\u012b paradoksa, ir atsaukties uz neform\u0101lu v\u0101rdiski izteikumiem. Sakot, ja apz\u012bm\u0113jumos b\u016btu pie\u013caujams tikai konkr\u0113ti noteikts izteikumu kopums, tad \u201eviss maz\u0101kais skaitlis, kam apz\u012bm\u0113\u0161anai nepietiek ar asto\u0146desmit burtiem\u201d<\/i> nepietiekami apz\u012bm\u0113jums neb\u016btu pie\u013caujams, kam\u0113r praktiski noder\u012bgi apz\u012bm\u0113jumi, piem\u0113ram, \u201easto\u0146u faktori\u0101lu\u201d<\/i> paliktu pie\u013caujami.<\/p>\n

Vai ir form\u0101li veidi, k\u0101 aprakst\u012bt sec\u012bbu (algoritmu) darb\u012bbu ar skait\u013ciem? Ir, un to netr\u016bkst \u2014 tos sauc par programm\u0113\u0161anas valod\u0101m. Izmantosim programmas (piem\u0113ram, Python), lai izvad\u012btu nepiecie\u0161amos skait\u013cus. Piem\u0113ram, piec\u0101m dev\u012btniekus der\u0113s programma print(\"9\"*5)<\/code>. M\u0113s joproj\u0101m interes\u0113jamies par \u012bs\u0101ko programmu noteiktam skaitlim. \u0160\u0101das programmas garumu sauc par Kolmogorova sare\u017e\u0123\u012bt\u012bbu<\/a><\/noindex> skait\u013ca; tas ir teor\u0113tiskais limits, l\u012bdz kuram noteikto skaitli var saspiest.<\/p>\n

Aiz Berija paradoksa tagad varam apl\u016bkot l\u012bdz\u012bgu: k\u0101ds ir viss\u012bk\u0101kais skaitlis, kura izvad\u012b\u0161anai nepietiek ar kilobaitiem kodu?<\/b><\/p>\n

M\u0113s dom\u0101sim t\u0101pat k\u0101 iepriek\u0161: ir 2561024 kilobaitu teksti, t\u0101d\u0113\u013c ar kilobaita programm\u0101m var izvad\u012bt ne vair\u0101k k\u0101 2561024 skait\u013cus. T\u0101tad, ir k\u0101ds skaitlis, kuru ne vair\u0101k par 2561024 nevar izvad\u012bt \u0161\u0101d\u0101 veid\u0101.<\/p>\n

Tom\u0113r uzrakst\u012bsim Python programmu, kas \u0123ener\u0113 visus iesp\u0113jamos kilobaitu tekstus, izpilda tos, un, ja tie izvada k\u0101du skaitli \u2014 pievieno \u0161o skaitli sasniedzamo skait\u013cu v\u0101rdn\u012bc\u0101. P\u0113c visu 2561024 iesp\u0113ju p\u0101rbaudes, neatkar\u012bgi no t\u0101, cik ilgi tas pras\u012bs \u2014 programma mekl\u0113, kur\u0161 ir viss\u012bk\u0101kais skaitlis, kas tr\u016bkst v\u0101rdn\u012bc\u0101, un izvada \u0161o skaitli. Izskat\u0101s ac\u012bmredzami, ka \u0161\u0101da programma iek\u013causies kilobait\u0101 kodu \u2014 un izvad\u012bs to pa\u0161u skaitli, kuru nav iesp\u0113jams izvad\u012bt ar kilobaita programmu!<\/p>\n

Kur ir tagad vilt\u012bba? Neform\u0101l\u0101s apz\u012bm\u0113jumi vairs nav attaisnojums!<\/p>\n

Ja j\u016bs mulsina tas, ka m\u016bsu programma pras\u012bs astronomisku atmi\u0146as daudzumu darbam \u2014 v\u0101rdn\u012bca (vai bitu mas\u012bvs) ar 2561024 elementiem \u2014 tad to pa\u0161u var izdar\u012bt ar\u012b bez t\u0101: katram no 2561024 skait\u013ciem sec\u012bgi p\u0101rbaud\u012bt visas 2561024 iesp\u0113jam\u0101s programmas, l\u012bdz atrodam piem\u0113rotu. Nav svar\u012bgi, ka \u0161\u0101da p\u0101rbaude ilgs \u013coti ilgi: p\u0113c maz\u0101k k\u0101 (2561024)2 p\u0101ru skait\u013ca un programmas p\u0101rbaudes, t\u0101 beigsies un atrad\u012bs to pa\u0161u sv\u0113to skaitli.<\/p>\n

Vai ar\u012b nebeigsies? Jo starp vis\u0101m programm\u0101m, kas tiks izm\u0113\u0123in\u0101tas, tiks sastapts while True: pass<\/code> (un t\u0101s funkcion\u0101l\u0101s analo\u0123ijas) \u2014 un t\u0101l\u0101k \u0161\u0101das programmas p\u0101rbaude vairs neies t\u0101l\u0101k!<\/p>\n

At\u0161\u0137ir\u012bb\u0101 no Berija paradoksa, kur vilt\u012bba bija neform\u0101lajos apz\u012bm\u0113jumos, otraj\u0101 gad\u012bjum\u0101 m\u0113s saskaramies ar labi mask\u0113tu p\u0101rformul\u0113jumu \u00abapst\u0101\u0161an\u0101s probl\u0113mu\u00bb<\/a><\/noindex>. Probl\u0113ma ir t\u0101da, ka no programmas nav iesp\u0113jams noteikt t\u0101s izvad\u012bjumu ierobe\u017eot\u0101 laik\u0101. It \u012bpa\u0161i, Kolmogorova sare\u017e\u0123\u012bt\u012bba nav apr\u0113\u0137in\u0101ma.<\/a><\/noindex>: nav nek\u0101ds algoritms, kas \u013cautu noteikt \u012bs\u0101k\u0101s programmas garumu, kas izvada dotu skaitli; t\u0101tad, nav ar\u012b risin\u0101juma Berija uzdevumam \u2014 atrast dotajam skaitlim \u012bs\u0101k\u0101 v\u0101rdisk\u0101 apz\u012bm\u0113juma garumu.
\n
Avots: 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\udd47Datu saspie\u0161anas paradoksi | ProHoster","description":"Datu saspie\u0161anas probl\u0113ma sav\u0101 visvienk\u0101r\u0161\u0101kaj\u0101 form\u0101 var attiekties uz.","canonical_url":"https:\/\/prohoster.info\/lv\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"lv_LV","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\/lv\/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\/lv\/wp-json\/wp\/v2\/posts\/31157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/comments?post=31157"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/posts\/31157\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/media\/23125"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/media?parent=31157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/categories?post=31157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/lv\/wp-json\/wp\/v2\/tags?post=31157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}