| Time & Place | Vorlesung / Gr. Übung: Montags und Dienstags, 13:15 Uhr - 14:45 Uhr (UP 3.007)
Kl. Übung: TBA | Gruppe | Termin (14-täglich) | Tutor | Raum | | 01 | Mittwoch, 11:30 - 13:00 | Youssef Naimi | IZ 305 | | 02 | Donnerstag, 09:45 - 11:15 | Max Bierwagen | IZ 305 | | 03 | Donnerstag, 15:00 - 16:30 | Erik Stahlmann | IZ 305 | | 04 | Donnerstag, 16:45 - 18:15 | Erik Stahlmann | IZ 305 | | 05 | Freitag, 09:45 - 11:15 | Jan Wasserscheidt | IZ 161 | | 06 | Freitag, 09:45 - 11:15 | Elias Kaiser | IZ 305 | | 07 | Freitag, 15:00 - 16:30 | Elias Kaiser | IZ 305 | |
| References | - U. Schöning: Theoretische Informatik - kurzgefasst. Springer, 2008.
- J. E. Hopcroft, R. Motwani, J. D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley Longman, 2002.
- M. Nebel: Formale Grundlagen der Programmierung. Vieweg+Teubner, 2012.
- M. Sipser: Introduction to the Theory of Computation. Cengage Learning, 2012.
- I. Wegener: Complexity Theory. Springer, 2005.
- D. Kozen: Automata and Computability. Springer, 1977.
- O. Goldreich: Computational Complexity. Cambridge University Press, 2008.
- A. M. Turing: On Computable Numbers, with an application to the Entscheidungsproblem.
|
Neuigkeiten - Es gibt die Möglichkeit eine englische Version in der Klausur zu erhalten. Diese werden allerdings nur nach Bedarf gedruckt. Solltest du eine englische Klausur schreiben wollen, sende bis zum 19.08. eine Mail an aschmidt@ibr.cs.tu-bs.de mit deinem Namen, Matrikelnummer, Studiengang und der Information, dass du in "Theoretische Informatik 2" die englische Klausur schreiben möchtest. (Unabhängig davon dürfen auch in der deutschen Klausur die Antworten in Englisch gegeben werden.)
- Die Vorlesung am 16.06. fällt krankheitsbedingt aus
- Die Vorlesung am 15.06. fällt krankheitsbedingt aus
- Die Übung der Gruppe 05 (Jan Wasserscheidt, Fr. 09:45 Uhr) verschiebt sich vom 19.06. auf 26.06.
- Die kleinen Übungen am Donnerstag, den 14.05., verschieben sich aufgrund des Feiertags um eine Woche nach hinten auf den 21.05.
- Bitte meldet euch auf der [Mailingliste] an.
- Die Einteilung in die Übungsgruppen wurde per Mail versandt. Solltet ihr keine Mail erhalten haben, sende bitte eine Mail an Arne Schmidt. Ein Gruppentausch ist in der Regel nur mit einem Tausch einer anderen Person möglich.
Klausur Die Klausur findet am 25.08. um 10:30 Uhr statt. Die Raumaufteilung wird 1-2 Tage vorher an dieser Stelle bekanntgegeben. Bitte seid 15 Minuten vorher anwesend. Mitzubringen sind: - Studierendenausweis
- Dokumentenechter Stift (u.a. kein Bleistift, Füller oder Rotstifte)
- Ein handschriftlich (nicht elektronisch oder über Tablet, o.Ä.), beidseitig beschriebenes Blatt DIN-A4.
- Wörterbuch (falls nötig) auf Papier ohne Notizen
Andere Hilfmittel sind nicht zugelassen. Papier wird von uns gestellt. Eine "Muster"-Klausur mit ausgewähltem Aufgabenpool ist verfügbar: [pdf] Hinweise zur Klausur Die Klausur geht insgesamt 120 Minuten und es sind 100 Punkte erreichbar. Sie ist allerdings als Überhangsklausur konzipiert, das heißt, man muss nicht jede Aufgabe lösen, um eine gute Note zu erhalten! Mit 40 Punkten hat man sicher bestanden. Bearbeitet die Klausur nicht einfach von vorn nach hinten, sondern schaut, welche Aufgaben einem am besten liegen und bearbeitet diese zuerst. Die Klausur wird 5 Teilgebiete mit jeweils 20 Punkten beinhalten, die ggf auf verschiedene Aufgaben aufgeteilt werden können. Die 5 Teilgebiete sind die folgenden: - Turing-Maschinen und Grammatiken (z.B. Modellieren, Analysieren)
- (Un-)Entscheidbarkeit (z.B. Reduktionen, PCP, SvR, ...)
- Komplexität 1 (L/NL oder P/NP) (z.B. Analyse, Reduktionen, Membership, Hardness, ...)
- Komplexität 2 (P/NP oder PSPACE/NPSPACE) (z.B. Analyse, Reduktionen, Membership, Hardness, ...)
- Weiterführendes (z.B. Einordnung neuer Komplexitätsklassen, Simulation von Turing Maschinen, ...)
Da ein Cheat-Sheet in die Klausur genommen werden darf, werden wenige bis gar keine Wissensfragen in der Klausur vorkommen. Der Fokus liegt auf Verständnisfragen, dem Anwenden von Theoremen und Algorithmen, sowie Transferwissen. Mailingliste Es gibt eine Mailingliste zur Veranstaltung. Bitte registriert euch dort. Wir versenden darüber Informationen. Es werden nur tubs-Adressen freigegeben. Bei Problemen wendet euch per Mail an Arne Schmidt. Hier geht es zur [Mailingliste]. |
