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:15-14:00 Uhr, HS IV (Raum 04A30,Lahnberge)
Beginn: 13. Oktober 2015

Übungen: Lukas Schiller
Beginn: 1. Vorlesungswoche (ab 15. Oktober 2015)

Die Anmeldung zu den Übungen erfolgt über das Ilias-System. Bitte treten Sie der Übungsgruppe Ihrer Wahl bis Mittwoch, den 14. Oktober 2014, 10.00 Uhr bei und geben Sie dabei einen alternativen Übungstermin an. Bei ungleichmäßer Auslastung der Übungsgruppen werden wir eine Umverteilung unter Berücksichtigung der von Ihnen angegebenen Alternativtermine vornehmen.

Übungsgruppen:
Tutor(in)TerminRaum
Do, 14-16 UhrSeminarraum XIII (Raum 03C45, Lahnberge) oder Seminarraum +2/0100 (Hörsaalgebäude, Biegenstraße)
Do, 16-18 UhrSeminarraum XIII (Raum 03C45, Lahnberge)
Fr, 10-12 UhrSeminarraum XIII (Raum 03C45, Lahnberge)

Fachdidaktisches Begleitseminar: für Studierende im (modularisierten) Lehramtsstudiengang Informatik
Vorbesprechung: Mittwoch, 21. Oktober nach der Vorlesung
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
Hinweis für Wiederholer: Einmal erbrachte Studienleistungen müssen nicht mehr wiederholt werden. Haben Sie bereits erfolglos an der Modulprüfung zum Modul "Theoretische Informatik" teilgenommen, sind Sie daher auf jeden Fall zur Wiederholungsprüfung zugelassen. Trotzdem empfehlen wir Ihnen, vor allem zur Klausurvorbereitung, aktiv an den Übungen teilzunehmen.
Anmeldung zur Modulprüfung: bis 15. Januar 2016
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 11. bis 15. Januar 2016 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 oder über das Ilias-System.
  • 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, 10. Februar 2016, 12.15 - 14.15 Uhr, HS A, Hörsaalgebäude der Chemie, Lahnberge
Bitte bringen Sie Ihren Studierendenausweis und den Personalausweis mit!
Klausureinsicht: Donnerstag, 11. Februar 2015, 14.15 - 15.15 Uhr, SR XIII (Raum 03C45, Lahnberge)

Wiederholungsklausur: Mittwoch, 16. März 2016, 12.15 - 14.15 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 wird kapitelweise im Ilias-System zur Verfügung gestellt.


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: Tuesday, 06-Oct-2015 19:38:09 CEST