Αλγοριθμικά κριτήρια (Ασάφεια διδακτικού πακέτου)

Ξεκίνησε από gpapargi, 09 Φεβ 2010, 11:35:14 ΠΜ

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

Αποτελούν οι εντολές εκχώρησης είσοδο για έναν αλγόριθμο;

Ναι
Όχι

pgrontas

Στο θέμα του daemon συμφωνώ με τον Ευρυπίδη. Θεωρώ ότι ο αλγόριθμος του daemon τερματίζει αφού δεχτεί την αίτηση και την προωθήσει κάπου αλλού ή υπολογίσει κάτι ή κάνει κάτι. Η διεργασία μπορεί να μην τερματίζει ο αλγόριθμος τερματίζει.

Για το θέμα της εκχώρησης:
Σαφώς και οποιαδήποτε εντολή εκχώρησης δεν είναι είσοδος. Όμως κάποιες μπορεί να είναι, αφού όπως προαναφέρθηκε μπορούν να αντικαταστήσουν κάποιες Διάβασε ή τα δεδομένα.
Το θέμα για μένα είναι αλλού: Πώς δικαιολογούμε ότι υπάρχει αλγόριθμος χωρίς είσοδο;
Η σύγχυση (και η δική μου) οφείλεται στο εξής: Ως είσοδο εννοούμε την αλληλεπίδραση με το χρήστη  ή με άλλο αλγόριθμο, ή εννοούμε τα δεδομένα πάνω στα οποία δουλεύει ο αλγόριθμος. Στην πρώτη περίπτωση ασφαλώς και μπορεί να μην υπάρχει είσοδος, ενώ στην δεύτερη υποχρεωτικά πρέπει να υπάρχει.
Δεν είμαι βέβαιος για το ποιο είναι το σωστό.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

pgrontas

Κάθισα και διάβασα τι λέει ο Knuth :angel: για την είσοδο:
Αντιγράφω:

Παράθεση"Input. An algorithm has zero or more inputs: quantities that are given to it
initially before the algorithm begins, or dynamically as the algorithm runs. These
inputs are taken from specified sets of objects. In Algorithm E, for example, there
are two inputs, namely m and n, both taken from the set of positive integers. "

Ο αλγόριθμος Ε είναι ο αλγόριθμος του Ευκλείδη, ο οποίος περιγράφεται ως εξής νωρίτερα:

ΠαράθεσηAlgorithm E (Euclid's algorithm). Given two positive integers m and n, find
their greatest common divisor, that is, the largest positive integer that evenly
divides both m and n.
El. [Find remainder.] Divide m by n and let r be the remainder. (We will have
0<r <n.)
E2. [Is it zero?] If r = 0, the algorithm terminates; n is the answer.
E3. [Reduce.] Set m <- n, n <- r, and go back to step El.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

sstergou

initially before the algorithm begins --> παράμετροι - εντολή δεδομένα

dynamically as the algorithm runs --> από το ρεπερτόριο της ψευδογλώσσας νομίζω ότι ταιριάζει μόνο η διάβασε

Η εκχώρηση δεν θεωρώ ότι έχει κάτι το δυναμικό.

sstergou

χεχε, δεν βλέπω να βγάζουμε άκρη... Μήπως να τον πάρουμε κανένα τηλέφωνο;

gthal

Θα τρελαθώ ... θα πηδηχτώ απ' το παράθυρο    :D
8 στους 12 ψηφίζουν ότι η εκχώρηση είναι είσοδος !!!???

Παράθεση από: tom στις 11 Φεβ 2010, 08:55:53 ΜΜ
Έστω το παρακάτω τμήμα αλγορίθμου:

...
3. α<-10
...
8. β<-α+20
...
15. Εμφάνισε β

Αν σκεφτείς το τρίπτυχο είσοδος->επεξεργασία-> έξοδος,  πριν ο αλγόριθμος (θεωρώ πως η "καρδιά του" είναι το κομμάτι της επεξεργασίας) μπει στη φάση επεξεργασίας (εντολή 8 ) δε γνωρίζει τι έχει το α (πρωτογενές δεδομένο). Μόνο ο compiler το γνωρίζει. Άντε και το Λ.Σ. ;-)
Διαφωνώ κάθετα  !!!
ο αλγόριθμος αυτός γνωρίζει τι τιμή έχει το α. (εδώ βρε την γνωρίζει και ο προγραμματιστής του!)
Αν θέλαμε να γράψουμε την "καρδιά" του αλγορίθμου που δεν την αφορά και δεν ξέρει τι τιμή έχει το α, θα γράφαμε
// Δεδομένα α //
...
β<-α+20
...
Εμφάνισε β

(χα χα, μου φαίνεται τόσο αστείο όταν σκέφτομαι ποιο πρόβλημα λύνει ο αλγόριθμος αυτός : "Να γραφεί αλγόριθμος που δέχεται ως είσοδο την τιμή 10, της προσθέτει 20 και εμφανίζει το αποτέλεσμα   :o ;D :D    Οικτρό !!!!   :)   )

Στα σοβαρά τώρα, ένας λιγότερο "φλύαρος" προγραμματιστής θα είχε γράψει τον εντελώς ισοδύναμο αλγόριθμο:
β <- 10+20
Εμφάνισε β
(όπου ποια είναι η είσοδος?)

Και ένας προγραμματιστής που είναι "στα καλά του" ( >:D  sorry δεν μπορώ να κρατηθώ, νομίζω ότι ξεφεύγουμε σε παραλογισμούς :) )  θα έγραφε τον εντελώς ισοδύναμο "αλγόριθμο" :
Εμφάνισε 30
(ωραίος αλγόριθμος !   :D )
και έχει βέβαια είσοδο το 30, έ;   :D    α, όχι ξέχασα : το 10 ! γιατί υπολόγισε το 10+20 :D  ή μήπως το -460 γιατί υπολογίζει το -460+490  ;   :o

Με τίποτα, μα ΜΕ ΤΙΠΟΤΑ, δεν δέχομαι ότι οι hardcoded τιμές αποτελούν είσοδο του αλγορίθμου.
Η είσοδος, για μένα, πρέπει εξ' ορισμού να είναι τιμές άγνωστες στον αλγόριθμο (στον προγραμματιστή ουσιαστικά) την ώρα που γράφεται ο αλγόριθμος (θέμα που όπως ξαναειπώθηκε από κάποιον, άπτεται του χαρακτηριστικού της  γενικότητας)
Από την άλλη πάλι, αν το λέει η πλειοψηφία κάτι θα ξέρει παραπάνω και το σέβομαι.
Συγχωρήστε μου τα "αστειάκια" πιο πάνω. Δεν εννοώ να γελοιοποιήσω καμιά άποψη.  :angel:
Απλά έχω κέφια λόγω των ημερών (αποκριάτικα πάρτυ κλπ) και μου βγήκε να διαφωνήσω με χιούμορ  :)
Πάντως διαφωνώ  !    :laugh:
Φιλικά,
Γιώργος Θαλασσινός

evry

Νομίζω ότι οι ψηφοφορίες είναι ενδεικτικές. Άλλωστε το να υπερψηφιστεί μια άποψη δε σημαίνει ότι είναι σωστή, άσε που το δείγμα (12) είναι πολύ λιγότεροι από τους χιλιάδες καθηγητές πληροφορικής που κάνουν το μάθημα. Απλά φαίνεται ενδεικτικά αυτοί που διαβάζουν το thread τι άποψη έχουν. Μπορούμε να διαφωνούμε ή να συμφωνούμε. Μπορεί επίσης κάποιοι να ψήφισαν τις εντολές εκχώρησης έχοντας στο μυαλό αυτό που ειπώθηκε, περί πρωτογενών τιμών εκχώρησης.
Δηλαδή δε νομίζω ότι κανείς πιστεύει πως όλες οι εντολές εκχώρησης είναι είσοδοι του αλγορίθμου αλλά φαντάζομαι ότι λίγο πολύ συμφωνούμε πως υπάρχουν εντολές εκχώρησης που θα μπορούσαν να θεωρηθούν είσοδοι στον αλγόριθμο
   Επίσης να θυμίσω ότι γενικότερα οι ψηφοφορίες ή έρευνες μέσω διαδικτύου, δηλαδή αυτές στις οποίες δεν βλέπεις ποιος ψηφίζει και δεν γνωρίζεις το background που έχει δεν θεωρούνται αξιόπιστες. Μπορούν να χρησιμοποιηθούν για να δείξουν κατευθύνσεις αλλά σίγουρα δεν μπορείς να τεκμηριώσεις αξιόπιστα αποτελέσματα. Για να το κάνεις αυτό θα πρέπει να ξέρεις ακριβώς το προφίλ αυτών που απάντησαν.
   Πάντως εγώ προσωπικά δεν έχω ψηφίσει ακόμα γιατί πιστεύω ότι το θέμα αυτό δεν είναι απλά μια ασάφεια του βιβλίου αλλά κάτι παραπάνω και δεν είναι άσπρο-μαύρο.
  Μήπως αν η ψηφοφορία γινόταν : Θα μπορούσε μια εντολή εκχώρησης να αποτελεί είσοδο ή έξοδο σε έναν αλγόριθμο;
  Μου φαίνεται ότι αυτό το κριτήριο μάλλον πρέπει να το αφήσουμε στην ησυχία του... :(
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Νίκος Αδαμόπουλος

Και εγώ είμαι από τους μειοψηφήσαντες!

Το να γράψει κάποιος:

α<-13
β<-15
γ<-16
μο<-(α+β+γ)/3
Εμφάνισε μο

...για τεστάρει τον κώδικά του, ναι μπορεί να το κάνει. Όμως αν το αφήσει τελικά έτσι, τότε έχει φτιάξει κάτι άχρηστο! Θα έπρεπε μετά να το κάνει:

Διάβασε α, β, γ
μο<-(α+β+γ)/3
Εμφάνισε μο

ή

Δεδομένα // α, β, γ //
μο<-(α+β+γ)/3
Εμφάνισε μο

Έτσι λοιπόν ο αλγόριθμος θα έχει 3 εισόδους και μία έξοδο.
Αν παρόλα αυτά κρατήσει τον αρχικό αλγόριθμο, τότε ναι έχει 0 εισόδους, αφού θα εμφανίζει πάντα το ίδιο αποτέλεσμα!!!

Αν και μπορεί να φαίνεται αιρετικό αφού ο θεός Knuth έχει γράψει κάποια πράγματα... Όμως μην καταλήξουμε σε ένα συμπέρασμα που όταν κάποιος το διαβάζει αρχικά δεν θα του κάθεται καλά, και θα πρέπει στη συνέχεια να διαβάζει μία επεξήγηση 2 σελίδων με κάμποσες παραπομπές για να μπορεί να το δεχτεί...!

alkisg

Παράθεση από: evry στις 13 Φεβ 2010, 11:51:58 ΠΜ
Δηλαδή δε νομίζω ότι κανείς πιστεύει πως όλες οι εντολές εκχώρησης είναι είσοδοι του αλγορίθμου αλλά φαντάζομαι ότι λίγο πολύ συμφωνούμε πως υπάρχουν εντολές εκχώρησης που θα μπορούσαν να θεωρηθούν είσοδοι στον αλγόριθμο
Εγώ πάλι διαφωνώ κάθετα. Θεωρώ ότι καμία εντολή εκχώρησης δεν μπορεί να θεωρηθεί ως εντολή εισόδου.
(εκτός αν έχουμε memory mapped IO ή συσκευές - άλλη συζήτηση... :-))

Για μένα υπάρχουν δύο τύποι εισόδου:

  • Είσοδος από το "περιβάλλον" του υπολογιστή, δηλαδή από κάποια πρωτογενή τιμή, π.χ. διάβασμα της θέσης του ποντικιού ή των πλήκτρων που πατήθηκαν στο πληκτρολόγιο ή του ρολογιού. Αυτές μεταφράζονται στην εντολή "in al,θύρα" της assembly. Δεν είναι τυχαία τα ονόματά τους, λέγονται "in" και "θύρες" επειδή αφορούν είσοδο.
  • Είσοδος από άλλον αλγόριθμο, δηλαδή οι παράμετροι εισόδου κατά την κλήση ενός υποπρογράμματος.
  • Η εκχώρηση τιμής όπως την λέτε θα ήταν μια τρίτη κατηγορία, «Είσοδος από τον προγραμματιστή».
    Δεν θεωρώ ότι υπάρχει τέτοια κατηγορία εισόδου, ο προγραμματιστής βάζει τον αλγόριθμο, όχι τα δεδομένα... :police:

Με μια πρόταση: είσοδος είναι ό,τι μπορεί να μεταβάλλει τα αποτελέσματα ενός αλγορίθμου.

Επειδή τα είχαμε πει πολύ αναλυτικά και παλιότερα, δεν πολυσυμμετέχω στις νέες ψηφοφορίες, αλλά το συγκεκριμένο τράβηξε το μάτι μου... ξανααποσύρομαι στο Ubuntu και την ανάπτυξη των sch-scripts, ώστε να μπορούμε να εγκαθιστούμε ένα εργαστήριο με ελάχιστα κλικ και να μας μένει χρόνος στη συνέχεια να αφοσιωθούμε στις ασάφειες του διδακτικού πακέτου... :angel:

sstergou

Παράθεση από: evry στις 13 Φεβ 2010, 11:51:58 ΠΜ
  Μήπως αν η ψηφοφορία γινόταν : Θα μπορούσε μια εντολή εκχώρησης να αποτελεί είσοδο ή έξοδο σε έναν αλγόριθμο;

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

Δηλαδή
α <- 10
β <- 20
αποτέλεσμα <- α + β


Και στις δύο περιπτώσεις έχουμε ένα πρόβλημα... Για να κρίνουμε αν η εκχώρηση είναι είσοδος-έξοδος θα πρέπει να ξέρουμε το πρόβλημα (την εκφώνηση)... Σας φαίνεται αυτό λογικό;

Άλλο τα δεδομένα του προβλήματος και άλλο η είσοδος του αλγορίθμου!!!!


gthal

Παράθεση από: alkisg στις 13 Φεβ 2010, 02:36:06 ΜΜ
Εγώ πάλι διαφωνώ κάθετα. Θεωρώ ότι καμία εντολή εκχώρησης δεν μπορεί να θεωρηθεί ως εντολή εισόδου.
μαζί σου !
Αν και καταλήγω όλο και περισσότερο ότι δεν είναι η εκχώρηση το πρόβλημα αλλά οι hardcoded (εκ των προτέρων γνωστές) τιμές.
Το ίδιο υποστηρίζω (αλλά λιγότερο εμφατικά) και για την έξοδο:
ένας αλγόριθμος που μονοσήμαντα καταλήγει στην εντολή αποτέλεσμα<-30 , μάλλον δεν χρειάζεται να τρέξει αφού ξέρω εκ των προτέρων το αποτέλεσμά του (εντάξει, ίσως να χρειάζεται και δικαίωμά του να επιστρέφει πάντα το 30)
Όμως ποτέ δε θα αμφισβητούσα το αποτέλεσμα<-έκφραση , όπου το αποτέλεσμα της έκφρασης δεν είναι εκ των προτέρων γνωστό.  Άρα το παράδειγμα του Στάθη έχει μια έξοδο χωρίς αξία (μήπως γιατί δεν έχει είσοδο?)

Παράθεση από: alkisg στις 13 Φεβ 2010, 02:36:06 ΜΜ
... ξανααποσύρομαι στο Ubuntu και την ανάπτυξη των sch-scripts, ώστε να μπορούμε να εγκαθιστούμε ένα εργαστήριο με ελάχιστα κλικ και να μας μένει χρόνος στη συνέχεια να αφοσιωθούμε στις ασάφειες του διδακτικού πακέτου... :angel:
Μπράβο Άλκη. Όταν ευκαιρήσεις, βρες μου και έναν τρόπο πώς μπορώ να διπλοψηφίσω  ;D ;D ;D
Φιλικά,
Γιώργος Θαλασσινός

pgrontas

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

Για παράδειγμα έστω ένας αλγόριθμος που υπολογίζει τυχαίους αριθμούς (η ιδέα από το άλλο θέμα)
Αλγόριθμος BlumBlumShub
Δεδομένα //x,m,ν//
Για ι απο 1 μεχρι ν
    χ<-χ*χ mod m
Τέλος_Επανάληψης
Τέλος BlumBlumShub


Είναι φανερό ότι ο συγκεκριμένο αλγόριθμος λύνει γενικά το πρόβλημα της παραγωγής τυχαίων αριθμών και οι τιμές x,m είναι κρίσιμες για την λειτουργία του. (μπορούμε να τον θεωρήσουμε ως γενική κατηγορία- class)

Αν υπάρχει ένας αλγόριθμος που λειτουργεί για συγκεκριμένα x,m (instance?) γιατί να μην θεωρήσουμε τα συγκεκριμένα x,m ως είσοδο;
Αλγόριθμος BlumBlumShub
χ<-290797
m<-50515093
Για ι απο 1 μεχρι ν
    χ<-χ*χ mod m
Τέλος_Επανάληψης
Τέλος BlumBlumShub


ή ακόμα καλύτερα:

Αλγόριθμος BlumBlumShub
χ<-290797
Για ι απο 1 μεχρι ν
    χ<-χ*χ mod 50515093
Τέλος_Επανάληψης
Τέλος BlumBlumShub


Προφανώς ο αλγόριθμος αυτός δεν είναι τετριμμένος και έχει αξία και στην γενική περίπτωση και στις ειδικές. Είσοδος είναι οι τιμές πάνω στις οποίες λειτουργεί ανεξάρτητα πώς τις παίρνει.
Επίσης όλα τα χ αποτελούν και έξοδο (θα μπορούσαμε να τα βάλουμε σε πίνακα και στα αποτελέσματα).
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

gthal

Οκ, Παναγιώτη. Ο 2ος αλγόριθμος πράγματι μπορεί να έχει αξία και να στέκει, είναι διαφορετικός όμως από τον 1ο
Έχει γραφτεί για να λειτουργήσει μόνο για τις συγκεκριμένες τιμές των x,m,ν (υποθέτω θα έδινες και κάποιο ν)
Ο 2ος αλγόριθμος δεν έχει είσοδο γιατί γράφτηκε για να τρέξει μόνο για αυτές τις τιμές.
Ο 1ος έχει είσοδο γιατί γράφτηκε για να τρέξει για οποιαδήποτε τιμή.
Το "instance" και το "class" δεν είναι ίδια. Απέχουν πάρα πολύ στο concept τους.

Και ένα άλλο επιχείρημα:
λες ότι είσοδος στο 2ο και 3ο αλγόριθμο είναι τα x,m,ν απλά και μόνο γιατί ήξερες ότι αυτά ήταν είσοδος στον αλγόριθμο-πατέρα  ;)
Γιατί εγώ ως "αμερόληπτος παρατηρητής" με το σκεπτικό που παρουσιάζεις, στον 3ο αλγόριθμο θα έλεγα ότι και το 1 (αρχική τιμή του ι) είναι επίσης είσοδος. Όπως επίσης και οποιαδήποτε άλλη σταθερή τιμή θα υπήρχε εκεί μέσα. Όλες ίδιες θα μου φαίνονταν αν δεν ήξερα ποια ήταν η πραγματική είσοδος του αρχικού :)
Και το πάω και λίγο πιο πέρα:  θα έλεγα ότι και το mod είναι είσοδος αφού μπορώ να φανταστώ ένα γενικότερο class αλγορίθμων από το οποίο "παράχθηκε" ο 3ος:
Αλγόριθμος BlumBlumShub
Δεδομένα //x,m,ν, function//
Για ι απο 1 μεχρι ν
    χ<-function(χ*χ , m)
Τέλος_Επανάληψης
Τέλος BlumBlumShub

και πάει λέγοντας ....
Φιλικά,
Γιώργος Θαλασσινός

pgrontas

Προσωπικά συμφωνώ ότι όλα τα παραπάνω που ανέφερες είναι είσοδος (και το 1) γιατί σε μια περίπτωση μπορεί να θέλαμε και τις ν τιμές ενώ σε άλλη μπορεί να θέλαμε τις 10 τελευταίες. Τροποποιείται η συμπεριφορά του αλγορίθμου.
Είναι όντως διαφορετικοί αλγόριθμοι, αλλά για μένα διαφορετικοί αλγόριθμοι με είσοδο.
Και αντί για function θα μπορούσαμε να είχαμε ένα πίνακα με τυχαίες τιμές που έχουμε μαζέψει από την φύση και σε κάθε περίπτωση να επιστρέφαμε άλλη.
Όλα είσοδοι. Οι δομές ελέγχου από την άλλη δεν είναι είσοδος (μέχρι αποδείξεως του εναντίον...) ;D
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

gthal

Μα αυτό εννοούσα με το "και πάει λέγοντας"
Και οι δομές ελέγχου θα μπορούσαν να δίνονται ως είσοδος...
...μέχρι να φτάσουμε στον πατέρα όλων των αλγορίθμων: το λευκό χαρτί   ;D
μόνο αυτός δεν έχει είσοδο (σύμφωνα πάντα με το σκεπτικό που δεν ασπάζομαι)
Φιλικά,
Γιώργος Θαλασσινός

pgrontas

Παράθεση από: gthal στις 13 Φεβ 2010, 08:09:53 ΜΜ
Μα αυτό εννοούσα με το "και πάει λέγοντας"
Και οι δομές ελέγχου θα μπορούσαν να δίνονται ως είσοδος...
...μέχρι να φτάσουμε στον πατέρα όλων των αλγορίθμων: το λευκό χαρτί   ;D
μόνο αυτός δεν έχει είσοδο (σύμφωνα πάντα με το σκεπτικό που δεν ασπάζομαι)
Ξέχασες το χρώμα μπορεί να είναι κίτρινο ή μπορεί να μην είναι χαρτί ;D
Μάλλον δίκιο έχει ο Ευριπίδης ότι καλύτερα να το αφήσουμε αυτό το κριτήριο.
Δεν μπορείς να τα βάλεις με τον  :angel:
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson