Wir werden uns mit folgenden Teilgebieten befassen:

Berechenbarkeit

• Turingmaschinen
• entscheidbare und rekursiv aufzählbare Sprachen
• nicht entscheidbare Probleme
• Halteproblem
• nicht rekursiv aufzählbare Sprachen

Komplexitätstheorie

• Klassen P und NP, Zeitkomplexität
• NP-Vollständigkeit
• Satz von Cook
• Reduktion

Algorithmen: Behandlung NP-vollständiger Probleme

• Heuristiken: Backtracking, Branch and Bound
• Approximationsalgorithmen

Formale Sprachen

• reguläre Sprachen, reguläre Grammatiken
• deterministische und nicht-deterministische Automaten
• reguläre Ausdrücke
• Äquivalenzsatz
• Pumping Lemma
• kontextfreie Sprachen, kontextfreie Grammatiken
• Kellerautomaten
• Chomsky Normalform, Äquivalenzsatz
• CYK-Algorithmus

Modulinformationen

• Modul I.2.3 Einführung in Berechenbarkeit, Komplexität und formale Sprachen
• V4 + Ü2 + ZÜ1 SWS (Kontaktzeit)
• 8 ECTS-Credits (Workload)
• Für weiterführende Informationen siehe auch den → Eintrag im Modulhandbuch.

Veranstalter und Betreuer

 Friedhelm Meyer auf der Heide,  Joachim Gehweiler,  Matthias Fischer, Christian Heinzemann, Jost Baron, Marcus Märtens, Andreas Cord-Landwehr, Janna Arnold, Sebastian Osterbrink, Frank Hellweg, Daniel Warner

Termine

Vorlesung V4

• Di 09-11 G Meyer auf der Heide
• Do 14-16 G Meyer auf der Heide
• Erste Vorlesung am 16.10.07

Zentralübung ZÜ 1

• ZÜ 1 Do 13-14 G Meyer auf der Heide
• Erste Zentralübung am 25.10.07

Die Anmeldung zu den Übungsgruppen erfolgt mit  StudInfo

Miniklausuren

• MK 1: Di, 4.12.2007, anstelle der Vorlesung. Pünktlich zu Vorlesungsbeginn kommen reicht aus, die Miniklausur wird nicht die gesamte Vorlesungszeit in Anspruch nehmen.
• MK 2: Do, 31.1.2008, anstelle der Zentralübung

Ablauf Übungsbetrieb

• Woche i: Ausgabe: Di. 9:00 Uhr als pdf im Web
• Woche i+1: Abgabe: Di. 9:00 Uhr auf Papier in den Kästen auf D3 Campus
• Woche i+2: Rückgabe: ab Di.
• Das erste Übungsblatt erscheint am16.10.07

Jedes Übungsblatt enthält bis zu 4 Aufgaben. Die abgegebenen Lösungen werden korrigiert und bewertet. Musterlösungen zu ausgewählten Hausaufgaben werden in Absprache mit den Studierenden erstellt. Dazu werden die Betreuer Studierende ansprechen, die besonders gelungene Lösungen abgegeben haben, und diese Lösungen gemeinsam zu Musterlösungen weiterentwickeln und im Netz bereit stellen.
Im Anschluss an die Vorlesung erfolgt eine Klausur über den Stoff dieser Veranstaltung. Wenn Sie aktiv in den Übungen mitarbeiten und an den Miniklausuren (s.u.) teilnehmen, können Sie Ihre Note wie folgt verbessern (Bonus):

• Erreichen Sie mindestens 50% der Punkte der Hausaufgaben, so verbessert sich die Note um 1/3 Notenpunkt.
• Erreichen Sie mindestens 75% der Punkte der Hausaufgaben, so verbessert sich die Note um 2/3 Notenpunkt.
• Erstellen Sie eine Musterlösung, die im Netz zur Verfügung gestellt wird, so verdoppeln Sie ihre Punkte für diese Aufgabe.

Eine Verbesserung der Note 5 (nicht bestanden) ist nicht möglich. Als Bonusleistung zählen die Hausaufgaben dieser Veranstaltung. Bonuspunkte aus früheren Vorlesungen können nicht angerechnet werden.
Zur Selbstkontrolle werden zwei Zentralübungen für Miniklausuren verwandt. Diese Klausuren werden (Varianten von) Hausaufgaben beinhalten. Für die Erlangung der Bonuspunkte ist die Teilnahme notwendig, signifikanter Abweichung von den Ergebnissen der Hausaufgaben werden in einem Beratungsgespräch mit Herrn Meyer auf der Heide diskutiert.

Klausur

• Voraussetzung für die Teilnahme an der Klausur ist mindestens eine bestandene Klausur der Vorlesungen Modellierung oder Datenstrukturen und Algorithmen.
• Die Klausuranmeldung erfolgt teils online und teils über das jeweils zuständige ZPS. Beachten Sie dazu die Informationen [hier]Der Klausurtermin ist vom 21.2.2008 auf Dienstag den 26.2.2008 verschoben worden! Die Klausur findet um 15-18 Uhr in der Sporthalle statt.
• Anmeldezeitraum ist vom 17.12.07 bis 14.01.08, 14:00 h (mehr ...)
• Lehramt im Hauptstudium, Austauschstudierende, Studierende, die Leistungsnachweis anstreben melden sich per E-Mail direkt bei Matthias Fischer an mafi(at)upb.de. Mit den Angaben: Name, Vorname, Matrikelnummer, E-Mail
• Die zweite Klausur findet am 2.04.08 von 9-12 Uhr im AM+C1 statt. Aufgrund der Teilnehmerzahl werden voraussichtlich alle im Audimax schreiben.
• Die Ergebnisse der Klausur vom 26.2.2008 finden Sie [hier]. Die Einsichtnahme ist möglich am 12.3.08 um 8:30 Uhr im Raum F1.310. "nicht erteilt" bedeutet, dass zwar Übungspunkte für einen Bonusschritt erzielt wurden, jedoch ist die relative Abweichung zum Ergebnis der Miniklausur zu groß. Diese Studierenden können dazu das Gespräch mit Herrn Meyer auf der Heide suchen (am besten während der Klausureinsicht). Nach dem Gespräch wird entschieden, ob der Bonusschritt gegeben wird. Zum Bestehen der Klausur sind 18 Punkte notwendig, durch einen Bonusschritt kann das nicht geändert werden.
• Die bei der Klausureinsicht entstandenen Änderungen sind jetzt berücksichtigt und in die Note eingerechnet. Die Noten sind beim Prüfungssekretariat gemeldet.
• Die Ergebnisse der Klausur vom 2.4.2008 finden Sie [hier]. Die Einsichtnahme ist möglich am 14.5.08 um 10:00 Uhr, voraussichtlich im Raum F1.310 (Ankündigung vorher beachten). "nicht erteilt" bedeutet, dass zwar Übungspunkte für einen Bonusschritt erzielt wurden, jedoch ist die relative Abweichung zum Ergebnis der Miniklausur zu groß. Diese Studierenden können das Gespräch mit Herrn Meyer auf der Heide während der Klausureinsicht suchen. Nach dem Gespräch wird entschieden, ob der Bonusschritt gegeben wird. Zum Bestehen der Klausur sind 19 Punkte notwendig, durch einen Bonusschritt kann das nicht geändert werden.
• Die Ergebnisse der zweiten Klausur sind aktualisiert und dem Prüfungsamt gemeldet.

Skript

Das Skript ist während der Vorlesung sukzessive publiziert worden. Die aktuelle Version steht ist  hier

Literatur

Bücher über Berechenbarkeit, Komplexität und Formale Sprachen

• Introduction to the Theory of Computation, von: Michael Sipser, PWS, 1997
• Introduction to Automata Theory, Languages, and Computation, von: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Addsion Wesley, 2001 (auch übersetzt: Einführung in die Automatentheorie, Formale Sprachen und Komplexität, ... , Pearson Studium, 2002)
• Computers and Intractability - A Guide to the Theory of NP-Completeness, von: Michael R. Garey, David S. Johnson, W.H. Freeman & Company, 1997
• Theoretische Informatik, von: Christel Baier, Alexander Asteroth, Pearson Studium, 2002
• Theoretische Informatik - Eine algorithmenorientierte Einführung, von: Ingo Wegener, Teubner, 1993
• The Theory of Computation, von Bernard M. Moret, Pearson Education, 1998
• Computational Complexity, von: Christos H. Papadimitriou, Addison-Wesley, 1994
• Theoretische Informatk - kurzgefaßt, von: Uwe Schöning, Spektrum, akad. Verlag, Heidelberg, 1997
• Elements of the Theory of Computation, von: Harry R. Lewis, Christos H. Papadimitriou, Prentice Hall, 1998
• Theory of Computing - A Gentle Introduction, von: Efim Kinber, Carl Smith, Prentice Hall, 2001

Bücher über Algorithmen

• Introduction to Algorithms, von: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, The MIT Press, 2001
• Algorithmen, von: Robert Sedgewick, Pearson Studium, 2002 (übersetzt aus dem Englischen, gibt es in verschiedenen Ausgaben mit Schwerpunkten in Java, C, C++)
• Algorithmen, von: Ellis Horowitz, Sartaj Sahni, Springer, 1981
• The Design and Analysis of Computer Algorithms, von: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman Addison Wesley, 1974
• Data Structures and Algorithms, von: Alfred V. Aho, J. D. Ullman, J. E. Hopcroft, Addison Wesley, 1983
• Algorithmik - Theorie und Praxis, von: Gilles Brassard, Paul Bratley, Prentice Hall, 1993
• Approximationsalgorithmen: Eine Einführung, von Rolf Wanka, Vieweg+Teubner, 2006
• Approximation Algorithms for NP-Hard Problems, von: Dorit S. Hochbaum, Wadsworth Publishing Company, 1997
• Probability and Computing - Randomized Algorithms and Probabilistic Analysis, von: M. Mitzenmacher, E. Upfal, Cambridge University Press, 2005
• Randomized Algorithms, von: Rajeev Motwani, Prabhakar Raghavan, Cambridge University Press, 1995
• The Art of Computer Programming (Vol. 1-4), von: Donald E. Knuth, Addison Wesley, 1997/1998

Bücher über mathematische Hilfsmittel

Es geht bei diesen Büchern nicht direkt um Algorithmen und Komplexität. Die Bücher stellen aber gezielt alle mathematischen Mittel bereit, wie Informatiker sie für ihre Analysen und Berechnungen dabei benötigen: Asymptotic, Folgen, Reihen, Rekurrenz,...

• Concrete Mathematics, von: Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Addison-Wesley, 1994
• Diskrete Mathematik für Informatiker, von: Rod Haggarty, Pearson Studium, 2004
• Diskrete Strukturen I, von: Angelika Steger, Springer, 2001
• Diskrete Strukturen II, von: Thomas Schickinger und Angelika Steger, Springer, 2001