 |
| 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)
|
|
