Schwerpunkt Theoretische Informatik

Die Schnittstelle zwischen Informatik und Mathematik bildet die Theoretische Informatik, die sich mit den Grundlagen beschäftigt. Hier wird abstrahiert von real exsistierenden Computern hin zu allgemeinen Rechnermodellen, die einerseits genauso mächtig, andererseits aber viel einfacher zu beschreiben sind als wirkliche Computer.

Das bekannteste solche Modell ist wohl die Turingmaschine. Entstanden sind diese Modelle - vor der Erfindung der modernen Computer - in der mathematischen Logik, die auch heute noch eine wesentliche Grundlage der Informatik bildet. An den formalen Modellen können mit mathematischen Methoden grundsätzliche Möglichkeiten und Grenzen von Computern untersucht werden. Zum Beispiel messen wir in der Komplexitätstheorie die Schwierigkeit eines Problems durch den Aufwand an Zeit oder Speicherplatz, den seine Lösung erfordert. Es zeigt sich, dass für viele wichtige Probleme dieser Aufwand immens hoch ist. Effizient lösbar sind dagegen durch endliche Automaten beschreibbare Probleme, die in der Automatentheorie untersucht werden.

Überhaupt ist die Entwicklungund Analyse effizienter Algorithmen ein zentrales Thema der Theoretischen Informatik. Neben den grundsätzlichen Methoden geht es uns auch immer um Algorithmen für konkrete kombinatorische Probleme aus der Praxis, z.B. für die Frequenzplanung von Sendernetzen oder die Beladung von Schwertransportern. Auch durch paralleles Rechnen kann man versuchen, schnelle Lösungen zu erzielen. Hierfür benötigt man spezielle Algorithmen, die Parallelität auf optimale Weise ausnutzen. Nicht für alle Probleme ist dies möglich.

Ein modernes Anwendungsgebit vieler Methoden aus der Theoretischen Informatik ist die Molekularbiologie. In der BioInformatik entwickelt man unter anderem aus algorithmischem Lernen, Grammatiken oder dynamischem Programmieren Verfahren zum Vergleich von DNS-Sequenzen oder zur Vorhersage der räumlichen Struktur von Proteinen.