Technische Universität Ilmenau

Algorithms and Data Structures - Modultafeln of TU Ilmenau

The Modultafeln have a pure informational character. The legally binding information can be found in the corresponding Studienplan and Modulhandbuch, which are served on the pages of the course offers. Please also pay attention to this legal advice (german only).
Information on the room and time of planned courses can be found in the e-calendar of events. Courses and examinations that are not listed in the e-calendar of events are planned "by appointment". A list of the events concerned can be found here: courses, examinations.

subject properties Algorithms and Data Structures in major Bachelor Informatik 2013
subject number100576
examination number220369
departmentDepartment of Computer Science and Automation
ID of group 2242 (Group for Complexity Theory and Efficient Algorithms)
subject leaderProf. Dr. Martin Dietzfelbinger
term Sommersemester
languageDeutsch
credit points8
on-campus program (h)79
self-study (h)161
Obligationobligatory
examexamination performance with multiple performances, 150 minutes
details of the certificate

schriftliche Prüfungsleistung 150 min; zusätzlich muss ein Paktikum als unbenotete Studienleistung erbracht werden

Signup details for alternative examinations
maximum number of participants
previous knowledge and experience

Algorithmen und Programmierung, Grundlagen und Diskrete Strukturen, Mathematik für Informatiker 1

learning outcome

Fachkompetenz: Die Studierenden kennen die Grundprinzipien des Algorithmenentwurfs und der Korrektheits- und Zeitanalyse von Algorithmen und Datenstrukturen. Die Studierenden kennen ein Verfahren für die Spezifikation von Datentypen und können dieses auf Beispiele anwenden. Sie kennen die O-Notation und ihre Regeln und können sie bei der Laufzeitanalyse benutzen. Die Studierenden kennen grundlegende Datenstrukturen über Spezifikation und Implementierungs­möglichkeiten und können die zentralen Perfomanzparameter benennen und begründen. Sie kennen fortgeschrittenere Datentypen wie  „binärer Suchbaum“ und Details der Implementierung als balancierter Suchbaum. Die Studierenden kennen das Prinzip und das Verhalten von einfachen Hashverfahren und können das zu erwartende Verhalten für die verschiedenen Verfahren beschreiben. Sie kennen Konstruktionen einfacher randomisierter Hashklassen und zugehörige Beweise.  Die Studierenden kennen die grundlegenden Sortieralgorithmen (Quicksort, Heapsort, Mergesort sowie Radixsort), können die Korrektheit der Verfahren begründen und ihre Laufzeit berechnen. Sie kennen die untere Schranke für vergleichsbasierte Sortierverfahren sowie den grundlegenden Datentyp  „Priority Queue“ und seine Implementierung auf der Basis von binären Heaps. Die Studierenden kennen die Grundbegriffe der Graphentheorie, soweit sie algorithmisch relevant sind, und können mit ihnen umgehen. Sie kennen die wesentlichen Datenstrukturen für die Darstellung von Graphen und Digraphen mit den zugehörigen Methoden und Performanzparametern.

Sie kennen Entwurfsprinzipien für Algorithmen (Divide-and-Conquer, Greedy, Dynamische Programmierung) und die zugehörigen Analyseverfahren und können sie in einfachen Fällen zum Algorithmenentwurf einsetzen. Sie kennen spezielle Divide-and -Conquer-Algorithmen und können das „Master-Theorem“ zur Analyse einsetzen. Sie kennen die Verfahren „Breitensuche“ und „Tiefensuche“, und können die Situationen identifizieren, in denen diese Verfahren benutzt werden müssen. Sie kennen weitere Anwendungen der Tiefensuche (Kantenklassifizierung, Kreisfreiheit, topologische Sortierung, starke Zusammenhangskomponenten) mit Korrektheits­beweisen. Die Studierenden kennen Algorithmen für die Berechnung kürzester Wege (Dijkstra, Bellman/Ford) mit ihren Anwendbarkeitsbereichen und den Korrektheitsbeweisen. Sie kennen die Datenstruktur „adressierbare Priority Queue“ mit Implementierungs- und Anwendungsmöglichkeiten). Sie kennen weiter Algorithmen für die Berechnung eines minimalen Spannbaums (mit Korrektheitsbeweisen) und der dafür nötigen Union-Find-Datenstruktur. Sie kennen Algorithmen für das „All-pairs-Shortest-Paths“-Problem auf der Basis des Prinzips „Dynamische Programmierung“, sowie weitere Beispiele für die Anwendung dieses Prinzips.   

Methodenkompetenz: Die Studierenden beherrschen Techniken zur Beschreibung von einfachen Systemen (Datentypen) und Verfahren (Algorithmen) sowie zur Beschreibung des Laufzeitverhaltens (O-Notation). Sie verstehen den Sinn von Korrektheitsbeweisen und beherrschen die grundlegenden Techniken für solche Beweise und für Laufzeitanalysen. Sie verstehen die Bedeutung der Effizienz bei der Implementierung von Algorithmen und Datenstrukturen.

content

Spezifikation von Berechnungsproblemen und von abstrakten Datentypen.

Analyse von Algorithmen: Korrektheitsbeweise für iterative und rekursive Verfahren, Laufzeitbegriff, O-Notation, Laufzeitanalyse.

Methoden für die Analyse von Laufzeit und Korrektheit.

Grundlegende Datenstrukturen (Listen, Stacks, Queues, Bäume).

Binäre Suchbäume, Mehrwegsuchbäume, balancierte Suchbäume  (AVL- und/oder Rot-Schwarz-Bäume, B-Bäume).

Einfache Hashverfahren, universelles Hashing.

Sortierverfahren: Quicksort, Heapsort, Mergesort, Radixsort. Untere Schranke für Sortieren.

Priority Queues mit der Implementierung als Binärheaps.

Divide-and-Conquer: Multiplikation ganzer Zahlen    Matrixmultiplikation, Master-Theorem,

Quickselect, Schnelle Fourier-Transformation

Grundbegriffe der Graphentheorie,

Datenstrukturen für Graphen (Adjazenzmatrix, Kantenliste, Adjazenzlisten, Adjazenzarrays). Durchmustern von Graphen: Breitensuche, Tiefensuche, Zusammenhangskomponenten, Entdecken von Kreisen,

topologische Sortierung, starke Zusammenhangskomponenten.

Greedy-Strategie: Teilbares Rucksackproblem,     Schedulingprobleme, Huffman-Kodierung, Kürzeste Wege 1: Algorithmus von Dijkstra, Minimale Spannbäume (Algorithmus von Kruskal, Union-Find), Algorithmus von Prim, randomisierter Algorithmus für minimale Schnitte.

Dynamische Programmierung: Editierdistanz,

Ganzzahliges Rucksackproblem (mit/ohne Wiederholungen), Kürzeste Wege 2: Algorithmus von Floyd-Warshall, Kürzeste Wege 3: Algorithmus von Bellman-Ford, das Problem des Handlungsreisenden.

media of instruction

Folienprojektion, Folien auf der Webseite. Details im Tafelvortrag. 

literature / references

- T. Ottmann, P. Widmayer, Algorithmen und Datenstrukturen, Spektrum Akademischer Verlag, 2002

- R. Sedgewick, Algorithms, Addison-Wesley, 2002 (auch C-, C++, Java-Versionen, auch auf deutsch bei Pearson) R. Sedgewick, Algorithms, Part 5: Graph Algorithms, Addison-Wesley, 2003

- K. Mehlhorn, P. Sanders, Algorithms and Data Structures - The Basic Toolbox, Springer, 2008

- S. Dasgupta, C. Papadimitriou, U. Vazirani, Algorithms, McGraw-Hill, 2007

- R. H. Güting, S. Dieker : Datenstrukturen und Algorithmen, B.G. Teubner Verlag, 2004

- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd ed., MIT Press, 2001 (auch auf deutsch bei Oldenbourg)

- V. Heun, Grundlegende Algorithmen, 2. Auflage, Vieweg, 2003

- J. Kleinberg, E. Tardos, Algorithm Design, Pearson Education, 2005

- U. Schöning, Algorithmik, Spektrum Akademischer Verlag, 2001

evaluation of teaching

Pflichtevaluation:

Freiwillige Evaluation:

SS 2008 (Vorlesung, Übung)

SS 2010 (Vorlesung)

SS 2011 (Vorlesung, Übung)

SS 2012 (Vorlesung, Übung)

SS 2013 (Vorlesung, Übung)

SS 2014 (Vorlesung, Übung, Praktikum)

SS 2015 (Vorlesung, Übung, Seminar)

SS 2016 (Vorlesung, Übung)

SS 2017 (Vorlesung, Übung, Laborpraktikum)

SS 2019 (Vorlesung, Übung, Laborpraktikum)

Hospitation: