Effizienz von Programmen

Klassifikation von Problemen

1. Probleme, die sich einer Formalisierung entziehen
2. Absolut unlösbare Probleme: Halteproblem, Wortproblem für Chomsky-Typ-0-Sprachen (FSuA)
3. Praktisch unlösbare Probleme: "Baum aller Schachspiele"; AP-Funktion (Speicher und Zeit)
4. Algorithmisch (inkl. mit Formel) lösbare Probleme

Effizienzbegriff

FALSCH: Computer sind immer schneller geworden, sodass die Effizienz von Programmen keine Rolle spielt

RICHTIG: Wir bestimmen den Aufwand (Ressourcenverbrauch: Zeit, Speicher) in Abhängigkeit von der Problemgröße n.

Zwei grundlegende Fragen, die wir uns in diesem Lehrgebiet stellen:

1. Wie können wir für konkrete Programme bestimmen (vorhersagen, i.S. einer Vorab-Leistungsgarantie), welche Rechenzeit sie zur Lösung eines Problems bestimmter Größe benötigen werden?
2. Kann man diesen erforderlichen Zeitaufwand für typische algorithmische Entwurfsmuster angeben bzw. begrenzen?