Lire & Voir : Les fondements de l’informatique
Histoire illustrée de l’informatique
Emmanuel Lazard et Pierre Mounier-Kuhn (préface de Gérard Berry)
EDP Sciences, 2e édition, novembre 2019
L’informatique peut être vue comme un mélange entre, au moins, le matériel composant l’ordinateur, sa programmation et l’algorithmique.
Au cours de son évolution, l’informatique tend à s’organiser en un empilement de couches, ce qui permet de maîtriser sa complexité, chaque couche ne « voyant » si possible que les deux autres à son contact direct. Cette invisibilisation des couches successives permet au plus grand nombre d’utiliser de manière intuitive et sans craintes des objets sophistiqués comme les téléphones les plus récents : sans avoir besoin de connaître quoi que ce soit ni des transistors, ni des langages de programmation, ni de l’algorithme cryptographique protégeant les conversations et échanges de texte, chacun peut ainsi discuter en toute sécurité avec son banquier. Pour celui ou celle qui souhaite comprendre les multiples facettes de l’informatique, il faut au contraire trancher l’oignon et observer ces imbrications de couches pas toujours parfaitement masquées les unes aux autres.
Dans ce livre, les auteurs décrivent dans une perspective historique la croissance de cet oignon informatique. Elle est loin d’avoir été régulière car elle est le fruit d’un foisonnement d’idées disparates et parfois contradictoires au sujet des diverses couches, initialement loin d’être masquées, même si un tri entre ces idées s’opère au cours du temps. Les auteurs présentent l’oignon à divers stades de son développement, ils mettent l’accent sur huit époques depuis les origines de l’humanité et sans surprise insistent sur un découpage du XXe siècle. Chaque chapitre est consacré à une époque et débute par une synthèse donnant une vue d’ensemble de l’évolution dans cette période. Ces synthèses évoquent aussi bien les besoins grandissants justifiant le développement de l’informatique, que les tâtonnements autour des verrous technologiques ainsi que les interactions entre les acteurs scientifiques, étatiques, ou industriels.
À l’origine, le calcul et le traitement des données sont les principaux besoins. Les acteurs sont les scientifiques aussi bien académiques qu’en R&D, mais aussi les États dans leurs dimensions gestionnaires et militaires, ainsi que les industriels. Les synthèses détaillent les interactions entre ces acteurs, ce qui fait pâlir l’image d’Épinal du génie solitaire. La seconde partie de chaque chapitre présente alors une sélection de découvertes de son époque. Ces découvertes pourraient donner le désagréable sentiment de passer du coq à l’âne mais la synthèse permet de les replacer dans leur contexte. Un autre mode de lecture est possible car chaque découverte est évoquée sur une ou deux pages par un texte qui peut aussi se lire indépendamment du reste. Les photos accompagnant les textes justifient totalement le qualificatif d’histoire illustrée.
Dès l’introduction, les auteurs annoncent que leur présentation de l’histoire ne se veut pas exhaustive. J’ai trouvé leur sélection très pertinente pour décrire l’histoire de l’informatique, les textes étant très denses tout en restant accessibles, aussi bien sur les aspects techniques que sur les dynamiques de développement entre les acteurs. Leurs synthèses donnent un très appréciable recul sur l’évolution d’ensemble du domaine. La possibilité de lire indépendamment les capsules d’une à deux pages sur des points isolés en fait aussi un livre accessible aux plus jeunes et/ou moins aguerris en informatique.
Le logiciel, entre l’esprit et la matière
Xavier Leroy, leçon inaugurale au Collège de France, novembre 2018
« Xavier Leroy est un informaticien français, professeur au Collège de France et précédemment directeur de recherche à l’INRIA (sic). Il est connu pour être le principal concepteur et développeur du langage Objective Caml. […] Xavier Leroy est un expert réputé dans le domaine des langages fonctionnels, de leur typage et de leur compilation. Ces dernières années, il a également beaucoup travaillé sur les méthodes formelles, les preuves formelles et la compilation certifiée. Il est notamment à la base du projet CompCert qui a réalisé un compilateur pour le langage C entièrement certifié à l’aide de Coq. » (source : Wikipedia)
Deuxième titulaire d’une chaire permanente en informatique au Collège de France, Xavier Leroy a donné sa leçon inaugurale le 15 novembre 2018, avec beaucoup de clarté et un peu d’émotion, sans exclure un soupçon de distanciation ironique vis-à-vis de l’institution qui l’accueille. Lors de son exposé, le scientifique a commencé par rendre hommage à ceux qui ont fait entrer l’informatique au Collège de France, en particulier Gérard Berry et Pierre-Louis Lions.
Après un bref historique de l’informatique, soulignant l’importance croissante prise par le logiciel, qui s’affranchit des contraintes liées au matériel, puis un rappel de quelques chiffres qui donnent le vertige — 10 millions de lignes de code pour un navigateur Web, 2 milliards pour l’ensemble des logiciels de Google —, l’exposé se focalise sur le programme de recherche de Xavier Leroy au Collège de France : les sciences du logiciel.
Xavier Leroy rappelle l’histoire des fondations logiques du calcul automatique, au début du XXe siècle. Il aborde ensuite les aspects pratiques, c’est-à-dire l’efficacité de ces calculs mais surtout leur mise en œuvre grâce aux langages de programmation. Il se livre ensuite à un survol humoristique de l’histoire des langages de programmation, pour en venir au cœur de son sujet, la vérification des programmes : puisque les connaissances sur les langages de programmation sont désormais si poussées, puisque leur formalisation est si avancée, comment est-il encore possible qu’il y ait des bugs dans les programmes ?
La dernière partie du cours porte sur la vérification formelle, consistant à établir, par le calcul ou par déduction logique, des propriétés vraies pour toute exécution du programme étudié. Xavier Leroy présente ainsi un panorama des outils pour la vérification formelle et illustre son propos en prenant un exemple de programme, dû à Donald Knuth, pour calculer les n premiers nombres premiers. Il termine sa leçon sur une note optimiste : la vérification formelle permet d’atteindre un équilibre entre créativité (dans la conception du programme) et rigueur (dans l’assurance que ce programme se comporte bien comme il est supposé le faire).
La logique mathématique est le fil rouge de cet exposé. Le lien étroit, appelé « correspondance de Curry-Howard », entre les aspects logiciels et la programmation d’une part, et la logique et la preuve d’autre part, est rapidement abordé, il fait l’objet du premier cours de Xavier Leroy, donné le 21 novembre 2018.
Extrêmement agréable à suivre, en particulier grâce à l’utilisation d’analogies bien choisies qui éclairent le propos, ainsi qu’à une progression soigneusement élaborée pour paraître naturelle à l’auditoire, cet exposé fourmille d’exemples, d’anecdotes et de citations qui titillent l’attention et témoignent d’une grande culture, et pas uniquement informatique, de l’orateur. Seule la partie traitant de l’algorithme calculant les n premiers nombres premiers de Donald Knuth est légèrement plus technique.
Après cette savoureuse mise en bouche, il ne reste plus qu’à profiter des cours dispensés par Xavier Leroy au Collège de France de novembre 2018 à janvier 2019, tous disponibles sur le site du Collège de France.
Wandida | La Wandida du Savoir
Parfois, on se pose des questions toutes simples à première vue. Seulement, dès qu’on commence à creuser, elles soulèvent des montagnes d’interrogations. Idéalement, on aimerait pouvoir poser cette question à quelqu’un et obtenir l’explication aussitôt. Les plus courageux d’entre nous se lanceront dans des recherches à tout-va, liront des livres sur la question, iront chercher des supports de cours, ou interroger des sages, etc. Mais si on n’a pas de sage sous la main ? On en ressort souvent plus perdu qu’au départ, quand on n’est pas complètement découragé par l’ampleur de la tâche.
Pour ce qui est de l’informatique, des mathématiques et de la physique, il existe Wandida, une plate-forme de mini-cours en ligne, développée par l’EPFL, en Suisse, depuis 2012. L’idée est de demander à un spécialiste de la question (pas toujours sage) de faire un cours sur une tablette qui fait office de tableau blanc. Par exemple, on se demande « comment fonctionne le célèbre moteur de recherche Google ? », ou encore « est-ce qu’on peut donner une interprétation algorithmique des démonstrations ? » (oui, vous avez déjà un niveau assez élevé si vous vous posez cette question). Si ces deux exemples peuvent paraître assez conceptuels, vous pouvez aussi vous demander comment, en pratique, « passer d’un tableau à une fonction pour la gestion de la mémoire en C ».
Notons que la plate-forme se décline en plusieurs langues comme l’arabe standard ou l’anglais, même si le français reste majoritaire. Les vidéos ne sont pas des traductions d’une langue vers une autre ; ce sont à chaque fois des locuteurs natifs de la langue qui donnent leur point de vue. Il s’agit bien là de ne pas dénaturer le propos et d’utiliser le plus efficacement possible les subtilités de la langue.
L’une des difficultés est d’arriver à proposer un contenu explicatif court. Pour cela, il est nécessaire de revoir l’approche explicative des concepts pour cibler les propriétés nécessaires et montrer comment elles s’appliquent. Ce qui permet de décloisonner les cours traditionnels et de ne pas perdre le spectateur. En cela, les contenus proposés respectent parfaitement la démarche. Certes, il ne s’agit pas d’une relation enseignant-étudiant, mais on s’y retrouve bien tout de même. En une dizaine de minutes, avec une écriture typique des enseignants, on plonge dans les méandres d’une question.
Au départ, Wandida s’adresse principalement aux étudiants en informatique, mais son évolution permet aujourd’hui de toucher un public plus large, moins spécialiste. Précisons que Wandida n’est pas une plate-forme de MOOC (Massive Online Open Courses). Il ne s’agit pas de proposer un cours global en informatique, mais d’accompagner les étudiants dans leur apprentissage. Cette plate-forme complètement ouverte ne nécessite aucune inscription et ne donne lieu à aucun suivi. Ce qui permet d’une part de tomber dessus par hasard, d’autre part, et surtout, de piocher dedans en fonction de ses besoins.
En résumé, si vous vous posez des questions simples néanmoins extrêmement compliquées sur l’informatique, Wandida vous sera d’une aide précieuse. Finalement, ce qui compte le plus, c’est qu’on continue de se poser des questions !
Penser, modéliser et maîtriser le calcul informatique
Gérard Berry, leçon inaugurale au Collège de France, novembre 2009
Cette leçon inaugurale donne le ton ; l’informatique est une discipline scientifique autonome, dont l’objet d’intérêt est le calcul automatisé, avec les notions qui y sont associées : algorithme, complexité, preuve, programme, information, codes, etc. En une heure d’un exposé particulièrement vivant, Gérard Berry présente les différents modèles de calcul sur lesquels planchent les chercheurs en informatique, tout en rappelant les enjeux scientifiques, techniques et sociétaux de ces recherches.
Un enthousiasme communicatif qui met en appétit pour les séances à venir et pour des lectures d’approfondissement sur Interstices, à propos des algorithmes, de la notion d’information ou de celle de calcul, ou encore de la machine de Turing et de la pensée de son concepteur.
Computer Science Unplugged – L’informatique sans ordinateur
Tim Bell, Ian H. Witten et Mike Fellows
Si on peut passer des heures à cliquer sur une souris sans rien apprendre d’informatique, on peut aussi apprendre beaucoup d’informatique sans toucher une souris ! Les activités d’éveil proposées dans le recueil Computer Science Unplugged en font la preuve. Destinées aux enfants à partir de l’école primaire, elles offrent une introduction aux fondements de la science informatique qui pourra intéresser petits et grands.
Adaptée de la version originale en anglais, en accord avec les auteurs, la version française est disponible ici en PDF haute définition pour l’impression (14 Mo) ou avec les images compressées pour affichage à l’écran (5 Mo).
L’équipe d’Interstices a eu le plaisir de piloter la traduction de ce document.
Les clés de la révolution numérique
Revue DocSciences n°5, novembre 2008
Partager avec toutes et tous les fondements de cette révolution numérique qui habite désormais notre quotidien : c’est la motivation de ce numéro de la revue DocSciences. Origine de l’ordinateur, mécanismes de codage de l’information, fondements de l’algorithmique, programmation, réseaux et cryptographie : autant de clés pour comprendre et maîtriser plutôt que subir la société numérique.
La revue DocSciences, éditée par le CRDP de l’académie de Versailles, est destinée plus particulièrement aux enseignants et aux lycéens. Dans ce numéro réalisé en partenariat avec Inria, les articles rédigés par des auteurs contribuant régulièrement à Interstices font découvrir les aspects fondamentaux de l’informatique. Des repères essentiels au moment où notre éducation se prépare à construire une génération de créateurs et de bâtisseurs du monde numérique de demain.
Musée des arts et métiers
Ce musée parisien, créé après la Révolution française pour mettre en valeur les instruments scientifiques et les prouesses techniques, présente de nombreux objets en lien avec l’informatique. Un parcours à travers ses collections vous mènera des machines à calculer mécaniques, dont la fameuse Pascaline, jusqu’aux robots, en passant par les métiers à tisser qui ont introduit une première forme rudimentaire de programmation.
De plus, une exposition temporaire intitulée « Carte à puce. Une histoire à rebonds » y est présentée jusqu’au 3 janvier 2016. Intégrée au parcours des collections permanentes, elle montre l’histoire de cette technologie à travers de nombreux objets et des vidéos, en particulier, une introduction fort originale à la cryptographie.
Jusqu’au mois d’avril 2009, l’installation De mémoires d’ordinateurs, présentée dans la petite salle d’actualités au premier étage, a permis aux visiteurs de voir à l’intérieur d’un ordinateur les différents éléments matériels qui le font fonctionner. L’accent était mis plus particulièrement sur le rôle joué par les mémoires, ainsi que sur la miniaturisation des composants.
Requiem pour une puce
Gérard Ramstein (Seuil 2001)
Un « roman policier » se déroulant à Cambridge en 1929 et où se télescopent (au mépris total de la chronologie) les fondateurs de l’informatique, prétexte pour présenter les concepts de base de la discipline. Savoureux, informatif et très agréable à lire : à recommander à tous ceux qui ne veulent pas en savoir plus sur les sciences du numérique (pour les aider à changer d’avis…).
Qui a tué le professeur Stibitz ? Comment Alan Turing, étudiant aussi génial qu’original, va-t-il prêter main-forte à l’inspecteur Langsdale pour comprendre les rapports entre la Pascaline et le langage binaire ?
Un livre pour tous, à lire sans modération.
Les ordinateurs de demain
Alain Schuhl (Le Pommier 2004)
Une loi empirique énoncée par Gordon E. Moore en 1965 dispose que le nombre de transistors placés dans un circuit intégré doublerait tous les deux ans. Cette « loi » s’est jusqu’à présent vérifiée : la capacité (en mémoire) et la puissance (de calcul) de ces « puces », au cœur de tout ordinateur comme de tous les dispositifs de calcul embarqués, se sont ainsi multipliées d’un facteur 32 tous les 10 ans. Il est clair cependant que cette croissance exponentielle ne pourra pas se poursuivre avec les technologies actuelles, essentiellement fondées sur l’emploi des transistors au silicium.
Après quelques rappels sur ces technologies et leur histoire, ce petit livre d’une soixantaine de pages, publié en 2004, fait donc le tour des technologies de substitution candidates : électronique moléculaire et électronique de spin, mais aussi calcul par hybridation de molécules d’ADN et calcul quantique. Remarquons que si les deux premières technologies sont neutres vis-à-vis du calcul, ce n’est certainement pas le cas des deux dernières, qui suggèrent de nouvelles approches algorithmiques.
Notons que le chapitre sur l’électronique de spin, ou « spintronique », fait évidemment référence aux travaux d’Albert Fert, lauréat français du prix Nobel de physique en 2007 pour la découverte de la magnétorésistance géante.
The (New) Turing Omnibus: 66 Excursions in Computer Science
A. K. Dewdney (W. H. Freeman & Company 1993)
Dans un format standardisé de six pages par sujet (un exposé soutenu par un exemple, des idées de travaux pratiques et deux références), l’auteur présente 66 concepts informatiques. Les thématiques abordées sont très variées, architecture, logiciel, algorithmique ou théorie. Quand un concept est trop important pour être traité en six pages, il est fractionné en plusieurs sous-concepts que l’on retrouve disséminés dans le livre. Au total, le livre représente beaucoup de connaissances techniques, mais chaque article ne mobilise qu’une poignée de notions. C’est le livre de l’Honnête Homme en informatique.
Un livre pour tous les curieux du « comment ça marche »… qui lisent l’anglais.
La machine en logique
Pierre Wagner (PUF 1998)
L’informaticien peut ne pas connaître les résultats de la logique formelle du XXe siècle, ni en avoir besoin. Pourtant, la logique du XXe siècle et l’informatique sont cousines. Ce livre peut servir d’introduction à certains de ses concepts, en lien avec les programmations logiques ou fonctionnelles, ou les méthodes formelles de développement de logiciel. L’auteur les présente très simplement dans des notations modernes, mais en les plaçant dans une perspective historique. Il introduit à la fin de l’ouvrage la notion intrigante de « pensée mécanique », qui ne serait autre que l’activité des machines, modélisable dans la logique.
Un livre qui ose attaquer des problèmes un peu ardus, mais à la portée de tous les étudiants en science ou technique.
Le rapport entre informatique et logique prend des formes extrêmement variées (par exemple la démonstration automatique, la programmation logique, le lambda-calcul, les machines de Turing, la sémantique) qui révèlent qu’il y a là un lien puissant, mais qui n’en dévoilent pas vraiment la nature ni les conséquences philosophiques. De ce dernier point de vue, la situation est particulièrement confuse puisque, par exemple, des auteurs ont pu tirer du théorème d’incomplétude de Gödel des conclusions philosophiques opposées sur la possibilité d’une intelligence artificielle. Pierre Wagner est philosophe et propose dans son livre une étude des relations entre machine, informatique et logique, et de leurs conséquences philosophiques. Le dernier point peut paraître superflu à un informaticien, mais il faut se souvenir que la logique intéresse le philosophe en tant que formalisation du langage, de l’argumentation et de la vérité. De son côté, l’informaticien peut ne pas connaître les résultats de la logique formelle du 20e siècle, ni en avoir besoin. Mais même dans cette situation, il peut avoir vent de théories informatiques comme les programmations logiques ou fonctionnelles, ou les méthodes formelles de développement de logiciel. Malheureusement, il lui sera difficile d’aller au delà de la surface des choses sans se heurter à des expressions comme « modèle de Herbrand », « élimination des coupures » ou « isomorphisme de Curry-Howard ». Ce livre peut aussi servir d’introduction à certains de ces concepts. Il les présente très simplement dans des notations modernes, mais en les plaçant dans une perspective historique. À ce propos, Pierre Wagner a partout la prudence de mentionner qu’il ne s’agit pas de la présentation d’origine.
Pierre Wagner s’intéresse donc aux machines qui ont un rapport intime avec la logique, celles dont parle la logique, même sans le dire, ou qui parlent de la logique. En particulier, ne sont pas concernées les machines comme celle de Jevons, une sorte de Pascaline du calcul booléen qui ne fait que réaliser un calcul algébrique. Au contraire, les machines de Turing, ou les machines à réduction du lambda-calcul, disent des choses sur la décidabilité ou la complexité de la logique.
Ce livre contient plusieurs chapitres de nature historique sur l’introduction de machines formelles dans la logique : systèmes formels à la Hilbert, machine de Turing, thèse de Church, théorème de complétude de Gödel, etc. L’auteur fait ensuite un exposé détaillé des théorèmes d’incomplétude de Gödel en en expliquant les conséquences, et sans en faire l’« épouvantail » qui en est fait habituellement. Il fait le constat que l’usage, souvent métaphorique, de la logique formelle pour répondre à des questions de philosophie de l’esprit s’arrête le plus souvent aux résultats de Gödel, et donc au début des années 1930. Pierre Wagner présente alors les travaux de Gentzen sur la normalisation des preuves, et l’isomorphisme de Curry-Howard. Ce dernier, en établissant une relation formelle entre programme et preuve, ajoute la question de la cohérence algorithmique à celle de la cohérence logique, et fait que des problèmes d’informatique théorique deviennent des problèmes de logique. C’est pour cela que l’auteur en fait la pierre angulaire des relations entre logique moderne et machine.
Un développement original de ce livre est celui sur la question d’une « intelligence artificielle » conçue comme l’imitation de l’intelligence humaine par une machine. L’auteur observe que les théorèmes d’incomplétude de Gödel ont été utilisés plus ou moins métaphoriquement à la fois pour défendre cette possibilité et pour la condamner. Pierre Wagner choisit une troisième voie et défend l’idée de l’étude de la pensée mécanique qui serait par définition l’activité des machines, et non pas une métaphore mécaniste de la pensée humaine. La logique serait alors une formalisation de cette pensée mécanique. Cette étude ne se limiterait pas aux méthodes heuristiques dites de l’intelligence artificielle, mais engloberait aussi les méthodes algorithmiques.
Histoire d’algorithmes : du caillou à la puce
Jean-Luc Chabert et al. (Belin 1994)
Cet ouvrage collectif donne à voir des algorithmes depuis l’antiquité jusqu’à l’émergence du concept. Les auteurs ont choisi de ne présenter que des algorithmes numériques. Pour chaque famille d’algorithmes, l’ouvrage présente la situation du problème, des documents originaux (éventuellement décryptés et paraphrasés) et des commentaires. Ils aident le lecteur à comprendre les circonstances de la création et ils le laissent faire le lien avec le monde algorithmique moderne. Une mine de documents pour l’esprit curieux.
Un livre de culture pour un large public, et aussi de beaux exemples pour les étudiants.
Bien que le concept formel d’algorithme ait émergé relativement récemment (avant l’ère informatique toutefois), on conçoit des algorithmes, on utilise le mot, on raisonne sur eux depuis fort longtemps. Cet ouvrage collectif donne à voir des algorithmes depuis l’antiquité jusqu’à l’émergence du concept. Les auteurs ont choisi de ne présenter que des algorithmes numériques. Pour chaque famille d’algorithmes, l’ouvrage présente la situation du problème, des documents originaux (éventuellement décryptés et paraphrasés) et des commentaires. Cela fait la matière de 14 chapitres, assez techniques à deux titres : d’abord il faut souvent faire un effort et se rappeler ses années d’école ou d’université pour suivre les sujets traités, et ensuite les documents présentés n’ont pas toujours les vertus pédagogiques d’un cours moderne. Un quinzième chapitre, hors numérotation, traite de l’émergence même du concept d’algorithme. On y voit les premiers textes de Gödel, Kleene, Church, Turing et Post sur le sujet.
Un trait marquant de cet ouvrage est que ses auteurs ont le parti pris du « fait brut ». Bien sûr, ils commentent les documents qu’ils présentent, mais toujours relativement au problème traité, et jamais dans la perspective de cette histoire d’algorithmes. Ils aident donc le lecteur à comprendre les circonstances de la création du document, mais ils le laissent faire le lien avec le monde algorithmique moderne. Une citation montre leur point de vue : « Cette épaisseur culturelle ajoutée est susceptible d’aider à se poser de vraies questions à propos de problèmes parfois envisagés de façon purement abstraite ». Ils sont loin de donner les réponses ! Dans cette démarche de responsabilisation du lecteur, les auteurs vont jusqu’à introduire sans prévenir un canular qui illustre la difficulté d’interpréter les documents antiques. Ce livre n’est donc pas un cours d’histoire des mathématiques ou de l’algorithmique, mais le complément documentaire d’un tel cours. Il est surtout une mine de documents pour l’esprit curieux.
Comment distinguer le simple du complexe ?
Complexité de Kolmogorov et profondeur logique de Bennett
Jean-Paul Delahaye
Exposé présenté au Laboratoire d’Informatique de Grenoble le 7 décembre 2009.
Dans cet exposé didactique, Jean-Paul Delahaye s’appuie sur de nombreux exemples pour introduire et comparer différentes formalisations de la notion de complexité, qui est au cœur des questions que se posent les mathématiciens et les informaticiens.
La première partie de l’exposé porte sur la complexité de Kolmogorov, qui s’appuie sur la théorie algorithmique de l’information de Gregory Chaitin et Andreï Kolmogorov, et fait suite aux théories sur la calculabilité de Alonzo Church, Kurt Gödel et Alan Turing. Elle donne de la notion d’information une vision nouvelle, complétant et précisant celle de Claude Shannon, qui permet de capturer et de mesurer toutes sortes de redondances et de régularités dans les objets auxquels on l’applique : les régularités de type statistique aussi bien que les régularités de type arithmétique, algébrique ou combinatoire.
Jean-Paul Delayahe montre ensuite comment l’application pratique de la complexité de Kolmogorov, par l’utilisation d’algorithmes de compression, conduit à de nouvelles méthodes de classification des langues, des séquences génétiques, mais aussi des textes littéraires, des morceaux de musique et des images.
Dans la troisième partie de l’exposé, Jean-Paul Delahaye montre les limites de la formalisation de Kolmogorov (qui ne permet pas de distinguer entre « complexité aléatoire » et « complexité organisée ») et comment des travaux très récents du physicien Charles Bennett sur le concept de profondeur logique ont permis de donner un sens rigoureux à cette distinction naturelle. Ce nouveau concept complète d’une manière élégante la complexité de Kolmogorov, en se fondant à nouveau sur la théorie de la calculabilité.
Complexité et décidabilité
Patrick Dehornoy (Springer 1993)
Destiné aux étudiants (de niveau bac + 2 ou plus), ce livre est une introduction à la théorie du calcul et de la complexité telle qu’elle s’est développée depuis les années 1930. Rigoureux, précis et relativement complet, ce livre est aussi l’outil idéal pour quiconque veut apprendre ce que sont les machines de Turing, la thèse de Church, les problèmes indécidables, les machines universelles, les problèmes NP-complets, etc.
Le mauvais résultat tout de suite, ou le bon résultat trop tard ?
Jean-Michel Muller
Conférence donnée dans le cadre du Colloquium Jacques Morgenstern à Sophia Antipolis.
Effectuer des calculs numériques avec des nombres à décimale, cela a longtemps été comme une collection de recettes de cuisine : on avait le choix entre utiliser cette arithmétique virgule flottante, et obtenir rapidement des résultats sans trop savoir quel degré de confiance on pouvait leur accorder, ou utiliser d’autres mécanismes beaucoup trop lents pour la plupart des applications. Bref, le choix était entre le mauvais résultat tout de suite, ou le bon résultat trop tard. La situation a quelque peu changé : de grands progrès ont été accomplis ces dernières années dans le domaine de l’arithmétique virgule flottante. On s’en persuadera en regardant comment les calculs actuels impliquent non seulement des opérations électroniques mais aussi des mécanismes bien plus « malins », illustrés ici par quelques exemples.
Newsletter
Le responsable de ce traitement est Inria. En saisissant votre adresse mail, vous consentez à recevoir chaque mois une sélection d'articles et à ce que vos données soient collectées et stockées comme décrit dans notre politique de confidentialité
Niveau de lecture
Aidez-nous à évaluer le niveau de lecture de ce document.
Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !