Aussagen über Algorithmen: (cont‘d)
Ø Aufwand/Effizienz
· Speicherplatzbedarf?
· Ausführungszeit?
· Abhängigkeit der Ausführungszeit von der Eingabe?
Der Korrektheitsbeweis für einen Algorithmus umfasst den
Beweis der Termination und den Beweis der Korrektheit!
Urfrage zur Algorithmisierbarkeit/Berechenbarkeit:
Was lässt sich algorithmisch lösen (berechnen)?
Gibt es einen Algorithmus, der in endlich vielen Schritten mit
der Ausgabe = f(Eingabe) stoppt, d.h. die (bekannte)
Abbildung f: (Eingabe) ¾¾® (Ausgabe) realisiert?