Was ist das hier? In diesem Seminar schauen wir uns gemeinsam die schönsten Algorithmen und Datenstrukturen der Informatik an.
Was muss ich machen? Jede:r Teilnehmer:in sucht sich einen Algo aus und gestaltet eine Seminarsession dazu. Diese sollte aus ca. 40 Minuten Vortrag und ca. 40 Minuten angeleiteter Übung bestehen. Im Anschluss versendet die Vortragende:r eine bis zu 5-seitige Ausarbeitung mit dem Kernstück des Vortrags. Die Themen werden beim ersten Treffen (am 19.4.23) vergeben.
Dabei werdet Ihr von Ben begleitet, der sich mindestens zweimal mit Euch trifft. Einmal, um Inhalt und Konzept des Vortrags zu besprechen und einmal, um Feedback zu einem konkreten Entwurf zu geben.
Was bringt Euch das? Neben dem fachlichen Inhalt, lernt Ihr in diesem Seminar Lesen, Schreiben und Sprechen. Ihr lest wissenschaftliche Literatur, schreibt einen Text, zu dem Ihr Feedback bekommt und haltet einen Fachvortrag. All das sind (nicht nur mit Blick auf eine zukünftige Bachelorarbeit) wichtige Fähigkeiten.
Welche Themen kann ich wählen? Ihr seid in der Auswahl Eures Themas sehr frei. Wir stellen eine Liste an Vorschlägen zur Verfügung, freuen uns aber auch auf Eure Ideen. Hier mal drei Beispiele möglicher Themen:
- Wie finde ich raus, ob eine Zahl eine Primzahl ist? Mit Randomisierung geht das in Polyzeit! (Miller Rabin)
- Raus aus dem lokalen Optimum! Wie überwinde ich die Schwächen der lokalen Suche?
- Was? Noch ein Heap mit O(1) decrease-key‽ Oder: Warum Hollow Heaps so cool sind.
- Über NP-Schwere hinaus: Parametrisierte Algorithmen und Kernelization.
- Wie finde ich mit weniger als 100 Corona-Tests von 100 Personen die drei Infizierten? Oder: Warum Group Testing toll ist.
- Cuckoo Hashing: Warum Hashing wirklich schnell ist.
- Wie kann ich Dir etwas Beweisen ohne Dir etwas über den Beweis zu verraten? Zero Knowledge Proofs sind zentral für die moderne Kryptographie (und wunderschön).
Was muss ich mitbringen? Es gibt keine formellen Voraussetzungen. Der behandelte Stoff aus Mathematik I und II wird erwartet, für manche Themen ist das Wissen aus der Theoretischen Informatik I und ggf. der Theoretischen Informatik II nützlich, für einige auch erforderlich. Weiterhin gibt es ein paar Themen, die ein Grundverständnis von Wahrscheinlichkeitstheorie voraussetzen.
Teilnehmer sollten Freude an abstraktem Denken und Knobeln mitbringen. Zusätzlich sind Teile der Literatur auf Englisch geschrieben und müssen in dieser Sprache auch verstanden werden.
Wie funktioniert die Bewertung? Grundlage der Benotung ist der Vortrag und die geleitete Übung. Eine herausragend gute/schlechte Ausarbeitung kann die Note nachträglich um bis zu einem Notenschritt beeinflussen.
Eine aktive Teilnahme an den Seminarvorträgen (nicht nur des eigenen) wird erwartet.
