Loading
     

Modulbeschreibung - Detailansicht

Wichtigste Meldungen anzeigenMeldungsfenster schließen
Moduldetails
Effiziente Algorithmen und Datenstrukturen
Fakultät für Informatik
TUINFIN
8
1
6
IN2003
Zuordnungen zu SPO-Versionen
Lehrveranstaltungen und Prüfungsveranstaltungen
Beschreibungen
15W
Export
Allgemeine Daten (Modulhandbuch)
Bachelor/Master
Einsemestrig
Wintersemester
Englisch
Arbeitsaufwand (Work Load)
240
90
150
Studien- und Prüfungsleistungen
Die Prüfungsleistung wird in Form einer Klausur von 150 Minuten erbracht. In dieser weisen Studierende anhand der gestellten Aufgaben nach, dass sie die begrifflichen und mathematischen Grundlagen der Algorithmenanalyse beherrschen. Ferner zeigen die Studierenden, dass sie über fundamentale und weitergehende Kenntnisse im Bereich der effizienten Datenstrukturen und Algorithmen verfügen. Sie weisen nach, dass sie in begrenzter Zeit typische algorithmische Probleme erkennen und analysieren können sowie Wege zu einer Lösung finden.
N
J
Beschreibung
IN0015 Diskrete Strukturen, IN0007 Grundlagen: Algorithmen und Datenstrukturen, IN0018 Diskrete Wahrscheinlichkeitstheorie
Nach der Absolvierung des Moduls sind Studierende in der Lage, die Laufzeit und den Speicherplatzbedarf von Algorithmen zu analysieren und zu bewerten. Darüber hinaus verfügen sie über ein grundlegendes Verständnis für die Arbeitsweise zahlreicher fundamentaler Algorithmen und Datenstrukturen. Dieses Verständnis versetzt sie in die Lage, für neue Probleme selbständig Algorithmen und Datenstrukturen zu entwickeln.
Das Modul behandelt zunächst die Grundlagen der Algorithmenanalyse. Anschließend werden fundamentale Datenstrukturen und grundlegende algorithmische Probleme behandelt.
Im Bereich der Grundlagen der Algorithmenanalyse studiert das Modul verschiedene Maschinenmodelle, Komplexitätsmaße sowie das Lösen von Rekursionsgleichungen.
Auf dem Gebiet der fundamentalen Datenstrukturen stellt das Modul verschiedene Suchbäume, Hash-Verfahren, Prioritätswarteschlangen und Union-Find-Datenstrukturen vor.
Im Bereich der grundlegenden Algorithmen konzentriert sich das Modul auf die Entwicklung von zahlreichen Maxflow- und Mincutalgorithmen sowie auf Algorithmen für das Matching-Problem.
Das Modul besteht aus einer Vorlesung und einer begleitenden Übung. Die Inhalte der Vorlesung werden im Vortrag und durch Präsentation vermittelt. Studierende werden insbesondere durch die Lösung von Übungsblättern zur inhaltlichen Auseinandersetzung mit den Themen angeregt. Die Lösung der Übungsaufgaben wird in der Übungsveranstaltung besprochen. Zusätzlich erhalten die Studierende durch die Korrektur der Übungsblätter eine individuelle Rückmeldung über ihren Lernerfolg.
Folien, Tafelarbeit, Übungsblätter
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, Clifford Stein: Introduction to Algorithms. McGraw-Hill, 1990.
Michael T. Goodrich, Roberto Tamassia: Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, 2002.
Volker Heun: Grundlegende Algorithmen: Einführung in den Entwurf und die Analyse effizienter Algorithmen, 2. Auflage, Vieweg, 2003.
Jon Kleinberg, Eva Tardos: Algorithm Design. Addison-Wesley, 2005.
Donald E. Knuth: The Art of Computer Programming. Vol. 1: Fundamental Algorithms. 3. Auflage, Addison-Wesley, 1997.
Donald E. Knuth: The Art of Computer Programming. Vol. 3: Sorting and Searching. 3. Auflage, Addison-Wesley, 1997.
Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization: Algorithms and Complexity. Prentice Hall, 1982.
Uwe Schöning: Algorithmik. Spektrum Akademischer Verlag, 2001.
Steven S. Skiena: The Algorithm Design Manual. Springer, 1998.
Modulverantwortliche*r
Susanne Albers, Prof. Dr. (susanne.albers@tum.de)