Einen wunderschönen guten Morgen und willkommen zur letzten Übung für
Grundbegriffe der Informatik heute mit dem Übungsblatt Nummer 6 und
dem Bonus Übungsblatt mit der inoffiziellen Nummer 7.
Bei der ersten Aufgabe auf dem sechsten Übungsblatt ging es wieder um
einen Sortieralgorithmus, der in diesem Pseudocode gegeben war.
Und wenn man sich das anschaut, was dieser Sortieralgorithmus macht,
Das ist ein Divide-and-Conquer-Algorithmus, der auf den Namen
Mergesort hört.
Und der Grund, warum der Mergesort heißt, ist, dass dieser Schritt
hinterher, mit dem man die aufgeteilten Ergebnisse wieder vereinigt,
ein Merging ist, ein Verschmelzen von Listen.
Was dieser Algorithmus im Prinzip macht, ist, eine beliebige Liste
nimmt er, dann zerteilt er diese Liste in zwei Unterlisten, eine linke
Liste und eine rechte Liste.
Die werden dann irgendwie rekursiv sortiert, so dass was zurückkommt
aus den Aufrufen eine sortierte linke Liste ist und eine sortierte
rechte Liste.
Und dann werden diese rechte Liste und diese linke Liste zusammen
verschmolzen, sodass das Ergebnis dann eine Sortierung ist aller
Elemente, wenn man halt die linke Liste und die rechte Liste
miteinander vereinigt.
Und die Art und Weise, wie er das macht, ist ein relativ einfaches
Verfahren.
Angenommen, wir haben so zwei Listen vor uns liegen.
Dann realisiert man das in der Regel so, dass man zwei Zeiger hat.
Jeweils initialisiert damit, dass die auf den Anfang einer jeder der
beiden Listen zeigen.
Und dann vergleicht man, welches Element von denen, auf denen die
beiden Zeiger gerade zeigen, ist kleiner.
In unserem Fall wäre das das Element zwei.
Dann notiert man sich das Element zwei in der resultierenden Liste und
erhöht den Zeiger bei der Liste, wo man gerade ein Element eingefügt
hat.
Das heißt letztendlich wird diese zwei aus der Liste rausgenommen und
die Liste wird um eins verkleinert.
Dann guckt man wieder, welches von den beiden, worauf gezeigt wird,
ist das kleinere Element, ist nach wie vor die zwei.
Erhöht wieder den Zeiger.
Dann vergleicht man jetzt sieben und drei, stellt fest, drei ist das
kleinere Element.
Erhöht dementsprechend den anderen Zeiger.
Stellt fest, vier ist das kleinere Element.
Erhöht den Zeiger, stellt fest, fünf ist das kleinere Element.
Erhöht den Zeiger, stellt fest, sechs ist das kleinere Element.
Und jetzt hat man den Sonderfall, dass halt eine der beiden Listen
schon komplett abgearbeitet ist.
Das heißt, da gibt es nichts mehr zu vergleichen.
Und was man dann halt machen muss, ist, dass man entsprechend die
verbleibenden Elemente in der Liste, die noch nicht abgearbeitet
wurden, halt rüber kopiert.
Also die sieben rüber kopiert, die acht rüber kopiert.
Und dann ist man auch fertig, sind beide Listen abgearbeitet.
Das ist der Merge Schritt.
Und wenn man sich jetzt diesen Merge Schritt anschaut, was der so an
Zeit braucht, dann ist es klar, dass der halt immer linear durch die
Listen durchgeht.
Also man muss jedes Element in dieser Liste anfassen.
Das heißt, wenn jetzt so eine einzelne Liste N Elemente hat, muss man
so etwas wie maximal zwei Endschritte durchführen.
Das heißt, man liegt da also in der in der Laufzeit her von diesem
Merge Schritt in O log von N.
Und wenn man jetzt wissen will.
Was die Laufzeit des Gesamtalgorithmus ist, dadurch, dass das eben ein
Divide and Conquer Algorithmus ist, kann man schauen, ob man mit dem
Master Theorem weiterkommt.
Wenn man sich dann das Master Theorem anschaut, die A und B ermitteln.
A war die Anzahl.
Der.
Aber die Anzahl der Größe der Probleme, in die ich zerhackt habe.
Die Anzahl der Probleme, in die ich zerhackt habe.
Und die Größe muss halt sein, N durch B.
Ich zerhacke also das große Problem, sortiere Liste in zwei
Teilprobleme.
Also ist A gleich zwei.
Und das Ganze, die Liste wird immer halbiert.
Also ist die Größe der Unterteilprobleme N halbe.
Das heißt A gleich B gleich zwei.
Dann von D A können wir nach A C gehen, weil halt der Knoten hier mit
dem A aufhört und da mit dem A anfängt.
Dann von B D können wir nach D A gehen.
Von B D können wir auch nach D C gehen und von B D können wir auch
nach D E gehen.
Und damit haben wir auch alle Möglichkeiten abgedeckt.
Jetzt ist die Frage, was hat das für eine Bedeutung?
Was dieser Kantengraf im Prinzip sagt ist, welche Kante kann ich von
welcher Kante aus erreichen?
Im Kantengraf sind halt zwei Kanten miteinander durch eine Kante
verbunden.
Wenn ich halt die eine Kante von der anderen Kante aus über einen
Knoten gehend erreichen kann.
Und wenn ich halt die Wege durch den Kantengrafen abzeichne, dann kann
ich halt insgesamt die Erreichbarkeit von Kanten damit machen.
Wenn ich also die Wegematrix des Kantengrafen mache, dann weiß ich,
welche Kante im ursprünglichen Karf von welcher anderen Kante aus
erreichbar ist und gegebenenfalls auch in wieviel Schritten.
Dementsprechend, wenn man halt hier sowas macht, bei dem ABC-Grafen
hat man auch relativ schnell die Knoten aufgeschrieben.
Und A nach B.
Und kann dann entsprechend auch die Kanten einzeichnen.
Und dann bei dem Grafen hier kann man auch relativ schnell die Knoten
aufschreiben.
E nach A, E geht nach B, E geht nach C und E geht nach D.
Und dann stellt man fest, die Knoten fangen alle mit einem E an.
Die Kanten, die sie repräsentieren, gehen alle vom E los, aber nie
geht irgendeine Kante in das E rein.
Das heißt, dementsprechend kann ich hier in dem Grafen keine
Verbindung machen.
Das ist also ein Graf ohne Kanten.
Danach sollte man das Ganze halt nochmal machen, basierend auf der
Adjacenzmatrix, damit man halt auch mal Adjacenzmatrix lesen, ein
wenig übt.
Wenn man sich das also hier an der Adjacenzmatrix anschaut, eigentlich
hatten wir gesagt, wir nummerieren durch von 0 nach 1.
Jetzt können wir halt von A nach Z durchnummerieren und würden halt
dementsprechend sagen A, B, C, D.
Dann kann man erst mal den ursprünglichen Grafen aufmalen.
A von A, dementsprechend ist der relativ einfach.
Ich habe vier Knoten, A, B, C und D.
Und dann kann ich in der Zweilabgabe lesen, von A geht es halt nach C.
Von B geht es nach A.
Und von B geht es auch nach D.
Und dann von C aus geht es nirgendswohin.
Und von A aus geht es auf
alle Fälle nach C.
Entschuldigung, von D aus geht es nach A.
Und von D aus geht es nach C.
Und damit hätte ich dann entsprechend den Grafen aufgebaut.
Und wenn ich dann den Kantengrafen daraus mache, habe ich die Knoten
relativ leicht wieder gemacht.
A, B, A, C.
Wir machen es am geschicktesten, fangen wir an mit D, C.
Dann ist es am leichtesten zu machen.
Und dann kann man dementsprechend von B, D nach D, C gehen.
Man kann von B, D nach D, A gehen.
Von D, A nach A, C.
Und von B, A nach A, C.
Das heißt, man hat so ein bisschen eine lineare Struktur da drin.
Und wenn man dann sich die zweite entsprechend hernimmt, die zweite
Matrix, dann sieht das am Ende halt entsprechend so aus.
Also von da sollte man den iterierten...
Also hiervon soll man den iterierten A-Grafen zeichnen, damit man halt
da hinkommt.
Wenn man es einfach machen will, zeichnet man sich halt erstmal den
ursprünglichen Grafen hin, dann den einfach iterierten Kantengrafen
und dann den normalen Grafen.
Das heißt, hier haben wir wieder A, B, C, D als Knoten.
Wir gehen von A nach B, wir gehen von B nach C,
dann gehen wir von C nach D und von D wieder zurück nach A.
Das heißt, wenn man so lang läuft, läuft man irgendwie immer so im
Kreis.
Und wenn man sich jetzt überlegt, dass man da so ein Ding hat, wo man
immer im Kreis läuft, und man sich überlegt, dass man jetzt
einzeichnen will, von welcher Kante kann ich zu welcher anderen Kante
kommen mit einem Zwischenknoten, dann kommt dabei heraus, dass im
Prinzip die Struktur genauso erhalten wird.
Das heißt, ich habe dann hinterher A, B, A, B, C, C, D und D, A als
Knoten und die Verknüpfung bleibt genau gleich, kann wieder genau den
gleichen Zyklus laufen.
Und das kann ich jetzt iterieren, so viel ich will, dann mache ich
halt daraus A, B, B, C, hier so ein Komma dazwischen, damit ich weiß,
wo die ursprünglichen Kanten anfingen und aufhörten, dann entsprechend
B, C, C, D, C, D, D, A und D, A, A, B und habe wieder genau die
gleichen Kanten wie vorher.
Und das kann ich jetzt ad infinitum durchführen, ich bekomme halt
immer wieder so einen Graphen raus.
Dann bei Aufgabe 6.3 war ein Akzeptor gegeben, der so aussah.
Und das Erste, was man machen sollte, ist, man sollte erstmal schauen,
welche Sprache wird dadurch angegeben und man sollte das dann halt
entsprechend hinschreiben als Konkatenationsabschluss des Epsilon
freien Konkatenationsabschluss und formales Produkt von Sprachen oder
Produkt von formalen Sprachen.
Gut, wenn man sich jetzt anschaut, was der Akzeptor macht, damit ich
in den akzeptierenden Zustand reinkommen muss, ich kann erstmal ein
oder gar kein A haben, dann muss ich mindestens ein B haben.
Und dann habe ich eine Verzweigung, wo ich über zwei Pfade gehen kann.
Ich kann entweder eins oder ganz viele A's einfügen und mache dann ein
B oder ich mache halt gar kein A und mache dann ein B.
Dann darf ich hier oben noch beliebig viele weitere B's machen, muss
dann mindestens noch mal ein A machen und danach darf ich beliebig
viele A's und B's einführen, damit ich im akzeptierenden Zustand
reinkomme.
Das heißt, wenn ich das also entsprechend hinschreiben will, dann
bekomme ich daraus entsprechend eine Sprache L von A, wo ich am Anfang
erst mal keins oder beliebig viele A's machen kann.
Das ist dann der epsilonfreie Konkatenationsabschluss über der
Sprache, die halt nur das Wort A enthält.
Dann muss ich daran konkatenieren die Sprache, die nur das Wort B
enthält, damit ich den Übergang machen kann.
Dann darf ich wieder keins oder beliebig viele A's einführen.
Also so ein epsilonfreier Konkatenationsabschluss.
Dann muss mindestens ein oder mehrere B's kommen.
Das wäre dann der Konkaten... Entschuldigung, das ist nicht der
epsilon, das ist der normale Konkatenationsabschluss.
Und das hier ist dann entsprechend der epsilonfreie
Konkatenationsabschluss.
Das heißt, epsilon darf nicht enthalten sein.
Muss einmal das B entsprechend mindestens einfügen, das heißt, den
epsilonfreien Konkatenationsabschluss.
Dann muss wieder mindestens ein A kommen.
Und danach darf keins oder beliebige Wörterkombinationen aus A kommen,
das heißt, da wieder den Konkatenationsabschluss machen.
Dann war verlangt, dass man daraus, wenn man hier fünf Zustände hat,
einen Akzeptor macht, der nur vier Zustände hat.
Und wo man da jetzt in dem Akzeptor Zustände verschwendet, sieht man
relativ leicht hier an der Struktur.
Hier vorne hatten wir schon so etwas wie keins oder beliebig viele As,
also diesen Konkatenationsabschluss über dem A-Sternchen.
Den habe ich hier hinten wieder drin stehen, nur dass ich da insgesamt
nochmal einen zusätzlichen Zustand machen muss.
Dementsprechend kann ich das Ganze auch einfach vereinfachen, indem
ich sage, ich habe meinen Startzustand 0, mache halt meine As, dann
mache ich meine Bs im nächsten Zustand und da darf ich eins oder
mehrere As machen, muss dann das B machen, das mich dann in einen
zweiten Zustand bringt.
Da kann ich dann nochmal beliebig viele Bs einfügen und mache dann den
Übergang, indem ich nochmal ein A einfüge, in einen akzeptierenden
Zustand, der halt der vierte Zustand ist und der kann halt As oder Bs
machen.
Das heißt also, diese Dreiecksstruktur kann man einfach auflösen,
indem man diesen Umweg über den Knoten 2 mit den Bs, da hier beides
mal die gleichen Symbole sind, einfach durch so eine Selbstschlinge
darstellt, spart man halt einen Zustand ein.
Und dann war als letztes noch angegeben, dass man einen endlichen
Akzeptor bauen soll, der vier Zustände hat und zwei akzeptierende
Zustände und entsprechend diese formale Sprache akzeptiert.
Und da sieht man schon, das ist im Prinzip fast dieselbe wie vorhin,
mit dem einzigen Unterschied, dass ich hier an der Stelle bei dem B+,
hier war vorhin noch ein A verlangt.
Das A ist jetzt optional geworden.
Das heißt, auf diese Art und Weise, wenn man sich das anschaut, der
hier, dieses A ist optional geworden in dem Akzeptor.
Das heißt, wenn ich hier in dem Zustand 2 schon angekommen bin, dann
bin ich auch schon akzeptierend.
Das heißt, wenn ich dann einfach diesen Zustand 2 noch als
akzeptierend definiere, dann habe ich halt einen Automat mit vier
Zuständen, zwei akzeptierenden Zuständen und dadurch, dass dieses A
optional geworden ist und das hier oben halt aus der verlangten
Sprache ja auch rausgenommen wurde, habe ich damit den Akzeptor
gebaut, der entsprechend diese Sprache auch akzeptiert mit zwei
akzeptierenden Zuständen.
Und dann bei der letzten Aufgabe
ging es noch ein bisschen ums Rechnen mit regulären Ausdrücken.
Bisher noch keine Anmerkungen, das ist ungewöhnlich.
Entweder bin ich gut in Form oder Sie sind schlecht in Form.
Dann bei der letzten Aufgabe ging es darum, ein bisschen mit regulären
Ausdrücken zu arbeiten.
Man hatte also formale Sprachen, die über diesem Alphabet AB aufgebaut
waren und sollte dann halt für jede formale Sprache einen regulären
Ausdruck hinschreiben.
Die erste Sprache sollte halt alle Wörter enthalten, die nicht das
Teilwort AB enthalten.
Und da muss man sich jetzt ein bisschen überlegen, wie sehen denn
solche Wörter aus, die nicht das Teilwort AB enthalten.
Ich kann erst mal mit einem A oder einem B anfangen.
Das heißt, ich kann erst mal beliebig viele A's in Kette machen oder
beliebig viele B's in Kette.
Und jetzt muss ich aufpassen, dass ich das richtig mache.
Dann...
Achso, Wörter, die das Teilwort ABB enthalten.
Ich kann also erst mal beliebige A's und B's haben.
Ich muss dann irgendwann verlangen, dass das ABB auch wirklich
vorkommt und danach kann ich wieder machen, was ich will.
Und auf die Art und Weise bin ich also in der Lage, dafür zu sorgen,
dass halt ein Wort vorkommt, der mindestens ABB enthält.
Jetzt brauchen wir einen Ausdruck, der dafür sorgt, dass dieses ABB
eben nicht enthalten ist.
Und da muss man sich halt überlegen, was heißt das?
Das ABB soll nicht enthalten sein.
Ich kann erst mal mit B's anfangen.
Solange ich mit B's anfange, ist erst mal noch nichts Schlimmes.
Dann muss ich aufpassen.
Wenn das erste Mal ein A kommt, dann muss ich aufpassen, dass nach dem
A nicht zwei B's kommen dürfen.
Es darf ein B kommen, aber sobald das gekommen ist, muss wieder ein A
kommen.
Und das kann ich mit diesem Ausdruck machen.
Wenn ich da Wörter zusammensetze, die sind entweder beliebig viele A's
oder es kommt irgendwann mal ein A mit einem B und wenn das B gekommen
ist, dann muss was das nächste kommt, kann entweder ein 1 das A sein
oder es kann wieder ein AB sein.
Und auf die Art und Weise kann ich alle Wörter aufbauen, die halt
nicht das Wort AB enthalten.
Jetzt beim dritten Mal sollte man Wörter haben, die das Wort ABB genau
zweimal enthalten.
Das kann man im Prinzip nach dem gleichen Schema machen, wie oben
auch.
Damit ich also das machen kann, ist das erste, ich muss das Wort
anfangen lassen und ich lasse das Wort mit irgendwas anfangen, das
erstmal nicht ABB enthält.
Das ist unser R2 Ausdruck.
Und dann kommt irgendwann das Wort ABB
und dann kommt wieder irgendwas, was nicht das Wort ABB enthält.
Also wieder nicht ABB enthält.
Dann muss wieder ABB kommen.
Und danach darf nur noch was kommen, weil das jetzt das zweite Mal
ist, dass ABB vorgekommen ist, irgendwas kommen, was eben nicht ABB
ist.
Das sind also die Wörter, die genau zweimal ABB enthalten.
Und dann, bei dem vierten war jetzt gespracht, eben Wörter, die nicht
genau zweimal das Teilwort ABB enthalten, die also nicht in dieser
Sprache L3 drin sind.
Ich brauche also alle Wörter, die nicht zweimal das Wort ABB
enthalten.
Damit ich mir jetzt nicht einen Wolf schreibe, definiere ich mir oder
greife ich zurück auf diesen Ausdruck R2.
Nennen wir ihn mal RN für Enthält nicht ABB.
Gut, welche Möglichkeiten habe ich?
Ich habe die Möglichkeit, dass das Wort niemals das Wort ABB enthält.
Wäre also RN.
Oder ich habe die Möglichkeit, dass der Ausdruck genau einmal das Wort
ABB enthält.
Das wäre dann also niemals ABB, einmal ABB und dann wieder niemals
ABB.
Zweimal ABB genau darf nicht vorkommen, aber es darf dreimal ABB
vorkommen oder eben mehrmals, mehr als dreimal ABB.
Oder in anderen Worten mindestens dreimal ABB.
Also RN, ABB, dann RN, ABB, RN, ABB.
Dann habe ich schon mal einen, der hat schon mal dreimal.
Und jetzt kann entweder ein Wort kommen, das niemals ABB enthält oder
ich kann halt zwischendrin mal wieder ein ABB einstreuen, wenn ich
will.
Und auf die Art und Weise habe ich halt die Fallunterscheidung
gemacht.
Niemals ABB, genau einmal ABB.
Mindestens dreimal ABB.
Und habe damit entsprechend Sprache 4 beschrieben.
So viel zum sechsten Übungsblatt.
Kommen wir zum Bonusblatt.
Das Bonusblatt fing an mit einer Aufgabe zur Turing-Maschine.
Und jetzt kann man sich erstmal in Ruhe anschauen, was diese Turing
-Maschine überhaupt macht.
Wenn man sich anschaut, was diese Turing-Maschine macht.
Die geht erstmal durch das Eingabewort durch und solange es A´s macht,
rattert die halt da drüber, bewegt den Kopf immer nach rechts und
lässt die A´s da so stehen, wie sie halt vorher standen.
Und dann kommt es irgendwann mal an einem B.
Und was es dann macht ist, dass es das B erstmal mit einem D ersetzt.
Und das D ist ein Symbol, das vorher halt nicht in den Eingabewörtern
ist.
Das heißt also, ich markiere mir sozusagen hier das B mit einem
Sonderzeichen, das nicht in den Eingabewörtern sein kann und gehe dann
nach rechts.
Und wenn ich nach rechts gehe, ratter ich über alle möglichen
Buchstaben, die noch kommen würden, drüber.
Die A´s und B´s, die im Eingabewort sein können, aber auch irgendwie
ein Zeichen C, das also nicht im Eingabewort ist, das ich wohl selber
irgendwie draufgeschrieben habe.
Wenn ich auf ein leeres treffe, wenn ich also alles, was bisher auf
dem Banzu in Reihe draufsteht, einmal abgearbeitet habe, ganz am Ende
bin, dann schreibe ich einen C raus, gehe wieder nach links, also in
die umgekehrte Richtung und bin dann in diesem Zustand R return.
Und dieser Zustand R geht wieder nach links über alle möglichen A´s
und B´s, die da stehen können, drüber, so lange, bis ich einen D
finde.
Und wenn ich das D finde, wo ich vorher das erste B, auf das ich
gestoßen bin, durch das D ersetzt habe, dann schreibe ich es zurück in
den B und mache rechts davon weiter.
Und dann geht das Ganze wieder von vorne los.
Mit anderen Worten, für jedes B, das ich im Eingabewort finde,
schreibe ich hinten an das Eingabewort nochmal ein C dran.
Das heißt, hinten die Anzahl der C´s sagen mir, wie viele B´s waren
denn vorher überhaupt in diesem Eingabewort drin.
Und wenn man sich das jetzt anschaut, in welchen Zuständen kann T für
eine Eingabe anhalten,
ich kann einmal komplett drüber rattern, ohne dass ich jemals ein B
finde.
Und dann bin ich hier und finde plötzlich ein leeres Zeichen und da
ist dann nichts mehr für definiert, wenn ich ein leeres Zeichen lese.
Das heißt also, ich kann zum Beispiel den S0 anhalten.
Hier bin ich drin, wenn ich mindestens einmal ein B gefunden habe.
Das heißt, hier ratter ich mindestens durch, bis ich ganz rechts auf
ein leeres finde.
Und dann ratter ich wieder ganz zurück, bis ich wieder das B gefunden
habe, das ich geschrieben habe.
Das heißt, ich werde auf alle Fälle so lange machen, bis ich da bin.
Dann kann es halt...
Ich habe dann halt das B hinten rausgeschrieben und ratter wieder
zurück an die Anfangsposition und mache dann alle A´s.
Und wenn ich dann irgendwann auf ein C stoße, in diesem Zustand, dann
halte ich auch in diesem Zustand an.
Die andere Frage lautet also, kann ich jemals in diesen Zuständen C
und R überhaupt anhalten?
In C kann ich nicht anhalten, weil C wird niemals ein D lesen.
D ist nicht ein Eingabewort und das D kann nur durch dieses S0 einmal
rausgeschrieben werden und wird dann halt entsprechend wieder
zurückersetzt bei diesem Durchgehen.
Das heißt, C wird niemals ein D lesen.
Das heißt, für alles, was es jemals lesen wird, ist ein Übergang
definiert.
Und bei dem hier, dieser Return, der rettert halt zurück.
Entweder rettert er zurück, oder da komme ich ja überhaupt nur dann
hin, wenn ich mal ein B rausgeschrieben habe.
Das heißt, der geht immer zurück, bis er ein D findet und das D wird
er auch immer finden, weil nämlich garantiert ist, dass das hier ganz
am Anfang mal rausgeschrieben wurde, weil ansonsten komme ich
überhaupt gar nicht bis in den Zustand R.
Das heißt also, der einzige Zustand, in dem ich überhaupt anhalten
kann, ist dieser Zustand S0.
Das ist also B.
Und für welche Wörter hält das an?
Naja, die Wörter dürfen aus A und B sein.
Der hält für alle Wörter an.
Also für alle Wörter komme ich immer wieder in diesen Zustand S0, wo
er anhält und ich komme nicht, dass ich ihn wieder überhaupt jemals
machen kann.
Jetzt ist die Frage, was ist Time T von dieser Turing-Maschine?
Time T ist die Abschätzung für das schlimmstmögliche Wort, für das
Eingabewort, das es am längsten dauert abzuarbeiten.
Und wenn ich mir jetzt überlege, was das macht, es schreibt raus, wie
viele Bs da drin sind, hinten als Cs.
Ein Wort, das nur As enthält, da macht das nichts, der rattert das nur
einmal drüber, das ist das Beste.
Ein Wort, das nur Bs enthält, da fällt halt die meiste Arbeit an.
Da geht er halt zum ersten B, macht daraus ein D, dann geht er bis ans
Ganze, ans Ende, das sind dann N-1 Schritte, schreibt dann das C raus,
muss dann wieder die N-1 Schritte ganz zurück, bis dahin, wo er das B
durch ein D ersetzt hat, ersetzt das, geht dann zum nächsten Zeichen,
das ist wieder ein B, dann muss der wieder das, die Turing-Maschine,
das Wort abarbeiten, inklusive des Cs, das er letztes Mal
rausgeschrieben hat, also wieder N-1 Schritte, und muss wieder
zurückgehen, sind also wieder N-1 Schritte.
Und wenn das Wort N-Zeichen lang ist, und nur aus Bs besteht, mache
ich das Ganze also N-mal, das heißt, ich bin damit in Theta von N²,
bei der schlimmstmöglichen Abschätzung, die man durch dieses Time T
machen soll.
Dann, nächster Sortieralgorithmus, und da war in der Aufgabenstellung
eine Unschönheit drin, der Kollege hatte das noch, dann leider sehr
spät, rumgeschrieben, wir hatten es dann im Forum gesehen, und der
Kollege hat es rumgeschrieben.
Was ist die Idee von diesem Sortieralgorithmus?
Dieser Sortieralgorithmus ist ein schönes Beispiel dafür, wie man
Rechenzeit durch Speicher eintauschen kann.
Also wie ich Rechenzeit sparen kann, indem ich Speicher haben will.
Meine, der Traum ist immer, dass man einen Sortieralgorithmus hat, der
in linearer Zeit arbeitet.
Also diese Sortieralgorithmen, die man hat, die sind alle irgendwie O
von N, mal irgendeinen Faktor, der von N abhängt.
Also sowas wie O von log N.
Und man hätte natürlich gerne diesen log N Faktor weg, man hätte gerne
einen linearen Sortieralgorithmus.
Und das kann man auf diese Art und Weise machen, wenn man halt mit dem
Speicher rumäßt, bis zum geht nicht mehr.
Das hier ist schon so ein bisschen eine optimierte Variante.
Die Grundidee ist einfach, also angenommen, ich sortiere natürliche
Zahlen.
Wenn ich jetzt natürliche Zahlen notiere, sortiere jede natürliche
Zahl, kann ich auch als Index eines Arrays nehmen.
Also ist die Idee, dass ich mir einen Array hernehme, und dann gehe
ich über die zu sortierende Liste hin.
Und in meinem Hilfsarray erhöhe ich jedes Mal den Index des Arrays um
1 von der Zahl, die ich gerade sehe.
Also wenn ich eine 2 sehe, dann erhöhe ich das Zählarray von 2 um 1.
Dann steht hinterher in diesem Zählarray drin, für jede mögliche Zahl,
wie häufig kommt die in der Liste vor.
Und dann brauche ich einmal nur, über dieses Zählarray drüber zu
gehen.
Und kann dann sozusagen die sortierte Liste aufbauen.
Das hat natürlich die Unschönheit, wie groß kann dieses Zählarray
sein.
Das kann ja theoretisch unendlich lang sein.
In der Praxis ist es beschränkt, weil die Anzahl der Zahlen, die wir
im Rechner darstellen können, erstmal auch häufig beschränkt ist, wenn
ich nicht irgendwie ganz besondere Sachen mache.
Aber wenn ich mich sozusagen weiß, was ist das kleinstmöglichste
Element und was ist das größtmögliche Element, dann kann ich das auf
die Art und Weise machen.
Und muss dann als Laufzeit habe ich O von maximale Anzahl am Maximum
der Zahlen, die ich überhaupt darstellen kann.
Das wäre also sogar fast, in einer gewissen Art und Weise, fast eine
konstante Art.
Aber dadurch, dass ich halt die Liste aufbauen muss und die Liste
hinterher wieder genauso viele Elemente enthält, wie ich in meiner
ursprünglichen Liste habe, bin ich dann also O von Länge N.
Damit man jetzt nicht zu viel Speicher verbraucht, kann man halt
vorher einmal über die Liste drüber gehen und gucken, was ist das
Maximum der Liste und was ist das Minimum der Liste und kann dann ein
Array anlegen, das halt max-min lang ist oder, und das war eigentlich
ursprünglich gemeint, weil das halt hier hinterher entsprechend
adressiert, ich hätte gerne ein Array, das von Min bis Max geht.
Das ich also adressieren kann über die Indizes Min und dann immer um 1
erhöht bis zum Index Max.
Und dann gehe ich halt über meine zu sortierende Liste drin, erhöhe
halt die Zähler in diesem Array jeweils und danach gehe ich am Ende
noch einmal über dieses Array drüber und füge so viele Indexzahlen in
die finale Liste rein, wie hier halt in dem Array an der Stelle drin
steht.
Das heißt, wenn man jetzt eine untere Schranke und die obere Schranke
angeben muss, dann muss man sich erstmal überlegen, was heißt es, das
Minimum und das Maximum von einem Element zu finden.
Man muss halt einmal über die gesamte Liste drüber gehen und kann dann
in Zeit O von N, wenn N die Länge der Liste ist, das Minimum
bestimmen.
Man kann in Zeit von O von Länge N das Maximum der Liste bestimmen.
Das heißt also, das Ganze läuft in O von N oder auch sogar in Theta
von N und damit auch in Omega von N.
Jetzt dieser Bucket Sort Algorithmus, untere, mittlere, obere
Schranke, ist halt so viele Elemente, wie ich drin habe, muss ich
immer anfassen, weil ich ja hinterher die finale Liste aufbauen muss
und auch, wenn ich einmal über die Liste drüber gehen muss, um das
Zähl -Array aufzubauen.
Das heißt, bin ich auch in O von zweimal von N, Omega zweimal von N,
also in Theta von A2N und damit entsprechend in Theta von N.
Jetzt ist die Frage, wann ist dieser Algorithmus schneller als der
Bucket Sort Algorithmus?
Gut, das ist dann halt der Fall.
Das ist davon abhängig, wie weit denn Max und Min auseinander liegen.
Das Problem ist, wenn Max und Min sehr weit auseinander liegen, also
angenommen, ich habe eine Liste mit 10 Elementen, das Minimum ist 0
und das Maximum ist 100.000, dann ist das nicht schneller, als wenn
ich die Liste selber sortiere, mit, sagen wir mal Merge Sort oder dem
Insertion Sort sortiere, weil ich hinterher das Problem habe mit der
Anzahl der Schritte.
Ich muss hinterher über ein Array durchgehen, das von 0 bis 100.000
gilt.
Das heißt, um 10 Elemente zu sortieren, muss ich durch dieses Cell
Array 100.000 Schritte durchgehen.
Und die meiste Zeit wird immer sein, okay, das Ding ist 0, nicht
anfügen.
Und für maximal 10 Elemente werde ich überhaupt eine Anfügeoperation
machen.
Eventuell weniger, wenn Elemente doppelt vorkommen.
Das heißt, wenn das der Fall ist, dann ist das nicht schneller.
Damit das also schneller sein muss, sein kann, muss also diese Länge
dieses Cell Arrays entsprechend kleiner sein, als dieses Log N mal N
Abschätzung, die man sonst braucht bei Insertion Sort oder Merge Sort.
Wenn das also der Fall ist, dann kann ich, bin ich echt schneller.
Das Schlimme ist, im O-Kalkül fällt das halt weg.
Im O-Kalkül merkt man diesen Unterschied nicht.
Im O-Kalkül ist das Ding immer noch in O von N.
Wenn man aber sich die tatsächliche Laufzeit anschaut, halt nicht.
Und diese schnelle Laufzeit im O-Kalkül kauft man sich halt durch
hohen Speicherverbrauch.
Also wenn ich halt Personalausweisnummern sortieren möchte, dann habe
ich da sehr große Max und sehr kleine Mins.
Das heißt, ich habe ein sehr riesengroßes Zähl-Array und muss dann
halt entsprechend viel Speicher investieren.
Plus, ich habe das Problem, dass ich ja dieses Zähl-Array indizieren
muss über die Zahlen, die ich sortieren will.
Das heißt, wenn ich zum Beispiel reelle Zahlen sortieren will, ich
kann kein Array bauen, der als Index eine reelle Zahl hat.
Das gibt mir im Augenblick keine Programmiersprache der Welt her.
Wenn ich das machen wollte, bräuchte ich irgendeine komplizierte
Funktion, die natürliche Zahlen auf Array-Indizes abbildet.
Und das braucht dann selber wieder sehr viel Laufzeit.
Das heißt, eigentlich geeignet ist das nur, wenn ich sowas wie
natürliche Zahlen indiziere oder wenn ich, keine Ahnung, ich habe
irgendwie eine ganz spezielle Architektur, wenn ich da mit den Zahlen,
die ich sortieren möchte, auch gleichzeitig Elemente in einem Array
effizient indizieren kann.
Und jetzt gibt es verschiedene Varianten.
Diese Variante des Algorithmus ist eine, die kann zum Beispiel nicht
mehrfach vorkommende Elemente machen, weil die hier nur true und false
hinschreibt.
Die andere Variante wäre, dass ich an der Stelle zähle, wie häufig
kommen mehrfachkommende Elemente vor.
Und dieser kann das an der Stelle halt nicht.
Die kann nicht auf Listen arbeiten, wo ein Element mehrmals vorkommt.
Dann hatten wir eine Aufgabe.
Da ging es darum, ein bisschen Regex-Bäume zu zeichnen.
Wenn ich also so einen regulären Ausdruck habe, wie hier.
Dann habe ich halt hier oben als erstes diese Konkatenations-
Funktion.
Hier im linken Zweig habe ich halt den A oder dann kommt ein Sternchen
und ein Sternchen.
Ich habe hier entsprechend das B und das A.
Dann kommt hier etwas Blödes, weil hier habe ich jetzt so eine ganze
Reihe von Konkatenationen, wo ich halt immer ein A habe, eine
Konkatenation, dann habe ich wieder ein A, eine Konkatenation und
insgesamt sind das sechs As, die ich auf die Art und Weise
zusammenbaue.
Und dann kommt hier nochmal eine Konkatenation dran.
Entschuldigung.
Dann kommt hier das Rechte, was dann konkateniert wird, das wird mit
einem Oder getrennt.
Hat dann links eine Konkatenation und rechts hat es halt ein Sternchen
mit einem B und bei der Konkatenation hat man halt links ein
Sternchen, rechts ein Sternchen, das C und das D.
Und wenn man jetzt anschaut, hier oben, da kann man ein bisschen was
einsparen.
Wenn man diese Konkatenation halt nicht linear macht, sondern wenn man
die halt entsprechend ein bisschen aufspaltet, schauen wir uns deshalb
einfach nur mal den Baum an für A-A konkateniert mit A-A-A.
Im Prinzip der gleiche Ausdruck wie da oben, dieses 6 As, aber halt
zwischendrin nochmal aufgeteilt.
Dann kriegt man halt einen Baum raus, der halt so aussieht.
Der ist also, wenn ich das vergleiche mit dem oberen Baum, der hat
halt 1, 2, 3, 4, 5, 6 und der hier hat halt 1, 2, 3, 4 Höhe, das heißt
habt ihr 2 Höheneinheiten eingespart und kann also, wenn ich hier in
dem regulären Ausdruck da oben einfach nochmal Klammer einfüge, dass
ich das halt hier entsprechend klammere, da diesen Teilbaum um 2
Höheneinheiten kleiner machen und kriege ich dann halt einen
Regexbaum, der halt ein bisschen kleiner ist.
Und dann die letzte Aufgabe war viel Geschwafel und dann musste man
ein bisschen knobeln.
Hatte eigentlich nichts mit Grundbegriffe der Informatik mehr zu tun.
Da war halt ein Tutor, fand das vielleicht ganz nett, so eine
Knobelaufgabe mit aufs Platz zu nehmen, also haben wir eine
Knobelaufnahme mit aufs Platz genommen.
Wer aufmerksam liest, weiß auch bei welchem Tutor er sich bedanken
darf.
Also, der fürchterliche Dr. Meta ist wieder da.
Und ich habe mir sagen lassen, ich bin ja leider ein altes Gewächs,
das lange Zeit keine Grundvorlesungen mehr gemacht hat.
Es gibt wohl auf den Übungsblättern da gewisse Unterschiede.
Und der Unterschied ist, dass wir in Grundbegriffe der Informatik auf
der guten Seite der Menschheit stehen.
Sie sind noch jung und naiv und glauben noch an das Gute im Menschen.
Wir sind gegen Dr. Meta.
Der ist böse.
Hinterher, wenn Sie dann Algorithmusübungsblätter lösen müssen, dann
werden Sie schon so verzweifelt genug sein, dass Sie mit Freude Dr.
Meta bei seinen Schandtaten unterstützen werden.
Wahrscheinlich ist deshalb Dr. Meta auch so erfolgreich, weil hier
noch die Erstsemester was gegen ihn machen müssen und hinterher die
höheren Semester dann schon dem ganzen überlegen sind.
Also, aber die Idee ist im Prinzip, was da mit vielen Worten
beschrieben wurde, ist ein Rätsel, das findet man eigentlich ein
Logikrätsel, das findet man relativ häufig.
Und die Idee ist, wenn man das lösen will, dass man einen
Zählstudenten bestimmt.
Also die Studierenden, die sich da gefangen sind, die sprechen sich ab
und bestimmen einen Studenten als den Zählstudenten.
Und was dann passiert ist, ohne Beschränkung der Allgemeinheit, sei
die Kiste am Anfang zum Beispiel geschlossen.
Wenn der Student reinkommt in den Raum und er sieht, dass die Kiste
geschlossen ist, dann macht er nichts.
Wenn der Zählstudent reinkommt und er sieht, dass die Kiste offen ist,
dann schließt er die Kiste.
Und wenn jetzt irgendein anderer Student reinkommt, dann weiß er, ob
er das erste Mal oder das zweite Mal in den Raum kommt oder das ente
Mal in den Raum kommt.
Wenn er das erste Mal in den Raum kommt, macht er was mit der Kiste
und wenn er wiederholt reinkommt, macht er eventuell nichts mit der
Kiste.
Wenn er also reinkommt in den Raum und die Kiste ist geschlossen, dann
öffnet er die Kiste.
Aber auch nur dann, wenn er zum allerersten Mal eine geschlossene
Kiste vorfindet.
Das heißt, auf die Art und Weise kann er sozusagen angeben, okay, ich
bin das erste Mal in diesem Raum gewesen und habe eine geschlossene
Kiste vorgefunden, ich öffne sie jetzt.
Und der Zählstudent weiß dann halt, wenn er eine offene Kiste sieht,
dass irgendeiner in den Raum zum ersten Mal reingekommen ist und eine
geschlossene Kiste vorgefunden hat.
Und schließt das wieder.
Und wenn der Student dann halt die Kiste insgesamt zwölf Mal
geschlossen hat, dann weiß er, dass alle seine anderen Kommilitonen
schon mindestens einmal in dem Raum drin waren und er war logischer
selber auch mindestens einmal in dem Raum drin.
Und dann weiß er, dass ganz sicher mindestens alle einmal in dem Raum
drin gewesen sind.
Das kann natürlich relativ lange dauern, weil der Einzige, der die
Kiste aufmachen darf, ist der Zählstudent.
Zusatzfrage.
Terminiert dieser Algorithmus?
Also sowas kann man sicherlich leicht in eine Turing-Maschine
reinschließen.
Terminiert die Turing-Maschine?
Genau.
Das ist ein stochastischer Algorithmus.
Das ist ein Zufalls-Algorithmus.
Das ist ein Las Vegas-Algorithmus.
Bei Zufall kann alles passieren.
Kann passieren, dass zum Beispiel nur der Zählstudent jedes Mal wieder
reingeschickt wird.
Das ist zwar sehr unwahrscheinlich, aber nicht unmöglich.
Das heißt, es kann durchaus sein, dass der Zählstudent immer
reingeschoben wird und dann kommt er raus und dann wird ein neuer
Student ausgewählt und dann ist wieder der Zählstudent und so geht das
halt ad infinitum weiter.
Das heißt also, es ist nicht garantiert, dass der Algorithmus
terminiert.
Das ist aber auch in Ordnung, weil der Algorithmus soll ja nur dann
terminieren, wenn halt mindestens alle einmal drin gewesen sind.
Aber ist halt nicht garantiert, dass wirklich am Ende alle einmal drin
gewesen sein werden.
Gut.
Damit sind wir am Ende der Übung.
Fragen noch?
Alle sind erschöpft.
Dann machen wir Schluss für heute.