Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2012 / Formale Sprachen und Komplexität


Inhaltsbereich

Formale Sprachen und Komplexität

Vorlesung, 3-std., Mi 12-14, Do 16-18, Hofmann; Übungen 2-std., Abel, Schöpp

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


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.


    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

         

        Artikelaktionen


        Funktionsleiste