4.0 VU Theoretische Informatik 1 (185.167)

Lehrveranstaltungsleiter: Christian Fermüller, Gernot Salzer

Diese Lehrveranstaltung ist ein Pflichtfach in den Bakkalaureatsstudien der Informatik, im Bakkalaureatsstudium Informatikmanagement sowie im Universitätslehrgang Datentechnik gemäß dem ab Wintersemster 2001/2002 gültigen Studienplan.

Aktuelles

• Ergebnisse der Prüfungen vom 30.6.06, 11.10.06, 28.11.06, 16.1.07 & Übung 2006:

  Matrikelnummer:

  Siehe auch die Notenstatistik.

• Nächste Übung/Prüfung: Die Lehrveranstaltung des Sommersemesters 2006 ist abgeschlossen. Ab Sommersemester 2007 wird die Lehrveranstaltung unter dem neuen Titel Theoretische Informatik und Logik abgehalten.

Inhalt und Lehrziel

Ziel dieser Lehrveranstaltung ist die Vermittlung von Grundbegriffen der theoretischen Informatik und ihrer Methodik. Im Einzelnen werden folgende Themen behandelt.

• Formale Sprachen und Automaten
• Aussagenlogik
• Elemente der Prädikatenlogik
• Grundelemente der formalen Verifikation von Programmen (Hoare-Kalkül)

Lehrveranstaltungstermine

Vorlesungsteil

Der Vorlesungsteil umfasst 3 Semesterstunden und findet geblockt zu folgenden Terminen statt:

Erste Vorlesung SS 2006: Dienstag, 7. März 2006, 16:15, Audi Max.

Die Vorlesungen werden einige Male entfallen bzw. wird der Vorlesungsteil bereits früher enden, sodass trotz der vier Einheiten je Woche im Semesterschnitt der Lehrveranstaltungsankündigung entsprechend nur ein Umfang von 3 Semesterstunden erreicht wird.
Die Vorlesung entfällt am 6.4.2006, da der Hörsaal für Sponsionsfeiern benötigt wird, sowie am 23.5.2006, wegen einer unverschiebbaren Kommissionssitzung.

Übungsteil

Der Übungsteil umfasst 1 Semesterstunde und wird in Gruppen zu je 20 Studierenden abgehalten, die von TutorInnen betreut werden. Die Anmeldung erfolgte mittels Anmeldesystem ab Mittwoch, 8.3.2006, 10:00. (Zur Kontrolle: Details zum Zertifikat, das das Anmeldesystem verwendet.)

Erste Übungseinheit: in der Woche 20.-24.3.2006.

Lernbehelfe

• Skriptum: Erstverkauf am Do, 16.3.2006, 12:50 vor AudiMax, danach Verkauf im Sekretariat des Arbeitsbereichs (Favoritenstr. 9/Stiege 2/3.Stock) während der Sekretariatszeiten.
  Bezüglich Verwendbarkeit alter Skripten siehe die FAQs.
  Das Skriptum besitzt 140 Seiten und kostet € 12,-

• Ergänzungen zum Skriptum:
  Beispiele zum Nachweis der Nichtregularität von Sprachen,
  Alles, was Sie schon immer über die Sprache {a^pb^q | q teilt p} wissen wollten,
  NP-Vollständigkeit,
  Syntax-versus-Semantik (Neufassung von Kapitel 2),
  Alternativer Formelbegriff,
  (Zur Prädikatenlogik siehe die entsprechenden Vorlesungsfolien, ab Folie 211)
  Liste der bisher gefundenen Fehler im Skriptum

• Vorlesungsfolien (im PDF-Format): werden im Laufe des Semesters hier zur Verfügung gestellt.
  Folien 1–28 (Einleitung, reguläre Sprachen)
  Folien 29–41 (endliche Automaten)
  Folien 42–71 (reguläres Pumping Lemma, kontextfreie Grammatiken)
  Folien 72–83 (Kellerautomaten, Eigenschaften kontextfreier Sprachen, monotone Sprachen)
  Folien 84–110 (Turing-Maschinen, Komplexitätstheorie)
  Folien 111–137 (Syntax vs. Semantik)
  Folien 138–161 (Einführung in die Logik, Grundbegriffe der Aussagenlogik)
  Folien 162–210 (Aussagenlogik: Normalformen, Sequentialkalkül, Tableaux, Resolution)
  Folien 211–242 (Prädikatenlogik: Grundbegriffe, Tableaux)
  Folien 243–292 (Prädikatenlogik: Resolution)
  Folien 1–292 (alle Folien zusammen)

• Weiterführende Literatur. Eine kommentierte Liste mit Literaturhinweisen finden Sie hier.

• Alte Prüfungsangaben: siehe weiter unten.

• TU-Help-Forum: Bei Fragen zum Stoff können Ihnen vielleicht auch Ihre KollegInnen im TU-Help-Forum unter www.informatik-forum.at weiterhelfen.

• Interaktive Übungshilfen: Programme, z.B., zum Ableiten im Sequential- oder Tableaux-Kalkül oder zur Bearbeitung von endlichen Automaten gibt es hier.

Beurteilungsmodus

Die Gesamtbeurteilung ergibt sich aus der in den Übungseinheiten erbrachten Leistung sowie aus dem Ergebnis der Prüfung über den Vorlesungsteil. Eine genaue Beschreibung finden Sie hier.

Prüfungstermine

Die Beurteilung des Vorlesungsteiles erfolgt aufgrund einer schriftlichen Prüfung am Ende des Semesters. Im darauffolgenden Semester werden drei Ersatztermine angeboten, die bei Nichtbestehen oder Versäumen eines vorangehenden Termins oder auch zwecks Notenverbesserung wahrgenommen werden können. Für die endgültige Beurteilung wird der beste Antritt gewertet.

Bei der Prüfung zugelassene Unterlagen: Skriptum sowie Ausdruck der Vorlesungsfolien. Keine gelösten Übungsbeispiele!

SS 2006

• Haupttermin: Fr, 30. Juni 2006, 18:00-20:00

WS 2006/07

• 1.Nachtermin: Mittwoch, 11. Oktober 2006, 16:30-18:30, Audi Max
• 2.Nachtermin: Dienstag, 28. November 2006, 17:00-19:00, EI 7
• 3.Nachtermin: Dienstag, 16. Jänner 2007, 17:00-19:00, EI 7

Für alle Termine ist eine Anmeldung über TUWIS++ bis einen Tag vor der Prüfung erforderlich! Überprüfen Sie vor der Anmeldung, ob Sie zur Teilnahme an der Prüfung berechtigt sind: In der zweiten Spalte Ihres Übungsergebnisses (Überschrift "Prfg") muss ja stehen.

Prüfungsergebnisse

Geben Sie Ihre Matrikelnummer ein und klicken Sie auf "Suchen", um Ergebnisse von Prüfungen und Tests der letzten 6 Monate abzufragen; ohne Matrikelnummer erhalten Sie eine Aufstellung der vorhandenen Ergebnislisten. Ältere Ergebnisse erhalten Sie auf Anfrage beim Lehrveranstaltungsleiter.

Siehe auch die Notenstatistik.

Alte Prüfungsangaben

Die Angaben werden im PDF-Format zur Verfügung gestellt.

Gernot Salzer