Menü
Positionsanzeige
Inhalt

[ INBIPVOBEKO ] VL Berechenbarkeit und Komplexität
Versionsauswahl
Es ist eine neuere Version 2021W dieser LV im Curriculum Masterstudium Artificial Intelligence 2024W vorhanden.
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 2021S
Ziele Ziel der LVA ist die Vermittlung der Grundlagen der theoretischen Informatik (Berechenbarkeitstheorie und Komplexititätstheorie). Die Studierenden lernen die wesentlichen Modelle der Berechenbarkeit und deren Zusammenhänge kennen und können Problemlösungen in diesen Modellen formulieren. Sie lernen, dass es Grenzen der Berechenbarkeit gibt und können nicht berechenbare Funktionen und nicht entscheidbare Probleme erkennen. Außerdem 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). Letztendlich können die Studierenden die grundlegenden Techniquen der praktischen Komplexitätsanalyse auf iterative und rekursive Algorithmen anwenden.
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 am Semesterende.
Lehrmethoden Folienvortrag mit Beispielen an der Tafel.
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
Sonstige Informationen https://risc.jku.at/courses/
Äquivalenzen INBPCVOFOG2: VO Formale Grundlagen 2 (3 ECTS)
Präsenzlehrveranstaltung
Teilungsziffer -
Zuteilungsverfahren Direktzuteilung