Herzlich willkommen zur letzten Vorlesung Theoretische Grundlagen der
Informatik in diesem Semester.
Ich werde heute eine kleine Zusammenfassung geben über Teile von dem,
was wir gesehen haben.
Kleine Warnung, das ist weder eine vollständige Zusammenfassung noch
sind es irgendwie die Teile, die besonders wichtig sind für die
Klausur oder sowas, sondern es ist auch nicht eine willkürliche
Zusammenfassung, aber ich hoffe, es hilft ein bisschen.
Ich habe versucht, ein bisschen das jung zu halten von dem, was am
Dienstag in der Übung gesagt wurde und noch mal die Aspekte, die dort
ein bisschen zu kurz gekommen sind, hier zu erwähnen.
Das Bild hier ist ein bisschen verzerrt.
Uns fehlt auf der rechten Seite so ein kleines Stück.
Ich hoffe, das macht keine Schwierigkeiten.
Ich kriege das jetzt nicht hin.
Das ist der Plan für heute.
Also wir werden größtenteils die Chomsky-Hierarchie uns noch mal
angucken und noch mal zusammenfassen, was sind die Elemente, die wir
dort gesehen haben, was sind die Verfahren, die wir dort gesehen
haben, was könnte so zum Beispiel in der Klausur passieren.
Und am Ende gucken wir uns noch mal Domino-Spielen an.
Okay, also die Chomsky-Hierarchie, ich werde jetzt von unten
aufrollen, also von speziell bis allgemein.
Das Speziellste, was wir kennengelernt haben, ist Chomsky-Typ 3.
Wir haben das in Form von Grammatiken letztendlich dargestellt.
Allerdings haben wir ganz am Anfang mit der Vorlesung auch damit zu
tun gehabt, nämlich in Form von regulären Sprachen.
Also Chomsky-Typ 3 Grammatiken ist das gleiche wie links- oder
rechtsreguläre Sprachen oder reguläre Sprachen.
Wir haben dann kennengelernt, die deterministischen endlichen
Automaten, die solche Sprachen beschreiben.
Und wir haben dann auch nicht-deterministische endliche Automaten
kennengelernt und so einen schönen Ringschluss gezogen, dass wir zu
jeder regulären Sprache einen nicht-deterministischen endlichen
Automaten kriegen, der die Sprache beschreibt.
Wir dann wiederum aus jedem, naja, nicht-deterministischen endlichen
Automaten einen deterministischen endlichen Automaten bekommen, der
die gleiche Sprache beschreibt.
Und alles, was von einem deterministischen endlichen Automaten
beschrieben wird, ist eine reguläre Sprache.
Also hier ist vor allen Dingen wichtig, dass nicht-deterministisch und
deterministisch gleichmächtig ist.
Mächtig nur im Sinne von, welche Sprache können durch solchen
Automaten beschrieben werden, nicht rücksichtnehmend auf irgendwie
Platz - oder Speicherbedarf oder so.
Bei den nicht-deterministischen endlichen Automaten haben wir sie mit
und ohne Epsilon-Übergänge kennengelernt.
Die Epsilon-Übergänge sind allerdings sehr hilfreich, sodass die
meisten Automaten tatsächlich Epsilon-Übergänge verwenden.
Aber wie gesagt, haben wir eigentlich angefangen, diesen Punkt hier
oben, diese Sprache, nicht über eine Grammatik zu definieren, was wir
dann erst am Ende gemacht haben, sondern über reguläre Ausdrücke.
Und da hatten wir vorher diesen Ringschluss, den können Sie wirklich
nicht sehen, das ist zu schade.
Okay,
also es steht einfach nur RegExpression.
Da haben wir diesen Ringschluss zwischen nicht-deterministisch und
deterministisch benutzt, um dann eigentlich über reguläre Ausdrücke zu
reden.
Sprachen, die durch reguläre Ausdrücke beschrieben werden.
Und der Teil mit der Chomsky-Hierarchie kam erst später, wo wir es
dann in Grammatiken dargestellt haben.
Gut, also wenn wir von Grammatiken sprechen, dann sind die Chomsky-3
-Grammatiken die speziellsten.
Da ist ja nicht viel erlaubt bei den Ableitungen.
Ein bisschen allgemeiner.
Achso, ach ja, dann haben wir natürlich über reguläre Sprachen
verschiedenste Verfahren kennengelernt.
Und ich habe hier einfach mal nur vier hingeschrieben.
Wir haben sogar noch ein paar mehr kennengelernt.
Also das Wortproblem ist natürlich immer die erste Frage, die man sich
da stellt.
Also gegeben die Sprache in irgendeiner sinnvollen Darstellung, wie
schwer ist es zu entscheiden, ob ein gegebenes Wort in der Sprache
liegt oder nicht.
Das ist das Wortproblem.
Und hier kann man das sehr leicht lösen, in Abhängigkeit davon, wie
die Sprache gegeben ist.
Die kann ja entweder durch eine Typ-3-Grammatik gegeben sein.
Wenn man dann das Wortproblem lösen möchte, dann muss man einfach das
Wort ableiten.
Also man muss in der Grammatik aus dem Startsymbol einfach ableiten
und eventuell backtracken, wenn man eine Wahl hatte, ab und zu.
Das Gute ist aber, dass man weiß, wann man aufhören muss, wenn das
Wort nämlich... das Wort wird ja Zeichen für Zeichen aufgebaut und
sobald man ein falsches Zeichen hat, braucht man da nicht
weitermachen.
Das ist also sehr einfach, wirklich von links nach rechts
durcharbeiten und eventuell backtracken.
Wenn man den deterministischen endlichen Automaten hat, der die
Sprache beschreibt, ist es noch einfacher.
Da ist wirklich deterministisch vorgegeben, da wird das Wort als Input
genommen und das Wort wird Zeichen für Zeichen abgelesen.
Der Automat wechselt vom Startzustand in den nächsten Zustand, in den
nächsten Zustand, je nachdem, wie er definiert ist.
Und dann am Ende sind wir in irgendeinem Endzustand und die Frage ist
bloß, ist er akzeptierend, ja oder nein?
Und wenn er akzeptierend ist, dann ist das Wort in der Sprache und
wenn nicht, dann nicht.
Wenn wir einen nicht-deterministischen endlichen Automaten gegeben
haben, der die Sprache beschreibt, dann ist es im Prinzip das Gleiche,
nur dass wir jetzt Wahlmöglichkeiten haben.
Wenn wir einen Epsilon-Übergang haben oder wenn wir ein Zeichen A
lesen, dann kann bei dem Nicht-Determinismus drin sein, dass okay, mit
einem A, was ich jetzt lese, kann ich entweder hier hingehen oder da
hingehen und dann muss man eventuell backtracken.
Aber alles in allem ist das Wortproblem immer noch sehr einfach zu
lösen.
Dann hatten wir uns angeguckt, die sogenannte Potenzmengen
-Konstruktion.
Das war der Schritt, wie wir von nicht-deterministischen endlichen
Automaten auf deterministische gekommen sind.
Das ist hier ein ganz kleines Beispiel eines nicht-deterministischen
endlichen Automaten.
Wir machen uns nochmal ganz klar, was das hier ungefähr ist.
Wir haben ein Alphabet von zwei Symbolen A und B.
Wir haben drei Zustände.
Q0 ist der Startzustand, Q1 und Q2 sind Endzustände.
Es gibt ein paar Übergänge, die hier nicht eingezeichnet sind.
Zum Beispiel was von Q0, wenn B gelesen wird oder von Q2, wenn B
gelesen wird.
Wir nehmen dann immer implizit an, dass die in einen Fehlerzustand
führen.
Also eigentlich hat der Automat vier Zustände und nicht drei, aber wir
malen nur drei hin.
Das ist aber immer wichtig für Sie, sich zu merken, dass es da
eventuell noch einen Fehlerzustand gibt.
Bei der Potenzmengen-Konstruktion konnte man nacheinander so machen,
diesen neuen Automaten, den nicht-deterministischen Automaten,
konstruieren, indem man sich angeguckt hat, die Zustände des neuen
Automaten waren die Teilmengen von Zuständen des alten Automaten.
Und die Frage ist, welche Teilmengen sind über welche Übergänge
erreichbar.
Und der Startzustand des neuen Automaten ist gerade das, was vom
Startzustand des alten Automaten, des nicht-deterministischen,
höchstens über Epsilon-Zu-Übergänge erreichbar ist.
Also hier ist U0 und Q2 sind über Epsilon-Übergänge erreichbar, also
null oder mehr Epsilon-Übergänge.
Und deswegen ist das unser Startzustand.
Und dann muss man einfach nur sich so eine Tabelle im Prinzip machen,
wo steht, das ist ein Zustand, den ich schon gebaut habe und für den
muss ich jetzt noch wissen, für jedes Zeichen meines Alphabets, wohin
könnte ich denn kommen, wenn ich von dort aus A lese oder wenn ich von
dort aus B lese, immer mit der Möglichkeit Epsilon-Übergänge zu
nehmen.
Also wenn ich das jetzt mache, dann kann man gucken von dieser blauen
Menge und ich nehme A, dann kann ich entweder in Q2 landen oder in Q1.
Deswegen gibt es hier den Übergang von diesem Zustand, Q0, Q2, mit A
nach Q1, Q2.
Wenn ich von diesen beiden B lese, dann lande ich in dem
Fehlerzustand, den ich jetzt hier einfach mal mit leerer Menge
gekennzeichnet habe.
Und jetzt habe ich einen neuen Zustand kennengelernt, nämlich Q1, Q2
ist auch ein Zustand.
Das heißt, ich muss den wieder vorne in meine Tabelle eintragen und
wieder gucken, was passiert denn, wenn ich von dem aus A lese oder B
lese oder Epsilon-Übergänge dabei mache.
Und genau, das ist jetzt der neue Zustand, Q1, Q2.
Und wenn ich von dem A lese, dann weiß ich, okay, dann lande ich auf
jeden Fall in Q2 oder in dem Fehlerzustand.
Und wenn ich von diesen beiden B lese, dann lande ich auf jeden Fall
in Q1.
Das heißt, hier schweitest es sich auf.
Jetzt wird mir das wirklich zu bunt hier.
Machen wir es so.
Sehen Sie ein bisschen besser, okay?
Gut, und dann haben wir wieder zwei neue Zustände kennengelernt, Q2,
und müssen uns überlegen, wenn wir da A lesen, landen wir wieder nur
in Q2, B lesen im Fehlerzustand.
Das heißt, wir kriegen hier so eine Schlaufe an A, und wenn wir das
für Q1 machen, dann A im Fehlerzustand und B landen wir wieder in Q1.
Okay, also das wäre jetzt hier der fast vollständige deterministische
Endliche Automat zu dem nicht-deterministischen da drüben.
Was uns noch fehlt, sind die akzeptierenden Zustände zu kennzeichnen.
Welche von denen sind akzeptierend?
Und das ist jetzt so, das hängt davon ab, was natürlich hier drüben
akzeptierend ist, nämlich Q1 und Q2.
Das heißt, überall wo Q1 oder Q2 auftaucht, ist akzeptiert.
In dem Fall wäre alles akzeptierend.
Und jetzt sehen Sie auch, dass es noch mal wichtig ist, sich
klarzumachen, dass es hier einen Fehlerzustand gibt, sowohl links als
auch rechts, den ich immer weggelassen habe.
Ansonsten sieht es so aus, als ob es hier alles akzeptiert und die
Sprache, die da beschrieben wird, ist aber wirklich nicht alle Wörter.
Also es gibt genügend Wörter, die da nicht akzeptiert werden von
diesem Automat.
Zum Beispiel alles, was man mit einem B anfängt.
Okay, also vergessen Sie den Fehlerzustand nicht, insbesondere wenn es
um den nächsten Punkt geht, also wenn Sie eventuell vielleicht diese
Potenzmengen -Konstruktion gemacht haben und glimpflich durchgekommen
sind, so wie ich hier mit einem relativ kleinen Automaten und dann den
Automaten minimieren wollen.
Das Problem an der Potenzmengen-Konstruktion ist ja die
Heißpotenzmengen -Konstruktion, weil sie eventuell potenziert.
Die Anzahl der Zustände könnte exponentiell wachsen.
Es könnte wirklich schon für kleine, nicht-deterministische, riesige
deterministische geben.
Deswegen ist es wirklich eine Sache, den Automaten zu minimieren.
Da hat man diesen Äquivalenzklassen-Automaten uns angeguckt und
definiert, was es heißt, dass zwei Zustände äquivalent sind.
Das ist im Prinzip, wenn sie das gleiche Akzeptanzverhalten haben.
Wir hatten zuerst geguckt, gibt es Zustände, die überhaupt nicht
erreicht werden können?
Vom Start-Zustand, die haben wir schon mal ausgeschmissen.
Und dann haben wir uns angeguckt, jetzt wissen wir, jeder Zustand ist
erreichbar.
Und die Frage ist, wenn ich schon mal bin in dem Zustand, welche
Wörter führen zu akzeptierenden oder zu nicht akzeptierenden
Zuständen.
Und wenn wir für zwei verschiedene Zustände herausgefunden haben, die
sind äquivalent, nämlich egal, wenn ich schon mal hier und da gelandet
bin, dann egal, was ich dann lese, ich lande immer wieder im
akzeptierenden oder nicht akzeptierenden, dann könnten wir die
zusammenfassen.
Und das machen wir zum Beispiel für diesen Automaten hier, indem wir
uns so eine Matrix, so eine halbe Matrix, hinschreiben.
Wir können auch einfach eine Tabelle im Prinzip machen, ist ja das
gleiche.
Und wir wollen jetzt hier reinschreiben in so eine Zelle, für so ein
paar von Zuständen, zum Beispiel Q1, Q0, in die Zelle wollen wir
reinschreiben, entweder nichts, wenn die Zustände äquivalent sind,
oder ein kürzestes Wort, was die Zustände
unterscheidet.
Also wenn man von den Zuständen ausgeht und dieses Wort liest, in
beiden Zuständen, dann ist es ein Unterschied, weil in dem einen ist
es akzeptierend und in dem anderen ist es nicht akzeptierend.
Oder in dem einen ist es eine Äquivalenzklasse und in dem anderen ist
es eine andere Äquivalenzklasse.
Das heißt, wir gehen jetzt die Wörter durch, alle möglichen Wörter,
der Länge nach, mit den kürzesten beginnt.
Das erste Wort, was wir uns angucken sollten, ist das leere Wort.
Und da sehen wir schon mal, dass dieses leere Wort schon mal eine
ganze Menge Paaren von Zuständen als nicht-äquivalent charakterisiert.
Weil einfach die Endzustände und die Nicht-Endzustände beim Lesen von
leerem Wort natürlich die einen akzeptieren und die anderen nicht.
Also hier macht es einen Unterschied.
Das heißt, wir haben schon mal diese grobe Klasterung unserer
Zustände.
Und jetzt könnte es noch sein, dass die beiden grünen äquivalent sind
oder alle drei blauen oder eine Teilmenge von den blauen äquivalent
sind.
Und das müssen wir weiter herausfinden, indem wir längere Wörter
angucken.
Also gucken wir uns an, Wörter der Länge 1, zum Beispiel A.
Und dann merken wir, bei den beiden grünen ergibt sich nichts.
Wenn ich von dem grünen A lese, lande ich wieder im grünen.
Wenn ich von dem grünen A lese, lande ich auch wieder im grünen.
Kein Unterschied.
Bei den blauen, wenn ich von Q2 oder Q1 A lese, in beiden Fällen lande
ich in dem grünen.
Kein Unterschied.
Aber wenn ich von Q0 aus A lese, dann lande ich in dem blauen.
Das macht Q0 anders als die anderen beiden blauen.
Okay.
Das heißt, hier in dieser Tabelle könnten wir uns jetzt das A
eintragen und wir wissen, dass Q0 sich abspaltet von dieser blauen
Gruppe und eine eigene Gruppe bildet.
Jetzt gehen wir weiter, gucken uns das Wort B an.
Das Wort B tut hier nichts.
Oder keine neuen.
Also wir haben ja jetzt nur noch zwei offene Fälle.
Ob Q1 und Q2 äquivalent sind und ob Q3 und Q4 äquivalent sind.
Und bei B, bei beiden, gibt es da keinen Unterschied.
Hört ich doch, ja.
Na gut.
Ich habe jetzt hier B A reingeschrieben.
Aber Sie sehen, dass beim Lesen von B es einen Unterschied macht, ob
wir in Q1 oder in Q2 sind.
Damit haben wir jetzt wieder eine neue Äquivalenzklasse kennengelernt
oder eine Verfeinerung unserer Partition kennengelernt.
Und wir wissen, wir haben dann bewiesen in der Vorlesung, wenn Sie in
einer Runde, wo Sie längere Wörter angucken, keine neue Verfeinerung
finden, dann können Sie aufhören.
Und das ist jetzt hier der Fall.
Wenn wir uns längere Wörter angucken, dann merken wir, dass Q3 und Q4
nicht getrennt wurden.
Das heißt, es ist immer noch wieder vor.
Und dann können wir aufhören.
Dann wissen wir auch, Q3 und Q4 sind äquivalent.
So, dann haben wir das Verfahren durchgeführt und das ist jetzt im
Prinzip diese Tabelle.
Alles, was uns daran interessiert, sind eigentlich die Kreuze, die
Fälle von Zuständen, die äquivalent sind.
Und die werden dann zusammengefasst zu einem neuen Automaten, dem
Äquivalenzklassenautomaten.
Und Sie haben bewiesen in der Vorlesung, dass dieser
Äquivalenzklassenautomat zustandsminimal ist unter den
deterministischen endlichen Automaten für diese Sprache.
Okay.
Gut.
Hier ist es jetzt auch wichtig, was ich davor gesagt habe, vergessen
Sie, wenn Sie den Automaten minimieren sollen, nicht den
Fehlerzustand.
Wenn Sie den Fehlerzustand irgendwie da nicht mit auf dem Schirm
haben, dann kann es sein, dass der Automat, den ich auf der Folie
davor habe, der wird ganz schnell einfach nur ein Zustand akzeptiert,
weil das so aussieht, als ob alles akzeptiert wäre.
So.
Das nächste Verfahren, was wir da kennengelernt haben, war das Pumping
-Lemma in der ersten Form für reguläre Sprachen.
Und da ist es mir wichtig, dass Sie mehr die Idee im Kopf haben, warum
es gilt, als die exakte Formulierung des Lemmas auswendig wissen.
Ich denke, es hilft einfach mehr, wenn man diese Idee im Kopf hat.
Also, das Pumping-Lemma sagt etwas aus über Eigenschaften von
regulären Sprachen.
Es benutzt, dass reguläre Sprachen genau durch deterministische
endliche Automaten beschrieben werden.
Für jede Sprache gibt es einen Automaten.
Einen endlichen deterministischen Automaten.
Der ist per Definition endlich, das heißt, er hat nur begrenzt viele
Zustände.
Wenn ich mir jetzt eine Abarbeitung angucke, und die Abarbeitung ist
ja die Länge des Wortes, die da abgearbeitet wird.
Wenn das Wort lang genug ist, länger als es Zustände gibt, dann muss
natürlich sich irgendwann ein Zustand wiederholen in der Abarbeitung.
Also, wenn ich nur lang genug ein Wort angucke, jedes Wort, das lang
genug ist, angucke, dann wird es abgearbeitet, sagen wir mal hier von
S in den Endzustand, in den akzeptierenden Endzustand QE, also das ist
ein Wort, was akzeptiert wird, ein Wort aus der Sprache, dann sagen
wir mal, ist QC hier der Zustand, der sich zuerst wiederholt.
Dann habe ich von S bis QC irgendein Teilwort, ein initiales Teilwort
U abgearbeitet.
Zwischen QC und wieder nach QC kommen, habe ich irgendein Mittelwort V
abgearbeitet und von QC bis zum Endzustand irgendein Postfix X.
Und jetzt sehen wir natürlich, dass die deterministischen endlichen
Automaten, weil sie kein Gedächtnis haben und gar nichts haben, und
deterministisch sind, ich kann auch von QC einfach nochmal durch die
Schlaufe gehen.
Oder ich kann die Schlaufe auch weglassen.
Ich kann nur UX abarbeiten, und das wird auch akzeptiert.
Ich kann UVX abarbeiten, ich kann UVVX abarbeiten und so weiter.
Das heißt, wenn ich weiß, dass UVX in meiner Sprache ist, dann weiß
ich auch, dass UVVVVVX in meiner Sprache ist.
Und für jedes Wort in der Sprache, was lang genug ist, finde ich diese
Aufteilung in UV und X.
Vielleicht mehrere, aber mindestens eine solche Aufteilung.
Und das ist die Idee.
Also das Pumping Lemma sagt ja erstmal etwas aus.
Jede reguläre Sprache hat diese Eigenschaft, dass ich aus Wörtern, die
lang genug sind, neue Wörter kriege, die wieder drin sind.
Und wir benutzen das jetzt, um zu zeigen, dass bestimmte Sprachen
nicht regulär sind.
Indem wir zeigen, dass diese Sprache diese Eigenschaft nicht hat.
Und das ist ein Tool für Sie, was die Möglichkeit bietet, zu zeigen,
dass etwas nicht regulär ist.
Das klappt nicht immer, aber schon ziemlich oft.
Gut.
Nächster Schritt.
Chomsky 2 oder kontextfreie Grammatik.
Die regulären Sprachen oder die Chomsky 3 Grammatiken, die sind schon
sehr eingeschränkt.
Chomsky 2 sind eigentlich die richtig schönen.
Das sind eigentlich die, die man sich wünscht, die kontextfreien
Grammatiken.
Wir haben dort wieder so einen Ringenschluss gemacht, allerdings ein
bisschen kürzer, nur mit zwei Items.
Und zwar, wir sind auf das Berechnungsmodell des Kellerautomaten, des
nicht -deterministischen Kellerautomaten gekommen.
Und haben bewiesen, dass jede Chomsky 2 Grammatik durch einen
Kellerautomaten berechnet wird.
Und jeder Kellerautomaten hat Chomsky 2 Grammatik berechnet.
Das war ein bisschen aufwendiger.
Das war ein ziemlich großer Ringschluss mit verschiedenen Normalformen
und leerem Stack und nicht-leerem Stack akzeptieren und so.
Aber letztendlich ist das die sehr simple Vereinfachung von dem, was
wir dort gemacht haben.
Hier ist es wichtig, dass wir nicht-deterministische Kellerautomaten
haben.
Wir haben nicht viel in der Vorlesung darüber geredet.
Ich glaube, in der Übung wurde es einmal erwähnt.
Deterministische Kellerautomaten sind tatsächlich etwas anderes.
Die sind wirklich nicht gleichmächtig.
Die beschreiben eine Teilklasse aller Chomsky 2 Sprachen.
Spezielle Kontextfreie Sprachen.
Aber so genau sind wir darauf nicht eingegangen, wie die Kontextfreien
Sprachen resettet sind.
Wir haben uns hier auf die echten Kontextfreien Sprachen konzentriert
und wir haben da vor allen Dingen zwei Normalformen kennengelernt.
Die Chomsky-Normalform und die Greibach-Normalform.
Die Greibach-Normalform, die wurde benutzt im Prinzip in diesem
Ringschluss von den Kellerautomaten, weil wir aus der Greibach
-Normalform ganz leicht den Kellerautomaten ablesen können.
Und aus dem Kellerautomaten auch eine Grammatik, die fast schon
Greibach -Normalform hatte.
Die Chomsky-Normalform war wichtig, um andere algorithmische Aussagen
zu treffen über Kontextfreie Sprachen.
Wie war das nochmal?
Um die Grammatik in Chomsky-Normalform zu bringen, müssen alle
Ableitungsregeln der Form sein, aus einem Nicht-Terminal wird genau
ein Terminal, also ersetze Variable durch Wert oder ersetze Variable
durch genau zwei Variablen.
Aus einem Nicht-Terminal sind auf der rechten Seite genau zwei Nicht
-Terminale.
Wir haben Verfahren kennengelernt, wie man diese Chomsky-Normalform
konstruiert, berechnet, aus einer gegebenen Grammatik.
Es ging über mehrere Schritte, die mehr oder weniger lang und
kompliziert waren.
Die groben Ideen dahinter waren, dass man zuerst die Y-Übergänge, das
sind die Übergänge oder Ableitungen von einem Terminal über eine Folge
von Ableitungen zum leeren Wort.
Jede Variable, die das ermöglicht hat, haben wir identifiziert und die
wollten wir eliminieren, diese Y-Übergänge.
Die haben wir dann ganz am Ende wieder eingebunden.
Dann haben wir, ich glaube, wir haben es in der Vorlesung ein bisschen
anders gemacht.
Wir haben zuerst die langen und gemischten rechten Seiten verkleinert
und entmischt.
Man kann das auch ganz am Ende machen.
Wenn auf der rechten Seite, da ist ja in normaler kontextfreier
Grammatik, darf auf der rechten Seite irgendwas stehen.
Solange auf der linken Seite nur eine, genau eine Variable steht, darf
auf der rechten Seite irgendwas stehen.
Das heißt, irgendein beliebiges Wort aus Terminalen und Nicht
-Terminalen.
Und da haben wir ein bisschen aufgeräumt, haben erstmal alle nur zu
Nicht -Terminalen gemacht oder genau einem Terminal und dann haben wir
die längeren gekürzt in zwei, durch Einführen von neun Variablen.
Und dann gab es noch das Problem, dass man jetzt Einheitsableitungen
hatte, nämlich Variable bildet ab auf genau eine Variable, die wir ja
auch nicht in der Normalform wollen.
Wir wollen Variable auf einen Wert oder Variable auf zwei Variablen.
Und diese Einheitsableitungen, da gab es die zyklischen, die so im
Kreis gingen, die mussten wir erstmal identifizieren und eliminieren.
Und dann gab es noch die nicht-zyklischen, aus A wird B, aus B wird C,
aus C wird B usw.
Und die haben wir dann auch noch eliminiert.
Und als wir damit dann fertig waren, dann waren wir endlich in Jobs
genommen.
Diese Normalform ist besonders wichtig, weil man zum Beispiel dann,
wenn die Grammatik in der Normalform gegeben ist, das Wortproblem
lösen kann mit einem kugelischen Algorithmus, dem CYK-Algorithmus.
Und der sah nochmal so aus, wir haben uns wieder mal eine halbe
Tabelle gemalt.
Hier unten in die letzte Zeile haben wir das Input, also das Wort, von
dem wir jetzt entscheiden wollen, ob es in der Sprache ist oder nicht,
reingeschrieben.
Und dann wollten wir jetzt mit dynamischer Programmierung die Zellen
dieser Tabelle füllen.
Und zwar in dieser Reihenfolge von unten nach oben und dann innerhalb,
ist eigentlich egal, aber von links nach rechts sagen wir mal.
Letztendlich ist dann für jede Zelle, die wir uns jetzt angucken
wollen, da wollen wir berechnen eine Menge von Variablen.
Und zwar genau die Variablen, die abgeleitet werden können zu diesem
Wort, was hier so schräg diagonal drunter steht unter der Zelle.
Also in diese Zelle hier müsst ihr jetzt alle Variablen ein, die eine
Ableitung haben, nach A, B, B, C.
Und in der ersten Zeile ganz unten ist es ganz leicht, wir gucken
einfach nur alle Regeln der Form an, Nicht-Terminal nach Terminal,
also nach A, und schreiben dann halt das entsprechende Nicht-Terminal
da rein.
Und im Allgemeinen, wenn wir irgendwo weiter oben sind, dann müssen
wir jetzt gucken, wir wissen, diese eine Variable soll nicht nur einen
Wert geben, sondern ein längeres Wort.
Das heißt, der erste Schritt muss sein, diese Variable durch zwei
Variablen zu ersetzen.
Und die müssen dann wiederum für den ersten Teil des Wortes und den
zweiten Teil des Wortes zuständig sein.
Wir wissen aber nicht genau, wie groß die Teile zueinander sind.
Deswegen müssen wir alle Möglichkeiten durchgehen.
Also es könnte sein, dass die erste Variable für die ersten drei
Buchstaben und die zweite für den letzten Buchstaben zuständig ist.
Das heißt, wir gucken uns jetzt hier an, gibt es eine Ableitungsregel,
die auf der rechten Seite zuerst etwas von hier und dann etwas von
hier hat.
Wenn es so eine Ableitungsregel gibt, dann schreiben wir die linke
Seite der Ableitungsregel in das Grüne, was auch immer fällt.
Aber das ist ja nicht die einzige Möglichkeit, unten dieses Wort zu
kriegen.
Wir müssen dann auch das überprüfen und auch das überprüfen.
Das heißt, pro Zelle haben wir jetzt linear viele Möglichkeiten von
Farben, die wir uns angucken müssen.
Und dann müssen wir immer durch die ganzen Ableitungsregeln.
Und letztendlich interessiert uns nur das Ergebnis, was da oben drin
steht.
Und zwar interessiert uns nur, ob dort das Startsymbol S, die
Startvariable S, ob die da drin steht.
Weil, wenn die da drin steht, dann ist es nämlich möglich, aus S genau
dieses Wort zu produzieren.
Und wenn sie da nicht drin steht, wenn es leer ist oder irgendwelche
anderen Nicht-Terminale da drin stehen, aber S nicht, dann ist es
nicht möglich und das Wort ist nicht in der Sprache.
Okay.
Dann hatten wir das Pumping Lemma für kontextfreie Sprachen
kennengelernt.
Wiederum als ein Tool, um zu zeigen, dass eine Sprache nicht
kontextfrei ist.
Aber formuliert ist es als eine Eigenschaft, die alle kontextfreien
Sprachen erfüllen.
Hier wieder, ich werde nicht die Formel hinschreiben mit den ganzen
Quantoren, sondern ich werde versuchen, Ihnen das Bild in den Kopf zu
setzen.
Wir gucken uns nicht die Automaten an.
Man kann das auch machen mit den Kellerautomaten.
Das ist aber nicht ganz so schön wie mit den endlichen Automaten.
Hier ist es eigentlich schöner, über die Syntaxbäume sich das zu
überlegen.
Also, wenn wir einen Syntaxbaum haben, also von S können wir das Wort
W ableiten.
Also das Wort W sehen Sie, wenn Sie von links nach rechts die Blätter
des Baumes so ablesen.
Das ist so meine kleine Illustration davon.
S in der Wurzel und dann weiter.
Dann, wenn das Wort lang genug ist und zum Beispiel die Grammatik in
Chomsky -Normalform ist, dann wissen wir, wenn das Wort lang ist,
viele Blätter hat, dann muss es auch ein Blatt geben, was sehr tief
liegt in dem Baum.
Dann muss es so einen langen Pfad geben, einen Pfad, der länger ist
als die Anzahl der Nicht-Terminale, die wir haben, als die Anzahl der
Variablen.
Dann muss ich also auf so einem Pfad hier runter, muss ich meine
Variable wiederholen, sagen wir mal Variable X.
Okay.
Und dann heißt es, wir haben hier irgendwas, das ist halt die
Eigenschaft dieses Syntax-Baumes, dass man die Blätter dann von links
nach rechts abliest.
Hier von S nach X haben wir hier was abgespaltet, was dann irgendein
Wort U ergibt und hier hinten irgendein Wort Z.
Und zwischen den beiden Xen haben wir hier unten Wort V und hier unten
Wort Y generiert.
Die könnten leer sein, aber sind nicht beide leer.
Und dann letztendlich unter dem X haben wir halt unten diesen
Mittelteil, kleinen x.
Und jetzt sieht man schon, dadurch dass es kontextfrei ist, kann ich
sozusagen den Teilbaum, der hier unter X hängt, auch einfach da unter
das X hängen.
Und das ist immer noch eine zulässige Ableitung.
Also ich kann diesen Orangenteil hier, dieses V und das Y, kann ich
auch einfach nicht machen.
Dann ist das kurze Wort auch in der Sprache.
Oder ich kann es mehrmals machen, so oft ich will.
Und wenn Sie das Bild richtig im Kopf haben, dann sollten Sie auch
fähig sein, diese Formel dahin zu schreiben, dass jedes Wort, das lang
genug ist, kann zerlegt werden in die Form U, V, X, Y, Z.
Mit V und Y zusammen nicht leer.
Sodass auch das Wort U, V hoch I, X, Y hoch I, Z in der Sprache ist
für jedes I.
Das ist das Pumping Lemma für kontextfreie Sprachen.
Und wir haben, glaube ich, relativ viele Beispiele auch gesehen, wie
man das verwendet, um zu zeigen, dass eine Sprache nicht kontextfrei
ist.
Gut, dann die Chomsky 0 und Chomsky 1 Grammatiken haben wir nicht ganz
so ausführlich besprochen.
Chomsky 1 sind, also die sind beide mit Turing-Maschinen.
Wir haben natürlich ganz ausführlich über Turing-Maschinen gesprochen
in dem Komplexitätskapitel.
Aber in dem Hierarchie-Kapitel nicht ganz so ausführlich.
Die Chomsky 1 Grammatiken sind die, die beschrieben werden durch
linear beschränkte, also im Platz linear beschränkte Turing-Maschinen,
nicht deteministische Turing-Maschinen.
N-Tape-N haben wir diese Klasse genannt.
Also Turing-Maschinen, die nicht deteministisch sind.
Und deren Platzbedarf linear im Input ist.
Die Sprachen, die solche Turing-Maschinen erkennen können, das sind
die Chomsky 1 Sprachen.
Hier wieder, es ist nicht bekannt, ob es das gleiche ist für
Determinist.
Wir wissen nicht, ob D-Tape-N das gleiche ist wie N-Tape-N.
Wir haben es definiert als N-Tape-N und haben über D-Tape-M eigentlich
gar nicht gesprochen.
Okay, also wenn Sie da irgendwie durcheinander kommen, in diesem
Bereich mit den nicht-deteministischen und deteministischen, solange
es nicht um Laufzeiten geht, immer nicht-deteministisch.
Für endliche Automaten macht das keinen Unterschied.
Für Kellerautomaten ist es das Richtige.
Und für Turing-Maschinen glauben wir das.
Also ist es auf jeden Fall das Richtige und eventuell macht es keinen
Unterschied.
Und für Chomsky 0, da haben wir diese Platzbeschränkung nicht.
Also alles, was von einer Turing-Maschine berechnet werden kann, alle
solche Sprachen, das sind die semi-entscheidbaren Sprachen, die sind
Chomsky 0.
Und da wiederum haben wir gezeigt, dass es keinen Unterschied macht,
ob die Turing-Maschine nicht-deteministisch oder deteministisch.
Gut, das Wortproblem in diesen Grammatiken, die sind jetzt sehr viel
schwieriger.
In endlichen Automaten war es ganz einfach und dem CYK-Algorithmus,
der geht auch noch.
Wenn man die Grammatik gegeben hat als Grammatik, dann kann man so
einen Ableitungsgraf machen.
Man kann im Prinzip einfach mal alles ableiten, was man ableiten kann.
Sozusagen mit Backtracking anfangen, aus S irgendeine Regel
anzuwenden, darauf wieder irgendwelche Regeln und so weiter.
Und wenn man das irgendwie clever macht, also so in der Breitensuche
mäßig, dass man nicht die ganze Zeit so tief irgendwo reingeht,
sondern wenn man das so breitensuchenmäßig aufzählt, dann wird man
auch irgendwann auf sein Wort treffen, falls es denn ableitbar ist.
Und hier ist jetzt der Unterschied, ob wir wissen, wann es soweit ist,
oder ob wir nicht wissen, wann es soweit ist.
Für Chomsky 1 ist es machbar.
Langsam, weil es exponentiell viele Möglichkeiten gibt, Wörter zu
machen mit n Ableitungsregeln.
Im Allgemeinen ein bisschen schwer, aber wir wissen, bis zu welcher
Tiefe wir gehen müssen.
Wenn wir dann das Wort nicht gefunden haben, dann ist es auch nicht
ableitbar.
Das liegt daran, dass die Grammatiken, die Chomsky 1 Grammatiken, sind
die, wo die rechte Seite immer mindestens so lang ist wie die linke
Seite.
Das heißt, wir wissen, die Wörter können nicht wieder zusammen
schrumpfen.
Wenn wir eine gewisse Wortlänge erreicht haben, dann ist es entweder
unser Wort, oder halt nicht, dann war das ein Fehlversuch.
Und wenn alle Versuche fehlschlagen, dann geht es halt nicht.
Okay.
Das Problem bei Chomsky 0 ist, dass wir jetzt allgemeine Grammatiken
haben und die können sich tierisch aufblähen, diese variablen Wörter,
und dann wieder zusammenfallen und wieder aufblähen und wieder
zusammenfallen und wir wissen nicht, wann wir fertig sind.
Wir wissen, wenn es ableitbar ist, werden wir es finden nach endlicher
Zeit, aber wir wissen nicht, wann wir aufhören müssen zu suchen.
Deswegen sind diese... hier ist das Wortproblem nur semi-entscheidbar.
Nicht-entscheidbar.
Gut.
Das hat so ein bisschen...
Ich weiß nicht, ob es so clever ist, hier NP schwer hinzuschreiben,
weil es gibt immer so ein bisschen die Gefahr, dass diese Chomsky
-Hierarchie mit der Komplexitätstheorie so vermischt wird.
Klar, beides handelt von Turing-Maschinen, und hier reden wir jetzt
auch über die Zeit für das Wortproblem, aber Sie sollten sich klar
machen, was die einzelnen Teile sind, was die Hierarchie-Seite ist,
was die Komplexitätstheorie-Seite ist, und was die paar Brücken sind,
die wir da geschlagen haben.
Zur Entscheidbarkeit, das ist jetzt die Frage sozusagen ganz am Rand
der Hierarchie, ob wir Typ 0 sind oder sogar noch darüber hinaus,
haben wir uns tatsächlich auch eine ganze Menge Gedanken gemacht.
Wir haben darüber geredet, also die Semi-Entscheidbarkeit ist mit
Turing -Maschinen definiert, was eine Turing-Maschine machen kann.
Und wir haben alternative Modelle uns angeguckt, aber letztendlich
gesehen, dass die ganz normale Einband-Einkopf-Turing-Maschine genauso
mächtig ist wie alles andere.
Also wir haben uns Mehrband-Turing-Maschinen angeguckt, Mehrkopf,
mehrdimensionale Turing-Maschinen, und gesehen, dass wenn es nicht um
Laufzeit, nicht um Platz geht, sondern einfach nur finden oder nicht,
die alle gleich mächtig sind.
Und wir haben uns auch Register-Maschinen und was wir vielleicht sonst
noch für Berechnungsmodelle kennengelernt haben, angeschaut und uns
überzeugt davon, dass es das Gleiche ist wie eine Turing-Maschine oder
nicht mächtiger als eine Turing-Maschine.
Man kann auch, ich weiß nicht, ob Guido das gemacht hat,
Kellerautomaten, wenn man denen zwei Stacks gibt, statt nur einen,
dann sind sie genauso mächtig wie eine Turing-Maschine.
Kann man sich ein bisschen so vorstellen, wenn man die zwei Stacks
nimmt und aneinanderplappt, dann hat man so ein Eingabeband im Prinzip
oder ein Arbeitsband, auf dem man alles machen kann.
Genau, und in diesem Zusammenhang gibt es die Church-These, dass sie
wahrscheinlich, wenn sie suchen werden, auch kein...
Welches Adjektiv wird da immer genommen?
Kein realistisches Berechnungsmodell finden, also kein vernünftiges
Rechnungsmodell finden, was mächtiger, echt mächtiger ist als eine
Turing -Maschine.
Also als Turing-Maschine schon das ziemlich genau abbilden, was
Computer tun können.
Okay, dann ging es um Probleme wie das Halte-Problem, also Fragen über
Turing -Maschinen und ob Turing-Maschinen halten werden und
Diagonalsprachen und dann später auch das Post-Korrespondenz-Problem.
Das sind so Fragen, die nicht entscheidbar waren.
Wir haben da Gödel-Nummern aufgestellt, universelle Turing-Maschinen,
das ist eine Turing-Maschine, die Turing-Maschinen simulieren kann.
Beliebige Turing-Maschinen mit beliebigem Input, sozusagen der
Superheld unter allen Turing-Maschinen.
Wir haben den Satz von Rice kennengelernt, der im Prinzip sagt, dass
alles Interessante über Turing-Maschinen ist unentscheidbar.
Hier ist es nochmal ganz wichtig, kurz sich diese Wortverklausulierung
klar zu machen.
Das ist ein bisschen ungeschickt, aber leider so gewachsen.
Also was entscheidbar heißt, das wissen Sie, Sie können in endlicher
Zeit akzeptieren, aber auch ablehnen.
Wir wissen, wann Sie fertig sind mit der Berechnung, ob es jetzt
akzeptiert oder ablehnt.
Semientscheidbar ist, Sie wissen, wenn Sie akzeptieren, werden Sie das
in endlicher Zeit tun.
Sie wissen aber nicht, wann Sie aufhören müssen zu suchen.
Eventuell wissen Sie das nicht.
Und Unentscheidbarkeit ist das Gegenteil von Entscheidbarkeit.
Nicht etwa das Gegenteil von Semientscheidbarkeit.
Also wenn etwas unentscheidbar ist, dann kann es immer noch
semientscheidbar sein oder noch nicht mal semientscheidbar.
Und leider gibt es sowas wie unsemientscheidbar, gibt es leider nicht.
Es gibt aber Funktionen oder Probleme, die weder entscheidbar noch
semientscheidbar sind.
Ich glaube, ich habe das mal in der Übung Ihnen vorgestellt.
Genau, also die Bottomline ist, fast alle interessanten Fragen, die
wirklich diese theoretische Natur haben, tun zwei Turing-Maschinen das
gleiche, hält eine Turing-Maschine auf dieser Eingabe, ist die
Sprache, die diese Turing-Maschine akzeptiert, ist die endlich und
alles Mögliche.
Fast alle solche Fragen sind unentscheidbar.
Im Prinzip, der Satz von Rice ist da sehr mächtig und zeigt, dass fast
alle unentscheidbar sind.
Gut, das war es soweit von diesem kleinen Rückblick aus der Chomsky
-Hierarchie.
Ich möchte gerne nochmal die Warnung sagen, dass Sie das bitte nicht
als vollständige Zusammenfassung der Vorlesung ansehen.
Das ist natürlich nicht möglich, in so kurzer Zeit alles vollständig
zu machen.
Ich habe einige Sachen genannt, ohne sie hinzuschreiben.
Ich habe, glaube ich, keine einzige Ableitungsregel irgendwo stehen zu
haben.
Sie müssen natürlich darüber hinaus viel mehr wissen, als was auf den
Folien ist.
Sie müssen wissen, wie so eine Greibach-Normalform aussieht.
Oder wie man Epsilon-Übergänge aus einem NEA entfernt.
Was ich auch komplett ausgespart habe, ist, was hoffentlich am
Dienstag in der Übung ein bisschen länger war, nämlich NP
-Vollständigkeit.
Die ganzen Reduktionen, was das heißt in NP, NP-Schwer,
Approximationsalgorithmen, schwach und stark NP-Vollständig oder
schwer.
Das ist etwas, was ich heute überhaupt nicht besprechen möchte.
Es wird gleich, wenn ich über Dominos rede, wenn wir einen NP
-Vollständigkeitsbeweis haben.
Aber nicht mit dem Fokus, um etwas zu wiederholen.
Haben Sie soweit erst mal Fragen?
Gut.
Dann machen wir einfach noch ein bisschen Domino, weil es Spaß macht.
Domino ist tatsächlich ein unterschätztes Spiel, oder zumindest ich
habe es unterschätzt.
Ich muss feststellen, dass gefühlt jeder Haushalt ein Domino-Spiel zu
Hause hat, aber niemand weiß, wie das zu spielen ist.
Und da gibt es wirklich interessante Varianten mit Punkten, die nicht
trivial sind.
Also es ist nicht nur, du legst, wenn du kannst, so nach Mao-Mao
-Prinzip, sondern mit Strategie teilweise.
Hier gucken wir uns eine kleine verallgemeinerte Form des Dominos an.
Die sieht wie folgt aus.
Also wir haben eine Menge S.
Das sind im Prinzip die Anzahl der Augen, die auf den Steinen möglich
sind.
Von 0 bis C.
Also bei normalen Dominos sind es von 0 bis 6, aber hier erlauben wir
jetzt von 0 bis C.
Und dann ein Stein ist im Prinzip ein ungeordnetes Paar von Zahlen.
Einfach wie viele Augen sind auf der einen Hälfte des Steins und wie
viele Augen sind auf der anderen Hälfte.
A und B.
Und das Spiel startet, dass jeder Spieler eine Menge von Steinen, im
Allgemeinen eine Multimenge von Steinen, weil es den gleichen Steinen
eventuell doppelt gibt, bekommt.
Auf die Hand.
Diese Menge sei T.I.
Dann, wir gucken uns das jetzt heute nur für zwei Spieler an, aber man
kann sich auch für mehrere Spieler, die dann zyklisch rumspielen, in
Runden spielen, aussetzen ist verboten.
Das heißt, in jeder Runde legt jeder Spieler genau einen Stein.
Mit einem ausgewählten Start.
Außerdem wollen wir für heute annehmen, dass es Perfect Information
gibt.
Also jeder kennt alle Steine im Spiel und jeder sieht alle Steine, die
jeder auf der Hand hat.
Also wir spielen mit offenen Karten.
Und wir machen die häufigste Variante des Dominionsspiels, wir bauen
eine Kette.
Und für die, die, zum Beispiel ich vor einem halben Jahr, die nicht
wissen, warum die Kette jetzt so komisch aussieht, so macht man das.
Wenn man so einen Stein hat, der auf beiden Seiten die gleiche Zahl
hat, dann legt man den so senkrecht zu der Laufrichtung der Kette hin.
Das ist für heute nur ästhetisch, aber für einige Spiele, wo Punkte
gezählt werden, da geht es immer darum, wie viele Augen sind auf den
beiden Enden der Kette gerade zusammen.
Das ist dann wichtig, weil die beiden sind dann beide auf dem Ende,
wobei der hier nur einer auf dem Ende ist.
Ich kann wirklich Ihnen nur raten, mal Dominion zu spielen.
Ich habe mir extra ein ordentliches Dominion-Spiel gekauft.
Ansonsten, die Regeln sind klar.
Was ein Mann-Mann-Da liegt, muss die gleiche Augenzahl haben.
Also eine 3 darf nur eine 3 berühren und eine 2 darf nur eine 2
berühren.
Gut, das ist eine Dominion-Kette.
Jetzt können wir darauf Probleme definieren, und zwar cooperative oder
competitive.
Cooperative heißt, dass die Spieler zusammen spielen und kooperieren.
Sie gegen das Spiel, und sie versuchen, das Spiel zu schlagen, in dem
Fall, indem sie eine möglichst lange Kette bilden.
Oder in dem Fall, indem sie dafür sorgen, dass ein Spieler keine
Steine mehr hat.
Also Cooperative Domino ist eine Anzahl N von Spielern.
Alle Steine liegen offen, die Spieler können kooperieren, sie können
sich absprechen.
Und sie wollen erreichen, dass Spieler 1 alle seine Steine ablegen
kann, ohne nachzuziehen.
Also immer Spieler 1 legt was, die anderen legen was, Spieler 1 legt
was, die anderen legen was.
Wenn sie das schaffen, so zu legen, dass Spieler 1 immer wieder alle
seine Steine runterspielen kann, haben sie gewonnen.
Wenn sie das nicht schaffen, haben sie verloren.
Competitive Dominos ist wahrscheinlich das, was sie eher so im Kopf
haben, wenn die Spieler gegeneinander spielen.
Kann man sich auch angucken und dann sich fragen, ob Spieler 1
gewinnen kann, wenn er sieht, was alles offen liegt, unabhängig davon,
was Spieler 2 macht.
Vielleicht ein kleines Sidenote.
Das da oben ist ein Entscheidungsproblem.
Das unten ist auch ein Entscheidungsproblem.
Das ist einfach nur eine Ja-Nein-Frage zu einer gegebenen Instanz.
Aber die unterscheiden sich gravierend in der Art, wie das Problem
formuliert ist.
Ich will da jetzt nicht weiter darauf eingehen, weil das den Rahmen
sprengen würde, aber hier unten haben wir noch dieses unabhängig
davon, was die anderen Spieler tun.
Also die Frage ist nicht einfach nur, existiert eine Lösung für das,
sondern existiert ein erster Zug, sodass für alle zweiten Züge von den
anderen...
Es gibt, existiert ein nächster Zug für mich, sodass für alle
Möglichkeiten der anderen Züge.
Es existiert ein nächster Zug für mich, sodass für alle Möglichkeiten
und so weiter.
Also wenn man jetzt Satisfiability machen würde, dann wäre das so ein
exist for all, exist for all, exist for all, exist for all.
Wobei hier oben bei normalem Satisfiability einfach nur exist.
Also Sie merken schon, da gibt es tatsächlich komplexitätsmäßig einen
gravierenden Unterschied, aber darauf wollen wir nicht eingehen.
Wir kümmern uns, wir wollen zeigen, dass etwas im NP liegt, wir
sollten das obere nehmen.
Unten wird nicht in NP liegen.
Wir kümmern uns um Cooperative Domino mit zwei Spielern.
Und den Satz, den wir zeigen wollen, ist Cooperative Domino für zwei
Spieler ist NP-vollständig.
Also wenn Sie sich hinsetzen zu Hause und Sie haben hier für
Allgemeinheit das Domino-Spiel mit 0 bis 10 Augen auf jedem Stein.
Und Sie wollen jetzt zu zweit gucken, ob Sie es schaffen können, mit
diesem ausgeteilten Stein diese Kette zu legen, sodass Spieler 1 alle
Steine weglegen kann.
Ist das ein schwieriges Problem?
Okay.
Gut, Beweis.
Zuerst zeigen wir, das liegt in NP.
Dafür müssen wir einen Zeugen angeben, der in Polynomialzeit überprüft
werden kann.
Und der Zeuge ist einfach die Kette.
Und wir sagen, die Kette muss anfangen mit einem Stein von S1.
Und die spielen wir ab.
Und es kann überprüft werden, dass es eine legale Kette ist, dass die
Zweien nur an den Zweien grenzen und die Dreien nur an den Dreien und
so weiter.
Das kann in Polynomialzeit leicht überprüft werden, dass jeder auch
wirklich nur seine Steine genommen hat.
Also liegt das Problem in NP.
Zu zeigen, es ist NP-schwer.
Das heißt, wir müssen ein anderes NP-schweres Problem darauf
reduzieren.
Wir müssen den logischen Schluss machen, wenn unser Problem einfach
wäre, wäre das andere Problem auch einfach.
Wir dürfen Cooperative Domino als Blackbox benutzen, um ein
Algorithmus für ein schweres Problem zu designen.
Polynomialzeitalgorithmus.
Das Problem, was wir hier nehmen, ist Hamilton Path.
Vielleicht naheliegend, Kette, irgendwie eine Aneinanderreihung von
Sachen und Hamilton Path ist sowas, was Sie kennen.
Jetzt ist bloß die Frage, wie machen wir das.
Also, wie gesagt, machen Sie sich klar, wir haben Hamilton Path.
Das heißt, wir wollen Hamilton Path lösen.
Und wir können benutzen, dass wir Domino lösen können.
Das heißt, wir müssen starten mit einer Instanz von Hamilton Path.
Einem Graphen G, beliebiger Graph, wir wissen nichts darüber.
Beliebiger Graph G, Knotenmenge V, Kantenmenge E.
Und wir müssen jetzt aus dem Graphen eine oder mehrere, möglicherweise
eine, Instanz von Domino definieren.
Sodass, wenn wir Domino lösen und die Lösung noch massieren, wir sehen
eine Lösung von Hamilton Path.
Also, wie definieren wir uns die Instanz?
Die Steine von Spieler 1 sollen die Knoten repräsentieren.
Von jedem Knoten da drin gibt es einen Stein, der einfach diesen
Knoten auf beiden Seiten hat.
Knoten sind OBDA-Zahlen.
Und Spieler 2 soll die Kanten haben als seine Steine.
Mit den beiden Endpunkt-Knoten als die beiden Seiten des Steins.
Und noch so einen Sternchen-Stein.
Der Sternchen-Stein sorgt nur dafür, dass...
Also, wir wollen ja, dass S1 alle seine Steine losführt.
Wozu ist der Sternchen-Stein gut?
Weiß ich nicht.
Macht für mich jetzt gerade irgendwie keinen Sinn mehr, warum der
Sternchen -Stein da ist.
Wir sind doch sowieso kooperativ.
Wir werden den Sternchen-Stein nicht einsetzen.
Ich meine, Sie können ihn gar nicht einsetzen.
Spieler 1 fängt an.
Aber was haben wir davon, dass Spieler 2 nicht gewinnen kann?
Wenn Spieler 2 gewinnt, dann hätten sie das kooperative Spiel sowieso
verloren.
Ich glaube, so eine Art Argument war ich dabei zu nennen, aber
irgendwie verstehe ich nicht, wozu wir verhindern müssen, dass Spieler
2 gewinnt.
Sie gewinnen ja, wenn Spieler 1 alle Steine loswird, und andernfalls
verlieren sie.
Dann kann es verschiedene Gründe geben, warum sie verlieren.
Vielleicht gewinnt Spieler 1 oder wird seinen letzten Stein los,
unmittelbar nachdem Spieler 2 seinen letzten Stein gelegt hat.
Und dann ist der Stein dafür da, dass das nicht passiert.
Ich glaube, es ist so etwas wie, wenn es 6 Knoten und 5 Kanten gibt,
und dann fängt der Knotenspieler an, und dann machen sie das alles
gut, und dann nach 5 Knoten legt der Kantenspieler seine fünfte Kante
und ist damit im Prinzip fertig, und dann ist vielleicht per
Definition das Spiel vorbei, und Spieler 1 ist seine Steine nicht
losgeworden.
Ja, dafür wird es sein.
Okay.
Gut, also es geht nur darum zu gucken, ob Spieler 1 noch einen Stein
legen kann, oder er hat noch Steine auf der Hand, kann aber keinen
legen.
Das sind die beiden Möglichkeiten.
Wir haben einfach diese dritte Möglichkeit, dass Spieler 2 schon
fertig ist, jetzt ausgeschlossen mit diesem Sternchen.
Gut.
So, jetzt, warum machen wir das?
Naja, die Steine von Spieler 1, die passen nicht aneinander.
Also, die einzige Möglichkeit zu machen ist, Spieler 1 fängt an,
Spieler 2 legt eine Kante, Spieler 1 muss wieder an die Kante
rangehen.
Und dann sind wieder beide Enden mit Knoten belegt, und ich kann nicht
als Spieler 1 an die Knoten rangehen, weil die nicht passen.
Die haben ja das jüngste Zahlenwerte.
Also, die einzige Möglichkeit ist, dass alternierend immer Knoten,
Kante, Knoten, Kante gespielt wird.
Und, ach ja, die Reduktion, also die Größe der Instanz, die wir jetzt
gerade gebaut haben von Domino, die muss natürlich polynomiell sein in
der Instanz von Hamilton Path.
Und das ist ganz klar, das ist hier nur linear in Anzahl Knoten plus
Kanten.
Gut, jetzt ist die Behauptung, die schon ein bisschen durchschimmert,
das ist immer so.
Wenn wir diese Reduktion aufbauen, dann bauen wir sie natürlich auf,
sodass sie funktioniert.
Und da ist immer schon die Motivation, warum wir das so definieren,
schon immer mit drin.
Und dann letztendlich kommt es einem so vor wie, warum müssen wir
jetzt überhaupt noch was zeigen?
Aber wir müssen dann natürlich noch formal zeigen die Behauptung, wenn
Hamilton Path eine Lösung hat, dann hat auch Domino eine Lösung, und
wenn Domino eine Lösung hat, dann auch Hamilton Path.
Also Spiele 1 gewinnt Cooperative Domino, genau dann, wenn die Domino
-Kette einen Hamilton Path in G beschreibt.
Das hier soll mal als Illustration dienen.
Das ist tatsächlich propiert aus einem Papier von 2014 von Eric DeMain
und Marr und Weingarten, die das so untersucht haben.
Und hier wäre eine Beispielinstanz von einem Grafen, und hier sind die
Knoten zufälligerweise 1 bis 6.
Dann hätte Spieler 1 diese 6 Steine, und der Graf hat jetzt 7 Kanten,
das heißt Spieler 2 kriegt diese 7 Steine.
Hier zum Beispiel Stein 2, 3 für die Kante von 2 nach 3.
Und tatsächlich hat dieser Graf einen Hamilton Path, in dem wir von 6
nach 4, 3, 2, 5, 1, beispielsweise, und so legen die das in die
Ordnung aus.
6, 4, 3, 2, 5, 1.
Okay?
Okay.
Formal gibt es zwei Richtungen zu zeigen, wie immer.
Wir nehmen erstmal an, es ist die Richtung von links nach rechts.
Also Spieler 1 gewinnt, daraus muss folgen, dass es einen Hamilton
Path hat.
Also Spieler 1 hat einen Stein für jeden Knoten, und Spieler 2 für
jede Kante.
Wenn Spieler 1 anfängt, dann fängt es an, und alle Steine gelegt hat,
dann müssen sozusagen alle seine Steine auf dem Tisch sein.
Und die müssen durch Kanten verbunden sein, das ist ja eine
Dominokette.
Und die Kanten haben nach den Dominoregeln die richtigen Endpunkte,
sodass man das wiederum in den Path auf den Grafen übertragen kann.
Und weil er jeden Knoten benutzt, und genau einmal benutzt, ist es ein
Hamilton Path.
Rückrichtung, wenn es einen Hamilton Path gibt, dann sind unsere
schlauen Spieler fähig, den zu identifizieren und ihr Dominospiel
entlang dieses Hamilton Paths zu planen und ihre Steine aus.
Das heißt, das ist die Rückrichtung.
Das heißt, um zusammenzufassen, da Hamilton Path NP schwer ist, und
wir vorher gezeigt haben, dass Cooperative Domino in NP liegt, gilt,
dass Cooperative Domino NP vollständig ist.
Erinnerung, solche Antwortsätze sind immer sehr schön auf der Klausur.
Nicht irgendwie mitten im Argument aufhören, weil manchmal sieht es so
aus, als ob sie keine Zeit mehr hatten oder keine Lust mehr und die
Aufgabe aufgehört haben.
Dabei haben sie gedacht, ist doch jetzt alles klar.
Alle entscheidenden Ideen waren noch schon da.
Also auch wenn es ein bisschen langweilig und wiederholend ist am
Ende, nochmal den Antwortsatz, wir haben also gezeigt.
Ja, so, das war nur so ein kleiner Exkurs, der vielleicht auch nochmal
NP -Vollständigkeitsreduktion aufgezeigt hat und der auch ein bisschen
Spaß macht.
Ich kriege keine Gelder von der Domino-Industrie, um sie zum
Dominospielen zu bewegen, aber ich kann es ihnen wirklich ans Herz
legen.
Wenn Sie keine Fragen mehr haben, es hat mich gefreut.
Das war die letzte Vorlesung von TGI.
Viel Glück, Erfolg und Spaß bei der Klausur.