Παράδειγμα αλγορίθμου που δεν πληρεί το κριτήριο της αποτελεσματικότητας

Ξεκίνησε από dafnib, 28 Φεβ 2008, 10:33:13 ΠΜ

« προηγούμενο - επόμενο »

dafnib

Ξέρω, είναι ένα πολυσυζητημένο θέμα.... Υπάρχει κάποιο παράδειγμα όμως που να φαίνεται ότι δεν πληρείται το κριτήριο της αποτελεσματικότητας; Ένας μαθητής μου  επιμένει καταλάβει τη διαφορά.... και έχει και δίκιο.

Ευχαριστώ.

Laertis

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

Διάβασε 5 ακέραιους αριθμούς.
Υπολόγισε το μέσο όρο.
Εκτύπωσε το μέσο όρο.

Η διαδικασία-εντολή Υπολόγισε το μέσο όρο δεν είναι απλή για τον υπολογιστή και δεν μπορεί να εκτελεστεί απ'ευθείας. Πρέπει να αναλυθεί σε εύρεση αθροίσματος και στη συνέχεια σε διαίρεση με το πλήθος για να υπολογιστεί ο μέσος όρος. Έτσι πρέπει να γίνει :

Διάβασε 5 ακέραιους αριθμούς.
Υπολόγισε το άθροισμα τους
Διαίρεσε με το πλήθος τους
Εκτύπωσε το μέσο όρο

Μπορεί το παράδειγμα - επειδή είναι απλοϊκό για να το καταλάβει ευκολότερα ένας μαθητής - να μην είναι εντελώς σωστό αλλά αυτή πιστεύω είναι η ουσία του κριτηρίου της αποτελεσματικότητας.
Νικολακάκης Γιώργος
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής
http://users.sch.gr/gnikola

sstergou

Έχω την εντύπωση ότι μία εντολή του τύπου Υπολόγισε_μέσο_όρο(α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


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

ΥΓ. Ε ρε που φτάσαμε να διαφωνούμε για κάτι το οποίο είναι εξ'ορισμού λάθος
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

sstergou

Παράθεση από: evry στις 28 Φεβ 2008, 09:25:19 ΜΜΥΓ. Ε ρε που φτάσαμε να διαφωνούμε για κάτι το οποίο είναι εξ'ορισμού λάθος

:) Δεν φταίμε μόνο εμεις πάντως!

Παράθεση από: evry στις 28 Φεβ 2008, 09:25:19 ΜΜΑπό αυτό εγώ καταλαβαίνω ότι πρέπει από πριν να "έχουμε πει" στον υπολογιστή (να έχουμε ορίσει στη γλώσσα του) τον τρόπο εκτέλεσης αυτής της εντολής

Τελικά υπάρχει ή όχι εκτέλεση και υπολογιστής ; :'(

Την εντολή χ <- ρίζα(4) ή την α <- ημ(π/2) ξέρει να την εκτελέσει; Σε τι αυτό διαφέρει από την Υπολόγισε_μέσο_όρο. Κάπου σιωπηλά υποθέτουμε ότι κάποιος το έχει πει στον υπολογιστή , ή τέλος πάντων στον εκτελεστή. Ποια εντολή είναι αρκετά απλή ώστε  να είναι απλή ; Εκτός και αν μιλάμε μόνο για τις βασικές πράξεις... Πολύ μπέρδεμα βρε παιδί μου , απαπα!

Laertis

Το παράδειγμα που ανέφερα μπορεί να είναι άστοχο για το κριτήριο της αποτελεσματικότητας αλλά έτσι όπως αυτό ορίζεται στο βιβλίο νομίζω ότι μπορεί να χρησιμοποιηθεί μόνο και μόνο για να κατανοήσει ένας μαθητής τι μπορεί να εννοεί.
Συμφωνώ με τον Ευριπίδη, ότι συζητάμε για κάτι το οποίο είναι κακά διατυπωμένο και δεν υπάρχει επαρκής επεξήγηση στο βιβλίο  αλλά με βάσει αυτό καλούνται να εξεταστούν τα παιδιά και πρέπει να "ανακαλύψουμε" τι ακριβώς προϋποθέτει η αποτελεσματικότητα του βιβλίου ως κριτήριο.
Νικολακάκης Γιώργος
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής
http://users.sch.gr/gnikola

zenctheo

Η αλήθεια είναι ότι και εμένα με απασχολεί αυτό το πρόβλημα. Πάντως σύμφωνα με τον Knuth η αποτελεσματικότητα του αλγορίθμου έγκειται στο να είναι όλα προσδιορισμένα επακριβώς και να μπορούν να εκτελεστούν από ένα άνθρωπο με μολύβι και χαρτί (art of computer programming 3rd edition σελ 6  :))
Έχω μια ερώτηση όμως την οποία δεν είμαι σίγουρο για τιν απάντηση της.
Ο παρακάτω αλγορίθμος.
Αλγόριθμος Δοκιμή
Διάβασε α
α<--α+β
Εμφάνισε α
Τέλος Δοκιμή

τι πρόβλημα παρουσιάζει από άποψη κριτηρίων;
Το β δεν είναι ορισμένο στον κώδικα του, άρα ο υπολογιστής δεν ξέρει να εκτελέσει την α<--α+β
Είναι πρόβλημα αποτελεσματικότητας ή καθοριστικότητας; Γιατί;


pik

Παράθεση από: zenctheo στις 20 Ιαν 2009, 02:32:35 ΠΜ

Ο παρακάτω αλγορίθμος.
Αλγόριθμος Δοκιμή
Διάβασε α
α<--α+β
Εμφάνισε α
Τέλος Δοκιμή

τι πρόβλημα παρουσιάζει από άποψη κριτηρίων;
Το β δεν είναι ορισμένο στον κώδικα του, άρα ο υπολογιστής δεν ξέρει να εκτελέσει την α<--α+β
Είναι πρόβλημα αποτελεσματικότητας ή καθοριστικότητας; Γιατί;


Σαφήνειας Ορισμού (καθοριστικότητας όπως το έχει το βιβλίο).

Η αποτελεσματικότητα ζητάει να έχουμε "ψιλοκόψει" αρκετά την λύση σε βήματα που μαγειρεύονται και χωνεύονται εύκολα. Αλλιώς πχ η φράση "Βάλε τα στοιχεία του πίνακα Α στη σειρά, από το μικρότερο ως το μεγαλύτερο" θα θεωρείτο αλγόριθμος ταξινόμησης. Το ένα και μοναδικό βήμα όμως που περιγράφει δεν είναι απλό. Πετάει το μπαλάκι στον αναγνώστη (ή τον υπολογιστή) για να κάνει όλη τη δουλειά μόνος του, χωρίς να τον καθοδηγήσει ουσιαστικά. Οπως το καταλαβαίνω, ένας αναποτελεσματικός αλγόριθμος έχει δυσανάλογες απαιτήσεις από αυτόν που προσπαθεί να τον εκτελέσει.

Για να γυρίσουμε στο παράδειγμά σου, τα βήματα από μόνα τους δεν είναι ιδιαίτερα απαιτητικά (ανάγνωση, πρόσθεση, εκτύπωση). Αυτό που μας εμποδίζει είναι το άγνωστο της τιμής του β. Όση εξυπνάδα και αν έχει ο αναγνώστης, και όση προσπάθεια και αν επενδύσει, δεν πρόκειται να βρει την τιμή του β. Για την "καθοριστικότητα" το βιβλίο μιλάει για "καθορισμό χωρίς καμία αμφιβολία για τον τρόπο εκτέλεσης", και νομίζω ότι εκεί είναι το προβλημά μας. Το β το θεωρούμε initialized σε 0 ακολουθώντας τις συμβάσεις κάποιων γλωσσών Η/Υ; Θεωρούμε ότι θα έχει όποια τιμή είχε ξεμείνει στη θέση μνήμης που ανατέθηκε στη μεταβλητή ακολουθώντας άλλες συμβάσεις; Δηλώνουμε αμηχανία;

raniasgr

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

gpapargi


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

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

evry

Για το δεύτερο που λες συμφωνώ, αλλά για το πρώτο με το συντακτικό λάθος? παραβιάζει σίγουρα την αποτελεσματικότητα?

Παράθεση από: Καρκαμάνης Γεώργιος στις 25 Μαΐου 2009, 12:48:16 ΠΜ
Θεωρώ για τα δεδομένα της ΑΕΠΠ ,πως ένας αλγόριθμος δεν πληροί το κριτήριο της αποτελεσματικότητας όταν υπάρχει σε αυτόν μια εντολή που είναι λάθος γραμμένη συντακτικά  ή χρησιμοποιεί σύμβολα που δεν έχουν οριστεί πράξεις γι'αυτά.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

jgalano

Τελικά, οι παρακάτω αλγόριθμοι, ποιο αλγοριθμικό κριτήριο δεν ικανοποιούν;
α)  Το κριτήριο της εισόδου;
β)  Το κριτήριο της καθοριστικότητας;
γ)  Το κριτήριο της αποτελεσματικότητας;
δ)  Όλα τα παραπάνω;


Αλγόριθμος Κριτήριο1
π<-- 0
Όσο όνομα<>’ΤΕΛΟΣ’ Επανάλαβε
   Διάβασε βαθμός
   Αν βαθμός=20 τότε
            π<-- π + 1
   Τέλος_Αν
   Εκτύπωσε όνομα, βαθμός
   Διάβασε όνομα
Τέλος_Επανάληψης
Εκτύπωσε π
Τέλος Κριτήριο1


Αλγόριθμος Κριτήριο2
Διάβασε όνομα
Όσο όνομα<>’ΤΕΛΟΣ’ Επανάλαβε
   Διάβασε βαθμός
   Αν βαθμός=20 τότε
            π<-- π + 1
   Τέλος_Αν
   Εκτύπωσε όνομα, βαθμός
   Διάβασε όνομα
Τέλος_Επανάληψης
Εκτύπωσε π
Τέλος Κριτήριο1


Ιδού η απορία !!!  :-\ :-\ :-\

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

ΠαράθεσηΓια το δεύτερο που λες συμφωνώ, αλλά για το πρώτο με το συντακτικό λάθος? παραβιάζει σίγουρα την αποτελεσματικότητα?

Το αναφέρω, γιατί θεωρώ πως μπορεί εύκολα να καταλάβει  ένας μαθητής τι σημαίνει "Μια εντολή να είναι εκτελέσιμη"

evry

Το 1ο της καθοριστικότητας, όχι της αποτελεσματικότητας ούτε της εισόδου
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr