 |
 |
 |
 |
 |
 |
|
|
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?
|
|
|
|
|