ΤΕΣΤ (ΑΣΚΗΣΕΙΣ) ONLINE
98 Tests / Διαγωνίσματα

Κεφάλαιο 05.2 – Σελίδα 102 – ΑΝΑΠΤΥΞΗ ΕΦΑΡΜΟΓΩΝ ΣΕ ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΟ ΠΕΡΙΒΑΛΛΟΝ Γ΄ ΛΥΚΕΙΟΥ – Απαντήσεις – Λύσεις

Ερωτήσεις - Θέματα για συζήτηση

Ερώτηση 7 (σελ. 102)

Τι είναι ο έλεγχος ορθότητας ενός αλγορίθμου και ποιοι περιορισμοί υπάρχουν αυτού του ελέγχου;

Σκέψη / Μεθοδολογία: Χρησιμοποιούμε τον ορισμό και το παράδειγμα του Παραδείγματος3 (εύρεση ελαχίστου σε πίνακα) από το §5.2 για να δείξουμε τον βασικό περιορισμό: η επιτυχής δοκιμή δεν αποδεικνύει ορθότητα.

Λύση:

  1. Ορίζουμε τον έλεγχο ορθότητας ως τη διαδικασία επιβεβαίωσης ότι ένας αλγόριθμος δίνει πάντοτε το σωστό αποτέλεσμα.
  2. Επισημαίνουμε τον βασικό περιορισμό: η επιτυχής εκτέλεση σε πεπερασμένο αριθμό δοκιμών δεν αποδεικνύει ότι ο αλγόριθμος είναι σωστός σε κάθε περίπτωση.
  3. Παραπέμπουμε στο Παράδειγμα3, όπου το σφάλμα εμφανίστηκε μόλις στην 4η δοκιμή, ενώ οι 3 πρώτες έδωσαν σωστό αποτέλεσμα.

Απάντηση: Ο έλεγχος ορθότητας ενός αλγορίθμου είναι η διαδικασία επιβεβαίωσης ότι ο αλγόριθμος δίνει πάντοτε το σωστό αποτέλεσμα, για κάθε δυνατή είσοδο. Ο βασικός περιορισμός είναι ότι ο έλεγχος με δοκιμαστικές εκτελέσεις («τρέξιμο» του προγράμματος μερικές φορές) δεν αποδεικνύει την ορθότητα: ακόμη κι αν όλες οι δοκιμές δώσουν σωστό αποτέλεσμα, μπορεί να υπάρχει σφάλμα που εμφανίζεται μόνο σε συγκεκριμένες, σπανιότερες περιπτώσεις εισόδου (όπως στο Παράδειγμα3, όπου το σφάλμα εντοπίστηκε μόλις στην 4η δοκιμαστική εκτέλεση). Άρα δεν υπάρχει απόλυτη εγγύηση ορθότητας μέσω πιθανολογικού/δοκιμαστικού ελέγχου.

Πρόσεξε:

  • Να τονιστεί ότι επιτυχείς δοκιμές δεν ισοδυναμούν με απόδειξη ορθότητας.

Ερώτηση 8 (σελ. 102)

Να περιγραφεί ο τρόπος απόδειξης της ορθότητας ενός αλγορίθμου και να δοθεί ένα παράδειγμα απόδειξης ορθότητας αλγορίθμου.

Σκέψη / Μεθοδολογία: Δίνουμε τις δύο συνθήκες απόδειξης ορθότητας του §5.2 και χρησιμοποιούμε το παράδειγμα ανταλλαγής τιμών δύο μεταβλητών ως συγκεκριμένη απόδειξη.

Λύση:

  1. Αναφέρουμε τις δύο απαραίτητες συνθήκες: (α) απόδειξη τερματισμού της εκτέλεσης, και (β) απόδειξη ότι ο τερματισμός οδηγεί σε αποδεκτό αποτέλεσμα.
  2. Ως παράδειγμα, θεωρούμε τον αλγόριθμο ανταλλαγής τιμών δύο μεταβλητών a, b με χρήση προσωρινής μεταβλητής t: t ← a, a ← b, b ← t.
  3. Δείχνουμε ότι τερματίζει πάντα (τρεις διαδοχικές εντολές ανάθεσης, χωρίς βρόχο) και ότι μετά την εκτέλεση ισχύει a = b₀ και b = a₀ (οι αρχικές τιμές έχουν πράγματι ανταλλαγεί), άρα ο αλγόριθμος είναι ορθός.

Απάντηση: Η απόδειξη της ορθότητας ενός αλγορίθμου πρέπει να περιλαμβάνει δύο συνθήκες: (α) απόδειξη ότι ο αλγόριθμος τερματίζει σε κάθε περίπτωση, και (β) απόδειξη ότι, όταν τερματίζει, οδηγεί σε αποδεκτά (σωστά) αποτελέσματα. Παράδειγμα: στον αλγόριθμο ανταλλαγής τιμών δύο μεταβλητών a και b με χρήση προσωρινής μεταβλητής t (t ← a, a ← b, b ← t), ο αλγόριθμος τερματίζει πάντα, αφού αποτελείται μόνο από τρεις διαδοχικές εντολές ανάθεσης χωρίς επανάληψη· και μετά την εκτέλεσή του ισχύει a = b₀ και b = a₀ (οι αρχικές τιμές των δύο μεταβλητών έχουν πράγματι ανταλλαγεί), άρα ικανοποιείται και η δεύτερη συνθήκη — ο αλγόριθμος είναι ορθός.

Πρόσεξε:

  • Να αναφερθούν και οι δύο συνθήκες (τερματισμός + ορθό αποτέλεσμα), όχι μόνο μία.