AuK

Aus ProgrammingWiki
Archivierte Version vom 2020-12-14T06:58:10+00:00. Aktuelle Version

Inhaltsverzeichnis

Algorithmen und Komplexität

Selbststudienmaterial

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 Halime
10. Verzweigen und Beschränken07.12.Yun Tao Tan, Amini Amir Muhammad Aflah bin
11. Greedy-Algorithmen14.12.Richard Mrosk, Christopher Hilgner
12. Randomisierte Algorithmen04.01.21Pascal Bayer, Tobias Frenzel
13. P-NP-Problem11.01.21Wagenknecht
14. Effiziente Näherungsverfahren18.01.21??

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