{"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\/da\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","title":{"rendered":"Paradoxer om datakomprimering","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Paradoxer Opgaven til komprimering af data i sin enkleste form kan relateres til tal og deres repr\u00e6sentationer. Tal kan repr\u00e6senteres med numeriske betegnelser (\"elleve\"<\/i> for tallet 11), matematiske udtryk (\"to til den tyvende\"<\/i> for 1048576), strengudtryk (\"fem niere\"<\/i> for 99999), egennavne (\"dyrets tal\"<\/i> for 666, \"\u00e5ret for Turing's d\u00f8d\"<\/i> for 1954), eller en vilk\u00e5rlig kombination af dem. Enhver betegnelse, der g\u00f8r det muligt for samtalepartneren entydigt at bestemme, hvilket tal der menes, er anvendelig. Det er \u00e5benlyst, at det er mere effektivt at informere samtalepartneren om \"faktorialen af otte\"<\/i> end den tilsvarende betegnelse \"fyrre tusinde treogtyve\"<\/i>. Her opst\u00e5r et logisk sp\u00f8rgsm\u00e5l: hvilken betegnelse for et givet tal er den korteste?<\/p>\n

Filosof Bertrand Russell offentliggjorde i 1908 \"Berry's paradoks\"<\/a><\/noindex>, som ber\u00f8rer sp\u00f8rgsm\u00e5let om betegnelser for tal fra den modsatte vinkel: hvad er det mindste tal, som ikke kan betegnes med f\u00e6rre end firs bogstaver?<\/b>
\nEt s\u00e5dant tal m\u00e5 eksistere: Af firs russiske bogstaver og mellemrum kan der kun dannes 3480 betegnelser, s\u00e5 med brug af firs bogstaver kan man maksimalt betegne 3480 tal. Dette betyder, at et tal, der er mindre eller lig med 3480, ikke kan betegnes p\u00e5 denne m\u00e5de.<\/p>\n

Det betyder, at dette tal vil blive repr\u00e6senteret med betegnelsen \"det mindste tal, som ikke kan betegnes med f\u00e6rre end firs bogstaver\"<\/i>, som har i alt 78 bogstaver! P\u00e5 den ene side m\u00e5 dette tal eksistere; p\u00e5 den anden side, hvis dette tal eksisterer, s\u00e5 stemmer dets betegnelse ikke overens med det. Et paradoks!<\/a><\/noindex><\/p>\n

Den enkleste m\u00e5de at feje dette paradoks v\u00e6k p\u00e5 er at henvise til uformelle verbale betegnelser. Man kan sige, at hvis der kun blev tilladt et specifikt s\u00e6t udtryk i betegnelse, s\u00e5 \"det mindste tal, som ikke kan betegnes med f\u00e6rre end firs bogstaver\"<\/i> ikke ville v\u00e6re en gyldig betegnelse, mens praktisk nyttige betegnelser som \"faktorialen af otte\"<\/i> ville forblive gyldige.<\/p>\n

Er der formelle m\u00e5der at beskrive sekvenser (algoritmer) af handlinger med tal? Ja, og der er rigeligt \u2014 de kaldes programmeringssprog. Lad os i stedet for verbale betegnelser bruge programmer (f.eks. i Python), der udskriver de \u00f8nskede tal. For eksempel vil programmet print(\"9\"*5)<\/code>. Vi vil stadig v\u00e6re interesseret i det korteste program for et givet tal. L\u00e6ngden af et s\u00e5dant program kaldes Kolmogorov-kompleksitet<\/a><\/noindex> af tallet; det er den teoretiske gr\u00e6nse, hvortil et givet tal kan komprimeres.<\/p>\n

I stedet for Berrys paradoks kan vi nu overveje et lignende: hvad er det mindste tal, som ikke kan udskrives af et kilobyte-program?<\/b><\/p>\n

Vi vil r\u00e6sonnere p\u00e5 samme m\u00e5de som f\u00f8r: der findes 2561024 kilobyte-tekster, hvilket betyder, at ikke mere end 2561024 tal kan genereres med kilobyte-programmer. Dermed er der et tal, som ikke kan genereres p\u00e5 denne m\u00e5de, og som ikke er st\u00f8rre end 2561024.<\/p>\n

Men lad os skrive et Python-program, der genererer alle mulige kilobyte-tekster, k\u00f8rer dem og, hvis de udskriver et tal, s\u00e5 tilf\u00f8jer det tal til en opn\u00e5elig ordbog. Efter at have kontrolleret alle 2561024 muligheder, hvor lang tid det end m\u00e5tte tage, vil programmet finde det mindste tal, der er frav\u00e6rende i ordbogen, og udskrive dette tal. Det virker indlysende, at et s\u00e5dant program vil holde sig inden for en kilobyte kode \u2014 og vil udskrive det tal, som ikke kan udskrives af et kilobyte-program!<\/p>\n

Men hvad er f\u00e6lden nu? Det er ikke l\u00e6ngere muligt at afskrive det p\u00e5 grund af uformelle betegnelser!<\/p>\n

Hvis det forvirrer dig, at vores program kr\u00e6ver en astronomisk m\u00e6ngde hukommelse for at k\u00f8re \u2014 en ordbog (eller bit-array) med 2561024 elementer \u2014 s\u00e5 kan alt det samme ogs\u00e5 g\u00f8res uden det: for hvert af de 2561024 tal kan vi se p\u00e5 alle 2561024 mulige programmer \u00e9n ad gangen, indtil vi finder en passende. Det betyder ikke noget, at en s\u00e5dan gennemgang vil tage meget lang tid: efter mindre end (2561024)2 par af tal og programmer vil det jo ende, og finde det eftertragtede tal.<\/p>\n

Eller vil det ikke ende? For blandt alle de programmer, der vil blive afpr\u00f8vet, vil vi st\u00f8de p\u00e5 while True: pass<\/code> (og dens funktionelle \u00e6kvivalenter) \u2014 og derefter vil kontrol af et s\u00e5dant program ikke kunne forts\u00e6tte!<\/p>\n

I mods\u00e6tning til Berrys paradoks, hvor f\u00e6lden var i de uformelle betegnelser, har vi i dette tilf\u00e6lde en godt camoufleret omformulering af \u00abstop-problemet\u00bb<\/a><\/noindex>. Det er umuligt at bestemme udfaldet af programmet inden for en endelig tid. Specifikt er Kolmogorov-kompleksiteten ukendelig<\/a><\/noindex>: der er ingen algoritme, der g\u00f8r det muligt at finde l\u00e6ngden af det korteste program, der udskriver et givet tal; derfor er der heller ikke nogen l\u00f8sning p\u00e5 Berry's problem \u2014 at finde l\u00e6ngden af den korteste verbale betegnelse for et givet tal.
\n
Kilde: 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\udd47Paradokser om datakompression | ProHoster","description":"Data compression problemstillingen i sin enkleste form kan relateres til.","canonical_url":"https:\/\/prohoster.info\/da\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"da_DK","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\/da\/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\/da\/wp-json\/wp\/v2\/posts\/31157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/comments?post=31157"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/posts\/31157\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/media\/23125"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/media?parent=31157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/categories?post=31157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/da\/wp-json\/wp\/v2\/tags?post=31157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}