{"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\/pt\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","title":{"rendered":"Paradoxos sobre compress\u00e3o de dados","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Paradoxos A tarefa de compress\u00e3o de dados em sua forma mais simples pode se referir a n\u00fameros e suas denomina\u00e7\u00f5es. N\u00fameros podem ser representados por numerais (\u00abonze\u00bb<\/i> para o n\u00famero 11), express\u00f5es matem\u00e1ticas (\u00abdois \u00e0 vig\u00e9sima\u00bb<\/i> para 1048576), express\u00f5es de string (\u00abcinco noves\u00bb<\/i> para 99999), nomes pr\u00f3prios (\u00abn\u00famero da besta\u00bb<\/i> para 666, \u00abano da morte de Turing\u00bb<\/i> para 1954), ou combina\u00e7\u00f5es arbitr\u00e1rias delas. Qualquer denomina\u00e7\u00e3o que permita ao interlocutor identificar claramente de qual n\u00famero se trata \u00e9 v\u00e1lida. \u00c9 evidente que comunicar ao interlocutor \u00abfatorial de oito\u00bb<\/i> \u00e9 mais eficaz do que a denomina\u00e7\u00e3o equivalente \u00abquarenta mil trezentos e vinte\u00bb<\/i>. Surge, ent\u00e3o, uma quest\u00e3o l\u00f3gica: qual \u00e9 a denomina\u00e7\u00e3o mais curta para um determinado n\u00famero?<\/p>\n

O fil\u00f3sofo Bertrand Russell publicou em 1908 o \u00abparadoxo de Berry\u00bb<\/a><\/noindex>, que aborda a quest\u00e3o das denomina\u00e7\u00f5es de n\u00fameros sob outra perspectiva: qual \u00e9 o menor n\u00famero para o qual n\u00e3o h\u00e1 denomina\u00e7\u00e3o suficiente utilizando oitenta letras? Esse n\u00famero deve existir: com oitenta letras russas e espa\u00e7os, \u00e9 poss\u00edvel formar apenas 3480 denomina\u00e7\u00f5es, portanto, usando oitenta letras, n\u00e3o \u00e9 poss\u00edvel denominar mais de 3480 n\u00fameros. Assim, existe um n\u00famero que n\u00e3o pode ser representado dessa forma e \u00e9 igual ou inferior a 3480.<\/b>
\nPortanto, para esse n\u00famero ser\u00e1 correspondente a denomina\u00e7\u00e3o<\/p>\n

\u00abo menor n\u00famero para o qual n\u00e3o h\u00e1 denomina\u00e7\u00e3o suficiente utilizando oitenta letras\u00bb , na qual h\u00e1 apenas 78 letras! Por um lado, esse n\u00famero deve existir; por outro, se esse n\u00famero existir, sua representa\u00e7\u00e3o n\u00e3o corresponde a ele. Um paradoxo!<\/i>, onde existem apenas 78 letras! Por um lado, esse n\u00famero deve existir; por outro, se esse n\u00famero existe, sua representa\u00e7\u00e3o n\u00e3o corresponde a ele. Um paradoxo!<\/a><\/noindex><\/p>\n

A maneira mais simples de ignorar esse paradoxo \u00e9 referir-se \u00e0 informalidade das denomina\u00e7\u00f5es verbais. Ora, se apenas um conjunto especificamente definido de express\u00f5es fosse permitido nas denomina\u00e7\u00f5es, ent\u00e3o , na qual h\u00e1 apenas 78 letras! Por um lado, esse n\u00famero deve existir; por outro, se esse n\u00famero existir, sua representa\u00e7\u00e3o n\u00e3o corresponde a ele. Um paradoxo!<\/i> n\u00e3o seria uma denomina\u00e7\u00e3o aceit\u00e1vel, enquanto denomina\u00e7\u00f5es praticamente \u00fateis, como \u00abfatorial de oito\u00bb<\/i> permaneceriam aceit\u00e1veis.<\/p>\n

Existem maneiras formais de descrever a sequ\u00eancia (algoritmo) de a\u00e7\u00f5es sobre n\u00fameros? Existem, e em abund\u00e2ncia \u2014 elas s\u00e3o chamadas de linguagens de programa\u00e7\u00e3o. Vamos usar programas (por exemplo, em Python) em vez de denomina\u00e7\u00f5es verbais para gerar os n\u00fameros desejados. Por exemplo, para cinco noves, o programa adequado seria print(\"9\"*5)<\/code>. Continuaremos a nos interessar pelo programa mais curto para um n\u00famero dado. O comprimento de tal programa \u00e9 chamado de complexidade de Kolmogorov<\/a><\/noindex> do n\u00famero; esse \u00e9 o limite te\u00f3rico at\u00e9 onde um n\u00famero dado pode ser comprimido.<\/p>\n

Em vez do paradoxo de Berry, agora podemos considerar um an\u00e1logo: qual \u00e9 o menor n\u00famero para o qual n\u00e3o \u00e9 suficiente um programa de um kilobyte para ser gerado?<\/b><\/p>\n

Vamos raciocinar da mesma forma que antes: existem 2561024 textos de um kilobyte, portanto, programas de um kilobyte podem gerar no m\u00e1ximo 2561024 n\u00fameros. Assim, algum n\u00famero, n\u00e3o maior que 2561024, n\u00e3o pode ser gerado por esse m\u00e9todo.<\/p>\n

Mas vamos escrever um programa em Python que gera todos os textos poss\u00edveis de um kilobyte, os executa e, se eles geram algum n\u00famero \u2014 adiciona esse n\u00famero ao dicion\u00e1rio de alcan\u00e7\u00e1veis. Depois de verificar todas as 2561024 possibilidades, quanto tempo isso levar, o programa busca qual \u00e9 o menor n\u00famero ausente no dicion\u00e1rio e o exibe. Parece evidente que tal programa se encaixaria em um kilobyte de c\u00f3digo \u2014 e geraria aquele n\u00famero que n\u00e3o pode ser gerado por um programa de um kilobyte!<\/p>\n

Qual \u00e9, ent\u00e3o, a pegadinha agora? N\u00e3o pode mais ser atribu\u00eddo \u00e0 informalidade das denomina\u00e7\u00f5es!<\/p>\n

Se voc\u00ea est\u00e1 preocupado que nosso programa exigir\u00e1 uma quantidade astron\u00f4mica de mem\u00f3ria para funcionar \u2014 um dicion\u00e1rio (ou array de bits) com 2561024 elementos \u2014 tudo isso pode ser feito sem ele: para cada um dos 2561024 n\u00fameros, devemos testar todas as 2561024 poss\u00edveis programas, at\u00e9 encontrar o certo. N\u00e3o importa que essa busca dure muito tempo: depois de testar menos de (2561024)2 pares de n\u00famero e programa, ela terminar\u00e1, encontrando aquele n\u00famero t\u00e3o desejado.<\/p>\n

Ou n\u00e3o ir\u00e1 terminar? Afinal, entre todos os programas que ser\u00e3o testados, aparecer\u00e1 while True: pass<\/code> e seus equivalentes funcionais \u2014 e ent\u00e3o as verifica\u00e7\u00f5es desse programa n\u00e3o ir\u00e3o mais adiante!<\/p>\n

Diferente do paradoxo de Berry, onde o truque estava na informalidade das denomina\u00e7\u00f5es, neste segundo caso temos uma reformula\u00e7\u00e3o bem disfar\u00e7ada do \"problema da parada\"<\/a><\/noindex>. A quest\u00e3o \u00e9 que n\u00e3o \u00e9 poss\u00edvel determinar a sa\u00edda de um programa em tempo finito. Em particular, a complexidade de Kolmogorov \u00e9 incomput\u00e1vel<\/a><\/noindex>: n\u00e3o existe nenhum algoritmo que permita, para um dado n\u00famero, encontrar o comprimento do programa mais curto que gera esse n\u00famero; portanto, n\u00e3o h\u00e1 solu\u00e7\u00e3o para o problema de Berry \u2014 encontrar o comprimento da representa\u00e7\u00e3o verbal mais curta para um n\u00famero dado.
\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\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\udd47Paradoxos sobre compress\u00e3o de dados | ProHoster","description":"A tarefa de compress\u00e3o de dados, em sua forma mais simples, pode ser relacionada a.","canonical_url":"https:\/\/prohoster.info\/pt\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"pt_PT","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\/pt\/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\/pt\/wp-json\/wp\/v2\/posts\/31157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/comments?post=31157"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/posts\/31157\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/media\/23125"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/media?parent=31157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/categories?post=31157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/tags?post=31157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}