ΚΡΙΤΗΡΙΑ ΑΛΓΟΡΙΘΜΩΝ

Ξεκίνησε από landreou, 17 Ιαν 2013, 08:19:53 ΠΜ

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

landreou

Γειά χαρά σε όλους του φίλους του ΣτΠ. Θα ήθελα να σας υποβάλλω ένα ερώτημα για ασκήσεις που αναφέρονται σε κριτήρια που ικανοποιούν έναν αλγόριθμο. Θα ήθελα να γίνεται ειδικά αιτιολόγηση για τα κριτήρια της Αποτελεσματικότητας και της Καθοριστικότητας ( τι κοιτάμε δηλαδή σε ένα αλγόριθμο για να δούμε αν ικανοποιεί αυτά τα δύο κριτήρια και πως το αιτιολογούμε με απλά λόγια).
Πχ να δίνεται ένα τμήμα αλγορίθμου και να ζητείται να αιτιολογήσουμε αν ικανοιποιεί τα 5 κριτήρια  (είσοδος-έξοδος-περατότητα-καθοριστικότητα-αποτελεσματικότητα).
Σας ευχαριστώ .

evry

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

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

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

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

landreou

Μπορείτε με συγκεκριμένο παράδειγμα να μας δείξετε πότε δεν ικανοποιούνται τα κριτήρια της καθοριστικότητας και της αποτελεσματικότητας; Για την περατότητα έχει πέσει και σχετικό θέμα στις Εξετάσεις 2005 όπως έχω δεί και το κατάλαβα.

gthal

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

για κ από 1 μέχρι 3
  γράψε κ/(κ-2)
τέλος_επανάληψης

παραβιάζει την καθοριστικότητα γιατί για κάποια τιμή του κ (εδώ για κ=2) θα επιχειρηθεί διαίρεση με το μηδέν

Διάβασε Χ
Εμφάνισε Τ_Ρ(Χ)

παραβιάζει την καθοριστικότητα γιατί είναι πιθανό να δοθεί τιμή του Χ για την οποία η τετραγωνική ρίζα δεν ορίζεται.
Φιλικά,
Γιώργος Θαλασσινός

landreou

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

nikolasmer

Αποτελεσματικότητα:

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

ή

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

landreou

Γεια σου φίλε nikolasmer και φίλοι του ΣτΠ.
Μια επεξήγηση αν γίνεται με βάση τον ορισμό που έχει δοθεί ή και με απλούστερα λόγια να γίνεται για τα δύο παραδείγματα που δόθηκαν και αφορούσαν την αποτελεσματικότητα .

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

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

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

Ευχαριστώ

petrosp13

Παράθεση από: nikolasmer στις 24 Ιαν 2013, 11:59:39 ΠΜ
Αποτελεσματικότητα:

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

ή

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

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

nikolasmer

Παράθεση από: gpapargi στις 08 Μαΐου 2007, 11:39:29 ΠΜ
Με είχε απασχολήσει αρκετά το θέμα παλαιότερα επειδή ακριβώς δεν έβγαζα άκρη από το σχολικό βιβλίο. Έτσι διάβασα το συγκεκριμένο κομμάτι από το βιβλίο του Knuth από όπου είναι παρμένα τα αλγοριθμικά κριτήρια. Κατάλαβα τα εξής:

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

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

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

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

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

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

Δεν ξέρω αν σε φώτισα ή σε σκότισα περισσότερο, αλλά αυτά είναι που προέκυψαν από το ψάξιμο που έριξα.
Μερεντίτης Νικόλαος
Πληροφορικός

nikolasmer

Εφόσον η αποτελεσματικότητα- Effectiveness λέγεται ο Αλγόριθμος και οι εντολές του να είναι απλές και εκτελέσιμες το πιο απλό παράδειγμα που μπορώ να σκεφτώ είναι
Διάβασε χ1, χ2
Εμφάνισε μο

Εγώ θέλω να μου βρεί το μέσο όρο 2 τιμών αλλά αυτός δεν "είναι" στο μυαλό μου για να το ξέρει.
Μερεντίτης Νικόλαος
Πληροφορικός

ikariofil

Διάβασε Χ
Αν X > 5 τότε
    ψ <- Χ -3
Τέλος_αν
Εμφάνισε ψ

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

nikolasmer

Παράθεση από: ikariofil στις 24 Ιαν 2013, 01:16:07 ΜΜ
Διάβασε Χ
Αν X > 5 τότε
    ψ <- Χ -3
Τέλος_αν
Εμφάνισε ψ

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

Πιστέυω πως είναι Αποτελεσματικότητα. Βέβαια σε καμία περίπτωση δεν μπορώ να βρίσκομαι στο μυαλό του Donald Knuth.
Μερεντίτης Νικόλαος
Πληροφορικός

landreou

Για ποιο λόγο όμως είναι η αποτελεσματικότητα ; Στις εξετάσεις ζητάνε και αιτιολόγηση .....

petrosp13

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

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

Johnkary

Καλησπέρα σας!
Θα ήθελα να μου εξηγήσει κάποιος κάτι που δεν καταλαβαίνω από τις λύσεις (Σ-Λ) του πρώτου θέματος πανελληνίων το 2000 στο ΑΕΠΠ ημερήσιου λυκείου.
Γιατί στην ερώτηση 2 και 3 του Θέματος 1Α είναι αντίστοιχα Σ και Λ;

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

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

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

petrosp13

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

Laertis

Τα θέματα αυτά έχουν δοθεί με άλλη σειρά οπότε και οι απαντήσεις δεν είναι αυτές που γράφει το site :

Θέμα 1ο
............
2.   Η περατότητα ενός αλγορίθμου αναφέρεται στο γεγονός ότι καταλήγει στη λύση του προβλήματος μετά από πεπερασμένο αριθμό βημάτων (εντολών).          Μονάδες 4   (Σωστό)

3.   Για να αναπαραστήσουμε τα δεδομένα και τα αποτελέσματα σ'  έναν αλγόριθμο,  χρησιμοποιούμε μόνο σταθερές.               Μονάδες 4   (Λάθος)

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



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

Johnkary

Σας ευχαριστώ για την άμεση απάντηση! Είπα κι εγώ, δεν μπορεί να στέκουν όλα αυτά.
Πάντως, οι ερώτηση 2, που αναφέρεται στην περατότητα, δεν θα μπορούσε όντως να είναι λάθος (ως ημιτελής πρόταση); Αφού, σύμφωνα με το σχολικό βιβλίο η περατότητα αναφέρεται ως εξής:
"Να τελειώνει (ο αλγόριθμος), φτάνοντας στο επιθυμητό αποτέλεσμα, σε πεπερασμένο αριθμό βημάτων ή χρόνο"

itt

Παράθεση από: Johnkary στις 19 Οκτ 2014, 06:59:38 ΜΜ
Σας ευχαριστώ για την άμεση απάντηση! Είπα κι εγώ, δεν μπορεί να στέκουν όλα αυτά.
Πάντως, οι ερώτηση 2, που αναφέρεται στην περατότητα, δεν θα μπορούσε όντως να είναι λάθος (ως ημιτελής πρόταση); Αφού, σύμφωνα με το σχολικό βιβλίο η περατότητα αναφέρεται ως εξής:
"Να τελειώνει (ο αλγόριθμος), φτάνοντας στο επιθυμητό αποτέλεσμα, σε πεπερασμένο αριθμό βημάτων ή χρόνο"

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

nikolasmer

ΠαράθεσηAn algorithm has five characteristics:

    Finiteness: the algorithm will end after a limited number of steps.
    Definiteness: each step can and must be precisely defined.
    Input: an algorithm is "provided" with zero or more quantities, either at the start or during operation, upon which its operation depends.
    Output: an algorithm generates zero or more "outputs" that have a definite relationship to the inputs.
    Effective: the steps of the algorithm must be simple and definite enough that they can theoretically be accomplished correctly and adequately with pencil and paper. A procedure requiring e.g. the mathematical quantity "pi" defined to an infinite number of decimal places would not satisfy this criterion.
http://www.ieee-uffc.org/ultrasonics/software/matlab/Lecture3/Lecture3_1.htm
Μερεντίτης Νικόλαος
Πληροφορικός

dmitry

Αποτελεσμάτικότητα

διαβασε α,β,γ
μο<--α+β+γ/3
γραψε μο


καθοριστικότητα

διαβασε α,β
γραψε α/β


περατότητα
ξέρετε όλοι.

isillo1

Παράθεση από: evry στις 17 Ιαν 2013, 04:51:05 ΜΜ
Τα μόνα κριτήρια που έχει νόημα να εξετασθούν είναι τα κριτήρια της περατότητας και της καθοριστικότητας. Αν κάποιος δοκιμάσει να εξετάσει τα υπόλοιπα νομίζω ότι θα υπάρξει πρόβλημα μια και όλοι οι αλγόριθμοι ικανοποιούν το κριτήριο της εισόδου (άρα τι σόι κριτήριο είναι αυτό?) και όσον αφορά αυτό της αποτελεσματικότητας δεν νομίζω ότι περιγράφεται όπως θα έπρεπε στο βιβλίο.

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

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

Αν ψάξεις στο στέκι για τα κριτήρια θα βρεις αρκετά threads. Το θέμα έχει ξανασυζητηθεί διεξοδικά

Συγνωμη φιλε μου νομιζω οτι εχεις αδικο αρχικα υπαρχουν αλγοριθμοι που δεν εχουν εισοδο ψαξτο  ;) και κατα δευτερον το κριτηριο της εισοδου αναφερεται στο οτι οι τιμες που εισερχονται πρεπει να ειναι ισες με αυτες που χρειαζεται το προβλημα για να λυθει ουτε περισσοτερες ουτε λιγοτερες

evry

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

Παράθεση από: isillo1 στις 21 Ιουν 2017, 11:08:36 ΜΜ
Συγνωμη φιλε μου νομιζω οτι εχεις αδικο αρχικα υπαρχουν αλγοριθμοι που δεν εχουν εισοδο ψαξτο  ;) και κατα δευτερον το κριτηριο της εισοδου αναφερεται στο οτι οι τιμες που εισερχονται πρεπει να ειναι ισες με αυτες που χρειαζεται το προβλημα για να λυθει ουτε περισσοτερες ουτε λιγοτερες

Επίσης μπορείς να μου δώσεις μια αναφορά σε αυτά που λες? Δηλαδή αναφέρεσαι σε κάποιον ορισμό με αποδοχή από την επιστημονική κοινότητα?
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr