Formale Grundlagen der Informatik (HWS 2017)

Grundanliegen der Informatik ist es, komplexe Probleme aus Wirtschaft, Wissenschaft und Gesellschaft in geeigneter Weise zu modellieren und einer rechentechnischen Lösung zuzuführen. Das ist in der Regel ein mehrstufiger Prozess, der ausgehend von einer informalen Beschreibung der Problemstellung folgende Schritte umfasst:

  • formale Spezifikation eines Berechnungsproblems,
  • Entwurf eines Lösungsalgorithmus,
  • Schreiben eines entsprechenden Computerprogramms in einer höheren Programmiersprache,
  • rechnerinterne Abarbeitung des Programms, was das Kompilieren des Programms in eine Folge von Maschinenbefehlen und die Abarbeitung dieser Folge durch einen entsprechenden Prozessor umfasst.

Inhalt dieser Vorlesung ist, diese Schritte für ein sehr einfaches formales Rechnermodell nachzuvollziehen und so ein prinzipielles Verständnis für die Grundkonzepte der Informatik wie Berechnungsproblem, Algorithmus, Programm, Schaltkreis, Abarbeitung von Maschinenbefehlen durch einen Prozessor zu erzeugen. Wesentlich dafür ist eine formal korrekte aber trotzdem gut verständliche Spezifikation dieser Konzepte, wofür sich die Sprache der Höheren Mathematik bewährt hat. Die Vorlesung beginnt mit einer Zusammenstellung der notwendigen mathematischen Grundbegriffe wie Mengen, Relationen, Abbildungen, Graphen und Boolesche Funktionen. Danach werden folgende Themen behandelt:

  • Einführung in die Aussagenlogik und die Realisierung Boolescher Funktionen durch logische Schaltungen
  • Endliche Automaten und ihre Realisierung durch logische Schaltwerke
  • Turing-Maschinen als einfaches Rechnermodell
  • Prinzipielle Grenzen der Berechenbarkeit