Theoretische Informatik

Ein Algorithmus ist eine endliche, eindeutig beschriebene Handlungsanweisung zur Lösung eines Problems. Er bekommt eine Eingabe, führt definierte Schritte aus und erzeugt eine Ausgabe.

Das klingt einfach, ist aber mächtig. Ein Algorithmus kann Zahlen sortieren, einen kürzesten Weg finden, eine Datei komprimieren, einen Text parsen oder eine Liste durchsuchen. Dafür braucht er kein Bewusstsein und kein Training. Er folgt einer präzisen Vorschrift.

In mathematischer Form können wir einen Algorithmus als Abbildung verstehen. Er nimmt Werte aus einer Eingabemenge und liefert Werte aus einer Ausgabemenge.

Algorithmen versteht man besser, wenn man sieht, wie sie arbeiten. Deshalb laufen die Beispiele hier nicht nur als Text, sondern als kleine Animationen. Du kannst sie abspielen, pausieren, zurücksetzen oder Schritt für Schritt durchgehen.

Der wichtige Punkt: Diese Verfahren sind keine neuronalen Netze. Sie lernen nicht aus Daten. Sie folgen exakt beschriebenen Regeln. Genau deshalb sind sie für NOVA trotzdem wichtig.

Ein Algorithmus kann korrekt sein und trotzdem praktisch unbrauchbar, wenn er zu langsam ist. Deshalb betrachtet man nicht nur, ob ein Verfahren funktioniert, sondern wie stark sein Aufwand mit der Eingabegröße wächst.

Die O-Notation beschreibt dieses Wachstum grob. Sie sagt nicht, wie viele Millisekunden ein Programm exakt braucht, sondern wie sich der Aufwand verhält, wenn n größer wird.

Graphprobleme sind überall: Routenplanung, Netzwerke, Abhängigkeiten, Webseiten, Dokumentverweise, Missionszustände und Wissensgraphen. Ein Graph besteht aus Knoten und Kanten.

Die Knoten können Orte sein. Die Kanten sind Verbindungen zwischen diesen Orten. Eine Kante kann ein Gewicht haben: Entfernung, Zeit, Energie, Risiko oder Kosten. Wenn Orte Koordinaten besitzen, kann die Distanz zwischen zwei Orten mit Vektorrechnung berechnet werden.

Vektoren sind geordnete Zahlenlisten. Sie sind eine der wichtigsten Brücken zwischen klassischer Informatik, Mathematik und moderner KI. Ein Bild kann als Vektor oder Tensor dargestellt werden. Ein Text kann über Embeddings als Vektor dargestellt werden.

Wenn wir Objekte als Vektoren darstellen, können wir Abstände, Ähnlichkeiten und Richtungen berechnen.

Eine formale Sprache ist eine Menge von Wörtern über einem Alphabet. Ein Alphabet ist eine Menge erlaubter Zeichen. Ein Wort ist eine endliche Folge solcher Zeichen. Eine Sprache ist eine Menge solcher Wörter.

Diese Reihenfolge ist wichtig: Erst verstehen wir, was eine formale Sprache ist. Dann ordnet die Chomsky-Hierarchie verschiedene Sprachtypen. Danach schauen wir uns konkrete Automaten und Grammatiken an.

Ein Automat ist ein Modell für ein System mit Zuständen. Er liest Eingaben Zeichen für Zeichen und wechselt abhängig vom aktuellen Zustand und dem gelesenen Zeichen in einen neuen Zustand.

Das ist extrem wichtig, weil viele Software-Systeme als Zustandsmaschinen verstanden werden können: Login-Flows, Missionsstufen, Roboterzustände, Parser, Dialogzustände oder Trainingsphasen.

Theoretische Informatik zeigt nicht nur, was Maschinen können. Sie zeigt auch Grenzen. Es gibt Probleme, für die kein allgemeiner Algorithmus existiert. Das berühmteste Beispiel ist das Halteproblem.

Das Halteproblem fragt: Gibt es einen Algorithmus, der für jedes beliebige Programm und jede Eingabe entscheidet, ob dieses Programm irgendwann anhält? Die Antwort ist nein.