Was können Computer? Das ist eine der fundamentalen Frage, auf die das Feld der theoretischen Informatik aufbaut. Diese LV bietet einen Überblick über die grundlegenden Techniken, um dieser Frage auf den Grund zu gehen. Hierzu formalisieren wir den Begriff der Berechenbarkeit durch Entwicklung verschiedener Werkzeuge und Modelle, wie formale Sprachen, Registermaschinen, und Turingmaschinen. Für jedes Berechenbarkeitsmodell betrachten wir lösbare und unlösbare Probleme, um die Leistungsfähigkeit von Computern im Allgemeinen verstehen und bewerten zu können.

Vortrag.

MotivationRegistermaschinenTuringmaschinenEndliche AutomatenKontextfreie SprachenDie These von ChurchUnberechenbarkeitEinführung in die Komplexitätstheorie

Mathematische Grundkenntnisse (Mengen, Sprachen, ..., einfache Beweistechniken).

Keine.

M. Sipser. Introduction to the Theory of Computation, 3rd ed. Cengage Learning, 2012.

Klausur am Ende des Semesters, Bearbeitungszeit: 100 Minuten, 90 Punkte.

Inhalt der Vorlesung

Note: Punkte1: >= 72 2: < 723: < 624: < 525: < 42