Formale Grundlagen der Informatik 1

Lehrende:

Prof. Dr. Petra Berenbrink

Kommentare/ Inhalte:

Die Vorlesung ist eine Erzatzvorlesung fuer FGI 1. Sie beinhaltet den zweiten  Teil von FGI 1, Hoerer muessen ebenfalls an ETI teilnehmen.

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.

Die Vorlesung wird mit einer Klausur abgeschlossen welche beide Teile (FGI und ETI) abprueft.   

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:

Es gibt für jede Vorlesung On-line-Tests, die mittels formativer Selbsttests Studierende unterstützen, so dass das Erlernte in Hinblick auf einfache Aussagen eigenständig überprüft werden kann.

Die Tests werden in der OpenOlat-Umgebung 
https://www.openolat.uni-hamburg.de/dmz/
ebenso bereitgestellt wie die meisten anderen Materialien des Moduls. Eine Anmeldung von allen Teilnehmenden mittels der Benutzerkennung, z.B. BAO1234, der Universtität ist für die Nutzung zwingend notwendig.

Hinweis:

Bitte melden Sie sich so früh wie möglich (bis Ende März) mindestens einmal im OpenOlat-System unter dem Link oben an, damit sie gleich zu Beginn des Semesters Zugang zu allen Materialien haben. 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. 

Zusätzliche Hinweise zu Prüfungen:

Für die Vorlesung ist zusätzlich zur Klausur das Bestehen der On-line-Tests in OpenOlat eine der Voraussetzungen für das Bestehen des Moduls.