Grundlagen der Theoretischen Informatik (Machines and Languages)

In der Veranstaltung wird  die klassische Theorie der Automaten und Algorithmen und ihrer Komplexität in ihren Grundzügen vorgestellt. Im Zentrum steht dabei das Studium der relativen Komplexität und Ausdruckskraft unterschiedlicher Klassen formaler Sprachen (Chomsky Hierarchie) einerseits und von Berechnungsmodellen (endliche Automaten, Kellerautomaten, Turingmaschinen) andererseits, sowie Äquivalenzen innerhalb beider Hierarchien. Das intuitiv einfach zu erfassende Modell der Turingmaschine als das Standardmodell der Berechenbarkeit und historischer Ausgangspunkt für die Entwicklung von programmierbaren Rechenmaschinen sowie der Lambda-Kalkül als Basis zum Verständnis vieler höherer Programmiersprachen stehen dabei im Mittelpunkt. Mit Turingmaschinen und anderer damit äquivalenter Berechnungsmodelle wird die Vorlesung zur Grenze dessen vorstoßen, was zumindest nach heutigem Wissen sowohl als praktisch als auch prinzipiell maschinell berechenbar angesehen werden muss. Über diese klassischen Modelle der Algorithmentheorie hinaus sollen, abhängig von der verfügbaren Zeit, ebenso  theoretische Grundlagen für nebenläufige und verteilte sowie für objektorientierte Programmierung eingeführt und an Beispielen diskutiert werden.