AuK

Aus ProgrammingWiki
Archivierte Version vom 2021-10-08T09:56:40+00:00. Aktuelle Version

Inhaltsverzeichnis

Algorithmen und Komplexität

Selbststudienmaterial

WS 21/22: Wahl der Vortragsthemen

ThemaTerminBearbeiter/in (jeweils so viele Personen, wie ?)Präsentation
1. Asymptotische Aufwandsordnungen11.10.21Wagenknecht-
2. Empirische Analyse, Regression und Lösung von Rekurrenzgleichungen18.10.21-
3. Abstrakte Datentypen (ADT)25.10.21Kevin Cebulla, Al Hwrani Mohammad-
4. Amortisierte Analyse01.11.21-
5. Graphen08.11.21Lucas Sommer-
6. Bäume15.11.21Karol Piasecki-
7. Hashing und Hash Tables22.11.21Anton Kießling-
8. Teile und Herrsche29.11.21Tom Lauber-
9. Dynamisches Programmieren06.12.21Samuel Raak-
10. Verzweigen und Beschränken13.12.21Moritz Michael-
11. Greedy-Algorithmen10.01.21Hatim El Asri-
12. Randomisierte Algorithmen17.01.22Ferris Antony Grabinski-
13. P-NP-Problem24.01.22Stefanie Schaarmann, Dennis Abbe-
14. Effiziente Näherungsverfahren31.01.22Denis 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 09SS 10SS 11WS 13/14Verantwortlich (WS 14/15)Thema (SS 12)SS 12WS 13/14Verantwortlich (WS 13/14)
EinführungXXXXCWMotivationXX
Effizienz von AlgorithmenXXXXCWEinführungXX
Hilfsmittel Mathematik 1XXXXCWFelder und ListenXX
Hilfsmittel Mathematik 2XXXXCWHash Tables und Assoziative ListenXXJ. Klinger, D. Franke
Teile und Herrsche 1XXXXXSortieren und SuchenXXDana Müller/Robert Stricker
Teile und Herrsche 2XXXX--PrioritätswarteschlangenXXOliver Krüger / Maciej Krzan
Systematische SucheXXXX--Sortierte FolgenXXD. Bitterlich / A. Häse
Verzweigen und beschränkenXXXXXGraphrepräsentationenXXJ. Hilsberg/H. Kretschmer
Dynamisches ProgrammierenXXXXXDurchläufe durch GraphenXXS. Feuerriegel, D. Soldan
Greedy-AlgorithmenXXXXXKürzeste WegeXXAndre Krause, Roman Stange
Probabilistische AlgorithmenXXXXXMinimaler SpannbaumXXA.Danker / D.Richter
P-NP-ProblemXXXXXAlgorithmische EntwurfsmusterXX
Näherungsverfahren 1XXXX--String matchingXXY. Oliynyk
Näherungsverfahren 2XXXX--Maximale FlüsseXXY. 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. ICW
--Effizienz von Alg. IICW
--Mathematische HilfsmittelCW
Grundbegriffe der Graphentheorie 1Effizienz von Alg. III V CÜFrank Ehrlich, Ralf Zücker
Grundbegriffe der Graphentheorie 2V CÜAnna Bremensztul, Maik Geier
Kürzeste Wege in un/bewerteten GraphenDynamisches 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, HeuristikenV CÜFalko Gawantka, Jonas Wolff
Färbungsprobleme V, CÜErik Bothe, Lars Eichhorn

Hinweis zur Behandlung von Algorithmen im Vortrag

  1. Mathematische Beschreibung
  2. Effizienzbetrachtung (theoretisch)
  3. Implementierung in einer PS, die vom Programming Wiki unterstützt wird
  4. 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 HerrscheAnna Bremensztul, Kevin Richter, Patrick Schmidt
Verzweigen und BegrenzenRene Krause, Okyanus Atlas, Felix Lüpke
Greedyalgorithmen und -heuristikenFlorian Haje, Erik Bothe, Maik Geier
Dynamisches ProgrammierenAlexander Preuß, Frank Ehrlich, Leonard Mory
P-NP-Problem und NäherungsverfahrenRalf Zücker, Falko Gawantka, Jonas Wolff
Probabilistische AlgorithmenLars Eichhorn

Literatur

Wagenknecht, Chr.: Algorithmen und Komplexität

Krischke; Röpcke: Graphen und Netzwerktheorie


WS 20/21: Wahl der Vortragsthemen

ThemaTerminBearbeiter/in (jeweils so viele Personen, wie ?)Präsentation
1. Asymptotische Aufwandsordnungen12.10.Justin Salzburg, Marvin SchützAsymptotische Aufwandsordnungen
2. Empirische Analyse, Regression und Lösung von Rekurrenzgleichungen19.10.CW (ausnahmsweise)-
3. Abstrakte Datentypen (ADT)26.10.Liam Landmann, Jonas Schied, Jenny ZeulerAbstrakte Datentypen
4. Amortisierte Analysezum späteren Termin??
5. Graphen02.11.Kristina Solbrig, Tim Döring, Max ScholzGraphen
6. Bäume09.11.Kim Pauligk, Marvin Schütz (für Jawael Rezaei)
7. Hashing und Hash Tables16.11.Maximilian-Felix Helm, Amadeus KinclHashing und Hash Tables
8. Teile und Herrsche23.11.Pascal Hönisch, Anna SchenkTeile und Herrsche
9. Dynamisches Programmieren30.11.George Antoun, Kawa Ramadan, Anass HalimeAnass_Dynamic_Programming.pdf
10. Verzweigen und Beschränken07.12.Yun Tao Tan, Amini Amir Muhammad Aflah binVerzweigen und Beschränken
11. Greedy-Algorithmen14.12.Richard Mrosk, Christopher HilgnerGreedy-Algorithmen
12. Randomisierte Algorithmen04.01.21Pascal Bayer, Tobias FrenzelRandomisierte Algorithmen
13. P-NP-Problem11.01.21WagenknechtWagenkn_P-NP-Problem-populaer.pptx.zip
14. Effiziente Näherungsverfahren18.01.21Eric GesemannApproximationsalgorithmen.pdf