{"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 problema della compressione dei dati, nella sua forma pi\u00f9 semplice, pu\u00f2 riguardare numeri e le loro rappresentazioni. I numeri possono essere rappresentati con numerali (\"undici\"<\/i> per il numero 11), espressioni matematiche (\"due alla ventesima\"<\/i> per 1048576), espressioni stringa (\"cinque nove\"<\/i> per 99999), nomi propri (\"numero della bestia\"<\/i> per 666, \"anno della morte di Turing\"<\/i> per 1954), o combinazioni arbitrarie di essi. Qualsiasi rappresentazione che consenta all'interlocutore di identificare senza ambiguit\u00e0 di quale numero si parla \u00e8 valida. \u00c8 evidente che comunicare all'interlocutore \"fattoriale di otto\"<\/i> \u00e8 pi\u00f9 efficace rispetto alla rappresentazione equivalente \"quarantamila trecentoventi\"<\/i>. Qui sorge una domanda logica: qual \u00e8 la rappresentazione pi\u00f9 breve per un dato numero?<\/p>\n

Il filosofo Bertrand Russell pubblic\u00f2 nel 1908 \"il paradosso di Berry\"<\/a><\/noindex>, che affronta il problema delle rappresentazioni dei numeri da un'altra prospettiva: qual \u00e8 il numero pi\u00f9 piccolo per il quale non sono sufficienti ottanta lettere?<\/b>
\nUn tale numero deve esistere: con ottanta lettere russe e spazi \u00e8 possibile formare solo 3480 rappresentazioni, quindi utilizzando ottanta lettere \u00e8 possibile rappresentare non pi\u00f9 di 3480 numeri. Pertanto, esiste un certo numero, non superiore a 3480, che non pu\u00f2 essere rappresentato in questo modo.<\/p>\n

Pertanto, a questo numero corrisponder\u00e0 la rappresentazione \"il numero pi\u00f9 piccolo per il quale non sono sufficienti ottanta lettere\"<\/i>, che consiste di sole 78 lettere! Da una parte, questo numero deve esistere; dall'altra, se questo numero esiste, la sua rappresentazione non gli corrisponde. Paradosso!<\/a><\/noindex><\/p>\n

Il modo pi\u00f9 semplice per ignorare questo paradosso \u00e8 richiamare l'informalit\u00e0 delle rappresentazioni verbali. Dunque, se nelle rappresentazioni fosse ammesso solo un insieme specifico di espressioni, allora \"il numero pi\u00f9 piccolo per il quale non sono sufficienti ottanta lettere\"<\/i> non sarebbe una rappresentazione valida, mentre rappresentazioni pratiche come \"fattoriale di otto\"<\/i> rimarebbero valide.<\/p>\n

Esistono metodi formali per descrivere una sequenza (algoritmo) di azioni sui numeri? S\u00ec, e in abbondanza \u2014 si chiamano linguaggi di programmazione. Useremo invece le rappresentazioni testuali programmi (ad esempio, in Python) che producono i numeri desiderati. Ad esempio, per cinque nove si adatta il programma print(\"9\"*5)<\/code>. Continuiamo a cercare il programma pi\u00f9 breve per un dato numero. La lunghezza di tale programma si chiama complessit\u00e0 di Kolmogorov<\/a><\/noindex> del numero; \u00e8 il limite teorico fino a cui un dato numero pu\u00f2 essere compresso.<\/p>\n

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

Razionalizzeremo esattamente come prima: esistono 2561024 testi di un kilobyte, quindi con programmi da un kilobyte si possono generare non pi\u00f9 di 2561024 numeri. Pertanto, esiste un certo numero, non superiore a 2561024, che non pu\u00f2 essere prodotto in questo modo.<\/p>\n

Ma scriviamo un programma in Python che genera tutti i possibili testi di un kilobyte, li esegue e, se producono un certo numero, lo aggiunge a un dizionario di risultati raggiungibili. Dopo aver controllato tutte le 2561024 possibilit\u00e0, indipendentemente dal tempo che ci vorr\u00e0, il programma cerca quale sia il numero pi\u00f9 piccolo assente nel dizionario e lo produce. Sembra ovvio che un tale programma rientrer\u00e0 in un kilobyte di codice \u2014 e produrr\u00e0 quel numero che non \u00e8 possibile generare con un programma di un kilobyte!<\/p>\n

Qual \u00e8, quindi, la trappola ora? Non si pu\u00f2 pi\u00f9 liquidare l'informalit\u00e0 delle rappresentazioni!<\/p>\n

Se vi preoccupa il fatto che il nostro programma richieder\u00e0 una quantit\u00e0 astronomica di memoria per funzionare \u2014 un dizionario (o un array di bit) di 2561024 elementi \u2014 si pu\u00f2 fare tutto ci\u00f2 senza di esso: per ciascuno dei 2561024 numeri provare ogni programma possibile di 2561024, finch\u00e9 non ne si trova uno adatto. Non importa che la ricerca duri molto a lungo: dopo aver confrontato meno di (2561024)2 coppie di un numero e un programma, finir\u00e0 per completarsi, e trover\u00e0 quel numero segreto.<\/p>\n

O non si concluder\u00e0? Dopo tutto, tra tutti i programmi che saranno testati, ci sar\u00e0 anche while True: pass<\/code> (e i suoi analoghi funzionali) \u2014 e la verifica di tale programma non andr\u00e0 avanti!<\/p>\n

A differenza del paradosso di Berry, dove la trappola risiedeva nell'informalit\u00e0 delle rappresentazioni, nel secondo caso abbiamo una riformulazione ben mascherata \"del problema dell'arresto\"<\/a><\/noindex>. Infatti, non \u00e8 possibile determinare l'output di un programma in un tempo finito. In particolare, la complessit\u00e0 di Kolmogorov non \u00e8 calcolabile<\/a><\/noindex>: non esiste alcun algoritmo in grado di determinare, per un dato numero, la lunghezza del programma pi\u00f9 breve che lo produce; pertanto, non esiste soluzione neanche per il problema di Berry \u2014 trovare per un numero dato la lunghezza della rappresentazione verbale pi\u00f9 breve.
\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 compito di comprimere i 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}]}}