Παραβίαση αλγοριθμικών κριτηρίων

Ξεκίνησε από souzanna79, 02 Οκτ 2018, 07:26:13 ΜΜ

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

souzanna79

Γεια σας συνάδελφοι.

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

Επειδή έχει πέσει και σαν θέμα (Επαναληπτικές 2003) νομίζω ότι είναι σημαντικό.

Παραθέτω όσα βρήκα στο φόρουμ υπέρ της μίας ή της άλλης άποψης.

https://alkisg.mysch.gr/steki/index.php?topic=1570.0

https://alkisg.mysch.gr/steki/index.php?topic=108.0

https://alkisg.mysch.gr/steki/index.php?topic=107.0

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

petrosp13

Πέρα από την καθοριστικότητα για παρονομαστες και την περατοτητα, αυτό το θέμα καλό θα είναι να μην αγγίζεται
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

pgrontas

Η καθοριστικότητα.
Κάτι τέτοιο νομίζω προκύπτει και από την συντριπτική πλειοψηφία των *αιτιολογημένων* απαντήσεων στα threads που παρέπεμψες.
Πάντως κάτι επίσημο σε αυτό δεν γνωρίζω να υπάρχει, αλλά στο συγκεκριμένo παράδειγμα δεν χρειάζεται κατά τη γνώμη μου.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

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

Αν διατυπώσουμε τα δύο κριτήρια με απλό και κατανοητό προς τον μαθητή τρόπο, μπορούμε να πούμε ότι

μια εντολή δεν ικανοποιεί  το κριτήριο της αποτελεσματικότητας όταν δεν μπορεί να εκτελεστεί καθόλου 
μια εντολή δεν ικανοποιεί το κριτήριο της καθοριστικότας όταν εκτελείται για ένα σύνολο τιμών, αλλά δεν εκτελείται για κάποια τιμή.

Στο συγκεκριμένο παράδειγμα η απώλεια τιμής σε μια μεταβλητή  οδηγεί στη μη εκτέλεση της εντολής (στη ΓΛΩΣΣΑ), άρα παραβιάζει το κριτηριο της αποτελεσματικότητας

pgrontas

Παράθεση από: Καρκαμάνης Γεώργιος στις 23 Οκτ 2018, 10:46:30 ΜΜ
Στο συγκεκριμένο παράδειγμα η απώλεια τιμής σε μια μεταβλητή  οδηγεί στη μη εκτέλεση της εντολής (στη ΓΛΩΣΣΑ), άρα παραβιάζει το κριτηριο της αποτελεσματικότητας
Πάντως από ό,τι βλέπω, στον πρώτο σύνδεσμο είχες διαφορετική γνώμη. Κάτι σε έκανε να αλλάξεις ή έχω καταλάβει λάθος;

Παράθεση από: Καρκαμάνης Γεώργιος στις 04 Οκτ 2008, 01:17:34 ΠΜ
1. Αν ο μαθητής απαντήσει ΝΑΙ τότε νομίζω πως πρέπει  να δικαιολογήσει πως ικανοποιείται το κάθε κριτήριο ξεχωριστά. Αν απαντήσει ΟΧΙ , τότε ποιο λογικό ακούγεται να γράψει το  κριτήριο που δεν ικανοποιείται και να το δικαιολογήσει. Δεν θυμάμαι και τι λύση και οδηγίες είχαν δοθεί από την επιτροπή εξετάσεων. Ας μας διαφωτίσει κάποιος παλιότερος.

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

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

Νομίζω ότι η πιο απλή και κατανοητή για τους μαθητές εξήγηση είναι αυτή που έχει δοθεί από τον gpapargi στην παλαιότερη συζήτηση (2ο link). Παραφράζω:
1. Η καθοριστικότητα παραβιάζεται όταν μια εντολή δεν μπορεί να εκτελεστεί επειδή κάποιο τμήμα της δεν ορίζεται είτε σε όλες είτε σε κάποιες περιπτώσεις (παράδειγμα: διαίρεση με το 0, απροσδιόριστες τιμές).
2. Η αποτελεσματικότητα παραβιάζεται όταν μια εντολή δεν είναι αρκετά απλή για αυτόν που εκτελεί τον αλγόριθμο ώστε να γνωρίζει πώς να την εκτελέσει. Για παράδειγμα δεν μπορούμε να έχουμε εντολές όπως βρες τον μεγαλύτερο, λύσε την τάδε εξίσωση (ή και σε περιπτώσεις της καθημερινής ζωής μείωσε την ανεργία κτλ.) αν δεν τις έχουμε περιγράψει σε απλούστερα βήματα.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

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

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

junior

Και γιατί σώνει και καλά πρέπει να παραβιάζει ένα από τα δύο κριτήρια καθοριστικότητας ή αποτελεσματικότητας και να μην ισχύει κάτι άλλο?
Π.χ.
Α) αν η μεταβλητή αυτή αφορά το βάρος σε gr ενός αντικειμένου που έπρεπε να πάρει τιμή από μια εντολή εισόδου, τότε θα μπορούσαμε να πούμε ότι παραβιάζει το κριτήριο της εισόδου.

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

Γενικά δεν σημαίνει ότι αν ικανοποιούνται και τα 5 κριτήρια, τότε ο αλγόριθμος δουλεύει και δίνει σωστά αποτελέσματα. Με άλλα λόγια τα κριτήρια είναι απαραίτητες προϋποθέσεις για να δουλέψει σωστά ο αλγόριθμος, αλλά όχι και ικανές. Δηλαδή αν ο αλγόριθμος δουλεύει σωστά, τότε σίγουρα ικανοποιούνται τα 5 κριτήρια. Το αντίστροφο δεν ισχύει γενικά.

Οπότε στο ερώτημα αν ο αλγόριθμος έχει ένα λογικό λάθος (π.χ. σε μία έκφραση αντί για + γράψαμε -), τότε ποιο κριτήριο παραβιάζεται; Προφανώς κανένα, απλά ο αλγόριθμος είναι λαθός.

Παράθεση από: Καρκαμάνης Γεώργιος στις 23 Οκτ 2018, 10:46:30 ΜΜ
Αν διατυπώσουμε τα δύο κριτήρια με απλό και κατανοητό προς τον μαθητή τρόπο, μπορούμε να πούμε ότι

μια εντολή δεν ικανοποιεί  το κριτήριο της αποτελεσματικότητας όταν δεν μπορεί να εκτελεστεί καθόλου 
μια εντολή δεν ικανοποιεί το κριτήριο της καθοριστικότας όταν εκτελείται για ένα σύνολο τιμών, αλλά δεν εκτελείται για κάποια τιμή.

Στο συγκεκριμένο παράδειγμα η απώλεια τιμής σε μια μεταβλητή  οδηγεί στη μη εκτέλεση της εντολής (στη ΓΛΩΣΣΑ), άρα παραβιάζει το κριτηριο της αποτελεσματικότητας

Δηλαδή η εντολή:
β <- α / 0
που δεν μπορεί να εκτελεστεί καθόλου, οποιαδήποτε τιμή να πάρει τα α, δεν ικανοποιεί το κριτήριο της αποτελεσματικότητας; Είναι λάθος απάντηση.

Άλλο λάθος σε εντολή (π.χ. χρησιμοποιώ τιμές ή ορίσματα που δεν επιτρέπονται, π.χ. διαίρεση με μηδέν ή λάθος σύμβολα, πχ c <- a & b) και άλλο μη εκτελέσιμη εντολή. Η αποτελεσματικότητα αναφέρεται στην απλότητα της εντολής, δηλαδή να είναι εντολή που να ανήκει στο ρεπερτόριο εντολών της υπολογιστικής μηχανής ή της γλώσσας προγραμματισμού.

Θα προσπαθήσω να δώσω κάποια παραδείγματα.

Α. Λάθος στις εντολές

- β <- α / 0, ο διαιρέτης πρέπει να είναι μη μηδενικός
- γ <- α γ *, αντί για γ <- α * γ
- α <- ΕΦ(90), το όρισμα της συνάρτησης ΕΦ πρέπει να είναι διάφορο του 0
- α <- Τ_Ρ(-1), το όρισμα της συνάρτησης Τ_Ρ πρέπει να είναι μη αρνητικός αριθμός
- α <- Τ_Ρ( #), το όρισμα της συνάρτησης Τ_Ρ πρέπει να είναι μη αρνητικός αριθμός

Β. Μη Ικανοποίηση της Καθοριστικότητας

Β1.
Διάβασε α, β
γ <- α / β
Γράψε γ

Δεν έχουν ληφθεί υπόψιν όλα τα ενδεχόμενα για την τιμή β

Β2.

Διάβασε α
β <- Παραγοντικό( α)
Γράψε β

Ας υποθέσουμε εδώ ότι το Παραγοντικό είναι συνάρτηση. Τότε δεν έχουμε λάβει υπόψιν μας ότι η τιμή του α μπορεί να μην είναι φυσικός αριθμός.


Γ. Μη Ικανοποίηση της Αποτελεσματικότητας

Γ1. Θα αναφερθώ στο παράδειγμα Β2. Γράφουμε λοιπόν:

Διάβασε α
Αν  (α είναι φυσικός) τότε
    β <- Παραγοντικό(α)
   Γράψε β
αλλιώς
   Γράψε 'Δεν ορίζεται παραγοντικό μη φυσικού αριθμού'

Εδώ τώρα αν θεωρήσουμε ως υπολογιστική μηχανή τον άνθρωπο, η εντολή Αν μπορεί να εκτελεστεί. Αν όμως η υπολογιστική μας μηχανή είναι αυτή που υλοποιεί την ΓΛΩΣΣΑ, προφανώς η εντολή Αν δεν είναι εκτελέσιμη, γιατί η συνθήκη (α είναι φυσικός) δεν είναι κατανοητή από την ΓΛΩΣΣΑ.

Γ2.

Στο παράδειγμα Γ1, αν δεν έχει οριστεί η συνάρτηση Παραγοντικό, τότε η εντολή   

β <- Παραγοντικό(α)

παραβιάζει το κριτήριο της αποτελεσματικότητας.

Τέλος η εντολή
c <- ρίζα ((c * (a+b)) ^a / ((b-c)^a)) + ((c-a)^b)^(1/c) - c*b
αν και θα μπορούσε να διασπαστεί σε απλούστερες, αυτό δεν σημαίνει ότι παραβιάζει το κριτήριο της αποτελεσματικότητας.

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

bugman

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

@junior, αν ικανοποιούνται όλα τα κριτήρια τότε ο αλγόριθμος είναι σωστός (απλά δεν το ξέρουμε πάντα από την αρχή). Όταν δεν είναι σωστός..τότε ψάχνουμε που έγινε το λάθος και σκεφτόμαστε τα κριτήρια. Κανένας δεν γράφει ένα σωστό πρόγραμμα από την αρχή (εκτός αν είναι μικρό και είναι πολύ έμπειρος). Κάνει δοκιμές για να τεκμηριώσει ότι δεν έχει λάθος. Μάλιστα σε μεγάλα προγράμματα τον έλεγχο τον κάνουν εξειδικευμένα άτομα ως προς το σύνολο των λειτουργιών με δοκιμές, και αυτό γιατί ο προγραμματιστής μπορεί να την πατήσει, επειδή στο νου του μπορεί να έχουν κολλήσει μια σειρά τιμών, να είναι προκατειλημμένος, και σε αυτές το πρόγραμμα (Αλγόριθμος αν θες), να δουλεύει. Έτσι ο ειδικός στους ελέγχους το ψάχνει χωρίς να έχει επηρεαστεί από την φάση ανάπτυξης, και ενδέχεται να βρει πρόβλημα! Βάλε στο νου σου ότι καμιά εφαρμογή δεν είναι εκατό της εκατό εντάξει, απλά για όσο είναι να κάνει δουλειά, και οι διορθώσεις θα βγουν όταν οι χρήστες το απαιτήσουν, όταν βρουν τα προβλήματα!


wmaster

Καλησπέρα,
νομίζω ότι παραβιάζει το κριτήριο της εισόδου.

gpapargi

Παιδιά η ιστορία με τα κριτήρια είναι παλιά και έχει συζητηθεί πολύ.
Κάποια στιγμή καταλάβαμε ότι τα κριτήρια είναι μεταφορά από τον Knuth οπότε είπαμε ότι καλύτερα να δούμε τι θέλει να πει ο Knuth στο βιβλίο του.
O Knuth τα λέει αλλιώς. Καταρχήν δε θεωρεί τα πάντα κριτήρια. Κριτήρια θεωρεί μόνο την καθοριστικότητα και την περατότητα. Τα άλλα τα θεωρεί «χαρακτηριστικά» που μπορεί να έχει ή να μην έχει ένας αλγόριθμος.

Η περατότητα είναι ξεκάθαρη. 

Παραβίαση της καθοριστικότητας είναι όταν αυτός που εκτελεί τις εντολές δεν «ξέρει» πώς να εκτελέσει κάποια από αυτές.

Για την αποτελεσματικότητα ο Knuth εκτός από το να την αποκαλεί «χαρακτηριστικό», λέει ότι θα πρέπει να μπορεί το συγκεκριμένο βήμα να εκτελεστεί από άνθρωπο με χαρτί και μολύβι. Δίνει για παράδειγμα το βήμα «αν η διοφαντική εξίσωση (ε) έχει λύση τότε κάνε αυτό» όπου (ε) μια διοφαντική εξίσωση για την οποία δεν ξέρουμε αν υπάρχει ή όχι λύση. Καταλαβαίνω δηλαδή ότι το effectiveness το χρησιμοποιεί ο Knuth σαν  «εφικτότητα» και είναι λάθος η μετάφραση σε «αποτελεσματικότητα».

Ίσως θα είχε νόημα να συζητήσουμε αν υπάρχουν επικαλύψεις ανάμεσα σε καθοριστικότητα και αποτελεσματικότητα πχ η συνθήκη «αν η διοφαντική εξίσωση (ε) έχει λύση» ίσως να παραβιάζει και τα 2 αφού αυτός που την εκτελεί δεν ξέρει τι να κάνει.

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

junior

Επειδή αναφέρθηκε ο Knuth από τον gpapargi, Ενδεικτικό Απόσπασμα της Ελληνικής Μετάφρασης του βιβλίου "Η Τέχνη του Προγραμματισμού" του D. Knuth των εκδόσεων Τζιόλα, όπως υπάρχει στο σύστημα Εύδοξος, στο οποίο αναφέρεται ο ορισμός και τα κριτήρια των αλγορίθμων.

https://static.eudoxus.gr/books/81/chapter-18549081.pdf

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

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

gpapargi

Παράθεση από: junior στις 23 Νοε 2018, 12:25:27 ΠΜ

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

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