Grundbegriffe aus der Informatik

Was ist eigentlich ein Algorithmus?

Es gibt verschiedene Definitionen für Algorithmen. Hier soll zunächst eine weniger “saubere”, dafür zugängliche Version dargestellt werden. Im Allgemeinen können Algorithmen nicht nur von Computern ausgeführt werden, es muss sich nur um eine eindeutige Handlungsforschirft handeln, die folgende Eigenschaften besitzt:

1. Eindeutigkeit: ein Algorithmus darf keine widersprüchliche Beschreibung haben. Diese muss eindeutig sein.
2. Ausführbarkeit: jeder Einzelschritt muss ausführbar sein.
3. Finitheit (= Endlichkeit): die Beschreibung des Algorithmus muss endlich sein.
4. Terminierung: nach endlich vielen Schritten muss der Algorithmus enden und ein Ergebnis liefern.
5. Determiniertheit: der Algorithmus muss bei gleichen Voraussetzungen stets das gleiche Ergebnis liefern.
6. Determinismus: zu jedem Zeitpunkt der Ausführung besteht höchstens eine Möglichkeit der Fortsetzung. Der Folgeschritt ist also eindeutig bestimmt.

Die mathematisch korrekte Definition basiert auf dem Konzept der Berechenbarkeit und dem Modell der Turingmaschine. Dazu später mehr.

Laufzeit von Algorithmen

Der Begriff Laufzeit beschreibt in der Informatik die Zeitdauer, die ein Programm zur Bewältigung einer Aufgabe benötigt.

Die absolute Laufzeit eines Programms ist von verschiedenen Faktoren, wie z. B. der Rechenleistung des Computers abhängig. Um verschiedene Algorithmen unabhängig von der ausführenden Maschine bezüglich ihrer Effizienz vergleichen zu können, wird die sogenannte Asymptotische Laufzeit angegeben. Um diese zu beschreiben, wird die Landau-Notation verwendet.

Ein klassischer Fall, in dem die Laufzeit eine große Rolle spielt sind Sortieralgorithmen. Sortierung ist für viele andere Algorithmen relevant, aber auch für menschenlesbare Ausgabe großer Datenbanken. Hier ist wichtig, wie sich die Laufzeit mit zunehmender Anzahl zu sortierender Elemente verhält.

Der Algorithmus Bubble Sort schneidet hier mit O(n²) schlechter ab als Quicksort mit O(n log(n)). Bei Bubble Sort verhält sich die Lautfzeit quadratisch zu der Anzahl Elemente - sollen also doppelt so viele Elemente sortiert werden, braucht der Algorithmus (im Mittel) vier mal so lange, Quicksort ist für viele Elemente bedeutend zeiteffizienter (siehe Grafik).

Hier findet ihr Videos zur Visualisierung verschiedener Sortieralgorithmen: Plot und ungarischer Volkstanz

Das Halteproblem

Tatsächlich lässt sich im Allgeinen nicht vorhersagen, ob ein Algorithmus überhaupt zu einem Ende gelangt. Diese Fragestellung ist in der Informatik als Halteproblem bekannt.

Alan Turing gelang der Beweis, dass es keinen Algorithmus gibt, der diese Frage für alle möglichen Algorithmen und beliebige Eingaben beantwortet. Wie viele theoretische Betrachtungen, wurde der Beweis anhand einer abstrakten Maschine vollzogen - die bekannteste ist die von Turing selbst entworfene Turingmaschine.