Inhalt

[ INBIPVOBEKO ] VL Berechenbarkeit und Komplexität

Versionsauswahl
Workload Ausbildungslevel Studienfachbereich VerantwortlicheR Semesterstunden Anbietende Uni
3 ECTS B2 - Bachelor 2. Jahr Mathematik Wolfgang Schreiner 2 SSt Johannes Kepler Universität Linz
Detailinformationen
Quellcurriculum Bachelorstudium Informatik 2013W
Ziele Ziel der LVA ist Vermittlung der Grundlagen der theoretischen Informatik (Berechenbarkeitstheorie und Komplexititätstheorie). Die Studierenden sollen die wesentlichen Modelle der Berechenbarkeit und deren Zusammenhänge kennen lernen, sowie erkennen, dass es Grenzen der Berechenbarkeit gibt (nicht berechenbare Funktionen, nicht entscheidbare Probleme). Weiters erfahren die Studierenden die grundlegenden Begriffe der asymptotischen Komplexität sowie die fundamentalen Klassen der Problemkomplexität und lernen die Grenzen der praktischen Berechenbarkeit kennen (NP-vollständige Probleme). Abgerundet wird die LVA durch die Präsentation von grundlegenden Techniquen der praktischen Komplexitätsanalyse von iterativen und rekursiven Algorithmen.
Lehrinhalte Endliche Automaten, Nichtdeterminismus und Determinisierung, Minimierung, reguläre Sprachen, reguläre Ausdrücke und deren Umwandlung von/in endliche Automaten, Turing-Maschinen, Register-Maschinen, Loop- und While-Programme, primitiv und mu-rekursive Funktionen, weitere Turing-vollständige Berechenbarkeitsmodelle, das Halteproblem, Problem-Reduktion, weitere unentscheidbare Probleme.

Komplexitätsmaße, Komplexität im schlechtesten und im durchschnittlichen Fall, asymptotische Komplexität, Komplexitätsklassen; Zusammenhang zwishen verschiedenen Komplexitätsmodellen, Problemkomplexität, NP-vollständige Probleme; beispielhafte Komplexitätsanalyse von iterativen und rekursiven Algorithmen, Lösen von Summen und Rekurrenzen, Analyse von randomisierten Programmen, amortisierte Analyse.

Beurteilungskriterien Schriftliche Klausur.
Lehrmethoden Klassische Vorlesung.
Abhaltungssprache Deutsch, bei Bedarf Englisch
Literatur
  • Wolfgang Schreiner: "Computability and Complexity" (Skript).
  • Dirk W. Hoffmann: Theoretische Informatik.
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation (deutsche Ausgabe: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit).
  • Michael Sipser: Introduction to the Theory of Computation.
  • Thomas H. Cormen et al: Introduction to Algorithms.
Lehrinhalte wechselnd? Nein
Äquivalenzen INBPCVOFOG2: VO Formale Grundlagen 2 (3 ECTS)
Präsenzlehrveranstaltung
Teilungsziffer -
Zuteilungsverfahren Direktzuteilung