Video 5-1: Grundbegriffe der Algorithmik

0:02 Im nächsten Abschnitt schauen wir uns Maschinen und Maschinenmodelle an und bisschen was diese Begriffmodelle in unserem Kontext heißen soll. Wir werden auch noch mal ganz kurz darüber reden, was überhaupt Algorithmen sind. Das hatte ich bisher auch tunlichst vermieden, da allzu sehr ähm mich festzulegen. Und noch ein Stückchen weiter ausgeholt, worum geht's in der Vorlesung global gesehen? Also einerseits Universitätsstudiengang soll wissenschaftlich fundiert sein. Insbesondere sind wir nicht ein reiner angewandter Studiengang. Wir hätten also gerne weniger davon und mehr ähm Verständnis in diesem Sinne. Ähm ich lese den Comic einmal vor, damit Sie äh mitnehmen können, worum es da gehen soll. Und ich sag dann gleich noch was dazu. The world is so complicated. The more I learn, the less clear anything gets. There are too many ideas and arguments to pick and choose from. How can I trust myself to know the truth about anything? And if everything I know is so shaky, how on earth what on earth am I doing teaching?

1:14 I guess you just do your best. No one can impart perfect universal truths to their students [räuspern] except math teachers. Thank you. Also Kontext ist ein bisschen nichts hält für die Ewigkeit, außer die Mathematik, wenn man das so äh zuspitzen möchte. Insbesondere im Kontext der Informatik und Algorithmik gibt es Dinge oder ähm Lösungen, die sind sehr speziell an eine aktuelle Technik oder Technologie geknüpft und die sollen sie auch beherrschen, die lernen Sie in praktischen Anwendungen, aber sie sollen auch dahinter blicken und wissen haben, dass ein bisschen längere halt halbwertszeit hat als das nächste JavaScript Framework.

1:59 Und äh dafür ist ein Ausflug Richtung Mathematik nötig. Dafür dafür ist es nötig, dass man Dinge ein wenig abstrahiert. Umgekehrt, wenn man den Schritt geschafft hat, ähm sind auch manche schnellbigen Änderungen nicht mehr ganz so ähm atemraubend und ähm wir hoffen, dass ähnliches auch mit der KI irgendwann sich einrüttelt. In der Algorithmik gibt's diesen Basissatz an Lösung auf einem Abstraktionsniveau, der sich bewährt hat schon eine einige Weile. Insofern haben wir da äh etwas leichteres Spiel.

2:41 Was bedeutet das also für uns? Äh, Universal Truths kann man natürlich verschieden interpretieren, aber was wir hier drunter verstehen wollen, sind eben diese äh Basisblöcke der Algorithmik, die sich bewährt haben, die über die Zeit auch gleich geblieben sind in dem Level äh, auf dem wir sie anschauen und die eben auch beweisbar Dinge liefern.

3:02 Das heißt, anders als wir das teilweise auch tun werden, den Code implementieren und laufen lassen reicht nicht immer aus, wenn der Maßstab äh diese Universal Truths sein sollen, sondern wir modellieren, was in der Realität oder in den Rechnern passiert auf einem etwas höheren Abstraktionsniveau und dafür hoffentlich ähm etwas, was die die Zeit besser überdauert. Wir wollen immer noch quantitative Vorhersagen machen. Ich werde gleich dann mehr dazu sagen, was das in dem Kontext heißen soll. und Experimente, also echten Code laufen lassen, tun wir trotzdem, brauchen wir trotzdem, aber eben als Validierung von einem Modell, in dem wir dann qualifizierte Aussagen machen können und nicht nur als das einzige, was gilt. Dementsprechend müssen wir über alle Aspekte, die wir in dem Kontext haben, Algorithmen und Eingaben und Maschinen, kurz nachdenken, wie können wir das abstrahieren von konkretem Gerät, das vor uns liegt. Das wollen wir hier tun. Und sie werden sehen, das ist gar nicht so abstrakt, wie es aus wie es ähm auf den ersten Blick klingt.

4:07 Bevor wir zu den Modellen kommen, auch noch mal ein paar Takte zu dem Begriff Algorithmus selbst. Äh, das Bild, was Sie da sehen, soll andeuten, dass auf erste Ernährung ein Algorithmus ein Berechnungsrezept ist, also eine Schritt für Schritt Anweisung, wie man etwas äh berechnet und ein bisschen konkreter, ein bisschen genauer, wissenschaftlicher, wenn Sie mögen, sind das drei Bedingungen. Die erste ist, es muss so beschrieben sein, diese Berechnung, die wir da ausführen, dass sie mechanisch nachvollziehbar oder ausführbar ist. Hier steht nicht ausführbar, sondern nachvollziehbar, weil es uns theoretisch reichen mag, dass äh man mechanisch interpretieren kann, was da zu tun ist, ohne dass es eine konkrete Maschine wirklich tun kann. Also eine Beschreibung für einen Algorithmus muss keine Programmiersprache verwenden, aber es muss eben eineindeutig sein und äh nicht sich ihr auf irgendwelche anderen Kontexte verlassen.

5:08 Ähm wir hätten auch gerne eine endliche Beschreibung, also wie auch immer das ähm die Beschreibung genausht, das Programm, sage ich mal, äh es muss endlich lang sein. Es darf nicht eine beliebige Fall underscheidung haben. Das sagen Sie ist ist offensichtlich. Ich kann ja nicht unendlichen Text tippen, wenn ich ein Java Programm schreibe. Wenn man Algorithmen sich ausdenkt, kommt man aber manchmal in den Punkt, dass man dann gibt's so ein paar verschiedene Fälle und dann ähm in jedem Fall weiß ich schon, was ich tun muss. Wenn das aber dann unendlich viele verschiedene Fälle sind, dann gilt das nicht. Dann ist das kein Algorithmus. passiert schneller, als man vielleicht so denken würde. Das heißt natürlich nicht, dass ein Algorithmus immer endlich lange rechnet. Also auch eine ganz kleine unendliche Weilschleife kann ja äh nie terminieren. Und der dritte Punkt, jetzt wird's ein bisschen schwammig, leider. Ähm, wir hätten gerne, dass ein Algorithmus nicht nur ein konkretes Programm ist, das vielleicht ein bestimmtes Problem löst, sondern eine ähm ganze in Klasse von Problemen. Also z.B. als einfachstes äh algorithmisches Problem die Addition von zwei Zahlen.

6:20 Was wir nicht als Algorithmus ansehen würden, ist ein Programm, das nur für zwei bestimmte Eingaben funktioniert. Das ist in dem Beispiel, glaube ich, klar und intuitiv vielleicht oft auch, aber das kann man nicht so gut formalisieren. Also, das ist ein Teil, der mathematisch gesehen Waage bleiben muss, weil wir uns sonst äh hier sehr lang verlieren, was das jetzt genau heißt, eine Problemklasse. Wann wann ist eine Problemklasse allgemein genug, dass wir das gelten lassen?

6:51 Für mechanisch nachvollziehbar äh ist erstmal okay, dass wir einfach sagen, ein Java Programm ist sowas, das kann ja ein Rechner ausführen, also es ist eindeutig beschrieben und damit auch mechanisch nachvollziehbar.

7:06 Trotzdem ist für uns ein Algorithmus oft eher eine eine Menge von Programmen oder eine etwas abstraktere Idee, die man auf verschiedene Art in Programme umsetzen könnte. Wir sagen dann auch, es gibt einen Algorithmus und mehrere Implementierungen.

7:20 Also als Beispiel, falls Sie den schon kennen, dann gut, wenn nicht, ist nicht so wichtig. Kommen wir noch zu äh ein Assortieralgorithmus Bubbelsort, der im Wesentlichen darauf beruht, wann immer ich zwei Elemente habe, die nebeneinander sind und in der falschen Reihenfolge sind, dann tausche ich die beiden. Das ist die Essenz von Bubbles, aber sie können sich jetzt diverse verschiedene Ideen ausdenken, wie das in Java Code genau aussieht. Irgendwie möchten wir darüber reden, dass das alles Bubblesort artige Programme sind, aber das können wir erst recht nicht konkret fassen. Das ist eine wage Sache. Also Algorithmus ist in erster Nährung ein Programm, das ähm allgemein ein Problem löst, nicht nur einen ganz konkreten Wert. Ähm wir hätten gerne aber, dass es auch abstrakter bedeutet, dass es ein Lösungsansatz, ein konkreter Lösungsansatz für ein algorithmisches Problem.

8:16 werden sie in Beispielen immer wieder sehen, dass es nicht so schwierig ist, die die Trennlinie dazuz ziehen, aber wir müssen uns an der Stelle Waage belassen. Die drei Punkte sind dagegen wichtig und das ist ähm Klassiker auch in der theoretischen Informatik. Das sind die Bedingungen für eine Berechnung, die wir äh möchten.

8:34 Der Name kommt übrigens von Alchwarismi, der letztlich ein Buch über Algebra geschrieben hat, auch nach ihm benannt, mehr oder weniger, äh in der er Berechnungsvorschriften für klassische Rechenoperationen beschrieben hat. Deswegen möchte ich immer auch gerne hier noch mal dran erinnern, sie haben alle schon in der Grundschule Algorithmen ausgeführt, auch wenn ihn niemand den Begriff genannt hat oder wenn man das nicht so verstanden hat, aber alles schriftliche addieren, schriftliches Multiplizieren, DVDen, all diese Rechenoperationen, die man dann Stelle für Stelle oder Ziffer für Ziffer ausführt, sind klassische Algorithmen. Ja, die haben wir halt ähm manuell ausgeführt, statt sie zu programmieren. Aber dem Algorithmus linkens hier steht was von Maschine. Ja, das ist äh mechanisch nachvollziehbar. Heißt einfach nur ohne Nachdenken kann auch ein Mensch machen.

9:32 Der zweite Begriff, mit dem ich schon so um mich geworfen habe, ist eine Datenstruktur. Was meinen wir eigentlich damit? Eine Definition, die ich so gewund habe, war organisierte Art Daten zu speichern und nutzbar zu machen. Das ist auch noch relativ schwammig. Äh, ich möchte es ein bisschen konkreter machen. Ähm, auf der einen Seite soll der Datenstruktur ein eine Menge von Operationen haben, ein Interface oder eine API, wie es auch in dem Speakbuch immer genannt wird. Also Dinge, die ich tun können möchte und äh die beschreiben mir, was passieren soll, aber nicht wie das passieren soll. Beispiel war unser Union Find Daten Datentyp soll diese Union Operation geben und die Feindoperation und ich beschreibe was dann das Ergebnis ist, aber ich sage noch nichts darüber wie das umgesetzt wird. Äh in der Welt etwas klassischer in der Welt Algorithmik nennt man das einen abstrakten Datentyp Abstract Data Type oder ADT. Das ist also eine Beschreibung von den Operationen und der Bedeutung. Sie können das ungefähr gleichsetzen mit einem Java Interface, aber es ist eben inklusive einer konkreten Beschreibung, was die Operation leisten sollen. Streng genommen ist ein Java Interface ja nur die Signatur der Methoden und ich kann vielleicht noch Kommentar Java Doc dazu schreiben, aber das ist nichts, was der Compiler anschaut.

11:03 Ähm für uns die Abstract Data Types sind für Menschen. Die beschreiben für Menschen, was passieren soll. Das heißt, die dürfen erstmal noch ein bisschen informeller sein.

11:15 Das also das eine, aber eine Datenstruktur selber ist dann eine Implementierung von so einem abstrakten Datentyp. Und dafür brauche ich zwei Dinge. Ich muss einerseits sagen, wie werden denn die Daten, die Operationen generieren, wie werden die gespeichert? Denken Sie wieder an unser Union Find Beispiel. Ich habe da diese Objekte schon von Anfang an, aber ich kann dann Union und Feind aufrufen, da passiert was und ich muss mir merken, was passiert ist, sonst kann ich die Queries nicht verab die ähm Feindabfragen nicht beantworten. In der Regel, das ist das typische, dass man das tut, indem man gewisse Invarianten formuliert. Also Bedingungen, die immer gelten sollen zwischen Operationen. Wenn eine neue Operation kommt, dann macht die diese Invariante temporär kaputt und wir müssen sie wiederherstellen. Das ist eine Art, wie wir oft für für Menschen oder für für Programmierer kompakt beschreiben können, was diese diese Regeln für die Daten ausmacht, aber es ist äh nicht der einzig mögliche Weg. Und das zweite ist, wir brauchen einen Algorithmus für jede Operation, der uns dann sagt, wie diese ausgeführt wird. Und das verwendet natürlich wie die Daten gespeichert werden. Man kann zu zusätzliche Eingaben haben.

12:38 Also jede Datenstruktur hat so einen abstrakten Datentyp im Hinterkopf. Der muss nicht immer einen festen Namen haben, aber ich glaube, die Beispiele, die wir so haben, da ist das immer der Fall.

12:47 Das hier ist eigentlich der Kern der Datenstruktur. Also eine Regel, wie wir Daten speichern und Algorithmen für die Operation. Ja, jedes Beispiel hatten wir ja mehrere gesehen. Quick Union ist ein Quick Find und die gewichteten Quick Find hatten wir Quick Union. hat wir ausführlich diskutiert. Äh ich hatte schon erwähnt, Algorithmen haben nicht unbedingt was mit Computern zu tun, gibt's schon viel länger. Ähm Elizgorithmus für den größten gemeinsamen Teiler kennen Sie bestimmt. Äh wenn nicht, dann lesen Sie es nach. Ist für uns jetzt nicht besonders relevant, aber ist natürlich ein Algorithmus, den man als Informatiker kennen sollte. Äh hier ist der Code dazu. Der ist unfassbar kompakt, weil es diese Modulo Operation in Java direkt gibt und man das rekursiv formulieren kann.

13:55 Der wurde natürlich verwendet lang bevor es Computer gab, aber funktioniert im Wesentlichen noch genauso. Also die Beschreibung, die man die man dafür verwendet für Menschen und für die Maschine ist sehr ähnlich. Na, etwas moderneres Beispiel, immer noch ähm nicht ganz äh jung, aber das ist ja genau der Punkt. Ähm Merchsort werden wir noch genauer sehen, was sich dahinter verbirgt. Hatte ich auch schon mal zu gefragt. ähm wurde beschrieben. Man könnte sagen, bevor es so richtig Computer gab, gerade so in der Anfangszeit. Definitiv waren das, was man damals so an Computern hatte, weit weit weg von dem, was wir heute verwenden. Gerade so noch ähnliche Architekturprinzipien, aber da ist schon eine Riesenlücke. Trotzdem ist der Algorithmus in dem in der Sprache, in der das so beschrieben wurde, im Wesentlichen gleich geblieben. Also all diese ähm Rechen, Rechen, Rechen Jahre dazwischen, 80 Jahre dazwischen haben nicht so richtig viel an diesem Algorithmus ändern müssen, obwohl sich alle Programmiersprachen, alle Hardware drunter massiv geändert hat. Und hier brauchen wir gar nicht drüber reden, da ist äh höchstens vielleicht noch der gleiche Sand, der jetzt im Silizium ist, äh vergleichbar.

15:18 Dementsprechend ähm stellt sich die Frage, wie wie würde man den Algorithmen so beschreiben, dass es wie diese zwei Beispiele klappt, dass die Kernidee, die da zur Lösung führt, auch noch in 10 Jahren nützlich ist und äh was man dafür, also ist eine schwierige Frage, auf die ich keine endgültige Antwort habe, sollte ich vielleicht direkt sagen. Es gibt verschiedene sinnvolle Möglichkeiten. Was definitiv eine doof Möglichkeit ist, ist sich zu sehr an konkrete Technologie zu fesseln, insbesondere wenn die nicht offen ist, sass man nicht ohne weiteres aus der wieder rauskommt. Das ist nicht mehr so ein richtig schlimmes Ding, aber es gab Programmiersprachen, die proprietär sind, wo niemand so richtig Einfluss drüber hatte, wie die sich weiterentwickeln und manch von denen gibt's dann auch nicht mehr. Vielleicht ist das ähm dann der Zahn der Zeit. Aber wenn sie Algorithmen in diesen Sprachen beschrieben hätten, dann ist es unpraktisch. Java hat diese Probleme im Wesentlichen nicht. Die Frage, die Sprache wird relativ offen weiterentwickelt.

16:19 Das war mal proprietäres Gut von Sun Microsystems, aber ist es nicht mehr. Open JDK, die Referenzimplementierung ist wesentlich ein Open Source. die groß äh allergrößte Teil, der Kern von Java sowieso die ganze Bibliothek können Sie den Quellcode nachlesen. Klingt erstmal so, als wäre das halbwegs ähm zukunftssicher und gibt's auch schon lang genug, dass sozusagen die Kinderkrankheiten ausgeräumt sind. Äh trotzdem habe ich so ein bisschen ähm Schmerzen, wenn wir allgemein immer gleichsetzen würden. Ein Algorithmus ist einfach ein Java Programm und was anderes brauche ich nicht. Äh abgesehen davon, dass natürlich immer ähm Grabenkämpfe in der Informatik gibt, was die beste Programmiersprache ist und da ja auch immer weiter Sprachen hinzukommen. Ähm gibt's zwei Gründe, warum warum das nicht immer eine gute Lösung ist. Äh, der Grund eins ist, manchmal würden wir gerne ein Algorithmus etwas abstrakter beschreiben, als es diese Sprache zulässt oder Details offen lassen, was in der Programmiersprache eigentlich nicht geht. Ich muss jede Funktion implementieren, bevor ich ein Programm laufen lassen kann.

17:30 Und damit habe ich mich für eine konkrete Implementierung für diese Methode entschieden. Und dann kann ich natürlich einen Kommentar hinschreiben und sagen, ja, da könnte man auch dies oder jenes machen, aber ein festes Java Programm ist immer eine feste Konvention, eine feste Entscheidung, wie wir das implementieren. Und manchmal ist das unbequem. So eine Krücke, um da rauszukommen, wäre zu sagen, wir implementieren gegen ein Interface. Also, wir rufen Methoden von dem Interface auf und sagen, jede mögliche, jede gültige Implementierung für dieses Interface würde auch für unseren Algorithmus funktionieren. Das ist ganz okay. Ähm, verlässt dann aber so ein bisschen auch die Javprache. Das Ding, was ich dann geschrieben habe, kann ich nicht ausführen, bevor ich nicht ähm das Interface irgendwie mal zumindest mit einer Stap Implementierung auch bereitstelle. Ähm, der zweite Punkt ist so ein bisschen subtiler, vielleicht und dazu komme ich noch ein bisschen mehr im Laufe äh des nächsten Abschnitts.

18:34 Die konkreten Programmiersprachen, die wir haben, spiegeln immer in gewisser Weise Restriktionen wieder der Hardware, die wir haben. Und in gewisser Weise sollen sie das auch, weil sie auch im praktischen Einsatz sind. Und für den praktischen Einsatz sind eben die Performance auf konkreten Maschinen das was sie was zählt. Und dann gibt's im Detail, wenn man schaut, wie man Dinge implementiert, immer Tradeoffs zu machen. Wie allgemein mache ich was oder wie sehr nutze ich die konkreten Features einer bestimmten Architektur? Hier sind so ein paar Beispiele, die sind jetzt nicht super relevant für Sie zu wissen, aber falls Sie konkrete Beispiele wollen, um Sie zu überzeugen, dass Java nicht unbegrenzt ist, äh dann sind das hier welche. Ich kann z.B. will nicht wirklich beliebig lange Arrays haben. 2 31 klingt jetzt erstmal viel, aber das sind ähm Umrechner ich mir aufschreiben sollen. Also sie kennen ja die Rechnung, wir machen das zusammen. 2 hoch 10 sind der 1000 etwa und das habe ich etwa dreimal.

19:38 Das heißt, das ist ein seh noch neun, das sind Gigabyte etwa, also so ein paar Gigabyte Einträge in einem Array, das kann man schon mal haben wollen. Äh ist ein bisschen mehr noch, weil das ja die Anzahl Einträge ist, nicht wirklich den Speicherplatz und man kann sich natürlich dann noch mit Krücken bemühen, aber das sind schon Größenordnungen, die manchmal nerven können. Theoretisch, aber hat man sich in in Java dazu eben entschieden, einfach um den den Tradeoff an der Stelle zu haben, dass für die ganzen Anwendungen, die nicht noch größere Arrays brauchen, der Zugriff ein bisschen schneller wird. Den zweiten Teil will ich gar nicht genau erklären, was dahinter verbirgt. Das heißt einfach, dass theoretisch eine Methode nicht beliebig lang sein kann, nicht beliebig viel Code haben kann und wir reden nicht über unendlich, sondern es gibt eine feste Größe. Könnte man natürlich einfach eine Untermethode aufrufen und dann ist das Problem wahrscheinlich gelöst.

20:43 Fazit für mich ist also so ein bisschen äh trotz all dieser Anwende werden wir doch meistens Java Code verwenden, einfach weil es eine kompakte Version ist, die algorithmische Idee zu beschreiben und man sich oft mit so ein paar Kniffen ähm der Unbequemlichkeiten entledigen kann. Sie sollten aber den Code, den wir verwenden, verstehen als jenseits von Java selbst mit diesen hardgecodeten Grenzen, z.B. für Array Größen, die denken wir uns mal einfach weg. Also, ich möchte auch in unserem Code keine ähm Features verwenden, die irgendwie z.B. darauf aufbauen, dass dass das diese Obergrenze ist. werden vielleicht ein bisschen mal äh noch mal im Sortierkapitel darauf zurückkommen. Ähm wir wir werden also vermeiden, diese Grenzen, die es in echtem Java gibt, irgendwie auszunutzen und wir werden so tun, als gäb es die nicht, damit unser Algorithmus für die Ewigkeit beschrieben ist. Und wenn man eine neue Sprache schreiben würde, die so aussieht wie Java, die aber diese Grenzen hier aufhebt, wie auch immer sie das dann tut, dann sollten unsere Algorithmen immer noch genauso funktionieren.

21:53 So, die Idee.