Αποστολέας Θέμα: ΚΡΙΤΗΡΙΑ ΑΛΓΟΡΙΘΜΩΝ  (Αναγνώστηκε 9355 φορές)

landreou

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 124
ΚΡΙΤΗΡΙΑ ΑΛΓΟΡΙΘΜΩΝ
« στις: 17 Ιαν 2013, 08:19:53 πμ »
Γειά χαρά σε όλους του φίλους του ΣτΠ. Θα ήθελα να σας υποβάλλω ένα ερώτημα για ασκήσεις που αναφέρονται σε κριτήρια που ικανοποιούν έναν αλγόριθμο. Θα ήθελα να γίνεται ειδικά αιτιολόγηση για τα κριτήρια της Αποτελεσματικότητας και της Καθοριστικότητας ( τι κοιτάμε δηλαδή σε ένα αλγόριθμο για να δούμε αν ικανοποιεί αυτά τα δύο κριτήρια και πως το αιτιολογούμε με απλά λόγια).
Πχ να δίνεται ένα τμήμα αλγορίθμου και να ζητείται να αιτιολογήσουμε αν ικανοιποιεί τα 5 κριτήρια  (είσοδος-έξοδος-περατότητα-καθοριστικότητα-αποτελεσματικότητα).
Σας ευχαριστώ .

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3059
  • to Iterate is human to Recurse divine
Απ: ΚΡΙΤΗΡΙΑ ΑΛΓΟΡΙΘΜΩΝ
« Απάντηση #1 στις: 17 Ιαν 2013, 04:51:05 μμ »
Τα μόνα κριτήρια που έχει νόημα να εξετασθούν είναι τα κριτήρια της περατότητας και της καθοριστικότητας. Αν κάποιος δοκιμάσει να εξετάσει τα υπόλοιπα νομίζω ότι θα υπάρξει πρόβλημα μια και όλοι οι αλγόριθμοι ικανοποιούν το κριτήριο της εισόδου (άρα τι σόι κριτήριο είναι αυτό?) και όσον αφορά αυτό της αποτελεσματικότητας δεν νομίζω ότι περιγράφεται όπως θα έπρεπε στο βιβλίο.

Για τα 2 που είπα δίνω κάποια παραδείγματα τι πρέπει να δεις:

Καθοριστικότητα :
   Διαίρεση με μηδέν, υπόριζο αρνητικό και γενικότερα οποιαδήποτε εντολή η εκτέλεση της οποίας είναι συντακτικά σωστή αλλά μπορείς να προβλέψεις για κάποια είσοδο τι αποτελέσμα θα έχει
Περατότητα:
   Κοιτάς αν υπάρχει επανάληψη και προσπαθείς να δεις αν αυτή τερματίζει πάντα.

Αν ψάξεις στο στέκι για τα κριτήρια θα βρεις αρκετά threads. Το θέμα έχει ξανασυζητηθεί διεξοδικά
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

landreou

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 124
ΚΡΙΤΗΡΙΑ ΑΛΓΟΡΙΘΜΩΝ
« Απάντηση #2 στις: 22 Ιαν 2013, 02:39:01 μμ »
Μπορείτε με συγκεκριμένο παράδειγμα να μας δείξετε πότε δεν ικανοποιούνται τα κριτήρια της καθοριστικότητας και της αποτελεσματικότητας; Για την περατότητα έχει πέσει και σχετικό θέμα στις Εξετάσεις 2005 όπως έχω δεί και το κατάλαβα.

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 879
Απ: ΚΡΙΤΗΡΙΑ ΑΛΓΟΡΙΘΜΩΝ
« Απάντηση #3 στις: 23 Ιαν 2013, 08:58:05 μμ »
Καλή ερώτηση φίλε μου.
Μπορώ να σου δώσω δύο παραδείγματα για την καθοριστικότητα αλλά για την αποτελεσματικότητα επιφυλάσσομαι διότι δεν είμαι βέβαιος κι εγώ αν την καταλαβαίνω. Η περιγραφή του βιβλίου είναι πολύ φλου και η διάκριση καθοριστικότητας και αποτελεσματικότητας μου φαίνεται πολύ οριακή ώστε να μπορώ να φτιάξω παράδειγμα (και δεν έχω βρει και κανένα)

Κώδικας: [Επιλογή]
για κ από 1 μέχρι 3
  γράψε κ/(κ-2)
τέλος_επανάληψης
παραβιάζει την καθοριστικότητα γιατί για κάποια τιμή του κ (εδώ για κ=2) θα επιχειρηθεί διαίρεση με το μηδέν

Κώδικας: [Επιλογή]
Διάβασε Χ
Εμφάνισε Τ_Ρ(Χ)
παραβιάζει την καθοριστικότητα γιατί είναι πιθανό να δοθεί τιμή του Χ για την οποία η τετραγωνική ρίζα δεν ορίζεται.
Φιλικά,
Γιώργος Θαλασσινός

landreou

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 124
Απ: ΚΡΙΤΗΡΙΑ ΑΛΓΟΡΙΘΜΩΝ
« Απάντηση #4 στις: 24 Ιαν 2013, 08:25:47 πμ »
Προκειμένου για την καθοριστικότητα και την περατότητα κατάλαβα από την εξήγηση που μου έδωσες και σ'ευχαριστώ όπως και όλους τους φίλους του ΣτΠ. Προκειμένου για την αποτελεσματικότητα τώρα κάποιος να μας δώσει τα φώτα του για να μη βρεθούμε προ εκπλήξεων αν δούμε τίποτα σχετικό στα θέματα .

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 534
  • There can be only one...may it be AEPP.
Απ: ΚΡΙΤΗΡΙΑ ΑΛΓΟΡΙΘΜΩΝ
« Απάντηση #5 στις: 24 Ιαν 2013, 11:59:39 πμ »
Αποτελεσματικότητα:

Διάβασε χ
ψ <- χ+ζ
Εμφάνισε ψ

ή

Διάβασε χ
Αν χ>10 και χ<=20 τότε
ψ <-"Περνάς"
Αλλιώς_αν χ>=1 και χ<=10 τότε
ψ <- "Δεν περνάς"
Αλλιώς
Εμφάνισε ""Λάθος Βαθμός"
Τέλος_αν
Εμφάνισε ψ
 ;)
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

landreou

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 124
Απ: ΚΡΙΤΗΡΙΑ ΑΛΓΟΡΙΘΜΩΝ
« Απάντηση #6 στις: 24 Ιαν 2013, 12:10:40 μμ »
Γεια σου φίλε nikolasmer και φίλοι του ΣτΠ.
Μια επεξήγηση αν γίνεται με βάση τον ορισμό που έχει δοθεί ή και με απλούστερα λόγια να γίνεται για τα δύο παραδείγματα που δόθηκαν και αφορούσαν την αποτελεσματικότητα .

Για την Αποτελεσματικότητα λέει το βιβλίο :

Αποτελεσματικότητα (effectiveness). Κάθε μεμονωμένη εντολή του αλγορίθμου να είναι απλή.
Αυτό σημαίνει ότι μία εντολή δεν αρκεί να έχει ορισθεί, αλλά πρέπει να είναι και εκτελέσιμη.

Πού φένεται αυτό στα δύο τμήματα αλγορίθμου που δόθηκαν ;

Ευχαριστώ

petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2167
Απ: ΚΡΙΤΗΡΙΑ ΑΛΓΟΡΙΘΜΩΝ
« Απάντηση #7 στις: 24 Ιαν 2013, 12:30:22 μμ »
Αποτελεσματικότητα:

Διάβασε χ
ψ <- χ+ζ
Εμφάνισε ψ

ή

Διάβασε χ
Αν χ>10 και χ<=20 τότε
ψ <-"Περνάς"
Αλλιώς_αν χ>=1 και χ<=10 τότε
ψ <- "Δεν περνάς"
Αλλιώς
Εμφάνισε ""Λάθος Βαθμός"
Τέλος_αν
Εμφάνισε ψ
 ;)

Αυτά μήπως αναφέρονται στην καθοριστικότητα;
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 534
  • There can be only one...may it be AEPP.
Απ: ΚΡΙΤΗΡΙΑ ΑΛΓΟΡΙΘΜΩΝ
« Απάντηση #8 στις: 24 Ιαν 2013, 12:37:53 μμ »
Με είχε απασχολήσει αρκετά το θέμα παλαιότερα επειδή ακριβώς δεν έβγαζα άκρη από το σχολικό βιβλίο. Έτσι διάβασα το συγκεκριμένο κομμάτι από το βιβλίο του Knuth από όπου είναι παρμένα τα αλγοριθμικά κριτήρια. Κατάλαβα τα εξής:

Στην αποτελεσματικότητα δεν έχει γίνει σωστή μεταφορά του όρου effectiveness από τα αγγλικά. Μεταφράστηκε σαν αποτελεσματικότητα αλλά το νόημα είναι κάτι σαν «πραγματοποιησιμότητα» αν μου επιτραπεί η έκφραση. Δηλαδή μιλάμε για τη δεύτερη ερμηνεία της λέξης effect.
http://www.in.gr/dictionary/lookup.asp?Word=effect

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

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

Κάπως έτσι κατάλαβα αυτά που γράφει ο μεγάλος Donald Knuth.   

Η καθοριστικότητα είναι κάτι απλό: Παραβίασή της έχουμε όταν αυτός που εκτελεί τον αλγόριθμο φτάσει σε κάποιο σημείο και πει «Ουπς… τι κάνουμε τώρα;»
Παραδείγματα παραβίασης της καθοριστικότητας είναι η διαίρεση με 0 αφού βάζεις τον υπολογιστή να κάνει κάτι που δεν γίνεται και λέει το «Ουπς… τώρα τι κάνουμε;»
ʼλλο παράδειγμα παραβίασης της καθοριστικότητας είναι το να πεις «Βάλε λίγο αλάτι» σε μια μαγειρική συνταγή. Πόσο είναι το λίγο αλάτι; Μια χούφτα; Ένα κουταλάκι της σούπας; Ένα κουταλάκι του γλυκού;

Αυτά για αρχή. Από κει και πέρα έχουν τεθεί εύστοχα ερωτήματα του στυλ «Τι θα γίνει αν αυτός που εκτελεί τον αλγόριθμο ξέρει ότι αρνητική τιμή σε ρίζα δίνει μιγαδικό ή ότι η διαίρεση με 0 δίνει άπειρο». Υπάρχουν περιβάλλοντα που χειρίζονται τέτοιες καταστάσεις από μόνα τους και δεν απαιτούν την παρέμβαση του προγραμματιστή με συνθήκες. Αυτά τα ερωτήματα σηκώνουν κουβέντα και τέτοιες έχουμε κάνει αρκετές. Έχω και άλλα ερωτήματα να θέσω εγώ. Αλλά νομίζω ότι σε πρώτη φάση ας μην σε μπλέξουμε άλλο.

Δεν ξέρω αν σε φώτισα ή σε σκότισα περισσότερο, αλλά αυτά είναι που προέκυψαν από το ψάξιμο που έριξα.
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 534
  • There can be only one...may it be AEPP.
Απ: ΚΡΙΤΗΡΙΑ ΑΛΓΟΡΙΘΜΩΝ
« Απάντηση #9 στις: 24 Ιαν 2013, 01:00:17 μμ »
Εφόσον η αποτελεσματικότητα- Effectiveness λέγεται ο Αλγόριθμος και οι εντολές του να είναι απλές και εκτελέσιμες το πιο απλό παράδειγμα που μπορώ να σκεφτώ είναι
Διάβασε χ1, χ2
Εμφάνισε μο

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

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

ikariofil

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 114
  • Γράψτε το προσωπικό σας σλόγκαν!
Απ: ΚΡΙΤΗΡΙΑ ΑΛΓΟΡΙΘΜΩΝ
« Απάντηση #10 στις: 24 Ιαν 2013, 01:16:07 μμ »
Διάβασε Χ
Αν X > 5 τότε
    ψ <- Χ -3
Τέλος_αν
Εμφάνισε ψ

Ποιο κατά τη γώμη σας κριτήριο του αλγορίθμου παραβιάζεται;
Καθοριστικότητα ή αποτελεσματικότητα;

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 534
  • There can be only one...may it be AEPP.
Απ: ΚΡΙΤΗΡΙΑ ΑΛΓΟΡΙΘΜΩΝ
« Απάντηση #11 στις: 24 Ιαν 2013, 01:43:17 μμ »
Διάβασε Χ
Αν X > 5 τότε
    ψ <- Χ -3
Τέλος_αν
Εμφάνισε ψ

Ποιο κατά τη γώμη σας κριτήριο του αλγορίθμου παραβιάζεται;
Καθοριστικότητα ή αποτελεσματικότητα;

Πιστέυω πως είναι Αποτελεσματικότητα. Βέβαια σε καμία περίπτωση δεν μπορώ να βρίσκομαι στο μυαλό του Donald Knuth.
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

landreou

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 124
Απ: ΚΡΙΤΗΡΙΑ ΑΛΓΟΡΙΘΜΩΝ
« Απάντηση #12 στις: 24 Ιαν 2013, 02:28:12 μμ »
Για ποιο λόγο όμως είναι η αποτελεσματικότητα ; Στις εξετάσεις ζητάνε και αιτιολόγηση .....

petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2167
Απ: ΚΡΙΤΗΡΙΑ ΑΛΓΟΡΙΘΜΩΝ
« Απάντηση #13 στις: 24 Ιαν 2013, 02:30:56 μμ »
Εμένα μου μοιάζει για Καθοριστικότητα γιατί ο ορισμός της προσδιορίζει ότι δεν θα πρέπει να υπάρχουν εντολές που να υπάρχει αμφιβολία για τον τρόπο εκτέλεσης τους
Αν το ψ δεν πάρει τιμή, είναι απροσδιόριστο το πώς θα εκτελεστεί η εντολή Εμφάνισε

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

Johnkary

  • Νέος
  • *
  • Μηνύματα: 6
Απ: ΚΡΙΤΗΡΙΑ ΑΛΓΟΡΙΘΜΩΝ
« Απάντηση #14 στις: 19 Οκτ 2014, 03:53:16 μμ »
Καλησπέρα σας!
Θα ήθελα να μου εξηγήσει κάποιος κάτι που δεν καταλαβαίνω από τις λύσεις (Σ-Λ) του πρώτου θέματος πανελληνίων το 2000 στο ΑΕΠΠ ημερήσιου λυκείου.
Γιατί στην ερώτηση 2 και 3 του Θέματος 1Α είναι αντίστοιχα Σ και Λ;

Οι επίμαχες προτάσεις:
<< 2. Για να αναπαραστήσουµε τα δεδοµένα και τα αποτελέσµατα σε έναν
αλγόριθµο, χρησιµοποιούµε µόνο σταθερές>> (Σ)  .... γιατί σωστό αυτό??

<< 3. Η περατότητα ενός αλγορίθµου αναφέρεται στο γεγονός ότι καταλήγει στη
λύση του προβλήµατος µετά από πεπερασµένο αριθµό βηµάτων>> (Λ) ... κι αυτό γιατί λάθος??

Παραθέτω τα Links των θεμάτων και των λύσεων
Εκφώνηση --->  http://spinos.eu/images/stories/panelladikes/2000.PDF
Λύσεις ---> http://spinos.eu/images/stories/panelladikes/2000_ANSWERS.PDF