Links und Funktionen
Sprachumschaltung

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


Inhaltsbereich

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

 


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


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

 

Artikelaktionen


Funktionsleiste