|
|
|
 |
Lehrstuhl
Mathematik & Informatik
Theoretische Informatik
WS 2007/2008 |
|
| |
| |
|
 |
|
|
| LV-NR |
150214
|
| Veranstaltung |
Theoretische Informatik
|
4.0 std.
|
NA 01/99 Mo 10.00-12.00
NC 6/99 Mi 10.00-12.00
|
|
| Dozent |
Simon, H. U.
|
| Übungsgruppe
|
n.V.
|
| Übungsgruppenleiter
|
Christian Brandl
|
| Klausurtermin SS 2008 |
21.08.2008, 09.00-12.00 Uhr, HIB
|
| Zugelassene Hilfsmittel in der Klausur |
Theoretische Informatik von Uwe Schöning und das Vorlesungsskript WS 07-08
|
| Hinweis (Bonuspunkte) |
Bei der Klausur gibt es keine Bonuspunkte.
|
| Klausurergebnisse |
Die Ergebnisse der Klausur vom 21.08.2008 können am Schwarzen Brett des Lehrstuhls eingesehen werden.
|
| Informationen zu den Übungsaufgaben
|
Vollständige! Liste nicht klausurrelevanter Aufgaben
|
| Klausureinsichtnahme |
14.10.2008, 18 Uhr, NA 1/64
|
| |
|
| |
|
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, der Angewandten Informatik und (als Wahlpflichtfach) an Studierende der IT-Sicherheit. Sie ist weiterhin ein wählbares Modul im Optionalbereich. 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.
Aufwärm-Blatt
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
Übungsklausur
Musterlösung
Hier wird jeweils der aktuelle Teil des Vorlesungsskriptes zum Download bereitgestellt.
Kapitel 1.1
Kapitel 1.2
Kapitel 1.3
Kapitel 1.4
Kapitel 2a
Kapitel 2b
Kapitel 3
|
|
| |
|
|
