Universität Bielefeld 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:

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:
Tutorien:
  1. Montag, 10 - 12 Uhr, C01-243 (Julia)
  2. Montag, 12 - 14 Uhr, U2-232 (Klaus)
  3. Dienstag, 12 -14 Uhr, C01-243 (Julia)
  4. Mittwoch, 14 -16 Uhr, C01-243 (Jascha)
  5. Freitag, 14 - 16 Uhr, C01-243 (Felix)
Übungsblätter: Siehe Stud.IP-Seiten der Veranstaltung!


Stefan Kopp, 2006-10-09