|
|
|
 |
Lehrstuhl
Mathematik & Informatik
Theoretische Informatik
WS 2006/2007 |
|
| |
| |
|
 |
|
|
| LV-NR |
150214
|
| Veranstaltung |
Theoretische Informatik
|
4.0 std.
|
NA 02/99 Mo 10.00-12.00
NC 6/99 Mi 10.00-12.00
|
|
| Dozent |
Simon, H. U.
|
| Übungsgruppe
|
n.V.
|
| Übungsgruppenleiter
|
Christian Brandl
|
| Informationen zur Übung und zur Klausur
|
Informationsblatt
|
| Klausurtermin |
|
| Zugelassene Hilfsmittel in der Klausur |
|
| Klausurergebnisse |
|
| ! Klausurbesprechung |
|
| |
|
| |
|
Voraussetzungen |
| |
|
Nützlich (aber nicht zwingend erforderlich) sind elementare Grundkenntnisse
in Informatik und Diskreter Mathematik sowie Vertrautheit mit mindestens einer Programmiersprache.
|
| |
|
Kommentar |
| |
|
Die Vorlesung richtet sich an Studierende der Mathematik und der Angewandten Informatik. Sie liefert eine Einführung in die Theorie der Grammatiken (insbesondere kontextfreie Grammatiken) und Automaten (endlicher Automat, Kellerautomat, Turing-Maschine). Sie gibt ferner einen Einblick in die Berechenbarkeits- und NP-Vollständigkeitstheorie, wo es um die Frage geht, welche Rechenprobleme (überhaupt bzw. mit vertretbarem Aufwand) gelöst werden können. Es wird sich zeigen, dass es inhärent schwere Probleme gibt, die von Rechnern nicht zufriedenstellend gelöst werden können.
|
| |
|
Literatur |
| |
|
Die Vorlesung orientiert sich
haupsächlich an dem Buch "Theoretische Informatik - kurzgefasst"
von Uwe Schöning (HTb, 2001). Zur Vertiefung des Stoffes kann sowohl
das Buch "Introduction to Automata Theory, Languages, and Computation''
von John E. Hopcroft, Rajeev Motwani und Jeffrey D. Ullman (Addison
Wesley, 2000) als auch "Introduction to the Theory of Computation" von M. Sipser
(PWS Publishing Company, 1997) dienen.
|
| |
|
Materialien |
| |
|
Das aktuelle Übungsblatt wird hier jeweils
(als ps-file) zum Download bereitgestellt werden.
Blatt 1
Blatt 2
Blatt 3
Blatt 4
Blatt 5
Blatt 6
Blatt 7
Blatt 8
Blatt 9
Blatt 10
Blatt 11
Blatt 12
Blatt 13
Blatt 14
|
| |
|
| |
|
Hier wird das Vorlesungsskript zum Download bereitgestellt werden.
Kapitel1.1
Kapitel1.2
Kapitel1.3
Kapitel1.3b
Kapitel1.4
Kapitel2a
Kapitel2b
Kapitel2c
Kapitel3
Lernziele zu Kapitel 1
Lernziele zu Kapitel 2 und 3
Besonders klausurrelevante Aufgaben
|
|
| |
|
|
