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 Bachelor Informatik 2021
Modulnummer200062
Prüfungsnummer220445
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2242 (Komplexitätstheorie und Effiziente Algorithmen)
Modulverantwortliche(r)Prof. Dr. Martin Dietzfelbinger
TurnusSommersemester
SpracheDeutsch
Leistungspunkte5
Präsenzstudium (h)45
Selbststudium (h)105
VerpflichtungPflichtmodul
AbschlussPrüfungsleistung mit mehreren Teilleistungen
Details zum AbschlussDas Modul Algorithmen und Datenstrukturen 1 mit der Prüfungsnummer 220445 schließt mit folgenden Leistungen ab:
  • schriftliche Prüfungsleistung über 90 Minuten mit einer Wichtung von 100% (Prüfungsnummer: 2200710)
  • Studienleistung mit einer Wichtung von 0% (Prüfungsnummer: 2200711)


Details zum Abschluss Teilleistung 2:

Praktikum, mündliche Präsentation und Diskussion

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

Grundlagen und Diskrete Strukturen

Mathematik 1

Lernergebnisse und erworbene Kompetenzen

Fachkompetenz: Die Studierenden kennen die Grundprinzipien des Algorithmenentwurfs und der Korrektheits- und Zeitanalyse von Algorithmen und Datenstrukturen. Die Studierenden kennen ein Verfahren für die Spezifikation von Datentypen und können dieses auf Beispiele anwenden. Sie kennen die O-Notation und ihre Regeln und können sie bei der Laufzeitanalyse benutzen. Die Studierenden kennen grundlegende Datenstrukturen über Spezifikation und Implementierungs­möglichkeiten und können die zentralen Perfomanzparameter benennen und begründen. Sie kennen fortgeschrittenere Datentypen wie  "binärer Suchbaum" und Details der Implementierung als balancierter Suchbaum. Die Studierenden kennen das Prinzip und das Verhalten von einfachen Hashverfahren und können das zu erwartende Verhalten für die verschiedenen Verfahren beschreiben. Sie kennen Konstruktionen einfacher randomisierter Hashklassen und zugehörige Beweise.  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.

Im Praktikum konnten die Studierenden konkrete Erfahrungen mit dem essentiellen Schritt von theoretisch entworfenen und analysierten Algorithmen zur praktischen Implementierung und experimentellen Evaluation machen. Das Praktikum führt in den Umgang mit einer zweiten Programmiersprache (C++) ein und führt zur grundlegenden Beherrschung dieser Sprache in Lesen und Verwendung. Die Studierenden können in diesem Aufgabenfeld selbst entwickelte Vorgehensweisen und eigene Erkenntnisse im Gespräch darstellen.

Methodenkompetenz: Die Studierenden beherrschen Techniken zur Beschreibung von einfachen Systemen (Datentypen) und Verfahren (Algorithmen) sowie zur Beschreibung des Laufzeitverhaltens (O-Notation). Sie verstehen den Sinn von Korrektheitsbeweisen und beherrschen die grundlegenden Techniken für solche Beweise und für Laufzeitanalysen. Sie verstehen die Bedeutung der Effizienz bei der Implementierung von Algorithmen und Datenstrukturen.

Sozialkompetenz: Die Studierenden haben die Erfahrung gemacht, dass zur Erreichung des Ziels der Vorlesung die Herstellung einer gemeinsamen konzentrierten Arbeitsatmosphäre wesentlich ist. Diskussionsbeiträge und Fragen werden von den Lehrenden und den Studierenden immer begrüßt. Die Studierenden können sich aktiv und interagierend an der Diskussion der Lösung der Übungsaufgaben in der Übung beteiligen. Sie sind fähig zu erkennen, dass unterschiedliche Herangehensweisen zum Ziel führen können, im Rahmen der mathematischen Regeln und des Standes der Kunst. Im Praktikum konnte die Kombination eigener Bemühungen mit der Annahme von unterstützender Beratung vom Tutor eingeübt werden. Die Studierenden erkennen, dass es sich lohnt, theoretische Ergebnisse der Vorlesung im Experiment zu hinterfragen und haben den Wert unterschiedlicher Perspektiven auf einen Sachverhalt erfahren. 

Inhalt

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.

Graphen und gerichtete Graphen und ihre Darstellung.
Graphdurchlauf: Breitensuche, einfache Tiefensuche

Medienformen und technische Anforderungen bei Lehr- und Abschlussleistungen in elektronischer Form

zum Moodle-Kurs

Vorlesung: Folienprojektion, Folien auf der Webseite, Details im Tafelvortrag

Übung: Tafel, Studierende präsentieren Lösungen, Entwicklung von Lösungen im Dialog

Im Praktikum: Programmieraufgaben, eigenständig zu lösen in dedizierter Programmierumgebung, On-Line-Auswertung der Lösungen.

Literatur
  • T. Ottmann, P. Widmayer, Algorithmen und Datenstrukturen, Spektrum Akademischer Verlag, 2002
  • R. Sedgewick, Algorithms, Addison-Wesley, 2002 (auch C-, C++, Java-Versionen, auch auf deutsch bei Pearson)
  • R. Sedgewick, Algorithms, Part 5: Graph Algorithms, Addison-Wesley, 2003
  • K. Mehlhorn, P. Sanders, Algorithms and Data Structures - The Basic Toolbox, Springer, 2008
  • R. H. Güting, S. Dieker: Datenstrukturen und Algorithmen, B.G. Teubner Verlag, 2004
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd ed., MIT Press, 2001 (auch auf deutsch bei Oldenbourg)
Lehrevaluation