Les articles les plus influents de l’histoire de l’informatique

 (terriblesoftware.org)
6 points par GN⁺ 2025-01-24 | 1 commentaires | Partager sur WhatsApp
  • De 1936 à 1998, sept articles d’informatique ont façonné les couches fondamentales de l’informatique moderne : calculabilité, théorie de l’information, bases de données, complexité, Internet, Web et recherche
  • L’article d’Alan Turing de 1936 pose le point de départ du modèle de calcul moderne en distinguant, avec la machine de Turing, ce qu’une machine peut ou ne peut pas calculer en principe
  • Claude Shannon, Edgar F. Codd et Stephen A. Cook ont chacun créé un langage commun pour parler de communication, de données et de difficulté des problèmes via la mesure de l’information et la correction d’erreurs, le modèle relationnel de données, ainsi que la NP-complétude et SAT
  • Les articles de Vinton G. Cerf et Robert E. Kahn, Tim Berners-Lee, Sergey Brin et Larry Page ont structuré la connectivité des réseaux, la liaison entre documents et la recherche sur le Web avec TCP/IP, le World Wide Web et PageRank
  • Si l’on ajoute à la liste bonus Lisp, la programmation structurée, les horloges logiques, la complexité logicielle et les Transformers, on voit que comprendre les concepts fondamentaux reste un avantage plus durable que de simplement suivre les nouveaux outils

Critères de sélection et vue d’ensemble

  • Cette liste n’est pas un classement absolu, mais un choix subjectif fondé sur leur influence sur le monde actuel
  • Les sept articles sont classés par ordre chronologique et dessinent une trajectoire allant du calcul à la communication, au stockage des données, à la difficulté du calcul, au réseau, au Web puis à la recherche
  • Même si de nouveaux langages, des avancées en IA, des percées quantiques et des frameworks JavaScript continuent d’apparaître, les concepts introduits par ces articles restent au socle de l’informatique moderne

1. “On Computable Numbers, with an Application to the Entscheidungsproblem” (1936)

  • Dans les années 1930, Alan Turing a posé les bases de ce qu’un ordinateur peut théoriquement faire grâce à la machine de Turing
  • Le modèle central se compose d’un ruban, d’une tête de lecture/écriture et d’un ensemble fini d’états
  • Ce modèle définit quels problèmes peuvent être résolus au sens mécanique, et lesquels ne peuvent pas l’être
  • Tous les langages de programmation et tout le code fonctionnent à l’intérieur du cadre défini par Turing, et même lorsqu’on parle d’informatique quantique, on se réfère encore aux limites qu’il a posées
  • Pour aller plus loin :

2. “A Mathematical Theory of Communication” (1948)

3. “A Relational Model of Data for Large Shared Data Banks” (1970)

  • Edgar F. Codd a proposé le modèle relationnel pour stocker et interroger de grands volumes de données
  • L’idée centrale consiste à stocker les données dans des tables et à les manipuler au moyen d’opérations logiques
  • Cette conception a conduit à SQL et à toute la famille des bases de données relationnelles, qui soutiennent les banques, les sites e-commerce et les systèmes d’entreprise
  • Même à l’ère du NoSQL, des concepts d’organisation des données comme les tables, les schémas ou la cohérence restent liés au modèle de Codd
  • Pour aller plus loin :

4. “The Complexity of Theorem-Proving Procedures” (1971)

5. “A Protocol for Packet Network Intercommunication” (1974)

  • L’article de Vinton G. Cerf et Robert E. Kahn pose les bases de TCP pour relier entre eux des réseaux isolés
  • Il a fourni un langage universel permettant à des réseaux différents de communiquer, les données étant découpées en petits paquets, acheminées par plusieurs chemins puis réassemblées à l’arrivée
  • Cette souplesse a rendu possible une connectivité mondiale sans avoir besoin d’un unique réseau géant centralisé
  • La navigation Web, l’envoi d’e-mails ou la connexion à un site bancaire reposent sur TCP/IP pour transporter les bits de manière fiable
  • Certaines applications en temps réel utilisent UDP, mais l’idée centrale du réseau fondé sur IP proposée par Cerf et Kahn est de réunir les appareils au sein d’un même réseau global
  • Pour aller plus loin :

6. “Information Management: A Proposal” (1989)

  • Une fois la communication entre machines facilitée, Tim Berners-Lee a proposé une direction pour un World Wide Web plus facile à utiliser pour les humains
  • L’idée centrale est un système hypertexte mondial reposant sur les hyperliens, les URL et HTTP
  • Les documents du monde entier ont cessé d’être isolés et ont commencé à se relier entre eux, faisant d’Internet un espace navigable non seulement pour les scientifiques, mais aussi pour le grand public
  • Les usages du Web comme les réseaux sociaux, le shopping en ligne ou les billets de blog lus à 3 heures du matin trouvent ici leur point de départ
  • Pour aller plus loin :

7. “The Anatomy of a Large-Scale Hypertextual Web Search Engine” (1998)

  • Sergey Brin et Larry Page ont conçu une approche fondée sur la link analysis pour traiter un Web où les liens et les pages explosaient en nombre, approche qui a ensuite évolué vers le moteur de recherche Google
  • L’idée clé, PageRank, considère les liens non comme de simples éléments de calcul par mots-clés, mais comme des votes de confiance
  • Cette méthode a fortement amélioré la pertinence des résultats et transformé le Web en un espace réellement explorable par la recherche
  • L’expérience consistant à poser une question à Google et à obtenir immédiatement une réponse repose sur PageRank et sur les nombreuses innovations qui ont suivi
  • PageRank a redéfini la manière d’explorer l’information en ligne et a contribué à ouvrir une nouvelle ère des technologies fondées sur les données, de la publicité à l’analytics en passant par le machine learning
  • Pour aller plus loin :

5 articles qui ont failli être inclus

  • “Recursive Functions of Symbolic Expressions and Their Computation by Machine” (1960) – John McCarthy
    • A introduit Lisp et le style de programmation fonctionnelle, toujours présents dans les langages et frameworks modernes
  • “Go To Statement Considered Harmful” (1968) – Edsger Dijkstra
    • Critique goto en expliquant qu’il produit un code désordonné et non structuré, et déclenche la révolution de la programmation structurée
  • “Time, Clocks, and the Ordering of Events in a Distributed System” (1978) – Leslie Lamport
    • Dans les systèmes distribués, les horloges réelles ne peuvent pas être parfaitement synchronisées, d’où la nécessité des horloges logiques
  • “No Silver Bullet—Essence and Accident in Software Engineering” (1986) – Fred Brooks
    • Sostient qu’il n’existe pas de méthode magique unique capable de résoudre la complexité intrinsèque du développement logiciel
  • “Attention Is All You Need” (2017) – Vaswani et al.
    • Présente l’architecture Transformer à l’origine de GPT et de nombreux modèles d’IA célèbres

L’impact durable des concepts fondamentaux

  • Aujourd’hui, de nouveaux langages, des innovations en IA, des percées quantiques et des frameworks JavaScript qui surgissent chaque semaine continuent d’affluer
  • Sans comprendre d’où viennent des concepts clés comme les structures de données, les algorithmes ou le Web, on se retrouve à empiler sans fin de nouveaux outils
  • Ces sept articles, ainsi que les articles bonus, permettent de revisiter les idées qui sont devenues les fondations essentielles de l’informatique moderne

À lire aussi

1 commentaires

 
GN⁺ 2025-01-24
Avis sur Hacker News

  • Communicating Sequential Processes (Hoare), The Next 700 Programming Languages (Landin), As We May Think (Bush) et Can Programming Be Liberated from the von Neumann Style (Backus) mériteraient aussi d’y figurer.
    Et ce cours a aussi l’air intéressant : https://canvas.harvard.edu/courses/34992/assignments/syllabu...
    « Ce cours couvre les articles que tout informaticien aurait dû lire, des années 1930 à aujourd’hui. C’est une expérience de synthèse destinée à aider les étudiants avancés en informatique à embrasser l’ensemble du domaine ; il ne s’agit pas d’un simple panorama, mais d’une façon de revivre le processus de création. En rejouant à grande vitesse toute l’évolution de l’informatique pour des étudiants ayant déjà un certain bagage, l’objectif est de leur permettre de se construire une vision unifiée du domaine. »

    • Il semble qu’il faille un compte Harvard pour accéder au cours.

  • Cette liste donne l’impression d’un assemblage un peu étrange. On ne sait pas trop s’il s’agit de choisir des articles ayant influencé l’informatique, c’est-à-dire la théorie du calcul, des articles ayant influencé la technologie, ou si l’on appelle simplement « informatique » tout ce qui touche de près ou de loin aux ordinateurs.
    L’article de Turing est un fondement de l’informatique, mais on peut se demander si la technologie aurait évolué différemment sans lui. La plupart des ingénieurs logiciel ne l’ont jamais lu. À l’inverse, le standard IP est une pierre angulaire technique, mais il contient très peu de science ; il s’apparente plutôt à une spécification de protocole relativement simple qu’il faut connaître si l’on travaille autour des réseaux.

    • Voir l’article sur PageRank placé, dans une liste aussi courte, à côté des travaux fondamentaux de Turing et Shannon sur la calculabilité et la théorie de l’information paraît quelque peu dissonant.
      « On Computable Numbers, with an Application to the Entscheidungsproblem » a aujourd’hui presque 90 ans, mais il est toujours aussi vrai et pertinent qu’à l’époque. Je ne suis pas sûr que PageRank soit encore aussi pertinent qu’en 1998, et encore moins qu’il le soit dans 50 ans.

  • C’est une bonne liste d’articles. J’en ai lu 5 sur les 7 ; ceux que je n’ai pas encore lus sont celui de Cerf et Kahn, et celui de Berners-Lee.
    L’article de Turing sur la calculabilité était particulièrement difficile à suivre, notamment parce qu’il nomme toutes sortes d’objets avec des majuscules gothiques, et que toutes ces lettres se ressemblent. J’ai dû consulter des ressources complémentaires pour parvenir à le lire ; aujourd’hui, je recommanderais de le lire avec le livre explicatif de Charles Petzold : https://www.amazon.com/Annotated-Turing-Through-Historic-Com...
    L’article de Cook sur la NP-complétude était lui aussi difficile, et, comme celui de Turing, nécessitait des supports complémentaires. Aujourd’hui, je recommanderais plutôt de commencer par un manuel d’introduction à la complexité algorithmique qui suive la preuve de Cook.
    L’article de Shannon est comme une œuvre d’art, écrite de manière claire et magnifique, mais ce n’est absolument pas une lecture légère.
    Les articles de Brin et Page, ainsi que celui de Codd, ne m’ont pas semblé particulièrement difficiles dans mon souvenir, mais comprendre le travail de Brin et Page demande un certain niveau d’algèbre linéaire.

    • Je ne vois pas où l’algèbre linéaire est nécessaire dans l’article de Brin et Page. Le terme « vecteur propre » apparaît une fois, mais c’est une mention accessoire.
      L’« algorithme itératif simple » est une manière de trouver un point fixe d’une contraction arbitraire, linéaire ou non. Le fait que ce soit aussi un vecteur propre est plutôt une distraction, et quelqu’un qui s’y connaît n’utiliserait pas l’élimination de Gauss.
    • Si l’on peut obtenir le fichier source .tex, demander à GPT de rendre les noms de variables plus lisibles, avec des noms plus longs qu’une seule lettre, peut aider.

  • Si vous pensez que A Mathematical Theory of Communication de Shannon est sa contribution la plus fondamentale à l’informatique, c’est que vous n’avez pas encore vu le mémoire de master qu’il a écrit dix ans plus tôt.
    https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_a...
    Il y montrait qu’il était possible de définir la logique booléenne à l’aide des éléments de commutation des circuits, c’est-à-dire des transistors.
    Bien sûr, cela ne vise pas à minimiser l’importance de son œuvre qui a posé les bases de toute la théorie de l’information.

  • Dire qu’il « a montré que si quelque chose est calculable, alors une machine peut en principe le traiter, et a esquissé l’hypothétique “Turing Machine” » ne correspond pas à ce que Turing a démontré.
    Ce qu’il a démontré dans cet article, c’est qu’il existe des problèmes qu’une Turing Machine ne peut pas résoudre, et donc probablement qu’aucune machine ne peut résoudre. C’est précisément l’Entscheidungsproblem du titre, c’est-à-dire le problème de la décision.
    Ce à quoi le texte original fait référence est ce qu’on appelle la thèse de Church-Turing, qui est littéralement proche d’une thèse. On ne peut pas vraiment la prouver, mais le fait que, depuis près de 100 ans, on n’ait trouvé aucun système de calcul plus puissant qu’une Turing Machine donne de très fortes raisons d’y croire.

    • Au cours des 100 dernières années, la réflexion sur ce qu’est l’intelligence artificielle est plutôt partie dans la direction exactement opposée.
      Au lieu de construire une machine contenant toutes les vérités connues, la recherche moderne d’intelligence artificielle fondée sur les machines s’est largement rapprochée de la construction de machines à feuilletons compilant des commentaires humains, ce qui diffère de l’approche axiomatique à la Leibniz.
    • Je pense que l’affirmation selon laquelle « personne n’a trouvé de système de calcul plus puissant qu’une Turing Machine » est fausse. Une Turing Machine ne peut pas effectuer de non-déterminisme, alors que le modèle d’acteurs le peut.

  • Beau travail. Comme je faisais quelque chose de similaire de mon côté, je recommande quelques articles de plus
    RSA : A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (1978)
    PageRank : The PageRank Citation Ranking: Bringing Order to the Web (1999)
    MapReduce : MapReduce: simplified data processing on large clusters (2008)
    Bitcoin : Bitcoin: A Peer-to-Peer Electronic Cash System (2008)
    rétropropagation : Learning representations by back-propagating errors (1986)
    logique de Hoare : An Axiomatic Basis for Computer Programming (1969)

  • Où est passé le célèbre Evolution of Unix time-sharing systems de Dennis Ritchie ?
    https://www.bell-labs.com/usr/dmr/www/cacm.pdf

  • Puisque tout le monde ajoute ses recommandations, j’en ajoute une aussi : même si Cook a introduit le premier la NP-complétude, l’article de Karp présentant 21 problèmes réductibles en temps polynomial à 3SAT a aussi été une énorme pierre angulaire, en suscitant un intérêt plus large pour la théorie de Cook
    https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_proble...

  • New Directions in Cryptography (1976) de Diffie et Hellman a-t-il été oublié ?

  • Ce ne sont pas des articles de recherche, mais Why Software Is Eating the World de Marc Andreessen et la première lettre d’Amazon aux actionnaires, en 1997, méritent une mention spéciale
    « Les entreprises de tous les secteurs doivent partir du principe qu’une révolution logicielle arrive. Cela inclut les secteurs qui reposent déjà aujourd’hui sur le logiciel »
    https://a16z.com/why-software-is-eating-the-world/
    « Mais c’est le Day 1 d’Internet, et si nous exécutons bien, c’est aussi le Day 1 pour Amazon.com »
    https://www.aboutamazon.com/news/company-news/amazons-origin...