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: 14. Oktober 2014

Übungen: Dipl.-Inform. Mischa Dieterle
Beginn: 2. Vorlesungswoche (ab 23. Oktober 2013)

Die Anmeldung zu den Übungen erfolgt über das Ilias-System. Bitte treten Sie der Übungsgruppe Ihrer Wahl bis Mittwoch, den 15. Oktober 2014, 14.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
Florian Fey Do, 14-16 UhrSeminarraum +2/0100 (Hörsaalgebäude, Biegenstraße)
Anneke Walter Do, 16-18 UhrSeminarraum XII (Raum 03C52, Lahnberge)
Katrin Sacher Fr, 10-12 UhrSeminarraum XII (Raum 03C52, Lahnberge)
gestrichen Fr, 12-14 UhrSeminarraum XII (Raum 03C52,Lahnberge)

Fachdidaktisches Begleitseminar: für Studierende im (modularisierten) Lehramtsstudiengang Informatik
Vorbesprechung: Mittwoch, 29. 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 16. Januar 2015
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 12. bis 16. Januar 2015 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, 11. Februar 2015, 12.15 - 14.15 Uhr, HS A, Hörsaalgebäude der Chemie, Lahnberge
Bitte bringen Sie Ihren Studierendenausweis und den Personalausweis mit!
Klausureinsicht: Donnerstag, 12. Februar 2015, 14.15 - 15.15 Uhr, SR XII (Raum 03C52, Lahnberge)

Wiederholungsklausur: Mittwoch, 1. April 2015, 12.15 - 14.15 Uhr, 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. Auf Wunsch können auch zu Vorlesungsbeginn gebundene Gesamtexemplare bestellt und nach ca. 2 Wochen 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: Tuesday, 03-Feb-2015 12:00:00 CET