Αποστολέας Θέμα: Παράδειγμα αλγορίθμου που δεν πληρεί το κριτήριο της αποτελεσματικότητας  (Αναγνώστηκε 11849 φορές)

Καρκαμάνης Γεώργιος

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 1087
Συμφωνώ με τον evry για το 1ο αλγόριθμο

Πιστεύω  πως και το 2ο δεν πληροί την καθ οριστικότητα.

nef

  • Θαμώνας
  • ***
  • Μηνύματα: 23
Τελικά νομίζω πως οι ορισμοί του βιβλίου για τα κριτήρια πληρότητας δεν πληρούν το κριτήριο της αποτελεσματικότητας.  Δεν είναι απλοί και αφήνουν πολλές ασάφειες  :) Υπάρχει κι άλλο ένα πρόβλημα: όταν οι μαθητές καλούνται να κατανοήσουν τα κριτήρια πληρότητας δεν ξέρουν ακόμα να σχεδιάζουν αλγορίθμους. Άντε λοιπόν να εξηγήσεις τι σημαίνει απλή εντολή.

Απ' το να καθόμαστε να αποκωδικοποιούμε την έννοια "απλή εντολή" υπάρχει ένα πιο απλός τρόπος που ακολουθώ και δεν έχω αντιμετωπίσει κανένα πρόβλημα μέχρι σήμερα. Εδώ θέλω να πω ότι καλούμαστε να παίξουμε ένα διπλό ρόλο κατα τη διάρκεια της διδασκαλίας. Πρώτον να είμαστε επιστημονικά επαρκείς και τεκμηριωμένοι και δεύτερον να ακολουθούμε τη γραμμή του σχολικού βιβλίου.

τι κάνω λοιπόν:

γράφω τον ορισμό του αλγορίθμου: Αλγόριθμος είναι μια πεπερασμένη σειρά ενεργειών, αυστηρά καθορισμένων και εκτελέσιμων σε πεπερασμένο χρόνο, που στοχεύουν στην επίλυση ενός προβλήματος.

Από τον ορισμό προκύπτουν 3 βασικά στοιχεία:
1. οι "ενέργειες" πρέπει να είναι αυστηρά καθορισμένες
2. οι "ενέργειες" πρέπει να είναι εκτελέσιμες
3. ο χρόνος δράσης τους να είναι πεπερασμένος

Από αυτά τα τρία προκύπτουν τα κριτήρια της καθοριστικότητας της αποτελεσματικότητας και της περατότητας αντίστοιχα.

Αν αγνοήσουμε προσωρινά το παράδειγμα του βιβλίου για τη διαίρεση με το μηδέν που το αναφέρει ως πρόβλημα καθοριστικότητας τα πράγματα είναι απλά:

Καθοριστικότητα σημαίνει κάθε εντολή να είναι σαφώς ορισμένη. Δηλαδή η μηχανή επεξεργασίας δεδομένων που θα κλιθεί να τη διεκπαιρεώσει να καταλάβει τι ζητάμε να γίνει. Μπορούμε να το συνδέσουμε με τη σωστή σύνταξη.

Η αποτελεσματικότητα έχει να κάνει με την εκτελεσιμότητα. Αν εκτελείται μια σαφώς ορισμένη εντολή. Εδώ θα κολλούσε το παράδειγμα με τη διαίρεση με το μηδέν. Ο εκτελεστής καταλαβαίνει τι πρέπει να κάνει, αλλά δε μπορεί να το εκτελέσει. ʼρα η εντολή είναι μη αποτελεσματική γιατί δεν παράγει αποτέλεσμα.

Όλο αυτό όμως χαλάει όταν το βιβλίο δίνει ως παράδειγμα παραβίασης της καθοριστικότητας τη διαίρεση με το μηδέν. Ταυτίζει δηλαδή την καθοριστικότητα με την αποτελεσματικότητα. Αυτό που μπορούμε να κάνουμε λοιπόν είναι όταν βρίσκουμε ένα πρόβλημα καθοριστικότητας σε έναν αλγόριθμο (συμπεριλαμβανομένης και της διαίρεσης με μηδέν) να θεωρούμε ότι είναι ταυτόχρονα και πρόβλημα αποτελεσματικότητας. Με αυτόν τον τρόπο οι μαθητές θα έχουν αντιληφθεί τη διαφορά των δύο κριτηρίων και θα απαντούν διπλωματικά αφού το βιβλίο τους ωθεί εκεί.

Επιπρόσθετα τα κριτήρια εισόδου και εξόδου ελέγχονται καθολικά στον αλγόριθμο. Εξετάζουμε αν ο αλγόριθμος έχει είσοδο και έξοδο. Συνεπώς για μία εντολή δεν έχει νόημα να εξετάζουμε αυτά τα δύο κριτήρια. Αν λοιπόν συναντήσουμε την εντολή α <--β και στο β δεν έχουμε φροντίσει να δώσουμε τιμή, παραβιάζουμε το κριτήριο της αποτελεσματικότητας. Πολύ απλά επειδή η εντολή αδυνατεί να εκτελεστεί.

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

Ν.Ε.Φ.