64-050 Vorlesung Formale Grundlagen der Informatik I

Lehrende: Prof. Dr. Petra Berenbrink; Dr. Daniel Moldt

Veranstaltungsart: Vorlesung

Anzeige im Stundenplan: FGI I - VL

Semesterwochenstunden: 4

Credits: 5,0

Unterrichtssprache: Deutsch

Min. | Max. Teilnehmerzahl: - | 550

Kommentare/ Inhalte:
Die Vorlesung umfasst zwei Blöcke:

1. Automatentheorie, formale Sprachen und Logik:
   Logikkalküle sind Grundlage für eine formale Semantik von sprachlichen Beschreibungen wie auch von Anweisungen in Programmier-, Spezifikations-, und Repräsentationssprachen. In der Vorlesung werden grundlegende Anteile der Aussagenlogik behandelt.
   Automaten dienen als einfache mathematische Modelle von Computern oder auch Algorithmen.
   Formale Sprachen dienen der Beschreibung des prinzipiellen, strukturellen Aufbaus von Programmier- und Spezifikationssprachen.
   
2. Berechenbarkeit und Komplexität:
   Die Theorie der Berechenbarkeit untersucht, in Verbindung mit der formalen Beschreibung von Komplexität, die Abgrenzung zwischen effektiv Ausführbarem und prinzipiell niemals Möglichem.
   Beweisverfahren sind ein grundlegendes Verfahren in diesem Bereich, das grundlegend eingeführt und behandelt wird.
   

Lernziel:
Die Studierenden sollen grundlegende formale Konzepte und Methoden, die für fast alle Teilgebiete der Informatik von Bedeutung sind, kennenlernen. Ferner sollen grundlegende Hilfsmittel für die Beschreibung, die Analyse, den Entwurf und die Bewertung von Problemen und deren Lösung besprochen und benutzt werden. Die Fähigkeit, mathematische Beweise verstehen und selbst führen zu können, ist hierbei ein weiteres zentrales Lernziel.

Vorgehen:
Vorlesung; ferner kommt den Übungen eine besondere Bedeutung zu, um den Umgang mit den formalen Methoden zu erlernen.

Vorlesungsmaterialien sind zum Teil auf Deutsch und zum Teil auf Englisch.

Literatur:
Die Vorlesung stützt sich insbesondere auf das Buch:
  Michael Sipser. Introduction to the Theory of Computation.
Weitere Literatur zur weiteren Vertiefung sind z.B.
   Schöning, Uwe (2000). Logik für Informatiker. Spektrum, Akademischer Verlag
   Hopcroft, John E., Motwani, Rajeev und Ullman, Jeffrey D. (2007) Introduction to Automata Theory, Languages, and Computation, 3ed, Pearson/Addison-Wesley (auch auf Deutsch erhältlich)
Juraj Hromcovic. Theoretische Informatik.
Alternativ ist aber auch jedes andere einführende Lehrbuch zur Logik und zur Automatentheorie für die Veranstaltung geeignet.