Dazu mussten wir uns erstmal anschauen, was ist ein Algorithmus.
Der ist eben wesentlich charakterisiert durch Allgemeinheit,
Determiniertheit und Endlichkeit.
Das heißt endliche Beschreibung und endliche Laufzeit.
Wir hatten gesehen, dass nicht jede Funktion von N nach N berechenbar
ist.
Das hatten wir eben gezeigt über dieses Diagonalisierungsverfahren,
dass es überabzählbar viele Funktionen gibt, aber nur abzählbar viele
berechenbare Funktionen.
Ich würde Sie doch bitten, ein bisschen leiser zu sein.
Ich glaube, da haben Sie mehr davon, da habe ich mehr davon.
Okay, wir hatten uns mit Entscheidungsverfahren beschäftigt.
Dieses Problem gehört einem Element zu einer Menge oder gehört es
nicht zu der Menge?
Und hatten gezeigt, dass es eben Probleme gibt, die nicht entscheidbar
sind.
Das war nochmal so die Struktur, also die entscheidbaren Mengen, das
ist die kleinste Menge.
Es gibt dann Mengen, die kann ich aufzählen, aber nicht entscheiden.
Entscheidbar waren sie nur, wenn die Menge selbst und das Komplement
aufzählbar waren.
Und dann gibt es noch die Menge der abzählbaren Mengen, die eben noch
eine Übermenge ist.
Und wir hatten uns dann angeschaut, wie sieht denn das aus mit dieser
Berechenbarkeit?
Wir brauchen ja für die Berechenbarkeit ein Berechnungsmodell.
Wir müssen wissen, welche Maschine oder welcher Automat oder was auch
immer berechnet denn da.
Und wir haben uns dann speziell die Turing-Maschinen angeschaut und
haben eben Turing-Berechenbarkeit und Turing-Entscheidbarkeit
definiert und haben gezeigt, dass es eine universelle Turing-Maschine
gibt, die andere Turing-Maschinen simulieren kann.
Das war so der Link zwischen Turing-Maschinen, die eigentlich, so wie
wir sie bisher kennengelernt hatten, immer nur ein ganz spezielles
Problem gelöst haben und Turing-Maschinen jetzt im universellen Fall,
also quasi programmierbar, ich gebe der Turing-Maschine eine
Beschreibung der Turing-Maschine, die sie simulieren soll, also im
Prinzip ein Programm und die Eingangsdaten und sie tut dann so, als
wäre sie diese andere Turing-Maschine.
Also wir haben quasi eine programmierbare Turing-Maschine.
Wir haben gezeigt, dass das im Prinzip möglich ist.
Der wesentliche Punkt, denke ich, von der letzten Vorlesung war diese
Church -These, die sagt, dass jede im intuitiven Sinn berechenbare
Funktion auch Turing-berechenbar ist.
Und das hat für uns wesentliche Bedeutungen.
Das heißt nämlich, dass wir, wenn wir auch noch diese zusätzliche
Annahme machen, dass sogar die Rechenzeit bis auf polynomielle
Faktoren richtig erfasst wird, dass also eine Turing-Maschine nicht
mehr als um einen polynomiellen Faktor mehr Zeit braucht, als ein
beliebiger anderer Rechner, dann bedeutet das, dass wir uns in Fragen
der effizienten Berechenbarkeit auf Turing-Maschinen beschränken
können.
Wenn eine Turing-Maschine ein Problem effizient berechnen kann, dann
kann ich das eben auch mit einem beliebigen anderen Rechner.
Und wenn ich nachweisen kann, dass es mit einer Turing-Maschine nicht
geht, dann weiß ich auch, dass es mit einem beliebigen anderen Rechner
nicht geht.
Und wir müssen also nicht mehr unterscheiden zwischen aufzählbar und
Turing -aufzählbar und entscheidbar und Turing-entscheidbar, weil die
eben gleichmächtig sind.
Gut, das Heide-Problem war ein Problem, wo Turing-Maschinen eben das
nicht entscheiden können.
Das heißt, wir haben eben ein Problem jetzt nachgewiesen, für das es
definitiv keinen Algorithmus gibt, der das entscheiden kann.
Und hier war nochmal die Zusammenfassung.
Diese verschiedenen Sprachklassen und jeweils die entsprechende
Grammatik dazu, den Automat dazu und was sonst noch für Besonderheiten
sind.
Und dann hatten wir angefangen mit der Komplexität.
Und bei der Komplexität beschäftigen wir uns mit der Frage,
was kostet uns denn die Berechnung einer Funktion?
Wie viel Platz brauchen wir zum Berechnen beispielsweise?
Wie viel Zeit brauchen wir zum Berechnen?
Und das hängt natürlich davon ab, was für ein Berechnungsmodell wir
zugrunde liegen.
Berechnen wir das auf einem sequentiellen Rechner?
Berechnen wir das auf einem parallelen Rechner?
Berechnen wir das auf einer Turing-Maschine?
Berechnen wir das auf einer Registermaschine?
Prinzipiell, wenn es eben nur darum geht, ob das effizient möglich ist
oder nicht, dann reicht uns da, wie wir gesehen haben, die Turing
-Maschine.
Und das hängt natürlich auch vom verwendeten Algorithmus ab.
Sie haben in Informatik 1 schon Komplexität angefangen zu behandeln.
Das war diese O-Notation, wo sie im Prinzip den Algorithmus
hergenommen haben und analysiert haben und gesagt haben, okay, dieser
Algorithmus braucht im schlechtesten Fall O von N² oder ähnliches.
Und was uns heute noch interessiert ist, gibt es denn Probleme, für
die man nachweisen kann, dass egal wie viel Zeit man reinsteckt und
egal wie viel Gehirnschmalz man reinsteckt, man gar keinen
effizienten, das heißt polynomiellen Algorithmus entwickeln kann oder
gibt es das nicht?
Es
sind im Wesentlichen zwei Aspekte interessant.
Der eine Aspekt ist die Zeitkomplexität, also wie viel Zeit braucht
eine Turing-Maschine, um eine bestimmte Funktion zu berechnen und wie
viel Platz braucht die Turing-Maschine.
Wobei Platz hier definiert war das letzte Mal als die Anzahl der durch
Schreiben veränderten Zellen des Bandes.
Also wie viele Zellen hat denn diese Turing-Maschine zur Berechnung
gebraucht?
Und diese Zeitkomplexität haben wir hier bezeichnet mit T, Turing
-Maschine abhängig von W, also jeweils abhängig von dem Wort, das
eingegeben wird.
Und das T ist definiert als gerade das Maximum aller kleinen T, unter
der Bedingung, dass die Turing-Maschine auf diesem Wort anhält, bei
der Berechnung dieses Wortes anhält und das Wort die Länge N hat.
Also das ist im Prinzip der Worst Case, also das Wort ist ja die
Eingabe für die Turing-Maschine zu berechnen und ich schaue mir jetzt
den Worst Case an, also die maximale Zeitkomplexität für Wörter einer
bestimmten Länge.
Und genau das gleiche ist bei der Platzkomplexität, das Groß P von N
ist eben gerade die Zeitkomplexität abhängig von diesem Wort W und die
maximale, sodass die Turing-Maschine anhält und die Länge des Wortes N
ist.
Gut, und wir hatten dann Komplexitätsklassen definiert.
Und da fangen wir jetzt mal hier nochmal mit der, wiederholen wir das
nochmal, die erste D-Time von G, wobei das G eben typische
charakteristische Funktionen sind, wie N² oder N hoch K oder 2 hoch N.
Ich weiß nicht woran es liegt, ob es daran liegt, dass heute die
Übungsblätter abgegeben wurden und es noch so viel zu diskutieren gibt
oder ob das Mikrofon schlecht eingestellt ist.
Wenn Sie mich nicht verstehen können, dann würde ich Sie bitten mir
das zu sagen, aber ich würde darum bitten, wenn sonst alles stimmt,
dass Sie auch einigermaßen ruhig sind.
Okay, D-Time von G war eben so definiert als alle Funktionen, sodass
diese Funktion F mit einer Zeitkomplexität O von G, diese Notation
kennen Sie aus Informatik 1, wobei das G eben eine typische Funktion
ist, wie beispielsweise N hoch K.
N hoch K wären alle polynomiellen Funktionen für ein festes K, also
beispielsweise N² oder N hoch 3 oder N hoch 4, sodass diese Funktion
in dieser Zeitkomplexität von einer deterministischen Turing-Maschine
berechenbar ist.
Das heißt, wir schauen uns die Wortlänge an und die Wortlänge ist
jetzt im Prinzip die Problembeschreibung.
Und überlegen uns, kann es eine deterministische Turing-Maschine
geben, die eben diese Funktion berechnet, in einer Zeitkomplexität O
von N hoch K oder O von 2 hoch N, das wären die exponentiellen
Funktionen.
Und Sie erinnern sich, dass 2 hoch N sehr viel schneller steigt als N
hoch K.
Und ich hatte es das letzte Mal schon gesagt, die, die ich polynomiell
berechnen kann, das sind für mich die effizienten Algorithmen, das
sind die, die noch akzeptabel sind.
Und wenn ich eben Komplexität 2 hoch N habe, dann ist das
exponentiell, dann wächst das so schnell, dass ich auch schon relativ
kleine Probleme nicht mehr in einer auch nur annähernd vernünftigen
Zeit berechnen kann.
Und entsprechend zu D-Time haben wir auch N-Time definiert und das war
die Zeitkomplexität, sodass alle Funktionen, die in Zeitkomplexität O
von G von einer nicht deterministischen Turing-Maschine berechenbar
sind.
D -Space war das gleiche für die Platzkomplexität, in diesem Fall eben
von der deterministischen Turing-Maschine und bei N-Space die
Platzkomplexität von einer nicht deterministischen Turing-Maschine.
Das heißt, wir versuchen jetzt hier nicht Algorithmen irgendwie zu
klassifizieren, sondern Probleme zu klassifizieren.
Ist es möglich, mit einer deterministischen oder nicht
deterministischen Turing-Maschine das in einer bestimmten Zeit zu
berechnen oder ist es nicht möglich?
Und dann haben wir die zwei ganz wichtigen Klassen definiert, nämlich
einmal die Klasse P, das war gerade die Vereinigungsmenge aller D-Time
von N hoch K, für alle K Element N.
Also egal welches K, alle Funktionen, die irgendwie in polynomialer
Zeit von einer deterministischen Turing-Maschine berechnet werden
können.
Deswegen hier das D-Time.
Und wir hatten definiert die Klasse NP, das war die Klasse der
Funktionen, die von einer nicht deterministischen Turing-Maschine in
polynomialer Zeit berechnet werden können.
Also hier deswegen das N.
Und ein Punkt, wo sich viele immer outen, dass sie eben nicht so genau
aufgepasst haben, das ist, wenn sie gefragt werden, was bedeutet denn
das NP?
Bei dem P, da weiß jeder, okay, das bedeutet polynomiell lösbar von
einer deterministischen Turing-Maschine und bei NP, da sagt dann
jeder, das ist eben nicht polynomiell lösbar.
Aber das bedeutet von einer nicht deterministischen Turing-Maschine in
polynomialer Zeit lösbar.
Gut, im Prinzip bedeutet das, diese nicht deterministische Turing
-Maschine weiß ja, welchen Weg sie gehen muss, welche Übergänge sie
benutzen muss, um entscheiden zu können, ob dieses Wort zur Sprache
gehört oder nicht.
Beziehungsweise, wenn sie das Wort akzeptieren will, was sie machen
muss, um das Wort zu akzeptieren.
Im Prinzip kann man das so deuten, dass die nicht deterministische
Turing -Maschine eine Lösung raten kann und dann in polynomialer Zeit,
denn sie muss ja nach wie vor durch den Baum durchgehen, in
polynomialer Zeit die Korrektheit der Lösung überprüfen kann.
Und es ist relativ einleuchtend, dass die meisten von den
Optimierungsproblemen, mit denen sie hier an der Uni oder im
Berufsleben zu tun haben, in diese Klasse NP fallen, von einer nicht
deterministischen Turing-Maschine gelöst werden können.
Wir schauen uns gleich einige solche Probleme aus NP an, aber wenn sie
eine Lösung haben, zu überprüfen, ob diese Lösung eine gültige Lösung
für das Problem ist, ist relativ einfach.
Wenn das Problem ist, für den Travelling Salesman eine Tour zu
bestimmen und es sagt Ihnen jemand, ich habe eine Tour der Länge 50
und gibt Ihnen diese Tour, dann können Sie sehr schnell überprüfen, ob
diese Tour tatsächlich die Länge 50 hat.
Umgekehrt, wenn Ihnen jemand sagt, ich habe hier ein Problem, gibt es
eine Tour der Länge 50, dann ist das unter Umständen sehr, sehr
schwer.
Wir werden zeigen nachher noch im Verlauf der Vorlesung, dass es eben
sehr, sehr schwer ist.
Aber wenn ich mal eine Lösung habe, das zu überprüfen, ist in den
meisten Fällen sehr einfach und deswegen hat diese Klasse NP sehr,
sehr viele uns interessierende Optimierungsprobleme.
Ja, ganz offensichtlich ist, dass die Klasse P eine Teilmenge der
Klasse NP ist.
Denn was ich mit einer deterministischen Touringmaschine lösen kann,
kann ich selbstverständlich auch mit einer nicht-deterministischen
Touringmaschine lösen.
Die Frage ist, gilt die Umkehrung auch?
Also ist P gleich NP oder ist P nicht gleich NP?
Und das ist das berühmteste offene Problem der Informatik.
Man geht heutzutage eigentlich mit an Sicherheit grenzender
Wahrscheinlichkeit davon aus, dass P ungleich NP, dass also die nicht
-deterministische Touringmaschine eben die Sachen doch schneller
berechnen kann als die deterministische.
Also auch um mehr als einen polynomiellen Faktor schneller.
Beweisen kann man es aber bisher noch nicht.
Gut, ein ganz wichtiges Prinzip ist das Prinzip der Reduzierbarkeit.
Wenn wir zwei Probleme haben, hier Q und Problem P, und wir bezeichnen
mit LP und LQ die Mengen der Lösungen zu diesem Problem, dann heißt Q
Polynomialzeit reduzierbar und wir schreiben das hier mit diesem
Ausdruck, also Q kleiner gleich Polynomialzeit reduzierbar auf P. Wenn
Q durch eine in Polynomieller Zeit berechenbare Funktion F in P
transformiert werden kann, das ist der eine Schritt, und jede Lösung
in Polynomieller Zeit zurück transformiert werden kann in die Lösung
von Q.
Also hier in dem Schaubild sieht man das nochmal sehr deutlich.
Ich habe ein Problem Q und jetzt transformiere ich das in ein anderes
Problem P in Polynomieller Zeit.
Und dann nehme ich an, okay, dieses Problem P, das könnte ich lösen.
Dann habe ich eine Lösung von P und ich transformiere diese Lösung
zurück in die Lösung von Q.
Auch in Polynomieller Zeit.
Das ist der wichtige Punkt, dann ist das Problem Q Polynomialzeit
reduzierbar auf P. Im Prinzip bedeutet das, Q
ist mindestens so schwer wie P.
Stimmt das?
Stimmt nicht.
Q ist höchstens so schwer wie P. Stimmt das?
Also was klar ist, ist wenn Sie das P polynomiell lösen können, wenn
Sie diesen Schritt in Polynomieller Zeit machen können, dann können
Sie auch diesen Schritt in Polynomieller Zeit machen.
Weil Sie einfach diesen Umweg gehen können.
Sie machen hier einen Schritt in Polynomieller Zeit, Sie machen noch
einen Schritt in Polynomial Zeit, und Sie machen dann den dritten
Schritt in Polynomielle Zeit.
Das heißt, Sie können das gesamte Problem Q in polynomialer Zeit
lösen, auch wenn Sie keinen direkten Algorithmus kennen, der Ihnen Q
jetzt direkt löst.
Aber wenn Sie einen Algorithmus kennen, der Ihnen P in polynomialer
Zeit löst, und Sie kennen die entsprechenden Transformationen, dann
können Sie auch Q in polynomialer Zeit lösen.
Die umgekehrte Folgerung ist, wenn Sie wissen, dass Q nicht
polynomiell lösbar ist,
und Sie haben diese Transformation von Q nach P und von der Lösung von
P nach Q, dann können Sie auch folgern, dass P nicht polynomiell
lösbar ist.
Denn wenn P polynomiell lösbar wäre, dann könnten Sie ja genau diesen
Weg gehen, könnten Q lösen und hätten damit ein Lösungsverfahren für
Q, was aber eben der Annahme widerspricht, dass Q nicht polynomiell
lösbar ist.
So, und das ist ganz interessant, denn wenn Sie ein Problem kennen, Q,
das nicht polynomiell lösbar ist, dann können Sie mithilfe dieser
Reduzierbarkeit verschiedene Probleme P hier untersuchen.
Und wenn Sie diese Transformationen finden können, dann wissen Sie
dann jeweils auch, okay, P ist damit nicht polynomiell lösbar und es
ist eine Möglichkeit, die nicht polynomielle Lösbarkeit nachzuweisen.
Ein ganz einfaches Beispiel, was vielleicht ein bisschen trivial
aussieht, Sie wollen wissen, ob die Multiplikation von Matrizen,
okay, also Sie wollen testen, ob die Multiplikation von Matrizen auf
die Inversion von Matrizen polynomialzeitreduzierbar ist.
Sie können aus diesen Matrizen A und B eine 3n kreuz 3n Matrix
generieren, die sieht so aus, das ist diese Matrix C.
Die ist jetzt größer als die ursprünglichen Matrizen A und B, die Sie
multiplizieren wollen.
Die ist eben 3n kreuz 3n, aber das ist immer noch polynomiell größer.
Und Sie nehmen jetzt an, okay, Sie können die Inversion dieser Matrix
berechnen und die sieht eben genau so aus, wie hier dargestellt.
Und der entscheidende Punkt ist, dass hier das AB wieder auftritt.
Und es ist klar, wenn Sie diese Matrix C invertieren können, dann
können Sie auch die Lösung hier, die Lösung der Matrixmultiplikation
von A und B quasi hier oben ablesen, in dieser Teilmatrix.
Das heißt, Sie können den Schritt gehen von Matrixmultiplikation in
polynomialer Zeit, erzeugen Sie diese Matrix C, dann haben Sie ein
Problem der Matrixinversion, Sie lösen dieses Problem, dann haben Sie
diese Lösung hier.
Und Sie haben eine Möglichkeit, aus dieser Lösung der Matrixinversion
die Lösung der Matrixmultiplikation abzulesen, indem Sie einfach hier
oben in die obere Ecke schauen.
Das heißt, Sie haben gezeigt, dass diese zwei Pfeile in polynomialer
Zeit lösbar sind und deswegen ist die Matrixmultiplikation in
polynomialer Zeit reduzierbar auf die Matrixinversion.
Gut, das heißt im Prinzip, Matrixinversion ist auf jeden Fall
mindestens so schwer wie Matrixmultiplikation.
Gut, ein Begriff, der Ihnen vielleicht auch noch häufiger über den Weg
läuft, wenn Sie im Bereich Optimierungsprobleme arbeiten, ist NP
-schwer und NP-vollständig.
Die zwei wollen wir jetzt definieren.
Ein Problem P heißt NP-schwer, wenn jedes Problem Q aus dieser Menge
NP, die wir vorhin definiert haben, polynomialzeitreduzierbar ist auf
P. Okay, wir haben also hier alle Probleme aus NP und wir weisen nach,
dass ich jedes Problem aus NP in polynomialer Zeit auf P reduzieren
kann.
Und das bedeutet natürlich, wenn ich das P in polynomialer Zeit lösen
kann, wenn ich das P in polynomialer Zeit lösen kann und ich für jedes
Problem Q Element NP diese Transformation machen kann, dann würde das
natürlich bedeuten, dass ich jedes Problem in NP auch polynomial lösen
kann.
Und wenn ich also für ein solches Problem P, das NP-schwer ist, einen
polynomiellen Algorithmus finden würde, dann hätte ich gezeigt, dass P
gleich NP ist, weil ich damit alle Probleme, die in NP liegen und die
ich ja auf P reduzieren kann, in polynomialer Zeit lösen kann.
Also es ist sehr unwahrscheinlich, dass man für ein Problem, das NP
-schwer ist, einen polynomiellen Algorithmus findet, weil dann würde P
gleich NP als Folgerung herauskommen.
Diese NP-schweren Probleme sind also im Prinzip die schwersten
Probleme...
Ah, ne, stimmt nicht.
Die NP-Vollständigkeit, da kommt das jetzt.
Ein Problem P heißt NP-vollständig, wenn zum einen das P NP-schwer ist
und P in NP liegt.
Okay, und das sind im Prinzip die schwersten Probleme in NP,
weil ich eben alle darauf reduzieren kann und aus dieser Begründung
eben, wenn ich eines lösen könnte, könnte ich alle lösen.
Der Begriff der NP-Vollständigkeit wurde 1971, also ist noch gar nicht
so lange her, definiert und seitdem wurden sehr viele Probleme als NP
-vollständig nachgewiesen.
Also so 1000 bis 2000, das wären eigentlich täglich mehr, von denen
man weiß, okay, die sind mindestens so schwer wie jedes andere Problem
in NP.
Die wichtigsten Beispiele, hier habe ich ein paar aufgezählt.
Das ist das Erfüllbarkeitsproblem der Aussagenlogik.
Das heißt, da haben wir gegeben eine beliebige Formel in konjunktiver
Normalform.
Das müssten Sie eigentlich aus Informatik 1 noch kennen.
Also beispielsweise in der Form x1 oder x2 oder nicht x3, das wäre ein
Term und x2 und x3 oder nicht x2 oder so, das wäre zum Beispiel für
konjunktive Normalform.
Und die Frage ist jetzt, gibt es eine Belegung der Variablen x1 bis
xn, sodass diese Aussage erfüllbar ist, also dass diese Aussage wahr
ist.
Und KUK hat eben für dieses Problem gezeigt, dass es NP-vollständig
ist, dass es mindestens so schwer ist wie alle anderen Probleme in NP.
Und das hat dann diese Lawine losgetreten.
Mithilfe der Reduzierbarkeit haben dann die Leute nachgewiesen, okay,
aber dieses Problem und jenes Problem und dieses andere Problem, die
sind alle auch mindestens so schwer wie das SAT-Problem.
Und dadurch hat man für immer mehr Probleme nachweisen können, dass
sie NP-vollständig sind.
Und sodass wir heute eben schon das für 1000 oder 2000 Probleme
kennen, so in der Größenordnung.
Ein typisches Problem, das Sie sicher kennen, ist das Traveling
Salesman Problem.
Wir haben einen Graphen gegeben mit Kantenlängen und wir suchen eine
Rundreise kürzester Länge, das heißt wir wollen alle Knoten genau
einmal besuchen und die Summe der Kanten, die wir dabei überschreiten,
soll minimal sein.
Das ist so ein ganz typisches NP-vollständiges Problem.
Ich hatte vorhin schon erläutert, dass es auf jeden Fall in NP liegt,
denn wenn Sie eine Lösung haben, können Sie in polynomialer Zeit
überprüfen, ob diese Lösung auch korrekt ist.
Und es ist eben auch NP-vollständig, das heißt es gehört zu den
schwersten Problemen in NP.
Andere Beispiele sind das Rucksackproblem, wo Sie eine Menge von
Gegenständen haben, die haben alle ein Gewicht und haben alle einen
Nutzen und Sie wollen Ihren Rucksack so packen, dass auf einerseits
Ihre Gewichtsgrenze, die Sie noch tragen können, nicht überschritten
wird, andererseits aber Sie eben genau die Sachen eingepackt haben,
die Ihnen den größten Nutzen bringen.
Oder Binpacking, Sie haben eine Reihe von Gegenständen und eine Reihe
von Behältern und Sie möchten möglichst wenige von diesen Behältern
verwenden, um die Gegenstände da reinzupacken.
Und die Frage ist halt, welcher Gegenstand kommt in welchen Behältern
mit welchen anderen zusammen?
Das sind typische NP-vollständige Probleme, wie sie Ihnen
wahrscheinlich als Operations Research auch bekannt sind.
Ein anderes Problem, mit dem wir uns auch ein bisschen beschäftigt
haben oder mit dem sich Herr Neumann auch sehr viel beschäftigt, ist
die Projektplanung mit beschränkten Ressourcen.
Wenn Sie zusätzlich noch zu der Beschränkung der Ressourcen zeitliche
Mindest - und Maximalabstände haben, also wenn Sie sagen, ich darf
diese Operation höchstens zwei Stunden nach dieser anderen ausführen,
weil Sie beispielsweise mit verderblichen Lebensmitteln arbeiten oder
was auch immer.
Oder auch, ich muss zwischen dieser Operation und der nächsten
mindestens zwei Stunden warten.
Beispielsweise, wenn Sie ein Stahlwerk haben, dann muss der Stahl,
nachdem er erhitzt ist, irgendwie erstmal abkühlen.
Dann haben Sie auch ein typisches NP-vollständiges Problem und wenn
Sie eben diese zeitlichen minimalen Maximalabstände haben, dann ist
sogar bereits die Bestimmung einer zulässigen Lösung NP-vollständig.
Also einer Lösung, die die Nebenbedingungen nicht verletzt.
Beim Travelling-Salesman-Problem ist es sehr einfach, eine Lösung zu
erzeugen, die die Nebenbedingungen verletzt.
Da haben wir ja eigentlich nur als Nebenbedingung jede Stadt genau
einmal besuchen.
Ja gut, und da geht man einfach die Liste einmal durch und dann hat
man eine Lösung.
Auch wenn die vielleicht schlecht ist, sie ist zulässig.
Bei der Projektplanung ist eben sogar die Bestimmung einer zulässigen
Lösung teilweise NP-vollständig.
Gut, wenn Sie das Thema interessiert oder wenn Sie mal für ein Problem
nachweisen wollen, dass es NP-vollständig ist, da gibt es eigentlich
nur ein Standardwerk und das ist das Buch von Gary und Johnson.
In dem sind sehr, sehr viele NP-vollständige Probleme erläutert und
die kann man dann als Grundlage benutzen, um die NP-Vollständigkeit
für weitere nachzuweisen.
Warum will man das machen?
Es kann eben sehr sinnvoll sein, für ein Problem nachzuweisen, dass es
nicht polynomiell lösbar ist.
Und das macht man genau über diese Reduzierbarkeit, indem man zeigt,
dass sich ein beliebiges NP-vollständiges Problem auf NP reduzieren
lässt.
Okay, hier ist nochmal die Beziehung dargestellt.
Wir haben also hier die polynomiell lösbaren Probleme, für die wir...
Also wir wissen, es liegt in P, wenn wir einen polynomiellen
Algorithmus angeben können, der dieses Problem löst.
Wir haben hier die Probleme, die als NP-vollständig nachgewiesen sind
und die Klasse NP umfasst noch mehr.
Das sind eben Probleme, für die man noch nicht weiß, beziehungsweise
man vermutet auch, dass es so eine Zwischenklasse gibt.
Wie gesagt, alles eine Vermutung, denn wenn jemand kommt und
nachweist, P gleich NP, dann fällt das alles zusammen und es gibt
einfach nur noch eine Klasse, aber es ist sehr unwahrscheinlich.
Gut, jetzt möchte ich Ihnen an einem Beispiel demonstrieren, wie man
nachweist, dass ein Problem NP-vollständig ist.
Okay, ausgehen tun wir dabei von dem Drei-Sat-Problem.
Das Sat-Problem hatte ich gerade schon erläutert, das ist einfach nur
die Frage, also Sat-Satisfiability-Problem, ob ein Bulscher Ausdruck
in konjunktiver Normalform erfüllbar ist.
Und das Drei-Sat ist eine kleine Abwandlung, bei der der Bulscher
Ausdruck noch die zusätzliche Beschränkung hat, dass jede Konjunktion
genau drei Literate hat.
Also hier ist ein Beispiel,
hier hat jede Konjunktion, das ist eine Konjunktion und das ist eine
und das ist eine, hat genau drei Literale.
Also x1 oder x2 oder x3 und nicht x1, ich habe das hier mit so einem
Hochkomma geschrieben, oder nicht x4 oder nicht x3 und so weiter.
Also die Frage jetzt einfach nur, gibt es eine Belegung x1, x2, x3,
x4, sodass der gesamte Term wahr wird.
Und man weiß, dass Drei-Sat NP-vollständig ist.
So, und was wir jetzt machen möchten, ist für ein anderes Problem
nachweisen, dass es auch NP-vollständig ist.
Und hier schauen wir uns das Clicken-Problem an.
Das ist wie folgt definiert, gegeben ist ein ungerichteter Graph mit
einer Menge von Knoten und einer Menge von Kanten und ein K-Element N.
Die Frage ist jetzt, gibt es eine Clique und die ist definiert als
vollständig verbundener Teilgraph, der Größe K in diesem Graphen.
Also gibt es eine Menge von Knoten, die vollständig verbunden sind,
eine Menge von K-Knoten, die vollständig verbunden sind in diesem
Graphen.
Und wir wollen jetzt zeigen, dass dieses Problem auch NP-vollständig
ist.
Und dazu reduzieren wir das Drei-Sat-Problem nach dem Clique-Problem.
Wir müssen uns also überlegen, wie können wir das Drei-Sat-Problem so
umwandeln, dass es ein Clique-Problem wird.
Dieses Clique-Problem nehmen wir an, das können wir lösen.
Und wie können wir die Lösung von dem Clique-Problem wieder zurück
wandeln in das Drei-Sat-Problem.
Das wollen wir jetzt versuchen.
Okay, sei C gleich C1 bis Cm die Menge der Konjunktionen, wobei Ci
gleich Ci1 oder Ci2 oder Ci3.
Also es ist jetzt einfach nur Notation, wie schreibe ich dieses Drei
-Sat -Problem auf.
Und da sage ich eben, ich habe m Konjunktionen und ich nummeriere die
durch von 1 bis m.
Und die Literale nenne ich jeweils Zi1 oder Zi2 oder Zi3.
Und das Zij ist natürlich Element aus X1 oder eines dieser Elemente
und das kann eben X1 bis Xn sein oder die Negation.
Also X1' bis Xn'.
Also das hier wäre Z11, das wäre Z12, Z13 in unserem Beispiel, das
wäre Z21 und eben Z21 ist jetzt gleich X1'.
Okay, nur Notationsfrage, aber das ist eben wichtig.
Gut, jetzt sagen wir, wir konstruieren einen Graphen mit 3m Knoten.
Und wir bezeichnen die Knoten nicht mit einer einzelnen Zahl, sondern
mit einem Paar ij.
Und zwar i von 1 bis m, das ist also gerade die Konjunktion.
Und j von 1 bis 3, wir haben also für jedes Zij einen Knoten.
Und wie zeichnen wir jetzt die Graphen?
Die zeichnen wir nach dieser Bedingung, wir zeichnen eine Kante von ij
nach i' j'.
Genau dann, wenn i ungleich j ist,
ich vermute, dass das verkehrt ist und dass das heißen müsste i
ungleich i'.
Ich schreibe es mal hin.
Schreiben will er auch nicht mehr.
Also ich vermute, dass das hier i' a, dass das hier i' i' heißen
sollte.
Denn die Idee ist, dass diese zwei Knoten in verschiedenen Klauseln
stehen sollen.
Also beispielsweise von diesem Literal zu diesem Literal könnte ich
eine Kante ziehen nach dieser ersten Bedingung, weil sie in
unterschiedlichen Konjunktionen steht.
Und als zweite Bedingung setze ich, dass Zij ungleich Zij' ist.
Das heißt, es sind beide Literale gleichzeitig erfüllbar.
Ja, wenn natürlich das eine X5 ist und das andere ist nicht X5, also
X5', dann sind die nicht beide gleichzeitig erfüllbar und dann möchte
ich auch keine Kante zwischen denen ziehen.
Okay, das sind also die zwei Bedingungen.
Und es ist relativ klar, dass ich diesen Graphen in polynomialer Zeit
erzeugen kann.
Ich zeichne mir diese drei M-Knoten hin und überlege dann für jedes
Paar Zij und J', erfüllen die diese Bedingungen, sind diese Variablen
in unterschiedlichen Klauseln und sind sie gleichzeitig erfüllbar.
Gut, jetzt wählen wir das K gleich M.
Das K ist ja das Gegebene und das M ist gerade die Anzahl der
Klauseln.
Und wir sagen jetzt, die Annahme ist jetzt G hat einen Clique der
Größe M.
Also wir können das Cliquen-Problem lösen.
Dann gibt es natürlich M Literale in M, in M verschiedenen
Konjunktionen, weil wir ja nur diejenigen verbunden haben, die auch
tatsächlich in unterschiedlichen Konjunktionen sind und die alle
gleichzeitig erfüllt werden können.
Und dann hätte ich eben das Dreisatzproblem gelöst, denn wenn es eine
solche Clique gibt, dann kann ich das Dreisatzproblem lösen und wenn
es keine solche Clique gibt, kann ich sie eben nicht lösen.
Und daraus folgt aus dieser Reduzierbarkeit, dass das Clique-Problem
NP schwer ist.
Das war also jetzt ein relativ einfaches Beispiel, wie man so eine NP
-Vollständigkeit nachweisen kann.
Okay, eine Bemerkung noch.
Meistens sind solche Optimierungsprobleme wirklich als
Optimierungsproblem definiert.
Und wir haben uns jetzt hier nur angeschaut, gibt es eine Clique der
Größe K in G oder gibt es eine Belegung der Variablen, sodass es
erfüllbar ist.
Also wir haben Entscheidungsprobleme angeschaut.
Prinzipiell finden Sie drei typische Problemstellungen.
Die eine Problemstellung wäre für dieses Clique-Problem, Sie haben
einen Graphen gegeben und Sie haben einen K gegeben und gibt es eine
Clique der Größe K in dem Graphen.
Das ist das, was wir gerade eben auch betrachtet haben.
Eine alternative Fragestellung wäre, Sie haben einen Graphen gegeben,
berechnen Sie das größte K, sodass der Graph eine K-Clique enthält.
Also was ist das größte K, für das es noch eine Clique gibt?
Für K gibt es noch eine Clique, für K plus 1 gäbe es keine mehr.
Und die dritte mögliche Fragestellung wäre, gegeben sei ein Graph,
berechnen Sie eine Clique, sodass es eben keine größere Clique gibt.
Also eine Clique mit K, sodass es keine größere Clique gibt.
Das heißt, Sie wollen nicht nur das K wissen, bei der dritten
Fragestellung, sondern Sie wollen außerdem wissen, welches ist denn
die Clique, welche Knoten gehören denn zu dieser Clique dazu.
Drei verschiedene mögliche Fragestellungen, ganz offensichtlich ist,
wenn Sie Fragestellung I lösen können, also beispielsweise
Fragestellung 3, dann können Sie natürlich auch I minus 1 lösen, also
2 oder 1.
Denn wenn Sie die maximale Clique berechnen können, dann brauchen Sie
ja nur abzählen, wie viele Knoten sind da drin, dann kennen Sie das
maximale K.
Und wenn Sie das K kennen, dann können Sie natürlich auch bei der
Problemstellung 1 angeben, okay, es gibt eine, die ist so groß oder es
gibt eben keine.
Interessanterweise gilt auch die Umkehrung, was ich jetzt hier nur mal
so ganz grob skizzieren möchte.
Wenn Sie nämlich die Fragestellung 1 lösen können, gibt es eine Clique
der Größe K, dann können Sie auch die Fragestellung 2 lösen.
Sie können nämlich eine binäre Suche machen.
Es können ja maximal, die maximale Größe ist ja beschränkt.
Es können nicht mehr, die Clique kann nicht größer sein, als die
Knoten in Ihrem Graphen haben.
Das heißt, Sie können bei N halber anfangen, können Problem 1 lösen
und dann wissen Sie, gibt es eine Clique der Größe N halber.
Wenn ja, dann wissen Sie, okay, wir sind in der oberen Hälfte, das
Maximum ist größer als N halber.
Wenn nein, wissen Sie, das Maximum ist kleiner als N halber.
Und dann können Sie das eben nach binärer Suche relativ schnell lösen
und haben dann in polynomieller Zeit auch, weil Sie ja maximal log N
Schritte brauchen, das größte K gefunden, für das es eben noch geht.
Und wenn Sie das größte K kennen, dann können Sie auch die Frage 3
berechnen und können wirklich prüfen, welche Knoten gehören denn dazu,
indem Sie einfach probeweise eine Kante aus dem Graphen herausnehmen,
das Problem nochmal lösen.
Wenn sich dadurch die Cliquegröße nicht ändert, war diese Kante nicht
wichtig für die Clique und sie kann ignoriert werden.
Und dadurch können Sie eben eine Kante nach der anderen herausnehmen
und letztendlich das Problem so weit reduzieren, bis Ihnen Ihr
Verfahren das 1 und 2 löst, sagt okay, jetzt gibt es keine so große
Clique mehr und dann haben Sie eben das Minimum gefunden.
Okay, das gleiche gilt für die meisten Optimierungsprobleme, das
heißt, wenn Sie NP-Vollständigkeit nachweisen wollen, dann genügt es
im Allgemeinen, sich die Entscheidungsvariante zu betrachten, also
das, was wir hier auch gemacht haben, das ist hier das
Entscheidungsproblem zu diesem Cliqueproblem und es reicht dafür, die
NP -Vollständigkeit normalerweise nachzuweisen.
Okay, warum beschäftigen wir uns überhaupt oder für Sie vielleicht
noch zusätzlich als Motivation, wenn Sie später mal in irgendeiner
Firma arbeiten und Ihr Chef gibt Ihnen die Aufgabe, hier wir haben
dieses Optimierungsproblem, was weiß ich, Tourenplanung,
Produktionsplanung, was auch immer, lösen Sie dieses Problem möglichst
optimal.
Dann können Sie da irgendwie 1-2 Wochen darüber nachdenken und Sie
können dann vielleicht letztendlich, kommt Ihnen nicht die richtige
Idee, Sie finden keinen effizienten Algorithmus, der das in
vernünftiger Zeit löst, um dieses Problem zu lösen.
Dann können Sie jetzt natürlich zu Ihrem Chef gehen und sagen, ich
kann keinen effizienten Algorithmus finden, vielleicht bin ich zu
dumm, wird Ihren Chef nicht sonderlich begeistern, kann ich mir
vorstellen.
Oder Sie könnten etwas mutiger auftreten, wenn Sie von sich selber
überzeugt sind und sagen, ich kann keinen effizienten Algorithmus
finden, wahrscheinlich gibt es überhaupt keinen solchen.
Auch das, also wenn Sie es nachweisen können, ist gut, wunderbar,
wahrscheinlich können Sie es nicht nachweisen, das heißt, das ist eine
sehr mutige Aussage und wenn Ihr Chef dann hinterfragt, dann wird er
feststellen, ja okay, das passiert eigentlich, Sie machen da
irgendeine Aussage, aber ohne Fundament darunter.
Jetzt nachdem Sie die Vorlesung gehört haben, können Sie zu Ihrem Chef
gehen und vielleicht sagen, ich kann keinen effizienten Algorithmus
finden, aber ich kann beweisen, dass das Problem NP vollständig ist
und das bedeutet, dass jede Menge andere berühmte Leute sich schon an
diesen Problemen versucht haben und keinen effizienten Algorithmus
finden konnten.
Also es gibt mit sehr, sehr großer Wahrscheinlichkeit wirklich keinen,
zumindest hat bisher noch keiner einen effizienten Algorithmus
gefunden.
Und damit müsste Ihr Chef eigentlich zufrieden sein.
Okay, jetzt ist noch die Frage, was können Sie Ihrem Chef als
Alternativen anbieten, wenn Sie nachgewiesen haben, das Problem ist NP
vollständig.
Sie könnten zusammen mit Ihrem Chef überprüfen, ob das Problem in
einer eingeschränkten Form vorliegt.
Ob Sie gewisse Rahmenbedingungen haben, die das Problem einfacher
machen als das generelle Problem.
Und dann könnte eventuell eine effiziente Lösung möglich sein.
Oder es gibt Situationen, in denen Sie sich vielleicht mit einer
suboptimalen Lösung zufrieden geben können.
Dann könnte man versuchen, polynomiell berechenbare Approximationen zu
finden.
Für das Euklidische TSP, also wenn Sie eine Ebene haben und Sie haben
die Abstände von einer Stadt zu einer anderen Stadt entsprechend genau
der euklidischen Distanz, also im Prinzip der Luftlinie, dann wirkt
das zum Beispiel ein Verfahren, dass das TSP in polynomieller Zeit,
sogar in quadratischer Zeit, also in kleiner polynomieller Faktor, bis
auf einen Faktor 1,5 approximiert.
Das heißt, Sie können mit dem Verfahren beweisen, dass Sie die
minimale Länge, die ja gesucht ist, um nicht mehr als 50%
überschreiten mit Ihrer Lösung.
Viel besser können Sie aber nicht mehr werden.
Also nicht in polynomieller Zeit, sonst wäre das Problem ja auch nicht
NP -vollständig.
Oder Sie können sich überlegen, eine geeignete systematische
Entwurfsmethodik anzuwenden.
Haben Sie hoffentlich in Operations Research gelernt, dynamisches
Programmieren sagt Ihnen vielleicht was oder Branch and Bound oder
Divide and Conquer.
Die erlauben Ihnen oder die gehen eben ganz systematisch an das
Problem ran und sind dadurch besser als eine beispielsweise
vollständige Enumeration aller Lösungen.
Sie würden also beim Traveling Assessment Problem wäre ja die naive
Lösung vielleicht, okay, ich probiere alle möglichen Reihenfolgen
durch.
Das ist natürlich sehr ineffizient und Sie können eben mit
entsprechenden Techniken das sehr stark reduzieren.
Die Lösungen, die Sie überhaupt anschauen müssen und so weiter.
Trotzdem ändert das nichts an der NP-Vollständigkeit.
Sie können deswegen, auch wenn das noch so systematisch und so toll
ist das Verfahren, kommen Sie nicht auf polynomielle Zeit runter.
Das heißt, es gibt auch nur, wenn Sie die Optimallösung finden wollen,
für kleine Probleminstanzen.
Aber vielleicht für größere als irgendwie ein naiver Ansatz.
Und vielleicht reicht es Ihnen ja, vielleicht wissen Sie, Sie haben
nie mehr als 100 Städte in Ihrem Problem, dann könnte sowas schon
ausreichen.
Eine andere Alternative wäre, dass Sie auf die Garantie für eine
bestimmte Lösungsgüte ganz verzichten.
Dass Sie also sagen, okay, dass es nicht optimal geht, habe ich schon
akzeptiert, aber ich kann auch keine Grenze angeben, wie hier in dem
Fall der Approximationen.
Aber dafür habe ich ein Verfahren, das sehr schnell ist.
Und das ist häufig auch ein wichtiger Aspekt, dass Sie innerhalb von
wenigen Sekunden eventuell berechnen können, zumindest eine halbwegs
vernünftige Lösung angeben können.
Ohne Garantie, die aber in den meisten Fällen eine relativ gute
Lösungsqualität bietet.
Beispiel hier ist Nearest Neighbor Heuristik für das TSP.
Das wäre, Sie fangen bei einer zufälligen Stadt an und Sie gehen dann
als nächstes immer zu der noch nicht besuchten Stadt, die die kleinste
Distanz hat von der Stadt, wo Sie jetzt sind.
Primitives Verfahren läuft sehr schnell, weil Sie immer nur in Ihrer
Nachbarschaft gucken müssen, was ist jetzt die nächste Stadt.
Sie laufen da einmal durch und dann haben Sie Ihre Tour erstellt, aber
Sie haben eben keine Garantie für die Lösungsqualität.
Die kann unter Umständen beliebig schlecht sein.
Oder Sie setzen randomisierte Verfahren ein, um den Lösungsraum zu
durchsuchen.
Beispiele wären hier Tabusuche, Simulated Annealing, Evolutionäre
Algorithmen oder Ameisenalgorithmen.
Wenn Sie an der Thematik interessiert sind, ich biete im
Sommersemester immer die Vorlesung Naturanaloge und verteilte
Optimierungsverfahren an.
Da werden genau diese Verfahren beschrieben und die erzeugen mal ein
paar verschiedene Lösungen, gucken wie gut sind diese Lösungen und
konzentrieren sich dann auf die guten Lösungen, versuchen noch mehr,
also aus diesen guten noch bessere zu erzeugen und mehr in die
Richtung zu suchen, wo die vielversprechend waren.
Meistens irgendwie so inspiriert durch Verfahren, die man sich aus der
Natur abgeguckt hat.
Gut, damit wäre ich am Ende von diesem Teil 1 Theoretische Aspekte
angelangt.
Lassen Sie mich noch mal ganz kurz zusammenfassen, was wir jetzt seit
Anfang des Semesters hier gemacht haben.
Wir haben formale Beschreibungen kennengelernt für
informationsverarbeitende Systeme.
Da ist eben insbesondere hervorzuheben die Automaten und die
Grammatiken, aber auch die regulären Ausdrücke.
Wir haben uns jeweils angeschaut, was ist denn die Ausdrucksfähigkeit
dieser Beschreibungen und wie effizient sind die jeweils, also wie
effizient kann ich mit denen arbeiten, wie effizient kann ich
beispielsweise, oder wie aufwendig ist diese Worterkennung, das ist
hier dieser Aspekt.
Wir haben uns angeschaut, welche sind denn äquivalent.
Also wir haben gesehen, dass die Typ-3-Grammatiken gerade genauso
mächtig sind wie die endlichen Automaten und so weiter.
Wir haben dann eben so eine Hierarchie aufgebaut, dass endliche
Automaten weniger können als Keller-Automaten.
Die können wieder, also deterministische, dann haben wir nicht
-deterministische, die haben die Turing-Maschinen und so weiter.
Was für uns eben auch interessant war in Bezug auf
Programmiersprachen, wo wir gesagt haben, eigentlich
Programmiersprachen sollten durch deterministische Keller-Automaten
erkannt werden können oder eben durch LRK-Grammatiken erzeugt werden,
weil die eben gerade die notwendige Ausdrucksfähigkeit haben, aber
eben noch effizient überprüfbar sind.
Und wir haben uns prinzipielle Grenzen der Informatik angeschaut in
der letzten Stunde und heute, also Fragen der Berechenbarkeit und der
Entscheidbarkeit und der Komplexität.
Gut, im Folgenden werden wir uns hier in der Vorlesung mit dem
nächsten Thema beschäftigen und da wird sie Herr Schmeck durchführen
und da geht es um Schaltnetze und Schaltwerke und dann übergebe ich
jetzt an Herrn Professor Schmeck.
Ja, schönen Tag, ich begrüße Sie auch nochmal ganz herzlich zur
Vorlesung Informatik II, zweiter Teil.
Herr Branke hat Ihnen ja den ersten Teil vorgeführt, die Aspekte der
theoretischen Informatik, wo es wichtige Grundlagen gab, um Dinge zu
verstehen, die wir in der Informatik machen.
Schauen wir uns jetzt den zweiten Teil an.
Da geht es um die Architektur von Rechensystemen, all das, was wir uns
so anschauen können, wenn es darum geht, ja, womit rechnen wir
eigentlich?
Herr Branke, nochmal vielen Dank, dass Sie den ersten Teil übernommen
hatten.
Dadurch hatte ich Zeit, mich um ein paar andere Dinge zu kümmern und
jetzt kümmere ich mich halt um den zweiten Teil.
Was machen wir eigentlich da drin?
Kurzer Rückblick, das hat gerade eben Herr Branke Ihnen erzählt,
formale Modelle der Informatik hat er behandelt.
Und jetzt geht es um den zweiten Teil, Architektur von Rechensystemen.
Ich werde Ihnen zunächst etwas erzählen über Schaltnetze und
Schaltwerke und also etwas über so die Hardwaregrundlagen.
Wir werden uns dann mit der Darstellung von Informationen im Rechner
beschäftigen, mit der Codierung von Informationen, mit der
Zahlendarstellung.
Und warum wollen wir Zahlen darstellen?
Wir wollen natürlich etwas rechnen.
Wir wollen also auch wissen, wie können wir eigentlich im Rechner die
arithmetischen Operationen ausführen.
Das machen wir dann halt in diesem Teil und anschließend schauen wir
uns die Rechnerarchitektur an.
Da gibt es ganz spezielle Architekturprinzipien, die man realisiert
bei Rechenanlagen.
Alle Prozessoren sind nach einem einheitlichen Prinzip aufgebaut und
darauf folgen dann einige Ausführungen zu verschiedenen Ebenen der
Programmierung, von der untersten Ebene der maschinennahen
Programmierung bis hin zu der höchsten Ebene, also irgendwelche
höheren Programmiersprachen, problemorientierte Programmiersprachen,
die wir ja brauchen, um entsprechend den Problemen unserer Programme
schreiben zu können.
Wichtig auch die Frage der Betriebssysteme.
Die Betriebssysteme sorgen ja dafür, dass wir Rechner effizient nutzen
können, dass wir als Nutzer besten Service kriegen vom Rechner und
andererseits der Rechner effizient, also möglichst gut ausgelastet ist
und das ist etwas, was sich eigentlich widerspricht, weil ja jeder
Benutzer möglichst exklusiven Zugriff haben möchte auf den Rechner,
aber die Betriebssysteme sind halt in der Lage das zu erreichen und am
Ende, wenn noch Zeit bleibt, erzähle ich Ihnen noch etwas über
Dateiorganisation.
Also, ich beginne mit einem Abschnitt, den Sie schon einmal gesehen
haben, nämlich in Informatik 1, da hat Ihnen Herr Studer etwas erzählt
über bursche Algebren.
Ich möchte das ganz kurz wiederholen, weil das für den Teil, den wir
dann gleich machen werden, eine wichtige Grundlage ist.
Das ist eine wichtige Grundlage für die Behandlung von Schaltnetzen
und Schaltwerken.
Ganz kurze Wiederholung der Begriffe, vielleicht ist es Ihnen noch in
Erinnerung.
Es geht also um den Begriff der burschen Algebra und was ist eine
bursche Algebra?
Das ist eine algebrasche Struktur, also haben wir hier eine Menge M
versehen, das ist also eine Menge mit mindestens zwei Elementen.
Standardbeispiel ist eine bursche Algebra, die zwei Elemente hat, aber
generell kann es eine beliebig große Menge aus sein und wir haben
einige Operationen, nämlich drei Verknüpfungen, einmal das bursche
Produkt, dann die bursche Summe und das bursche Komplement.
Also drei Verknüpfungen, zwei zweistellige Verknüpfungen, eine
einstellige Verknüpfung.
Und Sie erinnern sich hoffentlich daran, dass diese algebraische
Struktur einige Eigenschaften haben sollte.
Wir haben einige Axome gefordert, also Eigenschaften, die jede bursche
Algebra haben muss.
Das ist ja nur eine allgemeine Struktur hier, die man konkret
ausfüllen kann.
Und jede bursche Algebra muss also diese Huntington'schen Axome
erfüllen.
Der Huntington hat sich dadurch hervorgetan oder hier seinen Namen für
gegeben, dadurch, dass er gezeigt hat, diese vier Eigenschaften sind
ausreichend, um die gewünschten Eigenschaften der burschen Algebra
festzulegen.
Alle anderen Eigenschaften, die wir auch gerne haben, kann man daraus
dann ableiten.
Das eine ist eine Eigenschaft, die Sie auch alle kennen,
Kommutativität.
Das heißt, wir können die Operanden bei der Anwendung der Operationen
beliebig vertauschen.
Also A mal B ist immer gleich B mal A.
Sowohl für das Produkt gilt das, als auch für die Summe.
Also A plus B ist auch gleich B plus A.
Dann sind die beiden Operationen wechselseitig distributiv.
Und da kommt etwas, was Sie aus der Mathematik, aus dem normalen
Umgang mit algebraischen Strukturen im üblichen Rechnen eigentlich
nicht kennen.
Denn da kennen Sie nur diese Form hier der Distributivität, dass
nämlich A mal B plus C gleich A mal B plus A mal C ist.
Distributiv heißt ja, ich verteile etwas über etwas anderes.
Und was ich verteile, ist hier diese Operation Produkt.
Das Produkt verteile ich über die Komponenten, die in der Klammer
stehen.
Also das Produkt wird verteilt auf das B und auf das C.
Und genau so kann ich das natürlich auch machen bei den anderen
Operationen.
Hier wird die Verknüpfung plus, die Summe verteilt über die Operanden
in der Klammer.
Das heißt, da schreibe ich dann hin A plus B mal A plus C.
Das ist etwas, was wir aus der normalen Arithmetik nicht kennen, aber
gilt halt im buchenalen Algebra.
Das ist eine ganz wichtige Eigenschaft.
Und das ist Ihnen auch allen, denke ich, bekannt.
Dann brauchen wir zwei neutrale Elemente, die Elemente 0 und 1.
Es ist also das 1-Element in Bezug auf das Produkt.
Das heißt A mal 1 ist gleich A für alle Elemente der Menge M.
Und die 0 ist das 1-Element in Bezug auf die Addition.
Gleichzeitig das A plus 0 ist A.
Gleichzeitig das 0-Element in Bezug auf die Multiplikation.
Das steht hier aber übrigens gar nicht.
A mal 0 gleich 0.
Das steht da nicht.
Das ist aber so.
Das kann man aus diesen Aktionen hier schon schließen.
Und schließlich das A' ist, also die dritte Verknüpfung, das
Komplement.
A' ist komplementär zu A in der folgenden Weise, dass nämlich gerade A
mal A' gleich 0 ist.
Wenn Sie A und A' modifizieren entsprechend dieser Produktoperation,
dann kommt dabei das neutrale Element 0 heraus.
Also das sind die Eigenschaften, kurz wiederholt.
Es gibt eine ganze Reihe weiterer Eigenschaften.
Die kennen Sie hoffentlich alle auch noch.
Typische 0-1-Gesetze.
A mal 1 gleich A.
Das wissen wir bereits.
A mal 0 ist 0.
Dann steht hier A plus 1 ist 1.
A plus 0 ist A.
Okay, dieses A plus 0 gleich A, das wussten wir bereits aus dem ersten
Aktionen.
Hier ist es nochmal zusammengefasst.
Dann haben wir Idempotenz-Gesetze.
A mal A gleich A.
Also Sie können...
Das Produkt ist halt eine Operation, sodass für jedes Element der
Menge, dass sie selbst idempotent ist.
Wenn Sie es mit sich selbst modifizieren, bekommen Sie das Element
selber heraus.
Sie wissen, dass in der normalen Arithmetik haben wir das so, dass 1
mal 1 gleich 1 ist.
Das ist das einzige idempotente Element.
Hier ist jedes Element idempotent.
Sowohl bezüglich der Modifikation als auch bezüglich der Addition.
Dann gibt es die Assoziativ-Gesetze.
Das heißt A mal B mal C ist gleich A mal B in Klammern mal C.
Entsprechend für die Addition oder für die Summe.
Warum ist das eigentlich wichtig?
Wenn man dieses Gesetz hat, wenn das gilt in irgendeiner algebraischen
Struktur, dann heißt das, es kommt auf die Reihenfolge der Operationen
überhaupt nicht an.
Und wenn das nicht so wäre, dann wäre für den Informatiker eigentlich
die ganze Rechnerei schon erledigt.
Dann könnten wir gar nichts mehr umordnen.
Dadurch, dass wir das Assoziativ-Gesetz haben in der normalen
Mathematik, als auch hier in dieser buchstablichen Algebra, dadurch
können wir die Reihenfolge von Operationen verändern.
Wir können sie in der beliebigen Reihenfolge anordnen.
Wir können sie auch dadurch so umordnen, dass wir vielleicht daraus
einen sogenannten Berechnungsbaum machen.
Das werden wir später noch sehen.
Und dadurch kann man wesentlich effizientere Formen einer Berechnung
überhaupt erst entwickeln im Vergleich zu Operationen, die vielleicht
nicht assoziativ wären.
Da hätten Sie noch eine Möglichkeit, das auszuführen.
Und schließlich Regeln wie die De Morgan'schen Regeln.
Auch die kennen Sie vermutlich alle.
A mal B in Klammern Kompliment ist gleich A-Kompliment plus B
-Kompliment.
Entsprechend das Gesetz für die Summe.
Also wenn A plus B dazu das Kompliment genommen wird, dann bekommen
wir gerade A-Kompliment mal B-Kompliment heraus.
Und wir haben schließlich noch das Absorptionsgesetz.
Das heißt A mal A plus B ist gleich A.
Das heißt eine Erweiterung von A.
Im Prinzip, wenn Sie zu A etwas dazu addieren und dann das mit A
multiplizieren, kommt wieder das A heraus.
Und entsprechend für die Summe A plus A mal B ist gleich A.
Vielleicht ist Ihnen hier gerade eben etwas aufgefallen.
Wir haben hier immer so zwei Dinge nebeneinander stehen.
Auf der linken Seite stehen hier so einige Dinge mit dem Produkt und
auf der rechten Seite mit der Summe.
Das heißt wir haben in diesem Bereich hier einiges stehen, was links
daneben zumal stand, aber etwas anders.
Was ist der Unterschied?
Sie ersetzen einfach in zum Beispiel hier dieser Formel mit diesem
Ausdruck, dieser Gleichung, jedes Vorkommen des Produkts durch eine
Summe und bekommen dann das andere.
Und wenn Sie sich das hier anschauen, zum Beispiel hier A mal 0 gleich
0, die dazu passende Form ist diese hier.
A plus 1 ist 1.
Sie haben also das Produkt durch die Summe ersetzt und die 0 durch die
1 ersetzt.
Entsprechend ergibt sich hier die andere Gleichung.
Das was ich Ihnen hier gerade eben erläutert habe, das ist das
sogenannte Dualitätsprinzip, das in der burschen Algebra gilt, wenn
Sie irgendeine Aussage haben über einen solchen Ausdruck hier, oder
irgendeine Gleichung haben, in der Sie halt einfach dann alle Produkte
durch Summen ersetzen und die 1 durch die 0 und die 0 durch die 1
ersetzen, dann bekommen Sie wieder eine Gleichung raus.
Und das erleichtert einiges, wenn man Aussagen macht über bursche
Algebrennen, weil man sich nur für eine Hälfte der Ausdrücke überhaupt
Überlegungen machen muss.
Die andere bekommt man durch das Dualitätsprinzip geschenkt.
Dann gibt es noch etwas, das sogenannte doppelte bursche Komplement.
Wenn Sie das Komplement zweimal anwenden, dann gibt es die
Identitätsfunktion und schließlich noch die Aussage, dass das
Komplement des Null-Elements gerade das 1-Element ist und das
Komplement der 1 ist gerade die 0.
Also diese Gesetze kennen Sie wahrscheinlich alle, ich nehme an, dass
einige von Ihnen, die auch in der Schule sogar schon gelernt haben,
also das ist...
Wer von Ihnen hat in der Schule gelernt?
Niemand.
Was haben Sie denn für Matheunterricht gehabt?
Aber wer von Ihnen konnte sich nicht mehr daran erinnern, diese Sachen
schon gesehen zu haben in Informatik 1?
Wer konnte sich erinnern?
Ah, doch, ok.
Ich denke, es haben auch keineswegs alle in Informatik 1 schon gehört,
insofern kann es durchaus sein, dass es einige noch nicht gehört
haben.
Also, das waren die Eigenschaften, man kann diese, nochmal kurz
zurück, die Eigenschaften, die wir hier gesehen haben, diese Gesetze,
kann man alle ableiten aus den 4 Aktionen, die ich Ihnen vorhin
gezeigt habe, bei der Definition der burschen Algebra.
Das will ich hier alles nicht machen, das ist nur eine kurze
Wiederholung, damit Sie nochmal eingestimmt werden, worum es hier
eigentlich geht.
Was haben wir bei den burschen Algebren zu betrachten?
Wir wollen natürlich auch Funktionen betrachten, Abbildungen, die
Elemente von burschen Mengen, von burschen Algebren verknüpfen und die
abbilden auf andere.
Und was uns interessiert, ist besonders eine spezielle Form der
burschen Algebren, bei der wir hier diese zweielementige Menge haben,
b gleich 0,1, die bursche Menge.
Und jede Abbildung, also jede Abbildung f von b hoch n nach b, heißt
bursche Funktion.
Also eine endstellige Abbildung, die als Ergebnis entweder 0 oder 1
hat.
Genauso schauen wir uns bursche Terme an.
Bursche Terme, bursche Ausdrücke, auch der Begriff ist Ihnen
eigentlich bekannt, was man darunter versteht.
Wir brauchen gewisse Variablen.
Hier habe ich hingeschrieben a1, a2 bis an.
Wir könnten genauso gut hier hinschreiben a, b, c und so weiter,
beliebige Buchstaben.
Wir brauchen einfach nur ein Vorrat von Symbolen, um über Elemente der
burschen Algeber reden zu können.
Wir brauchen Variablen.
Und die bezeichnen wir halt in der Regel mit kleinen Buchstaben.
Dann brauchen wir eine Menge von Symbolen, um die Ausdrücke bilden zu
können.
Und wir nehmen natürlich an, dass die Symbole, die wir hier brauchen,
das sind also die 0, die 1, das Produktzeichen, das Pluszeichen, das
Komplementzeichen, Klammer auf und Klammer zu, die sollen nicht selbst
in der Menge der Variablen schon drin sein.
Und dann kommt die Definition, die eigentlich uns sagt, was ein
Ausdruck ist.
Jede Konstante, also 0 oder 1, ist ein burscher Term oder burscher
Ausdruck.
Und jede Variable in der Menge der Variablen v ist ein burscher Term.
Und wenn a und b bursche Terme sind, dann eben auch die Terme a
Komplement drauf angewandt.
Also das Komplementzeichen praktisch dahinter gefügt.
Oder die Folge, dass wir erst ein Klammeraufzeichen hinschreiben, dann
den Ausdruck a, dann ein Produktzeichen, dann den Ausdruck b und dann
ein Klammerzuzeichen und entsprechend das gleiche mit dem Pluszeichen
dazwischen.
Das sind bursche Terme oder bursche Ausdrücke.
Und wenn wir auf diese Art und Weise aus burschen Ausdrücken wieder
neue bursche Ausdrücke erzeugen, bekommen wir alle burschen Terme
geliefert.
Also nur Zeichnereien, die Sie in endlich vielen Schritten
entsprechend diesen beiden Regeln 1 und 2 bilden können, sind bursche
Terme.
Gut.
Wir hängen die beiden zusammen.
Das was interessant ist, ist natürlich, dass ich jede bursche Funktion
durch einen burschen Ausdruck beschreiben kann.
Also ich habe irgendeine Funktion von b hoch n nach b.
Irgendeine Funktion.
Das heißt, ich kann zu jeder Kombination von Nullen und Einzeln in
dieser Menge b, das sind ja n Argumente, kann ich angeben, welcher
Wert daraus kommt.
Ich kann dazu einen burschen Ausdruck formulieren, der genau diese
Funktion beschreibt.
Andersrum geht es genauso.
Jeder bursche Ausdruck mit n verschiedenen Variablen definiert genau
eine endstellige bursche Funktion.
Sie können durch den burschen Ausdruck genau die Funktion beschreiben.
Wie kann man durch einen Ausdruck eine Funktion beschreiben?
Das ist ganz einfach.
Sie müssen ja nur jeder Variablen, die vorkommen, einen Wert 0 oder 1
zuweisen.
Und je nachdem, wie Sie das zugewiesen haben, können Sie dann die
Regeln der burschen Algebra anwenden, um daraus festzustellen, welche
Werte dabei rauskommen.
Entsprechend bekommen wir dann aus dem Ausdruck, durch die Belegung
der Variablen, das wollte ich vielleicht noch dazu schreiben, dass es
hier um die Belegung der Variablen geht,
durch die Belegung der
Variablen mit Werten aus b.
Dadurch, durch die Belegung der Variablen mit Werten aus b, kann ich
dafür sorgen, dass ich entsprechend den Regeln der burschen Algebra,
die wir gerade angeschaut haben, dadurch habe ich hier nur noch 0 und
1 drin, ich weiß, wie 0 und 1 kombiniert werden, dadurch weiß ich
sofort, welcher Wert am Ende entsteht.
Das, was ich hier gerade gesagt habe, hat damit zu tun, wie ich
bursche Funktionen darstellen kann.
Ich habe gerade eben gesagt, bursche Funktionen und Ausdrücke
entsprechen sich eineindeutig.
Es gibt aber sogar noch eine ganze Reihe anderer Arten, Funktionen
darzustellen.
Also ich kann ja auch mich ganz dumm stellen und sage, ich schreibe
einfach eine Tabelle auf.
Zum Beispiel hier für diese wohlbekannte Funktion a XOR b, das
exklusive oder von zwei Werten a und b, das XOR, das soll folgende
Funktion sein, wenn beide Werte hier a und b 0 sind, kommt 0 raus.
Entsprechend, wenn einer von den beiden 1 ist, das ist das exklusive
oder, einer von beiden ist 1, dann kommt eine 1 raus.
Und hier, wenn sie beide 1 sind, dann haben wir wieder eine 0.
Dadurch habe ich mit einer Tabelle die Funktion beschrieben.
Kann ich für jede Funktion machen.
Ich gebe für jedes Argument, für jede mögliche Argumentkombination,
schreibe ich den Wert auf.
Das ist natürlich eine sehr einfache Art, das aufzuschreiben, ist nur
sehr teuer, weil natürlich so eine Wertetabelle, wenn sie n Variablen
haben, 2 hoch n Zeilen hat.
Sie haben 2 hoch n mögliche Belegungen von n Variablen mit 0 und 1.
Deswegen haben wir halt diese anderen Arten der Darstellung, über zum
Beispiel boolische Ausdrücke.
Und bei den boolischen Ausdrücken stellt man schnell fest, man kann
viele äquivalente Ausdrücke finden, die die gleiche Funktion
beschreiben.
Wenn das aber so ist, dann interessiert man sich dafür, wie man das
irgendwie normieren kann.
Deswegen interessieren wir uns für Normalformen.
Und zwar haben wir uns die disjunktive Normalform und die konjunktive
Normalform angeschaut bei Informatik 1.
Und disjunktive Normalform, das ist eine Disjunktion von Konjunktion
bzw.
eine Summe von Produkten.
Da sehen Sie hier die disjunktive Normalform, eine Summe von
Produkten.
Und wo kommen diese Produkte her?
Bei der disjunktiven Normalform, sogar bei der kanonischen
disjunktiven Normalform.
Erinnern Sie sich alle an das Verfahren, wie man das macht.
Man nimmt sich hier die 1-Zeilen der Wertetabelle, zum Beispiel.
Das ist der Term, der dieser 1-Zeile entspricht.
Warum?
Hier steht vorne eine 0 bei A und eine 1 bei B.
Und deswegen schreiben wir das A in komplementierter Form auf.
A' multipliziert also im Produkt mit B.
B tat hier auf als 1, hat den Wert 1.
Deswegen schreiben wir das B hin.
Also für jede 0 in dieser Zeile schreiben wir die Variable in
komplementierter Form hin.
Für jede 1 in der Zeile, in dieser Wertekombination, schreiben wir die
Variable in der nicht komplementierten Form hin.
Und entsprechend haben wir dann für die nächste Zeile diesen Term.
Da war das A 1 und entsprechend das B 0, deswegen steht hier A mal B'.
Also das ist die disjunktive Normalform, sogar die kanonische
disjunktive Normalform, für die Funktion Axor B, entsprechend der
Wertetabelle dort.
Und genau so kann man die konjunktive Normalform erzeugen.
Wie sah das bei der konjunktiven Normalform aus?
Da musste man ja ein Produkt von Summen bilden.
Und erinnern Sie sich an das Verfahren, wie man das gemacht hat?
Aus der Wertetabelle hat man sich die Nullzeilen genommen.
Und entsprechend gibt also diese Nullzeile, die führt zu dem Term A
plus B.
Da wurde nämlich für jeden 0 die Variable so hingeschrieben.
Und für jeder 1, wie hier bei der letzten Zeile, für jeder 1 in der
Wertetabelle wurde die Variable in komplementierter Form
hingeschrieben.
Und entsprechend die Variable dann addiert.
Das gibt also die Summen, die einzelnen Max-Therme.
Die Produkte oben bei der disjunktiven Normalform waren die Min
-Therme.
Und die werden halt einfach dann multipliziert.
Also haben wir hier zwei Normalform-Darstellungen der XOR-Funktion.
Einmal als disjunktive Normalform, einmal als konjunktive Normalform.
Ist Ihnen allen, zumindest also schon mal erzählt worden, hoffentlich
auch noch bekannt.
Und jetzt kommt eine dritte Form der Darstellung, die Ihnen noch nicht
bekannt ist.
Oder wer von Ihnen kennt ein Binary Decision Diagram?
Da hat sich noch niemand von Ihnen mit modernen CAD-Methoden
beschäftigt.
Binary Decision Diagrams sind eine wesentlich modernere Form der
Repräsentation von Funktionen.
Eine Datenstruktur im Wesentlichen, die sehr schöne Eigenschaften hat,
die wir uns nachher gleich anschauen werden.
5 Minuten habe ich noch.
Also, Sie sehen gleich als Unterschied, wie muss man hier zum Beispiel
einen Wert ermitteln in der Wertetabelle.
Wenn wir ein Funktionswert aus der Wertetabelle heraussuchen, schauen
wir uns an, die Belegung der Variablen mit Werten, das liefert uns
irgendeine Zeile, zum Beispiel diese hier.
Wenn wir die Zeile haben, brauchen wir nur nachzuschauen, aha, da
haben wir den Wert 1 und wir sind fertig.
Das ist ein Zugriff auf eine Tabelle, die irgendwo abgelegt ist.
Wenn Sie einen entsprechend großen Speicherplatz haben, haben Sie alle
zwei Einträge irgendwo abgelegt.
Konstante Zugriffszeit auf diesen Eintrag, also konstante Zeit für die
Funktionsauswertung.
Fantastisch.
Leider exponentieller Platz, um das darzustellen.
Ja, aber konstante Zeit ist fantastisch.
Schauen Sie sich das hier an, mit der disjunktiven Normalform.
Wenn Sie das auswerten wollen, dann müssen Sie sich die Belegung der
Variablen mit Werten anschauen.
A und B haben irgendwelche Werte, zum Beispiel 0 und 1.
Und dann müssen Sie die 0 und die 1 in diesen Ausdruck hier einsetzen.
Und müssen anschließend den Ausdruck auswerten, entsprechend den
Regeln der Buchenalgeberin.
Und wenn Sie sich diese Funktion anschauen, stellen Sie sich vor, Sie
hätten eine XOR-Funktion mit N-Variablen.
Kann man definieren, das wäre so eine Art Paritizfunktion.
Die ist 1, wann immer Sie eine ungerade Zahl von Einsen haben, bei den
Argumenten.
Und 0, wenn Sie eine gerade Anzahl von Einsen haben.
Und das heißt schon, dass Sie, wenn Sie so eine Funktion durch eine
disjunktive Normalform darstellen wollen, dann hätten Sie hier einen
Ausdruck, der 2 hoch N minus 1 Terme hat.
Da müssten Sie überall jetzt die Variablenwerte einsetzen und
entsprechend diese disjunktive Normalform auswerten.
Das ist ein ganz schöner Aufwand.
Nämlich ein exponentieller Aufwand, wenn Sie Pech haben.
Je nachdem, wie Sie das organisieren.
Und das heißt, wir hatten bei der Wertetabelle Aufwand konstant, um
einen Wert zu berechnen.
Bei der disjunktiven Normalform haben wir einen Aufwand, der ist
exponentiell.
Übrigens, Aufwand konstant ist nur realistisch, wenn der Zugriff auf
ein Element in der Tabelle in konstanter Zeit erfolgen kann.
Wenn Sie Pech haben, müssen Sie da erst noch einen Aufwand von etwa
Logarithmus -Anzahl der Variablen treiben.
Aber immerhin deutlich schneller.
Und das gleiche gilt natürlich hier für die konjunktive Normalform.
Da haben Sie entsprechend einen Aufwand, der kann sehr hoch sein.
Und wenn Sie sich das Binary Decision Diagram anschauen, dann bekommen
Sie folgendes.
Dieses Binary Decision Diagram, das jetzt die XOR-Funktion beschreibt,
wird wie folgt verwendet.
Wir schauen uns den Wert der Variablen A an.
Und je nachdem, ob das eine 0 oder 1 ist, geht man nach links oder
nach rechts.
Wenn wir die Zeile nehmen, die da oben steht, das war die 0-Zeile,
gehen wir also zu der nächsten Variablen, zum B.
Schauen, welchen Wert B hat.
B hat den Wert 1.
Das heißt, wir gehen hier zu 1 rüber und sind fertig.
Das heißt, wir haben linearen Aufwand in der Anzahl der Variablen.
Übrigens habe ich das hier oben bei dem Zugriff auf die Wertetabelle
etwas unterschlagen.
Sie müssen natürlich erstmal feststellen, welche einzelnen Werte die
einzelnen Variablen haben.
Also im Prinzip haben Sie den Aufwand immer.
Sie müssen ja jeden Wert der Variablen sich anschauen.
Also besser kann es gar nicht sein.
Das heißt, hier haben wir, egal welche Werte A und B haben, immer nur
einen Pfad durch diesen Graphen durchzulaufen.
Und das ist der große Vorteil der Binary Decision Diagrams.
Linearer Aufwand, Sie brauchen sich nur die Werte der Variablen
anzuschauen, entsprechend durch einen Graphen durchzulaufen und
bekommen den Wert der Funktion geliefert.
Und das schauen wir uns jetzt nochmal diese Folie zur Motivation an.
Nächste Woche mache ich das dann ausführlich.
Motivation für Binary Decision Diagrams nochmal.
Die Probleme, die wir mit den anderen Standarddarstellungen haben,
sind einmal, dass die Schalttabelle viel zu groß ist.
Also, Schalttabelle ist sehr groß, hat nämlich exponentiellen Aufwand.
Obwohl das so ist, wird übrigens in modernen Hardware-Systemen, in
normalen Hardware-Bausteinen, werden viele Funktionen über
Wertetabellen dargestellt.
Das sind aber sehr kleine Funktionen, mit vielleicht 3 oder 4 oder 5
Variablen, aber nicht mit 20 oder 40 Variablen.
Dann ist die kanonische disjunktive Normalform oder die kanonische
konjunktive Normalform, die sind auch meist sehr groß, können also
auch exponentiell groß sein, selbst wenn man sie vereinfacht.
Das heißt, auch da ist der Rechenaufwand sehr groß, wenn man
Funktionen auswerten will.
Und wenn Sie die Eigenschaften von Bushing-Funktionen untersuchen
wollen, haben Sie einfach zu viel Aufwand zu treiben mit diesen
Darstellungen und deswegen nimmt man eben diese reduzierten
Funktionsgrafen oder Binary Decision Diagrams.
Ich habe geschrieben, dass in den letzten Jahren, seit 1986 steht
hier, also es ist schon immerhin 16 Jahre, eine Entwicklung, in der
man diese Datenstruktur sehr intensiv untersucht hat mit der ganzen
Reihe von Varianten und festgestellt hat, dass man die in
hervorragender Form gerade für den rechnergestützten Entwurf von
Hardware einsetzen kann.
Und deswegen muss man heutzutage, wenn man irgendwas erzählt über
Grundlagen von Hardwarestrukturen, muss man auch etwas über BDDs
erzählen.
Und das ist aber nicht nur für diesen Bereich wichtig, auch in anderen
Bereichen, wenn man Funktionen darstellt, kann man sehr hilfreich
diese reduzierten Funktionsgrafen einsetzen.
Das ist eine allgemeine Reform der Binary Decision Diagrams.
Und damit werden wir uns dann am Mittwoch ab 8 Uhr wieder
beschäftigen.
Vielen Dank.