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.