Zur Hauptnavigation Zum Inhaltsbereich Zur Suche Zum Seitenfuß

Formale Grundlagen der Informatik 1
(Sommersemester 2015)

Veranstalter: Frank Heitmann
Zeit und Ort: Montag, 12-14 und Dienstag, 08-10 in ErzWiss H (erste Vorlesung am Dienstag, 7. April!)

Aktuelles:

  • [06.07.15] Da ist die Vorlesung auch schon um. Die Repetitoriumstermine stehen, s.u., bitte meldet euch an, indem ihr euch in die entsprechenden Listen eintragt!
  • [07.04.15] Die erste Vorlesung ist bereits online. Siehe Lecture2Go-Link unten. Vielen Dank an das Lecture2Go-Team!!
  • [23.03.15] Bitte beachten: Die erste Vorlesung ist am Dienstag, 7. April!

Links

Lesestoff:

Folien:

Skript:

  • Das Skript zum Automatenteil gibt es hier.
  • Einen Text zum Thema Ableitungen in der Aussagenlogik gibt es hier.

Repetitorien:

Die Repetitoriumstermine für den ersten Klausurtermin stehen. Bitte meldet euch zu den Repetitoriumsterminen an (begrenzte Platzzahl in B-201!), indem Ihr euch in die Listen an der Pinnwand vor dem TGI-Sekretariat (zwischen C-218 und C-219) eintragt. Die Termine:
  • FGI1 Repetitorium Gruppe 1
    • bei Frank Heitmann
    • in B-201
    • Di 14.7, 0900-1230 Uhr
    • Mi 15.7, 0900-1230 Uhr
    • Fr 17.7, 0900-1230 Uhr
  • FGI1 Repetitorium Gruppe 2
    • bei Niklas Steenfatt
    • in B-201
    • Mo 13.7, 1245-1615 Uhr
    • Di 14.7, 1245-1615 Uhr
    • Mi 15.7, 1245-1615 Uhr
  • FGI1 Repetitorium Gruppe 3
    • bei Jan Henrik Röwekamp
    • in B-201
    • Mo 13.7, 1630-2000 Uhr
    • Mi 15.7, 1630-2000 Uhr
    • Do 16.7, 1630-2000 Uhr
Nochmal: Bitte meldet euch zu den Repetitoriumsterminen an (begrenzte Platzzahl in B-201!), indem Ihr euch in die Listen an der Pinnwand vor dem TGI-Sekretariat (zwischen C-218 und C-219) eintragt.

Kommentare/Inhalte:

Die Modellierung und Analyse von Problemen sowie die Beurteilung gefundener Lösungen sind grundlegende Bestandteile der Informatik. Das Modul Grundlagen der Theoretischen Informatik beschäftigt sich auf mathematischer Basis mit Abstraktionen, Modellbildungen und Verfahren zur Beschreibung und Analyse von Algorithmen und Prozessen. Formale Methoden spielen in der Informatik die Rolle eines "Denkzeugs", mit dem der (abstrakte) Kern einer Sache knapp und präzise beschrieben werden kann. Wesentliche Hilfsmittel zur Modellierung von Problemen sind Kalküle, insbesondere logische Kalküle, formale Sprachen, Grammatiken und Automaten. Dadurch werden Modelle und Problemlösungen einer mathematischen Analyse zugänglich.

Eine ausführliche Modulbeschreibung findet sich im Modulhandbuch unter InfB-FGI 1:
http://www.inf.uni-hamburg.de/de/studies/orga/mhb/modulhandbuch_2013.pdf

Die Vorlesung umfasst drei Themenbereiche:

  • Grundlegende Begriffe, Notationsformen und Strukturen werden formal definiert und an Beispielen erläutert.
  • Logik: Logikkalküle sind Grundlage für eine formale Semantik von sprachlichen Beschreibungen wie auch von Anweisungen in Programmier-, Spezifikations, und Repräsentationssprachen. Die syntaktischen Beschreibungen ergeben Formale Sprachen, die über andere Erzeugungsmechanismen auch in dem dritten Themenbereich behandelt werden.
  • Automatentheorie, Formale Sprachen und Berechenbarkeit: Automaten dienen als einfache mathematische Modelle von Computern oder auch Algorithmen. Mit Formalen Sprachen wird der prinzipielle, strukturelle Aufbau von Programmier- und Spezifikationssprachen beschrieben. 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.

Lernziel:

Kennenlernen und Vertrautwerden mit grundlegenden formalen Konzepten und Methoden, die für fast alle Teilgebiete der Informatik wichtig sind. Erwerben und Einüben der Standardhilfsmittel für Beschreibung, Analyse, Entwurf und Bewertung von Problemen und deren Lösung.

Vorgehen:

Vorlesung; Die Veranstaltung legt großes Gewicht auf das Erlernen des Umgangs mit formalen Methoden. Aus diesem Grund kommt den Übungen eine besondere Bedeutung zu. Die erfolgreiche Teilnahme an den Übungen ist Voraussetzung für die Zulassung zur studienbegleitenden Abschlussprüfung (Klausur) (siehe auch 64-051). Informationen zu den Übungen sind hier zu finden: http://www2.informatik.uni-hamburg.de/tgi/lehre/vl/SS15/FGI1Ue

Literatur:

Jedes einführende Lehrbuch zur Logik und zur Automatentheorie eignet sich für die Veranstaltung. Wir empfehlen die nachfolgenden Bücher (das erste für den Logik-Teil, das zweite für den Automatenteil).
  • 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).
Imprint/Disclaimer
Last Change: 19:20 07/29/2015   Seitenanfang