An

Wie letzte Woche angekündigt, ab heute also nicht mehr Analyse von Algorithmen, sondern

Analyse von Problemen, hin auf ihre Berechnungskomplexität weiterhin.

Ich schreibe hier in der Überschrift zunächst mal Recall, also Erinnerung an Komplexitäten,

ja deswegen, weil sie die Anfangsgründe des ganzen Jahr schon kennen aus BFS.

Das heißt nichts von dem, was ich also in der heutigen Sitzung mache, dürfte in

irgendeiner Form wirklich neu sein. Es geht tatsächlich mehr um Erinnerung und

vielleicht noch eine Fixierung von Notation, wobei ich jetzt also hier mit Notation auch

nicht exzessiv wählerisch sein werde. Wir kennen schon ein Berechnungsmodell bzw.

das kannten Sie ja auch schon, das ist die Random Access Machine. Für viele Zwecke in

der Komplexität ist die nützlich, für viele andere Zwecke ist weiterhin die gute alte

Turing Maschine nützlich. So ich erinnere jetzt also, nachdem wir an die Random Access

Machine schon mal erinnert haben, an die Turing Maschine.

Eine zweite kurze T-App.

Das vielleicht hervorstechendste Merkmal der Turing Maschine ist, dass sie als Speicherbänder

verwendet, die, ich weiß gar nicht mehr, wie das Gegenteil von Random Access heißt.

Früher hatte man auf Computern, da waren sie noch ganz klein, als Speichermedium, nicht

etwa Disketten, die man heute noch als Speichersymbol merkwürdigerweise in jedem Office Programm

kennt, obwohl keiner so ein Ding je gesehen hat, sondern davor hatte man Kassetten, Tonkassetten,

auf die man sequenziell zugegriffen hat. Man konnte nicht irgendwo auf diese Kassette zugreifen,

sondern man musste die erstmal an die richtige Stelle spulen. Das dauert in unserer neuen

Sprechweise im Zweifelsfalle nie ein Jahr lange. Das heißt, in unserem Turing-Maschinen-Modell,

da haben wir nun High-Tech, nicht ein, sondern mehrere Bänder, wenn wir wollen. Es gibt auch

natürlich eine Version mit nur einem Band, das heißt, die Anzahl Bänder sehen wir als

Variabel an, durchnummeriert von 1 bis K.

Das erste Band, wenn es denn mehr als ein Band gibt, sehen wir an als das Eingabeband,

und das nehmen wir ernst. Das erste Band ist Read-Only, wir können auf das erste Band nicht schreiben.

Das letzte Band, so es denn mindestens drei Bänder gibt, ist das Ausgabeband, auch das

nehmen wir ernst. Das ist Write-Only, da können wir nicht von lesen. Ja, was befindet sich

überhaupt auf den Bändern? Die Bänder sind so diskret unterteilt, in einzelne Speicherplätze,

in einem solchen Speicherplatz, nennen wir eine Zelle. Es gibt jetzt verschiedene Versionen

des Ganzen, wenn wir nichts weiter dazu sagen, nehmen wir an, dass unsere Bänder nur einseitig

und endlich sind, also nach rechts. Es gibt eine Version, die man genauso gut verwenden

kann, in der die Bänder beidseitig und endlich sind, nach links und nach rechts. So, gibt

es also diese Zellen. Und zugegriffen wird auf die Bänder überschreibleseköpfe, eins

pro Band. So, die Dinger nenne ich im Allgemeinen nur Köpfe. Es ist ja auch nicht wahr, dass

sie jedes Mal Schreib- und Leseköpfe sind, das hier ist ein reiner Schreibkopf und das

hier ist ein reiner Lesekopf. So, und zugegriffen wird auf das Band eben in völliger Analogie

zum Kassettenrekorder über den Kopf allein. Das heißt, wir können immer nur auf die

Bänder zugreifen, an der der Kopf gerade steht. So, und dann haben wir hier einen Controller,

das ist das Programm. Und dieser Controller, der hat Zustände und zwischen diesen Zuständen

gibt es Übergänge. Hier gibt es noch mal keine bunte Kreide. Also diese einzelnen Punkte

hier in diesem Graphen, die nenne ich Zustände. Und der Controller, der kontrolliert die Schreibleseköpfe.

Das heißt, er bewegt sie und er transferiert Daten hin und her. Also er kann aufs Band

schreiben und er kann vom Band lesen über die Schreibleseköpfe. Zwei wichtige Charakteristika

dieses Modells sind diese, ich schreibe es auf Englisch. Es ist einerseits ein Infinite

State Modell. Es gibt unendlich viele Zustände. Deswegen, weil die Bänder unendlich groß sind.

Dagegen diese Kontrolleinheit hier unten, die das ganze steuert, die ist endlich. Die hat

nur endlich viele Zustände. Die ist eben ein Programm. Ja, genau, also ein Programm ist

ja auch endlich. Irgendwann mal sind wir fertig mit tippen und das Programm steht da als