Εισοδος Αλγορίθμου

[alkisg]

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

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

[ntzios kostas]

Δηλαδή Άλκη αν για παράδειγμα έχουμε την άσκηση να γίνει αλγόριθμος-πρόγραμμα το οποιο να υπολογίζει το άθροισμα και να εμφανίζει το πλήθος των όρων
1+1/2+1/3... μέχρι το άθροισμα να περάσει το 1000.

ποια είναι η είσοδος;

[gpapargi]

Αυτό που λέει ο Άλκης (και εγώ μαζί) είναι ότι τα 1, 1/2, 1/3 κλπ δεν είναι είσοδος. Είναι μέρος του αλγορίθμου το να τα παράγει. Για να είναι κάτι είσοδος πρέπει να είναι αρχικά «έξω» από τον αλγόριθμο και στη συνέχεια να μπει «μέσα». Εδώ οι τιμές είναι ήδη μέσα στον αλγόριθμο… ο αλγόριθμος παράγει τις τιμές.

Θεωρώ βέβαια ότι ο αλγόριθμος ξεκινάει στην πρώτη γραμμή με το
«Αλγόριθμος πρόσθεση» και ότι είναι από κάτω είναι μέρος του αλγορίθμου.

[ntzios kostas]

Καλημερά Γιώργο.

Άρα αυτή η εκφώνηση του προβλήματος δεν έχει νοήμα και το σχολικό πρέπει να αποσύρει αρκετές αντίστοιχες ασκήσεις.

Για να είναι κάτι είσοδος πρέπει να είναι αρχικά «έξω» από τον αλγόριθμο και στη συνέχεια να μπει «μέσα». .

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

[gpapargi]

Γιατί να μην έχει νόημα; Θα έχεις ένα αλγόριθμο που κάνει πάντα το ίδιο πράγμα. Για μένα το λάθος υπάρχει στην ασαφή γραφή του βιβλίου. Σου λέει ότι ο αλγόριθμος «πάντα» πρέπει να ικανοποιεί το κριτήριο της εισόδου και από την άλλη σου λέει ότι ο αλγόριθμος μπορεί να έχει και «καμία» τιμή σαν είσοδο.

Ποια η διαφορά του να έχεις «καμία» τιμή σαν είσοδο και του να μην έχεις είσοδο; Τι συμπέρασμα μπορεί να βγάλει ένας λογικός άνθρωπος από μια τέτοια πρόταση;

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

[ntzios kostas]

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


Στο παράδειγμα που έδωσα δεν ήθελα να μάθω τι είναι 1, 1/2,1/3 αλλά ποιά είναι η είσοδος.
Στον αλγόριθμο να κατασκευαστεί ένα μαγικό τετράγωνο ποια είναι η είσοδος;
Στο θέμα των εξετάσεων του 2001 με το μαθητή με 600000 δρχ και το υπολογιστικό σύστημα που είναι η εισοδος;
Στο θέμα ΔΣ4 σχολικό σελίδα 82 ποια είναι η είσοδος;
Στο θέμα ΔΣ6 σελίδα 26 ποια είναι η είσοδος;
κτλ...

Εγώ μπορώ να πω ότι είσοδος για όλα τα παραδείγματα, είναι τα δεδομένα από την εκφώνηση. Μπορείτε να βρείτε κάτι άλλο;

[alkisg]

Δηλαδή συνάδελφοι στον υπολογισμό περιφέρειας ενός κύκλου,
περιφέρεια <- 2*π*R
λέτε στους μαθητές ότι είσοδος (=δεδομένα) του αλγορίθμου είναι το 2, το π και το R;

Και κατά προέκταση, είναι όλες οι σταθερές δεδομένα; Ή μόνο αυτές που αναφέρονται στην εκφώνηση; Κι αν όχι, πώς τις ξεχωρίζετε;
Για παράδειγμα, στον παραπάνω υπολογισμό που είπε ο Κώστας, δεδομένα είναι το 1, 2, 3 (που μετράει ο μετρητής i), το 1/2, 1/3, 1/4 (που μετράει το 1/i), το 1+1/2, 1+1/2+1/3 (που υπολογίζει το sum) και το 1000;

Άλλη απορία. Η εντολή ανάθεσης τιμής είναι δηλαδή εντολή εισόδου; Γιατί τότε λέμε ότι εντολή εισόδου είναι η Διάβασε;
Κι αν είναι, τότε γιατί το
x <- y
ή το
i <- i + 1
δεν είναι είσοδοι;

Κι άλλη απορία. Ποιες "απλές εντολές" είναι τελικά εντολές εισόδου; Μόνο η ανάθεση τιμής; Γιατί να μην είναι και η ΑΝ ή η ΟΣΟ ή η αντιμετάθεσε που είναι επίσης απλές;


Γράφω και το πρωτότυπο κομμάτι από το βιβλίο του Knuth, μήπως ρίξει φως στο θέμα:

3) Input. An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins. These inputs are taken from specified sets of objects. In Algorithm E, for example, there are two inputs, namely m and n, which are both taken from the set of positive integers.

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

[ntzios kostas]

Κάτι πρόβλημα έχει σήμερα το site και τώρα μπόρεσα να μπω.


Άλκη οι αλγόριθμοι που σου ανέφερα έχουν είσοδο;

[alkisg]

Σύμφωνα με το βιβλίο, όχι, οι ασκήσεις
"κάντε ένα πρόγραμμα που να μετράει από το 1 ως το 10", ή
"να γράφει το αποτέλεσμα μιας συνάρτησης για x από 1 ως 10 με βήμα 0.01"
δεν έχουν είσοδο. Και συμφωνώ μαζί του. Είναι κλειστά συστήματα που παράγουν πάντα τα ίδια αποτελέσματα, επομένως η έξοδός τους δεν εξαρτάται από την είσοδο αφού δεν υπάρχει είσοδος.

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

Στην πράξη όμως σπάνια θα δούμε τέτοιους αλγορίθμους (εγώ δεν νομίζω να έχω δει κανέναν σε πραγματικό κώδικα). Π.χ. τον παραπάνω αλγόριθμο αν τον υλοποιούσε κάποιος προγραμματιστής θα τον μετέφραζε ως "να γράφει τις τιμές της συνάρτησης από Α ως Τ με βήμα Β", έτσι ώστε ο αλγόριθμος να έχει 3 εισόδους και να είναι και πιο ευέλικτος/χρήσιμος.
Ή, για τον υπολογισμό των 1000 πρώτων δεκαδικών του π, δεν θα έγραφαν τέτοιον αλγόριθμο, θα έβαζαν το 1000 σαν είσοδο (=εντολή Διάβασε) με όνομα Ν ώστε να αποφεύγουν να κάνουν compile κάθε φορά. Ας μην ξεχνάμε ότι όταν γραφόταν αυτές οι γραμμές (του Knuth) το compile έπαιρνε αρκετό χρόνο, δεν ήταν το "πατάω F9 και είμαι έτοιμος" που είναι τώρα.


Εν ολίγοις, πιστεύω ότι η συγκεκριμένη παράγραφος που συζητάμε είναι μια χαρά.
Διαφωνώ στο ότι τα αναγραφόμενα κριτήρια είναι υποχρεωτικά για να χαρακτηριστεί ως αλγόριθμος ένα κομμάτι κώδικα. Βέβαια θα απόφευγα να ζητήσω από τους μαθητές να υλοποιήσουν αλγορίθμους που να μην ικανοποιούν αυτά τα κριτήρια (δηλαδή δεν θεωρώ δόκιμο το ότι το βιβλίο έχει τέτοιες ασκήσεις).
Συγκεκριμένα για το κριτήριο της εισόδου, εάν αυτή απουσιάζει, ίσως απλά να χαρακτήριζα τον συγκεκριμένο αλγόριθμο "όχι καλοσχεδιασμένο", αφού θα παράγει πάντα την ίδια έξοδο, και επομένως αυτή μπορεί κάλλιστα να αντικατασταθεί από απλές εντολές ΓΡΑΨΕ ή από lookup table. Το τελευταίο το έχω δει συχνά σε "πραγματικά" προγράμματα, έχουν απλά ένα πινακάκι με τις τιμές που χρειάζονται, π.χ. τα πρώτα 1000 δεκαδικά του π. Και φυσικά ένα πινακάκι δεν χαρακτηρίζεται ως αλγόριθμος...

[Καρκαμάνης Γεώργιος]

Συνάδερφοι οπως βλέπετε η συζήτηση δεν οδηγεί πουθενά. Εχουμε χωριστεί σε δυο στραπόδεδα :Σε αυτούς που πιστεύουν ότι οι απλές εντολές θεωρούνται ως είσοδο και στους υπόλοιπους με την αντίθετη άποψη. Και τα δυο στρατόδετα αντιπαραθέτουν ηχηρά παραδείγματα για να δικαιολογήσουν την αποψή τους. Το αποτέλεσμα είναι πως κάποιος τρίτος που παρακολουθεί την σηζήτηση δεν μπορεί να  αποφασίσει ποιες απο τις δυο απόψεις είναι η πιο σωστή.
Νομίζω ότι δεν θα βγάλουμε καμία άκρη.
Μια λύση είχε δοθεί απο τον Αλκη σε παλιότερο θέμα η οποία ήταν :
1. να επικοινωνήσουμε με τον συγγραφέα του βιβλίου ώστε να μας διατυπώση τις απόψεις του για αυτό το θέμα και γενικά τι εννοεί με τον όρο "καμία μια ή περισσότερες απο μια εισοδους".
και συμπληρώνω :
2. να διατυπωθούν στους συγγραφείς όλες αυτές οι απόψεις και οι προβληματισμοί που αναφέρθηκαν παραπάνω
3. να  επιδιώξουμε να δοθεί μια επισημη απάντηση  απο το παιδαγωγικό ινστιτούτο , ανάλογη αυτή που είχει βγει για τους τελεστές div και mod για να καταλάβουμε επιτέλους τι ακριβώς γίνεται.

[ntzios kostas]

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

Οι περισσότεροι αλγόριθμοι δεν απαιτούν δεδομένα από τον χρήστη για να λειτουργήσουν. Μην έχουμε στο μυαλό μας μόνο τους αλγόριθμους που γίνονται πρόγραμμα. Υπάρχουν και οι άλλοι που δεν θα τους εκτελέσει ο υπολογιστής. Στα βιβλία μαγείρικής οι περισσότεροι αλγόριθμοι δεν απαιτούν δεδομένα από τον χρήστη, αυτόν δηλαδή που θα απολαύσει τα αποτελέσματα. (Είναι μεσημέρι ... καταλαβαίνετε)

[alkisg]

Οι περισσότεροι αλγόριθμοι δεν απαιτούν δεδομένα από τον χρήστη για να λειτουργήσουν.

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

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

Εξάλλου το βιβλίο καθηγητή προτείνει σε περιπτώσεις μεγάλης εισόδου να χρησιμοποιούνται εντολές σαν τη read data της basic (αντίστοιχη με το αρχείο εισόδου του Διερμηνευτή και της Γλωσσομάθειας) ακριβώς για να ξεχωρίζει η είσοδος και να μην χρησιμοποιούνται εντολές ανάθεσης για εισαγωγή τιμών, χαλώντας έτσι την είσοδο του αλγορίθμου.

[ntzios kostas]

Μπράβο...

Μάλιστα ο Knuth περιγράφει τα δεδομένα (=κρέας, αλάτι, κτλ) και τα αποτελέσματα σε έναν αλγόριθμο μαγειρικής, αλλά είναι πολύ μεγάλο για να το αντιγράψω εδώ... Smiley

Το κρέας και το αλάτι τα βάζει ως δεδομένα. Το κρέας και το αλάτι ο χρήστης δεν ξέρει ότι έχουν μπει στο φαί του, άρα δεν τα δίνει αυτός, Την ποσότητά τους ή την ύπαρξή τους πρέπει να την ξέρει ο προγραμματιστής, αυτός που έγραψε την συνταγή.
Η πρώτη εντολή της συνταγής μπορεί να είναι: Βάλε δύο κιλά κρέας στην κατσαρόλα (αντίστοιχα χ<- 2)
Και δεν θα λέει: ζήτα από τον χρήστη για το φαγητό πόσο κρέας θέλει; Αν ζήταγε πάντως από εμένα θα είχα πεθάνει της πείνας πάντως 

[alkisg]

Το κυρίως μέρος από το mail που έστειλα:

Είναι στο τέλος της σελίδας 25 και μιλάει για τα κριτήρια των αλγορίθμων:
        Είσοδος (input). Καμία, μία ή περισσότερες τιμές δεδομένων πρέπει να
        δίνονται ως είσοδοι στον αλγόριθμο. Η περίπτωση που δεν δίνονται τι-
        μές δεδομένων εμφανίζεται, όταν ο αλγόριθμος δημιουργεί και επεξερ-
        γάζεται κάποιες πρωτογενείς τιμές με τη βοήθεια συναρτήσεων παρα-
        γωγής τυχαίων αριθμών ή με τη βοήθεια άλλων απλών εντολών.
       
Πάνω σ' αυτό, και μετά από αρκετή συζήτηση, πολλοί συνάδελφοι πιστεύουν ότι η εντολή ανάθεσης τιμής
        α <- 1
αποτελεί είσοδο για ένα πρόγραμμα, ενώ οι υπόλοιποι πιστεύουν ότι είσοδο αποτελούν μόνο η εντολή Διάβασε, η εντολή Δεδομένα της ψευδογλώσσας (χρησιμοποιείται περίπου σαν τις παραμέτρους εισόδου των υποπρογραμμάτων) καθώς και εντολές παραγωγής πρωτογενών τιμών όπως είναι η random (αλλά όχι η ανάθεση τιμής).

Ένα πιο χαρακτηριστικό παράδειγμα:
        «Να γράψετε πρόγραμμα που να υπολογίζει τη συνάρτηση y(x) = x²-3x+2 για όλες τις τιμές του x από -1 έως 3 σε βήματα του 0.1.»
Με την παρακάτω υλοποίηση:
        Αλγόριθμος Άσκηση1
        Για x από -1 μέχρι 3 με_βήμα 0.1
            Εμφάνισε x^2-3*x+2
        τέλος_επανάληψης
        Τέλος ʼσκηση1

Έχει αυτός ο αλγόριθμος είσοδο ή όχι; Οι πρώτοι πιστεύουν ότι το -1, το 3 και το 0.1 είναι είσοδος, οι δεύτεροι ότι ο αλγόριθμος αυτός δεν έχει είσοδο.

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

Απάντηση του συγγραφέα του σχετικού κεφαλαίου:

Με απλά λόγια θα έλεγα το εξής.
Συμφωνώ με εκείνους που λενε ότι ουσιαστικά το input δίνεται
με το Διάβασε. Με την ίδια (αντίθετη) λογική και το α=1 και
το for/while κλπ είναι είσοδος. Δηλαδή, εν τέλει κάθε ανάθεση
είναι είσοδος ?

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

[ntzios kostas]

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

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

Εγώ θα σε ρωτήσω και κάτι άλλο Αλκη. Έχω το πρόβλημα να βρω όλους τους πρώτους από το 1 μέχρι το 100000. Αυτό δηλαδή δεν πρέπει να το λύσω αλγοριθμικά πρέπει οπωσδήποτε να αναγκάσω το χρήστη να δώσει τιμή. Ξέρω ότι τα δεδομένα του προβλήματος είναι 3: η αρχική τιμή, η τελική και πιθανών ο ορισμός για τους πρώτους.
Αν άλλαζα το πρόβλημα και λέω να εμφανίσει όλους από το 1 μέχρι το χ που το χ θα μου το δίνει ο χρήστης. Τότε ξέρω ότι τα δεδομένα του προβλήματος είναι η αρχική τιμή, η τελική τιμή που τη δίνει ο χρήστης και ο ορισμός των πρώτων. Αν όλα αυτά τα δεδομένα του προβλήματος και στις δύο περιπτώσεις δεν αποτελούν και δεδομένα του αλγόριθμου τότε πραγματικά δεν ξέρω τι να πω.

Ο συγγραφέας του βιβλίου δεν απάντησε πάντως ποια είναι η είσοδος στον αλγόριθμο που έδωσες. Ούτε όμως είπε ότι είναι λάθος ο αλγόριθμος αυτός.


Ειλικρινά ο στόχος μου είναι πάντως να βγάλουμε μία άκρη.