2424005 – Theoretische Grundlagen der Informatik

Im Gegensatz zu anderen Grundstudiumsvorlesungen werden in der theoretischen Informatik Themen behandelt, die weiter von den Anwendungen entfernt sind. Es geht um prinzipielle Fragestellungen, d.h. Fragen, die unabhängig von „Programmierungsaspekten“ oder „konkreten Rechnern“ sind: Gibt es Aufgaben, die von einem Rechner — unabhängig von der Art der Programmierung beziehungsweise von physikalischen und elektronischen Beschränkungen — nicht gelöst werden können? Welche Aufgaben können prinzipiell effizient (in vernünftiger Rechenzeit, mit vernünftigem Speicherplatzbedarf) gelöst werden?