| Grundlagen der
Theoretischen
Informatik II - Wintersemester 06/07 - |
|---|
Lehrstuhl Automatentheorie
Prof. Dr-Ing. Franz Baader
| INFORMATIONEN ZUR WIEDERHOLUNGSKLAUSUR (Prüfungszeit SS2007) |
|---|
| INFORMATIONEN ZUR KLAUSUR |
|---|
| Zielstellung der Lehrveranstaltung |
|---|
In der Vorlesung Grundlagen der Theoretischen Informatik I werden Automaten und Grammatiken vorgestellt, die formale Sprachen - d.h. Mengen von Wörtern - erkennen bzw. erzeugen. Je nach Typ des Automaten oder der Grammatik erhält man verschieden starke Ausdrucksmittel zur Beschreibung von Klassen formaler Sprachen. Die wichtigsten dieser Klassen sind in der sogenannten Chomsky-Hierarchie zusammengefaßt. Insbesondere die regulären und die kontextfreien Sprachen sind wichtige Hilfsmittel bei der Beschreibung syntaktischer Strukturen z.B. von Programmen. Ihre formale Untersuchung bildet daher die Grundlage für die Übersetzung von Programmiersprachen und die Konstruktion zahlreicher Software-Werkzeuge.
Neben der Vermittlung von Wissen über formale Sprachen, Grammatiken und Automaten ist ein weiteres Ziel der Vorlesung, die Studierenden mit der Arbeitsweise in der Theoretischen Informatik vertraut zu machen.
In der Vorlesung Grundlagen der Theoretischen Informatik II werden formale Berechnungsmodelle eingeführt, die es ermöglichen, den intuitiven Begriff der "berechenbaren Funktion" formal zu definieren. Dies ist insbesondere wichtig, wenn man zeigen will, daß es nicht-berechenbare Funktionen gibt. In der Vorlesung werden Turing-Maschinen, While-Programme und µ-rekursive Funktionen als derartige Berechnungsmodelle eingeführt und es wird gezeigt, daß diese Modelle äquivalent sind, d.h. dieselbe Klasse von Funktionen berechnen. Diese Äquivalenz stützt die These von Church, welche besagt, daß die Turing-berechenbaren Funktionen genau die intuitiv berechenbaren Funktionen sind.
Auch wenn eine Funktion im Prinzip berechenbar ist, kann der Aufwand für ihre Berechnung so hoch sein, daß das Berechnungsverfahren in der Praxis nicht einsetzbar ist. Im zweiten Teil der Vorlesung wird daher ein formaler Rahmen eingeführt, mit dessen Hilfe man die Berechnungskomplexität von Funktionen abschätzen kann. Insbesondere erlaubt dies die Lokalisierung von harten Berechnungsproblemen, d.h. Problemen die (wahrscheinlich) nicht in polynomieller Zeit gelöst werden können.
Hier geht es zu einer ausführlichen Lehrveranstaltungsbeschreibung.
| Organisation |
|---|
Die Vorlesung findet donnerstags in der 4. DS im Hörsaal HSZ/03/H statt und beginnt in der ersten Lehrveranstaltungswoche des Semesters. Das offizielle Vorlesungsskript (Stand Januar 2005) liegt für die Studenten auf dieser Seite bereit. Die Einschreibung in die einzelnen Übungsgruppen erfolgt über jExam und ist verbindlich. Die Übungen beginnen in der Woche vom 9.10. bis 13.10.06, d.h. mit einer ungeraden Woche (41. Kalenderwoche). In dieser Woche finden die Übungen für Gruppen mit dem Vermerk 1. Woche statt.
Es besteht die Möglichkeit, inhaltliche und organisatorische Fragen zur Lehrveranstaltung innerhalb einer Mailingliste zu diskutieren. Dabei ist zu beachten, dass bei Nutzung der Adresse, die bei der Anmeldung eingesetzt wurde, keine zeitliche Verzögerung wegen Moderation entsteht. Ansprechpartner für den Übungsbetrieb ist Dr. Monika Sturm.
| Skript und Folien zur Vorlesung |
|---|
| Übungsaufgaben |
|---|
Übungsaufgaben sind im Vorfeld der jeweiligen
Übung auf dieser Seite zu finden und selbständig auszuarbeiten. In
den Übungen erfolgt die Diskussion der studentischen Lösungen.
Am 31.01.07 fällt die Übung in der 1.DS (Übungsleiterin: Claudia Schmidt)
aus. Ausweichtermine sind: Mi. 5.DS, WIL A317;
Mo. 4. DS, Zeu 255;
Do. 1. DS, SE2/22;
Fr. 2. DS, SE2/22.
Ab sofort wird auf Grund zu geringer Nachfrage die Übung 15
(ungerade Woche, SCH/A185, Do., 6. DS) nicht mehr angeboten.
| Repetitorien |
|---|
| Literatur |
|---|
Die hier aufgeführte Literatur kann über den WebOPAC der SLUB gefunden werden.