Einführung in die theoretische Informatik

Eine wesentliche Aufgabe der Informatik besteht darin, Mittel und Wege zu entwickeln, die es gestatten, Probleme mit Hilfe eines Rechners zu lösen. Ein wichtiger Teilaspekt hierbei ist die Entwicklung von Algorithmen zur Berechnung gewisser Funktionen (d.h. zur Transformation von gegebenen Eingabedaten in gewisse Ausgabedaten). Damit stellt sich die folgende grundsätzliche Frage: "Welche Funktionen sind berechenbar?" Um diese Frage beantworten zu können, muss man natürlich zunächst präzisieren, was man unter einer "berechenbaren" Funktion verstehen will. Hier sind viele verschiedene Ansätze möglich, von denen wir einige in dieser Vorlesung kennenlernen und miteinander vergleichen wollen:
  1. Berechnung mittels imperativer Programmiersprachen (Beispiel: PASCAL),
  2. Berechnung mittels funktionaler Programmiersprachen (Beispiel: LISP),
  3. Berechnung mittels maschinen-naher Sprachen (Beispiel: ASSEMBLER),
  4. Mathematische Berechnungsmodelle (Beispiel: Turing-Maschinen).
Insbesondere werden wir sehen, dass es Funktionen gibt, die nicht berechenbar sind.

Ist eine Funktion berechenbar, so stellt sich als Nächstes die Frage nach dem dafür erforderlichen Aufwand. Dabei interessieren wir uns für die erforderliche Rechenzeit oder den erforderlichen Speicherplatz. Hierbei werden wir feststellen, dass es Funktionen gibt, für die kein optimaler Algorithmus existiert.

Literatur:

M.D. Davis, E.J. Weyuker:
Computability, Complexity and Languages
Academic Press, Orlando, 1983.
J.S. Mallozzi, N.J. DeLillo:
Computability with PASCAL
Prentice-Hall, Englewood Cliffs, N.J., 1984.
R. McNaughton:
Elementary Computability, Formal Languages, and Automata
Prentice-Hall, Englewood Cliffs, N.J., 1982.
C.H. Smith:
A Recursive Introduction to the Theory of Computation
Springer, New York, 1994.
G.J. Tourlakis:
Computability
Reston, Prentice-Hall, 1984.
K.W. Wagner:
Einführung in die theoretische Informatik
Springer, Berlin - Heidelberg, 1994.
Diese Vorlesung richtet sich an alle Studenten mit Interesse an den theoretischen Grundlagen der Informatik.