|
|
|
 |
Lehrstuhl
Mathematik & Informatik
Theoretische Informatik
WS 2004/2005 |
|
| |
| |
|
 |
|
|
| LV-NR |
150222
|
| Veranstaltung |
Theoretische Informatik
|
4.0 std.
|
NA 02/99 Mo 10.00-12.00
NA 02/99 Mi 10.00-12.00
|
|
| Dozent(inn)en |
Simon, H. U.
|
| Übungsgruppen
|
NA 02/99 Mo 8.30 -
10.00 (schon ab 13.12.)
|
| Uebungsgruppenleiter
|
Christian Brandl
|
| Erstmals am |
Mo, 11.10.2003 |
| Klausur |
15.02.2005, 11.00-14.00, HIC |
| Klausurergebnisse |
Die Klausurergebnisse hängen am Schwarzen Brett des Lehrstuhls aus. |
| Termin zur Klausureinsichtnahme |
12.04.2005,18.00-19.00 Uhr im Seminarraum NA 1/64 |
| |
|
| |
|
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
das Buch "Introduction to Automata Theory, Languages, and Computation''
von John E. Hopcroft, Rajeev Motwani und Jeffrey D. Ullman (Addison
Wesley, 2000) dienen.
|
| |
|
Materialien |
| |
|
Das aktuelle Übungsblatt steht hier jeweils zum
(als evtl. komprimiertes ps-file) zum Download bereit. (Die
Freischaltung erfolgt aber erst am Anfang der betreffenden Woche).
Blatt 1
Blatt 2
Blatt 3
Blatt 4
Blatt 5
Blatt 6
Blatt 7
Blatt 8
Blatt 9
Blatt 10
Blatt 11
Blatt 12
|
| |
|
Hier stehen die Musterlösungen der
Übungsblätter und der Klausur zum Downloaden
bereit.
Blatt 1
Blatt 2
Blatt 3
Blatt 4
Blatt 5
Blatt 6
Blatt 7
Blatt 8
Blatt 9
Blatt 10
Blatt 11
Blatt 12
Klausur
|
| |
|
Hier stehen einige mit Folien gehaltene Vorlesungen
zum Downloaden bereit.
Vorlesung vom 06. Dezember
Vorlesung vom 08. Dezember
Vorlesung vom 05. Januar
Vorlesung vom 12. Januar
|
|
| |
|
|
