News
Aktuell gibt es keine Neuigkeiten
Formale Sprachen & Automaten für Informatik-Lehramt Sekundarstufe I
-- Dieser Kurs richtet sich an Studierende des Lehramts für die Sekundarstufe I im Fach Informatik. --
-- This lecture is intended for students of the teaching degree program in computer science. --
Lernziele / Kompetenzen
Die Studierenden kennen verschiedene formale Sprachen und Automatenmodelle, sowie deren relative Stärken und Mächtigkeiten.
Außerdem verstehen sie den formalen Begriff der Berechenbarkeit und Nicht-Berechenbarkeit mit Hilfe von Turingmaschinen
als Rechenmodell und Grundideen der Komplexitätstheorie.
Inhalt
• Sprachen der Chomsky Hierarchie und ihre verschiedenen Definitionen über Grammatiken und Automaten
• Turingmaschinen, Determinismus und Nicht-Determinismus
• Entscheidbarkeit und Nicht-Entscheidbarkeit
• Komplexitätsklassen P und NP
Literaturhinweise
Schöning, U. (2012) Theoretische Informatik – kurz gefasst (5. Aufl.). Spektrum Akademischer Verlag. Heidelberg.