Video 3-1: 3SUM

0:01 Um den Kontext ein bisschen konkreter zu machen, fangen wir aber mit einem Beispiel an. Bevor wir also in die in die reine Mathematik dann abrutschen für einen Moment oder die Analysis abrutschen, schauen wir uns ein konkretes algorithmisches Problem an. Das mag auf den ersten Blick etwas künstlich oder aus der äh aus dem Kontext gerissen wirken. Äh werden aber noch mal drauf zurückkommen. Paar Anwendungen sind auch erwähnt, ähm auf die ich aber jetzt noch nicht genauer eingehen möchte. Das Problem heißt presum. Ähm, ein reines Zahlenproblem. Wir äh starten mit einer Eingabe von n ganzen Zahlen. Äh wichtig an der Stelle, die können positiv und negativ sein. Und wir suchen im Prinzip Trippel aus Zahlen, die sich zu null summieren. Äh, dafür brauche ich natürlich irgendwie negative Zahlen, damit das so richtig spannend wird. Und konkret ist die Frage hier, wie viele von diesen Trippeln gibt es? die sich zu null summieren. Okay, also formal aufgeschrieben ähm ist diese Anzahl C so definiert, ich habe eine Menge von Trippeln, nämlich von Indizs i JK, die geordnet sind, kleinster, mittlerer, größer, s, dass sich die entsprechenden Werte in diesem Array zu null summieren. Okay.

1:22 Und bis hierhin ist es die Menge all dieser Trippel und dann die Betragsstürche ma da draußen die Anzahl. äh die Kennenggröße, ich hatte bei der Brücke als als Analogie, die Eingabegröße für die Brücke war die Distanz, die wir überspannen wollen, die Größe vom Tal. Und das werden wir auch hier immer wieder brauchen. Ähm, wir brauchen eine Sache, die wir annehmen, dass sie wächst oder an der wir die kommt die Größe von der Eingabe festmachen. Das ist hier einfach die Anzahl Zahlen, mit der ich loslaufe.

1:57 Ohne allzu sehr zu motivieren, warum das so ist, ist das Problem so wie es da steht natürlich erstmal ganz abstrakt. Äh, es hat aber so ein paar ähm geometrische Anwendungen, wo genau dieses Problem am Ende der harte Kern ist, den man lösen muss. Also z.B. kolineare Trippel von Punkten sind einfach drei Punkte, die auf einer geraden liegen. Das ist ganz oft für irgendwelche geometrischen Konstruktionen so ein so ein Randfall, den man abfangen muss, der irgendwelche sonstigen Konstruktionen kaputt macht. Das heißt, das ist so ein Klassiker, den man in dem Precessing machen würde. Ähm, wenn Sie drüber nachdenken, ist das quasi das gleiche. Wenn Sie eine eine Menge von Geraden haben, können Sie rauskriegen mit diesem Problem, ob sich drei in genau einem Punkt schneiden. Zwei Geraden in der normalen Ebene schneiden sie ja immer in einem Punkt, aber wenn ich eine dritte Gerade dazu nehme, könnten sie sich in drei verschiedenen Punkten schneiden, ne? Im allgemeinen ist eher so, aber wenn ich die diese Gerade hier weiter rüber schiebe, dann treffen die sich genau einem Punkt und das läuft auch auf dieses Problem hinaus.

2:57 und gibt noch ein paar ähm paar andere ähnliche. Damit wir sicher sind, dass alle vom gleichen Problem ausgehen, machen wir eine kleinen Test dazu.

3:19 Das ist, glaube ich, die erste Slidochfrage, wo so ernsthaft inhaltlich was gefragt wird. Da gibt's also jetzt eine richtige Antwort, die ich Ihnen dann irgendwann zeige, aber noch nicht sofort und sie sehen auch für den Moment auch noch nicht, was ihre Komulatoren Komilitorinnen abstimmen.

3:39 Es ist aber keine Trickfrage. Es geht einfach nur darum, ob Sie die Problemdefinition genau gelesen haben. Wenn Sie mögen, kann ich auch zu der zurückmachen. Die Aufgabenstellung sehen Sie ja auch auf Ihrem Gerät.

4:28 Immer der Moment, der der mir Spaß macht, weil ich sehe ja schon, was sie alle so abgestimmt haben, aber sie wissen es noch nicht. Ich gebe ihn mal noch ein Z Minuten.

5:26 Ziel ist natürlich immer, dass wir dann auch von allen Antwort kriegen. Äh, sie wissen, das ist anonym und es interessiert mich auch nicht so sehr, was sie als einzelne so abgestimmt haben. Die Fragen sind auch oft so gestellt. Wie gesagt, hier nichts, keine Trickfrage. Soll nicht besonders knobelig sein, es soll nur eine Detail in der Definition noch mal klar machen. Ähm, die Fragen sind aber oft auch so gestellt, dass ich nicht erwartte, dass sie das schon wissen oder dass sie das direkt alle richtig machen. Es geht mehr darum um den Lerneffekt. Deswegen lassen sich bitte nicht abhalten abzustimmen. Gut, haben wir fast alle eingesammelt. Dann ähm zeige ich Ihnen mal die Ergebnisse. Zumindest s ich immer immer besonders spannend, wenn so quer durch die Bank alles dabei ist. Keiner hat 4,5 gestimmt. Das ist schon mal gut.

6:24 Also ich kann auch kann auch hier an der Stelle auflösen und wir berechnen das einfach kurz durch. Also, der Kern ähm an dem man auf jeden Fall in die eine oder andere das Richtung das Problem hätte definieren können, äh ist, was passiert eigentlich, wenn in dieser Eingabe ähm Zahlen mehrfach vorkommen? Das ist hier ja nicht ausgeschlossen. A kann die gleiche Zahl fünfm enthalten und dann ist erstmal, wenn ich nach Trippeln frage, vielleicht nicht klar definiert, was was möchte ich jetzt? möchte ich ähm dieses diese Zahl mehrmals verwenden können und es ist dann die gleiche Zahl oder gilt's für jede Position separat? Wenn jemand so eine Frage stellt, dann ist gut, wenn man eine formale Definition hat, denn hier steht unein unzweideutig eindeutig äh was die Antwort sein soll, nämlich die Anzahl aller Indexpar Indexpel. Dementsprechend würde eine Zahl, die mehrfach vorkommt, trotzdem mehrfach gezählt werden, auch wenn es die gleiche Zahl ist, weil die Indizs unterschiedlich sind.

7:29 Also hier konkret, was haben wir für Indic? Ja, das ist auch ein schöner ähm schöner Plug, um die Notation zu erklären, glaube ich, die kam noch gar nicht vor. Äh, das soll einfach heißen, das ist ein Array, der bei null anfängt und sechs Elemente hat. Und die runde Klammer ist wie für offene Intervalle in der Mathematik. Ähm, sie kennen sicher die Schreibweise so als die reellen Zahlen.

8:05 Also, das ist normalerweise die Menge der reellen Zahlen, die zwischen diesen Intervallen, zwischen diesen Grenzen liegt, also inklusive dem A, aber exklusive dem B. Und in in der Informatik haben wir sehr oft Intervalle von ganzen Zahlen. Deswegen hat sich hier so eine Notation eingebürgert, die letztlich das gleiche sagt, nur dass es jetzt eine ganze Zahl ist. Und auch wieder a inklusive und b exklusive. Ich hätte das natürlich umschreiben können als alle Zahlen von A bis b -1. Beides inklusive äh könnte man tun. Also das ist das gleiche, was man manchmal so schreibt, ne? A + 1 tuck tuck tuck bis b - 1.

8:55 Also ich sollte mir die englischen Einzen abgewöhnen hier. Das äh ist vielleicht so klarer. Das ist natürlich das gleiche, aber da wir in der Informatik gern bei null anfangen zu zählen. Warum eigentlich?

9:12 Da zeigt sich jetzt ob jemand mit Pointer Arithmetik äh programmiert hat. Ja. Ah, ich glaube, sie haben sie haben rechts. Es gibt noch einen zweiten Punkt. ähm null äh bis zu einer Zahl sind auch die Modologen. Das hat manchmal ähm ist manchmal bequemer. Und für Arrays, was ist ein Array? So wie Java es schreibt, ähm könnte man auch irgendeinen Anfangspunkt für diese Indizes nehmen. Äh aber auf Hardwareebene ist so ein Zugriff auf ein Array einfach nur den Pointer für den Start vom Array um Offset i verschieben und da macht es einfach Sinn, dass man bei null anfängt, weil das das erste Element ist äh oder was heißt macht Sinn. Das hat sich halt so eingebürgert. Ich glaube, das ist am Ende nur eine Konvention, die hätte man natürlich auch anders treffen können, aber sie ist unter allen Programmiersprachen, außer so ein paar komischen Exoten wie R und so, äh weit verbreitet das Arrays bei null anfangen.

10:32 Und so möchte ich das hier auch machen. Arrays fangen immer bei null an, um trotzdem bequem die Länge hinschreiben zu können, ohne jedes Mal -1 zu tippen, machen wir die Runden Klammern. Okay. Äh, die gibt's in der Schreibweise in Java nicht, aber andere Programmiersprachen haben das auch schon in wesentlichen in dieser Form übernommen. Langer Rede, kurze Sinn für unsere sechs Zahlen. Hier haben wir die Indizs 0 1 2 3 4 und 5. Das ist eine null, keine 6. Und welche Tripel habe ich jetzt, die sich zu null summieren? Na ja, die ersten drei, ne? 0 1 2. Dann kann ich aber auch statt der 2 die 5 nehmen. 0 1 5 und dann gibt's noch die 2 und die 2 -1, ne? Also 2 4 5 äh das sind die drei und dann können sie ausprobieren. Alle anderen äh summieren sich eben nicht zu null. Dementsprechend ist ist die drei die richtige Antwort.

11:33 Und ähm warum da eine Exception kommen sollte, weiß ich nicht. Äh das Problem hat ja so erstmal noch gar nichts mit Java zu tun. Frage oder Kommentar?

11:56 Genau. Die Reihenfolge der Indizs ähm steht auch hier. müssen sortiert sein. Äh, also I ist kleiner als J ist kleiner als K. Das heiß alle alle Tripel, die hier in dieser Menge vorkommen, sind sortiert.

12:13 Dementsprechend ähm 012 ist eine Lösung. Natürlich würden sich auch die Indizes 2 zu null summieren, aber die Definition von dem Problem sagt halt, ich hätte die gerne nur in sortierte Reihenfolge. Wäre auch sonst ähm redundant, dann würden sie jedes Tripel sechs mal zählen für alle Permutationen. Brauchen wir nicht einmal reicht. Ist aber auch nur eine Konvention. Und der Punkt ist, sie denken an meinen meine lange Rede irgendwann in den letzten Kapiteln, wenn wir auf solchen Abstraktionen aufbauen wollen, sie definieren diese Schnittstelle, ihr Kollege, Ihre Kollegin programmiert unter der Annahme, dass das unsere Konvention ist. ähm verwendet dann die Klassen, die Sie schreiben. Äh jetzt aber und Sie implementieren die dann. Somit das damit das am Ende zusammenpasst, müssen sie sich auf eine Konvention einigen, auch wenn die Konvention ein bisschen beliebig ist. Hätte man anders wählen können, aber wir haben uns für eine eben festgelegt. Und was wir ein bisschen trainieren müssen, ist äh genau lesen und sich Harklein an die Dinge halten. So ein bisschen pedant sein. Genau das, was unter inzwischenmenschlichen Beziehung manchmal eher nervt, ist mit dem Computer das, was man meistens braucht.

13:27 Da gibt's auch eventuell dann Reibereien manchmal Berufskrankheiten der Informatiker. Okay. Ähm, das heißt, wir haben jetzt das Problem verstanden. Jetzt wollen wir es vielleicht auch lösen, also einen Algorithmus dafür finden. Und an der Stelle ähm möchte ich was einführen, was wir immer und immer und immer wieder sehen werden. Und ich werde mich auch bemühen mit diesen Icons das irgendwie konsistent zu halten. Äh und was sie auch in den Übungen dann entsprechend so äh durchziehen sollen. Und immer es heißt, sie sollen einen Algorithmus entwerfen, stecken da eigentlich vier Schritte dahinter oder vier Teile, die sie liefern sollen. Sie beschreiben kurz, werde ihn gleich auf der nächsten Folie ein Beispiel zeigen, das kann manchmal ein Wort sein. Sie beschreiben kurz die Idee, die der Algorithmus verfolgt und die Datenstruktur. Das ist so ein bisschen ähm bis man ein paar Beispiele gesehen hat, vielleicht nicht so ganz klar, was das jetzt heißt und wie detailliert das sein muss.

14:26 Werden Sie aber sehen. Das ist im Wesentlichen das Ziel daran ist, dass aus der Idee alleine ein Experte, der schon viel Übung hat, dann den Rest sich denken kann und das soll sie trainieren, zu so einem Experten zu werden. Das soll uns das Leben leichter machen einzusortieren, was da jetzt kommt als nächstes. Ähm, das das Schlimmste ist so einen Algorithmenentwurf, wo dann so ein dreiseitiger Fließtext, Wall of Text kommt und man sich dann irgendwo rausklamüsern muss, was eigentlich passiert und wir wollen sie eben dahinziehen, dass sie das äh geschickt geschickter aufschreiben, effizienter aufschreiben. Die Idee selber ist aber dann doch zu abstrakt, um im gerade im Anfängerstadium zu prüfen, ob sie funktioniert. Deswegen kommen noch die anderen Teile. Pseudocode ist vielleicht am klarsten, das ist im Detail aufgeschrieben, wie dieser Algorithmus funktionieren soll. Werden wir auch noch viele Beispiele sehen. Dann wollen wir in der Regel einen Korrektheitsbeweis, der oder zumindest ein Argument, was plausibel macht, warum der Algorithmus die richtige Antwort liefert.

15:28 Algorithmische Probleme sind bei uns eiglich immer hier so dieser und dieser Form, wir haben irgendeine Eingabe und produzieren irgendein Ergebnis. Dementsprechend ist der Korrektheitsbeweis in aller Regel, dass die Ausgabe korrekt ist für alle möglichen möglichen denkbaren Eingaben. Und letztlich der Punkt, auf den ich vorhin ja schon angespielt habe, uns interessiert nicht nur, dass es irgendwie geht, sondern es soll schnell gehen oder effizient gehen. Das heißt, wir wollen wissen, was sind die die Kosten für diesen Algorithmus? Äh, das haben sie jetzt offiziell noch nicht gesehen, Tetklassen, aber steht hier schon mal für als Vorgotation. In aller Regel wollen wir einen eine Tetakklasse für den Worst Case haben, manchmal auch den Speicherbedarf, wenn der interessant ist. Das so ein bisschen problemabhängig.

16:15 Nach der Schablone sollen sie immer vorgehen. Und jetzt machen wir das mal. Also free wieder und an der Stelle auch ein Ratschlag, der für Klausuren schon helfen soll. Wenn sie ein Problem bekommen und irgendeinen Algorithmus bauen sollen oder es nicht genauer verlangt, wie gut oder wie schnell der sein soll, dann machen sie erstmal das einfachste. Das ist meistens auch das Dümmste und langsamste, aber das reicht manchmal auch schon. Wenn Sie das ein paar mal gemacht haben, wir werden das auch auf Kilonova dann üben, dann können Sie aus der Beschreibung von dem Problem, der Beschränkung, wie groß die Eingaben sind und dem Timelimit oft schon so ein bisschen abschätzen, ob ihr ganz einfacher Ansatz da funktionieren kann oder bis zu welcher Größe der funktionieren kann. Das kann man mit der Zeit lernen. Äh, für den Anfang machen wir es uns erstmal einfach. Wenn man die die einfachste Idee und für dieses äh Trippelfinden Problem ist die einfachste Idee sicherlich ähm hier Brot Force auch genannt hatte. Alle Trippel durchprobieren, die es gibt und prüfen, summiert es sich zu null, dann zähle ich. Summiert es sich nicht zu null, dann zähle ich es nicht. Das heißt, die algorithmische Idee ist hier dieser eine Satz.

17:25 Äh, wir können das als Code aufschreiben. Das ist schon sehr detaillierter Pseudo Code, aber ist hier einfach genug. mal so einen Zähler, der ist am Anfang null, dann habe ich drei geschachtelte Vorschleifen, die genau alle Tripel durchgehen. Der ähm worauf man achten muss, ist, dass die wieder sortiert sind. Also, ich habe I, J und K immer so direkt in der Schleife initialisiert, dass die eben aufsteigend sortiert sind. Das heißt, wir gehen jedes jedes zulässige Trippel, das wir vielleicht zählen möchten, auch genau einmal durch, dann bilden wir die Summe und falls die null ist, erhöhen wir den Zähler. Okay, ist sicherlich was, was sie auch ohne Probleme jetzt in Java umsetzen könnten. Haben sie ja äh in auf dem auf dem Level schon viel vielfach spannenderes gemacht. Ähm, der Pseudocode muss nicht Java Code sein, der darf aber auch Java Code sein. Ist an der Stelle ähm eine Option, aber nicht die einzige. Das Schöne an den einfachen Lösungen ist, dass der Korrektheitsbeweis dann oft ziemlich langweilig ist. Wir machen ganz genau das, was die Definition sagt. kann ja noch mal hierher kopieren. Letztlich haben wir hier in mathematischer Notation das stehen.

18:42 Aha. Ab und zuu gibt's so spannende Bugs in dem Programm. Manchmal sind Bugs, manchmal sitzt das Problem vorm Bildschirm oder steht. Ich kann den Hintergrund nicht markieren, der ist äh also hier nur noch mal eingefügt, wir berechnen mit dem Code effektiv in Vorschleifen ausgeführt, was in der formalen Definition in mathematischer Notation steht. Das ist schon das gleiche. Da gibt's nicht mehr viel zu tun für den Korrektheitsbeweis. Was noch fehlt, ist die Analyse und das ist der einzige Teil, wo dieser einfache Ansatz schon ein bisschen was ähm erfordert von uns. Deswegen machen wir das im Detail. Wir kommen dann noch mal drauf zurück, um das ein bisschen genau einzuordnen, was was mache ich hier? Hier erstmal ohne große Motivation verspreche ich Ihnen sozusagen, das was wir tun müssen ist zählen, wie oft diese Schleifen, diese innerste Schleife, die Zahlen 5 und 6 ausgeführt werden. Und im Wesentlichen ist die Anzahl dieser Ausführung von diesem innersten Teil, das ist ein gutes eine gute Nährung für die Zeit von dieser ganzen äh von dem ganzen Code.

20:06 Okay. Wie oft wird das ausgeführt, wenn ich geschachtelte Vorschleifen habe? auch da. Wir machen das noch ein bisschen strukturierter. Ich springe so ein bisschen jetzt erstmal da rein. Ähm geschachtelte Vorschleifen in diesem einfachen Sinn kann ich ersetzen durch eine Summe. Bin ich wieder der mathematischen Welt. Ich habe eine Ausführung pro Kombination von I, J und K. Die zähle ich mit ein und die Ausführung selber, da habe ich Schleifen, die genau die Vorschleifen emitieren. Sprich das I läuft von 0 bis N- J von I + 1 bis n- 2 und das K von S von I + 1 bis n- 2, das K von J + 1 bis N-1.

20:54 Damit wären wir im Prinzip fertig, nur ist das nicht sehr aussagekräftig. Wir können aber die Summen deutlich vereinfachen und das ist so ein bisschen Handwerkszeug. Der erste Schritt ist diese innere Summe summiert über ein. Das heißt, ich habe da als Ergebnis dieser inneren Summe genauso viel an Wert, wie ich Ausführungen habe dieser dieser Summe. Und im Allgemeinen, das ist ja ähm beide Endpunkte inklusive, habe ich Endpunkt Startpunkt + 1, weil hier der Endpunkt, das -1 halt ist das +1 direkt weggekürzt. Also, was ich meine ist äh Startpunkt und Endpunkt inklusive, die die Menge an Zahlen in diesem Bereich ist immer b - a + 1.

21:49 Das kann ich hier direkt einsetzen. Dann habe ich die innere Summe ersetzt. Okay, jetzt machen wir weiter mit dem Rest. An der Stelle könnte man jetzt die Summe aufspalten. Ich habe ja hier eine Summe über n. Das hängt gar nicht von i und J ab. Das könnte ich rausziehen und ich habe hier eine Summe über n über das j + 1. Ich kann es mir hier aber einfacher machen, wenn man sich genau anschaut, was hier passiert. Ich habe hier eine lineare Funktion, die fängt irgendwie, wenn der wenn das J den kleinsten Wert hat, dann fängt die bei null rum an, also bei bei n rum an und wenn J den größten Wert halt, geht sie fast bis 0 runter oder bis 1, wenn man genau ist. Das heißt, ich kann diese innere Summe rückwärts summieren. Summe ist ja kommutativ. Das heißt, ich summiere die Werte, die hier drin stehen, rückwärts. Dann habe ich die Summe ein bisschen vereinfacht.

22:38 Dafür setzen wir daf dafür muss man einfach den kleinsten größten Wert für j einsetzen. Wenn ich das hier mache, dann habe ich n - i + 1 + 1.

22:54 Das heißt, ich habe n - i -2 und für den für die obere Schranke hätte ich n - n - 2 + 1. Da kürzt sich das n weg. Aus der -2 und 1 wird -1 und dann wird ein +1 durch das. Okay, habe ich aber hier auch noch mal sauber aufgeschrieben. Also wir fangen von 1 an und laufen bis n - i - 2. Und damit ist dann der Teil, über den ich summiere, einfach nur j. Ich hatte ja gerade hier mir angeschaut, über welche Werte dieser dieser innere Termit. Damit ist das eine einfachere Summe. Insbesondere ist das eine Summe, die Sie vielleicht hoffentlich kennen. Äh, das ist diese kleine Gausformel. Sie kennen diesen Ich summiere die ersten Integer auf. Der clevere Trick ist, wir machen das doppelt.

23:56 einmal vorwärts und einmal rückwärts. Stellen fest, überall steht fünf, die gleiche Zahl und dann kann ich das ausrechnen. Ich habe dann nur das doppelte, das heißt, ich muss durch zwei teilen. Ähm, das ist die allgemeine Lösung. Es gibt aber auch ein Muss mal schauen, ob ich hier gerade die Navig navigieren kann.

24:35 Also sehen dooferweise die URL jetzt nicht. Dann kopiere ich die mal hier mit rein. Nur so für später. Also für ganz viele solcher Formeln, ich möchte eine Summe vereinfachen, gibt's eine tolle Formelsammlung, das TCS Sheet, das Theoretical Computer Science Cheat Sheet. Das finden Sie auch, wenn Sie es googeln. Ich habe eine leicht abgewandelte Version wegen meiner Onotation. Kommen wir später noch mal drauf zurück. Ähm, die finden Sie ja auf meiner Webseite. Deswegen der Link führt sie zu diesem äh von der mit der Version, wo nur hier auf der ersten Seite ein paar Dinge anders sind als im Original. Und insbesondere gibt's hier aber jede Menge Formeln. Also nur so zum ähm für den Kontext. Das Ding ist natürlich gebaut für Forscher, die damit ihren ganzen Tag verbringen. Wir werden die die ersten Handvollformeln überhaupt jemals nur benutzen und vielleicht ein paar einzelne noch zwischen raus. Dass da noch ganz viel anderer Kram drauf steht, braucht sie weder beunruhigen noch kümmern, aber vielleicht ist es ja irgendwann mal hilfreich. Deswegen dachte ich, ich streue es hier mal ein.

25:50 Insbesondere steht hier die allererste Formel. Ja, ist die, die wir jetzt benutzen wollen. Die können wir uns mal mitnehmen. In dem Fall würde ich hoffen, dass sie die auch so hinkriegen. Die ist ja leicht, sich zu merken, aber falls man sie mal vergessen sollte, dann findet man sowas auch auf diesem Cheat Sheet.

26:17 Damit können wir diese Summe vereinfachen. Und äh was muss ich dafür tun? Der unterte Bereich stimmt schon. Und oben habe ich jetzt eben statt n diesen Term. Das heißt, ich muss hier den einsetzen. Habe ich hier auch schon mal vorbereitet. Also hier ist n n + 1, das kürzt sich mit dem -2 -1 und das halbe das halbe kommt, weil wir wer die Summe vorwärts rückwärtsen. Jetzt sind wir einen Schritt weiter. Jetzt haben wir noch eine Summe außen, die immer noch übrig ist. Die ist hartnäckig und das sieht jetzt so ein bisschen einschüchternd aus mit diesem langen Bruch da in der Mitte. Das heißt, da können wir jetzt ein bisschen versuchen, Dinge zu vereinfachen. Der erste Punkt ist auch hier wieder, im großen und ganzen sind das zwei Terme, die sehr ähnlich sind und die rückwärts laufen. Ich meine, damit ich fange, wenn ich für i 0 anfange, dann habe ich hier ähm im wesentlichen n n n - 2 und n -1.

27:21 Und wenn ich die obere Schranke der Summe einsetze, dann kürzt sich das N weg und es bleiben so ein paar ähm kleine Zahlen übrig. Also konkret das n, dann habe ich 3 - 2, also 1 und hier 2. Das heißt, das ganze läuft von 1* 2/ bis zu n - 2 n- 1 halbe. Aber diese diese zwei Klammern, diese zwei Faktoren sind ja immer nur um eins unterschiedlich. S immer der hier ist eins kleiner als der hier. Ansonsten machen die schön die gleiche Bewegung mit. Also erste Vereinfachung ist rückwärts summieren. Dann komme ich zu dem Teil. Da summiere ich also jetzt ähm i und i + 1. Dann fängt i bei 1 an und endet bei n - 2. Genau was wir hier ausgerechnet hatten. Na und hier da kann ich ausmultiplizieren und an der Stelle lohnt es sich dann auch die Summe aufzuspalten in zwei. Also das hier ist ja i² + i. Und dann ziehe ich das in zwei Summen auseinander.

28:31 Wieder Summen sind kommutativ, ich kann die umgruppieren. Das da ist im Wesentlichen ja, was wir eben schon benutzt haben, kleine Gausformel. Das da ist irgendwie sozusagen der große Bruder davon. Den hat man vielleicht nicht im Kopf, aber auf dem Cheat, da finden Sie die Formel auch nicht weit weg. Äh tatsächlich direkt nebenend dran. Das heißt, wenn wir uns die auch mitnehmen, Ist ein bisschen mehr Materialschlacht, weil wir jetzt hier äh in dieser Formel n - 2 einsetzen müssen für n, aber zumindest sind wir dann alle summenlos.

29:29 Machen wir das. Also, der Teil ist wie gehabt, das ist n - 2 und n - 2 + 1. Das ein halb hier gibt die viertel und hier ähm da hat ich unten Nenner sechs und die zwei hier, das gibt die 12 und die anderen sind eben eingesetzt, was ich da in der in der Formel hatte. Uff, sieht jetzt auch schon äh immer noch nicht so toll aus, aber ich kann die auf einen Bruch ziehen und sie sehen, die haben ja ähm hier ein großen Teil gemeinsam. Das heißt, das kann ich ausklammern. Außerdem steht hier hier effektiv dreimal so viel wie hier. Das heißt, da gibt's dann auch noch mal einen Faktor 3 hier oben und dann vereinfacht sich das tatsächlich zu einer sehr kompakten Formel.

30:14 Den Teil äh rechne ich mal jetzt nicht noch mal von Hand nach. damit wir irgendwann mal vorankommen. Diese Art von Umform können auch Computer Algebra Systeme wie wie Wolfram Alpha oder ähm gibt auch ähm Sage Mark für Python als Open Source Lösung, die können das ganz gut, wenn man sie passend bedienen kann, können sie ab und zu verwenden, um sich zu überprüfen. In einfachen Fällen Teile wie sowas in vielleicht etwas weniger aufwendiger Form dürfen auch mal in der Klausur dran kommen oder in den Übung. Da sollen sie es schon dann auch von Hand zumindest können, aber sie müssen das nicht jedes Mal durch Xen. Mit dem Term werden wir jetzt erstmal fertig. Ich glaube, den kann man nicht wirklich schöner schreiben. Ähm, es sei denn, man erkennt, dass das äh ein Binomialkoeffizient ist, aber das ist ja nur eine Abkürzung für die gleiche Formel.

31:08 Äh, Klammer auf. Man hätte natürlich von Anfang an sehen können, dass was wir hier machen mit den Trippeln aus n genau ein Binomialkoeffizient ist. Wir wählen genau die drei elementigen Teilmengen aus einer nementigen Menge, aber dann hätten wir ja nicht so viel gelernt über Summenumformung und die direkte Übersetzung vom Code äh ist mir an der Stelle wichtig. Aber ist es denn jetzt gut? Was heißt es jetzt für unseren Algorithmus? Den Teil haben wir jetzt noch nicht adressiert. Und an der Stelle, bevor wir dann ähm diesen Algorithmus mit eventuell anderen Alternativen vergleichen, kann man trotzdem immer schon eine Überschlagsrechnung machen, denn wir haben ja hier jetzt eine konkrete Zahl. Wenn ich n einsetze, kriege ich irgendwas raus. Die Einheit davon ist ein bisschen seltsam. Das ist die Anzahl Ausführung dieser zwei Zeilen. Aber das ist so eine Handvoll äh Instruktion auf der CPU. Das wird so eine handvoll Nanosekunden brauchen.

32:04 Ähm, hier war ich mal mit einer Handvoll sehr großzügig. Die Annahme ist, ich mache eine von also eine Nahmesekunde kostet es diese beiden Zahlen auszuführen. Das wahrscheinlich ein bisschen zu optimistisch, aber für den ähm für den ganz groben für die ganz grobe Einordnung reicht es. Dann können Sie mal ein paar Werte für n einsetzen. Sehen Sie hier die Anzahliteration von diesen zwei Zeilen, die wächst schon ganz äh erstaunlich. Und umgerechnet in Operation pro Nesekunde habe ich am Anfang noch ganz gute Karten und dann springt es relativ schnell von Sekunden zu Minuten zu Tagen und dann können sie sich überlegen, dass sie das vielleicht für 10.000 noch machen können und für 100.000 1000 ist dann doch schon, da müssen sie dann irgendwie hochgradig parallelisieren oder Grafikkarten oder sonst irgendwas äh schlaues sich überlegen, damit das noch sinnvoll fertig wird.

33:03 Diese Art von Rechnung ist ganz oft hilfreich. Sollten Sie sich nicht ausreden lassen, dass man sowas machen kann, auch wenn es für viele Algorithmen nicht ganz so einfach geht, weil diese präzise Formel, wie wir sie hier am Ende hatten, die geht in diesem einfachen Beispiel, die wird's in anderen komplizierteren Algorithmen schwieriger haben, da werden wir es schwieriger haben, so eine explizite Formel zu finden. Da kommen wir noch mal wieder drauf zurück. möchte auch erwähnen, dass das Problem, dass wir hier uns angeschaut haben, Freum bessere Algorithmen hat. Die haben wir uns noch nicht überlegt. Also was hier steht, diese wir können wahrscheinlich für 100.000 Zahlen das Problem nicht lösen, bezieht sich auf unseren einfachen Algorithmus. Den haben wir analysiert und für den gilt diese Aussage.