Lehrveranstaltung von Prof. Dr. Sebastian Iwanowski an der FH Wedel im SS 2006:

Grundlagen der Theoretischen Informatik

Vorlesungstermin: Mi 15:30 Uhr - 16:45 Uhr, HS 6
Assistent: Maximilian Herold, Übung: Fr 14:00 Uhr - 15:15 Uhr, HS 6

Studiengänge: B_Inf1, B_TInf1, B_WInf1 sowie alle Informatikstudenten, die diese Veranstaltung noch nicht besucht haben

Vorlesungsinhalte:

Diese Vorlesung legt das theoretische Fundament zur Vorlesung Programmieren 1 und darauf aufbauender Programmierveranstaltungen
und wendet sich an die Anfänger aller Informatikstudiengänge.
Es gibt in den Inhalten Überschneidungen nicht nur zu Programmieren 1, sondern auch zur Vorlesung Diskrete Mathematik,
die aus Gründen der inhaltlichen Geschlossenheit gewünscht sind.

Die Vorlesung wurde als Grundlagen der Programmierung von mir erstmals im WS 2004/2005 gehalten.
Im SS 2005 folgte die Aufteilung der Logik zwischen Diskrete Mathematik und dieser Vorlesung.
Im WS 2005/2006 kam die Umbenennung in den gegenwärtigen Titel und die
Hinzunahme von Aspekten der logischen und funktionalen Programmierung.
Das Kapitel Logische Programmierung wird in diesem Semester wieder entfernt,
wobei das Thema Resolution weiterhin im Lehrplan bleibt
und im Kapitel Aussagenlogik behandelt wird.
Etwas mehr Zeit als beim letzten Mal soll für die Kapitel Funktionale Programmierung
und Komplexitätstheorie verwendet werden.

Die unter den Kapitelüberschriften bereitgestellten Folien könnten noch kurzfristig
vor oder auch nach der jeweiligen Vorlesungseinheit aktualisiert werden.
In einem solchen Fall wird das letzte Aktualisierungsdatum in rot hinter dem Kapitel angegeben.

In den Vorlesungseinheiten werden nicht nur die Folien präsentiert,
sondern auch an der Tafel weitere Erklärungen abgegeben und Beispiele
erläutert.

1. Einführung
2. Logik
    2.1 Aussagenlogik
    2.2 Prädikatenlogik
3. Verifikationstechniken
    3.1 Verifikation mit Hoare-Tripeln
    3.2 Verifikation von Verzweigungen
    3.3 Verifikation von Schleifen
    3.4 Modulare und funktionale Programmierung
    3.5 Rekursion (Aktualisierung von Slide 5 am 14.06.)
4. Einführung in die Komplexitätstheorie (Beispieltabelle für Komplexitätsgrößen)

Organisatorisches:

Zum Ende jeder Woche werden von Maximilian Herold Übungsaufgaben gestellt.
Diese stehen auf seiner Homepage im Netz.
Dort gibt es auch Informationen zu den studentischen Tutorien,
in denen Verständnisschwierigkeiten geklärt werden können.

Die Übungen sollen selbständig bearbeitet und bei Herrn Herold eine Woche
nach Ausgabetermin abgegeben werden (mit Angabe des Übungstermins/Tutors).
Der Tutor / die Tutorin streicht die Fehler an und bespricht die wichtigsten Schwierigkeiten im darauf folgenden Tutorium.
Außerdem werden Fragen zum laufenden Vorlesungsstoff beantwortet.

Herr Herold hält Fr 14:00 Uhr - 15:15 Uhr, HS 6 eine große Übung ab,
in der ausgewählte Aufgaben vorgeführt werden.
Außerdem gibt es Übungen zum laufenden Vorlesungsstoff.
Spätestens zum Anfang dieser Übung sollen die bearbeiteten Übungsaufgaben
der Vorwoche abgegeben werden.

Literatur:

    Roland Backhouse: Programmkonstruktion und Verifikation, Hanser 1989 (vergriffen, Kopie ist im Asta erhältlich), ISBN 3-446-15056-0
    Englische Neuauflage: Program Construction: Calculating Implementations from Specifications, Wiley 2003, ISBN 0470848820

    Helmut Balzert: Lehrbuch Grundlagen der Informatik, Spektrum 2005 (2. Auflage), ISBN 3-8274-1410-5
    in unserer Bibliothek: Spektrum 1999 (1. Auflage), ISBN 3-8274-0358-8

    Heinz-Peter Gumm / Manfred Sommer: Einführung in die Informatik, Oldenbourg 2004 (6. Auflage), ISBN  3-486-27389-2

    Gerhard Goos: Vorlesungen über Informatik, Band1: Grundlagen und funktionales Programmieren, Springer 2000 (3. Auflage), ISBN 3-540-67270-2

    Michael Huth / Mark Ryan: Logic in Computer Science, Cambridge University Press 2004 (2. Auflage), ISBN 052154310X

    Uwe Schöning: Logik für Informatiker, Spektrum 2000 (5. Auflage), ISBN 3-8274-1005-3