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

[alkisg]

<offtopic>

Το παράδειγμα που ανέφερα...

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

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

Επίσης άχρηστη παράθεση εντολών είναι η

Κώδικας: Text

1. ...
2. όσο [b]αληθής[/b] επανάλαβε
3.    ...
4. τέλος_επανάληψης

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

Τέλος, το

Κώδικας: Text

1. Αλγόριθμος HelloWorld
2. Αρχή
3.   Εμφάνισε "Hello world!"
4. Τέλος HelloWorld

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

[alkisg]

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

Ο

Κώδικας: Text

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

που ανέφερες παράγει πάντα την ίδια έξοδο με τον

Κώδικας: Text

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

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

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

[klm]

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

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

[Αριστείδης]

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

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

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

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

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

[P.Tsiotakis]

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

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

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

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

[andreas_p]

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

Κώδικας: Text

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

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


Απάντηση  :

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

[andreas_p]

Κώδικας: Text

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

Έχει είσοδο. (Β<-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) "...ένας αλγόριθμος μπορεί να έχει είσοδο από άλλες απλές εντολές", όπως και "πρέπει να έχω είσοδο απαραίτητα". Τι σημαίνει αυτό; Ότι όλες οι απλές εντολές (όπως και η Εμφάνισε) αποτελούν είσοδο;
Π.χ. τι θα λέγατε για τον παρακάτω κενό αλγόριθμο όσον αφορά στο κριτήριο της εισόδου;

Κώδικας: Text

1. Αλγόριθμος ΔενΚάνωΤίποτα
2. τέλος ΔενΚάνωΤίποτα

ή, αντίστοιχα,

Κώδικας: Text

1. Αλγόριθμος ΠάλιΔενΚάνωΤίποτα
2.   αν αληθής τότε
3.   τέλος_αν
4. τέλος ΠάλιΔενΚάνωΤίποτα

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

[filippos]

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

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

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

Επομένως, οι δύο προηγούμενοι "αλγόριθμοι" που παρουσιάζει ο Άλκης,

Κώδικας: Text

1. Αλγόριθμος ΔενΚάνωΤίποτα
2. τέλος ΔενΚάνωΤίποτα

ή, αντίστοιχα,

Κώδικας: Text

1. Αλγόριθμος ΠάλιΔενΚάνωΤίποτα
2.   αν αληθής τότε
3.   τέλος_αν
4. τέλος ΠάλιΔενΚάνωΤίποτα

δεν είναι αλγόριθμοι.

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

Κώδικας: Text

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

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

Κώδικας: Text

1. Αλγόριθμος HelloWorld
2. Αρχή
3.   Εμφάνισε "Hello world!"
4. Τέλος HelloWorld

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

[klitos]

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

[novulus]

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

[gpapargi]

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

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

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

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

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

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