Video 12-3: Übersicht Lehre der AG Algorithmik

0:02 Für den Rest von heute würde ich gerne einmal kurz andere Module beleuchten, die sie noch äh be uns in der AG machen können. Das ist, was wir aktuell getan haben, Algorithmen und Datenstrukturen. Und Sie sehen da so ein bisschen habe ich für mich selbst strukturiert die einzelnen Abschnitte, die kennen Sie ja. Woll wir also nicht noch mal im Detail reingehen. Äh rausgezoomt gibt's im im Bachelor Kernbereich dann eben noch effiziente Algorithmen. Hatte ich ja vielfach schon erwähnt. Wenn Sie ein bisschen genauer gucken wollen, was da so äh auf Sie zukommt, dann können Sie das hier machen. Und dann gibt's noch aktuell drei äh Schwerpunkt Vertiefungsveranstaltung.

0:40 einmal äh Advanced Algorithms, die sind dann noch auf Englisch in aller Regel, weil die auch im Master angeboten werden. Ähm, da schauen wir uns an, ah, wir hatten wir hatten gar nicht mehr über P und NP gesprochen. Ähm, dafür dafür ist mir sozusagen die Zeit ausgegangen. Das ist auch nicht Teil vom Prüfungsstoff für die Vorlesung. Ich hätte es aber, wenn wir noch ein ein Slot extra gehabt haben, äh kurz erwähnt, worum es da geht. ähm ist als Informatiker wichtig zu wissen. Die Kerninformatiker machen das sowieso in der theoretischen Informatik im Detail. Äh für Data Science kann man sich durch das Studium ähm buchieren, ohne das zu machen. Und da hätte ich dann ähm hier ein bisschen was mehr dazu gesagt. Darum geht's in der Vorlesung noch mehr im Detail. Also die Frage von die da im Raum steht ist, wenn ich ein algorithmisches Problem habe, das irgendwie schwierig aussieht, klassiker so Traveling Salesman Problem für die, die es äh Traveling Sales Person Problem für die, die das kennen. Äh da gibt's keinen Algorithmus, der irgendwie effizient in der Praxis funktioniert aus theoretischer Sicht, worst case Laufzeit. Ähm und dafür scheint es theoretisch fundierte gute Gründe zu geben, weil das Problem entw vollständig ist.

1:55 Jetzt kann man ähm einerseits diese Theorie ein bisschen untersuchen. Was heißt das und für welche Probleme kann man das zeigen? Und man kann aber auch nach Auswegen suchen. Wenn ein Problem NP vollständig ist, dann heißt es eine ganz präzise negative Aussage oder eine schlechte Nachricht. Man kann die aber aufweichen an verschiedenen Stellen. Man kann randomisieren, man kann nicht nur den Worst case angucken, man kann approximieren, alles Optionen, die dann auch in der Praxis relevant sind. und die Theorie dahinter, darum geht's eben fortgeschrittene Algorithmik.

2:29 Das zweite Modul ist Algorithmen der Bioinformatik. Da gibt's äh jede Menge Algorithmen, die aus der Biologie motiviert sind. oder Bioinformatik, sollte ich präziser sagen, wie Sie auch hier im Hintergrund sehen, ist im Wesentlichen die Analyse von Sequenzdaten, also Genomen, äh anderen anderen biologischen Sequenzen, Proteinen, all diese Dinge sind am Ende Textdaten, Strings, witzigerweise.

2:57 Ähm und dafür gibt es eine Reihe von etwas eigenartigen Fragestellungen, die aber aus der Biologie eben Sinn ergeben. Meistens ist es irgendwelche schwammigen suchen. Ich will kein exaktes Vorkommen von meinen Mustern, sondern so eine so ein ungefähres Vorkommen. Und dafür gibt's spannende Algorithmen. Und diese Algorithmen schauen wir uns da an. Es ist ein kein Bioinformatikmodul, indem wir ins Labor gehen, sondern wir schauen uns die Informatikmethoden dahinter an.

3:27 Und dann ähm parallel zu dieser Vorlesung, dieses Semester auch gelaufen äh fortgeschrittene Datenstrukturen. Das ist mehr oder minder die direkte Fortsetzung von den anderen beiden Veranstaltungen, wo wir noch mal noch mal tiefer einsteigen. Diese ganzen Arten von Dingen, wie wir sie hier auch besprochen hatten, Union Finddatenstrukturen und Suchbäume und Hashing und noch mehr äh kann man noch einiges ähm vertiefen und verfeinern und verbessern. Das ist Ziel von diesem Modul. Äh, auch da ist der Fokus auf den theoretisch besten, asymptotisch besten Verfahren mit ein bisschen in Auge auch auf äh was in der Praxis funktioniert.