Dr. Goulu

Pourquoi … Comment … Combien ?

Tri réversible ?

Bubble Sort

En informatique, le tri est une opération incontournable car il est beaucoup plus rapide de rechercher une information dans une liste triée que dans un fouillis. C’est pourquoi j’ai longtemps cru qu’une liste triée contenait plus d’information qu’une liste non triée, car je voyais le tri comme un pré-traitement permettant d’accélérer les opérations suivantes, donc un « plus » par rapport à une situation « moins » performante.

Pris d’un doute il y a quelques années, j’avais posé la question sur un forum consacré à l’informatique théorique :

« est-ce qu’une liste triée contient vraiment plus d’information qu’une liste non triée ?”

Un érudit professeur m’avait répondu simplement ceci :

« ce contient d’ est- information liste liste? non plus qu’ qu’ triée triée une une vraiment ».

J’ai mis un moment à comprendre la profondeur de cette réponse : ma question, une fois les mots triés par ordre alphabétique, était devenue incompréhensible, et contenait donc moins d’information que la phrase originale ! Depuis je sais que l’informatique détruit toujours l’information.

Ce petit concours a reposé la question sous un angle intéressant : est-il possible de programmer un algorithme de tri « réversible », permettant de remettre une liste triée dans son état initial ? Évidemment oui : il suffit de stocker en plus l’information perdue lors du tri, le plus simple étant de mémoriser l’état initial de la liste par exemple en ajoutant à chaque élément trié son numéro d’ordre :

« ce2 contient7 d’10 est-1 information11 liste5 liste14 non15 plus9 qu’3 qu’12 triée6 triée?16 une4 une13 vraiment8 ”.

Pour une liste contenant n éléments, on a besoin de log(n) bits* pour stocker chaque numéro, donc de n.log(n) bits au total.

Peut-on faire mieux? On pourrait se dire que beaucoup d’algorithmes de tri comme QuickSort permutent des éléments après les avoir comparés, et qu’il suffirait donc de stocker le résultat des comparaisons effectuées, soit un bit par test, pour pouvoir ensuite « défaire le tri » en parcourant la liste des bits à l’envers. Combien faut-ils de bits ? ben … au moins n.log(n) aussi puisque c’est justement le nombre de comparaisons qui détermine la « complexité » des algorithmes de tri, et que les bons algorithmes ont une complexité de n.log(n).

Rien ne sert de se casser la tête sur « algorithme de tri réversible », il ne peut pas être plus efficace que de simplement stocker l’ordre initial des données. Etonnant non ?

Le problème, c’est que la donnée du concours spécifie qu’on n’a le droit de stocker que 50% d’information supplémentaire par rapport à la taille des données : si on trie 4K octets, on n’a droit qu’à 2K de données supplémentaires. Or en fonction de ce qui précède on a besoin de 4096*log(4096) bits, soit 6K, plus que les données! En passant, ça signifie qu’en triant beaucoup de petites données, on peut perdre plus de la moitié de l’information contenu dans la liste initiale !

Bref, personne n’a gagné le petit concours parce que ce n’était tout simplement pas possible.,

Note* : en informatique, log(n) dénote évidemment le logarithme binaire ou base 2

30 janvier 2010 Posté par Dr. Goulu | Informatique, Théorique | | 9 commentaires

Echelle interactive de l’Univers

Bad Astronomy indique une très jolie réalisation graphique en Flash permettant de zoomer dans les ordres de grandeur de l’Univers, sur le modèle des impérissables « puissances de dix« , mais en interactif :

cliquez sur l'image pour la version interactive

Il y a décidément encore un trou de plusieurs ordres de grandeur entre le « diamètre » du neutrino et la longueur de Planck

30 janvier 2010 Posté par Dr. Goulu | Graphisme, Informatique, Science | | 2 commentaires

Un vent de haute technologie

Quand on s’intéresse à plein de choses, il arrive parfois qu’apparaisse soudain une nouvelle qui  relie miraculeusement des sujets très différents. C’est ce qui est m’est arrivé en lisant cet article de Thierry Seray.

$250'000 et 8kg pour du vent

Malgré de regrettables rebondissements judiciaires sans fin, la Coupe de l’America qui va se disputer prochainement à Valencia reste la « formule 1″ de la voile, où des budgets énormes permettent le développement de technologies de pointe. A ce titre, l’appareil que BMW Oracle prévoit embarquer* est proprement stupéfiant : le « Racer’s Edge » de la startup Catch The Wind Inc. permet de mesurer la vitesse et la direction du vent jusqu’à 1000 m de distance ! La précision annoncée (2° en direction et 0.5 nœuds en vitesse) donnerait un net avantage stratégique à Oracle. On peut donc s’attendre à ce qu’Alinghi tente par tout les moyens (légaux*…) d’empêcher son utilisation en course.

Reste que la technologie existe, et vise aussi d’autres applications. Catch The Wind Inc. propose le « Vindicator » pour le marché des éoliennes : en mesurant la vitesse du vent 300m avant l’hélice, il permet d’anticiper ses variations, et d’agir sur l’incidence des pales pour extraire plus d’énergie des rafales ou éviter un ralentissement de l’hélice dans une dévente et ainsi rapprocher le rendement de la limite de Betz.

Ces appareils sont basés sur la « vélocimétrie laser« , une technologie combinant LIDAR et effet Doppler. La mesure de vitesse se fait avec un interféromètre semblable à ceux utilisés pour la détection des exoplanètes par la méthode des vitesses radiales.

Ce genre d’engins tenait dans une camionnette il y a 20 ans, maintenant ils sont « portables », peut-être remplaceront-ils bientôt tous ces petits anémomètres qu’on voit tourner partout avant de finir intégrés dans nos téléphones iFaitTout.

Note* : parce que bon, on pourrait aussi imaginer envoyer un rayonnement bien pensé vers l’appareil pour le brouiller…

Références

  1. « Vélocimétrie laser » sur Wikipedia
  2. Closer look at Racer’s Edge, BMW Oracle’s cutting edge wind measurement device sur Valencia Sailing
  3. Philip L. Rogers, Kerry J.Vahala,  « Laser doppler velocimeter » United States Patent Nr 20080170235, 2008

27 janvier 2010 Posté par Dr. Goulu | Energie, Optique, Voile | , | 3 commentaires

Histoire d’angles

Combien d’unités de mesure des angles connaissez vous ? Il y a le degré, bien sur, le radian probablement, peut-être le grade, mais encore ?

"Angles, lines, light, and shadows" par Kefindooley sur flickr

Diviser un tour en 360 degrés est une excellente idée qu’a eu un illustre Babylonien anonyme il y a environ 4000 ans. Pourquoi 360 ? D’abord, 360 est un nombre hautement composé donc facile à diviser, et les Babyloniens comptaient en base 60. D’ailleurs ils divisèrent le degré en 60 minutes, et la minute en 60 secondes d’arc, et mêmes en tierces et quartes. Aussi probablement parce que 1° est un petit angle, mais un angle encore facilement mesurable à l’oeil: le diamètre angulaire de la Lune et du Soleil sont proches de 0.5°. Hipparque de Nicée trouva ces unités tellement pratiques et les publia si bien que le degré, la minute et la seconde sont aujourd’hui toujours les unités d’angle les plus utilisées. Il me semble bien que ce doit être la plus ancienne unité de mesure encore en usage, et de très loin.

Le radian a probablement été découvert le jour où l’illustre inventeur oublié de la roue a mesuré son rayon avec une ficelle et enroulé la ficelle sur le périmètre de son oeuvre. Il y ensuite été implicitement utilisé par tous les géomètres de l’Histoire, mais  mais ce n’est qu’en 1873 qu’un dénommé James Thomson imprima le mot « radian » sur des questions d’examen à ses étudiants 1,2. Le radian est une unité purement géométrique, directement liée à pi et indépendante de toute convention humaine. C’est pourquoi l’article de la Wikipedia sur le radian comporte deux informations contestables:

  1. le radian ne vaut pas environ 57,3°, c’est le degré qui vaut environ 0.0175 radians ;-)
  2. le radian n’est pas une unité dérivée du système international, car sa définition est totalement indépendante des unités MKSA, en particulier du mètre.

Le grade par contre est une vraie unité dérivée du système international, car elle est basée sur la définition du mètre de 1791 comme étant la dix-millionième partie d’un quart de méridien terrestre. En définissant un grade comme un 400ème de tour, on parcourait 100 km pour un grade sur une carte Michelin graduée dans ces unités, sur le méridien de Paris évidemment… Voilà donc une unité d’angle assez proche du degré mais moins pratique parce que 400 n’est pas hautement composé (8 diviseurs entiers contre 24 pour 360), et qui est liée à une unité de longueur alors que ni le degré ni le radian ne le sont… Après trois petits tours dans les classes hexagonales, le grade se dirige à grands pas vers la Poubelle de l’Histoire.

Toute cette longue introduction nous amène à une autre unité, peu connue et dont je voulais faire étalage :  le « pour mille d’artillerie ». Il y a si peu d’information sur ce terme que je pensais que ce n’était qu’une fantaisie suisse gravée sur les manivelles des canons que j’ai passé quelques semaines à pointer sur d’inoffensives montagnes sur lesquelles il fallait ensuite grimper pour chercher les obus non explosés qui auraient pu tuer des touristes (russes), voire des vaches. En fait le terme « pour mille d’artillerie » est un helvétisme du mil angulaire, un angle très proche du milliradian. Comme c’est un petit angle, sa tangente est presque égale à sa valeur en radians et vaut environ 1/1000, ce qui aide bien pour l’application sus-mentionnée : on tire à 10′000 m, ça pète 30 mètres à droite, hop, 3 pour mille à gauche, feu ! C’est bon, on peut ressortir les cartes de Jass et déboucher une autre bouteille..

Pour bien faire il faudrait environ 6283 mils par tour, mais 6400 est plus facile à diviser (25 diviseurs), et comme 6400=100 x 2^6, on peut même fabriquer un rapporteur gradué en mils en pliant un papier carré en deux par la diagonale, puis encore en deux par la bissectrice de l’angle de 45° et ainsi de suite plusieurs fois. Bref, le mil combine astucieusement la définition rigoureuse du radian, la divisibilité entière du degré (hélas pas par 3, mais par les puissances de 2 c’est bien utile aussi) et ajoute juste ce qu’il faut du système décimal. Une unité bien pratique, et pas seulement pour tirer sur ses voisins.

Je voulais encore citer d’autres unités d’angle découvertes en rédigeant cet article, notamment  le Du chinois, qui a une définition astronomique intéressante : il correspond au déplacement angulaire moyen du Soleil sur la voute céleste en 24h, soit 360°/ 365.25 [jours/an], ce qui donne un angle très proche du degré ! Les chinois avaient encore le cun, le chi et le zhang, mais c’étaient des unités pifométriques dont l’utilité se limite au Scrabble.

Références

  1. Trigo Historique
  2. Les origines des notations mathématiques

16 janvier 2010 Posté par Dr. Goulu | Géométrie, Histoire | | Pas encore de commentaires

Das System

Entre le foie gras et les flocons, j’ai dévoré « Das System », un thriller technologique de l’allemand Karl Olsberg sur l’apparition d’une intelligence artificielle distribuée sur internet.

Une startup (allemande) crée une sorte de BOINC pour prévoir la météo en utilisant la puissance de calcul des PC disséminés sur internet. Mais le truc devient un virus (un BOINC viral… idée à retenir …), et le système devient intelligent, conscient, et dangereux…

Vous avez peur ? Science-fiction futuriste ? En fait, plusieurs penseurs et scientifiques soutiennent  que nous ne sommes qu’à quelques décennies de la singularité technologique, le moment où les outils que nous avons crées n’auront plus besoin de nous pour fonctionner, ni pour produire d’autres outils. Aujourd’hui déjà, on estime que la puissance de tous les ordinateurs interconnectés sur internet équivaut à environ un cerveau humain, et la Loi de Moore nous promet l’équivalent artificiel des cerveaux de toute l’humanité dans 35 ans maximum…

Comme le mentionne un prof dans le roman, les microprocesseurs se reproduisent désormais beaucoup plus vite que les humains. Ils « se » reproduisent, car la conception et la production de machines ne peut plus s’envisager sans machines. En même temps qu’une extinction d’espèces basées sur la chimie du carbone, sommes-nous en train de démarrer une biologie du silicium ? Pour l’instant nous sommes encore indispensables pour certaines opérations délicates, notamment programmer, mais pour combien de temps ? Si un jour un logiciel devient capable de s’auto-améliorer en modifiant son propre code, ce ne sera plus qu’une question de secondes avant qu’on doive devenir très polis avec nos ordinateurs, dans le meilleur des cas…

La force du roman est de rendre ce scénario assez vraisemblable malgré d’inévitables raccourcis réducteurs, ou du moins de susciter la réflexion. Un bon bouquin à la Crichton donc, mais vous pouvez aussi attendre le film qui ne devrait pas tarder…

Référence :

  • Karl Olsberg, « Das System », Actes Sud, 2009, ISBN 9782742782581

Voir aussi:

13 janvier 2010 Posté par Dr. Goulu | Fiction, Informatique, Livres | | 13 commentaires