Theoretische Informatik I (Grundzüge der Informatik I)

Inhalte dieser Vorlesung sind:

In dieser Vorlesung wird in das unbedingt notwendige Grundwissen aus dem Bereich der Theoretischen Informatik eingeführt, das als Grundlage für viele Gebiete der praktischen und der technischen Informatik dient. Dabei werden die folgenden drei Gebiete angesprochen:

(1.) Formale Sprachen und Automaten
Eine formale Sprache ist eine Menge von (endlichen) Zeichenketten (Wörtern) über einem endlichen Zeichenvorrat (Alphabet). Jede Programmiersprache ist etwa eine solche formale Sprache. Welche Formalismen sind entwickelt worden, um formale Sprachen zu beschreiben? Es werden verschiedene Arten von Grammatiken betrachtet, wobei eine Grammatik ein formales System ist, das beschreibt, wie die Elemente einer Sprache erzeugt werden. Komplementär hierzu werden dann Klassen von Automaten entwickelt, die genau die Sprachen einer bestimmten Art akzeptieren.

(2.) Berechenbarkeitstheorie
Welche Funktionen sind überhaupt berechenbar, d.h., für welche Funktionen gibt es überhaupt Algorithmen, um sie zu berechnen? Zur Beantwortung dieser Frage braucht man einen formal fundierten Algorithmusbegriff. Hierzu gibt es viele verschiedene Ansätze, die aber alle letztendlich zueinander äquivalent sind, was zur sogenannten Churchschen These geführt hat. Insbesondere stellt es sich heraus, dass es Funktionen gibt, die nicht berechenbar sind, und es Probleme gibt, die nicht algorithmisch gelöst werden können. Beispiele solcher Probleme werden in der Vorlesung behandelt werden.

(3.) Komplexitätstheorie
Hier stellt man die Frage nach den notwendigen Resourcen für die algorithmische Lösung eines Problems, wobei man insbesondere nach dem erforderlichen Bedarf an Rechenzeit oder Speicherplatz fragt. Hier zeigt sich, dass es Probleme gibt, die zwar prinzipiell algorithmisch gelöst werden können, die aber dennoch praktisch unlösbar sind, weil jeder Algorithmus zur Lösung dieser Probleme mehr Zeit braucht als die verbleibende Zeit bis zum Ende unseres Sonnensystems. Zentral sind in diesem Bereich das bisher ungelöste P-NP-Problem und der Begriff der NP-Vollständigkeit.

Literatur

Uwe Schoening:
Theoretische Informatik - kurzgefasst.
Spektrum Akademischer Verlag Heidelberg/Berlin, 4. Auflage 2001, ISBN 3827410991.
Ergänzende Literatur:
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman:
Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie.
Oldenbourg, München, 4. Auflage 2000, ISBN 3486254952

Voraussetzungen:

Grundkenntnisse in der Mathematik und in der Programmierung. Die Vorlesung richtet sich an die Studierenden der Informatik und der Mathematik mit Nebenfach Informatik im zweiten Fachsemester. Sie wird auch allen anderen Studierenden empfohlen, die das Nebenfach Informatik haben.

Leistungsnachweis:

Durch regelmäßige Teilnahme an den Übungen und Bearbeitung der wöchentlichen Aufgaben sowie das Bestehen einer schriftlichen Abschlussprüfung kann ein Leistungsnachweis (Schein) erworben werden.