http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Algorithmen und Datenstrukturen

Mitteilungen

Die Klausureinsicht zu der Vorlesung "Algorithmen und Datenstrukturen" findet am 10. November 2016 von 09:00 bis 12:00 Uhr im Raum Z 1050 (Zusebau) statt.

Die Klausurergebnisse von "Algorithmen und Datenstrukturen" sind im System eingetragen und über die Thoska Karte abrufbar.

Die Ergebnisse der Bonusklausur "Algorithmen und Datenstrukturen" können Sie in der Übung bzw. im Sekretariat des Institut TI erfragen.

Wenn Sie Gefallen an den in dieser Vorlesung besprochenen Themen gefunden haben, empfehlen wir einen Blick in die Themenliste für das Proseminar "Algorithmen und Komplexität" für Bachelorstudierende im kommenden Wintersemester.

Evaluation der Übung (Stefan Walzer)

Alte Klausuren

Zur Klausurvorbereitung beachten Sie bitte folgende alte Klausuren:

Algorithmen und Datenstrukturen (neu)

Algorithmen und Datenstrukturen (alt)

Effiziente Algorithmen (mündliche Prüfung)

Vorlesungsfolien

1. Teil (AuD)

1. Einführung und Grundlagen

2. Fundamentale Datentypen und Datenstrukturen

3. Binärbäume

4. Suchbäume

5. Hashverfahren

6. Sortieralgorithmen

Druckversion
Blätterversion
[Stand: 19.05.2016]

7. Graphen, Digraphen, Breitensuche


2. Teil (EA + AuD)

8. Divide-and-Conquer-Algorithmen

8/FFT. Schnelle Fourier-Transformation

9. Tiefensuche

10. Greedy-Algorithmen

11. Greedy-Algorithmen für Graphprobleme

12. Dynamische Programmierung

Termine

Vorlesung:

Donnerstag, 15:00 - 16:30 Uhr, HU-Hs, Prof. M. Dietzfelbinger

Freitag, 13:00 - 14:30 Uhr, HU-Hs

Übungen:

Dienstag, 09:00 - 10:30 Uhr, Sr K 2026, C. Mattern

Mittwoch, 09:00 - 10:30 Uhr, Sr HU 202,  C. Mattern

Mittwoch, 11:00 -12:30 Uhr, Sr HU 210,  C. Mattern

Praktikum:

Donnerstag (G), 17:00 Uhr, LdV-Hs 2,  C. Mattern

Inhalt

1. Teil:

  • 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

2.Teil:

  • 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 Jarnik/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

Literatur

Neben den Vorlesungsfolien empfehlen wir folgende Literatur:

  • Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, 3rd Edition, MIT Press, 2009 (auch deutsche Ausgabe verfügbar)
  • Mehlhorn, Sanders: Algorithms and Data Structures, The Basic Toolbox, Springer-Verlag, 2008
  • Ottmann und Widmayer: Algorithmen und Datenstrukturen, 5. Auflage, Spektrum Akad. Verlag 2012
  • Sedgewick: Algorithmen, Addison-Wesley, 2002

Für den zweiten Teil der Vorlesung empfehlen wir weiterhin:

  • Dasgupta, Papadimitriou, Vazirani, Algorithms, McGraw-Hill, 2007
  • Kleinberg, Tardos, Algorithm Design, Pearson Education, 2005
  • Schöning, Algorithmik, Spektrum Akademischer Verlag, 2001
  • Sedgewick, Algorithms, Part 5: Graph Algorithms, Addison-Wesley, 2003

Elementare Einführungen:

  • Güting, Dieker: Datenstrukturen und Algorithmen, B.G. Teubner Verlag, 2004
  • Weicker, Weicker: Algorithmen und Datenstrukturen, Springer-Vieweg, 2013