Die einflussreichsten Papers in der Geschichte der Informatik

 (terriblesoftware.org)
6 Punkte von GN⁺ 2025-01-24 | 1 Kommentare | Auf WhatsApp teilen
  • Sieben Informatik-Papers aus den Jahren 1936 bis 1998 prägten die zentralen Schichten des modernen Computings: Berechenbarkeit, Informationstheorie, Datenbanken, Komplexität, Internet, Web und Suche
  • Alan Turings Paper von 1936 wurde mit der Turing Machine zum Ausgangspunkt moderner Berechnungsmodelle, indem es unterscheidet, was Maschinen prinzipiell berechnen können und was nicht
  • Claude Shannon, Edgar F. Codd und Stephen A. Cook schufen mit Informationsmessung und Fehlerkorrektur, dem relationalen Datenmodell sowie NP-completeness und SAT jeweils eine gemeinsame Sprache für Kommunikation, Daten und Problemschwierigkeit
  • Die Papers von Vinton G. Cerf und Robert E. Kahn, Tim Berners-Lee sowie Sergey Brin und Larry Page strukturierten mit TCP/IP, dem World Wide Web und PageRank die Vernetzung von Netzwerken, Dokumenten und Websuche
  • Betrachtet man zusätzlich die Bonusliste mit Lisp, strukturierter Programmierung, logischen Uhren, Softwarekomplexität und Transformer, wird das Verständnis von Grundkonzepten zu einem langlebigeren Wettbewerbsvorteil als neue Tools

Auswahlkriterien und Gesamtverlauf

  • Die Liste ist kein absolutes Ranking, sondern eine subjektive Auswahl nach der Wirkung, die diese Arbeiten auf die heutige Welt hatten
  • Die sieben Papers sind chronologisch geordnet und zeigen eine Entwicklung von Berechnung über Kommunikation, Datenspeicherung, Berechnungsschwierigkeit, Networking, Web bis zur Suche
  • Auch wenn ständig neue Sprachen, KI-Fortschritte, Quantensprünge und JavaScript-Frameworks auftauchen, bleiben die von diesen Papers geschaffenen Konzepte die Grundlage des modernen Computings

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

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

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

  • Edgar F. Codd schlug das relationale Modell vor, um große Datenmengen zu speichern und abzufragen
  • Die Kernidee besteht darin, Daten in Tabellen zu speichern und mit logischen Operationen zu manipulieren
  • Dieses Design führte zu SQL und relationalen Datenbanken und bildet die Grundlage für Banken, Retail-Websites und Enterprise-Systeme
  • Selbst im NoSQL-Zeitalter sind Konzepte der Datenorganisation wie Tabellen, Schemata und Konsistenz mit Codds Modell verbunden
  • Weiterführende Links:

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

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

  • Das Paper von Vinton G. Cerf und Robert E. Kahn legte die Grundlage für TCP, um voneinander isolierte Netzwerke miteinander zu verbinden
  • Es entstand eine universelle Sprache, mit der unterschiedliche Netzwerke kommunizieren können; Daten werden in kleine Pakete zerlegt, nehmen verschiedene Wege und werden am Ziel wieder zusammengesetzt
  • Diese Flexibilität machte globale Vernetzung möglich, ohne ein einziges riesiges Einheitsnetz aufbauen zu müssen
  • Aktivitäten wie Web-Browsing, E-Mail-Versand oder das Einloggen auf einer Banking-Website beruhen darauf, dass TCP/IP bits zuverlässig transportiert
  • Einige Echtzeitanwendungen nutzen UDP, doch die Kernidee des IP-basierten Networkings von Cerf und Kahn verbindet Geräte unter einem globalen Netzwerk
  • Weiterführende Links:

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

  • Nachdem Maschinen leichter miteinander kommunizieren konnten, schlug Tim Berners-Lee die Richtung für ein World Wide Web vor, das Menschen einfacher nutzen können
  • Die Kernidee ist ein globales Hypertext-System mit Hyperlinks, URLs und HTTP
  • Dokumente weltweit waren dadurch nicht länger isoliert, sondern miteinander verknüpft, und das Internet wurde zu einer Form, die nicht nur Wissenschaftler, sondern auch normale Nutzer erkunden konnten
  • Die Keime für Web-Erfahrungen wie Social Media, Online-Shopping oder Blogposts, die man um 3 Uhr morgens liest, finden sich in diesem Vorschlag
  • Weiterführende Links:

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

  • Sergey Brin und Larry Page entwickelten für das Web mit explodierender Zahl von Links und Seiten einen Ansatz auf Basis von Linkanalyse, aus dem die Google-Suchmaschine entstand
  • Die Kernidee PageRank betrachtet Links nicht nur als Faktor in einer Keyword-Berechnung, sondern als Vertrauensvotum
  • Dieser Ansatz verbesserte relevante Suchergebnisse erheblich und machte das Web zu einem durchsuchbaren Raum
  • Die Erfahrung, eine Frage bei Google einzugeben und sofort eine Antwort zu erhalten, basiert auf PageRank und vielen späteren Innovationen
  • PageRank definierte die Art der Online-Informationssuche neu und leitete eine neue Ära datengetriebener Technologien wie Werbung, Analytics und Machine Learning ein
  • Weiterführende Links:

Fünf Papers, die es fast in den Hauptteil geschafft hätten

  • “Recursive Functions of Symbolic Expressions and Their Computation by Machine” (1960) – John McCarthy
    • Führte Lisp und einen funktionalen Programmierstil ein, der auch in modernen Sprachen und Frameworks weiterlebt
  • “Go To Statement Considered Harmful” (1968) – Edsger Dijkstra
    • Kritisierte, dass goto unübersichtlichen, unstrukturierten Code erzeugt, und löste die Revolution der strukturierten Programmierung aus
  • “Time, Clocks, and the Ordering of Events in a Distributed System” (1978) – Leslie Lamport
    • In verteilten Systemen lassen sich reale Uhren nicht perfekt synchronisieren, weshalb logische Uhren nötig sind
  • “No Silver Bullet—Essence and Accident in Software Engineering” (1986) – Fred Brooks
    • Vertrat die Ansicht, dass es keine einzelne magische Methode gibt, die die wesentliche Komplexität der Softwareentwicklung löst
  • “Attention Is All You Need” (2017) – Vaswani et al.
    • Stellte die Transformer-Architektur vor, die hinter GPT und mehreren bekannten KI-Modellen steht

Die Wirkung grundlegender Konzepte

  • Heute erscheinen ständig neue Sprachen, KI-Innovationen, Quantensprünge und wöchentlich neue JavaScript-Frameworks
  • Wer nicht versteht, woher Kernkonzepte wie Datenstrukturen, Algorithmen und das Web stammen, häuft nur immer neue Tools an
  • Diese sieben Papers und die Bonusarbeiten führen die Ideen vor Augen, die zum Kernfundament des modernen Computings wurden

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-01-24
Meinungen auf Hacker News

  • Communicating Sequential Processes (Hoare), The Next 700 Programming Languages (Landin), As We May Think (Bush) und Can Programming Be Liberated from the von Neumann Style (Backus) wären ebenfalls aufnahmefähig.
    Und diese Vorlesung sieht auch gut aus: https://canvas.harvard.edu/courses/34992/assignments/syllabu...
    „Diese Lehrveranstaltung behandelt Arbeiten, die jeder Informatiker von den 1930er-Jahren bis heute gelesen haben sollte. Sie ist als umfassende Erfahrung gedacht, die fortgeschrittenen Informatikstudierenden hilft, das gesamte Fachgebiet zu überblicken; nicht als bloßer Überblick, sondern so, dass sie den kreativen Prozess noch einmal nachvollziehen. Ziel ist es, Studierenden, die bereits über einen gewissen Hintergrund verfügen, die gesamte Entwicklung der Informatik in schneller Folge vorzuführen und ihnen so eine integrierte Sicht auf das Fach zu vermitteln.“

    • Um die Vorlesung anzusehen, braucht man offenbar einen Harvard-Account.

  • Diese Liste wirkt wie eine etwas seltsame Mischung. Es ist unklar, ob sie Arbeiten auswählt, die die Informatik, also die Berechnungstheorie, beeinflusst haben, Arbeiten, die Technologie beeinflusst haben, oder ob sie einfach „alles rund um Computer“ als Informatik bezeichnet.
    Turings Arbeit ist eine Grundlage der Informatik, aber ich frage mich, ob sich die Technologie anders entwickelt hätte, wenn es sie nicht gegeben hätte. Die meisten Software Engineers haben sie nie gelesen. Umgekehrt sind IP-Standards zwar technologische Grundpfeiler, enthalten aber kaum wissenschaftlichen Inhalt und sind eher vergleichsweise einfache Protokollspezifikationen, die man kennen muss, wenn man im Umfeld von Netzwerken arbeitet.

    • Dass das PageRank-Paper in einer kurzen Liste neben Turings und Shannons Grundlagenarbeiten zu Berechenbarkeit und Informationstheorie steht, wirkt irgendwie unpassend.
      „On Computable Numbers, with an Application to the Entscheidungsproblem“ ist inzwischen fast 90 Jahre alt, aber heute noch genauso wahr und gültig wie damals. Ob PageRank heute noch so relevant ist wie 1998, geschweige denn in 50 Jahren, weiß ich nicht.

  • Eine gute Liste von Papers. Von den 7 Arbeiten auf der Liste habe ich 5 gelesen; die, die ich noch nicht gelesen habe, sind das Paper von Cerf und Kahn sowie das von Berners-Lee.
    Turings Berechenbarkeits-Paper war besonders schwer nachzuvollziehen, weil er allerlei Objekte mit gotischen Großbuchstaben benannt hat und diese Buchstaben alle ziemlich ähnlich aussahen. Ich brauchte Begleitmaterial, um das Paper lesen zu können; heute würde ich empfehlen, es zusammen mit Charles Petzolds kommentierendem Buch zu lesen: https://www.amazon.com/Annotated-Turing-Through-Historic-Com...
    Cooks NP-Vollständigkeits-Paper war ebenfalls schwierig und brauchte, wie Turings Paper, Begleitmaterial. Heute würde ich empfehlen, zuerst ein Einführungsbuch zur Komplexitätstheorie zu lesen, das Cooks Beweis nachvollzieht.
    Shannons Paper ist klar und wunderschön geschrieben, fast wie ein Kunstwerk, aber ganz sicher keine leichte Lektüre.
    Das Paper von Brin und Page sowie Codds Paper waren meiner Erinnerung nach nicht besonders schwierig, aber um die Arbeit von Brin und Page zu verstehen, braucht man gewisse Kenntnisse in linearer Algebra.

    • Ich weiß nicht, wo im Paper von Brin und Page lineare Algebra nötig sein soll. Das Wort „Eigenvektor“ kommt einmal vor, aber nur als beiläufige Erwähnung.
      Der „einfache iterative Algorithmus“ ist ein Verfahren, um den Fixpunkt einer beliebigen Kontraktion zu finden, ob linear oder nicht. Dass dieser auch ein Eigenvektor ist, ist eher hinderlich; jemand, der sich auskennt, würde dafür keine Gauß-Elimination verwenden.
    • Wenn man an die ursprüngliche .tex-Datei kommt, hilft es, GPT zu bitten, die Variablennamen lesbarer zu machen, also durch Namen zu ersetzen, die länger als ein einzelner Buchstabe sind.

  • Wenn man meint, Shannons A Mathematical Theory of Communication sei sein grundlegendster Beitrag zur Informatik, dann hat man seine zehn Jahre zuvor geschriebene Masterarbeit noch nicht gesehen.
    https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_a...
    Darin zeigte er, dass sich mit den Schaltelementen von Schaltungen, also Transistoren, boolesche Logik definieren lässt.
    Das soll natürlich nicht die Bedeutung seiner Leistung schmälern, mit der er die Grundlage der gesamten Informationstheorie geschaffen hat.

  • Die Beschreibung „Er zeigte, dass alles, was berechenbar ist, im Prinzip von einer Maschine verarbeitet werden kann, und entwarf die hypothetische ‚Turing Machine‘“ ist nicht das, was Turing bewiesen hat.
    Was er in diesem Paper bewiesen hat, ist, dass es Probleme gibt, die sich nicht mit einer Turing Machine lösen lassen, und dass sie daher vermutlich von keiner Maschine lösbar sind. Genau darum geht es beim Entscheidungsproblem im Titel.
    Worauf der ursprüngliche Text hinauswill, ist die sogenannte Church-Turing-These, die im wörtlichen Sinn eher eine These ist. Sie lässt sich nicht wirklich beweisen, aber da seit fast 100 Jahren kein Berechnungsmodell gefunden wurde, das mächtiger ist als die Turing Machine, gibt es sehr starke Gründe, daran zu glauben.

    • In den letzten 100 Jahren hat sich die Vorstellung davon, wo künstliche Intelligenz steht, eher in die völlig entgegengesetzte Richtung entwickelt.
      Statt eine Maschine zu bauen, die alle bekannten Wahrheiten enthält, läuft die moderne maschinenbasierte Suche nach künstlicher Intelligenz im Großen und Ganzen eher darauf hinaus, menschliche Kommentare zu durchforsten und eine kuratierte Feuilleton-Maschine zu erzeugen; das unterscheidet sich vom leibnizschen axiomatischen Ansatz.
    • Die Aussage „Niemand hat ein Berechnungsmodell gefunden, das mächtiger ist als die Turing Machine“ halte ich für falsch. Eine Turing Machine kann Nichtdeterminismus nicht ausführen, das Actor-Modell hingegen schon.

  • Gute Arbeit. Ich habe privat etwas Ähnliches gemacht und empfehle noch ein paar weitere Beiträge
    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)
    Backpropagation: Learning representations by back-propagating errors (1986)
    Hoare-Logik: An Axiomatic Basis for Computer Programming (1969)

  • Wo ist Dennis Ritchies berüchtigtes Evolution of Unix time-sharing systems geblieben?
    https://www.bell-labs.com/usr/dmr/www/cacm.pdf

  • Da alle ihre eigenen Empfehlungen beisteuern, füge ich auch noch eine hinzu: Cook hat zwar als Erster NP-Vollständigkeit eingeführt, aber Karps Paper, das 21 Probleme vorstellte, die sich polynomialzeitlich auf 3SAT reduzieren lassen, war ebenfalls ein enormer Grundstein, der ein breiteres Interesse an Cooks Theorie auslöste
    https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_proble...

  • Fehlt New Directions in Cryptography (1976) von Diffie und Hellman?

  • Es sind zwar keine wissenschaftlichen Paper, aber Marc Andreessens Why Software Is Eating the World und Amazons erster Aktionärsbrief von 1997 sind besonders erwähnenswert
    „Unternehmen in jeder Branche müssen davon ausgehen, dass die Software-Revolution kommt. Das gilt auch für Branchen, die heute bereits softwarebasiert sind“
    https://a16z.com/why-software-is-eating-the-world/
    „Aber dies ist Day 1 für das Internet, und wenn wir gut umsetzen, ist es auch Day 1 für Amazon.com“
    https://www.aboutamazon.com/news/company-news/amazons-origin...