Wir stellen klassische Algorithmen für zwei grundlegende Probleme vor und untersuchen sie im Zusammenhang mit realistischen Anwendungen. Unsere Botschaft ist, dass effiziente Algorithmen (in diesem Fall binäre Suche und Mergesort) ein Schlüsselelement sind, wenn es darum geht, Rechenprobleme mit skalierbaren Lösungen anzugehen, die große Instanzen bewältigen können, und dass die wissenschaftliche Methode für die Bewertung der Effektivität solcher Lösungen unerlässlich ist.

Unsere Einführung in Datenstrukturen ist ein sorgfältiger Blick auf die grundlegenden Abstraktionen von Stacks und Warteschlangen, einschließlich Leistungsspezifikationen. Anschließend stellen wir das Konzept der verknüpften Strukturen vor und konzentrieren uns auf ihren Nutzen bei der Entwicklung einfacher, sicherer, klarer und effizienter Implementierungen von Stapeln und Warteschlangen.

Die Abstraktion der Symboltabelle ist eines der wichtigsten und nützlichsten Werkzeuge für Programmierer, was wir in dieser Vorlesung anhand mehrerer Beispiele veranschaulichen. In Erweiterung des wissenschaftlichen Ansatzes der beiden vorangegangenen Vorlesungen stellen wir binäre Suchbäume vor und untersuchen sie, eine klassische Datenstruktur, die effiziente Implementierungen dieser Abstraktion unterstützt.

Die Rechentheorie hilft uns dabei, grundlegende Fragen über die Natur des Rechnens zu beantworten und gleichzeitig die Art und Weise, wie wir mit dem Computer interagieren, besser zu verstehen. In dieser Vorlesung führen wir in formale Sprachen und abstrakte Maschinen ein und konzentrieren uns dabei auf einfache Modelle, die in der Praxis tatsächlich von großem Nutzen sind.

1936 veröffentlichte Alan Turing eine Arbeit, die weithin als eine der wichtigsten wissenschaftlichen Arbeiten des 20. Jahrhunderts gilt. Dieser Vortrag ist den beiden weitreichenden zentralen Ideen des Papiers gewidmet: Alle Rechengeräte haben die gleiche Rechenleistung und es gibt Grenzen für diese Leistung.

Mit der Ausweitung der Computeranwendungen erkannten Informatiker und Mathematiker, dass eine Verfeinerung der Ideen von Turing erforderlich ist. Welche Rechenprobleme können wir mit den begrenzten Ressourcen, die in der realen Welt unausweichlich sind, lösen? Wie in diesem Vortrag beschrieben, bleibt diese Frage im Grunde genommen unbeantwortet.

Jeder Programmierer muss die grundlegenden Eigenschaften des verwendeten Computerprozessors verstehen. Glücklicherweise hat sich das grundlegende Design von Computerprozessoren seit den 1960er Jahren kaum verändert. In dieser Vorlesung geben wir Ihnen einen Einblick in die Funktionsweise Ihres Java-Codes, indem wir einen imaginären Computer vorstellen, der sowohl den Minicomputern der 1960er Jahre als auch den Mikroprozessorchips in den heutigen Laptops und mobilen Geräten ähnelt.

Im Anschluss an die Beschreibung des Prozessordesigns und der Low-Level-Programmierung geben wir einen Überblick über den Kontext, der bis in die 1950er Jahre zurückreicht, und erörtern die zukünftigen Auswirkungen der von-Neumann-Maschine, bei der Programme und Daten im selben Speicher gehalten werden. Wir befassen uns eingehend mit der Idee, dass wir neue Computer entwickeln, indem wir sie auf alten Computern simulieren - etwas, das nach Turings Theorie immer funktionieren wird.

Ausgehend von einigen einfachen Abstraktionen (Drähte, die Ein/Aus-Werte übertragen können, und Schalter, die die von den Drähten übertragenen Werte steuern können), befassen wir uns in dieser Vorlesung mit dem Entwurf von Schaltungen, die Computerprozessoren implementieren. Wir betrachten Gatter, die einfache logische Funktionen implementieren, und Komponenten für höhere Funktionen, wie z.B. die Addition. Die Vorlesung gipfelt in einer vollständigen Schaltung für eine arithmetisch-logische Einheit.

In dieser Vorlesung geben wir den letzten Teil unserer Antwort auf die Frage "Wie funktioniert ein Computer?", indem wir einen kompletten Schaltkreis für einen Computerprozessor entwickeln, bei dem jeder Schalter und jedes Kabel sichtbar ist. Diese Schaltung ist zwar vom Umfang her ganz anders, weist aber vom Design her viele der gleichen Merkmale auf wie die Schaltungen in Ihrem Computer und Ihrem Telefon.