http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Algorithmen und Datenstrukturen SS2015

Mitteilungen

Die Klausurergebnisse von "Algorithmen und Datenstrukturen" sind im System eingetragen und über die Thoska Karte abrufbar. Die Ergebnisse finden Sie auch am Aushang des Institut TI. 

Die Klausur findet am 20.07.2015, 10:00 - 12:30 Uhr im Audimax statt. Genauere Informationen finden Sie hier.

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.

 

Auswertung der Studierendenbefragung: Vorlesung AuD INF BA Vorlesung AuD ING-INF BA Übung AuD (Aumüller)

Klausurvorbereitung

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äre Bäume
  4. Binäre Suchbäume
  5. Hashverfahren
  6. Sortieralgorithmen
  7. Graphen, Digraphen, Breitensuche
    Für Ing-Inf:
    Für Inf:

2. Teil (EA + AuD)

  1. Divide-and-Conquer-Algorithmen
    Schnelle Fourier-Transformation:
  2. Tiefensuche
  3. Greedy-Algorithmen3.7.: Aktualisierung des Beispiels zum Huffman-Algorithmus!
  4. Greedy-Algorithmen für Graphprobleme3.7.: Hinweis auf Folie 119 beachten!
  5. Dynamische Programmierung
    aktualisiert, erweitert, korrigiert am 17.07.2015 

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 H 1518, Ch. Mattern

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

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

Praktikum:

Donnerstag (G), 17:00 Uhr, LdV-Hs 2, Ch. 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