Hochschule Ravensburg-Weingarten | Zurück zur Startseite


Prof. Wolfgang Ertel
Wolfgang Ertel
Professor Dr. rer. nat.

Theoretische Informatik

Aktuelle Informationen über Inhalte und Prüfungsbedingungen finden Sie im LSF

Organisation:

Studiengänge IN
Semester 1
Semesterwochenstd. 4
davon Praktikum 0
Vorraussetzungen

 Mathematik, Algorithmen, Komplexität

Leistungsnachweis Klausur

 

Professor Dr. W. Ertel

Allgemeine Beschreibung des Fachgebiets:

Ziel des Faches Theoretische Informatik ist es, die theoretischen Grundlagen von formalen Sprachen, Logik und Berechenbarkeit zu vermitteln.
Es wird ein vertieftes Verständnis formaler Sprachen und Maschinenmodelle als Voraussetzung für die Entwicklung von Parsern und Compilern vermittelt. Die Prädikatenlogik als wichtige Grundlage für formale Verfahren in Programmverifikation, Hardwaredesign und künstlicher Intelligenz wird von Grund auf als formale Sprache mit deklarativer Semantik eingeführt. Der für die automatische Beweiser und Verifikationssysteme wichtige Resolutionskalkül wird ausführlich behandelt.

Inhalt:

  • Logik
    • Prädikatenlogik (Syntax, Semantik, Kalküle, insbesondere Resolution)
    • Andere Logiken: Modallogik, Temporallogik, Fuzzy Logik
    • PROLOG
  • Formale Sprachen und Maschinenmodelle
    • Endliche Automaten und reguläre Sprachen
    • Kellerautomaten und kontextunabhängige Sprachen
    • Die Chomsky-Hierarchie
    • Turingmaschinen
Übungen zu Theorie und Praxis aller Teilgebiete vertiefen das Verständnis der behandelten Themen.

Literatur:

Dirk W. Hoffmann: Theoretische Informatik, Hanser Verlag 2009.

W. Ertel: Grundkurs Künstliche Intelligenz, Vieweg 2008 (für den Logikteil relevant)

J. Hopcroft, R. Motwani, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Addison Wesley, 2002

U. Schöning: Theoretische Informatik kurzgefasst, Spektrum Akademischer Verlag, 1992.

R. Socher. Theoretische Grundlagen der Informatik. Fachbuchverlag Leipzig, 2003.

J. Dassow: Logik für Informatiker, 2005.

Materialien zur Vorlesung:

Alte Klausuren:
WS 08/09
Alte Klausuren (GINF2):
WS 99/00   WS 00/01   SS 01   WS 01/02   SS 02   WS 02/03
Links zur Logik: siehe KI-Buch

Links zu Sprachen, Maschinen und Berechenbarkeit:

TP: Die Paranoide Maschine

Skripten, Einführungen, etc.

Turingmaschinen

Berechenbarkeit u. Komplexität

Busy Beaver

Graphen und Bäume

Lex, Yacc, reguläre Ausdrücke

Vorträge zu Theoretische Informatik / Logik

zelluläre Automaten

Sprachen und Automaten

Theoretische Informatik

Quantencomputer

Liste ungelöster Probleme der Informatik – Wikipedia

Vorlesungsaufzeichnungen vom Sommersemester 2013

Videos zusammen mit den Folien anschauen

Vorlesung Nr. Inhalt Datum
01 Vollständiges Video
Einführung
Aussagenlogik
Syntax
Semantik
Beweisverfahren
11.03.2013
02 Vollständiges Video
Beweisverfahren
Resolution
Hornklauseln
14.03.2013
03 Vollständiges Video
Hornklauseln
Berechenbarkeit und Komplexität
Anwendung und Grenzen
Prädikatenlogik erster Stufe
Syntax
Semantik
Quantoren und Normalformen
14.03.2013
04 Vollständiges Video
Quantoren und Normalformen
Beweiskalküle
18.03.2013
05 Vollständiges Video
Resolution
21.03.2013
06 Vollständiges Video
Automatische Theorembeweiser
Mathematische Beispiele
Anwendungen
25.03.2013
07 Vollständiges Video
Zusammenfassung
Grenzen der Logik
Das Suchraumproblem
Entscheidbarkeit und Unvollständigkeit
Der fliegende Pinguin
Modellierung von Unsicherheit
25.03.2013
Gastvortrag: Abelian Square Avoidance in Words and Distributed Computing 27.03.2013
08 Vollständiges Video
Logikprogrammierung mit PROLOG
PROLOG Systeme und Implementierungen
Einfache Beispiele
Ablaufsteuerung und prozedurale Elemente
04.04.2013
09 Vollständiges Video
Selbstmodifizierende Programme
Constraint Logic Programming (CLP)
Zusammenfassung
Formale Sprachen
Sprache und Grammatik
22.04.2013
10 Vollständiges Video
Sprache und Grammatik
Chomsky-Hierarchie
Reguläre Sprachen
25.04.2013
11 Vollständiges Video
Reguläre Sprachen
Kontextfreie Sprachen
25.04.2013
12 Vollständiges Video
Kontextfreie Sprachen
29.04.2013
Video zum CYK-Algortihmus
13 Vollständiges Video
Kontextfreie Sprachen
Kontextsensitive Sprachen
Rekursiv aufzählbare Sprachen (Typ-0)
Endliche Automaten
Deterministische Automaten
13.05.2013
14 Vollständiges Video
Deterministische Automaten
Nichtdeterministische Automaten
Automaten und reguläre Sprachen
16.05.2013
15 Vollständiges Video
Kellerautomaten
Transduktoren
Zelluläre Automaten
27.05.2013
16 Vollständiges Video
Berechenbarkeit
Berechnungsmodelle
27.05.2013
17 Vollständiges Video
Berechnungsmodelle
03.06.2013
18 Vollständiges Video
Berechnungsmodelle
Turing-Maschinen
05.06.2013
19 Vollständiges Video
Turing-Maschinen
Registermaschinen
Berechnungsmodelle, Zusammenfassung
Church'sche These
05.06.2013
20 Vollständiges Video
Akzeptierende Turing-Maschinen
Entscheidbarkeit
Unentscheidbare Probleme
06.06.2013
21 Vollständiges Video
Unentscheidbare Probleme
06.06.2013
22 Vollständiges Video
Unentscheidbare Probleme
Komplexitätstheorie
Algorithmische Komplexität
10.06.2013
23 Vollständiges Video
Algorithmische Komplexität
Komplexitätsklassen
13.06.2013
24 Vollständiges Video
Komplexitätsklassen
NP-Vollständigkeit
17.06.2013
25 Vollständiges Video
NP-Vollständigkeit
Nachtrag zum dynamischen Programmieren
20.06.2013