CS 460 - Theoretische Informatik
VL + UE 12 113 11460 CS 460 - Theoretische Informatik
Prof. Dr. R. Loogen
dienstags, 8:15-10:00 Uhr, HG 4 (Biegenstraße)
mittwochs, 8:15-10:00 Uhr, HG 4 (Biegenstraße)
Beginn: 12. April 2011
Die Vorlesung am Mittwoch, dem 13. Juli 2011 entfällt.
Übungen: Dipl.-Inform. Mischa Dieterle
Übungsgruppen:
Tutor(in)TerminRaumE-MailAchtung Terminverschiebungen
Marco Grebe Mi, 14-16 UhrSeminarraum 03C51 (Ebene C3, Lahnberge) grebe@mathematik Wegen des Tags der Informatik wird die Übung am 1. Juni auf 12-14 Uhr vorverlegt!
Wegen des Sport Dies wird die Übung am 8. Juni auf Donnerstag, den 9. Juni verschoben! Zeit und Ort bleiben.
Chengzhi Sun Mi, 16-18 UhrAchtung Neu ab 4. Mai: Seminarraum 03C51 (Ebene C3, Lahnberge) sunc@mathematik Wegen des Sport Dies wird die Übung am 8. Juni auf Donnerstag, den 9. Juni verschoben! Zeit und Ort bleiben.
Dominik Krappel Do, 12-14 UhrSeminarraum V (Ebene D5, Lahnberge)) krappel@mathematik An den beiden Feiertagen (2. Juni und 23. Juni) wird das Tutorium jeweils auf den darauffolgenden Freitag (3. Juni bzw. 24. Juni) verlegt. Zeit und Ort bleiben.
Florian Pfeiffer Fr, 10-12 UhrSeminarraum IV (Ebene D5, Lahnberge) pfeiffef@mathematik Wegen des Feiertags am 22.04. wird die erste Übung auf Donnerstag, den 21.04., 10-12 Uhr, SR IV vorverlegt.

Beginn: 2. Vorlesungswoche (ab 20. April 2009)
In der ersten Vorlesung erfolgt die Anmeldung zu den Übungen. Die Einteilung in Übungsgruppen wird durch Aushang in der zweiten Vorlesung bekanntgegeben.
Betreute Gruppenarbeit: donnerstags ab 16 Uhr, HS II, Lahnberge, freiwillige Teilnahme
Beginn: 14. 04. 2011 (1. Vorlesungswoche)
Fachdidaktisches Begleitseminar: für Studierende im (modularisierten) Lehramtsstudiengang Informatik
1. Termin: 6. Juli 2011, 18.00 Uhr, SR VII, Ebene D5, Lahnberge
2. Termin: 21. Juli 2011, 9.00 Uhr, SR VII, Ebene D5, Lahnberge
Fachgebiet Klassifikation Semester Leistungspunkte Skript
Informatik Grundstudium >= 2 9 ja

Voraussetzungen: Mathematische Grundkenntnisse, wie sie etwa in der Vorlesung Mathematik I vermittelt werden
Querverbindungen: Theoretische Informatik, Software- und Systementwurf, Compilerbau, Effiziente Algorithmen
Modulprüfung: Zulassungsvoraussetzungen für die Modulprüfung:
  • 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
Achtung: Unbenotete Leistungsnachweise aus Vorjahren werden nicht als Zulassung zur Abschlussklausur anerkannt!
Anmeldung zur Modulprüfung: bis zum 17. Juni 2011
Studierende in den Lehramtsstudiengängen und in den Bachelorstudiengägen des Fachbereichs (StPO 2010) müssen sich über das LSF/QIS-Portal zur Modulprüfung anmelden.
Alle anderen Studierenden melden sich bitte in den Vorlesungen oder in den Übungen der Woche vom 9. Juni bis zum 17. Juni per Liste an.
Bei Nichtbestehen der Klausur sind Sie automatisch zur Wiederholungsklausur angemeldet.
Termin der Modulprüfung: Klausur am 12. Juli 2011
Ü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 kopierten Lösungen führt zur Aufteilung der Punkte auf das Original und die Kopien.


Termine: Freiwilliger Zwischentest: 25. Mai 2011 zu Beginn der Vorlesung
Sondertutorium: Freitag, 8. Juli 2011, 16.00 Uhr (s.t.), HS I (Ebene A3, Lahnberge)
Klausur: Dienstag, 12. Juli 2011, 7.30 (!) - 10.00 Uhr, HG 5 (Biegenstraße)
Bitte bringen Sie Ihren Studierendenausweis und den Personalausweis mit!

Klausurergebnis: Von 53 Teilnehmern haben 20 bestanden.
Der nach der Klausureinsicht aktualisierte Aushang ist nur von Fachbereichsrechnern zugänglich.

Klausureinsicht: Donnerstag, 14. Juli 2011, 12.15 - 14.00 Uhr, Seminarraum V, Lahnberge
Diejenigen, die ihre Klausur am 14. Juli eingesehen haben, können ihre Klausur ab dem 15. August im Informatik-Sekretariat auf Ebene D5 abholen.
Nach der Wiederholungsklausur wird es einen weiteren Einsichttermin geben, bei dem auch Einsicht in die Klausur vom 12. Juli genommen werden kann.
Wiederholungsklausur: Mittwoch, 12. Oktober 2011, 10.00 - 12.00 Uhr, HS B, Hörsaalgebäude der Chemie, Lahnberge

Klausurergebnis: Von 32 Teilnehmern haben 4 bestanden.
Der Aushang ist nur von Fachbereichsrechnern zugänglich.

Klausureinsicht: Dienstag, 18. Oktober 2011, 18.00 - 18.30 Uhr, Seminarraum V, Lahnberge

Übungsblätter:
DateiAusgabedatumAbgabedatumZusatzmaterial
Blatt 1 12.04.2011 19.04.2011 -
Blatt 2 19.04.2011 26.04.2011 -
Blatt 3 26.04.2011 03.05.2011 -
Blatt 4 03.05.2011 10.05.2011 -
Blatt 510.05.2011 17.05.2011 -
Blatt 6 17.05.2011 24.05.2011 -
Blatt 7 24.05.2011 31.05.2011 -
Blatt 8 31.05.2011 07.06.2011 -
Blatt 9 07.06.2011 14.06.2011 -
Blatt 10 14.06.2011 21.06.2011 -
Blatt 11 21.06.2011 28.06.2011 -
Blatt 12 28.06.2011 05.07.2011 -
Klausur 2009 29.06.2011 - mündliche Bonusaufgaben


Literatur:
  • E. Hopcroft, R. Motwani, J.D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, 2. überarbeitete Auflage (Pearson-Studium (Addison-Wesley), 2002)
  • U. Schöning: Theoretische Informatik - kurzgefasst (Spektrum Akademischer Verlag, 2008, 5. Auflage)
  • G. Vossen, K.-U. Witt: Grundkurs der Theoretischen Informatik (Vieweg-Verlag, 5. Auflage, 2011)
  • D. W. Hoffmann: Theoretische Informatik (Hanser Verlag, 2009).
  • A. Asteroth, Chr. Baier: Theoretische Informatik (Pearson Studium, 2002).
Skript: Ein Skript kann im Informatik-Sekretariat auf D5 (Lahnberge) erworben werden.
Links: Visual Automata Simulator (VAS)
Programme zur Theoretischen Informatik (Übersichtsseite der Univ. Mainz)
Fleißige Biber


Inhalt:
  1. Einführung
  2. Automatentheorie und formale Sprachen
    • Grammatiken, Chomsky-Hierarchie
    • Endliche Automaten
    • Reguläre Ausdrücke und Sprachen
    • Eigenschaften regulärer Sprachen
    • Kontextfreie Sprachen
    • Turingmaschinen
    Zusammenfassungsfolie
  3. Berechenbarkeits - und Komplexitätstheorie


Zuletzt geändert: Thursday, 13-Oct-2011 18:44:29 CEST