Ich habe Ihnen gerade den Bubble Sort Algorithmus gezeigt, mit dem man mit dem Computer arbeiten können, um eine unsortierte, ungeordnete Liste natürlicher Zahlen zu ordnen.

Jetzt ist es immer interessant für Informatiker zu wissen, wie effizient ist denn der Algorithmus? Wie viele Schritte braucht der denn, um zum Ergebnis zu kommen? Ich verrate nämlich, es gibt noch weitere Sortier-Algorithmen und man möchte natürlich immer möglichst schnell zum Ergebnis kommen.

Das heißt, man sollte einen Algorithmus nehmen, der möglichst schnell und effizient arbeitet. Informatiker interessiert an dieser Stelle immer die Anzahl der Vergleichsoperationen, die man durchführen muss. Wie viele Vergleiche muss man denn jetzt beispielsweise durchführen, wenn man sechs Karten hat?

Gehen wir doch mal vom Anfang aus. Wir haben die erste Karte genommen. Wie viele Vergleiche haben wir im ersten Durchgang durchgeführt? Fünf, genau. Wir haben eine Karte genommen, haben mit fünf weiteren Karten verglichen.

Ab und zu hat die Karte gewechselt, aber egal, beim ersten Durchgang waren es fünf Schritte. Also beim ersten Durchgang haben wir fünf Vergleiche gebraucht. Jetzt war die größte Zahl hinten die Liste um eins kleiner. Wie viele Vergleiche haben wir dann gebraucht? Vier. Dann war die Liste wieder eins kleiner, dann haben wir drei Vergleiche gebraucht.

Dann war die Liste wieder um eins kleiner. Dann haben wir noch drei Karten gehabt. Dann haben wir eine Karte zweimal verglichen, also zwei Vergleiche. Und am Schluss, wenn noch zwei Karten übrig waren, noch ein Vergleich.

Jetzt können wir das mal ausrechnen. Wie viele Vergleiche haben wir gebraucht? Eins plus zwei ist drei, sechs, zehn, fünfzehn Vergleiche. Wir haben fünfzehn Vergleiche gebraucht. Jetzt könnte einer mal interessieren, wie viele Vergleiche brauche ich denn, wenn ich tausend Karten habe?

Wie viele Vergleiche brauche ich, wenn ich tausend Karten habe? Tausend Karten? 999 Fakultät. Was meinen die anderen?

999 mal drei, wir sammeln mal ein paar Hypothesen. Also, ich sammel hier rechts für die Hypothesen. 999 mal drei und 999 Fakultät.

Stimmt beides nicht. Okay, hier kommt 1001 mal 50.

Schreibt es mal auf. Sind wir schon auf dem richtigen Weg? In etwa 500.000. Ein bisschen weniger als 500.000.

Ein bisschen weniger als 500.000. Okay. Also, wir sind uns alle nicht sicher. Da müssen wir jetzt mal systematisch rangehen.

Und zwar gehen wir mal davon aus, dass wir N plus eins Karten haben. Die Erbsenzähler unter Ihnen dürfen weiterhin Sigma von N denken. Wir haben N plus eins Karten. Wir haben hier sechs Karten und ich will aber von der fünf ausgehen, weil ich hier mit der fünf beginnen will.

Also haben wir fünf plus eins Karten. Wir haben N plus eins Karten. Wenn wir N plus eins Karten haben, müssen wir alle Zahlen von eins bis N addieren, um auf die Anzahl der Vergleiche zu kommen.

Eins plus zwei ist mal rückwärts gedacht. Plus drei plus Punkt plus N. Wenn wir sechs Karten haben, müssen wir alle Zahlen von eins bis fünf addieren.

Weil die Liste immer um eins kleiner wird und dementsprechend die Anzahl der Vergleichoperation um eins kleiner. Wenn wir 1000 Karten haben, müssen wir alle Zahlen von eins bis 999 addieren. So, ich führe jetzt mal wieder neue Symbole ein. Diese Punkt-Punkt-Punkt-Schreibweise, die mag man nicht so.

Um zu sagen, man addiert alle Zahlen von eins bis N, formuliert man das auch so. Ein großes Sigma, das macht man so. Muss man vielleicht ein bisschen üben.

Und jetzt habe ich hier eine Laufvariable, die beginnt bei eins und die endet bei N. Und ich schreibe sie einfach hier rein. Das bedeutet, die Summe aller Zahlen oder die Summe von i gleich eins bis N über i.

Muss ich so vorstellen? Dieses Zeichen bedeutet, nimm dir i und setze es erstmal eins. Und nimm das, was da drin steht und ersetze überall i durch eins. So, dann schreiben wir plus hin.

Dann nimm das nächste i zwei und setze i ein, setze zwei ein. Und dann kommt wieder ein plus. Und dann ist i drei, setze es ein, plus und so weiter. Also wir haben sozusagen, wir laufen hier mit i von eins bis N schrittweise durch. Ersetzen das, was hier drin steht, immer durch das aktuelle i.

Und denken uns ein plus dazwischen. Ich führe es nochmal durch. Setze i gleich eins. Nimm das, was da drin steht und ersetze jedes i durch eins. Hier habe ich nur ein i stehen, also eins. Und dann kommt ein plus. Dann nimm den nächsten Teil, jetzt ist i zwei im nächsten Schritt. Ersetze hier drin alles, was i ist, durch zwei.

Gibt es nur eins und so weiter. Nächster Schritt, i ist drei und so weiter und so weiter. Bis i schließlich im letzten Schritt N ist, ersetze jedes i hier im Innenteil durch N. Und dann, als der letzte Schritt war, waren wir fertig.

Jetzt ist das sehr mühsam auszurechnen. Sie hatten hier schon Versuche gemacht, Wege zu finden, das einfach auszurechnen. Wir wollen nicht tausend Zahlen addieren. Das ist mühsam. Das heißt, wir brauchen irgendwie eine einfache Formel.

Das wäre schön. Eine einfache Formel. Und jetzt beginnt die eigentliche Arbeit der Mathematiker, die darin besteht, auf kreative Ideen zu kommen. Sie haben vielleicht den Eindruck gewonnen in der ersten Übung, dass alles sehr schematisch abläuft.

Das ist zum Teil auch wahr. Teile können schematisch ablaufen in der Mathematik. Aber viele Erkenntnisse in der Mathematik kommen nicht dadurch, dass man einfach irgendwie deduktiv was ableitet,

sondern dadurch, dass man eine Einsicht hat und eine Erkenntnis. Und das ist etwas, was nicht schematisch vorgeht. Hier muss man sich selbst mit bestimmten Strategien helfen, um zu einer Lösung zu kommen. Und eine gute Strategie, wie man sich selbst auf Erkenntnisse bringen kann,

ist, in der Mathematik etwas zu visualisieren. Etwas mal bildlich darzustellen. Mathematiker sind nur scheinbar Menschen, die formal in Symbolen denken. Mathematiker denken nur zum Teil in Symbolen.

Sie denken auch bildlich. Das ist der weitaus wichtigere Teil, um zu neuen Erkenntnissen zu gelangen. Deswegen veranschäulichen wir uns das mal bildlich. Nehmen wir mal dieses Beispiel nochmal, die Zahlen von 1 bis 5, addieren.

Wenn ich mir ein Bild male, könnte man sich das ja vielleicht so vorstellen. Ich habe erst die 1, dann addiere ich die 2 drauf, dann addiere ich die 3 drauf, dann addiere ich die 4 drauf

und dann addiere ich die 5 drauf. Sieht aus wie ein Dreieck, oder? Oh, ich habe es ein bisschen schiefgemalt.

Na ja. Sieht aus wie ein Dreieck. Das könnte man ja meinen. Das ist ja eigentlich die Fläche des Dreiecks durch diese ganzen Punkte. Vielleicht könnte man ja die Flächenformel mal anwenden, oder? Ein halber Grundseite mal Höhe.

Die Grundseite ist 5 lang, die Höhe ist 5 lang. Ein halber Grundseite mal Höhe, 5 mal 5 ist 25. Die Hälfte ist 12,5. Hier kommt nicht das richtige Ergebnis raus. Ah ja, okay, war eine Idee, stimmt aber nicht.

Aber jetzt könnte man auf eine andere Idee kommen, passen Sie mal auf. Wenn man so Punktmuster hat, jetzt habe ich eine Idee. Wenn man so Punktmuster hat, dann erinnert einen das vielleicht an so rechteckige Punktmuster.

Das Gauss-Verfahren, Sie wissen schon zu viel. Da will ich drauf hinaus, genau. Ich habe hier so rechteckiges, also wenn ich ein rechteckiges Punktmuster hätte, dann könnte ich einfach die beiden Seitenlänge miteinander multiplizieren und hätte die Anzahl der Punkte. Also mache ich jetzt mal das Folgende. Ich nehme mir mein Dreieck, kopiere es und setze es umgedreht nochmal drauf.

Ich mache das jetzt hier mal in einer anderen Farbe.

Ich habe das jetzt hier oben drauf gesetzt. Also hier auf den untersten habe ich es drauf gesetzt. Damit ist es auch hier oben, es liegt sozusagen schön auf.

So, ich habe jetzt hier so einen Dreieck mit den Seitenlängen 5 und 5 und hier auch mit den Seitenlängen 5 und 5. Was entsteht dann? Es entsteht ein Rechteck. Hier ist die Seitenlänge 5 und hier ist die Seitenlänge 6.

So, was muss ich machen, um die Anzahl aller Punkte hier zu nehmen? 5 mal 6, genau. So, das ist aber nicht die Anzahl der Punkte in unserem Dreieck,

sondern, genau, ich habe das Dreieck ja zweimal, also wenn ich jetzt 5 mal 6 durch 2 teile, komme ich auf meine 15. Aha, bitte? Wir können leider noch nicht teilen.

Wir können leider noch nicht teilen. Ja, genau, das war wieder der Erbsenzähler-Kommentar. Sie haben recht, ja. Deswegen habe ich ja vorher auch etwas keck gesagt, dass wir einfach jetzt mal davon ausgehen dürfen, dass wir alles wissen über die natürlichen Zahlen, was wir wissen. Sehr gut, ja.

Na gut, teilen können wir vielleicht schon, wenn wir sagen, teilen ist sozusagen die Umkehroperation zur Multiplikation. Welche Zahl muss ich mit 15 mal nehmen, damit ich auf 30 komme? Oder mit 2 mal nehmen, damit ich auf 30 komme? Welche Zahl muss ich mit 2 mal nehmen, damit ich auf 30 komme?

Okay, schon haben wir die Division. So, okay. Jetzt kann man daraus vielleicht ein allgemeines Schema ableiten. Wenn ich hier nicht 5 habe, sondern N habe, dann habe ich hier N plus 1,

nämlich gerade meine N, plus 1 noch oben drauf, weil ich das sonst nicht aufeinander bauen kann. Das bedeutet, wenn ich das allgemein habe, muss ich N mal N plus 1 nehmen und durch 2 teilen.

Und genau das ist die Summe aller Zahlen, also die Summe von I gleich 1 bis N über I.

Das heißt die Summe der ersten N natürlichen Zahlen, ohne die Null jetzt. Klar? Okay.