Akademik

Algorịthmentheorie,

 

aus der formalen Logik hervorgegangene mathematische Theorie, die sich mit der Konstruktion, der Darstellung und der maschinellen Realisierung von Algorithmen befasst und die Grundlagen der algorithmischen Sprachen (Algorithmus) liefert. Sie erlangte u. a. für die Anwendung von Rechenautomaten Bedeutung, indem sie Verfahren entwickelte, mit deren Hilfe sich zu vorgegebenen Algorithmen gleichwertige Algorithmen anderer Struktur (z. B. mit kürzerer Rechenzeit oder kleinerer Anzahl von Rechenschritten) finden lassen und gleichzeitig auch die prinzipielle Lösbarkeit von mathematischen Problemen untersucht werden kann.

 

In der Komplexitätstheorie als wichtigem Teilgebiet der Algorithmentheorie wird für spezielle Algorithmen der Berechnungsaufwand (z. B. hinsichtlich Zeit- oder Speicherplatzbedarf) in Abhängigkeit von den jeweiligen Eingangsdaten untersucht und es werden Algorithmen hinsichtlich ihres Berechnungsaufwandes verglichen.

 

Literatur:

 

J. Loeckx: A. (1976);

 R. H. Güting: Datenstrukturen u. Algorithmen (1992);

 T. Ottmann u. P. Widmayer: Algorithmen u. Datenstrukturen (³1996);

 U. Schöning: Algorithmik. (2001).