Grundlagen der Theoretischen Informatik

Universität Bielefeld - Technische Fakultät - AG Wissensbasierte Systeme

Grundlagen der Theoretischen Informatik

Vorlesung im Grundstudium/Bachelor (4SWS/ 8LP/ 1 benot. EL )
Dozent: Stefan Kopp
Belegnummer: 392003
Termine: Di 10-12, H3, und Do 10-12, H13

Voraussetzungen/Vorkenntnisse:
Vorausgesetzt werden mathematische Grundkenntnisse der naiven Mengenlehre und elementarer Beweistechniken, wie des Beweisens durch Widerspruch und durch vollständige Induktion (Modul "Mathematik 1").

Inhalt/Kommentar:
Zentrale Gegenstdände der Informatik sind Algorithmen und ihre sprachlichen Realisierungen als Programme sowie Problemlösungen durch Berechnungsverfahren. Die Vorlesung behandelt Grundlagen der theoretischen Informatik, mit denen eine formale Fundierung von Programmiersprachen gelegt werden soll. Im Teil I werden zunächst Grundzüge der Aussagen- und Prädikatenlogik im Hinblick auf ihre Rolle in informatischen Aufgabenstellungen vermittelt. Auf diese Grundlagen bauen Vorlesungen zur Logik und Rekursionstheorie, Logik-Programmierung, zum Übersetzerbau und zur Künstlichen Intelligenz auf. Im Teil II geht es um formale Sprachen und Grammatiken bis hin zu einer Typisierung von Sprachklassen nach ihrer Leistungsfähigkeit (Chomsky-Hierarchie). Unter dem Gesichtspunkt der Spracherkennung betrachtet der Teil III formale Sprachen und Automaten (deterministische und nichtdeterministische endliche Automaten, Kellerautomaten, Turing-Maschinen und RAM-Maschinen). Der abschließende Teil IV befasst sich mit Berechenbarkeitstheorie, die die grundsätzlichen Möglichkeiten und Grenzen der Algorithmisierbarkeit betrachtet, und mit der Komplexitätstheorie, die untersucht, mit welchem Aufwand an Berechnungsressourcen (Rechenzeit, Speicherplatz) algorithmische Aufgaben gelöst werden können.

Literatur:

Hopcroft,J.E., Motwani, R., Ullman, J.D.: Einführung in die Automatentheorie, Formale Sprachen und Komplexitdtstheorie. Addison-Wesley (Pearson Studium), 2002 (zur Vertiefung)

Kelly, J.: Logik im Klartext, Pearson Studium, 2003 (viele Beispiele!)

Lewis, H.R., Papadimitriou, C.H.: Elements of the theory of computation. Englewood Cliffs, N.J.: Prentice Hall, 1981 (zur Vertiefung)

Schöning, U.: Theoretische Informatik kurz gefasst. (2. Auflage) Heidelberg: Spektrum Akademische Verlag, 1995

Schöning, U.: Logik für Informatiker (4. Aufl.). Heidelberg: Spektrum Akdademischer Verlag, 1995 (in Auszügen)

Sipser, M.: Introduction to the theory of computation. PWS Publishing Company, 1996 (wird wegen guter Didaktik gelobt)

Wegener, I.: Kompendium Theoretische Informatik - eine Ideensammlung. Stuttgart: Teubner, 1996 (zur Ergänzung)

Paul, Wolfgang J.: Komplexitätstheorie, Teubner, Stuttgart 1978. (Handliches Lehrbuch, mathematisch orientiert)

Garey, M. R.; Johnson, D.S.: Computers and Intractability, Freeman and Company, New York, 1979. (Klassiker; umfassende Besprechung der Komplexitätsklassen, mit Beweisen für viele NP-harte Probleme)

Software:
Der Automatensimulator aus der Vorlesung kann hier herunter geladen werden.
Die Turingmaschine aus Beispiel 20.2 zur Ausfuehrung im Automatensimulator.

Terminplan:

Teil I: Grundzüge der Logik
1) 14.10.	Einführung; Aussagenlogik (AL)	Aufteilung der Übungsgruppen
2) 16.10.	Syntax und Semantik der AL; Erfüllbarkeit von AL-Formeln
3) 21.10.	Äquivalenz und Normalformen von AL-Formeln	Übungszettel 1
4) 23.10.	Hornformeln, Schlussverfahren, Vollständigkeit; Resolution der AL
5) 28.10.	Resolution; Prädikatenlogik erster Stufe (PL1): Syntax	Übungszettel 2
6) 30.10.	PL1: Semantik (Strukturen, Modelle); Äquivalenz und Normalformen
Teil II: Formale Sprachen & Grammatiken
7) 4.11.	Einführung; Formale Sprachen; Verkettung & Potenzen von Wortmengen	Übungszettel 3
8) 6.11.	Reguläre Ausdrücke/Sprachen; Backus-Systeme, Syntaxdiagramme
9) 11.11.	Kontextfreie Sprachen; Grammatik, Ableitung; Pumping-Lemma; XML	Übungszettel 4
10) 13.11.	Allgemeine Regelsprachen; Einseitig lineare Grammatiken
11) 18.11.	Äquivalenz rechts-/linkslineare Sprache und reguläre Sprache	Übungszettel 5
12) 20.11.	Bezug zu kfr. Sprachen; kss. Sprachen; Chomsky-Hierarchie
Teil III: Formale Sprachen & Automaten
13) 25.11.	Endliche Automaten (EA); akzeptierte Sprache	Übungszettel 6
14) 27.11.	EA und reguläre Sprachen; Nicht-det. endliche Automaten (NEA)
15) 2.12.	Äquivalenz EA und NEA; EA und reguläre Sprachen "revisited"	Übungszettel 7
16) 4.12.	EA als Rechner/Endliche Maschinen
17) 9.12.	Kellerautomaten; akzeptierte Sprache	Übungszettel 8
18) 11.12.	NKA und DKA; Akzeptieren durch leeren Stack; NKA und kfr. Sprachen
19) 16.12.	Turing-Maschinen; Äquivalenz mit allgemeinen Regelsprachen	Übungszettel 9
Teil IV: Berechenbarkeit, Entscheidbarkeit & Komplexität
20) 18.12.	Berechenbarkeitsbegriff; Turing-Maschinen
21) 6.1.	Turingsche These und Churchsche These	Übungszettel 10
22) 8.1.	Registermaschinen (RAM), RAM-Berechenbarkeit
23) 13.1.	Komplexität; uniforme/logarithmische Kosten	Übungszettel 11
24) 15.1.	Aufwandsanalyse; O-/Omega-/Theta-Notation
25) 20.1.	Komplexitätsklassen P/NP, P-NP-Problem	Übungszettel 12
26) 22.1.	NP-Vollständigkeit; Nicht-/Berechenbarkeit
27) 27.1.	Un-/Entscheidbarkeit; Halteproblem
28) 29.1.	Weitere unentscheidbare Probleme; Semi-Entscheidbarkeit
29) 3.2.	Rekursiv aufzählbar; kss Sprachen
30) 5.2.	Wiederholung - Klausurvorbesprechung

Übungen zur Vorlesung

Verantwortlich für die Übungen ist Julia Tolksdorf. Bei Problemen oder Fragen wendet euch bitte innerhalb ihrer Sprechzeiten oder per email (siehe Homepage) an sie.

Stefan Kopp, 2006-10-09