Θέμα: ΑΛΓΟΡΙΘΜΙΚΑ ΚΡΙΤΗΡΙΑ

[ΕΠΙΣΚΕΠΤΗΣ]

ΕΠΕΙΔΗ ΕΧΩ ΜΠΕΡΔΕΥΤΕΙ ΛΙΓΟ, ΠΟΙΟ ΑΛΓΟΡΙΘΜΙΚΟ ΚΡΙΤΗΡΙΟ ΠΑΡΑΒΙΑΖΕΤΑΙ ΣΤΙΣ ΠΑΡΑΚΑΤΩ ΠΕΡΙΠΤΩΣΕΙΣ:

1. ΔΙΑΙΡΕΣΗ ΜΕ 0
2. ΤΕΤΡΑΓΩΝΙΚΗ ΡΙΖΑ ΑΡΝΗΤΙΚΟΥ ΑΡΙΘΜΟΥ
3. ΠΑΡΑΣΤΑΣΗ ΜΕ ΜΕΤΑΒΛΗΤΗ ΠΟΥ ΔΕΝ ΤΗΣ ΕΧΕΙ ΕΚΧΩΡΗΘΕΙ ΤΙΜΗ Π.Χ Α<-Β+2 ΟΤΑΝ ΤΟ Β ΔΕΝ ΕΧΕΙ ΤΙΜΗ.

[ΕΠΙΣΚΕΠΤΗΣ]

1. καθοριστικότητα (δεν ορίζεται η πράξη)
2. Καθοριστικότητα (δεν ορίζεται η πράξη)
3. Είσοδος (δεν έχει πάρει τιμή η Β)

[ΕΠΙΣΚΕΠΤΗΣ]

Η προσπέλαση εκτός ορίων πίνακα, ποιό αλγοριθμικό κριτήριο παραβιάζει;

για παράδειγμα, όπως η έκφραση

γ <- β / α

πρέπει να διατυπωθεί ως:
ΑΝ Α<>0 ΤΟΤΕ
  γ <- β/α
ΤΕΛΟΣ_ΑΝ

ώστε να εξασφαλίζει την καθοριστικότητα, αντίστοιχα, εάν υπάρχει πίνακας Π, 10 στοιχείων, η:

ΔΙΑΒΑΣΕ Χ
ΓΡΑΨΕ Π[Χ]

πρέπει να διατυπώνεται ως:

ΑΝ Χ >=1 ΚΑΙ Χ <=10 ΤΟΤΕ
  ΓΡΑΨΕ Π[Χ]
ΤΕΛΟΣ_ΑΝ

ή έστω

ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
  ΔΙΑΒΑΣΕ Χ
ΜΕΧΡΙΣ_ΟΤΟΥ Χ>=1 ΚΑΙ Χ<=10
ΓΡΑΨΕ Χ

Διαφορετικά, μπορεί να χρησιμοποιηθεί δείκτης εκτός οιρίων οπότε θα είναι λάθος.

Ποιό κριτήριο παραβιάζεται;

[Επισκέπτης]

Νομίζω ότι και οι 3  περιπτώσεις παραβιάζουν το κριτήριο της αποτελεσματικότητας. Δεν είναι εκτελέσιμες εντολές. Και η περίπτωση με τον πίνακα το ίδιο. Σε μία μεταβλητή που δεν έχει δηλωθεί, η εντολή εκχώρησης σε αυτήν τη μεταβλητή δεν είναι εκτελέσιμη. (Η εντολή είναι απλή αλλά δεν είναι εκτελέσιμη)

[alkisg]

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

Το ίδιο και στην προσπέλαση πινάκων εκτός ορίων, η πράξη πιθανώς να εκτελεστεί αλλά να επηρεαστούν άλλες μεταβλητές (ή να κολλήσει ο Η/Υ σαν sideeffect). Π.χ. αν στην Pascal δηλώσω
var
  A: array[1..10] of integer;
  i: integer;
και μετά πω A[11] := 5,
τότε το i θα γίνει 5!
(θα πρέπει βέβαια να έχω απενεργοποιημένο το range checking).

Δε νομίζω ότι παραβιάζεται η αποτελεσματικότητα. Οι εντολές είναι απλές και εκτελέσιμες. Όμως υπάρχουν αμφιβολίες για τον τρόπο εκτέλεσής τους (=καθοριστικότητα).

BTW, αν δε θέλετε να δημιουργήσετε λογαριασμό στο στέκι, δε βάζετε τουλάχιστον το μικρό σας όνομα όταν στέλνετε ένα μήνυμα, για να μη βλέπουμε ΕΠΙΣΚΕΠΤΗΣ να ρωτά και ΕΠΙΣΚΕΠΤΗΣ να απαντά;

[filippos]

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

Όμως το διάβασμα πέρα από τα όρια του πίνακα με προβληματίζει.  Ορίζεται ως πράξη.  Όμως το "όρισμα" είναι λάθος.  Το στοιχείο που ζητάει ο "απρόσεκτος" που έγραψε την εντολή, δεν υπάρχει.  Ίσως να παραβιάζει το κριτήριο της "απροσεξίας" αλλά γιατί της καθοριστικότητας;  Θα το χαρακτήριζα απλά λογικό λάθος. 

Όσο για την προσπέλαση "ακαθόριστης" μεταβλητής (α<-β+2) πάλι δεν είμαι σίγουρος για το περί "καθοριστικότητας".  Δεν είναι ότι δε γίνεται.  Πάλι περί "απροσεξίας" πρόκειται.  Η πράξη είναι σαφώς καθορισμένη.  Το όρισμα δεν ... πήγε στο ραντεβού του

Όσο για τα περί των γλωσσών και της συμπεριφοράς τους, δε νομίζω ότι πρέπει να τα εξετάζουμε ως ενδεικτικά.  Οι γλώσσες αποτελούν προσεγγίσεις υλοποίησης.  Μία γλώσσα μπορεί να θεωρήσει την αδήλωτη μεταβλητή ως μηδέν (BASIC) και κάποια άλλη ως λάθος (ΓΛΩΣΣΑ).  Μία μπορεί να δώσει λάθος στην Τ_Ρ του αρνητικού και κάποια άλλη να επιστρέψει μιγαδικό αποτέλεσμα.

Το τι κάνει η μία γλώσσα και τι η άλλη είναι θέμα οριμού της. 

Το ερώτημα εδώ είναι τα "αλγοριθμικά" κριτήρια.

[chaos]

Καλημέρα,

Με δεδομένο τον ορισμό των κριτηρίων όπως ορίζεται στο σχολικό βιβλίο μάλλον και η περίπτωση της προσπάθειας "διαβάσματος" στοιχείου έξω από τα όρια του πίνακα καταστρατηγεί το κριτήριο της καθοριστικότητας (Κάθε εντολή πρέπει να καθορίζεται χωρίς καμία αμφιβολία για τον τρόπο εκτέλεσης της - στην Basic επί παραδείγματι σου βγαίνει το μήνυμα Subscript Out of Range). Σε ότι αφορά το α<-β+2, αν και ολες οι γλώσσες που γνωρίζω θα εκτελέσουν την παραπάνω πράξη με ότι "σκουπίδι" έχει ο καταχωρητής που αντιστοιχεί στην μεταβλητή β, θεωρώ ότι είναι αρκετά πονηρό σαν ερώτημα. Σίγουρα δεν γνωρίζουμε το αποτέλεσμα, άρα αν και είμαστε σίγουροι για το ποια πράξη θα γίνει δεν είμαστε σίγουροι για το αποτέλεσμα της πράξης άρα μπορούμε να πούμε ότι δεν ισχύει το κριτήριο της καθοριστικότητας. Αλλά εφόσον το βιβλίο λέει ότι πρέπει να υπάρχει οπωσδήποτε είσοδος και εδώ δεν υπάρχει (ασχέτως γλωσσών προγραμματισμού) μπορούμε επίσης να πούμε ότι δεν ισχύει το κριτήριο της εισόδου.. (μπέρδεμα!!!)

Ευχαριστώ,
Σωτήρης

[lsourtzo]

Όσο για την προσπέλαση "ακαθόριστης" μεταβλητής (α<-β+2) πάλι δεν είμαι σίγουρος για το περί "καθοριστικότητας".  Δεν είναι ότι δε γίνεται.  Πάλι περί "απροσεξίας" πρόκειται.  Η πράξη είναι σαφώς καθορισμένη.  Το όρισμα δεν ... πήγε στο ραντεβού του

(σχολικό):  Καθοριστικότητα (definiteness). Κάθε εντολή πρέπει να καθορίζεται χωρίς καμία αμφιβολία για τον τρόπο εκτέλεσής της. Λόγου χάριν, μία εντολή διαίρεσης πρέπει να θεωρεί και την περίπτωση, όπου ο διαιρέτης λαμβάνει μηδενική τιμή.

είναι σαφές ότι και οι 4 περιπτώσεις ποιο πάνω παραβιάζουν το εν λόγο κριτήριο !!

[alkisg]

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

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

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

[Επισκέπτης]

Δηλαδή ο αλγόριθμος:


Αλγόριθμος Δεν_είμαστε_καλά
   Α <- Β+2  ! Δεν έχει εισαχθεί το Β
   Εμφάνισε Α
Τέλος Δεν_είμαστε_καλά

παραβιάζει το κριτήριο της καθοριστικότητας... Επιτρέψτε σε έναν ταπεινό επισκέπτη να διαφωνήσει.

Ακόμα κι αν το Β είναι αποτέλεσμα υπολογισμών, δεν έχει εισαχθεί (άλλωστε και η εντολή Β <- 1 αποτελεί είσοδο)

Η συζήτηση για καταχωρητές κα γλώσσες προγραμματισμού είναι ενδιαφέρουσα  , αλλά σε ποιο μάθημα αναφέρεται;

[alkisg]

Ωπ!!! το Β <- 1 ΔΕΝ ΕΙΝΑΙ ΕΙΣΟΔΟΣ!

edit: Επειδή είμαι αλλεργικός στις παρεξηγήσεις, επιτρέψτε μου ένα μικρό offtopic.

<offtopic>
Η πρόταση που έκανα πιο πριν για να γράφετε τα ονόματά σας δεν είχε σαν στόχο να άρετε την ανωνυμία σας. Το στέκι επιτρέπει ανώνυμους επισκέπτες γιατί θεωρούμε ότι προσφέρουν στη συζήτηση, και επειδή αρκετοί έχουν λόγους να μένουν ανώνυμοι. Ο σκοπός της πρότασης ήταν απλά να καταλαβαίνουμε ποιος ρωτάει και ποιος απαντάει, γιατί με το να ρωτάει ΕΠΙΣΚΕΠΤΗΣ και να απαντάει ΕΠΙΣΚΕΠΤΗΣ δεν καταλαβαίνουμε. Οποιοδήποτε nickname και να βάζατε θα διατηρούσατε την ανωνυμία σας αλλά θα καταλαβαίναμε κι εμείς ποιος μιλάει κάθε φορά.

Για το "ένας ταπεινός επισκέπτης": τα επιχειρήματα των επισκεπτών δε βαραίνουν ούτε λιγότερο ούτε περισσότερο από των εγγεγραμμένων μελών. Ο ανώνυμος επισκέπτης μπορεί να είναι είτε μαθητής δημοτικού είτε ένας από τους συγγραφείς του βιβλίου (λέμε τώρα) είτε και το μεγαλύτερο κεφάλι της Πληροφορικής στην Ελλάδα (δεν ξέρω ποιος είναι). Τα επιχείρήματα παραμένουν επιχειρήματα και θα πρέπει να αξιολογούνται ισότιμα ανεξαρτήτως προέλευσης.
Βέβαια (και άσχετα με τη μέχρι τώρα συζήτηση) όταν κάποιος ασκεί κριτική οι κανόνες δεοντολογίας επιβάλλουν να αναφέρει το όνομά του.
</offtopic>

[ΚΥΡΙΑΚΟΣ]

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

Επομένως είναι προφανές ότι η εντολή "Β <-  1" είναι είσοδος σε έναν αλγόριθμο

[alkisg]

Νομίζω πως όχι. Ερμηνεύω την παραπάνω πρόταση ως εξής:
Περίπτωση αλγορίθμου ο οποίος δεν έχει καμία είσοδο έχει νόημα μόνο όταν ο αλγόριθμος δημιουργεί ή επεξεργάζεται κάποιες πρωτογενείς τιμές ... κτλ.

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

Πέρα από αυτό, επίσης νομίζω ότι το συμπέρασμά σου είναι αυθαίρετο. Το ότι πρωτογενείς τιμές μπορούν να προκύψουν από απλές εντολές δε σημαίνει ότι οι αναθέσεις τιμής δίνουν πάντα πρωτογενείς τιμές, μόνο και μόνο επειδή η ανάθεση τιμής είναι κι αυτή απλή εντολή.
Είναι σαν να λες (σόρρυ για το βλακώδες παράδειγμα που δίνω αλλά δεν θυμάμαι άλλο τόσο χαρακτηριστικό) ότι η γυναίκα πλένει, το πλυντήριο πλένει, άρα η γυναίκα είναι πλυντήριο. Δηλαδή προτασιακά έκανες
Α => Β (Α συνεπάγεται Β)
Γ => Β
συμπεραίνω ότι
Α = Γ
το οποίο είναι λάθος.

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

[ΑΡΙΣΤΟΜΕΝΗΣ]

Το παράδειγμα που ανέφερα δεν είχε καμία είσοδο με τις εντολές Διάβασε ή Δεδομένα. Η απουσία των παραπάνω εντολών σε έναν αλγόριθμο και η αντικατάστασή τους με συναρτήσεις παραγωγής τυχα'ιων αριθμών ή με τη χρήση απλών εντολών ουσιαστικά φροντίζει ώστε ΚΑΘΕ αλγόριθμος να ικανοποιεί ΑΠΑΡΑΙΤΗΤΑ το κριτήριο της εισόδου (βιβλίο μαθητή)

Με το σκεπτικό σου, ο αλγόριθμος:

Αλγόριθμος Δεν_είμαστε_καλά
   Β <- 1
   Α <- Β+2
   Εμφάνισε Α
Τέλος Δεν_είμαστε_καλά

Δεν έχει είσοδο, κάτι που δεν μπορεί να συμβεί αφού πρέπει ΑΠΑΡΑΙΤΗΤΑ να έχει

[Vangelis]

Υπάρχει μια ασάφεια σχετικά με τα κριτήρια και για το λόγο αυτό στα τελευταί θέματα φρόντισαν να αναφερθούν μόνο στο κριτήριο τερματισμού (που είναι ίσως το πιο ξεκάθαρο).

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