• 08.10.2014: Die Nachklausur ist korrigiert. Sie können Ihren Punktestand im Online-KVV nachsehen. Das Notenschema findet sich hier. Bei Fragen oder Problemen wenden Sie sich bitte an mich.
  Die Nachklausureinsicht ist am Freitag, den 10.10.2014, von 14–15 Uhr im SR046. Bei dieser Gelegenheit kann auch die erste Klauur noch einmal eingesehen werden.
• 02.10.2014: Am 07.10. findet die Nachklausur statt. Außer Schreibutensilien ist lediglich ein beidseitig handbeschriebenes DIN-A4 Blatt als Hilfsmittel erlaubt. Bitte bringen Sie ein Personaldokument mit Lichtbild sowie Ihren Studierendenausweis mit. Die Klausur findet statt im HS 1a der Silberlaube, Habelschwerdter Allee 45. Bitte bis 12:05 Uhr die Plätze einnehmen. Klausurbeginn um 12:15 Uhr.
• 29.09.2014: Katharina Klost und Kristin Knorr bieten ein Wiederholungstutorium zur Vorbereitung auf die Nachklausur an. Es findet statt am Mittwoch, den 01.10.2014 von 14–16 Uhr im SR005.
• 22.09.2014: Die Nachklausur findet statt am Dienstag, den 07.10.2014, von 12–14 Uhr. Falls Sie an der Nachklausur teilnehmen möchten, melden Sie sich bitte bis zum 01.10.2014 im Online-KVV unter dem Exam Sign Up Tool an.
  ACHTUNG: Niemand wird automatisch angemeldet; es sollen sich bitte alle im KVV anmelden. Nur so erhalte ich eine zuverlässige Schätzung der Teilnehmerzahl.
• 18.07.2014: Die Klausur ist korrigiert. Sie können Ihren Punktestand im Online-KVV nachsehen. Das Notenschema findet sich hier. Bei Fragen oder Problemen wenden Sie sich bitte an mich.
  Die Klausureinsicht ist am Dienstag, den 22. Juli 2014, von 16:15–17:15 Uhr im SR 055. Die Nachklausur ist voraussichtlich am Dienstag, den 07. Oktober 2014 von 12–14 Uhr (UPDATE). Weitere Informationen zur Nachklausur werden zu gegebener Zeit bekannt gegeben.
• 09.07.2014: Am 16.07. findet die Klausur statt. Außer Schreibutensilien ist lediglich ein beidseitig handbeschriebenes DIN-A4 Blatt als Hilfsmittel erlaubt, das mit abzugeben ist. Bitte bringen Sie ein Personaldokument mit Lichtbild sowie Ihren Studierendenausweis mit. Die Klausur findet statt im HS Informatik, im HS ZIB und im großen Hörsaal der Physiologie. Die Hörsaalaufteilung ist folgendermaßen: Nachnamen A–D schreiben im Hörsaal der Informatik, Nachnamen E–L im Hörsaal des ZIB, Nachnamen M–Z im großen Hörsaal der Physiologie. Bitte bis 10:05 Uhr die Plätze einnehmen. Klausurbeginn um 10:15 Uhr.
• 08.07.2014: Relaunch der Website im neuen Design.
• 07.07.2014: Die volle Punktzahl zum erreichen der aktiven und regelmäßigen Teilnahme wurde auf 300 Punkte festgelegt.
• 02.07.2014: Das elfte Aufgabenblatt ist online. Dies ist das letzte Aufgabenblatt.
• 30.06.2014: Die Abstimmung über den Spickzettel ist vorbei. Es haben 91 Personen mit JA und 61 Personen mit NEIN gestimmt. Damit ist bei der Klausur ein beidseitig handbeschriebenes DINA4-Blatt mit Notizen zugelassen.
• 28.06.2014: Bitte melden Sie sich im Online-KVV zur Klausur an, falls Sie teilnehmen möchten.
• 26.06.2014: Die Probeklausur ist online.
• 20.06.2014: Abstimmung über einen Spickzettel in der Klausur: Falls der Poll im KVV für Sie nicht funktioniert, stimmen Sie bitte hier ab: JA NEIN.
• 18.06.2014: Am Mittwoch, den 25.06.2014, hält Christoph Benzmüller eine Gastvorlesung über Logik und Berechenbarkeitstheorie.
• 18.06.2014: Das zehnte Aufgabenblatt ist online. Dies ist das vorletzte Aufgabenblatt.
• 12.06.2014: Am Montag, den 23.06.2014, findet von 10–12 Uhr im HS Informatik eine unverbindliche Probeklausur statt. Falls Sie daran teilnehmen möchten, melden Sie sich bitte über das Sign-Up-Tool im Online-KVV dafür an.
• 11.06.2014: Das neunte Aufgabenblatt ist online.
• 04.06.2014: Das achte Aufgabenblatt ist online.
• 28.05.2014: Das siebte Aufgabenblatt ist online.
• 21.05.2014: Das sechste Aufgabenblatt ist online.
• 17.05.2014: Immer Donnerstags, von 18–20 Uhr findet jetzt im HS Informatik ein Wunschkonzert-Tutorium statt, in dem beliebige Fragen zur Vorlesung beantwortet werden.
• 14.05.2014: Das fünfte Aufgabenblatt ist online.
• 12.05.2014: Auf Anraten der Tutoren wurde der reguläare Ausdruck bei Aufgabe 4.1b) vereinfacht.
• 07.05.2014: Das vierte Aufgabenblatt ist online.
• 30.04.2014: Das dritte Aufgabenblatt ist online.
• 23.04.2014: Die Klausur findet statt am Mittwoch, den 16.07.2014 von 10–12 Uhr im HS Informatik, im HS ZIB und im großen Hörsaal der Physiologie, Arnimallee 22. Details werden zu gegebener Zeit bekannt gegeben.
• 23.04.2014: Das erste Zusatztutorium zum Thema Logik und Beweise von Max Willert findet statt am Dienstag, den 29.04.2014, von 08–10 Uhr im HS Informatik. Der zweite Termin findet voraussichtlich eine Woche später am selben Ort statt.
• 23.04.2014: Das zweite Aufgabenblatt ist online.
• 15.04.2014: Max Willert bietet ein Zusatztutorium zum Thema Logik und elementare Beweistechniken an. Interessierte tragen bitte ihre Terminwünsche im Doodle ein.
• 02.04.2014: Das erste Aufgabenblatt ist online.
• 01.04.2014: Der erste Vorlesungstermin ist der 16.04.2014. Die Tutorien beginnen in der zweiten Semesterwoche. Die Anmeldung zu den Tutorien wird über das Online-KVV erfolgen. Ggf. gibt es noch Anpassungen der Tutoriumsgröße zu Semesterbeginn.

Die Übungszettel werden ausschließlich online erscheinen und zwar hier auf dieser Seite.

Voraussetzungen

• Grundlegende Kenntnisse zu diskreter Mathematik werden vorausgesetzt.

Literatur

• Uwe Schöning: Theoretische Informatik – kurz gefasst, 5. Auflage, Spektrum Akademischer Verlag, 2008
  Alles Wichtige knapp und übersichtlich zusammengefasst. Gut zur Prüfungsvorbereitung, aber eventuell wenig motivierend.
• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexität, Pearson Studium, 3. Auflage, 2011
  Der Klassiker. Enthält viele motivierende Beispiele und Hintergrundwissen. Die deutsche Übersetzung ist eine Zumutung etwas gewöhnungsbedürftig.
• Ingo Wegener: Theoretische Informatik – Eine algorithmenorientierte Einführung, 3. Auflage, Teubner, 2005
  Sehr detailliert, manchmal etwas technisch.
• Michael Sipser: Introduction to the Theory of Computation, 2nd ed., Thomson Course Technology, 2006
  Sehr schön und verständlich geschrieben. Die hinteren Kapitel gehen weit über den Vorlesungsstoff hinaus. Für Leute mit Interesse an der theoretischen Informatik.
• Ingo Wegener: Kompendium theoretische Informatik – Eine Ideensammlung, Teubner, 1996
  Verständliche Darstellung der wesentlichen Ideen ohne großen technischen Ballast. Nicht unbedingt als Hauptquelle für die Veranstaltung geeignet, aber als Ergänzung empfohlen.
• Anil Maheshwari und Michiel Smid: Introduction to Theory of Computation, 2014 [link]
  Vorlesungsskript aus Kanada.
• Andrew Hodges: Alan Turing, The Enigma
  Biographisches zu einem Pionier der theoretischen Informatik.

Es wird eine Klausur am Ende des Semesters geben, sowie eine Ersatzklausur vor Beginn des nächsten Semesters. Dabei gilt die Freiversuchsregel. Das heißt, man kann die Ersatzklausur nutzen, um das Ergebnis aus der Hauptklausur zu verbessern (nur bei erstmaligem Absolvieren des Moduls).

Der Klausurtermin ist Mittwoch, der 16.07.2014, von 10–12 Uhr, im großen Hörsaal der Physiologie, Arnimallee 22, im HS ZIB und im Hörsaal Informatik.

Für den Scheinerhalt muss man

• regelmäßig an dem Tutorium teilnehmen (bei mindestens 80% der Termine);
• mindestens 60% der Punkte auf den Übungszetteln Erreichen und mindestens zweimal im Tutorium vorrechnen; und
• die Klausur mit mindestens 50% der Gesamtpunktzahl bestehen.

Die erfolgreiche Teilnahme am Übungsbetrieb und Teilnahme an der Klausur sind unabhängige Leistungen.

Die Scheine sind benotet. Die Note beruht nur auf den Klausurergebnissen.

Die Vorlesung findet statt Montag und Mittwoch, 10–12 Uhr, im großen Hörsaal in der Takustraße 9. Es gibt fünf Tutor_innen (Katharina Klost, Kristin Knorr, Justus Pfannschmidt, Simon Tippenhauer und Max Willert).

Sprechzeit des Dozenten: Dienstag 14–15 Uhr in Zimmer 114 und nach Vereinbarung

Die Übungszettel werden jede Woche hier verlinkt. Sie werden ausschließlich online erscheinen. Die normale Bearbeitungszeit ist von Mittwoch bis zum Freitag 9 Tage später. Die Zettel sind vor 10 Uhr in die entsprechenden Tutorenfächer einzuwerfen. Die Bearbeitung erfolgt in Zweiergruppen.

Übungszettel, die nach dem angegebenen Termin abgegeben werden, zählen als nicht bearbeitet.