• Aktuelles
• Allgemeine Informationen
• Organisation
• Termine
• Prüfungsangelegenheiten
• Literatur

• (18.01.18) Die Vorlesungen am Dienstag, 23.01.18, und Dienstag, 30.01.18, (Tag der Lehre) fallen aus.
• (15.01.18) Die heutige Zentralübung fällt aus. Die Vorlesung findet wie gewohnt statt.
• (15.01.18) Die Übungsgruppe heute 11-13 Uhr bei Sascha Brauer fällt aus. Die Teilnehmer können abweichend an der zur gleichen Zeit stattfindenden Übung bei Laurens Porzenheim in D1 312 teilnehmen.
• (05.12.17) Für Lehramtsstudenten die diese Vorlesung als Veranstaltung EBK-L im Modul Modelle und Algorithmen hören, ist die Vorlesung am 05.12.17 die letzte inhaltlich relevante.
• (07.11.17) Am Montag den 13.11.17 beginnt die Zentralübung um 13:45 und die Vorlesung um 14:45.
• (16.10.17) Die Übung bei Kathrin Bujna (Di 11-13 Uhr in D1 303) findet nicht statt. Bitte besuchen Sie stattdessen die Übung bei Nino Schnitker zur gleichen Zeit in D1 312.
• (05.10.17) Die Vorlesung findet am Montag, den 09.10.17 noch nicht statt. Damit ist der erste Vorlesungstermin Dienstag, der 10.10.17.
• (25.09.17) Der Übungsbetrieb beginnt am Mittwoch der ersten Vorlesungswoche.

• Dozent: Prof. Dr. Johannes Blömer
• Übungsorganisation: Sascha Brauer, Kathrin Bujna

Modulinformationen

• Veranstaltungsnr.: L.079.05302
• Kontaktzeit: V4 + Ü2 + ZÜ1
• Workload: 8 ECTS
• Zulassungsvoraussetzung für diese Veranstaltung ist der erfolgreiche Abschluss mindestens einer der Veranstaltungen Modellierung oder Datenstrukturen und Algorithmen. Diese Zulassungsvoraussetzung gilt für Studierende im Bachelorstudiengang Informatik und alle anderen Studiengänge, die sowohl Modellierung als auch Datenstrukturen und Algorithmen als Pflichtveranstaltungen enthalten.

Inhalt

Berechenbarkeit 

• Turingmaschinen
• entscheidbare und rekursiv aufzählbare Sprachen
• Churchsche These
• Unentscheidbarkeit
• Das Halteproblem
• Diagonalisierung
• Reduktionen

Komplexität

• Zeitkomplexität von Turingmaschinen
• Komplexitätsklassen
• Klassen P und NP
• NP-Vollständigkeit
• Das Erfüllbarkeitsproblem Boolescher Formeln
• Satz von Cook-Levin
• Polynomialzeit-Reduktionen
• Heuristiken
• Approximationsalgorithmen

Formale Sprachen

• reguläre Sprachen, reguläre Grammatiken
• endliche Automaten
• reguläre Ausdrücke
• Pumping Lemma
• kontextfreie Sprachen, kontextfreie Grammatiken
• Kellerautomaten
• Chomsky Normalform
• CYK-Algorithmus 

Anmeldung zu Übungsgruppen 

• Die Anmeldung zu den Übungsgruppen findet ausschließlich über koaLA statt!
• Die Anmeldung wird im Laufe der ersten Vorlesungswoche freigeschaltet.
• Ihre Übungsgrupen-Auswahl in PAUL wird ignoriert. Die Eintragung in die Übungsgruppen, die Sie in PAUL vorgenommen haben, gilt NICHT als Übunsgruppenanmeldung. Diese Anmeldung müssen Sie in koaLA vornehmen.
• Wer eine Übung besucht, in die er nicht in koaLA eingeteilt ist, wird vom Tutor aufgefordert werden, den Raum zu verlassen, falls die Anzahl der Teilnehmer zu groß ist.

Vorlesungen

• In der Vorlesung wird der Stoff anhand von Folienpräsentationen erklärt und mit zusätzlichen Beispielen weiter veranschaulicht.
• Vorlesungsfolien werden in koaLA veröffentlicht.

Übungen

• In den Übungen werden Lösungen für Präsenzaufgaben in Kleingruppen erarbeitet. Neben der Vorgehensweise bei der Lösung wird auch das korrekte Formulieren einer Lösung besprochen.
• Da der Vorlesungsstoff in den Übungen nur sehr eingeschränkt wiederholt werden kann, ist eine gute Vorbereitung der Übungen durch Nacharbeiten des Vorlesungsstoffes und Beschäftigung mit Haus- und Präsenzaufgaben notwendig.

Auftretende Probleme

• Sollten im Laufe des Semester Probleme entstehen, so wenden Sie sich zunächst an Ihre Übungsgruppenleitung. Sollte das Problem dadurch nicht gelöst werden können, so wenden Sie sich bitte an die Mitarbeiter für die Übungsbetreuung.
• Bei Problemen mit dem Studium an sich können Sie sich an die Studienberatung oder Ihren Mentor wenden.

Hausaufgaben

• Aufgabenzettel werden immer Mittwoch morgens über koaLA veröffentlicht. Die Aufgaben auf diesen Zetteln sind innerhalb der angegebenen Frist schriftlich (leserlich!) zu lösen und abzugeben.
• Für die Lösung sind Gruppen mit 2-3 Mitgliedern zu bilden. Wichtig dabei: Lösungen zu Aufgabenzetteln können nur in den Gruppen abgegeben werden, in denen wenigstens eines der Gruppenmitglieder angemeldet ist.
• Die Abgabe der Aufgabenzettel ist in den gekennzeichneten Fächern der orangefarbenen Schränke im D3-Flur. Bitte geben Sie auf Ihrer Lösung die Namen und Matrikelnummern ALLER Gruppenmitglieder an, die an der Lösung beteiligt waren!
• Die Aufgaben werden von den Übungsleitern korrigiert. Sollten Probleme mit der Korrektur auftreten, haben Sie eine Woche ab dem Tag der allgemeinen Rückgabe Zeit, diese Probleme zu beseitigen. Eine Anpassung der erzielten Punkte ist nach Ablauf dieser Woche nicht mehr möglich. 

Vorlesungen

• Montag, 14-16 Uhr, L2
• Dienstag, 16-18 Uhr, P7 2.01

Zentralübung

• Montag, 13-14 Uhr, L2

Übungen

• Montag, 11-13 Uhr, D1 312 (Laurens Porzenheim)
• Montag, 11-13 Uhr, D1 303 (Sascha Brauer)
• Dienstag, 11-13 Uhr, D1 312 (Nino Schnitker)
• Dienstag, 14-16 Uhr, D1 303 (Johanna Gördes)
• Mittwoch, 14-16 Uhr, D1 303 (Philipp Heinisch)
• Freitag, 11-13 Uhr, D1 312 (Philipp Heinisch)

Anmeldung 

• Die Anmeldung zu den Klausuren erfolgt über PAUL. Details über den Beginn der Anmeldephase für die erste und zweite Klausur können auch PAUL entnommen werden.
• Die Anmeldung einer mündlichen Ersatzprüfung, anstelle der Wiederholung einer zwei mal nicht bestandenen Klausur, ist nicht an diese Anmeldephasen gebunden, sondern kann jederzeit direkt beim Prüfungssekretariat stattfinden. Beachten Sie dabei, dass Sie erst nach der Anmeldung einen Termin für die mündliche Prüfung erhalten. In jedem Fall sollten Sie sich vor Ihrem dritten Versuch mit dem Dozenten in Verbindung setzen!

Zulassungsvoraussetzungen

Um zur Klausur zugelassen zu werden müssen folgende Voraussetzungen erfüllt sein:

• In mindestens 75% der Heimübungszettel jeweils wenigstens 20% der Punkte erreicht.
• Erfolgreicher Abschluss mindestens einer der Veranstaltungen Modellierung oder Datenstrukturen und Algorithmen. (Gilt für Studierende aller Studiengänge, die sowohl Modellierung als auch Datenstrukturen und Algorithmen als Pflichtveranstaltungen enthalten.)

Klausurtermine

• Erste Klausur: 21.02.2018 um 9:00 in SP2
• Zweite Klausur: 28.03.2018 um 9:00 im Hörsaal G

Noten-Bonus für Klausuren

Für beide Klausuren kann ein zusätzlicher Bonus durch eine Mindestpunktzahl aus den Hausaufgaben erworben werden. Der Bonus verbessert die Prüfungsnote um eine oder zwei Noten-Teilstufen gegenüber der Klausurnote, wenn die Klausur bestanden ist.

Für einen Bonus sind folgende Voraussetzungen zu erfüllen:

• Klausurnote 4.0 oder besser und
• mindestens 60% der Gesamtpunkte aus den Hausaufgaben für eine Notenstufe als Bonus (Verbesserung um eine Teilnote, z.B. von 2,7 auf 2,3) und
• mindestens 80% der Gesamtpunkte aus den Hausaufgaben für zwei Notenstufen als Bonus (Verbesserung um zwei Teilnoten, z.B. von 2,7 auf 2,0).

Im Rahmen von früheren Vorlesungen erworbene Bonusstufen werden NICHT gewertet.

Hilfsmittel

• ein DIN A4 Blatt
• beidseitig in der eigenen Handschrift beschrieben
• mit Namen und Matrikelnummer
• keine Kopien
• Für nicht Deutsch-Muttersprachler zusätzlich: ein Wörterbuch ohne handschriftliche Eintragungen.

Die Nutzung weiterer Hilfsmittel wird als Täuschungsversuch gewertet!

• Michael Sipser (2006): Introduction to the theory of computation. Cengage Learning; 3 edition, ISBN 113318779X, 978-1133187790
• John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman (2006): Introduction to automata theory, languages, and computation. Pearson; 3 edition, ISBN 0321455363, 978-0321455369
• Harry Lewis; Christos H. Papadimitriou (1997): Elements of the Theory of Computation. Prentice-Hall; 2nd edition, ISBN 0132624788, 978-0132624787
• Uwe Schöning (2008): Theoretische Informatik - kurzgefasst. Spektrum Akademischer Verlag; 5 edition, ISBN 3827418240, 978-3827418241