AuK/Effizienz von Programmen

Wiki-Quelltext dieser Seite.

<language>Python</language>
==Klassifikation von Problemen==
# Probleme, die sich einer Formalisierung entziehen
# Absolut unlösbare Probleme: Halteproblem, Wortproblem für Chomsky-Typ-0-Sprachen (FSuA)
# Praktisch unlösbare Probleme: "Baum aller Schachspiele"; AP-Funktion (Speicher und Zeit)
# 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:
# 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?
# Kann man diesen erforderlichen Zeitaufwand für typische algorithmische Entwurfsmuster angeben bzw. begrenzen?

Effizienzbegriff Zeit-/Speicherbedarf. Die (Zeit-)'''Effizienz''' eines Programmes ist umso besser, je *weniger Zeit* es zur Lösung eines Problems benötigt.

Wir beschränken uns auf die Betrachtung der '''Zeiteffizienz'''. Begründung: Trade-off (Tauschgeschäft) zwischen Zeit- und Speichereffizienz. Beispiel „Fibonacci-Zahlen, rekursiv“: Memoizing kostet zwar Speicher aber reduziert die Rechenzeit, da Mehrfachberechnungen vermieden werden. => Es reicht, sich nur mit der Zeiteffizienz zu beschäftigen.