Formale Sprachen und Komplexität
Vorlesung, 3-std., Mi 14-16, Do 12-14, Hofmann; Übungen 2-std., Schöpp
Aktuelles
- 13.9.: Magister-, Diplom- und Lehramtsstudenten können die Scheine jetzt im Sekretariat des Lehrstuhls TCS bei Frau Sigrid Roden abholen.
- 1.8.: Die Nachklausur findet am 6. Oktober statt. Eine Anmeldung ist bis zum 6. September über UniWorX möglich. Bitte melden Sie sich auch dann erneut an, wenn Sie bei der ersten Klausur schon angemeldet waren.
Archiv nicht mehr aktueller Einträge
Inhalt
Die Vorlesung behandelt Grundlagen der Theoretischen Informatik: Sie gibt Einführungen in die Theorie der formalen Sprachen und Automaten sowie in die Berechenbarkeits- und Komplexitätstheorie.
Organisation
- Umfang: 3+2 Semesterwochenstunden
- Vorlesung: Prof. Dr. Martin Hofmann
- Übungen: Dr. Ulrich Schöpp
- Tutoren/Korrektoren: Matthias Benkard, Jan Brusis, Charlotte Prieß
Zeit und Ort
| Veranstaltung | Zeit | Ort | Beginn |
|---|---|---|---|
| Vorlesung | Mi, 14 - 16 Uhr | Hörsaal A125 (Hauptgebäude) | 04.05.2011 |
| Vorlesung | Do, 12 - 14 Uhr | Hörsaal D209 (Hauptgebäude) | 05.05.2011 |
| Übung | Mo, 10 - 12 Uhr | Raum B046 (Theresienstr. 39) | 09.05.2011 |
| Übung | Mo, 14 - 16 Uhr | Raum C112 (Theresienstr. 41) | 09.05.2011 |
| Übung | Do, 10 - 12 Uhr | Raum 104 (Richard-Wagner-Str. 10) | 12.05.2011 |
|
Übung
|
Fr, 10 - 12 Uhr
|
Raum 110 (Richard-Wagner-Str. 10)
|
13.05.2011
|
Zeitplan der Vorlesung
Die stattgefunden Termine wurden aktualisiert und geben den tatsächlichen Vorlesungsverlauf wieder. Inhalte der zukünftigen Termine sind vorläufig.
| Datum | Inhalt |
| 04.05. | Einführung, Inhaltsübersicht, Chomsky Grammatiken |
| 05.05. | Sprachen, Chomsky-Hierarchie |
| 11.05. | Wdh Hierarchie, Wortproblem, Typ-3 Sprachen, DEA |
| 12.05. | NEA, Potenzmengenkonstruktion |
| 18.05. | Potenzmengenkonstruktion (Korrektheit), Groesse von DEA vs NEA, reg.Gr.->NEA |
| 19.05. | regulaere Ausdruecke, Pumpinglemma. |
| 25.05. | Bsp. zum Pumpinglemma, Konstruktion des Minimalautomaten. |
| 26.05. | Myhill - Nerode, Abschlusseigenschaften Typ-3, Chomsky NF. |
| 01.06. | Pumpinglemma fuer CFL, CYK Algorithmus. |
| 02.06. | keine Vorlesung |
| 08.06. | Kellerautomaten, Abschlusseigenschaften Typ-2. Typ-1 Sprachen, Abschlusseigenschaften. |
| 09.06. | Turingmaschinen (Einband, Mehrband) |
| 15.06. | keine Vorlesung |
| 16.06. | keine Vorlesung |
| 22.06. | keine Vorlesung |
| 23.06. | keine Vorlesung |
| 29.06. | LOOP Programme, WHILE Programme, GOTO Programme, Äquivalenz WHILE=GOTO=Turingmaschine |
| 30.06. | Primitive Rekursion, Äquivalenz zu LOOP Programmen |
| 06.07. | Ackermannfunktion, mu-Rekursion |
| 07.07. | Halteproblem, Unentscheidbarkeit, Rekursiv Aufzählbar |
| 13.07. | Zeitkomplexität, P, NP |
| 14.07. | NP Vollständigkeit, Satz von Cook |
| 20.07. | Weitere NP vollständige Probleme |
| 21.07. | Wiederholung |
| 27.07. | keine Vorlesung |
| 28.07. | keine Vorlesung |
Übungen
- In den Übungen in der Woche vom 9.5. werden allgemeine Grundlagen behandelt. Übungsaufgaben dazu finden Sie in Blatt 0 (ohne Abgabe).
- Blatt 1 — Abgabe bis 13.5.
- Blatt 2 — Abgabe bis 20.5.
- Blatt 3 — Abgabe bis 27.5.; Hinweise zur Ergebnisüberprüfung bei den Aufgaben 3-2 und 3-3
- Blatt 4 — Abgabe bis 3.6.
- Blatt 5 — Abgabe bis 10.6.
- Blatt 6 — Abgabe bis 17.6.
- Blatt 7 — Abgabe bis 24.6.
- Blatt 8 — Abgabe bis 1.7.
- Blatt 9 — Abgabe bis 8.7.
- Blatt 10 — Abgabe bis 15.7.
- Blatt 11 — Abgabe bis 22.7.
- Blatt 12 — keine Abgabe
Literatur
- Uwe Schöning: Theoretische Informatik - kurz gefasst, Spektrum Akademischer Verlag
Klausur
Erstklausur
- Termin: Samstag, 30. Juli, 18-21 Uhr, Hörsäle B101, A140 (Hauptgebäude)
- Klausureinsicht: Freitag, 19. August, 10:00-11:00 Uhr, Raum L109, Oettingenstr. 67
Nachholklausur
- Termin: Donnerstag 6. Oktober, 17-20 Uhr, Hörsaal N 120 (Hauptgebäude)
- Einlass: 17:15 Uhr
- Beginn: ca. 17:30 Uhr; Nach Beginn ist kein Einlass mehr möglich.
- Bearbeitungszeit: 120 Minuten
- Die Klausur findet ohne Hilfsmittel statt. Insbesondere sind keine schriftlichen Unterlagen, keine Taschenrechner oder andere Rechner, keine Mobiltelefone oder andere Kommunikationsmittel erlaubt.
- Erforderliche Unterlagen:
- gültiger Immatrikulationsnachweis für dieses Semester
- gültiger Personalausweis oder Pass mit Lichtbild
- Schreibzeug (keine Rot- und Grünstifte, kein Bleistift)
- Eigenes Papier ist nicht erforderlich und darf für die Prüfung nicht benutzt werden.
Weitere Informationen
- Fragen zur Vorlesung können in einem Diskussionsforum bei die-informatiker.net diskutiert werden.
Artikelaktionen