Universität Hamburg - der Forschung, der Lehre, der Bildung, zur Homepage
art
Fachbereich InformatikAlgorithmen, Randomisierung und Theorie

Foto: UHH/Denstorf

ART

Formale Grundlagen der Informatik I

Die Vorlesung umfasst zwei inhaltliche Blöcke:

  1. Logik, Automatentheorie und formale Sprachen

    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 und der Prädikatenlogik 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.

Im Zentrum der Vorlesung steht insbesondere auch die mathematische Beschäftigung mit den oben genannten Themen, d.h. das Aufstellen und formale Beweisen von Behauptungen.

Aktuelles

  • 2017-06-20
    Am 21. Juni 2017 (Mittwoch) findet der “Dies Academicus” statt, weshalb der reguläre Lehrbetrieb an diesem Tag uniweit ausgesetzt wird. Teilnehmer von Übungsgruppen am Mittwoch können eine andere Übungsgruppe besuchen.
  • 2017-05-26
    Der zweite Teil der Vorlesung (Berechenbarkeit und Komplexität) beginnt am 29. Mai 2017 (Montag) und wird von Prof. Dr. Petra Berenbrink gehalten.
  • 2017-05-19
    Am 25. Mai 2017 (Donnerstag) ist ein Feiertag. Teilnehmer von Übungsgruppen am Donnerstag können eine andere Übungsgruppe besuchen.
  • 2017-05-18
    In den kommenden Tagen wird eine Musterlösung zu Übungsblatt 5 bereitgestellt werden.
  • 2017-05-14
    Foliensätze aktuallisiert.
  • 2017-04-18
    Für Automaten, Sprachen und Logik bitte die Folien des letzten Semesters verwenden, falls keine aktualisierte Fassung hier vorhanden ist: http://www.informatik.uni-hamburg.de/TGI/lehre/vl/SS16/FGI1/

Allgemeine Informationen

Veranstalter: Prof. Dr. Petra Berenbrink und Dr. Daniel Moldt

Organisation: Dr. Peter Kling

Übungsgruppenleiter: Prof. Dr. Petra Berenbrink, Christopher Hahn, Michael Haustermann, Anna Lina Heinzke, Damian Hofmann, Melf Johannsen, Dr. Dominik Kaaser, Dr. Daniel Moldt, David Mosteller, Lena Otterbach, Aly Rami, Jan Henrik Röwekamp, Martin Wincierz, Kim Wittenburg

Zeit & Ort:

Folien

Übungsblätter

Hier wird wöchentlich (Freitags) ein neues Übungsblatt herausgegeben. Dieses kann bis Ende der darauffolgenden Woche beim jeweiligen Übungsgruppenleiter abgegeben werden. Die Aufgaben des Übungsblattes werden in der Woche nach der Abgabe in den Übungen besprochen. Wir empfehlen die Bearbeitung in Gruppen von 2 bis 3 Personen.

Die Abgabe der Übungsblätter ist freiwillig, jedoch muss jeder Studierende mindestens drei Lösungen an der Tafel in der Übung vorstellen. Wer vier bis fünf (je nach Auslastung der Übungsgruppe) Lösungen an der Tafel präsentiert bekommt einen Bonus von 1/3 auf seine Klausurnote (sofern die Klausur bestanden wurde).

Literatur

Vorlesungsmaterialien sind zum Teil auf Deusch und zum Teil auf Englisch. Hilfreiche Literatur umfasst unter anderem:

  • Schöning, Uwe. Logik für Informatiker.
  • Hopcroft, John E., Motwani, Rajeev, and Ullman, Jeffrey D. Introduction to Automata Theory, Languages, and Computation.
  • Sipser, Michael. Introduction to the Theory of Computation.
  • Hromkovic, Juraj. Theoretische Informatik.