Effiziente Algorithmen und Datenstrukturen
Efficient Algorithms and Data Structures

Modul IN2003

Dieses Modul wird durch Fakultät für Informatik bereitgestellt.

Diese Modulbeschreibung enthält neben den eigentlichen Beschreibungen der Inhalte, Lernergebnisse, Lehr- und Lernmethoden und Prüfungsformen auch Verweise auf die aktuellen Lehrveranstaltungen und Termine für die Modulprüfung in den jeweiligen Abschnitten.

Basisdaten

IN2003 ist ein Semestermodul in Englisch auf Bachelor-Niveau und Master-Niveau das im Wintersemester angeboten wird.

Das Modul ist Bestandteil der folgenden Kataloge in den Studienangeboten der Physik.

  • Allgemeiner Katalog der nichtphysikalischen Wahlfächer
GesamtaufwandPräsenzveranstaltungenUmfang (ECTS)
240 h 90 h 8 CP

Inhalte, Lernergebnisse und Voraussetzungen

Inhalt

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.

Lernergebnisse

Nach der Absolvierung des Moduls sind Studenten 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.

Voraussetzungen

IN0015 Diskrete Strukturen, IN0007 Grundlagen: Algorithmen und Datenstrukturen, IN0018 Diskrete Wahrscheinlichkeitstheorie

Lehrveranstaltungen, Lern- und Lehrmethoden und Literaturhinweise

Lehrveranstaltungen und Termine

ArtSWSTitelDozent(en)Termine
VO 4 Efficient Algorithms and Data Structures (IN2003) Freitag, 10:00–12:00
Montag, 10:00–12:00
TT 2 Efficient Algorithms and Data Structures, Exercise Session (IN2003) Termine in Gruppen

Lern- und Lehrmethoden

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 Studenten durch die Korrektur der Übungsblätter eine individuelle Rückmeldung über ihren Lernerfolg.

Medienformen

Folien, Tafelarbeit, Übungsblätter

Literatur

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.

Modulprüfung

Beschreibung der Prüfungs- und Studienleistungen

Die Prüfungsleistung wird in Form einer Klausur 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.

Wiederholbarkeit

Eine Wiederholungsmöglichkeit wird am Semesterende angeboten.

Aktuell zugeordnete Prüfungstermine

Derzeit sind in TUMonline die folgenden Prüfungstermine angelegt. Bitte beachten Sie neben den oben stehenden allgemeinen Hinweisen auch stets aktuelle Ankündigungen während der Lehrveranstaltungen.

Titel
ZeitOrtInfoAnmeldung
Effiziente Algorithmen und Datenstrukturen I
Mi, 22.2.2017, 15:30 bis 18:30 MW: 1801
101
bis 15.1.2017 (Abmeldung bis 15.2.2017)

Kondensierte Materie

Wenn Atome sich zusammen tun, wird es interessant: Grundlagenforschung an Festkörperelementen, Nanostrukturen und neuen Materialien mit überraschenden Eigenschaften treffen auf innovative Anwendungen.

Kern-, Teilchen-, Astrophysik

Ziel der Forschung ist das Verständnis unserer Welt auf subatomarem Niveau, von den Atomkernen im Zentrum der Atome bis hin zu den elementarsten Bausteinen unserer Welt.

Biophysik

Biologische Systeme, vom Protein bis hin zu lebenden Zellen und deren Verbänden, gehorchen physikalischen Prinzipien. Unser Forschungsbereich Biophysik ist deutschlandweit einer der größten Zusammenschlüsse in diesem Bereich.