Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Theoretische Informatik: Epistemologie und RAM-Modelle
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 40 Zeilen
- Willkommen zu dieser Analyse der theoretischen Informatik. Wir untersuchen heute die epistemologischen Grundlagen, die es uns ermöglichen,
- komplexe physikalische Prozesse in abstrakte mathematische Modelle zu übersetzen. Im Zentrum steht das Random Access Machine Modell Kurz RAM und die
- Frage, warum wir elementaren Operationen Kosten von O1 zuweisen, obwohl die physikalische Realität viel komplexer ist. Beginnen wir mit dem fundamentalen
- Dilemma der Informatik. Wie generieren wir verlässliches Wissen über künstliche Systeme, die zwar von Menschen geschaffen, aber oft undurchschaubar
- komplex sind? Anders als die Physik, die eine bereits existierende Natur beschreibt, konstruiert die Informatik ihre Objekte, Algorithmen und
- Datenstrukturen selbst. Abstraktion ist hierbei kein bloßes Weglassen, sondern eine normative Entscheidung. Wir bestimmen aktiv, was als relevantes
- Detail zählt und was wir als bloßes Rauschen der Implementierung ignorieren. Dennoch existieren diese Abstraktionen nicht im luftleeren Raum. Wir sprechen
- von einer sogenannten Implementierungsspur. Ein abstrakter Stapelspeicher mag mathematisch rein durch das Lifoprinzip
- definiert sein, aber in der Realität verbraucht er Speicherzellen und Energie. Das RAM Modell versucht diese Spur zu minimieren, kann sie aber
- niemals vollständig tilgen. Warum tun wir das? Das Ziel ist Inviarianz. Wir wollen sagen können, dass ein Algorithmus effizient ist, ohne zu
- wissen, ob er auf einer Intel CPU oder einem Armprozessor läuft. Die Zuweisung von Einheitskosten ist ein methodologischer Trick, um zeitlose
- mathematische Wahrheiten über Prozesse zu formulieren, die auf zeitgebundenen Maschinen ablaufen. Um das abstrakte Modell zu verstehen, müssen wir sein
- physisches Vorbild betrachten, die von Neumann Architektur, das Fundament fast aller modernen Computer. John von Neumann etablierte 1945
- das Konzept des Stort Program Computers. Die Schlüsselaspekte sind ein gemeinsamer Speicher für Programm und Daten, was selbstmodifizierenden Code
- ermöglicht, eine strikt sequentielle Abarbeitung durch einen Befehlszähler und der namensgebende wahlfreie Zugriff, der das mühsame Spulen von Bändern wie
- bei der Touringmaschine überflüssig macht. In der Theorie unterscheiden wir oft zwischen der RAM und der Rasp. Während die Rasp die von Neumannchektur
- exakter abbildet, da das Programm imselben Speicher liegt wie die Daten, hat sich die RAM durchgesetzt. Beide sind polynomiell äquivalent, aber die
- RAM ist einfacher zu analysieren, da wir selten selbstmodifizierenden Code betrachten. Formalisiert durch Cook und Rhow besteht eine RAM aus vier
- Komponenten, einem unendlichen Speicher aus Registern, einem Befehlszähler, einem Akkumulator für Rechenoperationen und dem Programm selbst. Ein Zustand der
- Maschine ist definiert durch das Tupel aus Befehlszähler und Speicherinhalt. Die Atome der Komplexität sind die elementaren Operationen. Dazu gehören
- Datentransfers wie Load und Store, Arithmetik, logische Operationen und Kontrollflussbefehle wie Jump. All diesen Operationen weisen wir
- konventionsgemäß Kosten von O von 1 zu. Besonders hervorzuheben ist die indirekte Adressierung hier als Load Stern K dargestellt. Sie nutzt den
- Inhalt eines Registers als Adresse für den nächsten Zugriff. Ohne diese Operation wäre die effiziente Simulation von Zeigern, Listen und Bäumen in
- konstanter Zeit unmöglich. Sie ist der qualitative Unterschied zur Touringmaschine. Kommen wir nun zum Kern der Debatte, dem methodologischen Aspekt
- der Einheitskosten. Warum darf eine Multiplikation genauso viel kosten wie eine einfache Addition? Das Modell hat Stärken und Schwächen. Auf der positiven
- Seite ermöglicht es eine saubere Analyse der algorithmischen Struktur, ohne sich in Bitzählerei zu verlieren. Aber Vorsicht, wenn Zahlen beliebig groß
- werden, bricht das Modell zusammen. Theoretisch könnte man durch wiederholtes Quadrieren riesige Zahlen erzeugen und massive Parallelität
- kostenlos nutzen, die sogenannte Mation Anomalie. Als Korrektiv gibt es das logarithmische Kostenmaß. Hier kostet eine Operation Zeit proportional zur
- Länge der Zahl in Bits. Das ist physikalisch korrekter. Informationen zu verarbeiten kostet Energie und Zeit, aber für die tägliche Arbeit von
- Softwareingenieuren auf zu unhandlich. Der Ausweg aus diesem Dilemma ist das Wardrum Modell. Wir nehmen an, dass die Maschine auf Wörtern einer Breite W
- operiert, wobei W mindestens dem Logarithmus der Eingabegröße N entspricht. Das ist nur logisch, damit die Maschine überhaupt die Eingabe
- adressieren kann, müssen die Adressregister groß genug sein. Dieses Modell führt uns zur Transdichotomie. Da ein Maschinenwort log Bits enthält,
- können wir mit Bitweisen Operationen wie and oder XR tatsächlich log n Bits parallel in einem einzigen Schritt verarbeiten. Algorithmen wie Fusion
- Trees nutzen genau diese Eigenschaft, um schneller zu sortieren, als es durch bloße Vergleiche möglich wäre. Wo die Abstraktion jedoch am stärksten von der
- Realität abweicht, ist beim Speicher. Das Rammodell behauptet, jeder Zugriff koste gleich viel. In der Realität sehen wir eine Hierarchie. Register sind
- blitzschnell, aber ein Zugriff auf den Hauptspeicher, ein sogenannter Cashmiss, kann hunderte Taktzyklen kosten. Das Modell ist hier blind für die Latenz. Um
- dies zu kompensieren, nutzen wir erweiterte Modelle wie Cash Oblivius Algorithmen, die Datentransfers minimieren oder die Parallel RAM, kurz
- Payram, um GPUs und Multicore Prozessoren zu modellieren. Zusammenfassend lässt sich sagen, das RAM Modell mit Einheitskosten ist eine
- noble Lüge. Es ist physikalisch ungenau, aber epistemisch unglaublich nützlich. Es destilliert die essentielle Komplexität eines Problems heraus,
- gereinigt vom Rauschen der technologischen Implementierung. Danke für Ihre Aufmerksamkeit.
Zum Nachlesen
Theoretische InformatikIhre Inhalte sind die Automatentheorie, die Theorie der formalen Sprachen, die Berechenbarkeits- und Komplexitätstheorie, aber auch die Logik und formale …
KomplexitätstheorieDie Komplexität von Algorithmen wird in deren Ressourcenverbrauch gemessen, meist Rechenzeit oder Speicherplatzbedarf, manchmal auch speziellere Maße wie die …