| Wochentag | Uhrzeit | Hörsaal |
|---|---|---|
| Dienstag | 10-12 Uhr | EF 50/HS 1 |
| Donnerstag | 10-12 Uhr | HG III/Audimax |
Die Vorlesung „Grundbegriffe der theoretischen Informatik" ist eine Einführung in zentrale Gebiete der theoretischen Informatik, nämlich Komplexitätstheorie, Entscheidbarkeitstheorie, Automatentheorie, Grammatiken und Syntaxanalyse.
Zunächst wird diskutiert, wie sich die algorithmische Komplexität eines Problems definieren lässt. Darunter verstehen wir die Mindestressourcen (wie Rechenzeit), um ein Problem zu lösen. Während in der Vorlesung DAP2 spezielle Algorithmen für Probleme untersucht werden, müssen hier alle denkbaren Algorithmen für ein Problem betrachtet werden. Es zeigt sich, dass eine derartige Theorie unabhängig vom verwendeten Rechnertyp und von der verwendeten Programmiersprache möglich ist.
Für die meisten wichtigen Optimierungsprobleme gibt es einen trivialen Algorithmus mit exponentieller Laufzeit. Er probiert einfach alle möglichen Lösungen aus und wählt eine optimale Lösung. Für sehr viele dieser Probleme können wir zeigen, dass es entweder für sie alle effiziente Algorithmen gibt oder für sie alle keine effizienten Algorithmen gibt. Die Vermutung, dass die zweite Alternative wahr ist, beruht auf der NP-ungleich-P-Hypothese. Diese Hypothese stammt aus der NP-Vollständigkeitstheorie, dem wohl wichtigsten Teilgebiet der theoretischen Informatik. Diese Theorie wird vorgestellt, wobei ein neuer Zugang gewählt wird, in dem Randomisierung als Schlüsselkonzept aufgefasst wird.
In der Entscheidbarkeitstheorie wird untersucht, welche Probleme algorithmisch nicht lösbar sind. Dazu gehören so wichtige Probleme wie die Verifikation von Programmen und die Entscheidung, ob zwei Grammatiksysteme dieselbe Programmiersprache beschreiben. Für die Praxis ergibt sich die Konsequenz, nach Algorithmen für wichtige Spezialfälle zu suchen.
Endliche Automaten modellieren Schaltwerke, Rechnerkomponenten und Rechner mit beschränktem Speicher ebenso wie Cola-Automaten. Die Behandlung endlicher Automaten ist grundlegend für die Synthese und Analyse von Rechnern, die Verifikation von Hardwarekomponenten, den Entwurf von CAD-Werkzeugen und vieles andere.
Die Syntax von Programmiersprachen wird durch Grammatiken beschrieben. Grammatiken sollten einerseits komfortabel sein, um Programmkonstrukte elegant zu unterstützen. Andererseits ist es notwendig, dass der Test der syntaktischen Korrektheit, die syntaktische Zerlegung und die Compilierung effizient möglich sind. Dazu muss die Klasse der erlaubten Grammatiksysteme genügend eingeschränkt sein. Es wird gezeigt, warum kontextfreie Grammatiken und ihre Einschränkungen als Grundlage von Programmiersprachen geeignet sind.
Die Vorlesung enthält negative Ergebnisse (Probleme erweisen sich als unlösbar oder nicht effizient lösbar) und positive Ergebnisse. Im ersten Fall sparen wir uns die Zeit bei der Suche nach nicht existierenden Algorithmen und sind motiviert, eingeschränkte Ziele zu verfolgen. Im zweiten Fall werden stets theoretisch effiziente und praktisch anwendbare Algorithmen beschrieben und analysiert.
Diese Vorlesung stellt neue Anforderungen an die Studierenden. Es werden ganze Theorien vorgestellt. So sind Zwischenschritte abstrakter als in anderen Vorlesungen. Ein Lernerfolg ist erfahrungsgemäß nur möglich durch
Für die Teilnahme an den Übungsgruppen ist eine Anmeldung in der Vorlesung am 22.04. erforderlich. Die endgültige Einteilung in die Übungsgruppen wird am 24.04. hier und durch einen Aushang am Lehrstuhl 2 (GB IV, 2. OG) bekannt gegeben. Die ersten Übungen finden in der zweiten Vorlesungswoche (also ab dem 28.04.) statt. Ein Wechsel der Übungsgruppen ist nur aus zwingenden Gründen und in Rücksprache mit Philipp Wölfel (GB IV, Raum 326) möglich.
Das erste Übungsblatt wird in der ersten Vorlesung am 22.04. verteilt. Der Termin für die Abgabe ist Freitag, der 25.04., 10.00 Uhr. Alle weiteren Übungsblätter werden NICHT in der Vorlesung verteilt, sondern sind ab ihrem Erscheinungsdatum hier verfügbar und liegen im GB IV auf dem Flur des 2. OG (Lehrstuhl 2) zwischen Raum 325 und Raum 326 aus. Die Blätter erscheinen jeweils donnerstags und die Abgabe der Lösungen muss spätestens am darauf folgenden Donnerstag um 10.00 Uhr erfolgen (handelt es sich dabei um einen Feiertag, so verschiebt sich der Abgabetermin auf Freitag, 9.00 Uhr). Das zweite Übungsblatt erscheint schon in der ersten Vorlesungswoche, also am 24.04.!
Jedes Übungsblatt enthält 4 Aufgaben und pro Aufgabe können bis zu 5 Punkte erzielt werden. Eine Abgabe darf von bis zu 2 Personen gemeinsam erstellt werden. Die Lösungen dürfen auch von mehreren Gruppen erarbeitet werden, aber jede Gruppe muss ihre Lösung eigenständig formulieren und aufschreiben. Bitte bei der Abgabe Name, Matrikelnummer und Übungsgruppennummer mit angeben.
Einen Übungsschein erhält, wer