{"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\/no\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","title":{"rendered":"Paradoxer om datakomprimering","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"<p><img decoding=\"async\" alt=\"Paradoxer om datakomprimering\" src=\"\/wp-content\/uploads\/2019\/04\/d15fed5cc55334e6bb9bc3bbd7cbf50c.jpeg\" style=\"display:block;margin: 0 auto;\" \/> Oppgave med datakomprimering i sin enkleste form kan referere til tall og deres betegnelser. Tall kan betegnes med numeriske ord (<i>\u00abelleve\u00bb<\/i> for tallet 11), matematiske uttrykk (<i>\u00abto opph\u00f8yd i tjue\u00bb<\/i> for 1048576), strengeuttrykk (<i>\u00abfem niere\u00bb<\/i> for 99999), egennavn (<i>\u00abdyrets tall\u00bb<\/i> for 666, <i>\u00ab\u00e5ret Turing d\u00f8de\u00bb<\/i> for 1954), eller vilk\u00e5rlige kombinasjoner av dem. Enhver betegnelse som samtalepartneren kan entydig identifisere hvilket tall som menes, er gyldig. Det er \u00e5penbart at det er mer effektivt \u00e5 informere samtalepartneren om <i>\u00abfaktoriell \u00e5tte\u00bb<\/i> enn den tilsvarende betegnelsen <i>\u00abf\u00f8rti tusen tre hundre og tyve\u00bb<\/i>. Her oppst\u00e5r det et logisk sp\u00f8rsm\u00e5l: hva er den korteste betegnelsen for et gitt tall?<\/p>\n<p>Filosofen Bertrand Russell publiserte i 1908 <noindex><a rel=\"nofollow\" href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9F%D0%B0%D1%80%D0%B0%D0%B4%D0%BE%D0%BA%D1%81_%D0%91%D0%B5%D1%80%D1%80%D0%B8\">\u00abBerry-paradokset\u00bb<\/a><\/noindex>, som tar opp sp\u00f8rsm\u00e5let om tallbetegnelser fra den motsatte siden: <b>hva er det minste tallet som ikke kan betegnes med \u00e5tti bokstaver?<\/b><br \/>\nEt slikt tall m\u00e5 eksistere: av \u00e5tti russiske bokstaver og mellomrom kan man lage totalt 3480 betegnelser, noe som betyr at man ikke kan betegne mer enn 3480 tall med bruk av \u00e5tti bokstaver. Dermed er det umulig \u00e5 betegne et tall som ikke er st\u00f8rre enn 3480.<\/p>\n<p>Dermed vil dette tallet ha betegnelsen <i>\u00abdet minste tallet som ikke kan betegnes med \u00e5tti bokstaver\u00bb<\/i>, som inneholder bare 78 bokstaver! P\u00e5 den ene siden m\u00e5 dette tallet eksistere; p\u00e5 den andre siden, hvis dette tallet eksisterer, s\u00e5 samsvarer ikke betegnelsen med det. Et paradoks!<noindex><a rel=\"nofollow\" name=\"habracut\"><\/a><\/noindex><\/p>\n<p>Den enkleste m\u00e5ten \u00e5 avfeie dette paradokset p\u00e5, er \u00e5 referere til uformelle verbale betegnelser. Man kan si at hvis bare en spesifikk sett med uttrykk var tillatt i betegnelser, s\u00e5 <i>\u00abdet minste tallet som ikke kan betegnes med \u00e5tti bokstaver\u00bb<\/i> ville det ikke v\u00e6rt en gyldig betegnelse, mens prakiske nyttige betegnelser som <i>\u00abfaktoriell \u00e5tte\u00bb<\/i> ville forbli gyldige.<\/p>\n<p>Finnes det formelle m\u00e5ter \u00e5 beskrive sekvensen (algoritmen) av handlinger p\u00e5 tall? Ja, og i overflod - de kalles programmeringsspr\u00e5k. La oss bruke programmer (for eksempel i Python) i stedet for verbale betegnelser, som kan skrive ut de n\u00f8dvendige tallene. For eksempel, for fem niere, ville programmet <code>print(\"9\"*5)<\/code>. Vi vil fortsatt v\u00e6re interessert i den korteste programmet for et gitt tall. Lengden p\u00e5 et slikt program kalles <noindex><a rel=\"nofollow\" href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9A%D0%BE%D0%BB%D0%BC%D0%BE%D0%B3%D0%BE%D1%80%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C\">Kolmogorov-kompleksitet<\/a><\/noindex> til tallet; dette er det teoretiske grensepunktet for hvor mye et gitt tall kan komprimeres.<\/p>\n<p>I stedet for Berry-paradokset kan vi n\u00e5 vurdere et lignende: <b>hva er det minste tallet som ikke kan skrives ut med et kilobyte-program?<\/b><\/p>\n<p>Vi vil tenke likt som tidligere: det finnes 2561024 kilobyte-tekster, derfor kan kilobyte-programmer skrive ut ikke mer enn 2561024 tall. Det betyr at et visst tall, som ikke overstiger 2561024, ikke kan bli skrevet ut p\u00e5 denne m\u00e5ten.<\/p>\n<p>Men vi skal skrive et Python-program som genererer alle mulige kilobyte-tekster, kj\u00f8rer dem, og hvis de skriver ut et tall, legger det tallet til en oppn\u00e5elig liste. Etter \u00e5 ha sjekket alle 2561024 mulighetene, uansett hvor lang tid det m\u00e5tte ta - programmet leter etter det minste tallet som mangler i listen, og skriver ut dette tallet. Det virker opplagt at et slikt program vil f\u00e5 plass innenfor en kilobyte kode - og det vil skrive ut det tallet som ikke kan skrives ut med et kilobyte-program!<\/p>\n<p>Hva er s\u00e5 fellen n\u00e5? Den kan ikke lenger forklares ved uformelle betegnelser!<\/p>\n<p>Hvis du er bekymret for at programmet v\u00e5rt vil kreve en astronomisk mengde minne for \u00e5 fungere - en ordliste (eller bitarray) av 2561024 elementer - s\u00e5 kan alt det samme gj\u00f8res uten det: for hvert av de 2561024 tallene, pr\u00f8v alle 2561024 mulige programmer en etter en, til en passende program blir funnet. Det er ikke viktig at en slik pr\u00f8ving vil ta veldig lang tid: etter \u00e5 ha sjekket mindre enn (2561024)2 par av et tall og et program vil det avsluttes, og finne det dyrebare tallet.<\/p>\n<p>Eller vil det ikke avsluttes? For blant alle programmene som vil bli pr\u00f8vd, vil vi m\u00f8te <code>while True: pass<\/code> (og dens funksjonelle analoger) - og videre testing av et slikt program vil ikke f\u00f8re noe sted!<\/p>\n<p>I motsetning til Berry-paradokset, hvor fellen l\u00e5 i de uformelle betegnelsene, har vi i dette tilfellet en godt kamuflert omformulering av <noindex><a rel=\"nofollow\" href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D0%BE%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8\">\u00abstoppproblemet\u00bb<\/a><\/noindex>. Saken er at det er umulig \u00e5 fastsl\u00e5 et programs utdata p\u00e5 en endelig tid. Spesielt er Kolmogorov-kompleksitet <noindex><a rel=\"nofollow\" href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F\">uberegnelig<\/a><\/noindex>: det finnes ingen algoritme som gj\u00f8r det mulig \u00e5 finne lengden p\u00e5 det korteste programmet som skriver ut et gitt tall; dermed finnes det heller ingen l\u00f8sning for Berry-problemet \u2014 \u00e5 finne lengden p\u00e5 den korteste verbale betegnelsen for et gitt tall.<br \/>\n<br \/>Kilde: <a content=\"nofollow\" rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/post\/446976\/\">habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"<p>\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 [&hellip;]<\/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<!-- All in One SEO 5.0.5 - aioseo.com -->\n\t<meta name=\"description\" content=\"\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.\" \/>\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Yuri Gagarin\"\/>\n\t<link rel=\"canonical\" href=\"https:\/\/prohoster.info\/no\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh\" \/>\n\t\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.5\" \/>\n\t\t<meta property=\"og:locale\" content=\"nn_NO\" \/>\n\t\t<meta property=\"og:site_name\" content=\"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\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"\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\" \/>\n\t\t<meta property=\"og:description\" content=\"\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.\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/prohoster.info\/no\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh\" \/>\n\t\t<meta property=\"og:image\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:secure_url\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:width\" content=\"350\" \/>\n\t\t<meta property=\"og:image:height\" content=\"350\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2019-10-31T18:39:48+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2019-10-31T18:39:48+00:00\" \/>\n\t\t<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<meta property=\"article:author\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"\ud83e\udd47Paradoxer om datakomprimering | ProHoster","description":"Data komprimeringsoppgaver i sin enkleste form kan relateres til.","canonical_url":"https:\/\/prohoster.info\/no\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"nn_NO","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\/no\/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\/no\/wp-json\/wp\/v2\/posts\/31157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/no\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/no\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/no\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/no\/wp-json\/wp\/v2\/comments?post=31157"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/no\/wp-json\/wp\/v2\/posts\/31157\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/no\/wp-json\/wp\/v2\/media\/23125"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/no\/wp-json\/wp\/v2\/media?parent=31157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/no\/wp-json\/wp\/v2\/categories?post=31157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/no\/wp-json\/wp\/v2\/tags?post=31157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}