http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Algorithmen und Datenstrukturen SS 2014

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 23.07.2014, 13:30 - 16:00 Uhr im Audimax statt. Genauere Informationen finden Siehier.

Die Veranstaltung "Algorithmen und Datenstrukturen" findet dieses Semester zum ersten Mal nach der Prüfungsordnung 2013 für Informatik statt, also im Umfang 4 V + 2 Ü + 1 P. Studierende nach dieser Prüfungsordnung beachten bitte den Praktikumstermin.

Auswertung der Studierendenbefragung: Vorlesung AuD | Übung AuD | Praktikum AuD | Vorlesung EA | Übung EA

Termine

Vorlesung (Prof. M. Dietzfelbinger)

Montag13:00 - 14:30HU-Hs
Donnerstag13:00 - 14:30HU-Hs

 

Übung (Martin Aumüller und Christopher Mattern)

Dienstag17:00 - 18:30Sr HU 010
Mittwoch09:00 - 10:30Sr H 1519

 

Praktikum (Christopher Mattern)

Freitag (U)13:00 - 14:30K-Hs 2

Das Praktikum findet zunächst als Saalveranstaltung statt.

Prüfungsvorbereitung

Für Teilnehmer der AuD-Klausur:

Alte Klausuren (Teil 1 der neuen AuD-Vorlesung)

Für Teilnehmer der mündlichen Prüfung EA:

Fragebogen mit Beispielfragen [pdf

Vorlesungsfolien

Alle Folien zum Download [zip]

1. Teil (AuD)

  1. Einführung und Grundlagen 
  2. Fundamentale Datentypen und Datenstrukturen
  3. Binäre Bäume
  4. Suchbäume
  5. Hashverfahren
  6. Sortierverfahren
  7. Graphen, Digraphen, Breitensuche

2. Teil (AuD + EA)

  1. Divide-and-Conquer
    Foliensatz FFT
  2. Tiefensuche
  3. Greedy-Algorithmen
  4. Greedy-Algorithmen für Graphprobleme
    • Druckversion [neu: 8.7.]
    • Blätterversion [neu: 8.7.]
      (Fehler im Dijkstra- und Jarnik/Prim-Algorithmus
      mit PQ beseitigt. Dist-Werte wurden nicht korrekt gesetzt. Danke an T. Brewka für den Hinweis.)
    Zusatz: 
    Notizen zu freien Bäumen
    Information:
    Analyse Pfadkompression nicht prüfungsrelevant!
  5. Dynamische Programmierung Java-Code:
    • Floyd-Warshall/Bellman-Ford [zip]
    • Editierdistanz [zip]

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