Technische Universität Ilmenau

Algorithmen und Datenstrukturen 1 - Modultafeln der TU Ilmenau

Die Modultafeln sind ein Informationsangebot zu den Studiengängen der TU Ilmenau.

Die rechtsverbindlichen Studienpläne entnehmen Sie bitte den jeweiligen Studien- und Prüfungsordnungen (Anlage Studienplan).

Alle Angaben zu geplanten Lehrveranstaltungen finden Sie im elektronischen Vorlesungsverzeichnis.

Informationen und Handreichungen zur Pflege von Modulbeschreibungen durch die Modulverantwortlichen finden Sie unter Modulpflege.

Hinweise zu fehlenden oder fehlerhaften Modulbeschreibungen senden Sie bitte direkt an modulkatalog@tu-ilmenau.de.

Modulinformationen zu Algorithmen und Datenstrukturen 1 im Studiengang polyvalenter Bachelor Polyvalenter Bachelor mit Lehramtsoption für berufsbildende Schulen - Metalltechnik 2013 (IN)
Modulnummer100534
Prüfungsnummer2200370
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2242 (Komplexitätstheorie und Effiziente Algorithmen)
Modulverantwortliche(r)Prof. Dr. Martin Dietzfelbinger
TurnusSommersemester
SpracheDeutsch
Leistungspunkte3
Präsenzstudium (h)34
Selbststudium (h)56
VerpflichtungPflichtmodul
Abschlusskeiner
Details zum Abschluss
Alternative Abschlussform aufgrund verordneter Corona-Maßnahmen inkl. technischer Voraussetzungen

Prüfungsgespräch (mündliche Abschlussleistung) in Distanz nach §6a PStO-AB

Dauer: 30 Minuten

Technische Voraussetzung: Webex https://intranet.tu-ilmenau.de/site/vpsl-pand/SitePages/Handreichungen_Arbeitshilfen.aspx

Anmeldemodalitäten für alternative PL oder SL
max. Teilnehmerzahl
Vorkenntnisse

Algorithmen und Programmierung, Mathematik I.

Lernergebnisse und erworbene Kompetenzen

Die Studierenden kennen beispielhaft Methoden für die Spezifikation von Berechnungsproblemen und von abstrakten Datentypen und können sie für die grundlegenden Aufgaben und Datentypen anwenden. Sie können unter Verwendung  der O-Notation die Laufzeit von (auch zusammengesetzten) iterativen und rekursiven Algorithmen analysieren. Sie können auf iterative und rekursive Algorithmen Induktionsargumente anwenden, um die Korrektheit zu zeigen. 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 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 den grundlegenden Datentyp  „Priority Queue“ und seine Implementierung auf der Basis von binären Heaps. Die Studierenden kennen die Grundbegriffe der Graphentheorie 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. Sie können die Korrektheit dieses Verfahrens begründen.

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¨aume, 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 und technische Anforderungen bei Lehr- und Abschlussleistungen in elektronischer Form

zum Moodle-Kurs

Projektion von Folien

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)

SS 2018 (Vorlesung)

WS 2018/19 (Vorlesung, Übung)

Hospitation: