Grundbegriffe der theoretischen Informatik (GTI)

im Sommersemester 2004

Prof. Dr. Ingo Wegener

Inhalt

  1. Informationen zur Vorlesung
  2. Informationen zu den Übungen
  3. Begleitmaterial

 

Informationen zur Vorlesung

·         Vorlesungstermine

Wochentag

Uhrzeit

Hörsaal

Dienstag

10-12 Uhr

EF 50/HS 1

Donnerstag

10-12 Uhr

HG III/Audimax

 

·         Vorlesungsinhalt

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

 

·         Literatur

Die Vorlesung basiert auf den folgenden Büchern:


 

Informationen zu den Übungen

·         Veranstalter

Stefan Droste, Philipp Wölfel

·         Modalitäten

In der ersten Vorlesung am 20. April werden Anmeldezettel für die Übungen verteilt. Diese müssen bis zur zweiten Vorlesung am 22.April in der Vorlesung ausgefüllt abgegeben werden. Die Einteilung zu den Übungsgruppen wird dann am Freitag, dem 23. April, auf dieser Seite und auf dem schwarzen Brett des LS2 (GB 4, Campus Süd) bekannt gegeben. Die Übungsgruppen beginnen in der zweiten Vorlesungswoche, also ab dem 26. April.

Das erste Übungsblatt wird in der ersten Vorlesung am 20. April verteilt. Es soll bis zum Freitag, dem 23. April, um 10:00 Uhr abgegeben werden. Zu diesem Zeitpunkt wird die Einteilung zu den Übungsgruppen schon bekannt sein (siehe oben), sodass die Abgaben in die jeweils richtigen Briefkästen im Pavillion 6 abgegeben werden können (Name und Gruppennummer nicht vergessen). Von den 4 Aufgaben sind nur die ersten zwei schriftlich zu bearbeiten, die anderen zwei sind Präsenzaufgaben für die erste Übungsstunde. Ab dem 22. April werden die Übungsblätter dann jeweils am Donnerstag auf dieser Seite (als PDF- und PS-Dateien) und auf dem Flur des LS2 (zwischen dem Raum 325 und 326) erscheinen. Sie müssen bis zum Donnerstag der darauf folgenden Woche abgegeben werden. Sie enthalten in der Regel jeweils 4 Aufgaben zu jeweils 5 Punkten.

·         Übungstermine

Gruppe

Wochentag

Uhrzeit

Raum

BetreuerIn

1

Montag

10-12 Uhr

Experimentierhalle, SR 3.1

Rolf Harren

2

Montag

10-12 Uhr

ZB B, rechts

Christian Gunia

3

Montag

10-12 Uhr

GB 4, R 113

Philipp Wölfel

4

Montag

12-14 Uhr

ZB B, rechts

Christian Gunia

5

Montag

12-14 Uhr

GB 4, R 113

Philipp Wölfel

6

Mittwoch

8-10 Uhr

GB 4, R 425

Rolf Harren

7

Mittwoch

8-10 Uhr

ZB B, rechts

Dimo Brockhoff

8

Mittwoch

10-12 Uhr

ZB B, rechts

Dimo Brockhoff

9

Freitag

8-10 Uhr

GB 4, R 113

Christine Zarges

10

Freitag

8-10 Uhr

GB 4, R 318

Stefan Droste

11

Freitag

12-14 Uhr

GB 4, R 113

Christine Zarges

12

Freitag

12-14 Uhr

GB 4, R 318

Stefan Droste

    Neu: Die Einteilung in die Übungsgruppen kann hier eingesehen werden.

     ·         Sonstiges

Im Informatik-Portal gibt es ein Forum zur GTI Vorlesung.

 


 

Begleitmaterial

 


Letzte Veränderung: 23. April 2004