Morgen.

Wir hatten uns in den letzten beiden Lectures hatten wir uns mit

Constraint Satisfaction Problemen. Auf Deutsch im übrigen Beschränkungs-

Erfüllungsprobleme. Klingt irgendwie doof. Aber deswegen werde ich auch weiter

Constraint Satisfaction sagen. Es gibt viele deutsche Übersetzungen, klingen

doof, weil man sie nicht so kennt. Aber diese klingt irgendwie besonders doof.

Deswegen werde ich das wahrscheinlich nicht durchhalten. Um einzuordnen, wo wir

sind in der Vorlesung. Wir haben ja so eine Folge von Techniken, die entwickelt

worden sind. Zum Problem lösen uns angeguckt. Und der Sinn hinter dieser

Aufreihung war, dass wir immer mehr Informationen in die Verfahren einbringen.

Also das erste war einfach uninformierte Suche. Da wussten wir eigentlich nur,

dass wir Zustände haben. Die Zustände waren Black Boxes und wir haben

Aktionen oder Nachfolgerelationen oder was auch immer. Und die waren auch Black Boxes.

Konnte in nichts reingucken, hatte keine Information und konnte trotzdem

Problem lösen machen. Wir haben auch gesehen, dass wir damit nur sehr kleine

Probleme lösen können, weil einfach die Suchräume exponentiell sind. Und das

einzige, was gegen exponentielle Suchräume hilft, ist Information. Das erste,

was wir gemacht hatten, war, dass wir Heuristiken eingeführt hatten als so eine

Art Intuition einer Richtung. Damit lassen sich wesentlich größere Probleme lösen.

Und da gab es spezielle Algorithmen für zum Beispiel A-Sternen. Das nächste,

was wir gemacht haben, war dann, dass wir gesagt haben, okay Zustände,

danach haben wir letztlich diese allgemeinen Suchsachen erweitert auf Spiele,

Situationen, aber immer noch waren die Zustände im Wesentlichen Black Boxes.

Das nächste, was wir gemacht haben für diese Constraint-Satisfaction-Probleme

sind, ist, dass wir uns gesagt haben, wir gucken uns die Zustände näher an und

nehmen eine bestimmte Form an, nämlich, dass ich den Zustand ausdrücken kann

durch ein Konfigurationsproblem, in dem ich gewisse Variablen habe. Und diese

Variablen sollen Werte kriegen. Also die Lösungen sind nicht mehr einfach tumme

Zustände, in die ich nicht reingucken kann, sondern Variablenbelegungen. Und wenn ich

meinen Zustand oder mein Problem beschreibe, dann habe ich eben diese

Variablen. Jede Variabe hat einen Wertebereich, das heißt, was ich dafür

einsetzen kann. Und ich habe diese Beschränkungen, Constraints, und das ist

einfach eine Relation. Was ich möchte, dass Sie sich vor Augen führen, ist, dass

wir hier auch eine Black Box haben. Vielleicht könnten Sie sich mal überlegen,

was die Black Box hierbei ist. Weil als nächstes, und ich weiß nicht, ob wir heute

noch dazu kommen oder nicht, werden wir Logik einführen. Ich habe, weil einige

Leute gesagt haben, also etwa ein Drittel aller, die geantwortet haben, sie können

keine, sie haben Logik noch nie gesehen, werde ich also Logik auch in dieser

Vorlesung behandeln. Und werde es allerdings dann so machen, dass wir andere

Sachen, also dass ich den Overlap mit dem Zeugs, was Sie vielleicht schon in Ihren

Pflichtvorlesungen gehört haben, so ein bisschen kleiner halte. Also, das habe ich

eine Weile lang geredet, damit Sie Zeit hatten, nachzudenken, was wohl hier die

Black Box ist. Irgendwelche Ideen? Über was haben wir hier keine große

Information? Ja, genau, die Constraints, die Beschränkungen sind für uns weiterhin

Black Boxes. Black Boxes heißt, wir haben einfach einen Orakel, das sagt uns Ja oder

Nein. Das sind Constraints, die sagen, jo, drei und sieben ist in dem Constraint

wunderbar. Ja, zum Beispiel bei einem Ungleichheits-Constraint. Was wir in den

Algorithmen überhaupt nicht ausnutzen werden, ist das zum Beispiel so ein

Gleichheits-Constraint, dass der transitiv und symmetrisch ist und reflexiv.

Das werden wir nicht ausnutzen. Wir können auch nicht sagen, dieser Constraint ist ein