Proseminar / L3-Seminar (BaM-PS)

Kombinatorik und Computer

Sommersemester 2021

Prof. Raman Sanyal, Aenne Benjes

Aktuelles

Die Vorbesprechung zum Proseminar findet am Dienstag, 9. März 2021 um 14:00 per ZOOM statt. Den ZOOM-Link erhalten Sie per Email. Schicken Sie dazu eine Email an die richtige Permutation von S N A Y L A und @math.uni-frankfurt.de

Was

In diesem Proseminar wollen wir Themen aus der Vorlesung Computerorientierte Mathematik vertiefen und die kombinatorischen Aspekte dabei näher betrachten. Unter anderen wollen wir uns mit folgenden Themenkomplexen befassen:

Wie enumeriert man Teilmengen (fester Größe), Permutationen, ...?
Wir haben einfache (rekursive) Algorithmen kennengelernt um Teilmengen und Permutationen aufzuzählen aber diese Algorithmen haben den Nachteil, dass sie alle Teilmengen/Permutationen auf einmal erzeugen und das sind i.A. zu viele! Wie kann man Teilmengen, Permutationen und andere kombinatorische Objekte nach und nach erzeugen? Was, wenn sich zwei aufeinander folgende Objekte so wenig wie möglich unterscheiden sollen?
Wie arbeitet man mit Suchbäumen?
Wie löscht man einen Knoten und erhält die Suchbaum-Eigenschaft? Wie fügt man Elemente ein, so dass der neue Baum weiterhin (annährend) balanciert ist? Man muss dabei geschickt Teilbäume ``umpflanzen''.
Wie findet man ``kürzeste'' Wege in Graphen?
Gegeben ein Graph bei dem jeder Kante eine Länge zugeordnet ist. Wie findet man einen längen-minimalen Weg zwischen zwei Knoten? Wie findet man längen-minimale Wege zwischen allen Paaren von Knoten?
Gibt es Probleme/Aufgaben, die nicht in polynomieller Zeit lösbar sind?
Wir werden sehen, dass es für kürzeste Wege-Problem einen polynomialen Algorithmus gibt aber wie sieht es aus, wenn wir zB den längsten Weg in einem Graphen suchen? Aus dieser Frage lässt sich eine sehr natürliche und interessante Kategorisierung von algorithmischen (Entscheidungs)Problemen ableiten, die zu der zentralen Frage P vs. NP führt.

Voraussetzungen für die Teilnahme sind die Vorlesungen aus dem ersten Semester (Analysis 1, Lineare Algebra 1, Einführung in die computeror. Math.). Als Quellen werden uns u.a. die folgenden Bücher und Artikel dienen:

Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, MIT Press 2009
Wilf, Combinatorial Algorithms: An update, CBMS 1989
Knuth, The art of computer programming, Volume 4A, combinatorial algorithms, O'Reilly 2011
Pruesse, Ruskey, Generating linear extensions fast 1994

Link zum Vorlesungsverzeichnis.

Wann und wo

Mittwochs, 14:15-15:45, virtuell (ZOOM-Link auf Anfrage)

Organisation / Spielregeln

Ziel eines Proseminars ist Ihre Fähigkeiten mathematische Themen eigenständig zu erarbeiten, aufzubereiten und durch Vortrag und Ausarbeitung zu vermitteln weiterzuentwickeln. Dazu haben wir interessante, relevante und z.T. akutelle Themen ausgewählt, die Ihren mathematischen Horizont erweitern.

Das Proseminar ist unbenotet; Erfolgreiche Teilnahme am Proseminar setzt sich aus eigenständiger Arbeit, verständlichem Vortrag und Ausarbeitung und Teilnahme an allen Vorträgen zusammen. Sollten Sie an einem Vortrag nicht teilnehmen können, dann informieren Sie uns frühzeitig.
Anmeldung (mit Thema) erfolgt in der Vorbesprechung; siehe oben.
Im Vorfeld zum Vortrag geben wir gerne und reichlich Hilfestellung und Feedback. Ein sehr lesenswerter Artikel zu Wie halte ich einen Seminarvortrag? findet sich hier.
Es gibt mindestens zwei Treffen vor dem Vortrag.
Bei dem ersten Treffen sprechen wir über Inhalt und Probleme und einigen uns auf die Schwerpunkte Ihres Themas.
Bei dem zweiten Treffen (spätestens zwei Wochen vor dem Votragstermin) sprechen wir über Inhalt und Ablauf des Vortrags. Dazu sollten Sie eine Gliederung/Handout (ca. 2 Seiten) mitbringen. Das Handout ist dann für die anderen Teilnehmer*innen gedacht.
Die Vorträge sind ca. 70 Minuten lang, damit Zeit für Fragen und Diskussionen bleibt. Situationsbedingt werden die Vorträge als Folienvorträge (LaTeX-Beamer) oder handschriftlich mit Graphiktablet/Tablet+Pen gehalten. Bei Fragen sprechen Sie uns gerne an.
Innerhalb von drei Wochen nach dem Vortrag sollte eine Ausarbeitung (LaTeX, 6-8 Seiten) abgegeben werden. Darin wird, aufbauend auf der Vortragsgliederung, das Thema dargestellt. Die finalen Ausarbeitungen werden dann mit allen Teilnehmern des Proseminars geteilt. Eine LaTeX-Vorlage stellen wir zur Verfügung.

Themen und vorläufige Termine

Die folgende Tabelle gibt einen Überblick über die angebotenen Themen, Inhalte und zugeordnete Termine.

Termin Vortrag/Inhalt Quelle Vortragende

21.4.21 Heap-Sort
Halden (heaps), Heap-Sort, Vorrangwarteschlange (priority queues) [C, Chapter 6] Christoph N.

28.4.21 Quicksort
Strategie, best-, worst- und average-case Laufzeiten [C, Chapter 7] Nele D.

5.5.21 Operationen auf binären und balancierten Bäumen
Löschen aus Suchbäumen, Einfügen in balancierte Bäume, erwartete Höhe von zufälligen binären Bäumen [C, Chapter 12] Sonja L.

12.5.21 Rot-Schwarz Bäume
inkl. AVL-Bäume (Exercise 13-3) [C, Chapter 13] Johannes W.

19.5.21 Minimum Spanning Trees
[C, Chapter 23] Dennis M.

26.5.21 Single-Source Shortest Paths
[C, Chapter 24.1-3] Jonas G.

9.6.21 All-pairs shortest paths
[C, Chapter 25] Alexander D.

16.6.21 NP-Vollständigkeit, Teil 1
[C, Chapter 34] Amadeus W.

23.6.21 NP-Vollständigkeit, Teil 2
[C, Chapter 34] Simon W.

7.7.21 Erzeugen von Tupeln und Teilmengen
Lexikographische Erzeugung von Tupeln und Teilmengen (fester Größe); Kombinatorische Gray Codes [K, Chapter 7.2.1.1], [W, Ch.1+2 Arne G.

Impressum Datenschutzerklärung

Termin	Vortrag/Inhalt	Quelle	Vortragende
21.4.21	Heap-Sort Halden (heaps), Heap-Sort, Vorrangwarteschlange (priority queues)	[C, Chapter 6]	Christoph N.
28.4.21	Quicksort Strategie, best-, worst- und average-case Laufzeiten	[C, Chapter 7]	Nele D.
5.5.21	Operationen auf binären und balancierten Bäumen Löschen aus Suchbäumen, Einfügen in balancierte Bäume, erwartete Höhe von zufälligen binären Bäumen	[C, Chapter 12]	Sonja L.
12.5.21	Rot-Schwarz Bäume inkl. AVL-Bäume (Exercise 13-3)	[C, Chapter 13]	Johannes W.
19.5.21	Minimum Spanning Trees	[C, Chapter 23]	Dennis M.
26.5.21	Single-Source Shortest Paths	[C, Chapter 24.1-3]	Jonas G.
9.6.21	All-pairs shortest paths	[C, Chapter 25]	Alexander D.
16.6.21	NP-Vollständigkeit, Teil 1	[C, Chapter 34]	Amadeus W.
23.6.21	NP-Vollständigkeit, Teil 2	[C, Chapter 34]	Simon W.
7.7.21	Erzeugen von Tupeln und Teilmengen Lexikographische Erzeugung von Tupeln und Teilmengen (fester Größe); Kombinatorische Gray Codes	[K, Chapter 7.2.1.1], [W, Ch.1+2	Arne G.