AuK

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Algorithmen und Komplexität 1.1 Prüfungen !!! 1.2 Selbststudienmaterial 1.3 WS 21/22: Wahl der Vortragsthemen 1.4 SS 09, SS 10, SS 11, SS 12, WS 13/14, WS 14/15 1.5 WS 15/16: Vorträge - je eine Vorlesung und eine Übung (180 min.) 1.5.1 Hinweis zur Behandlung von Algorithmen im Vortrag 1.6 WS 15/16: Vorträge - je 90 min. (innerhalb der V- und Ü-Zeit) 1.6.1 Literatur 1.7 WS 20/21: Wahl der Vortragsthemen

Algorithmen und Komplexität

Prüfungen !!!

Termine

Schwerpunkte

Selbststudienmaterial

• ProgrammingWiki-Version. (Pflichtliteratur für WS 21/22)
• Jupiter Notebooks
• Wagenknecht, Chr.: Algorithmen und Komplexität

WS 21/22: Wahl der Vortragsthemen

Thema	Termin	Bearbeiter/in (jeweils so viele Personen, wie ?)	Präsentation (Link auf gehaltenes Referat)
1. Asymptotische Aufwandsordnungen	15.10.21	Wagenknecht	-
2. Empirische Analyse, Regression und Lösung von Rekurrenzgleichungen	22.10.21	Wagenknecht	-
3. Abstrakte Datentypen (ADT)	29.10.21	Kevin Cebulla, Al Hwrani Mohammad	Abstrakte Datentypen Präsentation
4. Amortisierte Analyse	12.11.21	Nicolas Käseberg	Amortisierte Analyse
5. Graphen	12.11.21	Nicolas Käseberg	Graphen
6. Bäume	19.11.21	Karol Piasecki	Bäume
7. Hashing und Hash Tables	26.11.21	Anton Kießling	Hashing, Übung
8. Teile und Herrsche	03.11.21	Tom Lauber	Divide and Conquer, Übung
9. Dynamisches Programmieren	10.12.21	Samuel Raak	Dynamische Programmierung
10. Verzweigen und Beschränken	17.12.21	Moritz Michael	-
11. Greedy-Algorithmen	07.01.21	Hatim El Asri	Greedy-Algorithmen
12. Randomisierte Algorithmen	14.01.22	Ferris Antony Grabinski	-
13. P-NP-Problem	21.01.22	Stefanie Schaarmann, Dennis Abbe	P-NP-Problem
14. Effiziente Näherungsverfahren	28.01.22	Denis Ceylan	-

Hinweis: Bitte seid fair und unterlasst es die Namen derjenigen, die sich bereits eingetragen haben, zu entfernen oder zu ersetzen. Ein "?" steht für einen Namen. Tragt ihr euch also ein, so löscht ihr dementsprechend ein Fragezeichen. Viele Themen sind sehr umfangreich und sollten deshalb nicht alleine bearbeitet werden.

Terminfestlegung Eine Woche vor Behandlung des Themas sollten die Vortragenden fest stehen, allerspätestens muss dies jedoch am Freitag der Fall sein. Nichtsdestotrotz sollten alle Teilnehmer/innen zu jedem Thema ausreichend vorbereitet sein, um notfalls den Vortrag halten zu können. Bereitet die Vorträge also am besten mit einem festen Partner bzw. mehreren festen Partnern (diejenigen, mit denen ihr auch euren Vortrag regulär halten würdet) für die nächsten Stunden vor.

SS 09, SS 10, SS 11, SS 12, WS 13/14, WS 14/15

Thema (SS 09-11; WS 14/15) SS 09 SS 10 SS 11 WS 13/14 Verantwortlich (WS 14/15) Thema (SS 12) SS 12 WS 13/14 Verantwortlich (WS 13/14) Einführung X X X X CW Motivation X X Effizienz von Algorithmen X X X X CW Einführung X X Hilfsmittel Mathematik 1 X X X X CW Felder und Listen X X Hilfsmittel Mathematik 2 X X X X CW Hash Tables und Assoziative Listen X X J. Klinger, D. Franke Teile und Herrsche 1 X X X X X Sortieren und Suchen X X Dana Müller/Robert Stricker Teile und Herrsche 2 X X X X -- Prioritätswarteschlangen X X Oliver Krüger / Maciej Krzan Systematische Suche X X X X -- Sortierte Folgen X X D. Bitterlich / A. Häse Verzweigen und beschränken X X X X X Graphrepräsentationen X X J. Hilsberg/H. Kretschmer Dynamisches Programmieren X X X X X Durchläufe durch Graphen X X S. Feuerriegel, D. Soldan Greedy-Algorithmen X X X X X Kürzeste Wege X X Andre Krause, Roman Stange Probabilistische Algorithmen X X X X X Minimaler Spannbaum X X A.Danker / D.Richter P-NP-Problem X X X X X Algorithmische Entwurfsmuster X X Näherungsverfahren 1 X X X X -- String matching X X Y. Oliynyk Näherungsverfahren 2 X X X X -- Maximale Flüsse X X Y. Oliynyk WS 15/16: Vorträge - je eine Vorlesung und eine Übung (180 min.) Bewertung: 60%, alles im Programming Wiki, kein Extrabeleg Thema (Graphentheorie) Passendes Thema (AuK, CW) Bearbeiter/in -- Effizienz von Alg. I CW -- Effizienz von Alg. II CW -- Mathematische Hilfsmittel CW Grundbegriffe der Graphentheorie 1 Effizienz von Alg. III V CÜ Frank Ehrlich, Ralf Zücker Grundbegriffe der Graphentheorie 2 V CÜ Anna Bremensztul, Maik Geier Kürzeste Wege in un/bewerteten Graphen Dynamisches Programmieren/Greedy-Algorithmen V CÜ Alexander Preuß, Florian Haje Minimal aufspannende Bäume V CÜ Rene Krause , Okyanus Atlas Matching Probleme V CÜ Leonard Mory, Felix Lüpke Euler-Kreise und -Wege; Postbotenproblem V CÜ Kevin Richter, Patrick Schmidt Hamilton-Kreise und -Wege, TSP, Heuristiken V CÜ Falko Gawantka, Jonas Wolff Färbungsprobleme V, CÜ Erik Bothe, Lars Eichhorn Hinweis zur Behandlung von Algorithmen im Vortrag Mathematische Beschreibung Effizienzbetrachtung (theoretisch) Implementierung in einer PS, die vom Programming Wiki unterstützt wird Empirische Effizienzanalyse WS 15/16: Vorträge - je 90 min. (innerhalb der V- und Ü-Zeit) Bewertung: 40%, alles im Programming Wiki, kein Extrabeleg Thema (Alg. Entwurfsmuster) Bearbeiter/in Teile und Herrsche Anna Bremensztul, Kevin Richter, Patrick Schmidt Verzweigen und Begrenzen Rene Krause, Okyanus Atlas, Felix Lüpke Greedyalgorithmen und -heuristiken Florian Haje, Erik Bothe, Maik Geier Dynamisches Programmieren Alexander Preuß, Frank Ehrlich, Leonard Mory P-NP-Problem und Näherungsverfahren Ralf Zücker, Falko Gawantka, Jonas Wolff Probabilistische Algorithmen Lars Eichhorn Literatur Wagenknecht, Chr.: Algorithmen und Komplexität Krischke; Röpcke: Graphen und Netzwerktheorie WS 20/21: Wahl der Vortragsthemen Thema Termin Bearbeiter/in (jeweils so viele Personen, wie ?) Präsentation 1. Asymptotische Aufwandsordnungen 12.10. Justin Salzburg, Marvin Schütz Asymptotische Aufwandsordnungen 2. Empirische Analyse, Regression und Lösung von Rekurrenzgleichungen 19.10. CW (ausnahmsweise) - 3. Abstrakte Datentypen (ADT) 26.10. Liam Landmann, Jonas Schied, Jenny Zeuler Abstrakte Datentypen 4. Amortisierte Analyse zum späteren Termin  ?? 5. Graphen 02.11. Kristina Solbrig, Tim Döring, Max Scholz Graphen 6. Bäume 09.11. Kim Pauligk, Marvin Schütz (für Jawael Rezaei) 7. Hashing und Hash Tables 16.11. Maximilian-Felix Helm, Amadeus Kincl Hashing und Hash Tables 8. Teile und Herrsche 23.11. Pascal Hönisch, Anna Schenk Teile und Herrsche 9. Dynamisches Programmieren 30.11. George Antoun, Kawa Ramadan, Anass Halime Anass_Dynamic_Programming.pdf (0.6 MB) 10. Verzweigen und Beschränken 07.12. Yun Tao Tan, Amini Amir Muhammad Aflah bin Verzweigen und Beschränken 11. Greedy-Algorithmen 14.12. Richard Mrosk, Christopher Hilgner Greedy-Algorithmen 12. Randomisierte Algorithmen 04.01.21 Pascal Bayer, Tobias Frenzel Randomisierte Algorithmen 13. P-NP-Problem 11.01.21 Wagenknecht Wagenkn_P-NP-Problem-populaer.pptx.zip (0.8 MB) 14. Effiziente Näherungsverfahren 18.01.21 Eric Gesemann Approximationsalgorithmen.pdf (0.1 MB)