Technische Universität Ilmenau

Algorithmen und Datenstrukturen - Modultafeln der TU Ilmenau

Die Modultafeln sind ein Informationsangebot zu unseren Studiengängen. Rechtlich verbindliche Angaben zum Verlauf des Studiums entnehmen Sie bitte dem jeweiligen Studienplan (Anlage zur Studienordnung). Bitte beachten Sie diesen rechtlichen Hinweis. Angaben zum Raum und Zeitpunkt der einzelnen Lehrveranstaltungen entnehmen Sie bitte dem aktuellen Vorlesungsverzeichnis.

Fachinformationen zu Algorithmen und Datenstrukturen im Studiengang Bachelor Informatik 2010
ACHTUNG: wird nicht mehr angeboten!
Fachnummer198
Prüfungsnummer2200056
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2242 (Komplexitätstheorie und Effiziente Algorithmen)
Fachverantwortliche(r)Prof. Dr. Martin Dietzfelbinger
TurnusSommersemester
SpracheDeutsch
Leistungspunkte4
Präsenzstudium (h)45
Selbststudium (h)75
VerpflichtungPflicht
Abschlussschriftliche Prüfungsleistung, 90 Minuten
Details zum Abschluss
max. Teilnehmerzahl
Vorkenntnisse

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

Lernergebnisse

Fachkompetenz: Die Studierenden kennen die Grundprinzipien des Algorithmenentwurfs und der Korrektheitsanalyse und Zeitanalyse von Algorithmen und Datenstrukturen. Die Studierenden kennen beispielhaft Verfahren für die Spezifikation von Datentypen. Sie kennen die O-Notation und ihre Regeln, sowie die Anwendung der O-Notation bei der Laufzeitanalyse. Die Studierenden kennen die grundlegenden Datenstrukturen „Array“, „Liste“, „Stack“, „Queue“, „gerichteter Baum“ und „Binärbaum“  mit ihren Implementierungsmöglichkeiten und können die zentralen Perfomanzparameter benennen und begründen. Sie kennen den Datentyp „binärer Suchbaum“ mit seinen Methoden für Einfügen und Suchen und den Datentyp „Mehrwegsuchbaum“. Die Studierenden kennen die Algorithmen für mindestens eine Variante von balancierten Binärbäumen und können sie an Beispielen durchführen. Die Studierenden kennen das Prinzip von einfachen Hashverfahren, verstehen die Funktionsweise und können das zu erwartende Verhalten für die verschiedenen Verfahren beschreiben. Sie kennen Konstruktionen einfacher randomisierter Hashklassen.  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, sowie einfache Graphdurchmusterungsverfahren (Breitensuche, Tiefensuche). Sie kennen einen Algorithmus für die Ermittlung eines minimalen Spannbaums.

Methodenkompetenz: Die Studierenden sind in der Lage, die behandelten Algorithmen an Beispielen auszuführen. Sie können Berechnungsprobleme und einfache abstrakte Datentypen wie Stack, Queue, Liste, Priority Queue und Varianten syntaktisch und semantisch spezifizieren (mathematisches Modell). Sie können mit Hilfe der O-Notation Zeitanalysen von einfachen iterativen und rekursiven Algorithmen vornehmen, Algorithmen nach ihrer Laufzeit klassifizieren und ihre Nützlichkeit einschätzen. Sie können die Korrektheitsanalyse für die in der Lehrveranstaltung untersuchten Algorithmen vornehmen und sie auf Varianten anpassen. Sie können für Problemstellungen geeignete Datenstrukturen und Algorithmen auswählen und deren Eignung nachweisen. Sie können Algorithmenparadigmen einsetzen, um für mit den behandelten Bereichen verwandte Themen neue Algorithmen zu finden und die Korrektheit zu  beweisen und die Laufzeit zu analysieren.

Inhalt

Spezifikation von Berechnungsproblemen und von abstrakten Datentypen. Analyse von Algorithmen: Korrektheitsbeweise für iterative und rekursive Verfahren, Laufzeitbegriff, O-Notation, Laufzeitanalyse.  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. Priority Queues mit der Implementierung als Binärheaps. Grundbegriffe der Graphentheorie (ungerichtete und gerichtete Graphen, Markierungen an Knoten und Kanten, Wege und Kreise, Bäume und Wälder, Zusammenhangskomponenten). Datenstrukturen für Graphen (Adjazenzmatrix, Kantenliste, Adjazenzlisten, Adjazenzarrays). Durchmustern von Graphen: Breitensuche, Tiefensuche, Zusammenhangskomponenten, Entdecken von Kreisen. Minimale Spannbäume. Begleitend: Methoden für die Analyse von Laufzeit und Korrektheit.

Medienformen

Projektion von Folien, Folien und Übungsblätter auf der Vorlesungswebseite.

Literatur

*  G. Saake, K.-U. Sattler, Algorithmen und Datenstrukturen, 4. Auflage, dpunkt, 2010.

* R. Sedgewick, Algorithmen in C++, Pearson Studium, 2001.

*  T. Ottmann, P. Widmayer, Algorithmen und Datenstrukturen, Spektrum Akademischer Verlag, 4., überarb. Aufl. 2002

* R. H. Güting, S. Dieker: Datenstrukturen und Algorithmen, Teubner, 2004

*  T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, Second Edition, MIT Press 2001. (Auch auf deutsch erhältlich.)

* M. T. Goodrich, R. Tamassia, Data Structures and Algorithms in Java, 2. Auflage, Wiley, 2003.

Lehrevaluation

Pflichtevaluation:

Freiwillige Evaluation:

SS 2008 (Vorlesung, Übung)

SS 2010 (Vorlesung)

SS 2011 (Vorlesung, Übung)

SS 2012 (Vorlesung, Übung)

SS 2013 (Vorlesung, Übung)

Hospitation:

Informationen und Handreichungen zur Pflege von Modul- und Fachbeschreibungen durch den Modul- oder Fachverantwortlichen finden Sie auf den Infoseiten zum Modulkatalog.