Video 3-0: Motivation

0:03 Im nächsten Kapitel schauen wir uns ein paar mathematische Grundlagen an, die wir immer wieder verwenden werden, wenn wir uns mit Algorithmen und Datenstrukturen beschäftigen.

0:10 Und da geht es ähm insbesondere um die Analyse von Algorithmen, die eben jetzt gleich noch mal kurz äh die Motivation zeigen, in der Informatik ganz essentiell ist. Es geht uns selten nur darum, ob man was irgendwie machen kann. So ein bisschen in der theoretischen Informatik ist auch das Thema, aber in aller Regel wollen wir wissen, wie schnell was geht. Denn wenn es nicht für halbwegs interessant große Eingaben schnell genug machbar ist, ist es fast so schlecht wie nicht machbar in der Praxis. Ähm das bedeutet aber, wir müssen uns ein bisschen darüber unterhalten, was heißt es eigentlich, wie bewerten wir und vergleichen wir Algorithmen? Dafür brauchen wir diese ähm bisschen mathematischen Werkzeuge dafür. und wir werden uns äh in Vorbereitung auf die Analyse von Algorithmen noch äh mit rekursiv definierten Sachen beschäftigen.

1:06 Noch mal eine Folie, die Sie schon kennen. Meine Analogie mit dem Brückenbrauen. Waren wir vielleicht nicht mehr im Detail drüber reden. Ich hoffe, sie erinnern sich. Mein Punkt an der Stelle war, oftmals ist eine eine Aufgabe zehn mal größer zu machen, nicht nur zehn mal so teuer, sondern deutlich mehr als zehn mal. In der Informatik haben wir ganz oft mal zehn, bevor wir bei den Eingabegrößen ankommen, die wir häufig haben. Dementsprechend ist die Art, wie sehr was größer und teurer wird, wenn wir in Faktor 10 in der Größe von der Eingabe dazu gewinnen. Der dominante Teil, der überhaupt die Kosten bestimmt und sozusagen wie gut wir auf kleinen Einzelschritten arbeiten, fast schon nicht mehr so relevant. Das ist nicht komplett irrelevant, aber es ist dominiert von diesem Wachstum mit der Eingabegröße.

2:06 Das heißt, aber irgendwie müssen wir das quantifizieren, was wir mit dieser Skalierbarkeit meinen. Ich hatte das da am Anfang noch ein bisschen wolkig und qualitativ belassen. Ähm, das ist jetzt vorbei. Für Algorithmen kommt's wie gesagt in erster Nährung auf das Wachstum der Kosten an und nicht so sehr auf die konkreten Zahlen. Ähm wie gesagt, wie in erster Nährung, ich werde ganz oft dann auch dazu sagen, wo die erste Näherung dann nicht gut genug ist. Trotzdem müssen wir die erstmal meistern.

2:38 Das heißt, insbesondere schnell ähm an Details im Coach bringen und Sachen optimieren, wo wir hier ein bisschen was da ein bisschen was sparen. Wenn sie den falschen Algorithmus optimieren, dann ist das alles für die Kratz der Aufwand, denn weder einen Detail der Implementierung noch eine zehnfach hundertfach größere Hardware rettet einen, wenn die Eingabe mehrere Zehner ähm Potenzen größer wird und der Algorithmus da eben nicht nicht mit skaliert.

3:12 den deutlich größeren Einfluss haben die richtige Wahl der Algorithmen und Datenstrukturen, denn damit können sie dieses Wachstum selbst verändern, potenziell verbessern. Ein Ziel wird's da auch sein, wir werden an vielen Stellen für algorithmische Probleme, die einem so begegnen, verschiedene Lösungen kennenlernen. Und die haben oft so einen gewissen Tradeoff. Manche sind einfacher, dafür sind sie langsamer, andere sind komplizierter, aber dafür schneller. Und dann lohnt sich ähm zu fragen, wie wie viel Unterschied macht sich ähm in dem Wachstum dieser Kosten da bemerkbar, wenn ich die eine oder andere Variante wähle. Und manchmal ist auch gar nicht so klar, wenn ich zwei Algorithmen habe, welcher besser ist, da kommt's dann auf ähm auf die Eingabe an. Für all das äh werden wir uns asymptotische Approximationen anschauen, also konkret Ohnotation, die den wahrscheinlich irgendwo schon begegnet ist. werden das auch noch mal von null an klar definieren und dann äh wissen sie Bescheid, egal ob Sie es vorher schon kannten und es ist sie müssen damit einfach so souveränen, dass sie das verwenden können, ohne ein paar der üblichen Fehler zu machen und dass sie sattelfest sind in der Bedeutung, was diese Unnotation ihnen sagen kann und was auch nicht manchmal an An der Stelle ist ist für mich wichtig in einem universitärenstudium insbesondere, dass wir mit formalen Definitionen loslegen. Sie werden an vielen Stellen Abkürzung nehmen können und dürfen, sobald wir die entsprechend gebaut haben, aber sie sollen an jeder Stelle grundsätzlich in der Lage sein, auf First Principles Definition runter zurückzugehen, denn das ist der einzige Weg, um im Zweifel irgendwie ein Missverständnis auszuräumen oder eine Unklarheit zu beseitigen.

5:05 auch da wieder regelmäßig wird Ihnen irgendeine KI oder ein Kollege was an den Kopf werfen, wo sie denken, Moment, kann das stimmen? Und dann können sie entweder beim Kopfkratzen verbleiben oder sie gehen zu der Definition und prüfen nach. M.