|
|
|
 |
Lehrstuhl
Mathematik & Informatik
Theoretische Informatik
WS 2005/2006 |
|
| |
| |
|
 |
|
|
| LV-NR |
150218
|
| Veranstaltung |
Theoretische Informatik
|
4.0 std.
|
NA 6/99 Mo 10.00-12.00
NC 6/99 Mi 10.00-12.00
|
|
| Dozent |
Simon, H. U.
|
| Übungsgruppe
|
Na 3/99 Mi 14.00-15.30
|
| Übungsgruppenleiter
|
Christian Brandl
|
| Klausur |
20.März, 9-12 Uhr, HNA, einzig erlaubte Hilfsmittel:Skript und "Theor. Inf.-kurzgefasst" von Schöning
|
| Klausurergebnisse |
31.03.2006, Schwarzes Brett am Lehrstuhl
|
| Klausureinsichtnahme |
21.04.2006, 11.30-12.30 Uhr, NA 01/99
|
| |
|
| |
|
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 immer mittwochs
(als ps-file) zum Download bereitgestellt. (Die noch folgenden Übungsblätter
sind noch nicht freigeschaltet).
Blatt 1
Blatt 2
Blatt 3
Blatt 4
Blatt 5
Blatt 6
Blatt 7 Aufgabe 7.1
Blatt 8
Blatt 9
Blatt 10
Blatt 11
Blatt 12
Blatt 13
|
| |
|
| |
|
Hier steht das Vorlesungsskript und eine Zusammenfassung zu den Lernzielen der einzelnen Kapitel zum Download bereit.
Kapitel1.1
Kapitel1.2
Kapitel1.3
Kapitel1.3b
Kapitel1.3c
Lernziele Kapitel 1
Kapitel1.4
Kapitel2.1f
Kapitel2.4
Kapitel2.5
Kapitel2.6f
Kapitel2.9
Kapitel3
Lernziele Kapitel 2 und 3
Liste besonders klausurrelevanter Aufgaben
|
|
| |
|
|
