{"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\/it\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","title":{"rendered":"Paradossi sulla compressione dei dati","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Paradossi Il compito di comprimere i dati nella sua forma pi\u00f9 semplice pu\u00f2 riguardare i numeri e le loro denominazioni. I numeri possono essere rappresentati con numerali (\u00abundici\u00bb<\/i> per il numero 11), espressioni matematiche (\u00abdue elevato alla ventesima\u00bb<\/i> per 1048576), espressioni testuali (\u00abcinque nove\u00bb<\/i> per 99999), nomi propri (\u00abnumero della bestia\u00bb<\/i> per 666, \u00abanno della morte di Turing\u00bb<\/i> per 1954), o combinazioni arbitrarie di essi. \u00c8 accettabile qualsiasi denominazione che permetta al tuo interlocutore di identificare inequivocabilmente di quale numero si sta parlando. \u00c8 chiaro che comunicare all'interlocutore \u00abfattoriale di otto\u00bb<\/i> \u00e8 pi\u00f9 efficiente che utilizzare la denominazione equivalente \u00abquarantamila trecentoventi\u00bb<\/i>. Qui sorge una domanda logica: qual \u00e8 la denominazione pi\u00f9 breve per un dato numero?<\/p>\n

Il filosofo Bertrand Russell nel 1908 pubblic\u00f2 \u00abil paradosso di Berry\u00bb<\/a><\/noindex>, che tocca la questione delle denominazioni dei numeri da un'altra prospettiva: qual \u00e8 il numero pi\u00f9 piccolo per cui non bastano ottanta lettere per rappresentarlo?<\/b>
\nUn tale numero deve esistere: con ottanta lettere russe e spazi possiamo formare solo 3480 denominazioni, quindi usando ottanta lettere si possono rappresentare al massimo 3480 numeri. Pertanto, non \u00e8 possibile rappresentare un numero che sia superiore a 3480 in questo modo.<\/p>\n

Pertanto, a questo numero corrisponder\u00e0 la denominazione \u00abil numero pi\u00f9 piccolo per cui non bastano ottanta lettere\u00bb<\/i>, che contiene solo 78 lettere! Da un lato, questo numero deve esistere; dall'altro, se questo numero esiste, la sua denominazione non gli corrisponde. Paradossale!<\/a><\/noindex><\/p>\n

Il modo pi\u00f9 semplice per ignorare questo paradosso \u00e8 fare riferimento all'informalit\u00e0 delle denominazioni verbali. Come se, se nelle denominazioni si ammesso solo un insieme di espressioni specificamente definite, allora \u00abil numero pi\u00f9 piccolo per cui non bastano ottanta lettere\u00bb<\/i> non sarebbe una denominazione valida, mentre denominazioni praticamente utili come \u00abfattoriale di otto\u00bb<\/i> resterebbero valide.<\/p>\n

Esistono metodi formali per descrivere la sequenza (algoritmo) di operazioni sui numeri? S\u00ec, e in abbondanza \u2014 li chiamiamo linguaggi di programmazione. Invece delle denominazioni verbali, utilizzeremo i programmi (ad esempio, in Python) per ottenere i numeri necessari. Ad esempio, per cinque nove \u00e8 adatta la seguente programma print(\"9\"*5)<\/code>. Continueremo a interessarci al programma pi\u00f9 breve per un numero dato. La lunghezza di tale programma viene chiamata complessit\u00e0 colmogoroviana<\/a><\/noindex> del numero; questo \u00e8 il limite teorico fino al quale un numero dato pu\u00f2 essere compresso.<\/p>\n

Invece del paradosso di Berry, ora possiamo considerare un analogo: qual \u00e8 il numero pi\u00f9 piccolo per il quale non \u00e8 sufficiente un programma di chilobyte?<\/b><\/p>\n

Ragioneremo come prima: ci sono 2561024 testi di chilobyte, quindi con i programmi di chilobyte si possono generare al massimo 2561024 numeri. Pertanto, un certo numero, non maggiore di 2561024, non pu\u00f2 essere generato in questo modo.<\/p>\n

Ma scriveremo un programma in Python che genera tutti i possibili testi di chilobyte, li esegue e, se producono un certo numero, allora aggiunge questo numero a un dizionario di quelli raggiungibili. Dopo aver verificato tutte le 2561024 possibilit\u00e0, qualunque sia il tempo necessario\u2014il programma cerca qual \u00e8 il numero pi\u00f9 piccolo assente nel dizionario e lo restituisce. Sembra ovvio che tale programma rientrer\u00e0 in un chilobyte di codice e produrr\u00e0 proprio quel numero che non pu\u00f2 essere generato da un programma di chilobyte!<\/p>\n

Qual \u00e8 dunque l'inghippo adesso? Non \u00e8 pi\u00f9 possibile attribuire la non formalit\u00e0 delle notazioni!<\/p>\n

Se ti preoccupa che il nostro programma richieder\u00e0 una quantit\u00e0 astronomica di memoria per funzionare\u2014un dizionario (o un array di bit) di 2561024 elementi\u2014si pu\u00f2 fare esattamente la stessa cosa anche senza di esso: per ciascuno dei 2561024 numeri, esaminare uno dopo l'altro tutti i 2561024 possibili programmi, finch\u00e9 non si trova quello giusto. Non importa che tale ricerca richieder\u00e0 molto tempo: dopo aver verificato meno di (2561024)2 coppie di numero e programma, essa terminer\u00e0 e trover\u00e0 quel prezioso numero.<\/p>\n

O non terminer\u00e0? Infatti, tra tutti i programmi che verranno testati, ci sar\u00e0 while True: pass<\/code> (e i suoi analoghi funzionali)\u2014e da quel momento in poi il controllo di tale programma non andr\u00e0 avanti!<\/p>\n

A differenza del paradosso di Berry, dove l'inghippo era nella non formalit\u00e0 delle notazioni, nel secondo caso abbiamo una riformulazione ben mascherata del \"problema dell'arresto\".<\/a><\/noindex>Il fatto \u00e8 che non \u00e8 possibile determinare il suo output per un programma in un tempo finito. In particolare, la complessit\u00e0 colmogoroviana \u00e8 non calcolabile.<\/a><\/noindex>: non esiste alcun algoritmo che consenta di trovare, per un dato numero, la lunghezza del programma pi\u00f9 corto che produce quel numero; quindi, non esiste soluzione nemmeno per il problema di Berry \u2014 trovare, per un dato numero, la lunghezza della pi\u00f9 breve rappresentazione verbale.
\n
Fonte: 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\udd47Paradossi sulla compressione dei dati | ProHoster","description":"Il problema della compressione dei dati, nella sua forma pi\u00f9 semplice, pu\u00f2 riferirsi a.","canonical_url":"https:\/\/prohoster.info\/it\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"it_IT","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\/it\/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\/it\/wp-json\/wp\/v2\/posts\/31157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/comments?post=31157"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/posts\/31157\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/media\/23125"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/media?parent=31157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/categories?post=31157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/tags?post=31157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}