Entwurf und Analyse von Algorithmen (EAA)

3VU MAT.356UF WS19/20

(Hinweis: Andere Formen (VU, UE) dieser LV werden nicht mehr angeboten. Bezüglich möglicher Anrechnungen konsultieren Sie bitte die Dekanatshomepage oder wenden Sie sich bitte an Ihren Studiendekan.)

Diese Seite enthält Informationen und Materialien für die Lehrveranstaltung Entwurf und Analyse von Algorithmen. Weitere Informationen (z.B. LV-Termine, Zuordnung zu Studien) sind auf der offiziellen TUGOnline Seite der Lehrveranstaltung zu finden.

Lehrveranstaltungsthemen

Hier wird ein Überblick über die behandelten Inhalte entstehen. Weiteres Material wird im Laufe des Semesters hinzugefügt.

• Kurzvortrag erste Einheit

• Zusatzinformationen erste Einheit

• Kapitel 01: Einführung

• Kapitel 02: Rekursionsgleichungen: zusätzliches Material in [1, Kapitel 4.3-4.5]

• Kapitel 03: Dynamisches Programmieren; 04: Optimale Triangulierung

• Kapitel 04: Slides Minimum Weight Triangulation

• Kapitel 05: Slides Randomisierter Suchbaum

• Kapitel 06: Slides Convex Hulls (Intro, Jarvis' Wrap, Graham Scan)

• Kapitel 06: Konvexe Hüllen (Graham Scan, Iteratives Einfügen)

• Kapitel 07: Einfache Graphenalgorithmen

• Kapitel 08: Minimale Spannbäume

• Kapitel 09: Kürzeste Wege in Graphen

• Kapitel 10: Komplexitätstheorie

Übungsblätter

Weiteres Material wird im Laufe des Semesters hinzugefügt.

• Zusatzinformationen zu den Übungsblättern

• Übungsblatt 0: Selbsteinschätzung (wird nicht beurteilt)

• Übungsblatt 1: Asymptotische Notation. Fragestunde: Fr 25.10.2019, 12:00, Seminarraum IST (IC02062). Einsichtnahme: Fr 8.11.2019, 14:00-15:30, Seminarraum IST (IC02062).

• Übungsblatt 2: Konvexe Hüllen.

• Zusatzübungsblatt: Schneebälle. Abgabe optional.

• Übungsblatt 3: Graphenalgorithmen. Fragestunde: Do 16.1.2020, 15:00, Besprechungsraum IST (IC02074). Einsichtnahme: Di 11.02.2019, 16:00-17:00, Seminarraum IST (IC02062).

Teilklausuren

Die Termine wurden auch in der ersten LV-Einheit bekanntgegeben, siehe auch Zusatzinformationen erste Einheit.

• TK1: 18.11.2019 13:00-16:00 in 3 Gruppen, HS i13. Stoff bis inklusive LV am 11.11.2019. Fragestunde vor der TK: Freitag 15.11.2019, 13:30-14:30, Seminarraum IST, Einsichtnahme: Fr 08.12.2019, 13:00, Seminarraum IST (IC02062), Inffeldgasse 16b, 2.Stock.
  • Familienname A-J: 13:10
  • Familienname K-R: 14:00
  • Familienname S-Z: 14:50

• TK2: 27.01.2020 13:00-16:00 HS i13. Stoff bis inklusive LV am 20.01.2020. Fragestunde vor der TK: Freitag 24.1.2020, 16:00-17:00, Seminarraum IGI (IC01074)
  • Familienname PUC-ZIN: 13:10
  • Familienname HIE-PRO: 14:00
  • Familienname ABD-HER: 14:50

Die Punkte der Übungen und Teilklausuren werden via TUGOnline als Teilergebnisse des Prüfungstermines aus MAT356UF mit Termin 31.01.2020 00:00 bekanntgegeben.

Zusätzliches Material

• Webseite mit einigen animierten Algorithmen

Derzeit werden die animierten Algorithmen im Rahmen von Studentenprojekten neu implementiert.

Empfohlene Fachliteratur

• Algorithmen allgemein:
  • [1] Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, MIT Press London, 1990 (Second Edition 2001, Third Edition 2009; Titel deutsche Version: Algorithmen, eine Einführung)
  • [2] Sedgewick: Algorithms, Addison-Wesley.

• Geometrie:
  • [3] de Berg, Cheong, van Kreveld , and Overmars. Computational Geometry. Algorithms and Applications (third edition). Springer, Berlin, 2008.
  • [4] Aichholzer, Jüttler: Einführung in die angewandte Geometrie, Birkhäuser.

• Komplexität:
  • [5] Garey, Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness, Freeman and Company.

-- OswinAichholzer - 23 Sep 2019