Formale Sprachen und Komplexität
Aktuelles
- Eine Einsicht in die Nachholklausur ist am Montag, den 22.10. von 13-14 Uhr im Raum L109 (Oettingenstr. 67) möglich.
- 20.8.: Die Anmeldung zur Nachholklausur ist bis zum 26.9. bei UniWorX möglich.
...
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. Andreas Abel, Dr. Ulrich Schöpp
- Tutoren/Korrektoren: Tobias Adolph, Jan Brusis, Isabella Cortrie, Sebastian Franz
Zeit und Ort
| Veranstaltung | Zeit | Ort | Beginn | Dozent |
|---|---|---|---|---|
| Vorlesung | Mi, 12 - 14 Uhr | Hörsaal B001 (Oettingenstr. 67) |
18.04.2012 | Hofmann |
| Vorlesung | Do, 16 - 18 Uhr | Hörsaal 003 (Schellingstr. 3) | 19.04.2012 | Hofmann |
| Übung | Mo, 14 - 16 Uhr | Raum B134 (Theresienstr. 39) | 23.04.2012 | Adolph |
| Übung | Di, 16 - 18 Uhr | Raum B015 (Hauptgebäude) | 24.04.2012 | Adolph |
| Übung | Mi, 10 - 12 Uhr | Mensa 042 (Leopoldstr. 13a) | 02.05.2012 | Cortrie |
| Übung | Do, 10 - 12 Uhr | Raum C113 (Theresienstr. 41) | 26.04.2012 | Cortrie |
Planung
Da die Vorlesung trotz der zwei wöchentlichen Vorlesungstermine insgesamt nur den Umfang von 3 SWS hat, entfallen einige Vorlesungstermine. Die Übungen finden dagegen durchgehend statt.
Zurzeit ist für die Vorlesung folgende Planung vorgesehen:
| Nr. | Datum | Thema | Hinweise |
| 1. | 18.04. | Einführung, Inhaltsübersicht, Chomsky Grammatiken (S1.1.1) |
|
| 2. | 19.04. | Sprachen, Chomsky-Hierarchie (S1.1.2) |
|
| 3. | 25.04. | Wortproblem, Typ-3 Sprachen, DEA (S1.1.3-S1.1.5,S1.2.1) |
|
| 26.04. | |||
| 4. |
02.05. | NEA, Potenzmengenkonstruktion (S1.2.2) |
|
| 5. |
03.05. | Potenzmengenkonstruktion (Korrektheit), Groesse von DEA vs NEA, reg.Gr.->NEA (S1.2.2) |
|
| 6. | 09.05. | regulaere Ausdruecke (S1.2.3) |
|
| 7. | 10.05. | Pumpinglemma (S1.2.4), Satz von Myhill - Nerode (S1.2.5), | |
| 8. | 16.05. | Wdh. Myhill - Nerode, Konstruktion des Minimalautomaten (S1.2.5) Abschlusseigenschaften Typ-3. (S1.2.6) |
|
| 17.05. | Himmelfahrt |
||
| 9. | 23.05. | Chomsky Normalform (S1.3.1), Pumpinglemma fuer CFL, CYK Algorithmus rekursiv (S1.3.2,S1.3.4) |
|
| 10. | 24.05. | CYK Algorithmus iterativ+Beispiel, Kellerautomaten, Abschlusseigenschaften Typ-2 (S1.3.3, S1.3.5) |
|
| 30.05. | |||
| 31.05. | |||
| 06.06. |
|||
| 07.06. |
Fronleichnam |
||
| 11. |
13.06. | Typ-1 Sprachen, Turingmaschinen (S1.4) |
|
| 12. | 14.06. | Intuitive Berechenbarkeit, Mehrbandmaschinen, LOOP Programme |
|
| 13. | 20.06. | WHILE-Programme, GOTO-Programme, Aequivalenz zu Turingmaschinen (S2.3) |
|
| 14. | 21.06. | Ackermannfunktion, mu-Rekursion (S2.5) |
|
| 15. | 27.06. | Halteproblem, Unentscheidbarkeit, Rekursiv Aufzählbar (S2.6) |
|
| 16. | 28.06. | Reduktionen, Postsches Korrespondenzproblem, Zeitkomplexität, |
|
| 17. | 04.07. | P, NP, NP Vollständigkeit (S3.1, S3.2) |
|
| 18. | 05.07. | Satz von Cook, weitere NP vollständige Probleme (S3.3) |
|
| 19. | 11.07. | Weitere NP vollständige Probleme, Forts. (S3.3) |
|
| 20. | 12.07. | Wiederholung |
|
| 18.07. | |||
| 19.07. |
Übungen
Hausaufgaben sind einzeln abzugeben, sie werden korrigiert und bewertet. Die Aufgaben sind einzeln mit der erreichbaren Punktzahl gekennzeichnet. Die erreichten Übungspunkte werden auf bestandene Klausuren als Bonus angerechnet. Dabei entsprechen 100% der Übungspunkte einem Bonus in Höhe von etwa einer Klausuraufgabe (10%-14%).
Hinweis: Sie dürfen Lösungsansätze mit Kommilitonen diskutieren, jedoch muss jeder Teilnehmer seine Abgabe allein erstellen. Plagiate werden geahndet.
Abgabe der Übungen jeweils bis Montag vormittag 12.00 Uhr elektronisch über UniWorX oder auf Papier im Übungskasten in der Theresienstr.
- In ersten den Übungen werden allgemeine Grundlagen behandelt.
Übungsaufgaben dazu finden Sie in Blatt 0 (ohne Abgabe). - Blatt 1: Abgabe bis 30.04.2012
- Blatt 2: Abgabe bis 07.05.2012
- Blatt 3: Abgabe bis 14.05.2012
- Blatt 4: Abgabe bis 21.05.2012; Hinweis zu Aufgabe 4-2
- Blatt 5: Abgabe bis 31.05.2012
- Blatt 6: Abgabe bis 11.06.2012
- Blatt 7: Abgabe bis 18.06.2012
- Blatt 8: Abgabe bis 25.06.2012
- Blatt 9: Abgabe bis 02.07.2012
- Blatt 10: Abgabe bis 09.07.2012
- Blatt 11: Abgabe bis 16.07.2012
- Blatt 12: Keine Abgabe
Literatur
Die Vorlesung richtet sich nach dem Buch
Uwe Schöning
Theoretische Informatik - kurz gefasst
Spektrum Akademischer Verlag
Alle relevanten Definitionen, Konzepte, Beispiele und Beweise werden an die Tafel geschrieben. Es gibt kein Skript!
Klausur
Erstklausur
- Klausureinsicht: 6.8.2012 10-11 Uhr im L109 in der Oettingenstr. 67
- Termin: 28. Juli 2012, 11.00 bis maximal 13.30 Uhr, Audimax, Uni Hauptgebäude
Nachholklausur
- Termin: 10. Oktober 2012, 10-13 Uhr, Hörsaal B 001, Oettingenstr. 67
Einlass (vorraussichtlich): 10.00 Uhr
Beginn: 10.15 Uhr
Keine Hilfsmittel erlaubt. Keine elektronischen Geräte am Platz!
Mitbringen:- Studienausweis oder Immatrikulationsbescheinigung
- Lichtbildausweis
- Stifte (dokumentenecht, nicht rot, nicht grün)
Weitere Informationen
- Fragen zur Vorlesung können in einem Diskussionsforum bei die-informatiker.net diskutiert werden.
Artikelaktionen