{"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\/fr\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","title":{"rendered":"Paradoxes sur la compression des donn\u00e9es","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Paradoxes La t\u00e2che de compression des donn\u00e9es, dans sa forme la plus simple, peut se r\u00e9f\u00e9rer aux nombres et \u00e0 leurs d\u00e9signations. Les nombres peuvent \u00eatre d\u00e9sign\u00e9s par des num\u00e9raux (\u00abonze\u00bb<\/i> pour le nombre 11), par des expressions math\u00e9matiques (\u00abdeux \u00e0 la vingti\u00e8me\u00bb<\/i> pour 1048576), par des expressions textuelles (\u00abcinq nines\u00bb<\/i> pour 99999), par des noms propres (\u00able nombre de la b\u00eate\u00bb<\/i> pour 666, \u00abl'ann\u00e9e de la mort de Turing\u00bb<\/i> pour 1954), ou par des combinaisons arbitraires de ceux-ci. Toute d\u00e9signation qui permet \u00e0 l'interlocuteur d'identifier sans ambigu\u00eft\u00e9 de quel nombre il s'agit est valable. Il est \u00e9vident qu'il est plus efficace de dire \u00e0 l'interlocuteur \u00able facteuriel de huit\u00bb<\/i> que la d\u00e9signation \u00e9quivalente \u00abquarante mille trois cent vingt\u00bb<\/i>. La question qui se pose ici est : quelle d\u00e9signation pour un nombre donn\u00e9 est la plus courte ?<\/p>\n

Le philosophe Bertrand Russell a publi\u00e9 en 1908 le \u00abparadoxe de Berry\u00bb<\/a><\/noindex>, qui aborde la question des d\u00e9signations des nombres sous un angle oppos\u00e9 : quel est le plus petit nombre pour lequel il n\u2019est pas suffisant d\u2019utiliser quatre-vingts lettres ?<\/b>
\nUn tel nombre doit exister : avec quatre-vingts lettres russes et espaces, on peut composer seulement 3480 d\u00e9signations, donc, avec l'utilisation de quatre-vingts lettres, il est impossible de d\u00e9signer plus de 3480 nombres. Ainsi, un nombre ne pouvant pas \u00eatre d\u00e9sign\u00e9 de cette fa\u00e7on ne d\u00e9passera pas 3480.<\/p>\n

Donc, ce nombre sera d\u00e9sign\u00e9 par \u00able plus petit nombre pour lequel il n\u2019est pas suffisant d\u2019utiliser quatre-vingts lettres\u00bb<\/i>, qui contient seulement 78 lettres ! D'une part, ce nombre doit exister ; d'autre part, si ce nombre existe, alors sa d\u00e9signation ne lui correspond pas. Un paradoxe !<\/a><\/noindex><\/p>\n

La fa\u00e7on la plus simple de balayer ce paradoxe est de faire r\u00e9f\u00e9rence \u00e0 l'informalit\u00e9 des d\u00e9signations verbales. On pourrait dire que si seules un ensemble sp\u00e9cifiquement d\u00e9fini d'expressions \u00e9tait autoris\u00e9 alors \u00able plus petit nombre pour lequel il n\u2019est pas suffisant d\u2019utiliser quatre-vingts lettres\u00bb<\/i> cela ne constituerait pas une d\u00e9signation valide, tandis que des d\u00e9signations pratiquement utiles comme \u00able facteuriel de huit\u00bb<\/i> resteraient valides.<\/p>\n

Existe-t-il des moyens formels pour d\u00e9crire la s\u00e9quence (algorithme) d'actions sur les nombres ? Oui, et en abondance \u2014 on les appelle des langages de programmation. Utilisons des programmes au lieu de d\u00e9signations verbales (par exemple, en Python), pour afficher les nombres n\u00e9cessaires. Par exemple, pour cinq nines, le programme suivant convient : print(\"9\"*5)<\/code>. Nous allons continuer \u00e0 nous int\u00e9resser \u00e0 la plus courte programme pour un nombre donn\u00e9. On appelle la longueur d'un tel programme la complexit\u00e9 de Kolmogorov<\/a><\/noindex> .; c'est la limite th\u00e9orique \u00e0 laquelle un nombre donn\u00e9 peut \u00eatre compress\u00e9.<\/p>\n

Au lieu du paradoxe de Berry, on peut maintenant envisager un analogue : quel est le plus petit nombre pour lequel un programme de moins d'un kilo-octet n'est pas suffisant ?<\/b><\/p>\n

Nous allons raisonner de la m\u00eame mani\u00e8re qu'auparavant : il existe 2561024 textes d'un kilo-octet, donc, avec des programmes d'un kilo-octet, on peut produire au maximum 2561024 nombres. Il existe donc un certain nombre, qui ne d\u00e9passe pas 2561024, qui ne peut pas \u00eatre produit de cette mani\u00e8re.<\/p>\n

Mais \u00e9crivons un programme en Python qui g\u00e9n\u00e8re tous les textes d'un kilo-octet possibles, les ex\u00e9cute, et si l'un d'eux produit un nombre, ajoute ce nombre \u00e0 un dictionnaire d'atteignabilit\u00e9. Apr\u00e8s avoir v\u00e9rifi\u00e9 toutes les 2561024 possibilit\u00e9s, peu importe le temps que cela prendra \u2014 le programme cherche quel est le plus petit nombre absent du dictionnaire et l'affiche. Il semble \u00e9vident qu'un tel programme tiendra dans un kilo-octet de code \u2014 et affichera ce nombre qui est impossible \u00e0 produire avec un programme d'un kilo-octet !<\/p>\n

Quel est donc le pi\u00e8ge maintenant ? Avec une telle formalisation, on ne peut plus passer \u00e0 la l\u00e9g\u00e8re sur les notations !<\/p>\n

Si vous \u00eates d\u00e9rang\u00e9 par le fait que notre programme n\u00e9cessitera une quantit\u00e9 astronomique de m\u00e9moire pour fonctionner \u2014 un dictionnaire (ou un tableau de bits) de 2561024 \u00e9l\u00e9ments \u2014 on peut faire tout cela sans lui : parcourir chacun des 2561024 nombres un par un en testant tous les 2561024 programmes possibles jusqu'\u00e0 ce que l'on trouve le bon. Peu importe que ce processus prenne beaucoup de temps : apr\u00e8s avoir v\u00e9rifi\u00e9 moins de (2561024)2 paires du nombre et du programme, il doit se terminer et trouver ce nombre tant convoit\u00e9.<\/p>\n

Ou ne se terminera-t-il pas ? Car parmi tous les programmes qui seront test\u00e9s, on rencontrera while True: pass<\/code> et ses analogues fonctionnels \u2014 et ensuite, la v\u00e9rification d'un tel programme n'avancera plus !<\/p>\n

Contrairement au paradoxe de Berry, o\u00f9 le pi\u00e8ge r\u00e9sidait dans la non-formalisation des notations, dans le second cas, nous avons une reformulation bien masqu\u00e9e \"du probl\u00e8me de l'arr\u00eat\"<\/a><\/noindex>. En effet, il est impossible de d\u00e9terminer la sortie d'un programme dans un temps fini. En particulier, la complexit\u00e9 de Kolmogorov est non calculable.<\/a><\/noindex>: il n'existe aucun algorithme permettant de trouver, pour un nombre donn\u00e9, la longueur du programme le plus court affichant ce nombre ; par cons\u00e9quent, il n'y a pas de solution non plus pour le probl\u00e8me de Berry \u2014 trouver, pour un nombre donn\u00e9, la longueur de la repr\u00e9sentation verbale la plus courte.
\n
Source : 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\udd47Paradoxes sur la compression des donn\u00e9es | ProHoster","description":"Le probl\u00e8me de la compression des donn\u00e9es, dans sa forme la plus simple, peut \u00eatre li\u00e9 \u00e0.","canonical_url":"https:\/\/prohoster.info\/fr\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"fr_FR","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\/fr\/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\/fr\/wp-json\/wp\/v2\/posts\/31157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/comments?post=31157"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/posts\/31157\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/media\/23125"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/media?parent=31157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/categories?post=31157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/tags?post=31157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}