Pour découvrir les concepts et outils fondamentaux des sciences et technologies de l'information et de la communication, quelques ouvrages de référence et exposés diffusés en vidéo.

">
Les Newsletters Interstices
Activité du processeur lors l’exécution d’un programme © Inria / Photo H. Raguet
    Niveau facile
    Niveau 1 : Facile

    Les fondements de l’informatique

    Culture & Société
    Algorithmes

    Pour découvrir les concepts et outils fondamentaux des sciences et technologies de l'information et de la communication, quelques ouvrages de référence et exposés diffusés en vidéo.

    Wandida | La Wandida du Savoir

    couverture

    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 plateforme 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 plateforme 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, on ne retrouve pas la 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 plateforme 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 plateforme 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, mais 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 !

    Maxime Amblard

    Penser, modéliser et maîtriser le calcul informatique

    Gérard Berry, leçon inaugurale au Collège de France, novembre 2009

    Leçon inaugurale de Gérard Berry 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.

    Voir la vidéo.

    Computer Science Unplugged – L’informatique sans ordinateur

    Tim Bell, Ian H. Witten et Mike Fellows

    couverture

    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

    couverture

    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 l’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

    couverture

    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)

    couverture

    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)

    couverture

    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)

    couverture

    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)

    couverture

    L’informaticien peut ne pas connaître les résultats de la logique formelle du 20e siècle, ni en avoir besoin. Pourtant, la logique du 20e 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.

    Olivier Ridoux

    Histoire d’algorithmes : du caillou à la puce

    Jean-Luc Chabert et al. (Belin 1994)

    couverture

    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.

    Olivier Ridoux

    Comment distinguer le simple du complexe ?
    Complexité de Kolmogorov et profondeur logique de Bennett

    Jean-Paul Delahaye

    Exposé de Jean-Paul delahaye au LIG

    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é.

    Voir la vidéo.

    Complexité et décidabilité

    Patrick Dehornoy (Springer 1993)

    couverture

    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

    couverture

    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.

    Voir la présentation.

    Newsletter

    Recevez chaque mois une sélection d'articles

    Niveau de lecture

    Aidez-nous à évaluer le niveau de lecture de ce document.

    Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (Il ne sera pas publié).

    Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !

    Découvrez le(s) dossier(s) associé(s) à cet article :

    Dossier

    Ressources pour le lycée

    DossierCulture & Société

    Lire et voir