Les fondements de l'informatique

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 STIC (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 stipule 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 6 pages par sujet (un exposé soutenu par un exemple, des idées de travaux pratiques et 2 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 6 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 20^e siècle, ni en avoir besoin. Pourtant, la logique du 20^e 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.
Lire une critique plus détaillée de cet ouvrage .

Les Métamorphoses du calcul

Gilles Dowek (Le Pommier 2007)

Socle des mathématiques, la notion de démonstration s'est profondément transformée dans les trente dernières années. Le calcul, longtemps éclipsé par le raisonnement, retrouve aujourd'hui sa place dans les démonstrations. L'ouvrage retrace les avancées mathématiques qui sont à l'origine de ces transformations. Il nous amène en particulier à réfléchir sur les liens entre les mathématiques et l'informatique, notamment la possibilité maintenant offerte de dépasser les limites en taille des démonstrations mathématiques.

Un livre très accessible, à la frontière des mathématiques, de l'informatique et de la philosophie, qui fait réfléchir sur les évolutions des mathématiques.

Petite introduction à l'algorithmique - À la découverte des mathématiques du pas à pas

Pierre Damphousse (Ellipses 2005)

« Petit » par la taille, cet ouvrage donne une vision rigoureuse et concise des concepts centraux de l'algorithmique, en les illustrant par des exemples et en les mettant en perspective par de nombreuses références historiques.
En résumé, un ouvrage d'informatique mathématique à la fois fluide et rigoureux, destiné à un lectorat étendu mais averti, qui évite tout jargon informatique et ne nécessite aucune connaissance d'un langage de programmation.

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.
Lire une critique plus détaillée de cet ouvrage .

À la racine des nombres - Une histoire du calcul numérique des origines à nos jours

Philippe A. Doisy (Ellipses 2006)

Le calcul de la racine carrée d’un nombre, tel est le fil rouge de cet ouvrage. Pas moins d’une vingtaine de méthodes de calcul sont exposées, dont les plus anciennes remontent à l’époque babylonienne.

Leur justification mathématique est entrelacée de repères historiques, tant sur les techniques numériques et les mathématiciens qui les inventèrent que sur les outils de calcul disponibles pour les mettre en œuvre. L'auteur présente ainsi calculi et tables à calcul, abaques, bouliers, tables de logarithmes, compas de proportion, règle à calcul… jusqu’aux calculettes modernes, où la détermination d’une racine carrée s’obtient d’une simple pression sur la touche appropriée. Même aujourd'hui cachés, les algorithmes utilisés s’inscrivent en filiation directe de leurs antiques prédécesseurs.

Sans doute pas une histoire exhaustive du calcul numérique, mais un fascinant cocktail pédagogique de science et d’histoire(s).

Mathématiques concrètes - Fondations pour l'informatique

Ronald L. Graham, Donald E. Knuth et Oren Patashnik (Vuibert 2003)

Traduction de Concrete Mathematics (Addison-Wesley Company 1988).
Un type particulier de mathématiques (basées sur le discret plus que sur le continu) constitue la base de l'informatique. Ce type de mathématiques devrait avoir plus de place par rapport à celui tourné vers les sciences pour l'ingénieur telles qu'elles existaient il y a cinquante ans (et qui est encore dominant dans l'enseignement en France). Problèmes récurrents, sommes, théorie élémentaire des nombres, probabilités discrètes, calcul asymptotique sont quelques-uns des thèmes de ce livre pour étudiant en informatique (niveau bac ou plus) souhaitant apprendre les mathématiques qui auront le plus de chances de lui être utiles.
Un livre qui ose attaquer des problèmes un peu ardus, mais à la portée de tous les étudiants en science ou technique.

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.
Présentation, vidéo et transparents .

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.

Entre mathématiques et informatique : l'analyse des algorithmes

Philippe Flajolet

Conférence donnée dans le cadre du Colloquium Jacques Morgenstern à Sophia Antipolis.
Présentation, vidéo et transparents .

Jusqu'au dix-neuvième siècle, les mathématiques sont de nature largement algorithmique, mais les problèmes de complexité, s'ils sont présents, restent souvent subliminaux. L'avènement de l'informatique pose, dès les années 1950, de nombreuses questions, dès lors que l'on cherche à comprendre, prédire, et quantifier les performances des algorithmes. Le nouveau domaine de l'analyse d'algorithmes est fondé par Donald Knuth au début des années 1960. Au fil de quelques exemples, cette conférence retrace l'évolution des idées depuis la période des pionniers jusqu'à maintenant. On voit ainsi surgir des domaines mathématiques extraordinaires issus des recherches en informatique. Tous ces domaines illustrent, selon le mot du physicien Eugene Wigner, la « déraisonnable efficacité des mathématiques » dans les sciences, ici, l'informatique.

La déraisonnable efficacité des mathématiques

Gilles Dowek

Conférence donnée dans le cadre du Colloquium Jacques Morgenstern à Sophia Antipolis.
Présentation , vidéo au format Real et transparents en PDF.

Depuis le XVII^e siècle, on s'interroge sur les raisons de l'efficacité des mathématiques comme outil de description de la nature, ou, pour reprendre les mots de Galilée, sur les raisons pour lesquelles « Le Grand Livre de la nature est écrit en langage mathématique ». Beaucoup d'idées reçues sur le sujet sont, au passage, à démythifier.

L'informatique est une science qui offre une nouvelle manière d'aborder cette question en se demandant ce qui est calculable dans un temps fini. C'est un des piliers de l'informatique théorique, la notion de fonction calculable (liée à ce qu'on appelle la « thèse de Church ») qui permet à Gilles Dowek de proposer une réponse possible, finalement époustouflante de simplicité à ce problème philosophique... qui est... ah non, nous préférons vous laisser le découvrir !

C'est aussi un bel exemple de ce que l'informatique, en tant que science, bien au-delà des ordinateurs, permet de comprendre du monde.