Video 6-3: Mathematische Analyse von Algorithmen

0:03 Jetzt habe ich einiges über Laufzeiten gesagt, ein bisschen kürzer als das noch mal zur mathematischen Analyse von Algorithmen. Das sind die zwei Dinge, die für unser Algorithm Science, für diese Methode äh Methodik Hand in Hand gehen. Auf der einen Seite versuchen wir eine Hypothese aufzustellen aus der Überlegung, wie lange ein Algorithmus brauchen sollte nach so einem abstrakten Modell und dann validieren wir das mit Experimenten, wo wir die Laufzeit stoppen und die die Zeiten plotten und all diese Dinge, die sie eben gesehen haben. Ähm in dem nächsten Abschnitt möchte ich noch ein bisschen das Handwerkszeug nachliefern, wie man in den meisten Fällen so eine Analyse machen kann. Wir hatten ein Beispiel gesehen für das Freeum äh und noch äh ein paar Fake Beispiele für Rekursion. Da hatten wir nicht wirklich die Algorithmen analysiert, sonder die Rekursion gelöst. Also jetzt noch mal ein bisschen, wie komme ich von äh von Code dann zu Laufzeiten? Äh diese Idee könnte man sagen, geht auf Donald Koth zurück, so der der Großvater der theoretischen Informatik, der insbesondere für diese Bücher bekannt ist. Wer wer kennt die Art of Computer Programming? Ist das ein Begriff für jemand?

1:18 Äh, das sind sehr umfassende Bücher, die auf in sehr bestimmtem Stil, ich hatte schon mal erwähnt, dass sie diese ähm Assembly Code Beschreibung von Algorithmen verwenden, glaube ich. Ähm, na ja, der ist der ist der Pionier, der ähm sozusagen sagte, wir können präzise mathematisch analysieren, wie lange ein Algorithmus brauchen sollte. Alles was wir dafür tun müssen ist bestimmen, wie lange dauern die elementaren Schritte, aus denen ein Algorithmus zusammengesetzt ist. Hier sind so ein paar Beispiele und fairerweise eigentlich nur Schätzungen, wie lange die üblicherweise brauchen. Äh, da ist dann in der Praxis tatsächlich äh die Geschichte ein bisschen komplizierter, aber wir wir nehmen mal diese Durchschnittswerte, die z.B. Wir sagen, dass das Adieren von zwei Gleitkommazahlen doppelt so teuer ist wie das Addieren von zwei ganzen Zahlen. Um und bei das hinkommen. Äh insbesondere die Vision ist auch in Hardware so ein Stück weit iterativer Schritt, ist dadurch doch ein Stück langsamer als ähm andere Operationen.

2:22 und solche zu äh trigonometrischen Funktionen, das sind in der Regel ja keine Hardware primitiven Operationen, sondern kleine Algorithmen, die eben numerische Approximation dafür berechnen, irgendwelche Taylorreihenentwicklung und so solche Dinge, äh die brauchen dann eben schon eine Größenordnung mehr. Das ist ein Zutat 1. Zutat 2 ist für ein Programm ähm noch hier mal ein bisschen noch abstrahiert. Das sind noch weitere ähm primitiven Operationen. Die meisten, die man in Java so hat, brauchen konstante Zeit. Also, da gibt's keine Abhängigkeit von irgendeiner Eingabegröße.

3:04 Ausnahmen sind diese ähm Dinge wie neue Arrays anlegen. Das ist ein kleines Schnipselchen Java Code. Was sich aber in Java dahinter versteckt, ist, dass die Arrays initialisiert werden mit null im Fall von int und das kostet eben Zeit proportional zur Länge von dem Array. Insbesondere, wenn Sie so mehr dimensionale Arrays anlegen, ist das natürlich relativ teuer, wenn n groß ist. Das muss man einfach wissen, dass diese Operationen nicht konstante Zeit haben in aller Regel, während für die anderen für die anderen Operationen ist es irgendeine Konstante, der wir hier mal einen Namen geben. Dahinter steckt natürlich eigentlich eine echte Zahl, aber die Zahl hängt ja von der Maschine ab. Also könnte man sagen, es ist eine Konstante, die man dann bestimmt, je nach Hardware, wo man das wirklich laufen lässt. Zutat 1. Ja, wie lange dauert eine ein elementarer Schritt in meinem Algorithmus? Äh, die Zutat 2 ist dann, wie oft führe ich jeden diese Befehle aus? Wie viele habe ich davon?

4:04 Um das nicht ausarten zu lassen, wir werden gleich sehen, das ist aufwendig und will man im Allgemeinen nicht in dem Detail gerade machen, aber ich habe das hier mal äh knurische Analyse genannt, wenn man das die volle Zoomstufe reinhaben möchte. Machen wir nur auf dem Spielbeispiel one sprich, ich habe eine Liste von Zahlen und ich möchte alle ein Tuppel, also alle einzelnen Zahlen finden, die sich zu null summieren, also alle Nullen zählen. Das ist was dieser Code hier macht. Der läuft einmal durch das Array und zählt, wie oft habe ich null gesehen? Also algorithmisch uninteressant, aber wir wollen analysieren, wie lange der braucht und zwar möglichst präzise. Äh was man hier im eigentlich machen möchte, ist jetzt zerlegen diesen Code in einen Kontrollflussgraf. Äh wann wird welcher Befehl wie oft ausgeführt? Wir machen das mal nur so grob anhand der Zeilen im Code. Also, wenn ich einmal so einen Aufruf mache für One Sum mit einem Array der Größe N und ich schreib das hier mal in unserer Pseudo Code Notation. So, in Wirklichkeit würde ich in in Java natürlich nur dieses Array Objekt A übergeben und das enthält dann seine Länge als D length, wie hier auch gezeigt.

5:25 Äh, so einen Aufruf würde die verschiedenen Zeilen unterschiedlich oft ausführen. Diese Zeile 2, die führe ich genau einmal aus, denn da gehe ich einmal rein und dann springe ich raus und dann bin ich fertig. Ich springe nie mehr zurück. Ähm, ähnlich ist es hier für die letzte Zeile. Die führe ich auch genau einmal aus. Dann ist ja auch der Methodenaufruf fertig. Ein bisschen spannender ist jetzt der Teil in der Schleife. Äh insbesondere hier diese Zeile mit der Vorschleife äh möchte ich mal insbesondere hier diese diesen Vergleich zählen. Äh ich habe natürlich einen Teil hier, das I = 1, das gehört eigentlich noch so ein bisschen in die Zeile davor. Ja, dieses führen wir ja nur einmal aus am Anfang. Dann habe ich diese zwei Teile, die ich wiederholt in der Schleife ausführe. Wie oft wird dieses I kleiner N verglichen? Wie oft wird dieser Vergleich gemacht? Na ja, so oft wie ich die Schleife ausführe plus einmal, denn einmal mache ich am Ende den Vergleich, der dann schief geht und aus der Schleife rausspringt.

6:32 Ich fange mit null an. Ich höre bei n auf. Das heißt, n mal wird die Schleife durchlaufen. Kann wir hier schon gleich dran schreiben für die nächste Zeile. Aber dieser Teil hier oben, der wird n + 1 mal ausgeführt, weil eben dieser eine Aufruf für den Vergleich noch kommt, der dann die Schleife verlässt.

6:50 Endausführung vom Schleifenrumpf. Weniger klar ist, wie oft dieses äh Inkrement hier ausgeführt wird, denn das hängt von den Daten ab. Und dann mal sind wir hier jetzt mal ähm äh an der Stelle schwammig oder faul. Wir sagen einfach nur, das ist irgendwas zwischen 0 und n mal.

7:12 Und wenn ich es genauer wissen will, dann muss ich mir die Daten angucken. Ich könnte z.B. sagen, im worst case wird's immer die größte Zahl sein.

7:25 Das heißt, da nehmen wir einfach das N auch an der Stelle. Okay. Äh in sauber aufgeschrieben ist, dass hier diese Tabelle, die also angibt, wie oft jede Zeile ausgeführt wird. sind aber die gleichen Zahlen wie eben.

7:37 Was wir eigentlich wollen, ist aber nicht die Zeilen, sondern die Elementaroperationen, die diesen Algorithmus ausmachen. Und das sind hier im Wesentlichen diese. Ich habe variablen Deklaration, ich habe Zuweisung, ich habe Vergleiche verschiedene Art Array Zugriffe und ich habe dieses Inkrement von den von dieser Countvariable und dann kann ich zählen, wie oft kommen die im Code vor mal äh welche Frequenz hat dieses Vorkommen? Also hier steht deshalb eine drei, weil Variablendeklaration passieren hier und hier und hier. Jede von diesen Stellen im Code wird genau einmal ausgeführt. Deswegen habe ich am Ende drei Variablend Deklarationen über die ganze Ausführung dieser Methode. Machen wir noch ein anderes Beispiel hier. Ähm diese echt kleiner Vergleiche, die habe ich natürlich nur hier. Und da hat man uns gerade überlegt, dass es diese Zeile, die n + 1 mal ausgeführt wird. Das heißt, ich habe insgesamt n + 1 echt kleiner Vergleiche.

8:38 Dann kann ich am Ende diese Frequenz mit den Kosten multiplizieren und alles aufsummieren. Wenn ich das mache, dann kriege ich so eine Formel für die Gesamtkosten in Abhängigkeit von meiner Eingabegröße und in Abhängigkeit von diesen konstanten Kosten für die ganzen Elementaroperationen, die ich dann einzeln stoppen könnte auf meiner Maschine, die mich interessiert. Das könnte man jetzt immer so machen. Ähm, da werden wir aber dann doch manchmal nicht die Geduld für aufbringen. Das ist sehr zäh und mühsam und manchmal äh zählt man dann ganz präzise irgendwelche Teile, die gar nicht für die Laufzeit sehr relevant sind. Also, das ist grundsätzlich möglich. Das ist der Punkt, um dem es mir hier geht. Grundsätzlich kann ich das versuchen. Wir werden das aber in aller Regel nicht machen, sondern wir machen uns das Leben ein bisschen leichter. Ja.

9:40 Genau, da habe ich mich noch korrigiert, weil ähm fairerweise auch die äh Originalvorlage das falsch hatte. Hier diese Vorschleife, das ist eine Variablendeklaration, ganz klar. Und die habe ich noch mitgezählt. Genau. Hier stand mal eine zwei, weil ähm ich wei schild von mir in dem Fall, aber es sind eben diese drei Variablen. Also dieses präzise Zählen auch ist es jetzt zwei oder drei Variablen, dieser konstante Overhead, den wir einmal haben, wenn wir danach 10 000 mal die Schleife ausführen, ist jetzt echt nicht der Punkt. Ja, das ist das ist schön zu wissen, dass wir das grundsätzlich tun könnten, aber das ist weder relevant noch praktikabel.

10:21 Deswegen ist die Lösung ein abstraktes Kostenmaß zu suchen. Hatten wir letztes Mal auch schon drüber gesprochen. Und hier z.B. bietet sich an, die Array Zugriffe zu zählen. Das ist um und bei die innerste Schleife. Das wird so oft auf ausgeführt wie die am häufigsten ausgeführte Codeelle insgesamt. Das heißt, da werden die Gesamtkosten proportional sein zu dieser Anzahl äh Array Zugriffe. Und das ist was wir am Ende brauchen.

10:57 Also in Kurzform könnte man sagen, in diesem abstrakten Kostenmaß haben wir statt diesem chaotischen Ding hier einfach diese sehr viel kürzere Angabe, dass die Kosten von One Suome Till the N Array Zugriffe sind. Das ist kurz und prägnant und für die Vorhersage der Laufzeit im Wesentlichen genauso gut.

11:25 äh auch noch ein bisschen historisches Zitat. Allen Turing ist bestimmt ein Begriff äh Pionier der Informatik in verschiedensten Bereichen. Ähm und im Wesentlichen nimmt er auch diese Beobachtung vorweg, dass wenn man so eine präzise Analyse machen will, wie lange was dauert, äh um gute Algorithmen zu finden, möchte man sich auf was zurückziehen. Er sagt hier für sein Anwendung ist jetzt nicht so wichtig, wo der was der Kontext ist. Wir wählen ein bestimmtes äh abstraktes Kostenmaß, Anzahl Multiplikation und Recordings ist, glaube ich, ein Schreibzugriff auf ein Array, wenn man es äh in heutige Sprache übersetzt. Und das ist das, was wir zählen, um zu bestimmen, welchen Algorithmus wir verwenden wollen. Also auch eine klassische alte Idee, dass man diese ganz präzise Analyse ersetzt durch etwas äh das ein abstraktes Kostenmaß als Basis hat. So, dann noch eine eine wichtige Folie, die Ihnen ein bisschen Handwerkszeug geben soll. Im Allgemeinen ist diese Frage, wie oft wird eine bestimmte Codezeile ausgeführt? Unlösbar schwierig. Man kann Programme schreiben, in denen man beweisen kann, dass kein Programm das automatisch kann. Man kann Programme schreiben, wo die Lösung im Wesentlichen eine offene mathematische Frage ist, für die noch niemand eine Antwort hat. Also werden wir da auch im Allgemeinen keine zufriedenstellende Lösung von Ihnen erwarten können. Aber es gibt ganz viele eingeschränktere Fälle, wo es systematisch und methodisch geht, äh rein mechanisch. Und da möchte ich Ihnen ein paar Regeln zu zeigen.

13:02 Äh, der erste einfachste Punkt, wann ich einzelne Zuweisungen und an Anweisungstatements habe dieser Form und viele andere, zählen wir die im Wesentlichen als Konstantzeit 1, zum abstrakten Kostenmaß gehören, manchmal ignorieren wir sie auch komplett. Das ist relativ langweilig. Häufigster anderer Punkt, den wir schon benutzt haben, ist eine Vorschleife. Wenn die so dem üblichen äh Muster einer Zellschleife folgt, kann ich die immer übersetzen in eine Summe. Dann kommt's drauf an, wie lange diese Schleifen rum braucht. Also hier ist weiterer Code, der irgendwie auch davon abhängt, was das J gerade für einen Wert hat. Aber angenommen, wir haben schon die Laufzeit für diesen Schleifenrumpf bestimmt. Dann bekomme ich die Schleife für die die Laufzeit, Entschuldigung, für die Schleife als Summe über diese innere Zeit. Hatten wir schon verwendet für Freeam. Hatten wir damals nur nicht ganz so äh methodisch äh hingeschrieben.

14:02 Wenn ich so Dinge habe, was gibt's noch im Programm? If Statements sind im im Grunde harmlos, wenn wir nur eine obere Schranke wollen, dann nehme ich einfach den schlimmeren der beiden Fälle. äh einfache Worst Case Idee. Was gibt's sonst neuen Programmen? Es gibt noch Schleifen und Rekursion und da ähm ist es ein bisschen schwieriger, eine allgemeingültige Sache anzugeben. Ich habe hier ein Beispiel für eine Schleife mal aufgeschrieben, die ähm nicht ganz unüblich ist. Wir haben eine Schleife mit einer Abbruchbedingung über eine Zellvariable N. Dann gibt's einen gewissen Code vorher, dann wird n halbiert und dann mache ich noch irgendwas und ich möchte wissen, wie lange dauert das insgesamt? Genauso funktioniert's auch für rekursive Funktionen. Sie wissen vielleicht, man kann das eine andere überführen. Ganz allgemein sind sind Schleifen und Rekur Rekursion im Wesentlichen gleichausdrucksstark.

14:57 Äh hier ist quasi der gleiche Code noch mal ausgeschrieben als als Rekursion. Ich habe irgendeine Abbruchbedingung, was ich dann äh mache, wenn diese Schleife beendet ist. Ansonsten fange ich an, führe diesen Teil Aus, dann mache ich meinen rekursiven Aufruf in diesem Fall mit meinem N und dann das B halbe. Das ist für die Laufzeit äquivalent, nicht für den exakten Code in diesem Fall. Aber wie analysiere ich, wie analysiere ich sowas? Im allgemeinen schwierig, denn ich muss irgendwie zählen, wie oft ich diese Schleife oder die Rekursion ausführe. Aber unter der Annahme hier, dass A und B den Wert von n nicht verändern, kann ich hier eine Rekursionsgleich aufstellen, die für beide Fälle gilt. Ich habe eine Abbruchbedingung. Wenn mein N klein ist, dann äh passiert nichts. Sagen wir kosten 1. Wenn man n größer ist, dann zähle ich in der Rekursion die Kosten zusammen. Ich habe die Kosten für A und für B für diese jeweiligen Aufrufe hier mit dem passenden Wert von N. Und ich habe einen rekursiven Aufruf bzw. die nächste Schleifeniteration, da verwende ich die gleiche Funktion eben mit dem angepassten N.

16:11 Und dann können Sie hoffen, dass die Rekursion, die dabei rauskommt, eine ist, die wir direkt mit dem Master Theorien lösen können. Dann sind wir, dann haben wir es geschafft. Im Allgemeinen gibt's dafür keine Garantie, aber wenn wir wenn wir sie ähm nach einer Analyse von Algorithmen fragen, dann wird sich schon auf Bereiche beschränken, wo das dann auch machbar ist.

16:36 Um und bei sind das die Fälle, denen man so begegnet. Ähm, man kann natürlich immer versuchen noch allgemeiner äh Analysen zu machen, aber dann muss man schon irgendwie Adok Argumente erfinden. Sehr viel mehr schematische Regeln als diese gibt es eigentlich nicht.

16:59 Hier sind noch ein paar Beispiele ähm ähm die das noch mal ausführen. Äh hier ist so ein Zwischending to sum. Also, ich suche Paare von Zahlen, die sich zu null summieren. Auch wieder als diese äh Brotforce Algorithmus aufgeschrieben. Wenn mein Kostenmaß Array Zugriffe ist, dann habe ich genau an diesen beiden Stellen ein Array Zugriff und ich frage mich jetzt, wie oft der passiert. Da würden Sie jetzt die äh Schachtel, die geschachtelten Schleifen nach dieser Regel umformulieren. Wir haben den inneren Aufruf, also hier das hier. Das hat Kosten 2. Dieses if, das hat bequemerweise Kosten null, denn wir haben uns jetzt drauf geeinigt, wir zählen nur Array Zugriffe. Das heißt, diese ganze Schleife hat immer Kosten 2. Das ist also jetzt mein mein TB. Und äh dankenswerterweise hängt dieses hier auch weder von I noch von J ab. als könnte sagen, das hier ist mein TB und das hängt zwar von I und J nominell ab, ist aber immer zwei. Das heißt, das macht den mit den Parametern nichts.

18:08 Dann gehen wir alle Ebene nach draußen. Jetzt habe ich hier so eine Vorschleife, die von i + 1 bis n läuft. Das heißt, sie haben j von i + 1 bis n - 1 der letzte Wert. Und da rufen wir TB von I und J auf, aber das ist ja einfach zwei, das hier innen. Hei, äh wir können dann den Wert ausrechnen. Ähm, im Interesse der Zeit kürze ich das mal ab und wir machen uns ähm wir machen den Spaß mit dem Summen ausrechnen jetzt nicht noch mal. Für die ganze äußere Schleife habe ich jetzt den grünen Teil als das TB, sagen wir mal, das hier heißt dann TC.

18:55 Und dann habe ich hier noch mal so eine Schleife. Das heißt, meine Gesamtlaufzeit ist i von 0 bis n - 1 von TC von I. Und wenn man jetzt das grüne hier ausgerechnet hätte, könnte man das hier einsetzen und käme am Ende auf die Lösung. Wir haben ja schon ein komplizierteres Beispiel gemacht. Nach genau den gleichen Regeln kommt man auch hier zur Lösung. ähm würde ich im Interesse der Zeit jetzt abkürzen.

19:22 Man kann aber auch diese Rechnung ähm dann schon zwischendrin vereinfachen zu einer Tilde Approximation. Also durch diesen Einsatz von einem bequemen Kostenmaß und der asymptotischen Approximation wird die Rechnung auch einfach deutlich angenehmer.

19:50 Ja, es gibt noch eine Folie für. Das hatten wir aber schon gemacht. Das ist äh können Sie zurückblättern. Da hatten wir die Rechnung ausführlich gemacht. Wenn wir uns hier auch drauf einigen, wir zählen die Anzahl Array Zugriffe, dann hat man am Ende als Kosten einb n hoch 3. Wir hatten das n sechel für die Anzahl Ausführung von dem inneren rum.

20:19 Gut, dann belassen wir es dabei. Äh, wir sehen uns am Montag wieder und schauen uns da dann noch ein paar Algorithmen an. Ähm, mindestens haben Sie jetzt ein bisschen strukturierter diese Analyse gemacht. Das werden wir definitiv auch noch ein bisschen einüben.