Video 6-1: Algorithm Science

0:02 In diesem nächsten Abschnitt, den ich mit einem neuen Begriff Algorithm Science betitelt habe, zu dem ich gleich was sagen werde, greifen wir noch mal auf, was wir an Modellen für die Algorithmenanalyse uns schon angeschaut haben und setzen uns noch mal ein bisschen in in den größeren Kontext, wie wir mit ähm der Performance von Algorithmen umgehen. In der Informatik ist ja immer nicht nur interessant, ob was geht, sondern auch wie schnell oder mit welchen Kosten. Und deswegen ist ganz zentral, dass man eine Methodik hat, um für so eine algorithmische Fragestellung rauszukriegen, wie schnell oder wie gut, mit welchen Kosten kann ich die den lösen oder eine bestimmte Lösung, wie gut ist die denn oder welche von verschiedenen sollte ich nehmen? Ähm, ein Versuch diese diesem dieses Ziel zu umreißen ist diese Definition von Algorithm Science. Da hatten wir in in einer Community eine Weile diskutiert und wir waren mit all den Begriffen, die es so gibt, nicht ganz zufrieden.

1:02 Deswegen haben wir versucht, diesen hier zu prägen. Ähm, sie können dann längere bisschen bisschen philosophisch Met ausgeholt, wenn Sie sowas interessiert, nachlesen auf Robert Setick Website. Äh, der dazu ein bisschen ähm den Kontext auch erläutert. Lassen Sie mich die Definition einmal vorlesen, mit der wir am Ende dann zufrieden waren. Algorithm science ist die Application of the scientific method. Dazu gleich noch ein, zwei Worte. Application of the scientific method for the design and analysis of algorithms developing mathematical models montag characteristics of algorithms inputs formula hypothes relevant study of performance on specific classes of computers and systems running experiments to validate these hypothes and iterating appropriate with the goal of improving performance. Also ein paar Teile davon kennen Sie schon. Wir haben uns schon mathematischmodelle für die Analyse angeschaut. äh ein bisschen systematischer kommen wir da heute auch noch mal zur Analyse selber und ähm wir hatten auch schon ein zweimal Programme laufen lassen und gestoppt, wie lange sie so brauchen. Ähm was wir bisher nicht getan hatten, war das explizit als ein Experiment zu formulieren im Sinne von einer naturwissenschaftlichen Disziplin. Und genau das ist aber eigentlich das passende Framework dafür.

2:29 Was hat's mit dieser Scientific method auf sich? die wissenschaftliche Methode. Ähm, dazu hören wir eine Minute, was von Richard Feineman, bekannter Physiker, der insbesondere auch dafür bekannt ist, recht prägnante, knackige Talks zu geben.

3:04 if we see whatly and computation to nature or we say compared to experiment or experience compare it directly with observation to see if if it works if it disagrees with experiment it's wrong and that simple statement is the key to science it doesn't make a difference how beautiful your guess is it doesn't make a difference how smart you are who made the guess or what his name Okay, der Ton war schrecklich. Ähm, was er sagte ist, wie wie kommen wir mit neuen Naturgesetzen um die Ecke? Wir raten sie. Und dann gab es erstmal Gelächter und dann sagte er, raten sie nicht. So läuft das wirklich. Und wenn man sie geraten hat, dann versucht man die Konsequenzen dieser neuen Gesetze irgendwie vorherzusagen. In der Physik in der Regel ist es eine Formel. Man kann was berechnen und dann macht man ein Experiment und prüft, ob diese dieses neue Gesetz, diese Hypothese den Datenstand hält. Und falls sie das nicht tut, dann ist sie halt einfach falsch, egal wie clever oder schlau oder bekannt jemand ist, der diese Vermutung oder die Theorie aufgestellt hat.

4:27 Soweit so einfach. Äh, das Ganze ist dann natürlich auch irgendwie in ein Kreis. Was mache ich, wenn meine Theorie falsch war? Ich verfeine sie irgendwie. Sie war ja vermutlich nicht komplett falsch, nur nicht ganz wichtig und so weiter und so fort. Was er hier natürlich wunderschön unter den Tisch kehrt in diesem kurzen, wenn es nicht zu den Daten passt, dann ist halt die Theorie falsch. Ist die Frage, ob das Experiment denn äh korrekt durchgeführt wurde, ob es das Richtige prüft, ob die Aussage so ganz crisp 01 ist es ja oft nicht. Das ist eher so ein eine statistische Frage, wie gut passt deine die Theorie zu den Daten und so weiter und so fort. Ähm, all das sind tatsächlich dann praktische Sorgen, die uns auch in unserem Kontext heimsuchen. Experimente für uns sind Algorithmen laufen lassen und messen, was ihre Kosten sind. Und da kann äh wie in allen Experimenten diverse Dinge schiefgehen, die gar nicht damit zu tun haben, dass das, was wir untersuchen, irgendwie falsch oder kaputt oder langsam ist oder unsere Hypothese falsch war, sondern äh die Messung selbst kann einfach methodische Fehler haben und die sind wie auch sonst in der Wissenschaft nicht in den Naturwissenschaften nicht ganz einfach auszuräumen.

5:42 Da werden wir nur so ein bisschen einsteigen, aber äh das ist definitiv was, was ich hier noch anmerken wollte. So wie er das beschreibt, es klingt das super einfach.

5:57 Woher kommt das ähm Interesse in der Informatik? Das ein bisschen die Historie. Ähm Analytical Machine und Charles Babbage sagt ihn fällt i dazu ein anderer Name ein von der bekannten Person, die man mit Informatik assoziiert. Das steht gar nicht auf der Folie, deswegen ist es ähm wichtiger Punkt. Charles Babbage war ein wesentlichen Ada Lovelesses Arbeitgeber.

6:21 Sehr oft als Pionierin der Informatikerinnen gefeiert, als erste Programmiererin. Charles Babish war dieser englische Adlige, der so in seiner Freizeit an Rechenmaschinen getüftelt hat. Und hier gibt's mal so eine, die ähm nachgebaut ist, aber das kann nur ein Teil davon sein. Soweit ich weiß, wurde die komplette Analytic Engine nie gebaut, weil auch nicht ganz alle Details klar waren. Hat das dann am Ende nicht fertig stellen können. Äh der Punkt ist, das ist eine gute Weile her, lange vor Konrad Zuse, der so den als deutscher Pionier den ähm den Preis bekommt für den ersten programmierbaren Computer, den man wirklich bauen konnte und der elektronisch funktioniert. Das hier war rein mechanisch. Na ja, und er sagt, ähm, sobald diese Maschine irgendwo zum Einsatz kommt, wird die Frage aufkommen, wie oft muss ich die Kurbel drehen, bis die Antwort da ist und äh weil ich das Ding programmieren kann. Das ist auch, wenn man das hier in diesem mechanischen Ding nicht so sehen kann, man kann da ähm Programme vorgeben, welche Berechnungsschritte passieren sollen und äh dann ist auch die Frage, welche welchen Algorithmus in unserer heutigen Sprache möchte ich denn da verwenden, damit ich möglichst wenig kurbeln muss? Hm, eine ganz alte Frage, also die die Laufzeit ähm vorher zu sagen. Äh auf den Folien gibt's so ein paar verschiedene Charaktere Stakeholder, die so ein ähm illustrieren sollen, aus welchen Perspektiven man auf dieses ganze Thema gucken kann. Die sind hier abgebildet.

7:54 Ähm und ihre Rolle ist natürlich da noch nicht ausdifferenziert. Das ist noch nicht ganz klar, wo sie vielleicht sich hinbewegen. Äh Programmierer ist hier so ein bisschen synonym mit praktisch äh angewandten Dingen zu verstehen. Und das wäre dann eher Sie kennen vielleicht die Dilbert Comics, das ist halt der Chef, den interessiert nicht so sehr, ob das schöne Algorithmik ist. der will halt, dass sie äh der Cashflow stimmt. Und dann gibt's auch noch die Forscher, die den, na ja, die den Kopf in die Wolke stecken. Ähm schön finde ich hier den Fokus auch ähm könnte man rauszoomen auf die ganze Informatik. Diese Trennung zwischen Programmierer und Theoretiker, die so ein bisschen hier sehr 01 gemalt ist, die gibt's in der ganzen Informatik. Die Informatik ist so eine witzige Mischung aus ähm Ingenieursdisziplinen, die Systeme bauen und Anwendung lösen und Strukturwissenschaftlern, die fast mathematische Fragen eigentlich beantworten oder zumindest Wissenschaft im Sinne der Physik, in der es auch nicht primär darum geht, Anwendung zu schaffen, sondern die Welt zu verstehen, wie sie ist. Und das haben wir in der Informatik unter einem Hut. In der Physik gab es auch mal, aber dann hat sich irgendwann die klassischen Ingenieurs, Wissenschaften äh in in ihren verschiedenen Formen ausgegliedert als ein eigenes Feld und so ein bisschen was von der Physik übrig ist, ist eigentlich alles diese Strukturwissenschaft äh und der Ingenieursteil ist ausgelagert. Das ist in der Informatik bisher nicht passiert. Wir haben noch alles unter einem Hut. Es gibt zwar Software Engineering auf der einen Seite und dann theoretische Informatik auf der anderen Seite ähm auf dem anderen Ende des Spektrums und wir reden miteinander und der Abstand ist gar nicht so groß.

9:36 Aber wir haben das alles so unter einem Hut noch und das merkt man an manchen Themen dann auch, dass äh da so ein gewissen Spannungsbogen gibt. Na gut, äh aus Sicht dieser verschiedenen Charaktere kann man verschiedene Gründe haben, warum man Algorithmen analysieren möchte. Ähm, in der Regel will man wissen, wie lange was braucht. Das ist dieses, wie oft muss ich hier kurbeln, bevor meine Antwort rausfällt. Ich habe in der Regel mehrere Lösungen, die ich vergleichen will. Hat wir alles schon auch äh besprochen. Dann möchte ich wissen, welcher besser ist, wie mache ich das? Ja, wahrscheinlich Asymptotik und so weiter und so fort. Und äh wenn ich eine Anwendung habe, die harte Garantien braucht, wie lange was dauern darf, dann kann mir das meistens nur die so eine theoretische Analyse liefern. Und ähm der Punkt, auf den wir hier nur so am Rande eingehen, der in theoretische Informatik dann vollkommt und ein bisschen in effiziente Algorithmen, ist was kann ich überhaupt machen oder wo gibt's grundsätzliche Grenzen, die irgendwie uns entgegenstehen, Dinge noch besser zu lösen.

10:40 Die pragmatische Lösung ist natürlich, falls Sie am Ende der die Programmiererrolle haben, dann wollen Sie vermeiden, dass erst ganz am Ende irgendwas schiefgeht, weil sie die Algorithmik nicht durchdringen. Und ähm schön finde ich diesen Begriff von Performance Bug. Wir alle kennen Bugs, wenn irgendwas schief geht und das Ergebnis falsch ist. Aber ein Performance Bug ist eben was, wenn das System, das sie bauen, nicht geeignet ist, schnell genug zu sein, um eine Aufgabe zu lösen, also vielleicht den Durchsatz nicht erreicht, den sie brauchen, dann ist es fast so schlimm wie falsches Ergebnis, denn am Ende ist es auch nicht effektiv.

11:21 In der Regel stellen wir uns diese Fragen. Äh, ist mein Programm zu langsam oder warum ist das so? Und wenn es äh nicht genug Speicher kriegt, wie wie passiert das? Und in der Informatik, wie in anderen Naturwissenschaften, sage ich mal jetzt einfach so, als sei Informatik auch eine äh können wir die wissenschaftliche Methode verwenden, um diese Fragen zu bearbeiten, vielleicht zu klären.

11:46 Hier noch mal ähm bisschen strukturierter, was man unter wissenschaftlicher Methode in Naturwissenschaft versteht. Das ist dieser dieser Kreis, den wir auch vorhin schon angesprochen hatten. Ähm die Philosophie der Wissenschaft ist ist an der Stelle jetzt nicht so ähm entscheidend für uns. Das wird oft in den konkreten Beispielen klar sein. Ähm wenn man Hypothesen formuliert und die wissenschaftlich sein sollen, dann müssen die immer konkret und falsifizierbar sein. Wenn Sie mögen, können Sie dieses Feineman Video geht noch länger und da führt er das auch noch schön aus mit knackigen Pseudocience Beispielen. Äh führt uns jetzt hier zu weit. Wenn wenn Sie eine Hypothese formulieren, die zu schwammig und zu weich ist, als dass man sie widerlegen kann, dann ist sie nicht nur wenig hilfreich, sondern unwissenschaftlich.

12:39 Und ähm im im Kontext von Algorithmen ist das manchmal so ein Problem mit der O-Notation. Wenn Sie mit einem Experiment widerlegen wollen, dass ein Algorithmus in groß O von N Laufzeit hat, dann haben Sie das Problem, dass das groß O ja beliebig große Konstanten erlaubt. Das heißt, egal wie ihre Daten ausgehen, sie können damit eigentlich so eine groß Notation nie widerlegen. Das ist der Grund, warum hier in dem Kapitel viel Fokus gelegt werden wird auf diese Tildenotation, die eine konkrete Konstante beinhaltet. Die gibt i nämlich eine konkrete Zahl. ist auch immer noch, es ist immer noch asymptotisch. Das heißt, man hat immer noch den Grenzprozess äh, den man irgendwie berücksichtigen muss, aber man bekommt zumindest eine konkrete Vorhersage, die man mit den Daten vergleichen kann. Und dann kann man äh versuchen, sich plausibel zu machen. Ist das nah genug dran für die Eingabegrößen oder ist das widerlegt widerlegen die Daten meine Hypothese?