Technische Universität Ilmenau

Algorithmen, Automaten und Komplexität - 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 Modulnummer 200063 - allgemeine Informationen
Modulnummer200063
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer2241 (Automaten und Logik)
Modulverantwortliche(r)Prof. Dr. Dietrich Kuske
SpracheDeutsch
TurnusSommersemester
Vorkenntnisse

Algorithmen und Programmierung, Umgang mit mengentheoretischen Begriffen und Notationen (z. B. erworben in "Mathematik 1")

Lernergebnisse und erworbene Kompetenzen

Die Studierenden nnen grundlegende Algorithmen und Datenstrukturen anhand von Beispielen beschreiben, sind in der Lage, die Effizienz von Algorithmen zu bestimmen und können geeignete Algorithmen auswählen bzw. anpassen.

Die Studierenden kennen die Stufen 0, 2 und 3 der Chomsky-Hierarchie, ihre automatentheoretischen Charakterisierungen und können die Umwandlungen ausführen, sind in der Lage, Nachweise der Nicht-Regularität zu führen,sind mit Abschluss- und algorithmischen Eigenschaften der regulären und kontextfreien Sprachen vertraut.

Die Studierenden kennen die Klassen der semi-entscheidbaren und der entscheidbaren Probleme mit wesentlichen Beispielen, sind in der Lage, die Church-Turing These zu formulieren, ihre Bedeutung darzustellen und Argumente zu ihrer Begründung anzugeben.

Die Studierenden kennen die Komplexiätsklassen P und NP und einige NP-vollständige Probleme, können erläutern, warum die NP-schweren Probleme nicht effizient lösbar sind.

Die Studierenden können kritische Fragen zum behandelten Stoff, Probleme bei der Erarbeitung des Wissens bzw. bei der Lösung der Aufgaben klar formulieren und in Diskussionen mit Kommilitonen und Lehrenden vertreten.

In den Vorlesungen und im Selbstudium haben sie die genannten Kenntnisse erworben, in den Übungen und im Selbstudium die genannten Fähigkeiten der Anwendung erlernt.

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.

  • reguläre Sprachen: deterministische und nichtdeterministische endliche Automaten, reguläre Ausdrücke, effektiver Abschluss unter Booleschen Operationen, Verkettung und Iteration, Entscheidbarkeit von Leerheit, Inklusion und Äquivalenz, Pumping-Lemma
  • kontextfreie Sprachen: Kellerautomaten, Parsing, effektiver Abschluss unter positiven Booleschen Operationen, Verkettung und Iteration, Entscheidbarkeit der Leerheit, Pumping-Lemma, Nichtabschluss unter Schnitt
  • semi-entscheidbare Sprachen: Turing-Maschine
  • Berechenbarkeit: Church-Turing These, Unentscheidbarkeit des Halteproblems und der Universalität von kontextfreien Sprachen
  • Komplexitätstheorie: die Klassen P und NP, NP-Vollständigkeit, 3-SAT, graphentheoretische Probleme

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

Tafel, Folien, Übungsblätter

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
  • Schöning, "Theoretische Informatik kurzgefasst"
Lehrevaluation
Spezifik Referenzmodul
ModulnameAlgorithmen, Automaten und Komplexität
Prüfungsnummer2200712
Leistungspunkte5
SWS6 (4 V, 2 Ü, 0 P)
Präsenzstudium (h)67.5
Selbststudium (h)82.5
VerpflichtungPflichtmodul
Abschlussschriftliche Prüfungsleistung, 180 Minuten
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: 20 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
Spezifik im Studiengang Bachelor Ingenieurinformatik 2021
ModulnameAlgorithmen, Automaten und Komplexität
Prüfungsnummer2200712
Leistungspunkte5
Präsenzstudium (h)67
Selbststudium (h)83
VerpflichtungPflichtmodul
Abschlussschriftliche Prüfungsleistung, 180 Minuten
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: 20 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