English website

Hörerkreis:

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

Termin der Vorlesung und großen Übung (im Wechsel): Do 17:00 Uhr - 18:15 Uhr, HS4

Es wird 7 Vorlesungen und 5 große Übungen geben: Die genauen Vorlesungstermine sind in der Vorlesungsgliederung unten angegeben. In den anderen Wochen der Vorlesungsperiode findet eine Übung statt. Die Übungen zu dieser Vorlesung werden mir betreut. Ich gebe insgesamt 5 Übungsblätter heraus und führe die Lösungen in der Regel eine Woche später in der großen Übung vor.

Zusätzlich steht für die Aufarbeitung des Lernstoffs in Kleingruppen der Tutor Alexander Hartung zur Verfügung. Er bietet jeweils einmal pro Woche einen Übungstermin an, der freiwillig ist und bei Verständnisschwierigkeiten besucht werden kann. Die Tutorien starten in der 4. Woche ab 27.04. Der Tutor korrigiert auch die Übungsaufgaben. Jeder Übungsteilnehmer muss sich aus diesem Grund in genau einem Tutorium eintragen, auch wenn er nicht an den Übungsstunden teilnimmt. Der Tutor hält 2 Übungsgruppen, die 2-wöchentlich im Wechsel stattfinden. Die Teilnehmerzahl an den Gruppen sollte ungefähr gleichverteilt sein, damit sich eine echte Kleingruppenarbeit einstellen kann. Daher werden die Gruppen getrennt verwaltet (auch wenn sie zum selben Tutor gehören). Details werden noch bekanntgegeben.

Die Übungsaufgaben sollen selbständig bearbeitet und in der nächsten großen Übung abgegeben werden (mit Angabe der Übungsgruppe). Der Tutor streicht die Fehler an und bespricht die wichtigsten Schwierigkeiten im darauf folgenden Tutorium. Außerdem werden Fragen zum laufenden Vorlesungsstoff beantwortet.

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!

Theoretische Informatik wird wie die Mathematik 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 den Tutor sehr zu empfehlen. Sollte sich dann herausstellen, dass Ihre Lösung nicht den Anforderungen entsprach, dann ist der Besuch von Großer Übung und Tutorenstunde genau das richtige Forum, um das zu verbessern.

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.

Diese Vorlesung wird im Vergleich zu früheren Semestern inhaltlich stark komprimiert, um sie für Erstsemester parallel zum restlichen Programm studierbarer zu machen: Es verbleiben lediglich die 2 Schwerpunkte Formale Logik und Verifikation von Programmen.

Das in der theoretischen Informatik ebenfalls wichtige Teilgebiet der Algorithmik und Komplexitätstheorie wird im 2. Semester im Rahmen der Vorlesung Automaten und Formale Sprachen behandelt, welche als Fortsetzung dieser Vorlesung angesehen werden kann. Daher sollten die beiden Vorlesungen trotz anderslautender Studienordnung möglichst nicht zugleich besucht werden, sondern hintereinander. Praktische Anwendungen von Algorithmik werden auch in der Vorlesung Programmiersprachen sowie systematischer in der Vorlesung Algorithmen und Datenstrukturen in C behandelt.

Der im Folgenden präsentierte Foliensatz fasst den Inhalt der Vorlesung zusammen. Er hat nicht den Anspruch eines Skriptes. Das in schwarz gesetzte Datum hinter dem Kapitel ist der Tag, an dem dieses Kapitel durchgenommen wird. Hier kann es zu geringfügigen Abweichungen im genauen Stoffumfang kommen.

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 (09.04.)

2. Logik

    2.1 Aussagenlogik (16.04.)

    2.2 Prädikatenlogik (30.04.) (Foliensatz geändert am 29.04.)

3. Verifikationstechniken

    3.1 Verifikation mit Hoare-Tripeln (14.05.)

    3.2 Verifikation von Verzweigungen (28.05.)

    3.3 Verifikation von Schleifen (18.06.)

    Vorbereitung für Syntax und Funktionsweise von Prozeduren in dieser Vorlesung
    3.4 Verifikation von rekursiven Prozeduren (02.07.) Übungsbeispiele hierzu

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