Τι είναι ο έλεγχος ορθότητας ενός αλγορίθμου και ποιοι περιορισμοί υπάρχουν αυτού του ελέγχου;
Σκέψη / Μεθοδολογία: Χρησιμοποιούμε τον ορισμό και το παράδειγμα του Παραδείγματος3 (εύρεση ελαχίστου σε πίνακα) από το §5.2 για να δείξουμε τον βασικό περιορισμό: η επιτυχής δοκιμή δεν αποδεικνύει ορθότητα.
Λύση:
Απάντηση: Ο έλεγχος ορθότητας ενός αλγορίθμου είναι η διαδικασία επιβεβαίωσης ότι ο αλγόριθμος δίνει πάντοτε το σωστό αποτέλεσμα, για κάθε δυνατή είσοδο. Ο βασικός περιορισμός είναι ότι ο έλεγχος με δοκιμαστικές εκτελέσεις («τρέξιμο» του προγράμματος μερικές φορές) δεν αποδεικνύει την ορθότητα: ακόμη κι αν όλες οι δοκιμές δώσουν σωστό αποτέλεσμα, μπορεί να υπάρχει σφάλμα που εμφανίζεται μόνο σε συγκεκριμένες, σπανιότερες περιπτώσεις εισόδου (όπως στο Παράδειγμα3, όπου το σφάλμα εντοπίστηκε μόλις στην 4η δοκιμαστική εκτέλεση). Άρα δεν υπάρχει απόλυτη εγγύηση ορθότητας μέσω πιθανολογικού/δοκιμαστικού ελέγχου.
Πρόσεξε:
Να περιγραφεί ο τρόπος απόδειξης της ορθότητας ενός αλγορίθμου και να δοθεί ένα παράδειγμα απόδειξης ορθότητας αλγορίθμου.
Σκέψη / Μεθοδολογία: Δίνουμε τις δύο συνθήκες απόδειξης ορθότητας του §5.2 και χρησιμοποιούμε το παράδειγμα ανταλλαγής τιμών δύο μεταβλητών ως συγκεκριμένη απόδειξη.
Λύση:
t ← a, a ← b, b ← t.Απάντηση: Η απόδειξη της ορθότητας ενός αλγορίθμου πρέπει να περιλαμβάνει δύο συνθήκες: (α) απόδειξη ότι ο αλγόριθμος τερματίζει σε κάθε περίπτωση, και (β) απόδειξη ότι, όταν τερματίζει, οδηγεί σε αποδεκτά (σωστά) αποτελέσματα. Παράδειγμα: στον αλγόριθμο ανταλλαγής τιμών δύο μεταβλητών a και b με χρήση προσωρινής μεταβλητής t (t ← a, a ← b, b ← t), ο αλγόριθμος τερματίζει πάντα, αφού αποτελείται μόνο από τρεις διαδοχικές εντολές ανάθεσης χωρίς επανάληψη· και μετά την εκτέλεσή του ισχύει a = b₀ και b = a₀ (οι αρχικές τιμές των δύο μεταβλητών έχουν πράγματι ανταλλαγεί), άρα ικανοποιείται και η δεύτερη συνθήκη — ο αλγόριθμος είναι ορθός.
Πρόσεξε:
