Algorithms and Data Structures - Interactive curriculae of TU Ilmenau

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

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.

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.

Folienprojektion, Folien auf der Webseite. Details im Tafelvortrag. 

- 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

mündliche Prüfungsleistung 30 min; zusätzlich muss ein Paktikum als unbenotete Studienleistung erbracht werden

mündliche Prüfungsleistung 30 min; zusätzlich muss ein Paktikum als unbenotete Studienleistung erbracht werden

mündliche Prüfungsleistung 30 min; zusätzlich muss ein Paktikum als unbenotete Studienleistung erbracht werden

mündliche Prüfungsleistung 30 min; zusätzlich muss ein Paktikum als unbenotete Studienleistung erbracht werden