Video 5-2: Datenmodelle

0:02 Im nächsten Abschnitt schauen wir uns Datenmodelle an, wo wir uns also die Eingabe anschauen. Dazu so ein bisschen auch wieder ähm ausgeholt. Wenn ich Ihnen die Frage stellen würde, wer ist schneller, ein Mensch zu Fuß oder ein Zug? Was würden Sie sagen? Ja, der Zug ist schneller. Ja.

0:34 Also, wer schon immer mal jemand irgendwann am Bahnhof verabschiedet hat, der weiß, wenn so ein Zug anrollt, kann man noch eine Weile nebenher spurten und winken. Also ist natürlich ähm der Punkt ist, kommt drauf an, ja, äh wie lang die Strecke ist und auf lange Sicht gewinnt natürlich der Zug. Vielleicht, wenn man noch dazu sagt, ich bring es dann gleich zu Algorithmen zurück, wenn ich die Zugstrecke erst noch bauen muss, okay, dann ist vielleicht schon gar nicht mal so klar. Äh was es für Algorithmen heißt, ist natürlich, dass wir auch da verschieden große Eingaben haben können, die der Distanz hier entsprechen. Und je nachdem, was ich so brauche, mag die eine oder andere Lösung besser sein. Und insbesondere, wenn ich meine Zeit berücksichtige, die Strecken zu bauen, also den Algorithmus zu implementieren, dann ist vielleicht ein weniger komplexes Konstrukt, wie ich lauf einfach äh doch schneller, als wenn ich den Zug bauen muss und dann erst fahren kann. Kommt aber sehr drauf an, wenn ich das halt nur für einmal mache, dann ist es vielleicht so. Wenn ich den mehrfach verwende, ist es wieder anders. Also jetzt einfach so ein bisschen im Hinterkopf behalten. Ähm, die guten Algorithmen wollen wir da verwenden, wo sich es lohnt. Und das ist auch Aufwand. und den wollen wir da investieren, wo sich es lohnt. Aber wie fassen wir das jetzt äh ein bisschen konkreter.

1:52 Also, um das sinnvoll äh zu beantworten, müssen wir die die Strecke irgendwie festhalten. Und analog kann ich bei Algorithmen nicht wirklich sagen, ob ein Algorithmus schneller als ein anderer ist, wenn ich die auf irgendwelchen unterschiedlichen Eingaben verglichen habe, dann weiß ich nie so wirklich, ob es jetzt an der Eingabe lag oder am Algorithmus oder an beidem oder wie auch immer. Deswegen werden wir uns versuchen, die Welt ein bisschen einfacher zu machen. Die Annahme dahinter ist immer, es gibt irgendwie Eingaben, also Probleminstanzen, die schwieriger sind als andere. Und in allererster Nährung sind halt manche Eingaben irgendwie größer als andere. Auch das ist wieder allgemein ganz konkret zu fassen bisschen schwierig, aber in jedem jedem Beispiel, das wir uns anschauen, ist eigentlich klar, dass es so eine Art Eingabegröße gibt. Ich möchte nur betonen, das ist nicht Gott gegeben. Oder Eingabegröße ist nicht irgendwas, was es ähm inherent in dem Problem gibt. Wir können das eigentlich fast immer definieren, was das sein soll. Also hier könnten wir sagen, es ist die Gesamtstrecke, die wir fahren.

2:56 Eine eine Option. Ähm, wir hatten ja auch schon Beispiele, wo wir das getan haben, wenn Sie auf die Folien zurückgehen. Da hatte ich das auch schon so so genannt. Wir hatten das Three Sum Problem mit den Zahlen, in den wir Tripel suchen, die sich zu null addieren. Und da war es naheliegend zu sagen, die Anzahl Zahlen der Eingabe ist unsere Eingabegröße. Ich hätte aber auch die Gesamtsumme der Zahlen nehmen können. Warum nicht? stellt sich halt in dem Fall raus, ist eine Quatschin, weil die die teureren Eingaben sind die mit mehr Zahlen und nicht unbedingt die mit größeren Zahlen mit so einem mit so einer kleinen Fußnote dran, auf die ich noch mal zurückkommen werde, äh nach der Pause, denke ich. Äh Union Find hatten wir sogar zwei Dinge, die sinnvoll als Eingabegröße gelten. Sowohl die Anzahlobjekte als auch die Anzahl von Aufrufen.

3:49 Äh wie der Name hier schon andeutet, ist n eher das, was wir als Eingabegröße ähm uns anschauen und dann die Anzahl Operationen. Da werden wir versuchen, eine Operation nach der anderen uns anzuschauen. Aber grundsätzlich kann es auch sein, dass in ein Problem sich mehrere Dinge aufdrängen als Eingabegröße. Mann muss man die irgendwie kombinieren. Das ist mal das eine. Das heißt aber jetzt, wenn ich die Kosten von dem Algorithmus mir anschaue, dann hängen die von dieser Eingabe ab im Allgemeinen und damit auch von dieser Größe. Das ist das, warum wir sie mit Asymptotiken so viel geärgert haben, wo wir immer Funktionen von n haben. Denn in der Regel ist Laufzeit, was wir damit meinen, eine Funktion in Abhängigkeit der Eingabegröße, weil wir immer erwarten müssen, größere Eingaben dauern länger.

4:40 Ein konkretiertes Beispiel hatten wir uns ja damals mühsam hergeleitet. Das war genau die Anzahl dieser zwei Zeilen in der innersten Schleife wurden so oft ausgeführt, wenn wir n Zahlen in der Eingabe hatten für das für diese Brotw Lösung von Sum.

5:03 Selbst das ist aber oft noch unbequem, denn selbst wenn die Größe der Eingabe gleich bleibt, ist bei manchen Algorithmen immer noch sehr unterschiedlich, wie lange der Algorithmus dann braucht. Dafür werden wir noch viele Beispiele sehen. Ähm die bisherigen Beispiele sind so ein bisschen mit Absicht so gewählt gewesen, dass ihn dass dieser Aspekt nicht so wichtig ist, damit sie da nicht äh von der Analyse abgelenkt wurden. aber eher der üblichere Teil, dass das von der Eingabe abhängt. Und die klassische Lösung dafür in der Informatik ist pessimistisch rangehen und sagen, wir nehmen die schlimmstmögliche Eingabe einer Größe. Was wir dann bekommen für unseren Algorithmus ist die Worstcease Performance. Und äh wenn ich also eine Schranke für diese Worst case Performance habe, dann gilt die natürlich für alle weniger schlimmen Eingaben auch. Das heißt, das ist die beste Garantie, die ich geben kann, die allgemeinste Garantie, die ich geben kann. Deshalb ist sie so beliebt, weil sie einfach eine klare obere Grenze für die Kosten liefert.

6:06 Es gibt Alternativen, die manchmal zum Einsatz kommen. Man kann auch optimistisch sein und gucken, ich schaue mal, was im besten Fall passiert. Das ist selten ein guter Ratgeber für die Praxis, aber manchmal ist es ähm ein aufschlussreich, diesen Worst Case und Best Case zu vergleichen, um zu sehen, wie groß ist denn da die Lücke, wenn es denn eine gibt. Und vielleicht am realistischsten oder am pragmatischsten wäre sowas wie einen Average Case. Das heißt, alle Eingaben sind irgendwie möglich und ich hätte gern den durchschnittlichen die durchschnittlichen Kosten oder ich könnte das auch probabilistisch machen. Vielleicht sind nicht alle Eingaben gleich wahrscheinlich. Vielleicht habe ich typische Eingaben und seltene und ich mache so einen Erwartungswert. Kommen wir wieder auf das Stochastikkapitel zurück. Ähm das ist oft das, was ein was einem die genauste Aussage liefert, ist aber auch am schwierigsten zu bekommen, wenn man es analytisch machen möchte. Deswegen werden wir das hier nur in paar gezielten Beispielen uns anschauen, wo es eben sehr weit vom Worst Case weg ist. Aber allgemein ist das relativ schwierig.

7:13 In allen Fällen habe ich dann, obwohl der Algorithmus selbst Datenabhängig ist, die Kosten wieder auf eine einzige Funktion in der Eingabegröße reduziert. Ja, die diese Funktion hat natürlich eine andere Bedeutung in den drei Fällen und wie gesagt in den allen meisten Fällen, wenn wenn nichts explizit da, dann denken Informatiker immer im Worst Case. Das ist der übliche Fall. Das heißt, ich habe eine Funktion, die mir dann den schlimmstmöglichen Fall begrenzt und das ist natürlich dann eine Garantie, die immer gilt.