l'Extraordinaire Aventure du Chiffre

magnifique je suis un mordu de ce type de documentaire

samedi, 11 août 2012 19:15
Retrouver la source de toutes les informations grâce à un algorithme

Citation :

Les crimes, attentats, épidémies et simples rumeurs pourraient dorénavant être prévenus et pistés grâce à l'informatique.
Le chercheur Petro Pinto vient en effet de mettre au point un programme qui permettait de remonter à l'origine d'une information.
Le post-doctorant portugais Petro Pinto de l'Ecole polytechnique fédérale de Lausanne (EPFL) aurait inventé un algorithme pour retrouver la source de n'importe quelle information circulant sur le réseau. Il pourrait ainsi s'agir aussi bien d'un attentat que d'une épidémie ou d'une rumeur. Dans la revue Physical Review Letters de ce vendredi, le chercheur qui travaille sous l'autorité des professeurs Patrick Thyran et Martin Vetterli pour le Laboratoire de communications audiovisuelles de l'EPFL, explique : "Grâce à notre méthode, nous parvenons à remonter à la source de tous types d'informations circulant dans un réseau et ce en n'écoutant qu'un nombre restreint de membres".
Comme le scientifique l'explique dans son étude, il pourrait par exemple retrouver l'auteur d'une rumeur circulant entre 500 membres d'un même réseau, en analysant les messages de 15 à 20 contacts seulement. "Notre algorithme est capable de refaire à l'envers le chemin parcouru par l'information, et de remonter à la source", déclare le chercheur. Cela pourrait notamment servir à déterminer l'origine d'un spam ou d'un virus. Mais le système pourrait également être utile à l'identification de la source d'une épidémie ou à sa prévention. Un test a d'ailleurs déjà été effectué pour identifier l'origine d'une maladie infectieuse d'Afrique du Sud.
Petro Pinto raconte ainsi : "En modélisant les réseaux de circulation d'eau, rivières ou transports humains, nous avons pu retrouver l'endroit où se sont déclarés les premiers cas". "En choisissant judicieusement des points de contrôle, on pourrait alors détecter plus vite une propagation épidémique", souligne le chercheur mettant en avant la prévention de la transmission de maladies.
Outre cette expérience, le programme a été testé une seconde fois sur les communications téléphoniques en rapport avec les attentats du 11 septembre 2001. "En reconstruisant le réseau de ces terroristes uniquement sur la base des informations parues dans la presse, notre système nous a livré trois suspects potentiels, dont l'un était le leader avéré de ces attaques, selon l'enquête officielle". L'outil pourrait donc servir très prochainement aux enquêteurs, policiers et gendarmes, d'après le chercheur.

http://french.irib.ir/info/science/item/205846-retrouver-la-source-de-toutes-les-informations-gr%C3%A2ce-%C3%A0-un-algorithme

L'algorithmie relève du topic informatique berhoum mais merci

@DR LECTER bonjour j'ai fait une petite recherche le mot algorithme est liée au nombre depuis ( l'an 820 ) mais tu a raison l'algorithme est utilisé en informatique dans les années 1930

Qu’est-ce qu’un algorithme ?

Citation :

Même si les algorithmes sont souvent considérés comme étant du ressort exclusif des mathématiques et de l'informatique, leur champ d'application est en réalité beaucoup plus vaste.

Le mot « algorithme » vient du nom du grand mathématicien persan Al Khwarizmi (vers l'an 820), qui introduisit en Occident la numération décimale (rapportée d'Inde) et enseigna les règles élémentaires des calculs s'y rapportant. La notion d'algorithme est donc historiquement liée aux manipulations numériques, mais elle s'est progressivement développée pour porter sur des objets de plus en plus complexes, des textes, des images, des formules logiques, des objets physiques, etc.

De la méthode

Un algorithme, très simplement, c'est une méthode. Une façon systématique de procéder pour faire quelque chose : trier des objets, situer des villes sur une carte, multiplier deux nombres, extraire une racine carrée, chercher un mot dans le dictionnaire… Il se trouve que certaines actions mécaniques - peut-être toutes ! - se prêtent bien à la décortication. On peut les décrire de manière générale, identifier des procédures, des suites d'actions ou de manipulations précises à accomplir séquentiellement. C'est cela, un algorithme. En tant que méthode, il répond donc à des questions du type : « comment faire ceci ? », « obtenir cela ? », « trouver telle information ? », « calculer tel nombre ? ». C'est un concept pratique, qui traduit la notion intuitive de procédé systématique, applicable mécaniquement, sans réfléchir, en suivant simplement un mode d'emploi précis.

Un exemple commun est par exemple la recherche d'un mot dans le dictionnaire. On regarde d'abord la première lettre du mot, et on la compare avec celle des mots de la page où le dictionnaire est actuellement ouvert. Suivant la position relative des deux lettres en question dans l'ordre alphabétique, on tourne alors les pages en avant ou en arrière, jusqu'à ce que les premières lettres coïncident. Puis on reproduit la même procédure avec la deuxième lettre du mot, puis la troisième, et ainsi de suite… Cet algorithme familier nous indique que les objets manipulés ne sont pas nécessairement des nombres ou des objets mathématiques. Ici, ce sont des mots, ou des lettres. De plus, on comprend que pour qu'un algorithme soit applicable, il faut que les objets manipulés se présentent sous un format bien précis, qui assure à la fois l'efficacité et la généralité du procédé. En l'occurrence, s'il s'agit d'un dictionnaire français, il faut que les mots recherchés soient des mots français écrits en lettres latines, et surtout que, dans le dictionnaire, les mots soient bien classés par ordre alphabétique !

Du nombre à l'information

La vertu essentielle des algorithmes est de permettre l'exécution optimisée de procédés répétitifs, essentiellement grâce à la formalisation et à la description des enchaînements logiques à un niveau plus abstrait, et donc plus général. Ils s'étendent ainsi à des domaines de la société toujours plus nombreux et plus inattendus. Cette généralisation a accompagné le développement des langages de programmation depuis les années 60, qui permettent aujourd'hui la manipulation de structures et d'objets ayant des propriétés et des comportements analogues à ceux du monde ordinaire. Leur relation avec les couches profondes du traitement informatique est assurée après coup par le compilateur, de manière transparente pour le programmateur et le concepteur d'algorithmes.

En définitive, le codage numérique des objets manipulés (au niveau informatique) est devenu secondaire pour l'algorithmique. L'essentiel est de percevoir les éléments clés d'un processus de calcul, ou d'un procédé quelconque, et d'imaginer les suites d'opérations logiques les plus astucieuses et les plus efficaces pour le mettre en œuvre de façon automatique et performante. L'algorithme est donc en réalité le squelette abstrait du programme informatique, sa substantifique moelle, indépendante du mode de codage particulier qui permettra sa mise en œuvre effective au sein d'un ordinateur ou d'une machine mécanique.

L'importance des ordinateurs

Bien avant le premier ordinateur électronique, dans les années trente, les mathématiciens ont découvert un modèle général de machines procédant de manière logique (Logical Computing Machine) - les fameuses machines de Turing, capables d'effectuer mécaniquement tous les algorithmes possibles et imaginables, déjà découverts ou qui le seront jusqu'à la fin des temps. La thèse, dite de Church-Turing, selon laquelle tous les algorithmes sont représentables et effectuables sur une Machine de Turing, est aujourd'hui universellement acceptée. Il a même été démontré de manière formelle que les mécanismes de toutes les machines obéissant aux lois de la physique classique (newtonienne), aussi complexes soient-ils, ne pourront jamais réaliser des opérations qui ne soient pas assimilables (moyennant les correspondances adéquates) à un calcul sur une machine de Turing.

Or une telle machine n'est pas un monstre de complexité que l'humanité devra attendre des millénaires avant de posséder. C'est un modèle d'une simplicité extrême, et nos ordinateurs actuels sont bien plus complexes, dans leur conception et dans leur fonctionnement, qu'une machine de Turing élémentaire. Voilà pourquoi ce qu'une telle machine peut faire, tout ordinateur moderne peut également le faire : calculer tout ce qui est calculable, mettre en œuvre n'importe quel algorithme. Les seules limitations ne sont ni mathématiques, ni conceptuelles, mais liées à la physique : il s'agit de la vitesse de calcul et de la mémoire disponible qui, même si elles augmentent chaque année de manière vertigineuse, ne seront jamais infinies.

D'où l'importance d'identifier des algorithmes efficaces, et de représenter les données utiles de la manière la plus adéquate possible.

Algorithmes en recherche d'efficacité


Image d'un arbre de jeu pour le Tic-Tac-Toe

Quelle que soit leur puissance théorique, les machines informatiques réelles sont soumises à des limitations physiques touchant à la puissance de calcul, c'est-à-dire le nombre d'opérations élémentaires pouvant être effectuées chaque seconde, ainsi qu'à la mémoire disponible, c'est-à-dire la quantité d'informations qu'un programme peut avoir à disposition, ou auxquelles il peut accéder à tout moment en un temps raisonnable.

On peut ainsi évaluer le « coût » d'une opération informatique ou d'un calcul, au sens large, par le temps et la mémoire que nécessite son exécution. Une part importante de la recherche en algorithmique consiste à élaborer des algorithmes de plus en plus efficaces, c'est-à-dire ayant un « coût » le plus faible possible. Il apparaît souvent qu'un effort d'analyse important au moment de la conception permet de mettre au point des algorithmes extrêmement puissants vis-à-vis des applications, avec des gains de temps exceptionnels.

Prenons l'exemple, non-mathématique, de l'art du découpage japonais. Pour produire un motif géométrique compliqué dans une feuille de papier, on peut naïvement faire des trous aux ciseaux, un peu partout. Mais cette manière de procéder est à la fois difficile, longue et imprécise. Une autre méthode consiste à effectuer d'abord des pliages astucieux, pour ne donner ensuite que deux ou trois coups de ciseaux dans un coin (ce qui est très facile), et déplier la feuille. Le résultat sera invariablement plus précis (la symétrie étant automatique), et obtenu plus rapidement, avec bien moins de coups de ciseaux. La difficulté a été déplacée dans l'identification du bon algorithme, c'est-à-dire ici la succession et la localisation des pliages et des coups de ciseaux adéquats.

Pour résoudre un même problème, on peut souvent utiliser différents algorithmes, qui n'ont pas tous la même complexité . Ainsi, le calcul du PGCD (plus grand commun diviseur) de deux nombres entiers naturels non nuls peut être effectué de bien des manières. Il est possible de trouver le résultat en essayant la division par tous les entiers, mais le mathématicien grec Euclide a trouvé une méthode plus élégante, connue sous le nom d'algorithme d'Euclide. L'idée est la suivante : on divise le plus grand des deux nombres par le plus petit des deux, puis le plus petit des deux par le reste de la première division euclidienne. On recommence jusqu'à ce que le reste (qui diminue sans cesse) devienne nul.

Parallèlement à l'optimisation des algorithmes, une part importante de la recherche porte sur l'évaluation précise de leurs performances, et notamment sur la façon dont ces performances évoluent avec la taille des objets manipulés. La recherche systématique d'efficacité, si importante lorsqu'il s'agit de résoudre des problèmes complexes ou de fournir des réponses rapides, passe également par la recherche de nouveaux types de représentations ou d'organisations des données. On a vu l'influence des modes de rangement avec l'exemple du dictionnaire. Dans ce cas particulier, comme dans beaucoup d'autres, une structure « en arbres » se révèle particulièrement adaptée .



Un autre exemple, très différent, de l'utilisation de la structure d'arbres en informatique est la notion d'arbre de jeu (game tree) qui permet de modéliser pour un jeu à deux joueurs l'ensemble des enchaînements des différents coups possibles et de leurs ripostes jusqu'à une certaine profondeur. Donald Knuth, professeur émérite à Stanford, auteur de l'ouvrage de référence sur l'algorithmique, en plusieurs volumes, intitulé « The Art of Computer Programming » (« L'art de la programmation informatique »), considère d'ailleurs les arbres comme « la structure la plus fondamentale de toute l'informatique ».

Si les progrès de la technologie des ordinateurs sont bien connus, avec l'accroissement exponentiel de la puissance de calcul et des capacités de stockage, ceux de l'algorithmique ne sont pas moins extraordinaires. Qu'on pense par exemple aux algorithmes de compression des images ou du son, ou à ceux permettant de calculer la suite des décimales de pi. Si on est passé de quelques milliers de décimales dans les années 1950, à plus d'un trillion fin 2002, c'est à peu près à part égale en raison des avancées technologiques et algorithmiques.



http://interstices.info/jcms/c_5776/quest-ce-quun-algorithme

Des chercheurs trouvent une formule, pour résoudre tous les sudokus

Citation :

Deux chercheurs américains sont parvenus à mettre au point un algorithme mathématique, qui permet de résoudre tous les sudokus, très rapidement, et sans avoir à réfléchir ou observer la grille de chiffres.
5, non... 6 ou 3 ? ou 2 ? Depuis plusieurs années, le sudoku a fait une entrée en force dans les journaux. Alors que ceux-ci publiaient autrefois des mots croisés pour divertir leur lectorat, aujourd'hui, bon nombre d'entre eux ne jurent plus que par ces jeux en forme de grille. Le principe est simple : dans la forme classique, il faut remplir toute la grille en plaçant les chiffres de 1 à 9 de telle manière que deux identiques ne se retrouvent pas sur la même ligne, sur la même colonne ou dans le même carré. Pour cela, il faut partir des symboles déjà inscrits et s'adonner à une série de réflexions et de déductions, permettant de placer au fur et à mesure chaque chiffre.
De facile, à moyen puis difficile voire diabolique, il en existe désormais de tous les niveaux. Certains se résolvent ainsi en quelques minutes quand d'autres peuvent prendre plus d'une heure voire plusieurs. Quand on ne parvient pas à le finir, une seule possibilité s'ouvre alors... regarder la solution. Mais des chercheurs de l'université de Notre-Dame aux Etats-Unis ont décidé eux, d'aller chercher plus loin pour résoudre ses casse-têtes chiffrés. En effet, Zoltan Toroczkai et Maria Ercsey-Ravasz ont mis au point un algorithme mathématique capable de résoudre n'importe quel sudoku, très rapidement et sans même avoir à le considérer.
C'est dans le cadre de leurs recherches sur l'optimisation et la complexité informatique que les deux scientifiques se sont intéressés à ce jeu défini en 1979 par l'Américain Howard Garns. Selon eux, les fans de Sudoku utilisent un système de "force brutale" pour résoudre les problèmes, combiné avec un fort processus de déduction. Ils essaient alors tous les combinaisons de chiffres possibles jusqu'à ce que la réponse correcte soit trouvée. Mais si cette méthode est efficace, elle représente une grande perte de temps, estiment les chercheurs plutôt fiers de leur trouvaille publiée dans la revue Nature Physics.
Un nouveau classement des grilles de 1 à 4
A la place, ceux-ci proposent donc d'utiliser leur algorithme universel qui est entièrement déterminant et arrive toujours à la réponse correcte, ceci en bien moins de temps. Au cours de leurs travaux, les chercheurs ont d'ailleurs constaté que le délai nécessaire pour résoudre le problème avec leur algorithme dépendait de la difficulté de la grille attribuée par ses concepteurs. Ils sont ainsi parvenus à développer une échelle de difficulté des problèmes ou des puzzles.
Elle s'étend de 1 à 4 et correspond à peu près à la classification du "facile" à "très difficile" appliquée d'ordinaire. Plus en détail, l'échelle indique notamment qu'une grille de "force" 2 met 10 fois plus de temps à être résolue qu'une de force 1. Ajouté à cela, elle précise également que le puzzle le plus difficile connu aujourd'hui atteint le niveau de 3,6. Mais on ignore aujourd'hui si d'autres grilles encore plus complexes existent.
Savoir jusqu'où l'homme peut aller
"Je ne m'étais pas intéressés au Sudoku jusqu'à ce que l'on commence à travailler plus généralement sur la classe des problèmes SAT" (boolean SATisfiability problem), qui visent à savoir s'il existe une solution à une série d'équations logiques données, explique Toroczkai. "Dans la mesure où le Sudoku fait partie de cette classe, cela semblait être un bon banc d'essai pour notre résolveur, donc je me suis familiarisé avec. Pour moi, et d'autres scientifiques étudiant de tels problèmes, c'est une question fascinante de savoir jusqu'où les hommes peuvent aller en résolvant des Sudokus et sans faire marche arrière, autrement dit sans faire de choix au hasard, en voyant où cela mène et si cela ne fonctionne pas, en recommençant", ajoute t-il.
Reste que pour utiliser l'algorithme des chercheurs, il faut tout de même s'y connaitre un tantinet en mathématiques et qu'au final, les sudokus servent justement à occuper son temps. Quoi de plus satisfaisant que d'achever le remplissage de la grille, après trente minutes d'asticotage mental ? Outre l'intérêt scientifique, pas sûr donc que la résolution instantanée des grilles convainque tant que cela ! Mais les chercheurs estiment que leur algorithme pourrait servir pour résoudre une grande variété de problèmes rencontrés dans l'industrie, l'informatique et même la biologie.

http://french.irib.ir/info/science/item/222954-des-chercheurs-trouvent-une-formule-pour-r%C3%A9soudre-tous-les-sudokus