Organisatorisches

Hörerkreis:
1. Semester aller Bachelor-Informatikstudiengänge (Inf, TInf, MInf, WInf)

Vorlesungstermin: Do 15:30 Uhr - 16:45 Uhr, AudiMax
Große Übung: Do 17:00 Uhr - 18:15 Uhr, AudiMax

Die Übungen zu dieser Vorlesung werden von Melanie Storm betreut. Zusätzlich stehen für die Aufarbeitung des Lernstoffs in Kleingruppen studentische Tutoren zur Verfügung. Diese bieten jeweils einmal pro Woche einen Übungstermin an (wird in der ersten Vorlesungswoche festgelegt).

Zum Ende jeder Woche stellt Frau Storm Übungsaufgaben. Diese stehen auf ihrer 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 Frau Storm 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.

Die große Übung wird von Frau Storm geleitet: Dort werden nach Abgabe der eine Woche zuvor gestellten Übungen durch die Studierenden ausgewählte Aufgaben davon vorgeführt. Außerdem gibt es Übungen zum laufenden Vorlesungsstoff.

Für einen erfolgreichen Studienbeginn gebe ich folgende Empfehlung:

Die Teilnahme an den Übungen ist freiwillig, ebenso die Abgabe und Lösung der Übungszettel. Wer die Übungsaufgaben nicht kontinuierlich bearbeitet, hat nach den Erfahrungen der letzten Semester keine Chance, die Klausur zu bestehen: Klausuraufgaben sind von derselben Art wie Übungsaufgaben!

Wie in Mathematik wird auch in Theoretischer Informatik vieles nicht gelernt, sondern verstanden. Dafür muss geübt werden.

Da viele Studienanfänger die Qualität ihrer Arbeit noch nicht gut einschätzen können, ist eine Abgabe und Kontrolle durch die Tutoren sehr zu empfehlen. Sollte sich dann herausstellen, dass Ihre Lösung nicht den Anforderungen entsprach, dann ist der Besuch von Großer Übung und Tutorium genau das richtige Forum, um das zu verbessern.

 

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. Inhalte und Umfang der Themen sind in diesem Semester dieselben wie im letzten. 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.

 

Vorlesungsgliederung

1. Einführung
2. Logik
    2.1 Aussagenlogik
    2.2 Prädikatenlogik
          Beispiel vom 01.11. in Prolog, Interpreter kann hier heruntergeladen werden.
3. Verifikationstechniken (Zusammenfassung dieses Kapitels für die Vorbereitung auf die Klausur)
    3.1 Verifikation mit Hoare-Tripeln
    3.2 Verifikation von Verzweigungen
    3.3 Verifikation von Schleifen (Beispiel: Euklidischer Algorithmus)
    3.4 Modulare und funktionale Programmierung
          (Vorbereitungsmaterial für die unterschiedlichen Typen der Parameterübergabe in Prozeduren)
    3.5 Rekursion
4. Einführung in die Komplexitätstheorie (Folien 11 und 12 aktualisiert am 17.01.)

 

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

David Harel / Yishai Feldman: Algorithmik, Springer 2006, ISBN 3-540-24342-9

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