64-055 Vorlesung Einführung in die Theoretische Informatik

Lehrende:

Dr. Daniel Moldt

Zeit/Ort:

Mo 12 - 14, Erwiss H

Kommentare/ Inhalte:

Diese Vorlesung umfasst die Blöcke: 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.
Im algorithmischen Bereich werden zum Abschluss zudem Grundlagen der Berechenbarkeit und Komplexität einführend behandelt.

Beweisverfahren sind ein zentrales Konzept in diesem Bereich, das grundlegend eingeführt und behandelt wird.
Im Zentrum der Vorlesung stehen zum einen die mathematische Beschäftigung mit den oben genannten Themen, d.h. das Aufstellen und formale Beweisen von Behauptungen und zum anderen die Modellierung, d.h. die Konstruktion, Bewertung und Verwendung von Modellen.

Weitere Informationen siehe:
https://www.inf.uni-hamburg.de/inst/ab/art/teaching

Lernziel:

Die Studierenden lernen grundlegende formale Konzepte und Methoden kennen, die für fast alle Teilgebiete der Informatik von Bedeutung sind. Ferner werden grundlegende Hilfsmittel für die Beschreibung, die Analyse, den Entwurf und die Bewertung von Problemen und deren Lösung besprochen und benutzt. 
Ziele sind dabei zum einen wesentliche Kenntnisse und Fähigkeiten der Modellierung in Form von syntaktischen, semantischen und pragmatischen Konzepten und Verfahren zu erwerben und zum anderen Fähigkeiten, mathematische Beweise zu verstehen und selbst führen zu können, anzueignen. 

Vorgehen:

Jede Woche werden Inhalte aus Sipser und Schöning behandelt.
Es gibt für jede Vorlesung einen Vortest und einen Nachtest.
Der Vortest einer Vorlesung muss bis zum Beginn der Vorlesung erfolgreich abgeschlossen worden sein.
Der Nachtest einer Vorlesung muss vor dem Beginn der nächsten Vorlesung ebenfalls erfolgreich abgeschlossen worden sein.

Vortests unterstützen mittels formativer Selbsttests Studierende, so dass die Vorbereitung des Lesestoffs vorab in Hinblick auf einfache Aussagen eigenständig überprüft werden kann.
Die Nachtests dienen der Überprüfung, ob die komplexeren Inhalte der jeweiligen Vorlesung richtig erfasst wurden und auf einfache Beispiele angewendet werden können.

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 (spätestens bis Ende März) mindestens einmal im OpenOlat-System mit der B-Kennung 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 die Bücher:

• Michael Sipser (2013). Introduction to the Theory of Computation. Third Edition. Cengage Learning. Boston, ISBN-13: 978-1-133-18779-0
  https://kataloge.uni-hamburg.de/DB=1.18/LNG=DU/SID=af7c84eb-1/CMD?ACT=SRCHA&IKT=1016&SRT=YOP&TRM=sipser
• Uwe Schöning (2000). Logik für Informatiker. 5. Auflage. Spektrum Akademischer Verlag. Heidelberg, ISBN: 3-8274-1005-3
  https://kataloge.uni-hamburg.de/DB=1.18/SET=1/TTL=1/CMD?ACT=SRCHA&IKT=1016&SRT=YOP&TRM=sch%C3%B6ning

Weitere Literatur zur weiteren Vertiefung sind z.B.:

• 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 Hromkovic (2014). Theoretische Informatik. Springer Vieweg. Wiesbaden
  im VPN online Version: https://link.springer.com/book/10.1007/978-3-658-06433-4
• Gottfried Vossen und Kurt-Ulrich Witt (2016). Grundkurs Theoretische Informatik
  Eine anwendungsbezogene Einführung für Studierende in allen Informatik- Studiengängen 6.,
  erweiterte und überarbeitete Auflage, Springer Vieweg im VPN online Version:
  https://link.springer.com/book/10.1007/978-3-8348-2202-4

Alternativ sind aber auch andere einführende Lehrbücher zur Logik und zur Automatentheorie für die Veranstaltung geeignet.