So, herzlich willkommen zur sechsten Übung.
Wir werden heute als erstes das Kapitel 7a in der offiziellen
Nomenklatur fertig machen.
Danach werden wir uns kurz nochmal Substitutionen und Unifikationen
anschauen.
Anschließend möchte ich gerne eine kurze Pause einlegen, um danach
dann den Prolog vorzuführen.
All diejenigen, die Prolog schon in der Schule hatten oder Prolog
sonst wie auch schon kennen, die seien herzlich eingeladen, sich das
anzugucken.
Können aber wahrscheinlich auch genauso gut gehen, weil wir nicht
wirklich tief in Prolog einsteigen.
Wird wahrscheinlich wenig Neues für Sie dabei sein.
Das schon mal vorab.
Gut, wir haben in der letzten Übung am Freitag gesprochen vom Aufwand.
Wir haben gesagt, wir definieren erstmal einen gewissen Umfang N und
gehen da im Allgemeinen von der Anzahl der Eingabewerte aus.
Also zum Beispiel von der Anzahl der Listen-Elemente.
Das ist relevant beim Sortieren oder beim Einfügen.
In anderen Fällen, wie zum Beispiel Verschlüssungs-Algorithmen wie RSA
oder Tripledesk, kommt es mehr darauf an, wie viele Bits der Schlüssel
enthält.
Und deswegen ist die Eingabe dann in dem Fall tatsächlich von der
Anzahl der Bits abhängig.
Dann haben wir definiert den Aufwand T von N.
Und das ist ganz abstrakt die Anzahl der Zeit- und Speichereinheiten,
die wir brauchen, um zu einem ganz bestimmten Algorithmus das Problem
zu lösen, wenn der Umfang der Eingabe eben N beträgt.
Die Komplexität war der geringst mögliche Aufwand, mit dem man das
Problem lösen kann.
Wir hatten gesagt, wir gehen davon aus, dass wir konstante Faktoren
rauslassen.
Wir betrachten nur Zeit- und Speichereinheiten und sagen gar nicht,
wie groß die sind.
Das ist einfach eine Konstante, die wir rauskürzen.
Ob unsere Zeiteinheit jetzt eine Millisekunde oder zwei Millisekunden
oder drei Millisekunden oder fünf Sekunden ist, ist uns völlig
wurscht.
Insofern, da wir da eine Konstante haben, würde auch ein zusätzlicher
Prozessor ja diese Konstante gerade mal durch zwei teilen.
Insofern sagen wir, wir gehen davon aus, wir haben einen Prozessor mit
unbeschränkt großem Hauptspeicher und unsere Speicherzellen sind
beliebig lang.
Wenn es natürlich nur gerade darauf ankommt, dass unsere Eingabe zum
Beispiel Zeichenketten sind und wir die Anzahl der Zeichen eben als
Umfang betrachten, dann ist eine Speicherstelle natürlich nicht eine
Zeichenkette in aller Regel.
Also da müssen Sie dann mit der Definition schon ein bisschen
aufpassen.
Das Ganze nennen wir Random-Access-Maschine und die ist die Grundlage
für den sogenannten O-Kalkül.
Den hat ein deutscher Zahlentheoretiker mit Namen Edmund Landau, einer
schönen Stadt hier an der südlichen Mainstraße, aber da sind sogar
einige Vertreter da.
Ob die jetzt tatsächlich zusammenhängen, die beiden, das will ich
jetzt nicht beschwören.
Jedenfalls, ich habe Ihnen erzählt von dem konstanten Faktor K.
Dieser konstante Faktor K gilt aber tatsächlich nur für einen Umfang,
der erheblich ist.
Das heißt, wenn mein N praktisch gegen unendlich geht, für einen
kleineren Umfang kann es durchaus sein, wenn wir jetzt zum Beispiel
mal hier den Umfang betrachten von 0 bis 10 für die Eingabe N, also
für den Umfang von N, dann kann es durchaus sein, dass hier ein
Algorithmus mit der blauen Kurve besser ist als ein Algorithmus mit
der grünen Kurve.
Ab einem gewissen Punkt jedoch wird ein höherer Aufwand uns insofern
das Ganze verändern, als Sie sehen, dass uns hier der blaue
Algorithmus wirklich abhaut und extrem teuer wird zum Berechnen, der
grüne Algorithmus aber immer noch linear bleibt und weiter wächst.
Da uns konstante Faktoren nicht interessieren, ist es auch
hinreichend, wenn wir interessante Operationen zählen.
Das heißt, wenn jetzt in der ersten Zeile Plus, in der zweiten Zeile
Minus und in der dritten Zeile Mal gerechnet wird oder sonst irgendwas
zwischen irgendwelchen Zahlenwerten, dann ist uns das eigentlich egal.
Dann ist halt eine Operation in dem Moment dreimal so lang.
Die theoretische Grundlage für das werden wir auch gleich noch sehen.
Zunächst einmal wollen wir uns aber so zum Abschätzen, dass wir mal
ungefähr einordnen können, wovon wir denn überhaupt reden, mal so
verschiedene Funktionsklassen anschauen, die es denn so gibt.
Und wenn wir von Aufwand sprechen, dann sprechen wir nicht von Aufwand
wie in der Form, der Algorithmus ist doppelt so aufwendig wie der.
Das gibt es nicht bei uns.
Das ist eine Funktionsklasse, sie erinnert sich an die Konstante.
Die zwei kann ich einfach rausziehen und damit sind die gleich
aufwendig und feierabend.
Dann nehme ich halt einfach einen schnellen Rechner, also warte
anderthalb Jahre, sind die Prozessoren doppelt so schnell und dann ist
die Sache wieder erledigt.
Wenn wir von Aufwand sprechen, sprechen wir wirklich von
Funktionsklassen, wo es richtig heftig wird.
Das heißt, wir haben jetzt zum Beispiel den Jahrenaufwand hier
aufgetragen.
Also wir haben an beiden Skalen Logarithmus.
Das heißt, dass wir sämtliche n hoch i als gerade haben hier.
Und Sie sehen, dass n² natürlich deutlich stärker steigt als n und n
hoch 3 steigt nochmal stärker.
Und Sie sehen an diesem Beispiel von 2 hoch n, zum Beispiel auch was
mit dieser blauen Kurve eben gemeint war, dass es vorher, also bis 8,
schon sein kann, dass ein Algorithmus mit 2 hoch n effizienter wäre
als einer mit n hoch 3.
Aber Sie sehen, dass wenn Sie dann mehr als wegen mir 8 Zeichen
verarbeiten wollen oder wenn Sie eine List mit mehr als 8
Zeichenketten sortieren wollen oder sowas in der Richtung, dann wird
das halt wirklich deutlich der Unterschied.
Die Funktionen, die wir zur Verfügung haben, sortieren wir in
Funktionsklassen ein.
Das heißt, egal wie jetzt unser Algorithmus tatsächlich aussieht, ob
er jetzt einmal so aufwendig oder doppelt so aufwendig ist, für uns
ist nur relevant, in welcher dieser Funktionsklassen er reinfällt.
Und diese Funktionsklassen werden eben so, wie hier drauf auf der
Folie steht, definiert.
Das heißt, die Klasse der Funktionen Groß-O von f von n sind all
diejenigen Funktionen g von n, für die gilt 0, logischerweise ist der
Aufwand immer nach unten, wenn wir nichts zu tun haben, sind wir am
schnellsten, ist kleiner gleich dieses g von n, ist kleiner gleich
irgendeinem c von n mal f von n.
Das heißt, es gibt irgendeine Konstante, sodass ab irgendeinem n dann
praktisch der Funktionswert hier immer größer ist, größer gleich als
diesem g von n.
Das ist einfach die Klasse der Groß-O von f von n.
Für f von n setzen wir dann zum Beispiel eine von diesen hier
aufgeführten Funktionen ein, also zum Beispiel 2 hoch n oder n log 2
von n.
Und genauso definieren wir ebenfalls klein-o von n, nur fordern wir
hier, dass für alle c größer 0, dass wir da irgendein n finden, sodass
das größer ist.
Das heißt, Groß-O und Klein-O von f von n sind, ich sag mal, so eine
Art obere Schranke für das Ganze.
Da können Sie sagen, naja, mein Algorithmus ist auf jeden Fall nicht
so aufwendig wie die Funktion, die hier drin steht.
Wenn ich die griechischen Buchstaben nehme, also Groß- und Klein
-Omega, sind das in dem Fall praktisch untere Schranken, die ich
angeben kann.
Dass der Algorithmus also nicht weniger aufwendig ist, sondern auf
jeden Fall mehr aufwendig.
Und wenn das Ganze ziemlich parallel ist, also diese Bedingung hier
erfüllt, dann ist der Algorithmus in der Funktionsklasse Theta von n.
Das heißt für Sie, im Endeffekt, Sie müssen hier die fünf Definitionen
einmal lernen, dann wissen, und dann können Sie damit auch Mathematik
betreiben.
Erstmal nochmal zur Bedeutung.
Wir sprechen davon, dass eine Funktion g in der Klasse Groß-O von f
von n ist, wenn g höchstens so schnell wächst wie f.
Wenn Sie sich das durchlesen, nachvollziehen und dann hiergegen
prüfen, dann sehen Sie, dass das praktisch hier die formale
Schreibweise ist für das, was hier in der ersten Zeile steht.
So sagen wir, dass wenn eine Funktion aus Klein-O von f von n ist,
dass sie dann deutlich langsamer wächst als eben dieses f.
Wenn sie aus Groß-O von f von n ist, dann wächst sie mindestens so
schnell wie f.
Wenn sie aus Klein-O von f von n ist, dann wächst sie deutlich
schneller als f.
Sie sehen, das sind also quasi diese unteren Schranken zum Abschätzen.
Und wenn sie aus Theta von f von n ist, dann wächst sie eben genauso
schnell.
Wir haben auf dieser Folie ein Beispiel angegeben.
Sie erinnern sich, Entschuldigung, an die Addition der Elemente oder
aller Elemente einer Liste mit n Einträgen.
Die ist offensichtlich in der Klasse O von n, weil das ist linear.
Ich muss, wenn ich sie alle addieren will, jedes Element nehmen und zu
meiner aktuellen Summe dazuzählen.
Ich kann es also nach oben beschränken.
Es wächst höchstens so schnell wie die Funktion n.
Sie wissen, wir ignorieren Konstanten.
Sie wächst aber auch mindestens so schnell wie die Funktion n in dem
Fall.
Das heißt, sie ist in Groß-O von n, sie ist in Groß-Omega von n und
deswegen auch in Groß-Theta von n.
In diesem Fall sagt man, Sie haben das vielleicht schon hin und wieder
in der Vorlesung gehört, das Ding hätte linearen Aufwand.
Sie haben davon gehört, dass wir von exponentiellem Aufwand sprechen.
Das wäre zum Beispiel genau dann der Fall, wenn wir eben hier 2 hoch n
als Funktion in dem Groß-O angeben würden in der Funktionsklasse.
Machen Sie sich begreiflich, anhand all dieser Formeln, dass wir hier
tatsächlich den konstanten Faktor stehen haben, den wir im Endeffekt
ignorieren wollen.
Das heißt, es existiert einen.
Das Ganze ist nicht konstruktiv, wir geben gar nicht an, was das für
einer ist.
Wir sagen nur, es existiert einer.
Und das andere, was eben wichtig ist, ist, dass wir den Umstiegspunkt,
den sogenannten, beachten.
Und das ist eben genau dieses n0, ab dem dann eben f von n tatsächlich
größer ist als das g von n.
g von n ist ja an dieser Stelle größer als das f von n.
Aber ab unserem Umstiegspunkt ist nämlich f von n tatsächlich größer.
Und dann stimmen die Aussagen, die wir eigentlich treffen.
Zum O-Kalkül gibt es einige Rechenregeln.
Die sind eigentlich recht einfach.
Die sollen aber der Vollständigkeit halber alle mal erwähnt sein.
Und Gelegenheit, das Ganze auf einem Übungsblatt zu üben, bekommen Sie
auch noch.
Nicht auf diesem Übungsblatt, aber auf einem der nächsten.
Wenn jetzt die Funktion f von n aus Groß-O von r von n ist und g von n
aus Groß-O von s von n ist, dann ist f von n plus g von n, wenn wir
diese beiden zusammenzählen, in Groß-O von r von n plus s von n.
Wie Sie auf dieser Folie schon sehen, ist Groß-O eigentlich die
wichtigste Funktionsklasse, mit der man im Allgemeinen arbeitet.
Das ist immer so die Abschätzung nach oben, die man ganz gerne hätte.
Weil wir möchten ja angeben, möglichst, wir haben gesagt, Groß-O
wächst höchstens so schnell wie f.
Wenn es deutlich langsamer wächst als f, dann ist natürlich immer gut
angeben, wenn wir ein klein o von 2 hoch n betrachten, dann ist da
natürlich so ziemlich fast alles drin.
Alles wächst viel langsamer als das.
Also wir möchten schon mit der Schranke wieder so weit wie möglich
nach unten gehen.
Okay, das ist jetzt auch ein Beispiel für das, was ich vorhin sagte,
wenn wir eine Addition und dann eine Subtraktion und dann eine
Multiplikation haben.
Das heißt, wir haben den Aufwand von der Addition mit O von 1, wir
haben den Aufwand für die Subtraktion mit O von 1 und den von der
Multiplikation von O von 1.
Wenn wir die drei addieren, dann hätten wir hier stehen, Groß-O von 1
plus 1 plus 1 ist 3, Groß-O von 3 ist das gleiche wie O von 1.
Das heißt, wir haben immer noch die Funktionsklasse O von 1 für diesen
Rechenschritt.
Das sind einfach nur, das verstecken wir in der Konstante.
So, was wichtig ist zu bemerken, ist, dass diese Funktionsklassen
natürlich Mengen sind.
Jedoch schreiben wir oftmals auch, dass G von N gleich O von F von N
ist, statt G aus O von F von N.
Und das ist also, auch wenn Sie das auf dem Übungsblatt oder in der
Klausur tun, völlig okay, weil wir eben so gut auch damit rechnen
können, wie wir das gerne hätten.
Wenn wir jetzt irgendeine dieser Funktionsklassen hätten, für V setzen
wir jetzt also Groß-O ein oder Klein-O oder sonst irgendwas, dann
gelten die hier aufgeführten Rechenregeln.
Beispielsweise, wieder sehr interessant ist dann wieder die da, wenn
wir konstant oft etwas hier von machen, was in irgendeiner
Funktionsklasse liegt, wirklich egal welche, dann ist das immer noch
die gleiche Funktionsklasse.
Das heißt, ob wir einmal addieren oder drei Additionen untereinander
haben, ist uns völlig wurscht, bleibt immer die gleiche
Funktionsklasse.
Was auch interessant ist, ist eben, dass wenn ich hier so eine
Multiplikation habe, das heißt, wenn ich zum Beispiel eine Schleife
habe und in der Schleife mache ich etwas, dann hat die Schleife selber
natürlich einen gewissen Aufwand, ich sage jetzt mal N, und das, was
innen drin hat, hat auch einen gewissen Aufwand, M.
Und Sie sehen natürlich sehr leicht ein, dass der Gesamtaufwand davon
dann natürlich N mal M ist und eben sich nicht, auf keinen Fall, in
keiner Weise in einer Konstante verstecken lässt.
Wir haben jetzt hier einige Beispiele angegeben zur, wie gesagt,
wichtigsten Klasse Groß-O.
Wenn wir eine Funktion haben, die Konstant 2 ist, das heißt, egal was
wir reinfüttern in unseren Algorithmus, der braucht immer 2.
Diese 2 können wir prima in der Konstante verstecken, also ist das die
Klasse O von 1.
Auch Pi ist konstant, das ist deshalb in der Klasse O von 42.
Wieso O von 42?
Das ist genau das Gleiche wie O von 1.
Jetzt steht hier, die Funktion 1 sei in der Klasse O von N-Fakultät.
Wie kommt denn das zustande?
Kann sich das jemand erklären?
Ja, bitte.
Sie haben recht.
Also in der Tat ist das natürlich auch in der Klasse N-Fakultät.
Es geht ja darum, Groß-O ist eine obere Schranke.
Ich kann ja meine obere Schranke so hoch wählen, wie ich will.
Natürlich interessiert mich immer eine möglichst kleine obere
Schranke.
Aber die Aussage hier ist in der Tat völlig korrekt, wenn auch für uns
eher nutzlos.
Interessanter wird es dann wieder, wenn wir uns diese Zeile angucken.
N² plus N.
N, das heißt, das ist ja schon erheblich, dieses N.
Da ist ja schon was, was von der Eingabelänge deutlich abhängig ist.
Aber wir sagen trotzdem, dass es in der Klasse O von N² ist.
Warum?
Na ja, wenn wir das N hinreichend groß wählen, wenn wir weit genug
rausschwimmen, dann ist es ziemlich egal, ob da noch plus N dazukommt
oder nicht mehr plus N dazukommt.
Wenn Ihr Algorithmus wegen diesem ersten Faktor hier schon 10 Jahre
zum Berechnen braucht, dann ist Ihnen egal, ob er wegen dem zweiten
Faktor noch eine Stunde zusätzlich braucht oder nicht.
Deswegen ist das hier praktisch in dem Moment der dominierende Term.
Logischerweise, Sie denken dran, mit dem Konstanten, das können wir
hier wieder rausnehmen, weil das wieder also O von 2N² ist eben das
Gleiche wie O von N².
Das ist diese Abschätzung.
Und hier haben wir es dann noch ein bisschen weitergetrieben und Ihnen
einfach mal gezeigt, es ist wirklich wurscht, was Sie da hinten dran
schreiben und auch was Sie da vorne dran schreiben.
Das Einzige, was uns interessiert, ist praktisch dieser größte Term
hier innen drin.
Und so sehen Sie dann auch für weiter angegebene Funktionen, wie dann
da die Klasse dazu aussähe.
Interessant wird es an solchen Stellen hier.
Das heißt, da müssen Sie dann tatsächlich Ihre Analysekenntnisse
auspacken und dann eben nachgucken, welches von den beiden der Term
ist, der schneller wächst.
Und dabei kommt dann eben raus, dass das Wurzel aus N ist.
Sie haben in der letzten Vorlesung bei Herrn Groß kennengelernt, dass
es Probleme gibt, die sich mit linearem Aufwand lösen lassen, dass es
welche gibt, die sich mit polynomiellem Aufwand lösen lassen und
welche, die sich eben nur mit exponentiellem Aufwand lösen lassen.
Interessant ist für uns, ob es eine Funktion gibt, die sich mit
polynomiellem Aufwand lösen lässt und das ist eigentlich nur so ein
Vorgriff auf Info 3 und auch formale Systeme.
Uns interessiert dann, gibt es tatsächlich einen Algorithmus mit
polynomiellem Aufwand oder ist es eben der exponentielle Aufwand, der
mir dann eben extrem nach oben abhaut.
Interessanter ist an dieser Stelle noch diese Tabelle, in der einfach
mal so ein paar Abschätzungen für Sie sind.
Das heißt, die Funktion Logarithmus von N ist für Eingabewerte von 1
gleich 0.
Von 10 gleich 2, 105, 1007 und 1009.
Für die Funktion N ist es natürlich 1, 10, 100, 1000 und 10000.
Und für NlogN, was jetzt der Aufwand für den besten Sortieralgorithmus
ist, den es geben kann, das kann man sogar dann beweisen, dass es
nicht tiefer geht.
Sie erinnern sich, das habe ich Ihnen das letzte Mal schon umrissen.
Man kann beweisen, dass Algorithmen oder dass Probleme eine gewisse
Komplexität haben, die man nicht unterschreiten kann.
Sie können so lange Algorithmen basteln, wie Sie möchten.
Sie werden keinen finden, der besser ist und da kann man das dann
sogar garantieren, dass wenn Sie einen finden, der NlogN hat, dass der
dann in der Klasse der besten Algorithmen drin ist.
Was Sie hier sehen können, ist, dass NlogN wirklich sehr wenig
schneller wächst als O von N oder als N.
Und dass jetzt hier in der Tat ich das N ziemlich groß wählen muss,
dass da ein deutlicher Unterschied ist.
Sie erinnern sich, wir haben auch nie gesagt, wie groß oder wie klein
die Konstante sein darf.
Und wenn die Konstante, sagen wir mal, 11 ist, dann ist der
Umstiegspunkt hier bei weitem noch nicht erreicht.
Und wenn Sie aber wissen, Ihre Eingaben umfassen nie mehr als 10.000
Elemente, dann wissen Sie sogar, dass ein Algorithmus der Form mit dem
Aufwand NlogN dann immer noch besser ist, als wenn Sie hier mit dem
Aufwand N aber eine internen Konstante von 11 haben.
Okay, und was Sie halt eben an dieser Stelle noch sehen, ist, dass Sie
bei einem quadratischen Aufwand natürlich sehr schnell sehr stark
wachsen, aber bei einem exponentiellen Aufwand, hier E hoch N statt 2
hoch N, aber das ist eigentlich auch egal, dass Sie da so schnell so
weit abhauen, dass da ein Haufen Malz verloren ist und Sie tunlichst
auf jeden Fall so einen Algorithmus vermeiden wollen.
Sie überlegen sich an dieser Stelle sehr leicht, wir können natürlich
dieses N halbieren, wenn wir sagen, wir nehmen zwei Prozessoren, um
das Ganze auszurechnen.
Aber Sie sehen auch, wenn ich jetzt zum Beispiel im Falle eines RSAs
oder sonst was in der Richtung, einfach nur ein zusätzliches
Schlüsselbit dazunehme, weil der Schlüssel ist der, der da oben steht.
Wenn ich da nur ein Bit dazunehme, dann habe ich schon zwei
Prozessoren wieder erschlagen.
Nehme ich zwei Bit dazu, dann habe ich vier Prozessoren, nehme ich
drei Bit dazu, das ist noch nicht mal ein Byte.
Wir sprechen noch nicht mal über ein halbes Byte im Moment.
Und dann habe ich schon acht oder sechzehn Prozessormaschinen
ausgeschlossen.
Und so geht das natürlich weiter.
Und das ist jetzt die Grundlage, die Sie einfach mal kennen sollten,
um besser zu verstehen, dass wenn Herr Goos oder ich von Aufwand
sprechen oder von Klassen oder sonstigen Dingen, dass Sie dann wissen,
wie Sie das Ganze einordnen können.
Lesen Sie das Ganze mal in Ruhe durch.
Die Gelegenheit, es zu üben, werden Sie sicher auch noch bekommen.
So.
Wo wir gerade davon sprechen, warum bekommen Sie die Gelegenheit, das
zu üben, nicht auf dem aktuellen Übungsblatt?
Nun, das aktuelle Übungsblatt ist leider ein bisschen lang geworden.
Es ist ziemlich leicht, die Tutoren fanden es alle gut, aber leider
etwas lang.
Ich sage einfach nur Mut, packen Sie es an.
Es ist also schnell gemacht, sage ich mal.
Woran ich Sie in dem Zusammenhang auch noch erinnern möchte, ist, dass
wir eine Probeklausur schreiben.
Und das am 19.12.2003.
Und zwar von 14 Uhr bis 15.30 Uhr hier in diesem Hörsaal.
Mein Tipp an Sie ist, versuchen Sie jetzt schon mal anzufangen, das
Lernen zu üben.
Das klingt jetzt vielleicht ein bisschen albern, aber Sie müssen
einfach etwas effizienter lernen, als Sie das bisher in der Schule
machen konnten, weil, wie Sie gemerkt haben, die Stoffdichte hier
erheblich höher ist.
Das heißt, Sie haben für Ihre Klausuren im Allgemeinen schlicht und
ergreifend nicht so viel Zeit wie in der Schule.
Das heißt, Sie müssen das Lernen üben.
Das war auch für mich ein schmerzhafter Prozess, bis ich das dann
endlich konnte.
Sie müssen sich hinsetzen, Sie müssen sich lange konzentrieren, Sie
müssen den ganzen Stoff wiederholen.
Es reicht nicht aus, wenn Sie die Folien durchlesen und denken, das
habe ich alles verstanden.
Das klappt leider nicht.
Sie müssen es wirklich, Sie müssen sich Klausuren besorgen in der
Fachschaft, Sie müssen diese Übungsaufgaben rechnen, Sie müssen den
ganzen Stoff einfach aus dem FF reproduzieren können.
Die Aufgaben sind allesamt auf der Klausur deutlich eindeutiger als
auf dem Übungsblatt, aus dem einfachen Grund, da wir die
Klausuraufgaben noch sorgfältiger prüfen und auch von anonymen
Testrechnern so lange gegenrechnen lassen, bis möglichst keine Fragen
mehr auftauchen.
Sie sind aber höchstwahrscheinlich trotzdem genug, dass auch weitere
Fragen während der Klausur auftauchen wollen.
Das ist natürlich etwas, was wir verhindern wollen.
Die Aufgaben sind aber in aller Regel deutlich präziser als auf dem
Übungsblatt.
Die Aufgaben sind auch leichter als auf dem Übungsblatt, sage ich mal.
Aber Sie haben das Problem, dass Sie nur eine Stunde haben.
Das heißt, Sie können sich nicht hinsetzen und lange über die Aufgaben
überlegen.
Sie müssen den Stoff einfach beherrschen.
Natürlich können Sie sich den ganzen Stoff innerhalb, sagen wir mal,
10 Minuten, einer halben Stunde herleiten, wenn Sie den Überblick über
den kompletten Stoff haben.
Aber das Problem ist, dass Sie die Zeit in der Klausur nicht haben.
Das heißt, Sie sollten jetzt schon mal anfangen zu üben.
Warum sollten Sie das tun?
Das ist Ihre erste Möglichkeit, tatsächlich das Klausurfeeling
mitzubekommen, wie das Ganze so ist.
Also wie das mit dem Stress ist, mit dem Vorbereitungsstress, mit dem
Anmelden und solchen Dingen, alles zusammen.
Und in Ihrem Interesse, also es geht für Sie um nichts, Sie kriegen
keine Punkte dafür.
Wenn Sie da durchfallen, haben Sie sich nichts verbaut oder sonst
irgendwas.
Es ist nur für Sie ein Angebot, dass Sie das mit der Klausur schon mal
üben können, damit Sie dann im Februar, am 20.
Februar, alle fit sind und vielleicht nicht ganz, aber ein bisschen
alte Hasen sind und wissen, wie man Klausuren am besten vorbereitet
und schreibt.
Dazu eine Frage, ja?
Alte Klausuren bekommen Sie in der Fachschaft, da laufen Sie in die
Fachschaft und...
Ach so, alte Probeklausuren bekommen Sie nicht.
Sie bekommen nur alte, normale Klausuren.
Aber sagen wir mal, den Stoff, den wir bis Weihnachten haben, an dem
ändert sich ja nichts mehr.
Das heißt, wenn Sie auf diese Probeklausur lernen, haben Sie sich
natürlich auch einen Gefallen getan, indem Sie dann im Februar nicht
mehr so viel lernen müssen.
Weil Sie den Stoff ja dann schon mal gelernt haben.
Und daran werden Sie dann auch feststellen, dass etwas, was Sie schon
mal begriffen haben, halt auch auf jeden Fall schneller wieder zu
lernen geht.
Aber Sie halten das, wie Sie wollen.
In dieser Klausur geht es um nichts.
Wenn Sie keine Lust haben, sie mitzuschreiben, brauchen Sie an dem Tag
auch gar nicht zu kommen.
So, wiederholen möchte ich an dieser Stelle die Substitution.
Und zwar,
wie war das?
Wie wenden wir denn eine Substitution auf einen Term an?
Unsere Substitution, im Allgemeinen bezeichnet man sie mit Sigma, hin
und wieder auch mal als Tau, schreiben wir als eckige Klammer auf, S-V
zu.
Das bedeutet, dass wir das hier durch das hier ersetzen wollen.
Also,
was heißt das?
Und wie gehen wir dafür vor?
Das hört sich jetzt zunächst mal einfach an.
Problem ist aber, wenn sich da Dinge überkreuzen, dann kann man sich
verheddern.
Darum geben wir hier einen Algorithmus an, wie Sie Schritt für Schritt
da sicher durchkommen.
Also, wenn T eine Variable ist, also im Speziellen jetzt die Variable
V, dann ist Sigma von T, also der Term, auf dem wir die Substitution
Sigma anwenden, das ist jetzt genau das gleiche, wie wenn wir
schreiben würden T und die Substitution direkt da hinten dran
schreiben.
Also hier ist noch nichts passiert.
Wir haben einfach nur das Sigma eben durch unsere Substitution, unsere
ausgeschriebene Substitution ersetzt und ersetzen jetzt einfach mal
den T, den Term T, durch eben unsere Variable, für die der Term ja
repräsentiert.
Und dann sehen wir, in dem Ausdruck V wollen wir das V durch ein S
ersetzen, also kommt in dem Fall S heraus.
Wenn T jetzt nicht die Variable V ist, sondern irgendeine Konstante C
oder irgendeine andere Variable, eben nicht gleich V, dann ist
offensichtlicherweise die Substitution angewendet auf den Term T, das
gleiche wie der Term T.
Das heißt, wir haben V in diesem Term ja nicht gefunden.
In dem Term steht ja irgendwas anderes drin.
Daher wissen wir, dass wir da nichts zu tauschen brauchen und dann
kommt das Ergebnis raus.
Jetzt kommt der Punkt, wenn der Term eine Funktionsanwendung ist, also
irgendein F aus Sigma, könnte jetzt dann in dem Fall auch G oder sonst
irgendwas sein, und wir haben die Unterterme T1 bis Tn.
Dann ist Sigma von T definiert als F von T Sigma bis Tn Sigma.
Das heißt, wir machen in dem Schritt eigentlich noch nichts, außer das
Sigma jetzt auf alle Unterterme anzuwenden.
Wie sieht das im Beispiel aus?
Wir nehmen mal an, unser Term T sei jetzt F von G von X, H von Y, P
von Q von Z.
Unsere Substitution sei jetzt, dass wir das X durch ein R ersetzen
wollen und das S durch ein Z ersetzen wollen.
Wir wollen T Sigma berechnen, das heißt, wir schreiben unseren Term
hin und einfach das Sigma hintendran.
Da wir jetzt genau den Punkt 3 erreicht haben, da wir eine
Funktionsanwendung haben, ziehen wir das Sigma von hinten einfach zu
allen Untertermen da hinten rein.
Das heißt, unser Sigma wandert jetzt nach hier, hier und hier.
So, jetzt gucken wir im nächsten Fall nach, das heißt, wir haben hier
wieder hinter einer Funktionsanwendung stehen, also ziehen wir das
Sigma wieder innen rein.
Hier sieht es genauso aus, Funktionsanwendung, wir ziehen das Sigma
innen rein.
Und hier haben wir ebenfalls die Funktionsanwendung P von Q von Z,
ziehen das also rein, aber eben noch hinter das Q von Z.
In dem Fall sehen wir, das ist Regel 1, in der wir das X, sollen wir
ja durch das R ersetzen.
Wir sehen hier Y, darauf die Substitution angewendet, das ist weder
das noch das, also wird Y nicht ersetzt, sondern bleibt stehen.
Und wir ziehen das Sigma weiter rein, also das hier war Regel 1.
Gut, wir machen weiter, hier gibt es keine Sigmas mehr, hier ebenfalls
nicht, wir brauchen praktisch nur noch hier hinten Sigma Z zu
berechnen, Z sollte durch S ersetzt werden.
Also haben wir in dem Fall wieder Regel 1 angewendet und eben
tatsächlich das ersetzt.
Ein anderes Beispiel schauen wir uns hier an, und zwar wollen wir hier
das X durch das Y ersetzen und das Y durch das Z.
Und das ist so ein Beispiel, das schief gehen würde, wenn Sie jetzt
einfach naiv ersetzen wollten.
Sie sagen, naja, das X ersetzt sich durch das Y, dann hätte ich ja
stehen, F von G von Y, Komma H von Y.
Ach nee, ich sollte ja das Y ersetzen, F von G von Y durch Z, und
schon wird es dann eben falsch.
Das heißt, Sie müssen erst anfangen, Sie schreiben ja Sigma hinten
dran, Sie ziehen Ihr Sigma rein, mit der Regel 3, so lange, bis Sie
tatsächlich was ersetzen können, das können Sie an dieser Stelle
ebenfalls noch nicht, sondern Sie müssen das Sigma immer noch eins
weiter reinziehen.
Und erst an dieser Stelle, wenn Sie es hier stehen haben, können Sie
was ersetzen.
Das heißt, hier steht X Sigma, das heißt, X wird in dem Fall
tatsächlich durch Y ersetzt, und Y Sigma, das heißt, Y wird durch Z
ersetzt.
Und dann kommt auch der korrekte Term raus.
Also Hinweis an Sie, auf jeden Fall erstmal das Sigma innen
reinziehen, sonst wird es nämlich falsch.
Zur Unifikation, um die nochmal zu wiederholen.
Wir haben gesagt, dass eine Substitution Sigma eine Unifikation für
zwei Terme S und T ist, wenn die Substitution angewendet auf die
beiden Terme, wenn das Ergebnis davon gleich ist.
Genau dann sagen wir, dass Sigma ein Unifikator ist.
Nehmen wir mal an, Sigma ist ein Unifikator und Tau eine beliebige
Substitution.
Dann folgt daraus, dass Sigma Tau ein Unifikator ist.
Warum?
Nehmen wir mal an, V definieren wir als S Sigma und W definieren wir
als T Sigma.
Und da Sigma ein Unifikator ist, ist S Sigma gleich T Sigma.
Einverstanden?
Gut, jetzt haben wir ja genau definiert, dass S Sigma gleich V ist und
W Sigma gleich T.
Also gilt deswegen V gleich W.
So, jetzt wenden wir noch unsere Substitution an.
Da wir ja zwei gleiche Terme haben, müssen die Terme natürlich auch
gleich bleiben, wenn wir die gleiche Substitution auf den gleichen
Termen anwenden.
Wir haben ja nur verschiedene Variablen bezeichnet.
So, und das war aber eben genau S Sigma und T Sigma.
Und das zeigt uns also, dass S Sigma Tau gleich T Sigma Tau.
Und daraus folgt eben, dass Sigma Tau auch ein Unifikator ist.
Sie sehen, dass sich hier an dieser Stelle eine Relation definieren
lässt.
Und diese Relation ist wieder ein Beispiel für eine Quasi-Ordnung, Sie
erinnern sich.
Nehmen wir jetzt mal an, dass unser Sigma ein Unifikator ist.
Und wenn für alle anderen Unifikatoren gilt, dass sie, also da sollte
ich vielleicht dazu sagen, dass die Relation ist allgemeiner als.
Und wenn dann gilt, dass alle anderen Unifikatoren Sigma Strich
allgemeiner sind als unser Sigma, und daraus folgt, dass unser Sigma
auch allgemeiner ist als Sigma Strich, dann sagen wir zu diesem Sigma
der allgemeinste Unifikator.
Da ist natürlich jetzt die Frage, wie findet man denn so einen
allgemeinsten Unifikator?
Das schauen wir uns gleich auf der nächsten Folie an.
Zunächst einmal noch die Anmerkung, dass wir unseren Unifikator Sigma
Tau, der ja bekanntlich nun auch einer ist, den betrachten wir einfach
als untere Schranke, und unseren allgemeinsten Unifikator ist dann
quasi das Supremum, also die größte untere Schranke.
An dieser Stelle noch einmal der Hinweis, dass es sein kann, dass ich
zwei Terme habe, für die kein Unifikator existiert.
Ein sehr einfaches Beispiel ist, wenn ich den Term x, also s gleich x
und t gleich f von x nehme.
Da können Sie für x natürlich beliebiges einsetzen.
Sie kriegen das f, Klammer auf, Klammer zu, außenrum rum, um das x in
keinster Weise weg.
Sie können da also nichts einsetzen, sodass das f verschwindet.
Das bleibt Ihnen immer stehen und deswegen werden die Terme garantiert
niemals gleich.
Um zu einem Unifikator zu kommen, schauen wir uns den
Unifikationsalgorithmus von Robinson an.
Wie Sie sehen, hat er sich schon vor ziemlich langer Zeit über sowas
Gedanken gemacht.
Das macht den Algorithmus aber nicht schlechter.
Der ist immer noch korrekt.
So, dafür müssen wir uns erstmal angucken, was ein Abweichungspaar
ist.
Abweichungspaar ist einfach so definiert, dass es das erste Paar ist
zweier unterschiedlicher Unterterme.
Also unsere Terme sind s und t.
Und dann ist es das erste Paar unterschiedlicher Unterterme, wenn wir,
wichtig, s und t von links durchlesen.
Und als Beispiel haben wir dann hier mal s und t angegeben.
Und wir lesen durch, f ist unterschiedlich.
Naja, und wie Sie dann sehen, kommt dann g von a und h von x und y und
h von z.
Und hier kommt erst das u und dann g von a und h von b und h von c.
So, jetzt könnte man ja hier irgendwie sagen, naja, die sind ja schon
hier ziemlich ähnlich, also ist dann, nee, falsch.
Wie hier steht, es ist das erste Paar unterschiedlicher Terme, wenn
wir s und t von links nach rechts durchlesen.
Das wäre dann also g von a von h von x und u.
Das wäre unser Abweichungspaar.
So haben wir das definiert.
So, und der Algorithmus ist dann ziemlich klar der Nase nach, ziemlich
direkt.
Wir nehmen mal an, wir haben hier unsere beiden Eingaben, unsere
beiden Terme s und t.
Wir fangen an mit einer Substitution, das leere Wort, das heißt, das
Ding substituiert nichts.
Ja, also,
substituieren Sie Ihr Handy im Zustand an mit einem Handy im Zustand
aus.
Danke.
So, gut, also wir fangen erstmal an mit einer Substitution, die gar
nichts macht.
Das heißt, wir lassen alle Variablen zunächst mal so, wie es ist.
Und dann gehen wir in eine Schleife und machen, solange wir ein
Abweichungspaar finden.
Und zwar von sigma s und sigma t.
Sie denken dran, wir haben am Anfang die identische Substitution.
Das heißt, am Anfang, das erste Mal, wenn wir hier reinlaufen, steht
da a von s und t.
Also, das passt dann schon.
Und das definieren wir jetzt hilfsweise als p und q, damit wir mit
denen weiterarbeiten können.
Wenn wir so ein Abweichungspaar finden, dann kann es sein, dass unser
p eine Variable ist und dass dieses p in q nicht vorkommt.
Dann definieren wir oder ergänzen wir unsere Substitution sigma eben
um den Ausdruck, wo wir die Variable p, ja, das ist ja kein Term,
sondern eine Variable in dem Moment, ersetzen durch das, was in q
steht.
Weil das soll ja da praktisch sein am Ende.
Wenn p jedoch eine Variable ist und p in q vorkommt, dann sind s und t
nicht unifizierbar.
Sie erinnern sich an das x und das f von x.
Das wäre dann eben genau so ein Beispiel, dass x die Variable ist,
also unser p, und das aber nur dummerweise in unserem q f von x
vorkommt.
So, das Gleiche, wenn ich keinen Fehler gemacht habe, steht das Ganze
hier nochmal, nur mit verdrehtem p und q, ganz einfach, damit es
vollständig und symmetrisch ist.
Wenn jedoch weder p noch q eine Variable ist, dann gilt, s und t sind
nicht unifizierbar.
Also Sie sehen ein, dass das ziemlich einfach ist.
Gut, wir machen noch ein Beispiel zum Unifikationsalgorithmus.
Das ist dasselbe Beispiel, wie es eben dastand, um unser
Abweichungspaar zu finden.
Wir fangen also an mit der Substitution Epsilon, also wo wir nichts
substituieren.
Das heißt, unser a von s Sigma und t Sigma ist unser a von s und t,
unser Abweichungspaar.
Und dieses Abweichungspaar haben wir ja eben gerade berechnet, g von
a, h von x und u.
Und das definieren wir jetzt als p und q.
So, wir stellen fest, dass diese Regel anwendbar ist.
q ist eine Variable und q kommt in p nicht vor, offensichtlich.
Und deswegen ergänzen wir unser Sigma, um eben diesen Ausdruck hier,
dass wir u ersetzen durch g von a und h von x.
Unser erster Schritt.
So, in unserem nächsten Schleifendurchlauf haben wir unser Sigma
gegeben aus dem Schritt davor, also g von a und h von x.
Setzen wir für u ein und berechnen jetzt erstmal s Sigma.
Das heißt, wir ersetzen in s alle u's durch diesen Ausdruck hier.
Das ist natürlich immer noch das gleiche s, weil da kein u drin war.
Nur hier ersetzen wir dieses u durch eben diesen Ausdruck und haben
dann das hier neu drin stehen.
Der Rest bleibt gleich.
So, wir bilden wieder unser Abweichungspaar.
Das ist in dem Fall, wie Sie einfach sehen.
Also hier vorne ist alles gleich.
Und dann haben wir y und g von a und h von b.
Das haben wir dann hier stehen.
Das ist unser Abweichungspaar.
Definieren wir wieder als p und q.
Wenden unsere Regel an, dass y eine Variable ist, die hier drin nicht
vorkommt.
Ergänzen dann wieder unsere Substitution und haben dann nicht nur das,
was da oben drin stand, drin stehen, sondern eben auch noch zusätzlich
jetzt das hier.
Das machen wir dann weiter.
Ich habe Ihnen die beiden Termine nochmal hingeschrieben zum
Vergleichen.
Wir haben diese Substitution und wenden jetzt auf unser s und unser t.
Die sind also immer noch unsere ursprünglichen.
Diese Substitution an.
Und dann, wie Sie sehr schön sehen, kommt hier vorne tatsächlich
überall das Gleiche raus.
Das ist ja so.
Wir wollen ja, dass die beiden Termine hinterher gleich sind.
Sie unterscheiden sich nur noch da hinten.
Das heißt, sie unterscheiden sich noch nicht mal hier, sondern in der
Tat erst ab hier.
Das ist unser unterschiedliches Ding.
Das ist also z und c und das setzen wir für p und q ein.
Wie Sie sehen, haben wir jetzt zwei Möglichkeiten, Regeln anzuwenden.
Entweder ist p die Variable, die in q nicht vorkommt, so rum, oder ist
eben q die Variable, die in p nicht vorkommt.
Je nachdem sähe unsere Substitution halt eben so oder so aus.
Und Sie sehen ein, dass es damit zwei allgemeinste Unifikatoren gibt.
Und zwar die Substitution, die wir eben hatten, ergänzt um...
Wir setzen c für z ein oder eben z für c.
Sie sehen also, diese allgemeinsten Unifikatoren unterscheiden sich
nur voneinander durch Variablenbezeichnung.
Also, wenn Sie dann auf dem nächsten Übungsblatt sowas rausbekommen,
auf dem Übungsblatt Nummer 7, dann muss es nicht falsch sein, wenn in
der Musterlösung was anderes steht.
So, das war es jetzt dazu.
Wir fangen jetzt nach einer kleinen Pause an mit Prolog.
Und wenn Sie kein Interesse daran haben, Sie können auch gerne draußen
Flieger schmeißen.
Dankeschön.
So, ich würde dann gern weitermachen, wenn Sie so freundlich wären,
den Platz zu nehmen.
Und zwar, warum machen wir denn überhaupt Prolog, wenn wir doch
eigentlich Haskell tun wollen?
Und Haskell möglicherweise schon Ende nächster Woche, aber spätestens
in der übernächsten Woche anfängt?
Na, ganz einfach.
Wir wollen Prolog verwenden als ein Demonstrationsobjekt für die eine
oder andere Technik, um Ihnen überhaupt die ganze Aussagen- und
Prädikatenlogik etwas näher zu bringen.
Und wir machen im Rahmen der Vorlesung in Prolog tatsächlich auch nur
Dinge, für die Prolog gemacht ist, und nicht irgendwelche anderen
Dinge, die man in Haskell tatsächlich besser machen kann.
Das heißt, Sie kriegen keinen besonders tiefen Einblick in Prolog, Sie
kriegen aber so das Notwendigste gezeigt, damit Sie so ein bisschen
damit rumspielen können, um, sagen wir mal so, das Innerste von Prolog
vielleicht mal so erkennen zu können.
So, Prolog ist eine logische Programmiersprache und verarbeitet quasi
Fakten und auch Klauseln.
Und in der Aussagenlogik haben Sie bereits kennengelernt, dass wir
grundsätzliche Aussagen haben, die wir nicht weiter hinterfragen, also
zum Beispiel Zürich hat einen Bahnhof und Bern hat einen Bahnhof und
wir haben irgendwelche Formeln, mittels derer wir dann irgendwelche
Schlussfolgerungen ziehen können.
Zum Beispiel, wenn zwei Städte x und y einen Bahnhof haben, dann sind
x und y miteinander verbunden.
So, in Prolog würde das Ganze dann formal als Klauseln aufgeschrieben
und würde dann so aussehen.
Bahnhof Zürich, Punkt, Bahnhof Bern, Punkt und verbunden x, y ist
genau dann, wenn Bahnhof x und Bahnhof y.
Hierbei gilt es zu beachten, dass wir gewisse Konstantenbezeichner
haben, in dem Fall zum Beispiel Zürich und Bern, und die werden eben
kleingeschrieben und wenn Sie etwas groß schreiben, dann ist es eine
Variable und eine prima Fehlerquelle.
Wenn die Variable aus Versehen klein wurde, dann haben Sie Spaß und
wundern sich, worum es geht.
Damit ich es nicht vergesse, habe ich es gleich mit auf die erste
Folie geschrieben.
Es gibt so den Unterstrich, das heißt, Sie können auch statt dem y
wegen mir irgendwie Unterstrich nur schreiben und das würde dann
bedeuten, dass Sie zwar erwarten, dass an dieser Stelle eine Variable
steht, dass Ihnen aber wurscht ist, was da steht und dass Sie das
nicht weiter brauchen.
Wir sprechen im Prolog von zwei Formen von Klauseln, zum einen von den
Fakten und zum anderen von den Regeln.
Ein Faktum ist eben dieses genannte Bahnhof Zürich und dieses Faktum
können wir dann lesen als den Satz, Zürich hat einen Bahnhof.
Auf der anderen Seite haben wir die Regeln, die mit diesem Doppelpunkt
Minus geschrieben werden und da sagen wir, dass eben zwei Städte
verbunden sind, zwei Städte x und y, genau dann, wenn Sie einen
Bahnhof haben.
Was wichtig ist, dass Sie alles immer mit einem Punkt beenden, sonst
meint Prolog, Ihre Zeile geht noch irgendwo weiter.
Das heißt, hinter jeder Zeile, hinter jedem Befehl, den Sie absetzen,
schreiben Sie einfach immer einen Punkt und im Endeffekt betrachten
Sie das hier, dieses Komma, als ein Und im Prolog.
So, was noch wichtig ist bei der Nomenklatur, ist, dass wir diese
linke Seite hier Kopf nennen und die rechte Seite, also dieses Bahnhof
x, Bahnhof y Punkt, das ist eben der Körper.
Wir haben für diese Schreibweise im Prolog zwei verschiedene
Interpretationen.
Zum einen können wir eine Regel so interpretieren, dass der Kopf gilt,
genau dann, wenn alle Bedingungen des Körpers wahr sind.
Sie erinnern sich, die waren durch Kommas getrennt, also ein Und.
Und bei einem Faktum, das ja bedingungslos wahr ist, das können wir
einfach so interpretieren, dass hier implizit so ein True steht.
Das ist also immer wahr, das Faktum.
Im Prolog spricht man auch gerne von Beweisen.
Der Prolog-Interpreter versucht, für Sie etwas zu beweisen.
Und wenn Sie jetzt zum Beispiel ein Faktum bewiesen haben wollen,
Bahnhof Zürich, dann weiß der Prolog-Interpreter, da es ja nur ein
Faktum ist und hier ja implizit True steht, muss er nichts beweisen,
das ist wahr.
Um aber zu beweisen, dass zum Beispiel X und Y verbunden sind, muss er
erst beweisen, dass X einen Bahnhof hat und Y einen Bahnhof hat und
wenn das beides so ist, dann hat er bewiesen, dass die beiden
verbunden sind.
Das sind einfach so diese beiden Sichtweisen auf ein und dasselbe
Ding.
Wie sieht ein Prolog-Programm aus?
Wenn Sie alle Ihre Prolog-Klausel nehmen, die Sie geschrieben haben
und das zusammenwerfen, dann haben Sie ein sogenanntes Prolog-Programm
und an dieses Prolog-Programm, also hier habe ich Ihnen das als
Beispiel nochmal hingeschrieben, das sei jetzt unser Prolog-Programm,
und dieses Programm beschreibt eben einen gewissen Sachverhalt.
Es repräsentiert ein gewisses Weltwissen.
Und das ist eigentlich auch das Schöne an Prolog, dass Sie hier
überall nur, sagen wir mal, mit den Wörtern aus dem Bereich auch
arbeiten, aus dem Sie kommen.
Sie haben nicht wie in Jahren irgendein Public, Static, Final, Int,
weiß der Kuckuck was, sondern Sie haben eigentlich nur die Wörter, mit
denen Sie umgehen können.
Das heißt, Sie könnten dieses Programm hier fast einem Eisenbahner in
die Hand geben und er wüsste, was damit gemeint ist.
Sie können aber dann eben auch, wenn Sie jetzt für einen
Bäckereifachverkäufer seine Kassensoftware programmieren wollen, dann
können Sie in seiner Terminologie bleiben.
Das ist halt eine schöne Eigenschaft von Prolog.
Und im Endeffekt ist so ein Prolog-Programm nur eine große
Wissensdatenbank, aus der wir bestimmte Dinge ableiten können.
Das steht hier am nächsten Punkt direkt, dass wir uns jetzt hier über
einen bestimmten Sachverhalt informieren können und zum Beispiel eine
Anfrage stellen können, wie ob Zürich und Bern miteinander verbunden
sind.
Das würde dann einfach so aussehen, indem wir hinschreiben, verbunden,
Klammer auf, Zürich, Komma, Bern, Klammer zu Punkt.
Das wäre dann die Anfrage.
So, dann geht der Prolog-Compiler jetzt los oder der Prolog
-Interpreter.
Wir wollen an dieser Stelle einen Interpreter verwenden, der
einfachthalber.
Und versucht dann eben logisch abzuleiten, Sie erinnern sich, Aussagen
- und Prädikatenlogik, einfach abzuleiten, ob er jetzt hier mit Ja
oder mit Nein antworten muss.
Eine weitere Möglichkeit, die wir hier haben, also wir haben nochmal
das gleiche Programm hier stehen, ist, da die Beweise konstruktiv sind
und er nicht nur rät, ob die Antwort jetzt Ja oder Nein ist, sondern
tatsächlich aktiv versucht, zu beweisen, dass dem so ist, können wir
auch Anfrage mit solchen Variablen drin stellen.
Und dann sagt mir der Prolog-Compiler, ja, ich kann das beweisen, also
dass Bern und eine Stadt S verbunden ist, wenn ich annehme, dass S zum
Beispiel Zürich ist.
Und das wird dann eben auch tatsächlich so ausgegeben.
Nein, also er wird sich für irgendeinen Namen entscheiden und den dann
ausgeben.
Wenn Sie alternative Resultate sehen wollen, dann geben Sie da hinten
dran noch den Strichpunkt ein und dann wird er die Entscheidung
rückgängig machen für das S, das müsste hier irgendwo stehen, steht
erst auf der nächsten Folie, und macht dann mit einer anderen Stadt
weiter.
So, Prolog, wer, wie, wo, was wollen wir denn da überhaupt tun?
Wir werden an dieser Stelle, so Sie Prolog in der Schule gemacht
haben, werden Sie den wahrscheinlich kennen, den Open-Source-Freeware
-SWI -Prolog-Compiler benutzen.
Der ist für unsere Fälle mehr als ausreichend.
Was Sie dafür kennen müssen, um das Ding tatsächlich zu benutzen, ist
zunächst einmal die Eingabeaufforderung.
Wenn Prolog irgendwas von Ihnen eingegeben haben möchte, schreibt es
hin, Fragezeichen, Minus.
Und dann sollen Sie irgendwas da hinten dran schreiben und dran
denken, das Ding auch mit einem Punkt zu beenden, sonst wird er Sie so
lange eingeben lassen, bis Sie schwarz sind.
Wenn Sie jetzt Ihr Prolog-Programm geschrieben haben, also Ihre Fakten
und Regeln in einer Datei manifestiert haben, dann können Sie diese
Datei laden mit dem Befehl CONSULT und dann können Sie hier Ihren
Dateinamen reinschreiben.
Wenn Sie die einfachen Hochstriche verwenden, dann sollten Sie dort
auf jeden Fall auch solche Dinge verwenden können, wie eigene Dateien
oder wie heißt das unter Windows?
Einstellungen und eigene Dateien mit Leerzeichen und Üs und Äs und
hast du nicht gesehen, alles drin.
Was aber wichtig ist, ist, dass Sie auf jeden Fall immer die
Vorweisstriche verwenden, auch unter Windows.
So, wenn Sie jetzt ein paar Anfragen gestartet haben und irgendwie
festgestellt haben, das ist irgendwie nicht so ganz genau das, was ich
machen wollte, um jetzt kurzerhand mal ein Faktum leicht abzuändern
oder sowas, geben Sie einfach EDIT ein und einen Punkt hinten dran,
dann wird er Ihren Windows-Standard-Editor öffnen und Ihnen darin dann
Ihre aktuelle Datenbasis zeigen.
Allgemein zur Hilfe kommen Sie, wenn Sie den Befehl HELP mit Punkt
eingeben und wenn Sie jetzt zu einem bestimmten Befehl, wie zum
Beispiel EDIT oder CONSULT Hilfe haben wollen, dann geben Sie einfach
HELP mit dem Parameter des Namens der Funktion an.
Dann kommen Sie dazu.
Wenn Sie die Nase voll haben, dann tippen Sie HALT und danach einen
Punkt und dann sind Sie es los.
Wie funktioniert jetzt PROLOG intern?
Meine Damen und Herren, wenn Sie eine Anfrage stellen und PROLOG das
Ganze beantworten soll, dann sucht PROLOG von oben nach unten.
Nach irgendeiner Klausel, also einem Faktum oder einem...
So, wenn PROLOG ein Faktum findet, dann wissen wir, dieses Faktum ist
bedingungslos wahr und deswegen kann er jetzt aufhören, weil den Teil
hat er auf jeden Fall bewiesen.
Wenn es sich um eine Regel handelt, dann war ja aufgebaut, dass wir
den Kopf hier links stehen haben und dann den Körper rechts und dann
wird praktisch...
ist ja der linke Teil, also der Kopf bewiesen, wenn wir den Körper
beweisen können, weil wir ja praktisch so einen Folgtauspfeil hier
haben.
Das heißt, er wird dann versuchen, den Körper zu beweisen, und zwar
von links nach rechts, zuerst das erste zu beweisen, dann das zweite
zu beweisen und so fort.
So, an dieser Stelle sei darauf verwiesen, dass wir sagen, dass ein
Kopf auf eine bestimmte Klausel passt und da verwenden wir praktisch
genau das, was wir im Matching im Kapitel 3.6 gesehen haben und mit
einer bestimmten Substitution, also das wir an dieser Stelle zum
Beispiel einsetzen können, für x Bern einsetzen und wenn wir für ys
einsetzen mit dieser Substitution, passt dann diese Anfrage auf diesen
Kopf und dann können wir tatsächlich damit weitermachen.
Wenn wir den Körper ersetzt haben, wie gesagt, also den Körper für den
Kopf eingesetzt haben, bleibt uns ja das hier zu beweisen.
Unser Beispiel von eben, da lautet die Anfrage ja, ob Bern und
irgendeine Stadt verbunden sind, das heißt, wir passen das hier drauf
auf diesen Kopf und dann bleibt ja das hier zu beweisen.
Dann wird ja x zu Bern und das y wird zu s und dann muss der Prolog
-Interpreter praktisch diese Anfrage hier beweisen.
Das sind jetzt seine neuen, man sagt auch Ziele.
So, er fängt von links an nach rechts, das heißt, er versucht erst
mal, das Linke zu beweisen.
Da findet er, das ist ein Fakt und sagt, okay, ist bewiesen.
So, jetzt bleibt halt noch übrig Bahnhof S und auch hier fängt er
wieder ganz vorne an und versucht, so lange eine Substitution zu
finden, bis halt irgendeine Klausel passt.
Und da steht dann gleich ganz oben drin in dem Programm Zürich und
hier findet er in der Tat eine Substitution, dass ich Zürich für S
einsetze und dann sagt er mir, okay, mit S gleich Zürich kann ich es
beweisen.
Dass das jetzt auch stimmt, was ich Ihnen da so erzähle,
wollen wir mal eben kurz ausprobieren.
Keine Sorge, im Rechenzentrum ist es noch langsamer.
Okay, Sie sehen, ich habe also genau die Datenbasis eingegeben.
Naja, fast, ein bisschen gelogen.
Ich habe noch zusätzlich eine Stadt Genf mit eingegeben und auch
unsere Regel hier.
Und wenn ich das jetzt in den Prolog Interpreter lade, die
Standardinstallation von diesem SWI Prolog sieht dann direkt vor, dass
ich nur noch doppelt draufklicken brauche, dann habe ich es drin.
Und dann kann ich tatsächlich meine Anfrage stellen in der Form
verbunden Bern und Genf.
Sie sehen, wenn Sie keinen Punkt eingeben, können Sie hier noch
beliebig lange Enter drücken und es wird nichts passieren.
Sie müssen Ihren Punkt eingeben und dann wird er Ihnen antworten.
Okay.
Gut, als alternativen Test.
Wollen wir uns anschauen.
Verbunden.
Bern.
Oh, ich hasse englische Tastaturen.
Bern und Köln.
Was soll er jetzt tun?
Er hat zwei Möglichkeiten, er könnte abstürzen oder er könnte uns Nein
ausgeben.
Uns ist das Zweite deutlich angenehmer.
Und warum gibt er Nein aus?
Na gut, er kannte Köln nicht.
Ein guter Compiler wie C, Haskell oder Java oder sonst, wie wer jetzt
abgestürzt hätte gesagt, Unknown Identifier.
Gut, Haskell sagt halt einfach, ja, kenne ich nicht, kann ich keine
Klausel für passen, also kann ich es nicht beweisen, also kann ich
auch das obere Ziel, also das Verbunden nicht beweisen, also gebe ich
Nein aus.
Das Ganze
funktioniert ja nun, indem ich diese Substitutionen anwende.
Und wie wende ich diese Substitutionen an?
Wie finde ich das Ganze raus?
Na, Prolog funktioniert mit Unifikation.
Auf dieser Folie steht jetzt theoretisch viel mehr Blabla, aber da Sie
Unifikation ja jetzt nur schon kennen, brauche ich das Ganze nicht
nochmal zu wiederholen.
Das ist jetzt so ein Beispiel dafür, wie wir uns vorstellen, dass Sie
etwas von diesem Studium haben.
Sie haben mittlerweile festgestellt, dass der Praxisbezug nicht
wirklich offensichtlich ist.
Also meistens.
Aber Sie lernen nichtsdestotrotz irgendwelche Dinge, von denen Sie
irgendwann später sagen, aha!
Also, ich möchte Ihnen noch ein einfaches Beispiel geben.
Ich habe das Vertiefungsfach Datenbanken damals gehabt, bei der grauen
Eminenz Lockermann.
Und da ging es um Datenbankimplementierung und Datenbankeinsatz.
Und obwohl es ja nun mit Postgres und MySQL auch freie Datenbank,
Datenbanksoftware mit öffentlichem Source-Code gibt, haben wir dort
nicht einmal reingeguckt.
Ich habe mir gedacht, was soll denn das alles?
Wie kann man denn insbesondere Datenbankimplementierung hören und
nicht einmal sich anschauen, wie es in der Tat konkret implementiert
ist?
Und es ist also tatsächlich so, wenn Sie die Theorie hinter dem Ganzen
mal verstehen und dann sehen, man kann es eigentlich nur so machen und
gar nicht anders, dann können Sie sich ganz schnell erklären, warum
das eine oder andere so funktioniert.
So war es also so, dass ich dann einmal ein konkretes Problem hatte,
was es mit dem Microsoft SQL Server zu lösen galt und anhand der
Anfrage ließ sich praktisch erkennen, wie der Microsoft SQL Server
intern arbeitet.
Man hat also gesehen, dass er Unions nicht richtig verarbeiten kann,
also das Zusammennehmen verschiedener Mengen.
Und allein daraus können Sie dann, wenn Sie das Wissen haben, wie es
intern funktioniert, weil man es nicht anders machen kann, können Sie
dann schließen, aha, Microsoft scheint das Ganze so und so und so zu
realisieren.
Und Sie können dann auch Vorhersagen treffen, wie sich der Microsoft
SQL Server in anderen Anfragefällen verhält, ohne dass Sie jemals eine
Zeile Code aus dem Microsoft SQL Server gesehen haben.
Und das ist also auch die Grundidee bei diesem Studium, dass Sie das
Ganze so lernen, dass Ihr Wissen eben nicht zugeschnitten ist auf
speziell C oder eben speziell Java oder eben MySQL oder wegen mir auch
der SQL Server von Microsoft, sondern dass Sie die Prinzipien
verstanden haben und dass Sie Ihr Wissen möglichst lange anwenden
können.
Gut, so viel dazu.
Ein Prinzip, was ich Ihnen noch eben erklären möchte, weil sich das
anhand von Prolog recht gut erklären lässt, das ist das sogenannte
Backtracking.
Wir haben gesehen, wenn wir Zürich und Bern eingegeben haben als
Fakten und dann nach einem Bahnhof fragen, dann wird er uns von oben
herunter erstmal das erste Faktum ausgeben und das ist in dem Fall ja
eben gerade Zürich.
So, und jetzt gäbe es hier in dem Fall noch mindestens ein weiteres,
was passen würde.
In meiner Beispieldatei gäbe es sogar zwei, die passen würden.
Und das wäre, wenn wir zum Beispiel X, also Zürich für X einsetzen,
Quatsch, Bern für X einsetzen oder dann eben Gen für X einsetzen.
So, und wenn Sie jetzt das Semikolon eingeben, um sich weitere
Lösungen ausgeben zu lassen, dann macht er die Entscheidung für das
erste hier oben rückgängig und sucht weiter und wird dann das nächste
von oben gesehen natürlich einsetzen.
Und das Ganze nennt man dann Backtracking.
Und wenn Sie das innerhalb eines größeren Auswertungs- oder
Beweisversuchs seitens des Prolog Compilers haben und er muss
Entscheidungen rückgängig machen, dann wird das Verstehen, warum man
das Ganze Backtracking nennt, auch etwas leichter.
Dazu muss man sich das Ganze ein bisschen abstrakter angucken.
Nehmen wir mal an, also der Prolog Compiler sucht, versucht eine
bestimmte Klausel auf ein Ziel zu passen.
Und das versucht er natürlich so lange, bis er irgendeine Klausel
gefunden hat, die zu unserem aktuellen Ziel Z-Strich passt.
So, wegen mir, er hat zuerst Bern ausgegeben, Bern wollten sie nicht.
Dann hat er das ausgegeben, das wollte er auch nicht.
Dann hat er Zürich ausgegeben, das wollten sie auch nicht haben.
Dann hat er gesagt, na dann kann ich es aber leider nicht beweisen.
Wenn wir ein übergeordnetes Ziel hatten, dann kann er zurückgehen und
sagen, na gut, auf dem Weg konnte ich das Ziel nicht beweisen.
Ich hätte aber noch eine andere Alternative, das hier zu beweisen,
nämlich indem ich das hier beweise.
Und das hier kann ich dann wieder dadurch beweisen, dass ich versuche,
das da unten zu beweisen.
Sie erinnern sich an den Algorithmus, um Postfix-Notationen oder
Präfix -Notationen aufzuschreiben, wie Sie dann durch diesen Baum
marschieren.
Sie müssen ja auch immer wieder zurück.
Und das ist praktisch dieses Backtracking.
Sie versuchen, irgendwo eine Lösung zu finden, bis in ein Blatt des
Baums zu kommen.
Und wenn Sie da sind, dann haben Sie es geschafft.
Wenn Sie nicht weiterkommen, dann ist es halt blöd, da müssen Sie
zurückgehen und einen anderen Ast versuchen.
Und das Ganze macht Prolog systematisch und das ist eben das, was wir
Backtracking nennen.
Was ich Ihnen noch zeigen möchte, was halt nun mal leider doch zum
Handwerkszeug gehört, wenn Sie programmieren möchten, das Dumme ist,
dass es hin und wieder mit dem Programmieren auch mal schief geht und
irgendwie nicht das passiert, was wir uns vorgestellt haben.
Dazu gibt es zwei Möglichkeiten.
Einmal den Befehl Trace.
Der wird uns ausgeben, alles, was Prolog so am Arbeiten ist.
Und es gibt aber auch die Möglichkeit, dass wir einen einzelnen
Ausdruck praktisch überwachen.
Und das geht dann so, wenn wir es bei eingeben und den Ausdruck
dahinter schreiben, Schrägstrich Stelligkeit.
Werden Sie hin und wieder in Prolog drüber stoßen?
Naja, das mit der Stelligkeit, das kennen Sie ja von dem Sigma Null
und Sigma Eins und Sigma Zwei.
Wir hatten Klammern drum.
Das ist halt einfach die Stelligkeit, die wir haben.
Das heißt, das sind die Anzahl der Variablen im Kopf der Klausel.
Unser Trace zum Beispiel, der Befehl hier oben, nimmt überhaupt keine
Parameter entgegen.
Deswegen schreibt man den als Trace Null.
Unser Faktum Bern, dass Bern einen Bahnhof hat, sehen Sie, hat ja
genau einen Parameter, also schreiben wir Schrägstrich Eins und
verbunden XY schreiben wir dann mit Schrägstrich Zwei.
So, wozu dient das Ganze?
Wir könnten ja nun auch noch einen verbunden XYZ irgendwo definiert
haben.
Das würden wir dann betiteln mit verbunden mit Drei.
Wenn Sie jetzt einen Zwei setzen wollen, müssen Sie natürlich sagen,
was Sie überwachen wollen.
Ob Sie die zweistellige Funktion überwachen wollen oder die
dreistellige Funktion.
Dazu gucken wir uns jetzt ein kleines bisschen längeres Programm an.
Wir haben also unsere drei Bahnhöfe hier und wir haben ein
zusätzliches Faktum, wo wir sagen, dass der Bahnhof von Genf
geschlossen ist.
Wieder unser verbunden, unsere Regel und zusätzlich haben wir jetzt
noch eine Regel erreichbar, X, und dafür fordern wir, dass die zwei
Städte verbunden sind und dass die Stadt bzw.
dafür fordern wir, dass unser Bahnhof X oder unsere Stadt X verbunden
ist mit irgendetwas und wir fordern, dass dieser Bahnhof auch nicht
geschlossen ist, der Stadt.
Wir hätten hier natürlich genauso gut Bahnhof hinschreiben können,
aber ich wollte Ihnen nochmal die Funktion dieses Unterstrichs
darlegen, in dem Sie sehen können, das heißt, wir fordern hier das
schon, damit die aufeinander passen, dass hier irgendwas steht, aber
es ist uns egal, was hier steht.
Wir fordern nur, dass dieses X eben, wenn wir das hier versuchen zu
beweisen, dass das dann auch nicht gilt.
Um einen Bestimmten zu überwachen, zum Beispiel das Geschlossen,
würden wir dann einfach geschlossen 1 eingeben oder implizit wird er
dann, da er nur das Geschlossen mit einem Parameter kennt, dann
geschlossen 1 annehmen, wenn wir ihn nur geschlossen sagen.
Das wollen wir uns anhand zweier Anfragen angucken.
Also ich habe hier das Programm geladen, was hier oben in der
Präsentation hingedruckt war und ich möchte Ihnen jetzt erstmal einen
Trace zeigen.
Das heißt, ich sage ihm, er soll jetzt tracen und dann sage ich,
verbunden, Bern, Genf.
So, als erstes fragt er mich oder sagt mir Bescheid, dass er jetzt da
hineingehen will, dass er jetzt das versucht zu beweisen, was
irgendwie klar ist, weil dazu habe ich ihn ja gerade aufgefordert.
Gut, er geht da rein und wir sehen jetzt, aha, er versucht, jetzt
möchte er beweisen, dass Bern einen Bahnhof hat.
Dann sagen wir, okay, das lassen wir jetzt mal zu und er sagt, Exit,
okay, er hat es bewiesen.
Jetzt versucht er als nächstes zu beweisen, dass Genf einen Bahnhof
hat.
Wir können hier statt Enter zu drücken auch was anderes tun, was kann
man da noch tun?
H eingeben, dann kann man sehen, was man noch alles tun kann.
Man kann ihm zum Beispiel, wie Sie hier sehen, kann man ihm sagen,
dass das jetzt schiefgehen soll, dass er das jetzt mal probehalber
nicht beweisen können soll.
Das heißt, ich gebe dann ein F ein und sage Fail.
Und dann leitet er natürlich sehr klug ab, dass wenn er nicht beweisen
kann, dass Genf einen Bahnhof hat, dann kann er auch nicht beweisen,
dass das ganze Ding hier so ist, also dass die verbunden sind.
Und dann gibt er in der Tat No aus.
Was ich Ihnen aber eigentlich noch zeigen wollte, war das mit dem Spy.
Und zwar wollen wir einen Spy setzen auf...
was war es denn?
Auf geschlossen.
So, jetzt teilt er mir mit, dass er in der Tat etwas gefunden hat, was
geschlossen heißt und da die Stelligkeit 1 annimmt.
So, jetzt können wir unsere zwei Anfragen eingeben.
Verbunden, Bern, Genf.
Wir haben den Spy eingegeben auf geschlossen.
Das heißt, er überwacht das geschlossen und wenn wir verbunden Bern,
Genf eingeben, wird geschlossen nicht aufgerufen.
Das heißt, wir sollten da ganz unbehelligt durchkommen.
Sagt er einfach Yes.
Sehr schön.
Und jetzt wollten wir eingeben, ob Bern erreichbar ist.
Sie sehen, geschlossen ist für Bern so nicht definiert.
Nichtsdestotrotz haben wir einen Spy aufgeschlossen und er sollte das
jetzt trotzdem dann anzeigen.
In der Tat, er hat offenbar, wie Sie sehen, zuerst das Ziel hier
erreichbar.
Das heißt, er hat zuerst das verbunden, hat er offenbar schon bewiesen
und er ist dann in das Not reinmarschiert und versucht jetzt, das
geschlossen zu beweisen.
Das heißt, er hat das alles übersprungen.
Er hat uns damit, weil wir uns da sicher sind, dass wir da unseren
Fehler nicht gemacht haben, hat er uns damit auch nicht weiter
behelligt.
Er sagt jetzt nur hier, dass er das jetzt prüfen möchte, geschlossen
Bern, das gestehen wir ihm mal zu.
Das heißt, wir sehen jetzt hier, das ist also, wie wir es erwartet
haben, fehlgeschlagen.
Jetzt haben wir hier das Not stehen.
Das ist ja eigentlich das Ziel, was oben drüber war.
Wir wollten ja zeigen, dass das eben gerade nicht gilt, dass Bern
geschlossen ist.
Okay, dann verlassen wir das.
Und das war ja unser ursprüngliches Ziel, was wir zeigen wollten.
Und das ist also auch nicht erreichbar und er tut, was wir wollen.
Sie wollen in die andere Übung, deswegen nur noch der Hinweis, Sie
laden sich die Folien runter.
Haben wir es noch nicht so spät?
Ach, Sie wollen in die HM-Übung.
Schönen Gruß an Herrn Schmölger.
Sie finden das Material hier.
Ganz kurz noch der Hinweis, dieses Tutorial hier, das ist praktisch
die Grundlage meiner Folien.
Und das hier ist etwas dick, aber da ist halt gerade das hier
interessant.
Da steht so Bedienensachen für den Prolog Compiler.
Dankeschön.
Tschüss.