08.079.050 Formale Sprachen und Berechenbarkeit

Lehrende/r: Univ.-Prof. Dr. Friederike Schmid

Veranstaltungsart: online: Vorlesung/Übung

Anzeige im Stundenplan:

Semesterwochenstunden: 4

Credits: 6,0

Unterrichtssprache: Deutsch

Min. | Max. Teilnehmerzahl: - | -

Voraussetzungen / Organisatorisches:
Die Veranstaltung findet digital in MS Teams statt. Bitte installieren Sie MS Teams und treten dem Team "Formale Sprachen und Berechenbarkeit SS21" mit dem Teamcode 1g4zypl bei.

Inhalt:

• Mathematische Grundlagen
  
• Formale Sprachen
  


• Reguläre Sprachen und endliche Automaten
  
• Kontextfreie Sprachen und Kellerautomaten
  


• Berechenbarkeit
  


• Turing-Maschine als Berechnungsmodell
  
• Weitere Berechnungsmodelle und Äquivalenz zur TM
  
• Church’s-These: TM-Berechenbarkeit stimmt mit der intuitiven Definition von Berechenbarkeit überein
  
• Unentscheidbare Probleme
  

Empfohlene Literatur:

• Dirk Hoffmann: Theoretische Informatik
  
• Asteroth/Baier: Theoretische Informatik
  
• Schöning: Theoretische Informatik - kurz gefaßt
  
• Hopcroft, Motwani, Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie
  
• Priese, Erk: Theoretische Informatik - Eine umfassende Einführung
  

Zusätzliche Informationen:
keine

Digitale Lehre:
Der Übungsbetrieb findet digital über MS Teams statt (Beitrittscode 1g4zypl). Alle weiteren Informationen, zum Beispiel wie die Vorlesung stattfindet, finden Sie dort.