Ξέρω, είναι ένα πολυσυζητημένο θέμα.... Υπάρχει κάποιο παράδειγμα όμως που να φαίνεται ότι δεν πληρείται το κριτήριο της αποτελεσματικότητας; Ένας μαθητής μου επιμένει καταλάβει τη διαφορά.... και έχει και δίκιο.
Ευχαριστώ.
Θα σου δώσω ένα απλοϊκό παράδειγμα σε ελεύθερο κείμενο το οποίο μπορεί εύκολα να παραβιάσει το κριτήριο της αποτελεσματικότητας :
Διάβασε 5 ακέραιους αριθμούς.
Υπολόγισε το μέσο όρο.
Εκτύπωσε το μέσο όρο.
Η διαδικασία-εντολή Υπολόγισε το μέσο όρο δεν είναι απλή για τον υπολογιστή και δεν μπορεί να εκτελεστεί απ'ευθείας. Πρέπει να αναλυθεί σε εύρεση αθροίσματος και στη συνέχεια σε διαίρεση με το πλήθος για να υπολογιστεί ο μέσος όρος. Έτσι πρέπει να γίνει :
Διάβασε 5 ακέραιους αριθμούς.
Υπολόγισε το άθροισμα τους
Διαίρεσε με το πλήθος τους
Εκτύπωσε το μέσο όρο
Μπορεί το παράδειγμα - επειδή είναι απλοϊκό για να το καταλάβει ευκολότερα ένας μαθητής - να μην είναι εντελώς σωστό αλλά αυτή πιστεύω είναι η ουσία του κριτηρίου της αποτελεσματικότητας.
Έχω την εντύπωση ότι μία εντολή του τύπου Υπολόγισε_μέσο_όρο(α1,α2,α3,α4,α5) δεν παραβιάζει κανένα αλγοριθμικό κριτήριο, καθότι μπορεί να εκτελεστεί πολύ εύκολα από "έναν άνθρωπο με ένα μολύβι και ένα τετράδιο" όπως αναφέρεται στο The art of computer programming από όπου οι συγγραφείς μετέφεραν όχι και τόσο καλά τα αλγοριθμικά κριτήρια.
Το θέμα έχει συζητηθεί ξανά https://alkisg.mysch.gr/steki/index.php?topic=1072.0
Ένα παράδειγμα που μου έρχεται στο μυαλό χωρίς πολύ σκέψη είναι :
χ <- Δώσε_μια_ρίζα_από_την_εξίσωση('χ^2-λογ(χ) + ρίζα(χ) - χ^1/4 + 2^χ = 0')
σε αυτή την περίπτωση η εντολή Δώσε_μια_ρίζα_από_την_εξίσωση δεν είναι και τόσο απλό να εκτελεστεί (νομίζω δηλαδή!) γιατί ίσως δεν έχει αναπτυχθεί ακόμη αλγόριθμος που να επιλύει τέτοιες εξισώσεις. Διατηρώ μια επιφύλαξη για το μαθηματικό κομμάτι γιατί δεν τα ξέρω και πολύ καλά.
Αυτό που καταλαβαίνω εγώ είναι ότι μια εντολή παραβιάζει την αποτελεσματικότητα εάν δεν έχει αναπτυχθεί άλλος αλγόριθμος ο οποίος να την εκτελεί (χωρίς να είναι απαραίτητο αυτός να περιλαμβάνεται στην λύση του προβλήματος που αντιμετωπίζουμε)
Με βάση τον (έστω και λάθος) ορισμό του βιβλίου μια εντολή παραβιάζει το κριτήριο της αποτελεσματικότητας όχι αν δεν έχει αναπτυχθεί αλγόριθμος που να την εκτελεί αλλά όπως λέει και το βιβλίο όταν "είναι απλή και εκτελέσιμη". Από αυτό εγώ καταλαβαίνω ότι πρέπει από πριν να "έχουμε πει" στον υπολογιστή (να έχουμε ορίσει στη γλώσσα του) τον τρόπο εκτέλεσης αυτής της εντολής.
ΥΓ. Ε ρε που φτάσαμε να διαφωνούμε για κάτι το οποίο είναι εξ'ορισμού λάθος
Παράθεση από: evry στις 28 Φεβ 2008, 09:25:19 ΜΜΥΓ. Ε ρε που φτάσαμε να διαφωνούμε για κάτι το οποίο είναι εξ'ορισμού λάθος
:) Δεν φταίμε μόνο εμεις πάντως!
Παράθεση από: evry στις 28 Φεβ 2008, 09:25:19 ΜΜΑπό αυτό εγώ καταλαβαίνω ότι πρέπει από πριν να "έχουμε πει" στον υπολογιστή (να έχουμε ορίσει στη γλώσσα του) τον τρόπο εκτέλεσης αυτής της εντολής
Τελικά υπάρχει ή όχι εκτέλεση και υπολογιστής ; :'(
Την εντολή χ <- ρίζα(4) ή την α <- ημ(π/2) ξέρει να την εκτελέσει; Σε τι αυτό διαφέρει από την Υπολόγισε_μέσο_όρο. Κάπου σιωπηλά υποθέτουμε ότι κάποιος το έχει πει στον υπολογιστή , ή τέλος πάντων στον εκτελεστή. Ποια εντολή είναι αρκετά απλή ώστε να είναι απλή ; Εκτός και αν μιλάμε μόνο για τις βασικές πράξεις... Πολύ μπέρδεμα βρε παιδί μου , απαπα!
Το παράδειγμα που ανέφερα μπορεί να είναι άστοχο για το κριτήριο της αποτελεσματικότητας αλλά έτσι όπως αυτό ορίζεται στο βιβλίο νομίζω ότι μπορεί να χρησιμοποιηθεί μόνο και μόνο για να κατανοήσει ένας μαθητής τι μπορεί να εννοεί.
Συμφωνώ με τον Ευριπίδη, ότι συζητάμε για κάτι το οποίο είναι κακά διατυπωμένο και δεν υπάρχει επαρκής επεξήγηση στο βιβλίο αλλά με βάσει αυτό καλούνται να εξεταστούν τα παιδιά και πρέπει να "ανακαλύψουμε" τι ακριβώς προϋποθέτει η αποτελεσματικότητα του βιβλίου ως κριτήριο.
Η αλήθεια είναι ότι και εμένα με απασχολεί αυτό το πρόβλημα. Πάντως σύμφωνα με τον Knuth η αποτελεσματικότητα του αλγορίθμου έγκειται στο να είναι όλα προσδιορισμένα επακριβώς και να μπορούν να εκτελεστούν από ένα άνθρωπο με μολύβι και χαρτί (art of computer programming 3rd edition σελ 6 :))
Έχω μια ερώτηση όμως την οποία δεν είμαι σίγουρο για τιν απάντηση της.
Ο παρακάτω αλγορίθμος.
Αλγόριθμος Δοκιμή
Διάβασε α
α<--α+β
Εμφάνισε α
Τέλος Δοκιμή
τι πρόβλημα παρουσιάζει από άποψη κριτηρίων;
Το β δεν είναι ορισμένο στον κώδικα του, άρα ο υπολογιστής δεν ξέρει να εκτελέσει την α<--α+β
Είναι πρόβλημα αποτελεσματικότητας ή καθοριστικότητας; Γιατί;
Παράθεση από: zenctheo στις 20 Ιαν 2009, 02:32:35 ΠΜ
Ο παρακάτω αλγορίθμος.
Αλγόριθμος Δοκιμή
Διάβασε α
α<--α+β
Εμφάνισε α
Τέλος Δοκιμή
τι πρόβλημα παρουσιάζει από άποψη κριτηρίων;
Το β δεν είναι ορισμένο στον κώδικα του, άρα ο υπολογιστής δεν ξέρει να εκτελέσει την α<--α+β
Είναι πρόβλημα αποτελεσματικότητας ή καθοριστικότητας; Γιατί;
Σαφήνειας Ορισμού (καθοριστικότητας όπως το έχει το βιβλίο).
Η αποτελεσματικότητα ζητάει να έχουμε "ψιλοκόψει" αρκετά την λύση σε βήματα που μαγειρεύονται και χωνεύονται εύκολα. Αλλιώς πχ η φράση "Βάλε τα στοιχεία του πίνακα Α στη σειρά, από το μικρότερο ως το μεγαλύτερο" θα θεωρείτο αλγόριθμος ταξινόμησης. Το ένα και μοναδικό βήμα όμως που περιγράφει δεν είναι απλό. Πετάει το μπαλάκι στον αναγνώστη (ή τον υπολογιστή) για να κάνει όλη τη δουλειά μόνος του, χωρίς να τον καθοδηγήσει ουσιαστικά. Οπως το καταλαβαίνω, ένας αναποτελεσματικός αλγόριθμος έχει δυσανάλογες απαιτήσεις από αυτόν που προσπαθεί να τον εκτελέσει.
Για να γυρίσουμε στο παράδειγμά σου, τα βήματα από μόνα τους δεν είναι ιδιαίτερα απαιτητικά (ανάγνωση, πρόσθεση, εκτύπωση). Αυτό που μας εμποδίζει είναι το άγνωστο της τιμής του
β. Όση εξυπνάδα και αν έχει ο αναγνώστης, και όση προσπάθεια και αν επενδύσει, δεν πρόκειται να βρει την τιμή του
β. Για την "καθοριστικότητα" το βιβλίο μιλάει για "καθορισμό χωρίς καμία αμφιβολία για τον τρόπο εκτέλεσης", και νομίζω ότι εκεί είναι το προβλημά μας. Το β το θεωρούμε initialized σε 0 ακολουθώντας τις συμβάσεις κάποιων γλωσσών Η/Υ; Θεωρούμε ότι θα έχει όποια τιμή είχε ξεμείνει στη θέση μνήμης που ανατέθηκε στη μεταβλητή ακολουθώντας άλλες συμβάσεις; Δηλώνουμε αμηχανία;
Αν αυτό έπεφτε σε θέμα πανελληνίων θα έπρεπε να αναφέρουμε ότι παραβιάζει και το κριτήριο της εισόδου αφού το β δεν έχει τιμή.
Ρίξτε μια ματιά στο link που στέλνω
https://alkisg.mysch.gr/steki/index.php?topic=944.msg4894#msg4894
Θεωρώ για τα δεδομένα της ΑΕΠΠ ,πως ένας αλγόριθμος δεν πληροί το κριτήριο της αποτελεσματικότητας όταν υπάρχει σε αυτόν μια εντολή που είναι λάθος γραμμένη συντακτικά ή χρησιμοποιεί σύμβολα που δεν έχουν οριστεί πράξεις γι'αυτά.
Για το δεύτερο που λες συμφωνώ, αλλά για το πρώτο με το συντακτικό λάθος? παραβιάζει σίγουρα την αποτελεσματικότητα?
Παράθεση από: Καρκαμάνης Γεώργιος στις 25 Μαΐου 2009, 12:48:16 ΠΜ
Θεωρώ για τα δεδομένα της ΑΕΠΠ ,πως ένας αλγόριθμος δεν πληροί το κριτήριο της αποτελεσματικότητας όταν υπάρχει σε αυτόν μια εντολή που είναι λάθος γραμμένη συντακτικά ή χρησιμοποιεί σύμβολα που δεν έχουν οριστεί πράξεις γι'αυτά.
Τελικά, οι παρακάτω αλγόριθμοι, ποιο αλγοριθμικό κριτήριο δεν ικανοποιούν;
α) Το κριτήριο της εισόδου;
β) Το κριτήριο της καθοριστικότητας;
γ) Το κριτήριο της αποτελεσματικότητας;
δ) Όλα τα παραπάνω;
Αλγόριθμος Κριτήριο1
π<-- 0
Όσο όνομα<>ΤΕΛΟΣ Επανάλαβε
Διάβασε βαθμός
Αν βαθμός=20 τότε
π<-- π + 1
Τέλος_Αν
Εκτύπωσε όνομα, βαθμός
Διάβασε όνομα
Τέλος_Επανάληψης
Εκτύπωσε π
Τέλος Κριτήριο1
Αλγόριθμος Κριτήριο2
Διάβασε όνομα
Όσο όνομα<>ΤΕΛΟΣ Επανάλαβε
Διάβασε βαθμός
Αν βαθμός=20 τότε
π<-- π + 1
Τέλος_Αν
Εκτύπωσε όνομα, βαθμός
Διάβασε όνομα
Τέλος_Επανάληψης
Εκτύπωσε π
Τέλος Κριτήριο1
Ιδού η απορία !!! :-\ :-\ :-\
ΠαράθεσηΓια το δεύτερο που λες συμφωνώ, αλλά για το πρώτο με το συντακτικό λάθος? παραβιάζει σίγουρα την αποτελεσματικότητα?
Το αναφέρω, γιατί θεωρώ πως μπορεί εύκολα να καταλάβει ένας μαθητής τι σημαίνει "Μια εντολή να είναι εκτελέσιμη"
Το 1ο της καθοριστικότητας, όχι της αποτελεσματικότητας ούτε της εισόδου
Συμφωνώ με τον evry για το 1ο αλγόριθμο
Πιστεύω πως και το 2ο δεν πληροί την καθ οριστικότητα.
Τελικά νομίζω πως οι ορισμοί του βιβλίου για τα κριτήρια πληρότητας δεν πληρούν το κριτήριο της αποτελεσματικότητας. Δεν είναι απλοί και αφήνουν πολλές ασάφειες :) Υπάρχει κι άλλο ένα πρόβλημα: όταν οι μαθητές καλούνται να κατανοήσουν τα κριτήρια πληρότητας δεν ξέρουν ακόμα να σχεδιάζουν αλγορίθμους. Άντε λοιπόν να εξηγήσεις τι σημαίνει απλή εντολή.
Απ' το να καθόμαστε να αποκωδικοποιούμε την έννοια "απλή εντολή" υπάρχει ένα πιο απλός τρόπος που ακολουθώ και δεν έχω αντιμετωπίσει κανένα πρόβλημα μέχρι σήμερα. Εδώ θέλω να πω ότι καλούμαστε να παίξουμε ένα διπλό ρόλο κατα τη διάρκεια της διδασκαλίας. Πρώτον να είμαστε επιστημονικά επαρκείς και τεκμηριωμένοι και δεύτερον να ακολουθούμε τη γραμμή του σχολικού βιβλίου.
τι κάνω λοιπόν:
γράφω τον ορισμό του αλγορίθμου: Αλγόριθμος είναι μια πεπερασμένη σειρά ενεργειών, αυστηρά καθορισμένων και εκτελέσιμων σε πεπερασμένο χρόνο, που στοχεύουν στην επίλυση ενός προβλήματος.
Από τον ορισμό προκύπτουν 3 βασικά στοιχεία:
1. οι "ενέργειες" πρέπει να είναι αυστηρά καθορισμένες
2. οι "ενέργειες" πρέπει να είναι εκτελέσιμες
3. ο χρόνος δράσης τους να είναι πεπερασμένος
Από αυτά τα τρία προκύπτουν τα κριτήρια της καθοριστικότητας της αποτελεσματικότητας και της περατότητας αντίστοιχα.
Αν αγνοήσουμε προσωρινά το παράδειγμα του βιβλίου για τη διαίρεση με το μηδέν που το αναφέρει ως πρόβλημα καθοριστικότητας τα πράγματα είναι απλά:
Καθοριστικότητα σημαίνει κάθε εντολή να είναι σαφώς ορισμένη. Δηλαδή η μηχανή επεξεργασίας δεδομένων που θα κλιθεί να τη διεκπαιρεώσει να καταλάβει τι ζητάμε να γίνει. Μπορούμε να το συνδέσουμε με τη σωστή σύνταξη.
Η αποτελεσματικότητα έχει να κάνει με την εκτελεσιμότητα. Αν εκτελείται μια σαφώς ορισμένη εντολή. Εδώ θα κολλούσε το παράδειγμα με τη διαίρεση με το μηδέν. Ο εκτελεστής καταλαβαίνει τι πρέπει να κάνει, αλλά δε μπορεί να το εκτελέσει. ʼρα η εντολή είναι μη αποτελεσματική γιατί δεν παράγει αποτέλεσμα.
Όλο αυτό όμως χαλάει όταν το βιβλίο δίνει ως παράδειγμα παραβίασης της καθοριστικότητας τη διαίρεση με το μηδέν. Ταυτίζει δηλαδή την καθοριστικότητα με την αποτελεσματικότητα. Αυτό που μπορούμε να κάνουμε λοιπόν είναι όταν βρίσκουμε ένα πρόβλημα καθοριστικότητας σε έναν αλγόριθμο (συμπεριλαμβανομένης και της διαίρεσης με μηδέν) να θεωρούμε ότι είναι ταυτόχρονα και πρόβλημα αποτελεσματικότητας. Με αυτόν τον τρόπο οι μαθητές θα έχουν αντιληφθεί τη διαφορά των δύο κριτηρίων και θα απαντούν διπλωματικά αφού το βιβλίο τους ωθεί εκεί.
Επιπρόσθετα τα κριτήρια εισόδου και εξόδου ελέγχονται καθολικά στον αλγόριθμο. Εξετάζουμε αν ο αλγόριθμος έχει είσοδο και έξοδο. Συνεπώς για μία εντολή δεν έχει νόημα να εξετάζουμε αυτά τα δύο κριτήρια. Αν λοιπόν συναντήσουμε την εντολή α <--β και στο β δεν έχουμε φροντίσει να δώσουμε τιμή, παραβιάζουμε το κριτήριο της αποτελεσματικότητας. Πολύ απλά επειδή η εντολή αδυνατεί να εκτελεστεί.
Εν ολίγοις βοηθάει πολύ τους μαθητές η εξής φιλοσοφία: τα κριτήρια εισόδου , εξόδου και περατότητας πρέπει να τα ελέγχουμε στο σύνολο του αλγορίθμου ενώ τα κριτήρια καθοριστικότητας και αποτελεσματικότητας για κάθε εντολή ξεχωριστά.
Ν.Ε.Φ.