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

dafnib

  • Νέος
  • *
  • Μηνύματα: 8
  • Γράψτε το προσωπικό σας σλόγκαν!
Ξέρω, είναι ένα πολυσυζητημένο θέμα.... Υπάρχει κάποιο παράδειγμα όμως που να φαίνεται ότι δεν πληρείται το κριτήριο της αποτελεσματικότητας; Ένας μαθητής μου  επιμένει καταλάβει τη διαφορά.... και έχει και δίκιο.

Ευχαριστώ.

Laertis

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 1466
  • Δεν αντέχω την (συμ)-πίεσηηη .......
    • ΑΣΚΗΣΕΙΣ-ΘΕΜΑΤΑ ΑΕΠΠ
Θα σου δώσω ένα απλοϊκό παράδειγμα σε ελεύθερο κείμενο το οποίο μπορεί εύκολα να παραβιάσει το κριτήριο της αποτελεσματικότητας :

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

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

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

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

sstergou

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 983
  • Program or be Programmed
    • pseudoglossa.gr
Έχω την εντύπωση ότι μία εντολή του τύπου Υπολόγισε_μέσο_όρο(α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')
σε αυτή την περίπτωση η εντολή Δώσε_μια_ρίζα_από_την_εξίσωση δεν είναι και τόσο απλό να εκτελεστεί (νομίζω δηλαδή!) γιατί ίσως δεν έχει αναπτυχθεί ακόμη αλγόριθμος που να επιλύει τέτοιες εξισώσεις. Διατηρώ μια επιφύλαξη για το μαθηματικό κομμάτι γιατί δεν τα ξέρω και πολύ καλά.

Αυτό που καταλαβαίνω εγώ είναι ότι μια εντολή παραβιάζει την αποτελεσματικότητα εάν δεν έχει αναπτυχθεί άλλος αλγόριθμος ο οποίος να την εκτελεί (χωρίς να είναι απαραίτητο αυτός να περιλαμβάνεται στην λύση του προβλήματος που αντιμετωπίζουμε)
« Τελευταία τροποποίηση: 28 Φεβ 2008, 06:15:15 μμ από sstergou »
Στάθης Στέργου - sstergouATgmailDOTcom - http://www.pseudoglossa.gr

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3167
  • to Iterate is human to Recurse divine

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

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

sstergou

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 983
  • Program or be Programmed
    • pseudoglossa.gr
ΥΓ. Ε ρε που φτάσαμε να διαφωνούμε για κάτι το οποίο είναι εξ'ορισμού λάθος

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

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

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

Laertis

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

zenctheo

  • Νέος
  • *
  • Μηνύματα: 4
Η αλήθεια είναι ότι και εμένα με απασχολεί αυτό το πρόβλημα. Πάντως σύμφωνα με τον Knuth η αποτελεσματικότητα του αλγορίθμου έγκειται στο να είναι όλα προσδιορισμένα επακριβώς και να μπορούν να εκτελεστούν από ένα άνθρωπο με μολύβι και χαρτί (art of computer programming 3rd edition σελ 6  :))
Έχω μια ερώτηση όμως την οποία δεν είμαι σίγουρο για τιν απάντηση της.
Ο παρακάτω αλγορίθμος.
Κώδικας: [Επιλογή]
Αλγόριθμος Δοκιμή
Διάβασε α
α<--α+β
Εμφάνισε α
Τέλος Δοκιμή
τι πρόβλημα παρουσιάζει από άποψη κριτηρίων;
Το β δεν είναι ορισμένο στον κώδικα του, άρα ο υπολογιστής δεν ξέρει να εκτελέσει την α<--α+β
Είναι πρόβλημα αποτελεσματικότητας ή καθοριστικότητας; Γιατί;


pik

  • Νέος
  • *
  • Μηνύματα: 4

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


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

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

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

raniasgr

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

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2452
  • I 'm not young enough to know everything

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

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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3167
  • to Iterate is human to Recurse divine
Για το δεύτερο που λες συμφωνώ, αλλά για το πρώτο με το συντακτικό λάθος? παραβιάζει σίγουρα την αποτελεσματικότητα?

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

jgalano

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


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


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


Ιδού η απορία !!!  :-\ :-\ :-\
« Τελευταία τροποποίηση: 26 Μάι 2009, 12:29:40 πμ από jgalano »

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

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

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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3167
  • to Iterate is human to Recurse divine
Το 1ο της καθοριστικότητας, όχι της αποτελεσματικότητας ούτε της εισόδου
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr