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.

# Problem: große Unterschiede zwischen einzelnen Probleminstanzen in Bezug auf die Effizienzaussage (z.B. Suchverfahren, wenn das zu suchende Element ganz am Anfang einer Liste steht; Primzahlprüfung für $n$-stellige natürliche Zahlen)
# Problem: Einfache Lösungen (d.h. schnell ermittelbare Resultate für kleine Problemgrößen) skalieren nicht mit wachsender Problemgröße. D.h. kein linearer Zusammenhang.
# Problem: Wie können wir entscheiden, welche Option für ein Programm die effizienteste ist?

===Wie wird Zeiteffizienz gemessen?===
====&hellip; mit einem Timer====
          time module    import time
                         def c_to_f(c): 
                             return c*9/5+32
          start clock    t0 = time.clock()
          call function  c_to_f(100000)
          step clock     t1 = time-clock() - t0
                         print("t= ", t, ": ", t1, "s, ")

Nachteile:
* Zeitmessung ist inkonsistent
* Ziel: verschiedene Algorithmen bewerten
* Laufzeit variiert zwischen Alg., zwischen Implementationen, zwischen Computern auf denen sie laufen
* Ergebnisse sind unter Verwendung kleinerer Inputs nicht vorhersagbar.
* keine Aussage zum Verhältnis zwischen Eingabe und Rechenzeit

====… durch Zählen der Operationen====
Annahme, dass bestimmte elementare/atomare Operationen (z.B. math. Op., Zuweisungen, Zugriff auf Obj., Vergleiche) konstante Zeit beanspruchen. Dann zählt man die Operationen, die in Abhängigkeit von der Inputgröße ausgeführt werden.

        def mysum(x):
            total = 0                   1 Operation
            for i in range(x+1):        1 Operation, x-mal                                            
                total += i              2 Operationen, x-mal
        return total                    ---------------------
                                        1 + 3x Operationen

Ergebnis: Wenn ich die Eingabe verzehnfache, verdreißigfacht sich die Zahl der Elementaroperationen.

Diese Messmethode ist besser als die erste (Zeitmessung), hat Vorteile:
* ist unabhängig vom konkreten (vernetzten) Computer, auf dem das Programm läuft
* Ergebnis ist eine Relation zwischen Input und Zählung

und Nachteile:
* ist implementationsabhängig 
* keine klare Definition, welche Operationen zu zählen sind