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

Ξεκίνησε από ΕΠΙΣΚΕΠΤΗΣ, 11 Απρ 2006, 02:03:09 ΜΜ

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

ΕΠΙΣΚΕΠΤΗΣ

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

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

Παράθεση από: filippos στις 12 Απρ 2006, 07:52:49 ΠΜ
Όσο για την προσπέλαση "ακαθόριστης" μεταβλητής (α<-β+2) πάλι δεν είμαι σίγουρος για το περί "καθοριστικότητας".  Δεν είναι ότι δε γίνεται.  Πάλι περί "απροσεξίας" πρόκειται.  Η πράξη είναι σαφώς καθορισμένη.  Το όρισμα δεν ... πήγε στο ραντεβού του :)
(σχολικό):  Καθοριστικότητα (definiteness). Κάθε εντολή πρέπει να καθορίζεται χωρίς καμία αμφιβολία για τον τρόπο εκτέλεσής της. Λόγου χάριν, μία εντολή διαίρεσης πρέπει να θεωρεί και την περίπτωση, όπου ο διαιρέτης λαμβάνει μηδενική τιμή.

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

alkisg

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

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

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

Επισκέπτης

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


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

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

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

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

alkisg

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

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

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

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

ΚΥΡΙΑΚΟΣ

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

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

alkisg

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

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

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

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

ΑΡΙΣΤΟΜΕΝΗΣ


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

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

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

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

Vangelis

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

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


alkisg

#15
<offtopic>
Παράθεση από: ΑΡΙΣΤΟΜΕΝΗΣ στις 12 Απρ 2006, 01:59:29 ΜΜ
Το παράδειγμα που ανέφερα...

ΑΡΙΣΤΟΜΕΝΗ, δεν ανέφερες κάτι παραπάνω. Είναι η πρώτη φορά που μιλάς. Πιο πάνω μίλαγε ο ΚΥΡΙΑΚΟΣ, και ακόμα παραπάνω ο ΕΠΙΣΚΕΠΤΗΣ (για όσους δεν κατάλαβαν, πρόκειται για το ίδιο άτομο).
Είναι δυνατόν να παρακολουθήσει κάποιος τη συζήτηση όταν αλλάζεις όνομα σε κάθε post;
</offtopic>

Παραθέτοντας κάποιες εντολές δεν είναι ΑΠΑΡΑΙΤΗΤΟ να σχηματιστεί αλγόριθμος. Το πρόγραμμα που έγραψες δεν κάνει τίποτα χρήσιμο, και γι' αυτό δε θεωρείται αλγόριθμος. Παραβιάζει το κριτήριο της εισόδου.

Επίσης άχρηστη παράθεση εντολών είναι η
Κώδικας: Αλγόριθμος
...
όσο [b]αληθής[/b] επανάλαβε
   ...
τέλος_επανάληψης

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

Τέλος, το
Κώδικας: Αλγόριθμος
Αλγόριθμος HelloWorld
Αρχή
  Εμφάνισε "Hello world!"
Τέλος HelloWorld

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

alkisg

#16
Για να δώσω ένα ακόμα επιχείρημα, ισοδύναμοι αλγόριθμοι λέγονται αυτοί που αν τροφοδοτηθούν με την ίδια είσοδο παράγουν πάντα την ίδια έξοδο (βλ. π.χ. http://eom.springer.de/A/a011900.htm)

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

που ανέφερες παράγει πάντα την ίδια έξοδο με τον
Κώδικας: Αλγόριθμος
Αλγόριθμος Δεν_είμαστε_καλά
   Εμφάνισε 3
Τέλος Δεν_είμαστε_καλά

ο οποίος ακόμα και κατά τη δική σου ερμηνεία δεν έχει καμία είσοδο.

Είναι δυνατόν δύο αλγόριθμοι να είναι ισοδύναμοι και ο ένας να έχει είσοδο και ο άλλος να μην έχει;

klm

Το ότι οι δύο αλγόριθμοι δίνουν το ίδιο αποτέλεσμα, δεν σημαίνει οτι είναι ισοδύναμοι. Άλλλωστε το βιβλίο αναφέρει οτι είσοδος θεωρείται και μία απλή εντολή όπως β<--1. ʼρα δεν παραβιάζεται το κριτήριο εισόδου.

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

Αριστείδης

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

Το "Εμφάνισε "Hello world!" " είναι απλή εντολή, θεωρώ οτι το "Hello world!" αποτελεί είσοδο

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

Γενικά το θέμα με έχει προβληματίσει πολύ, και έχω ζυγίσει και τις δυο πλευρές, θεωρώ οτι είναι θολό

Η πρόταση: "Ένας αλγόριθμος μπορεί να μην έχει είσοδο" είναι Σωστή ή Λάθος;

P.Tsiotakis


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

Όταν δεν δίνονται τιμές (εντολή Διάβασε και Δεδομένα), τότε λέμε οτι καμία τιμή δεν δίνεται

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

Επομένως η πρόταση: "Ένας αλγόριθμος μπορεί να μην έχει είσοδο" είναι Λάθος


andreas_p

Επισκέπτη, Καλημέρα

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


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


Απάντηση  :

Το  Β απροσδιόριστο, άρα και το  Α,  συνεπώς  δεν πληρείται το κριτήριο  της αποτελεσματικότητας.
Δεν έχω και είσοδο (π.χ.  Διάβασε  Β  ή   Β <- 1)  άρα δεν πληρείται και το κριτήριο  της  εισόδου.

andreas_p

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


Έχει είσοδο. (Β<-1)

andreas_p

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

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

Παραβιάζονται τα παρακάτω κριτήρια :

1)  εισόδου ( γιατί το Β δεν πήρε τιμή είτε με Διάβασε είτε με εντολή εκχώρησης).

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




gpapargi

Η αποτελεσματικότητα είναι ένα περίεργο πράγμα. Κατά τη γνώμη μου φαίνεται να  έχει προκύψει από κακή μεταφορά του effectiveness από τα αγγλικά. Ουσιαστικά η σωστή μετάφραση θα ήταν (αν υπάρχει τέτοια λέξη) «πραγματοποιησιμότητα». Δηλαδή κάτι που είναι δυνατό να πραγματοποιηθεί.

Σημαίνει ότι η εντολή μπορεί να πραγματοποιηθεί σε πεπερασμένο χρόνο με χαρτί και μολύβι. 2 παραδείγματα που αναφέρει ο Knuth σαν παραβίαση του effectiveness είναι:

Παράδειγμα 1
Συνθήκη που να λέει «Αν η διοφαντική εξίσωση Ε1 έχει λύση τότε κάνε αυτό»
Όπου Ε1 μια εξίσωση για την οποία δεν ξέρουμε αν υπάρχει λύση και δεν έχουμε αποδείξει ότι δεν υπάρχει. Είναι δηλαδή ανοικτό πρόβλημα.

Παράδειγμα 2
Να κάνεις διαίρεση με δεκαδικές αναπαραστάσεις άρρητων αριθμών που δεν είναι δυνατό να αναπαρασταθούν με πεπερασμένο πλήθος ψηφίων.

Και τα 2 δεν είναι δυνατό να εκτελεστούν με μολύβι και χαρτί. Οι εντολές αυτές δεν είναι πραγματοποιήσιμες (effective).

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

Για την είσοδο, η γνώμη μου είναι ότι η εντολή ανάθεσης (α<- 3) δεν είναι είσοδος. Είναι μέσα στον αλγόριθμο και παράγεται από τον ίδιο τον αλγόριθμο. Για  να έχω είσοδο θα πρέπει κάτι να είναι έξω και μετά να μπει μέσα.

Η πλάκα είναι ότι ο Knuth δεν τα αποκαλεί κριτήρια αλλά features (χαρακτηριστικά). Που σημαίνει ότι δεν είναι τόσο καθοριστική η τήρησή τους. Criterion αποκαλεί μόνο της καθοριστικότητα. Επίσης ισχυρή έννοια (με τη λέξη must) δίνει στην περατότητα και την καθοριστικότητα. Σε είσοδο και έξοδο όχι.

Τέλος ξεκαθαρίσω ότι δεν αναφέρω τον Knuth  επειδή είναι ένα καλό βιβλίο. Τον αναφέρω γιατί από εκεί πήραν οι συγγραφείς τα «κριτήρια». Άρα αν δεν καταλάβω τι λέει το βιβλίο ανοίγω τον Knuth για να δω τι θα ήθελαν να πουν οι συγγραφείς.

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

Γενικά πάντως αν πέσει θέμα στις εξετάσεις πάνω σε σκοτεινό σημείο (κάτι που είναι πολύ εύκολο να γίνει) θα πέσει πολύ ξύλο.

alkisg

Παιδιά ερωτησούλες για να καταλάβουμε λίγο καλύτερα ποιες γνώμες "κυκλοφορούν" μεταξύ μας.
1) Η εντολή εκχώρησης τιμής αποτελεί είσοδο;
Απ' ότι βλέπω παραπάνω, alkisg και gpapargi ψηφίζουν όχι, andreas_p και επισκέπτης ναι... Οι υπόλοιποι τι λέτε;

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

ή, αντίστοιχα,
Κώδικας: Αλγόριθμος
Αλγόριθμος ΠάλιΔενΚάνωΤίποτα
  αν αληθής τότε
  τέλος_αν
τέλος ΠάλιΔενΚάνωΤίποτα


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

filippos

Έχω την αίσθηση ότι πρέπει να το θέμα είσοδος - έξοδος πρέπει να δούμε διαφορετικά.

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

Ένας αλγόριθμος επεξεργάζεται δεδομένα και παράγει αποτελέσματα.  Δεν νοείται αλγόριθμος που δεν επεξεργάζεται κάτι (δεν έχει είσοδο).  Δε νοείται αλγόριθμος που δεν "παράγει" κάτι (δεν έχει έξοδο).

Επομένως, οι δύο προηγούμενοι "αλγόριθμοι" που παρουσιάζει ο Άλκης,
Παράθεση από: alkisg στις 12 Μαΐου 2006, 12:16:19 ΜΜ
Κώδικας: Αλγόριθμος
Αλγόριθμος ΔενΚάνωΤίποτα
τέλος ΔενΚάνωΤίποτα

ή, αντίστοιχα,
Κώδικας: Αλγόριθμος
Αλγόριθμος ΠάλιΔενΚάνωΤίποτα
  αν αληθής τότε
  τέλος_αν
τέλος ΠάλιΔενΚάνωΤίποτα
δεν είναι αλγόριθμοι.

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

Παράθεση από: andreas_p στις 12 Μαΐου 2006, 08:56:13 ΠΜ
Κώδικας: Αλγόριθμος
Αλγόριθμος Δεν_είμαστε_καλά
   Β <- 1
   Α <- Β+2
   Εμφάνισε Α
Τέλος Δεν_είμαστε_καλά


Εάν η λειτουργία του παραπάνω αλγόριθμο είναι να υπολογίζει το διπλάσιο του 1, τότε το Α αποτελεί την είσοδό του και το Β την έξοδό του, ενώ στον παρακάτω αλγόριθμο:

Παράθεση από: alkisg στις 12 Απρ 2006, 02:56:41 ΜΜ
Κώδικας: Αλγόριθμος
Αλγόριθμος HelloWorld
Αρχή
  Εμφάνισε "Hello world!"
Τέλος HelloWorld


η είσοδος ταυτίζεται με την έξοδο, δηλαδή το αποτέλεσμα του αλγόριθμου ταυτίζεται με το δεδομένο του (ουσιαστικά δεν υπάρχει επεξεργασία)

klitos

1. καθοριστικότητα
2. καθοριστικοτητα
3. αποτελεσματικοτητα  ( δεν ειναι εκτελεσιμη οχι γιατι δεν υπαρχει καμια αμφιβολία  αλλα γιατι δεν εχει ορισθει το β )
κλητος χατζηγεωργιου

novulus

Όντως το ζήτημα είναι μπλεγμένο. Να κάνω και εγώ μια ερώτηση η οποία θεωρώ ότι θα μπλέξει περισσότερο την πράγματα.  Ο αλγόριθμος που εμφανίζει τον ... εαυτό του (εχει διατυπωθεί ήδη λύση στο forum) είναι αλγόριθμος; Τι συμβαίνει εκεί με την είσοδο;
Thus spake the master programmer:
"When you have learned to snatch the error code from the trap frame, it will be time for you to leave."

gpapargi

Με αυτό που κάνεις Φίλιππε ουσιαστικά θεωρείς αλγόριθμο την επεξεργασία των δεδομένων. Οπότε τα δεδομένα που επεξεργάζεται ο αλγόριθμος είναι η είσοδος.

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

Επίσης και στην έξοδο μπορείς να βρεις προβληματικές περιπτώσεις. Πχ στην πράξη οι εφαρμογές συχνά αποτελούνται από περισσότερα από ένα προγράμματα που τρέχουν στο background σαν δαίμονες. Για να μην τα ξεκινάς ένα ένα φτιάχνεις ένα script που τα ξεκινά όλα και στη συνέχεια τερματίζει. Αυτό το σκριπτάκι μπορείς θεωρητικά να το φτιάξεις χωρίς να έχει κάποια έξοδο σε logfile. Οπότε… βασικά δεν έχει ούτε είσοδο ούτε έξοδο. Αλλά είναι πολύ πρακτικό και πολύ συνηθισμένο.

Σϊγουρα αυτός που σκέφτηκε τα αλγοριθμικά «κριτήρια» είχε στο νου του ότι ο αλγόριθμος πρέπει να κάνει κάτι. Να έχει κάποια επίδραση στο περιβάλλον του αλλιώς είναι άχρηστος. Και έτσι μίλησε για είσοδο και έξοδο. Αλλά εξαιρέσεις μπορείς να βρεις άμα πας γυρεύοντας.

Η γνώμη μου είναι ότι κακώς λέγονται κριτήρια. Τα κριτήρια είναι βαριά λέξη και σημαίνει ότι αν δεν τα έχεις τότε δεν έχεις αλγόριθμο. Πιστεύω ότι θα πρέπει να τα λέγαμε «Χαρακτηριστικά». Θυμίζω και αυτά που έγραψα παραπάνω για τα «features» του Knuth.

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