Theoretische Informatik
Unter Algorithmus ist ein Verfahren zu verstehen, das so stark formal spezifizert ist, dass es maschinell ausgeführt werden kann. Der Namen hat seinen Ursprung im Buch von Al Khvarizmi (arabischer Matematiker des IX. Jahrhundert) über einfache arithmetische Operationen.
In der Informatik ist ein Automat ein abstraktes Modell einer Maschine, die sich gemäß konkreter Regeln verhält. Ein Automat hat in der Regel einen inneren Zustand und bekommt eine Eingabe, die meistens Zeichen für Zeichen gelesen wird.
Berechenbarkeit ist eine Eigenschaft einer Funktion die zu gegebenen Eingaben die entsprechende Ausgabe berechnet.
Eine formale Sprache ist eine Menge von Wörtern(Alphabet) über eine endliche Menge von Objekten(Zeichen). Ein Wort ist eine Folge von Zeichen(String).
Unter einem Code wird im Allgemeinen eine Vorschrift verstanden, in der Symbole einer Darstellung in solche einer anderen übertragen werden. Bekannt sind vor allem Codes zur Verschlüsselung von Botschaften. Ein Code kann aus Daten, Ziffern, Zeichen, Buchstaben, usw. bestehen.
Die Komplexität eines Algorithmus gibt den maximalen Ressourcenbedarf an und wird oft in Abhängigkeit von der Länge der Eingabe angegeben und für große Längen asymptotisch abgeschätzt. Die Komplexität eines Problems ist durch den Ressourcenverbrauch eines optimalen Algorithmus zur Lösung dieses Problems definiert. Die betrachteten Ressourcen sind meist die Anzahl der benötigten Rechenschritte oder der Speicherbedarf. Es interessiert dabe jedoch nicht der Aufwand eines konkreten Programmes auf einem bestimmten Computer, sondern das Wachstum des Ressourcenbedarfs, beim Anstieg der zu verarbeiten Daten.
Die Graphentheorie untersucht die Eigenschaften von Graphen und ihre Beziehungen zueinander. Viele algorithmische Probleme können auf Graphen zurückgeführt werden, weshalb die Graphentheorie in der Informatik, insbesondere der Komplexitätstheorie, von großer Bedeutung ist. In der Graphentheorie ist ein Graph eine Menge von Punkten (Knoten oder auch Ecken genannt), die eventuell durch Linien (Kanten oder auch Bögen genannt) miteinander verbunden sind.
