CS 460 - Theoretische Informatik
VL + UE 12 113 11460 CS 460 - Theoretische Informatik
Prof. Dr. R. Loogen
dienstags, 12:15-14:00 Uhr, HS IV (Raum 04A30,Lahnberge)
mittwochs, 12:20-14:00 Uhr, HS IV (Raum 04A30,Lahnberge)
Beginn: 15. Oktober 2013

Übungen: Dipl.-Inform. Medhi Zarrad
Beginn: 2. Vorlesungswoche (ab 24. Oktober 2013)

Übungsgruppen:
Tutor(in)TerminRaum
Andreas Voeth Do, 14-16 UhrSeminarraum XIII (Raum 03C45, Lahnberge)
Florian Fey Fr, 10-12 UhrSeminarraum IV (Raum 05A35, Lahnberge)
Jasper Olbrich Fr, 12-14 UhrHörsaal IV (Raum 04A30,Lahnberge)

Fachdidaktisches Begleitseminar: für Studierende im (modularisierten) Lehramtsstudiengang Informatik
Fachgebiet Klassifikation Semester Leistungspunkte Skript
Informatik Grundstudium >= 2 9 ja

Voraussetzungen: Mathematische Grundkenntnisse, wie sie etwa in der Vorlesung Mathematik I oder Mathematik II 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
Achtung: Unbenotete Leistungsnachweise aus Vorjahren werden nicht als Zulassung zur Abschlussklausur anerkannt!
Anmeldung zur Modulprüfung: bis 17. Januar 2014
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 13. bis 17. Januar 2014 per Liste an.
Bei Nichtbestehen der Klausur sind Bachelorstudierende automatisch zur Wiederholungsklausur angemeldet. Lehramtsstudierende müssen sich zur Wiederholungsklausur wieder anmelden.
Übungsablauf:
  • Die Ausgabe der Übungszettel erfolgt über das Ilias-System, in das Sie sich mit Ihrem HRZ-Login einloggen können.
  • Die Abgabe der Hausaufgaben erfolgt 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: Klausur: Mittwoch, 12. Februar 2014, 12.00 - 14.00 Uhr, HS A, Hörsaalgebäude der Chemie, Lahnberge
Bitte bringen Sie Ihren Studierendenausweis und den Personalausweis mit!
Klausureinsicht: Termin wird noch bekanntgegeben.

Wiederholungsklausur: Dienstag, 1. April 2014, 10.00 - 12.00 Uhr, HS A, Hörsaalgebäude der Chemie, Lahnberge
Bitte bringen Sie Ihren Studierendenausweis und den Personalausweis mit!

Unterlagen zur Vorlesung Übungsblätter, Folien und weitere Unterlagen werden über das ILIAS-System bereitgestellt:


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.


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
  3. Berechenbarkeits- und Komplexitätstheorie
    • Berechenbarkeitsbegriff, Churchsche These
    • Unentscheidbarkeit
    • Komplexitätstheorie


Zuletzt geändert: Monday, 28-Oct-2013 21:21:02 CET