CS 460 - Theoretische Informatik
12 113 11460 CS 460 - Theoretische Informatik
Prof. Dr. R. Loogen
dienstags, 9:15-11:00 Uhr, HG 5 (Biegenstrasse)
mittwochs, 9:15-11:00 Uhr, HG 5 (Biegenstrasse)
Beginn: 17. April 2007
Übungen: mittwochs 14-16, HS II oder 16-18, SR I, donnerstags 14-16, SR I oder 16-18, SR I oder freitags 14-16, SR III, jeweils Lahnberge
Beginn: 2. Vorlesungswoche (25.- 27. April 2007)
Übungsgruppen:
Tutor(in)TerminRaumInfos
Bastian HacklerMi, 14-16 UhrSeminarraum X (Ebene D3, Lahnberge) In der letzten Vorlesungswoche wird diese Übung auf Donnerstag, den 19.7., 16-18 Uhr, SR X verschoben.
Jens SchömannMi, 14-16 UhrSeminarraum V (Ebene D5, Lahnberge))
Marc KochMi, 16-18 UhrSeminarraum I (Ebene D3, Lahnberge)
Michael SzaboDo, 14-16 UhrSeminarraum I (Ebene D3, Lahnberge)
Ulrike GeorgiDo, 16-18 UhrSeminarraum I (Ebene D3, Lahnberge))

Die Einteilung in Übungsgruppen wird durch Aushang in der zweiten Vorlesung bekanntgegeben.
Forum zur theoretischen Informatik: Hier können Aufgaben, Fragen, Verständnisprobleme, Vorlesungsstoff und Tutoriumsbelange diskutiert werden.
Betreute Gruppenarbeit: montags 16-18, SR III, Lahnberge
Beginn: 23. 04. 2007
Fachdidaktisches Begleitseminar: für Studierende im (modularisierten) Lehramtsstudiengang Informatik
Beginn: Do 14. Juni 2007, 18.00 Uhr, Hörsaal IV (Lahnberge) - Vorbesprechung: Do 3. Mai 2007, 13.30 - 14.15 Uhr, SR V (Ebene D5, Lahnberge)
Fachgebiet Klassifikation Semester Leistungspunkte Skript
Informatik Grundstudium >= 2 9 nein

Voraussetzungen: Mathematische Grundkenntnisse, wie sie etwa in der Vorlesung Mathematik I vermittelt werden
Querverbindungen: Theoretische Informatik, Software- und Systementwurf, Compilerbau, Effiziente Algorithmen
Scheinkriterien: Unbenoteter Leistungsnachweis:
  • Regelmäßige und aktive Teilnahme an den Übungen
  • Vorrechnen von mindestens zwei Aufgaben
  • Erwerb von mindestens 50% der erreichbaren Punkte in den Übungsaufgaben, 40 % für Lehramtsstudierende
  • höchstens zwei unbearbeitete Zettel
  • Erwerb von mindestens 8 Punkten in den beiden Leistungskontrollen
    Sonderregelung: Durch das Vorrechnen von mündlichen Aufgaben in den Übungsgruppen können pro vollständig und richtig vorgerechneter mündlicher Aufgabe 2 Sonderpunkte erworben werden, mit denen der Punktestand aus den Leistungskontrollen aufgestockt werden kann. Die Tutoren bestimmen, welche Aufgaben vorzurechnen sind. Dies bedeutet, dass diejenigen, die in den Leistungskontrollen weniger als 8 Punkte erworben haben, ab sofort verpflichtet sind, an den Übungsgruppen teilzunehmen.
Benoteter Leistungsnachweis: Zusätzlich Bestehen der Klausur am Semesterende
Achtung: Unbenotete Leistungsnachweise aus Vorjahren werden nicht anerkannt!
Übungsablauf:
  • Die Ausgabe der Übungszettel und die Abgabe der Hausaufgaben erfolgen dienstags vor der Vorlesung.
  • Die Abgabe ist in Zweiergruppen möglich.
  • Die Rückgabe und Besprechung findet in den Übungsgruppen statt.
  • Die Abgabe von abgeschriebenen Lösungen ergibt 0 Punkte für die Kopien und das Original


Termine: 1. Leistungskontrolle: Dienstag , 22. Mai 2007, 9.15 - 9.30 Uhr
2. Leistungskontrolle: Dienstag , 19. Juni 2007, 9.15 - 9.30 Uhr

Sondertutorium: Montag, 23. Juli 2007, 15 - 18 Uhr, SR III
Klausur: Mittwoch, 25. Juli 2007, 9.15 - 11.30 Uhr, Hörsaal A, Hörsaalgebäude der Chemie, Lahnberge
Klausureinsicht und -rückgabe: Donnerstag, 26. Juli 2007, 13.15 - 14.00 Uhr, Seminarraum V (Ebene D5, Lahnberge)
Grillen: Donnerstag, 26. Juli 2007, ab 15.15 Uhr vor Mo's Diner, Lahnberge (Grillgut /Salate und Geschirr bitte mitbringen, Getränke sind vorhanden)
Sondertutorium: Donnerstag, 27. September 2007, 17.00 - 19.00 Uhr, Seminarraum I, Lahnberge
Nachholklausur: Donnerstag, 4. Oktober 2007, 9.15-11.30 Uhr, Hörsaal B im Chemie-Hörsaalgebäude, Lahnberge
Klausureinsicht und -rückgabe: Freitag, 5. Oktober 2007, 11.45 - 12.15 Uhr, Seminarraum V (Ebene D5, Lahnberge)
Das Klausurergebnis ist durch Aushang auf der Ebene D5 (gegenüber dem Informatik-Sekretariat) bekanntgegeben. Zum Bestehen der Klausur sind 32 Punkte erforderlich. Von 24 Teilnehmern haben 14 bestanden.

Übungsblätter: Blatt 1, Abgabe: 24.04.2007
Blatt 2, Abgabe: 02.05.2007 (mittwochs wegen Feiertag am 1. Mai)
Blatt 3, Abgabe: 08.05.2007
Blatt 4, Abgabe: 15.05.2007
Blatt 5, Abgabe: 22.05.2007
Blatt 6, Abgabe: 29.05.2007
Blatt 7, Abgabe: 05.06.2007
Blatt 8, Abgabe: 12.06.2007
Blatt 9, Abgabe: 19.06.2007
Blatt 10, Abgabe: 26.06.2007
Blatt 11, Abgabe: 03.07.2007
Blatt 12, Abgabe: 10.07.2007, letztes Blatt in der Wertung
Blatt 13, Abgabe: 17.07.2007, Zusatzblatt

Zum Üben: Klausuren aus den Jahren 2003 und 2005

Literatur:
Links: Visual Automata Simulator (VAS)
Programme zur Theoretischen Informatik (Übersichtsseite der Univ. Mainz)
Fleißige Biber


Inhalt:
  1. Automatentheorie und formale Sprachen
    • Grammatiken, Chomsky-Hierarchie
    • Endliche Automaten und reguläre Sprachen
    • Kellerautomaten und kontextfreie Sprachen
    • Turingmaschinen und rekursiv aufzählbare Sprachen
  2. Berechenbarkeitstheorie
    • Berechenbarkeitsbegriff, Churchsche These
    • Unentscheidbarkeit
  3. Komplexitätstheorie
    • Aufwand von Berechnungen
    • Die Klassen P und NP
    • Reduktionen und NP-Vollständigkeit


Zuletzt geändert: Thursday, 04-Oct-2007 19:31:01 CEST