14-Berechenbarkeit und Formale Sprachen previous clip next clip

Recording date 2011-12-05

Via

Passwort

Language

German

Faculty

Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung)

Format

lecture

  • Registermaschinen und Turingmaschinen als Modelle des Berechenbaren, die Churchsche These und unentscheidbare Probleme
  • NP-Vollständigkeit und das P-NP-Problem

  • Endliche Automaten

  • Grammatiken und die Chomsky-Hierarchie

  • Kontextfreie Grammatiken und Kontextfreie Sprachen

  • Kellerautomaten

Lernziele und Kompetenzen:

Die Studierenden

  • erwerben fundierte Kenntnisse über die Grenzen der Berechenbaren, insbesondere lernen sie, wie man beweist, dass bestimmte Aufgaben unlösbar sind bzw. dass sie vermutlich nicht schnell gelöst werden können;

  • lernen die wesentlichen Techniken kennen, mit denen man Programmiersprachen beschreiben und syntaktisch korrekte Programme erkennen kann;

  • erwerben fundierte Kenntnisse in den Beweis- und Analyse-Methoden der algorithmisch orientierten Theoretischen Informatik

Up next

Wanka, Rolf
Prof. Dr. Rolf Wanka
2011-12-09
Passwort
Wanka, Rolf
Prof. Dr. Rolf Wanka
2011-12-12
Passwort
Wanka, Rolf
Prof. Dr. Rolf Wanka
2011-12-16
Passwort
Wanka, Rolf
Prof. Dr. Rolf Wanka
2011-12-19
Passwort
Wanka, Rolf
Prof. Dr. Rolf Wanka
2011-12-23
Passwort

More clips in this category "Computer Science"

2016-12-08
IdM-login
protected  
2014-10-10
Studon
protected  
2019-06-30
Free
public  
2019-01-25
Free
public  
2019-04-17
Studon
protected  
2015-07-07
Free
public