Erweiterte Suche

Algorithmen

Prof. Dr. André Schulz
Dr. Franziska Jahnke, Marvin Landwehr, Stefan Marczinzik, Nico Vehren, Sebastian Wintz

Die Klausur fand am Donnerstag, 13. Februar, von 12 bis 14 Uhr im Hörsaalgebäude (M1, M2, M3) statt.
Die Klausureinsicht fand am 28.2. von 11 bis 12 Uhr in M6 statt. Eine Einsicht zu einem vorherigen Termin ist nicht möglich.

Die Nachklausur fand am Montag, 31. März, von 9 bis 11 Uhr im M1 statt. Die vorläufigen Ergebnisse hängen ab jetzt an der Tür von Raum 812 aus. Die Klausureinsicht findet am 4.4. von 11 bis 12 Uhr im Lichthof im 8ten Stock statt. Eine Einsicht zu einem vorherigen Termin ist nicht möglich.

Ich bitte alle Teilnehmer sich in folgende Mailingliste einzutragen!.
An Stelle eines Skriptes wird zur Vorlesung ein Wiki (link) angelegt. Alle Teilnehmer sind dazu eingeladen daran mitzuarbeiten.


Termine | Übungsblätter | Vorlesungen | Literatur


Die Vorlesung beginnt am 14. Oktober, die Übungen am 22./23. Oktober. Eine Sprechstunde zur Vorlesung findet mittwochs, 10-12 Uhr, bei Franziska Jahnke (Raum 812) statt.

Vorlesung Montags 08:00 - 10:00 M2 Einsteinstr. 62    
  Donnerstags 08:00 - 10:00 M2 Einsteinstr. 62  
Übungen Dienstag 14:00 - 16:00 M3 Einsteinstr. 62 Stefan Marczinzik Briefkasten 171
  Dienstag 16:00 - 18:00 N3 Orleans-Ring 10 Nico Vehren Briefkasten 173
  Mittwoch 08:00 - 10:00 M5 Einsteinstr. 62 Sebastian Wintz Briefkasten 164
  Mittwoch 14:00 - 16:00 SR7 Einsteinstr. 62 Marvin Landwehr Briefkasten 180
  Mittwoch 16:00 - 18:00 N3 Orleans-Ring 10 Marvin Landwehr Briefkasten 180

Termine | Übungsblätter | Vorlesungen | Literatur


Um zur Klausur zugelassen zu werden, muss man die wöchentlichen Übungsblätter erfolgreich bearbeiten und aktiv in den Übungen mitarbeiten. Eine Zulassung zur Klausur erreicht man, wenn man 50% der möglichen Punkte bei den Übungszetteln erzielt hat. Die Klausur findet am Ende des Semesters statt. Das Abschneiden bei der Klausur legt die Note fest.

Die Übungsaufgaben erscheinen jeweils montags auf dieser Seite. Die Abgabe ist am Donnerstag der darauf folgenden Woche um 12:00 Uhr. Es besteht die Möglichkeit der Bearbeitung in 2er-Gruppen.

Ab Montag, 14.10., um 12:00 Uhr können sich alle Teilnehmer für eine der fünf Übungsgruppen eintragen. Nutzen sie dazu das Kursbuchungssystem des Fachbereiches.

Zusatzaufgaben unbewertet (wird nicht abgegeben)
Übungsblatt 01 Abgabe: 24.10.2013
Übungsblatt 02 Abgabe: 31.10.2013
Übungsblatt 03 Abgabe: 07.11.2013
Übungsblatt 04 Abgabe: 14.11.2013
Übungsblatt 05 Abgabe: 21.11.2013
Übungsblatt 06 Abgabe: 28.11.2013
Übungsblatt 07 Abgabe: 05.12.2013
Übungsblatt 08 Abgabe: 12.12.2013
Übungsblatt 09 Abgabe: 19.12.2013
Übungsblatt 10 Abgabe: 09.01.2013
Übungsblatt 11 Abgabe: 16.01.2013
Probeklausur Abgabe (freiwillig): 24.01.2013 (gibt Bonuspunkte)
Zum Turing-Maschinen Simulator (link).

Termine | Übungsblätter | Vorlesungen | Literatur


#1: 14.10.13 Einführung, Vorlesungsinhalte, deterministischer endlicher Automat (DEA) Folien (kompakt) WikiLink
#2: 14.10.13 Nichtdeterministischer endlicher Automat (NEA), ?uivalenz DEA/NEA, Abschluss Regul?e Sprachen Folien (kompakt) WikiLink
#3: 21.10.13 Reguläre Ausdrücke, Satz von Kleene Folien (kompakt) WikiLink
#4: 24.10.13 Äquivalenz von Zuständen, Table-Filling Algorithmus, Myhill-Nerode Relation Folien (kompakt) WikiLink
#5: 28.10.13 Minimierung von DEAs, Satz von Myhill-Nerode Folien (kompakt) WikiLink
#6: 31.10.13 Minimierung nach Brzozowski, Pumpinglemma Folien (kompakt) WikiLink
#7: 4.11.13 Kontextfreie Grammatiken, Mehrdeutigkeit, Beziehung kontextfreie/reguläre Sprachen Folien (kompakt) WikiLink
#8: 11.11.13 Überführung in Chomsky Normalform, CYK-Algorithmus, Einführung Kellerautomaten Folien (kompakt) WikiLink
#9: 14.11.13 Sprachen von Kellerautomaten sind kontextfrei Folien (kompakt) WikiLink
#10: 18.11.13 Kontextfreies Pumpinglemma mit Anwendungen, Abschlusseigenschaften von kontextfreien Sprachen Folien (kompakt) WikiLink
#11: 21.11.13 Einband- und Mehrband-Turingmaschinen Folien (kompakt) WikiLink
#12: 25.11.13 Halbband-Turingmaschinen, Nichtdeterministische Turingmaschinen, Aufzählbarkeit, Church-Turing These Folien (kompakt) WikiLink
#13: 28.11.13 Abzählbarkeit, Existenz von nicht-erkennbaren Sprachen Folien (kompakt) WikiLink
#14: 02.12.13 Satz von Rice Folien (kompakt) WikiLink
#15: 05.12.13 ?uivalenz von Turingmaschinen, Linear beschr?kte Turingmaschinen und davon abgeleitete Sprachen Folien (kompakt) WikiLink
#16: 09.12.13 Nichtentscheidbarkeit des Postschen Korrespondenzproblem Folien (kompakt) WikiLink
#17: 12.12.13 Rekursionsthorem Folien (kompakt) WikiLink
#18: 16.12.13 Anwendungen Rekursionsthorem, Entscheidbarkeit logischer Theorien Folien (kompakt) WikiLink
#19: 06.01.14 Entscheidbarkeit logischer Theorien, Formale Beweissysteme Folien (kompakt) WikiLink
#20: 09.01.14 Gödels S?ze, Einführung Komplexitätstheorie, P Folien (kompakt) WikiLink
#21: 13.01.14 Komplexitätsklassen NTIME und NP Folien (kompakt) WikiLink
#22: 16.01.14 NP-Vollständigkeit, Satz von Cook-Levin (1.Teil) Folien (kompakt) WikiLink
#23: 20.01.14 Satz von Cook-Levin (2.Teil), NP-Vollständigkeit von CNFSAT und 3SAT Folien (kompakt) WikiLink
#24: 23.01.14 NP-Vollständigkeit von CLIQUE, Vertex-Cover, und gerichtetem Hamiltonkreis Folien (kompakt) WikiLink
#25: 27.01.14 NP-Vollständigkeit von Hamiltonkreis, TSP und SUBSET-SUM, Modell Registermaschine Folien (kompakt) WikiLink
#26: 30.01.14 Zusammenfassung Folien

Termine | Übungsblätter | Vorlesungen | Literatur


  • Michael Sipser,
    Introduction to the Theory of Computation,
    PWS Pub. Co., ISBN 978-0534947286 (1. Auflage)
    PWS Pub. Co., ISBN 978-0534950972 (2. Auflage)
  • Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D.
    Introduction to Automata Theory, Languages, and Computation (3rd ed.)
    Addison-Wesley. ISBN 8178083477.
    deutsche Ausgabe: Pearson, ISBN 978-3868940824
Impressum | © 2007 FB10 WWU Münster
Universität Münster
Schlossplatz 2 - 48149 Münster
Tel.: +49 (251) 83-0 - Fax: +49 (251) 83-3 20 90
E-Mail: