2007 IEEE Workshop

Die Theoretische Informatik stellt die Grundlage für alle weiteren Teilgebiete im Bereich der Informatik dar. Sie beschäftigt sich vor allen Dingen mit der Abstraktion und Modellbildung, sowie grundlegenden Fragestellungen bei der Struktur und Verarbeitung, der Übertragung und Wiedergabe von Daten. Die Theoretische Informatik wird in weitere Forschungsgebiete gegliedert, dazu zählen die Kryptologie, die Automatentheorie, die formale Semantik und Log, sowie die Theorie der formalen Sprachen, wobei diese Liste keinen Anspruch auf Vollständigkeit erhebt.

Grundlagen zur Definition und Ausführung, sowie zur Prüfung von Programmen und Programmiersprachen stellt die Theoretische Informatik ebenfalls zur Verfügung. Dabei werden auch sehr heikle Problemstellungen untersucht und es soll versucht werden, hierbei die passenden Lösungsansätze zu finden.

Verbunden ist die Theoretische Informatik mit der Mathematik und der Logik gleichermaßen, entwickelt wurde sie bereits im 20. Jahrhundert. Dabei sind wichtige Begründer der Theoretischen Informatik Noam Chomsky oder Alonzo Church, um nur einige zu nennen.

Bei der Automatentheorie und den formalen Sprachen, denen in der Theoretischen Informatik eine besondere Bedeutung zukommt, geht es darum, dass Automaten formale Sprachen erkennen können. Gebildet werden diese aus der Grammatik. Bei der Automatentheorie werden insbesondere die unterschiedlichen Automaten oder Rechenmaschinen untersucht. Dabei geht es darum, welche Leistungen diese erbringen können und zu welchen Berechnungen sie in der Lage sind.

Des Weiteren gibt es in der Theoretischen Informatik die so genannte Chomsky-Hierarchie. Sie teilt die formalen Sprachen oder Programmiersprachen in verschiedene Klassen innerhalb einer Hierarchie ein. Dabei wird davon ausgegangen, dass die Programmiersprachen eine möglichst einfache Struktur aufweisen. Unterschieden wird in insgesamt vier verschiedene Klassen: Die regulären Sprachen, die kontextfreien Sprachen, die kontextsensitiven Sprachen und die rekursiv aufzählbaren Sprachen. Während die regulären Sprachen von endlichen Automaten erkannt werden können, werden kontextfreie Sprachen von Kellerautomaten erkannt. Linear beschränkte Turingmaschinen erkennen die kontextsensitiven Sprachen und allgemeine Turingmaschinen die rekursiv aufzählbaren Sprachen.

Auch die Berechenbarkeitstheorie ist ein wichtiger Aspekt der Theoretischen Informatik. Hier geht es um die Lösung von Problemen mit Hilfe von Algorithmen. Damit wird also die Berechenbarkeit von verschiedenen Problemen genauer untersucht. Speziell die innere Struktur der verschiedenen Problemstellungen wird dabei unter die Lupe genommen und die Probleme werden nach Lösbarkeit oder Unlösbarkeit klassifiziert.