Les mathématiques de la complexité. Le développement prodigieux des capacités de calcul des ordinateurs depuis 1945 a créé un nouveau terrain de recherche et d'investigation pour la recherche mathématique.
Une des pistes ouverte par cette révolution culturelle a été la question de la « calculabilité » et l'autre l'invention de structures aptes a traiter de façon adéquate les structures biologiques a l'occasion du décodage de la structure du génome (bioinformatique). Ces deux question ont été réunie sous la catégorie des « mathématiques de la complexité ». La naissance puis le développement de l'informatique a eu un impact fort sur les mathématiques de deux façons, tout d'abord parce que c'est elle qui a créé les bases de l'informatique (qui découlent directement des travaux sur la calculabilité) avant même que les dispositifs n'existent « en dur », et que les capacités de calculs ont conduit à l'apparition de réflexions mathématiques sur la meilleure façon d'organiser un calcul.
Théorie algorithmique de l'information - INRIA. Quelques rudiments de calculabilité et de complexité - INRIA. Algorithmique : tri et complexité. La théorie de la complexité en cryptologie. Philippe Guillot Maître de conférences : cryptologie La cryptographie contemporaine s'appuie sur des fonctions à sens unique.
Ces fonctions sont facilement calculables, mais il est pratiquement impossible, avec une valeur, de retrouver le paramètre qui a conduit à cette valeur. Par exemple, en choisissant deux grands nombres premiers, il est facile de les multiplier. Actuellement, le seul produit ne permet pourtant pas de retrouver les facteurs si ceux-ci sont choisis assez grands. Si je vous donne, par exemple, le défi de factoriser le nombre 2.027.651.281, vous aurez sans doute beaucoup de mal à trouver les facteurs sans un outil performant de calcul. Vue d'artiste de la machine de Turing (sans la table de transition). © Schadel, DP Le souci est que l'existence de tels problèmes n'est pas assurée. . • une unité centrale de calcul qui peut se trouver dans un nombre fini d'états ;
En relation avec le sujet du cours - Chaire d'Informatique et sciences numériques (2012-2013) Bardet. P12-M1-Crypto_2.pdf. Reseaux-ihes-V1.pdf. ISICIL-ANR-EA01-SNAetWS-0906.pdf. Lazega-et-al-in-Zwirn@V2.pdf. L’histoire vue par les réseaux sociaux. L’anthropologie computationnelle est cette branche des « humanités numériques » qui cherche à comprendre la mentalité des peuples en utilisant les ressources de l’ordinateur et du Net.
La Technology Review nous apprend que Peter Gloor (@pgloor, blog), du centre du MIT pour l’intelligence collective, et son équipe ont ainsi utilisé la Wikipédia pour établir quels étaient, pour chaque culture, les personnages les plus importants (le papier original est disponible chez ArXiv). A cette fin, ils ont effectué des recherches sur les pages « célébrités » de quatre Wikipédia différentes : l’anglo-saxonne, l’allemande, la chinoise et la japonaise. Problèmes d'optimisation avec propagation dans les graphes : complexité paramétrée et approximation. Primalite_irem_2011.pdf. 1 - LÁSZLÓ BARABÁSI : « Une théorie de la complexité s'appuiera sur la science des réseaux.
Bitcoin et contenu en calcul. Quand on examine le protocole technique du bitcoin, on tombe sur un point apparemment insignifiant qui le complique bizarrement et semble mystérieux concernant la mesure de la longueur d'une blockchain.
En réalité il est important. Beaucoup plus, c'est la mise en œuvre pratique — pour la première fois semble-t-il— d'une idée théorique fondamentale de la théorie du calcul : l'idée que certaines chaînes de caractères ne peuvent résulter que d'un long calcul, autrement dit qu'elles possèdent un « contenu intrinsèque en calcul », ou selon les termes de la théorie «une grande profondeur logique de Bennett ».
Dans le cas du bitcoin, la présence de cette propriété n'est pas assurée par une démonstration en bonne et due forme, mais seulement par le savoir faire des cryptologues. Il n'en reste pas moins que cette idée est décisive pour que l'ensemble du protocole tienne debout. La valeur de la blockchain Pour gagner, il faut être le premier à résoudre une énigme assez difficile. La théorie A. B. Modéliser la propagation d’une épidémie. « Allora c’è un ordine del mondo !
» gridai trionfante. « Allora c’è un po’ d’ordine in questa mia povera testa » rispose Gugliemo. Umberto Eco, « Il nome della rosa », Bompiani, 1981 « Alors il y a un ordre du monde ! » criai-je triomphant. « Alors il y a un peu d'ordre dans ma pauvre tête », répondit Guillaume. Umberto Eco, « Le nom de la rose », trad. La propagation d’un agent infectieux au sein d’une population est un phénomène dynamique : les effectifs d’individus sains et malades évoluent dans le temps, en fonction des contacts au cours desquels cet agent passe d’un individu infecté à un individu sain non immunisé, l’infectant à son tour. Image prise au microscope électronique de virus de la grippe A.
S(t) + I(t) + R(t) = P Ce système peut être représenté graphiquement par un ensemble de trois compartiments connectés par des flux d’individus qui passent de l’un à l’autre : Diagramme des flux d’individus dans le modèle SIR. Combien d’objets dans une image ? - INRIA. Livre sur la complexité algorithmique. J'ai rédigé un livre sur la complexité algorithmique, paru en avril 2014 aux éditions Ellipses.
Il est aussi disponible librement en version électronique pdf (430 pages, 1,9 Mo) sous licence Creative Commons (paternité, pas d'utilisation commerciale, partage dans les mêmes conditions). La présente version de juin 2014 contient quelques corrections par rapport à la version imprimée : errata listées ici. Il couvre en détail les bases du domaine ainsi que de nombreux sujets avancés. Voici les différents chapitres : Le modèle de calculConsidérations de base sur le tempsNP-complétudeConsidérations de base sur l'espaceUniformité et non-uniformitéAlgorithmes probabilistesOracles et limites de la diagonalisationLa hiérarchie polynomialeComptageProtocoles interactifsBornes inférieures non uniformesDérandomisation et bornes inférieures. 0805michel.pdf.