AuK

Aus ProgrammingWiki

Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Algorithmen und Komplexität

Selbststudienmaterial

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
9. Dynamisches Programmieren 30.11. George Antoun, Kawa Ramadan, Anass Halime
10. Verzweigen und Beschränken 07.12. Yun Tao Tan, Amini Amir Muhammad Aflah bin
11. Greedy-Algorithmen 14.12. Richard Mrosk, Christopher Hilgner
12. Randomisierte Algorithmen 04.01.21 Pascal Bayer, Tobias Frenzel
13. P-NP-Problem 11.01.21  ??
14. Effiziente Näherungsverfahren 18,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 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 Frank Ehrlich, Ralf Zücker
Grundbegriffe der Graphentheorie 2 V Anna Bremensztul, Maik Geier
Kürzeste Wege in un/bewerteten Graphen Dynamisches Programmieren/Greedy-Algorithmen V Alexander Preuß, Florian Haje
Minimal aufspannende Bäume V Rene Krause , Okyanus Atlas
Matching Probleme V Leonard Mory, Felix Lüpke
Euler-Kreise und -Wege; Postbotenproblem V Kevin Richter, Patrick Schmidt
Hamilton-Kreise und -Wege, TSP, Heuristiken V Falko Gawantka, Jonas Wolff
Färbungsprobleme V, 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 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



Persönliche Werkzeuge