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, H14, und Do 10-12, H6

Voraussetzungen/Vorkenntnisse:
Vorausgesetzt werden mathematische Grundkenntnisse der naiven Mengenlehre und elementarer Beweistechniken, wie des Beweisens durch Widerspruch und durch vollstÃ�ndige Induktion.

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-vollstÃ�ndige 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) 16.10.	Einführung; Aussagenlogik (AL)	Aufteilung der Übungsgruppen
2) 18.10.	Syntax und Semantik der AL; Erfüllbarkeit von AL-Formeln
3) 23.10.	Äquivalenz und Normalformen von AL-Formeln	Übungszettel 1
4) 25.10.	Hornformeln, Schlussverfahren, Vollständigkeit; Resolution der AL
5) 30.10.	Resolution; Prädikatenlogik erster Stufe (PL1): Syntax	Übungszettel 2
6) 6.11.	PL1: Semantik (Strukturen, Modelle); Äquivalenz und Normalformen
Teil II: Formale Sprachen & Grammatiken
7) 8.11.	Einführung; Formale Sprachen; Verkettung & Potenzen von Wortmengen	Übungszettel 3
8) 13.11.	Reguläre Ausdrücke/Sprachen; Backus-Systeme, Syntaxdiagramme
9) 15.11.	Kontextfreie Sprachen; Grammatik, Ableitung; Pumping-Lemma; XML	Übungszettel 4
10) 20.11.	Allgemeine Regelsprachen; Einseitig lineare Grammatiken
11) 22.11.	Äquivalenz rechts-/linkslineare Sprache und reguläre Sprache	Übungszettel 5
12) 27.11.	Bezug zu kfr. Sprachen; kss. Sprachen; Chomsky-Hierarchie
Teil III: Formale Sprachen & Automaten
13) 29.11.	Endliche Automaten (EA); akzeptierte Sprache	Übungszettel 6
14) 4.12.	EA und reguläre Sprachen; Nicht-det. endliche Automaten (NEA)
15) 6.12.	Äquivalenz EA und NEA; EA und reguläre Sprachen "revisited"	Übungszettel 7
16) 11.12.	EA als Rechner/Endliche Maschinen
17) 13.12.	Kellerautomaten; akzeptierte Sprache	Übungszettel 8
18) 16.12.	NKA und DKA; Akzeptieren durch leeren Stack; NKA und kfr. Sprachen
19) 20.12.	Turing-Maschinen; Äquivalenz mit allgemeinen Regelsprachen	Übungszettel 9
Teil IV: Berechenbarkeit, Entscheidbarkeit & Komplexität
20) 8.1.	Berechenbarkeitsbegriff; Turing-Maschinen
21) 10.1.	Turingsche These und Churchsche These	Übungszettel 10
22) 15.1.	Registermaschinen (RAM), RAM-Berechenbarkeit
23) 17.1.	Komplexität; uniforme/logarithmische Kosten	Übungszettel 11
24) 22.1.	Aufwandsanalyse; O-/Omega-/Theta-Notation
25) 24.1.	Komplexitätsklassen P/NP, P-NP-Problem	Übungszettel 12
26) 29.1.	NP-Vollständigkeit; Nicht-/Berechenbarkeit
27) 31.1.	Un-/Entscheidbarkeit; Halteproblem
28) 5.2.	Weitere unentscheidbare Probleme; Semi-Entscheidbarkeit
29) 7.2.	Rekursiv aufzählbar; kss Sprachen
30) 26.2.	Klausur

Uebungen zur Vorlesung

Verantwortlich für die Uebungen ist Christian Becker. Bei Problemen oder Fragen wendet euch bitte innerhalb seiner Sprechzeiten (momentan Donnerstag, 14-15 Uhr) oder per email (siehe Homepage) an ihn.

Informationen zu den Ã�bungen finden sich auf den Stud.IP-Seiten der Veranstaltung. Dort werden auch alle Übungszettel zum Herunterladen im öffentlichen Bereich zur Verfügung gestellt.

Tutoren:

Klaus Neumann
Felix Rabe
Jascha Schewtschenko
Julia Tolksdorf

Tutorien:

Montag, 10 - 12 Uhr, C01-243 (Julia)
Montag, 12 - 14 Uhr, U2-232 (Klaus)
Dienstag, 12 -14 Uhr, C01-243 (Julia)
Mittwoch, 14 -16 Uhr, C01-243 (Jascha)
Freitag, 14 - 16 Uhr, C01-243 (Felix)

Übungsblätter: Siehe Stud.IP-Seiten der Veranstaltung!

Stefan Kopp, 2006-10-09