Theoretische Informatik: Epistemologie und RAM-Modelle
Topico Deutsch
https://www.youtube.com/watch?v=pI8kkC5iVZ4

Transkript (automatisch erstellt)

0:00 Willkommen zu dieser Analyse der theoretischen Informatik. Wir untersuchen heute die epistemologischen Grundlagen, die es uns ermöglichen,
0:08 komplexe physikalische Prozesse in abstrakte mathematische Modelle zu übersetzen. Im Zentrum steht das Random Access Machine Modell Kurz RAM und die
0:17 Frage, warum wir elementaren Operationen Kosten von O1 zuweisen, obwohl die physikalische Realität viel komplexer ist. Beginnen wir mit dem fundamentalen
0:27 Dilemma der Informatik. Wie generieren wir verlässliches Wissen über künstliche Systeme, die zwar von Menschen geschaffen, aber oft undurchschaubar
0:36 komplex sind? Anders als die Physik, die eine bereits existierende Natur beschreibt, konstruiert die Informatik ihre Objekte, Algorithmen und
0:45 Datenstrukturen selbst. Abstraktion ist hierbei kein bloßes Weglassen, sondern eine normative Entscheidung. Wir bestimmen aktiv, was als relevantes
0:54 Detail zählt und was wir als bloßes Rauschen der Implementierung ignorieren. Dennoch existieren diese Abstraktionen nicht im luftleeren Raum. Wir sprechen
1:03 von einer sogenannten Implementierungsspur. Ein abstrakter Stapelspeicher mag mathematisch rein durch das Lifoprinzip
1:11 definiert sein, aber in der Realität verbraucht er Speicherzellen und Energie. Das RAM Modell versucht diese Spur zu minimieren, kann sie aber
1:21 niemals vollständig tilgen. Warum tun wir das? Das Ziel ist Inviarianz. Wir wollen sagen können, dass ein Algorithmus effizient ist, ohne zu
1:30 wissen, ob er auf einer Intel CPU oder einem Armprozessor läuft. Die Zuweisung von Einheitskosten ist ein methodologischer Trick, um zeitlose
1:39 mathematische Wahrheiten über Prozesse zu formulieren, die auf zeitgebundenen Maschinen ablaufen. Um das abstrakte Modell zu verstehen, müssen wir sein
1:47 physisches Vorbild betrachten, die von Neumann Architektur, das Fundament fast aller modernen Computer. John von Neumann etablierte 1945
1:57 das Konzept des Stort Program Computers. Die Schlüsselaspekte sind ein gemeinsamer Speicher für Programm und Daten, was selbstmodifizierenden Code
2:07 ermöglicht, eine strikt sequentielle Abarbeitung durch einen Befehlszähler und der namensgebende wahlfreie Zugriff, der das mühsame Spulen von Bändern wie
2:16 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
2:25 exakter abbildet, da das Programm imselben Speicher liegt wie die Daten, hat sich die RAM durchgesetzt. Beide sind polynomiell äquivalent, aber die
2:34 RAM ist einfacher zu analysieren, da wir selten selbstmodifizierenden Code betrachten. Formalisiert durch Cook und Rhow besteht eine RAM aus vier
2:44 Komponenten, einem unendlichen Speicher aus Registern, einem Befehlszähler, einem Akkumulator für Rechenoperationen und dem Programm selbst. Ein Zustand der
2:54 Maschine ist definiert durch das Tupel aus Befehlszähler und Speicherinhalt. Die Atome der Komplexität sind die elementaren Operationen. Dazu gehören
3:04 Datentransfers wie Load und Store, Arithmetik, logische Operationen und Kontrollflussbefehle wie Jump. All diesen Operationen weisen wir
3:15 konventionsgemäß Kosten von O von 1 zu. Besonders hervorzuheben ist die indirekte Adressierung hier als Load Stern K dargestellt. Sie nutzt den
3:26 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
3:35 konstanter Zeit unmöglich. Sie ist der qualitative Unterschied zur Touringmaschine. Kommen wir nun zum Kern der Debatte, dem methodologischen Aspekt
3:45 der Einheitskosten. Warum darf eine Multiplikation genauso viel kosten wie eine einfache Addition? Das Modell hat Stärken und Schwächen. Auf der positiven
3:55 Seite ermöglicht es eine saubere Analyse der algorithmischen Struktur, ohne sich in Bitzählerei zu verlieren. Aber Vorsicht, wenn Zahlen beliebig groß
4:04 werden, bricht das Modell zusammen. Theoretisch könnte man durch wiederholtes Quadrieren riesige Zahlen erzeugen und massive Parallelität
4:12 kostenlos nutzen, die sogenannte Mation Anomalie. Als Korrektiv gibt es das logarithmische Kostenmaß. Hier kostet eine Operation Zeit proportional zur
4:22 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
4:31 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
4:41 operiert, wobei W mindestens dem Logarithmus der Eingabegröße N entspricht. Das ist nur logisch, damit die Maschine überhaupt die Eingabe
4:49 adressieren kann, müssen die Adressregister groß genug sein. Dieses Modell führt uns zur Transdichotomie. Da ein Maschinenwort log Bits enthält,
4:59 können wir mit Bitweisen Operationen wie and oder XR tatsächlich log n Bits parallel in einem einzigen Schritt verarbeiten. Algorithmen wie Fusion
5:08 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
5:16 Realität abweicht, ist beim Speicher. Das Rammodell behauptet, jeder Zugriff koste gleich viel. In der Realität sehen wir eine Hierarchie. Register sind
5:26 blitzschnell, aber ein Zugriff auf den Hauptspeicher, ein sogenannter Cashmiss, kann hunderte Taktzyklen kosten. Das Modell ist hier blind für die Latenz. Um
5:36 dies zu kompensieren, nutzen wir erweiterte Modelle wie Cash Oblivius Algorithmen, die Datentransfers minimieren oder die Parallel RAM, kurz
5:44 Payram, um GPUs und Multicore Prozessoren zu modellieren. Zusammenfassend lässt sich sagen, das RAM Modell mit Einheitskosten ist eine
5:53 noble Lüge. Es ist physikalisch ungenau, aber epistemisch unglaublich nützlich. Es destilliert die essentielle Komplexität eines Problems heraus,
6:03 gereinigt vom Rauschen der technologischen Implementierung. Danke für Ihre Aufmerksamkeit.