Vorlesungen Algorithmen und Datenstrukturen (EI) Effiziente Algorithmen und Datenstrukturen I Perlen der Informatik III Proseminar Algorithms for daily life Hauptseminar IT-Security Threats Praktikum Algorithmen-Entwurf Lehrveranstaltungen für Doktoranden

Effiziente Algorithmen und Datenstrukturen I

• Dozent:
  Prof. Dr. Christian Scheideler
• Bereich:
  4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
  Wahlpflichtvorlesung im Gebiet Algorithmen
• Zeit und Ort:
  Dienstag, 8:00-10:00, MI 00.13.009A
  Donnerstag, 08:00-10:00, MI 00.13.009A
• Übung:
  2 SWS Übung zur Vorlesung
  Übungsleitung: Jonas Pfoh
  
• Ankündigungen:
  Die Gesamtnoten der EA Vorlesung sind jetzt über das CAMPUS Tool abrufbar. Die Einsicht der Endterm Klausur findet am Dienstag, den 24. Februar um 14 Uhr im Raum 03.11.018 statt.
• Schein:
  Einen Übungsschein erhält, wer erfolgreich an den Klausuren (Mittel- und Endklausur) teilnimmt.
• Klausuren:
  Mittelklausur: Di, den 9. Dezember 2008, 16:15-18:15 Uhr in CH 21010.
  Klausureinsicht: Mi, 28.01., 14-16 Uhr in 03.11.018.
  Endklausur: Mo, den 9. Februar 2009, 8:30-10:30 Uhr in CH 21010.
  Die Mittelklausur wird die erste Hälfte (Kapitel 1-5) und die Endklausur die zweite Hälfte des Semesters abdecken. Als Hilfsmittel ist nur ein beidseitig handbeschriebenes DIN A4-Blatt erlaubt.
  Wiederholungsklausur: Mo, den 6. April 2009, 16:30-18:30 Uhr, MW 1350
  Die Wiederholungsklausur wird den gesamten Stoff der Vorlesung abdecken. Als Hilfsmittel ist nur ein beidseitig handbeschriebenes DIN A4-Blatt erlaubt.
• Hörerkreis:
  Studierende im Hauptstudium der Informatik
  Studierende mit Nebenfach Informatik
• Voraussetzungen:
  Stoff des Informatik Grundstudiums
• Empfehlenswert für:
  Grundkenntnisse im Bereich Algorithmen
• Inhalt:
  1. Einleitung
     1. Maschinenmodelle
     2. Komplexitätsmaße
     3. Pseudocode
  2. Höhere Datenstrukturen
     1. Priority Queues
     2. Suchstrukturen (Arrays und Bäume)
     3. Wörterbücher (Hashing)
     4. Union-Find-Datenstrukturen
  3. Sortieren und Selektieren
  4. Kürzeste Wege
  5. Minimale Spannbäume
  6. Lineare Algebra
  7. Matchings in Graphen
  8. Netzwerkfluss
  9. Generische Optimierungsverfahren
• Weiterführende bzw. verwandte Vorlesungen:
  Effiziente Algorithmen und Datenstrukturen II
  Internet-Algorithmik
• Folien:
  • Kapitel 0: Organisation und Inhalte (in Powerpoint und pdf, Stand 14.10.).
  • Kapitel 1: Einleitung (in Powerpoint und pdf, Stand 20.10.).
  • Kapitel 2: Priority Queues (in Powerpoint und pdf, Stand 28.10.).
  • Kapitel 3: Suchstrukturen (in Powerpoint und pdf, Stand 11.11.).
  • Kapitel 4: Hashing (in Powerpoint und pdf, Stand 28.11.).
  • Kapitel 5: Sortieren und Selektieren (in Powerpoint und pdf, Stand 28.11.).
  • Kapitel 6: Verschiedenes (in Powerpoint und pdf, Stand 2.12.).
  • Kapitel 7: Graphen (in Powerpoint und pdf, Stand 15.12.).
  • Kapitel 8: Kürzeste Wege (in Powerpoint und pdf, Stand 12.01.).
  • Kapitel 9: Minimale Spannbäume (in Powerpoint und pdf, Stand 19.02.).
  • Kapitel 10: Lineare Algebra (in Powerpoint und pdf, Stand 19.03.).
    Weitere Unterkapitel (aus EA-Skript von Prof. Mayr):
    • 4-Russen-Algorithmus
    • Matrixmultiplikation a la Strassen
    • Transitive Hülle
  • Kapitel 11: Matchings in Graphen (in pdf, aus EA-Skript von Prof. Mayr).
  • Kapitel 12: Approximationsalgorithmen (in Powerpoint und pdf, Stand 03.02.).
• Skript:
  Siehe das (teilweise abweichende) WS 98/99-Skript von Prof. Mayr.
• Programme:
  Das Programm LinearSorting.cpp ist ein Beipsiel dafür, wie man in linearer Zeit sortieren kann.
• Literatur:
  Die Vorlesung folgt in wesentlichen Teilen dem Buch:
  • Michael T. Goodrich, Roberto Tamassia.
    Algorithm Design: Foundations, Analysis, and Internet Examples.
    John Wiley & Sons, Inc., 2002.
  Ergänzendes und vertiefendes Material zur Vorlesung findet sich in:
  • Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, Clifford Stein.
    Introduction to Algorithms.
    2. Auflage, The MIT Press, Cambridge, MA, 2001.
  • Volker Heun.
    Grundlegende Algorithmen: Einführung in den Entwurf und die Analyse effizienter Algorithmen.
    2. Auflage, Vieweg, Braunschweig-Wiesbaden, 2003.
  • Donald E. Knuth.
    The Art of Computer Programming: Fundamental Algorithms.
    3. Auflage, Addison-Wesley, Reading, MA, 1997.
  • Donald E. Knuth.
    The Art of Computer Programming: Sorting and Searching.
    2. Auflage, Addison-Wesley, Reading, MA, 1997.
  • Uwe Schöning.
    Algorithmik.
    Spektrum Akademischer Verlag, Heidelberg, 2001.
  • Robert Sedgewick.
    Algorithmen.
    2. Auflage, Pearson Education, München, 2002.
• Sprechstunde:
  siehe hier