Prof. Dr. Klaus Volbert
Letzte Aktualisierung: 08.05.2011
Grundlagen der Informatik (Sommersemester 2011, V4, Ü2, 8 ECTS-Punkte)
Es werden im Wesentlichen folgende Grundlagen der theoretischen Informatik behandelt:
- Formale Sprachen und Automaten
- Alphabete, Wörter, Sprachen, Grammatiken
- Deterministische und nichtdeterministische endliche Automaten
- Minimierung endlicher Automaten
- Reguläre Sprachen und reguläre Ausdrücke
- Nichtreguläre Sprachen und das Pumping-Lemma
- Kontextfreie Sprachen
- Abschlusseigenschaften
- Berechenbarkeit
- Berechenbarkeitsbegriff
- Turingmaschinen
- Entscheidbarkeit, Halteproblem
- Church'sche These
- Komplexität
- Polynomielle Algorithmen
- Nichtdeterminismus
- Klassen P und NP
- NP-Vollständigkeit
Weitere Informationen im Kursraum:
Termine
Vorlesungen, Start: 04.05.2011:
- Mi. : 13:30 - 15:00, Raum E204
- Do.: 11:45 - 13:15, Raum U314
Übungen, Start: 10.05.2011:
- Gruppe 1 (IN1a/IT1a): Di.: 11:45 - 13:15, Raum E204 (Klaus Volbert)
- Gruppe 2 (IN1b/IT1b): Mi.: 10:00 - 11:30, Raum U311, U314 ab 13.07.2011 (Johannes Eichenseer)
Literatur
- Baier, C., Asteroth, A.: Theoretische Informatik, Pearson Studium, 2002
- Hoffmann, D.W.: Theoretische Informatik, Hanser Verlag, 2009
- Hopcroft, J.E., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages and Computation, Addison Wesley, 2006 (deutsche Version der 2. Auflage: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Pearson Studium, 2002)
- Schöning, U.: Theoretische Informatik – kurzgefaßt, Spektrum Akademischer Verlag, 1995
- Sipser, M: Introduction to the Theory of Computation, Thomson Course Technology, 2006
- Vossen, G., Witt, K.-U.: Grundlagen der Theoretischen Informatik mit Anwendungen, Vieweg, 2002
- Wegener, I.: Theoretische Informatik, Teubner, 2005
