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

[evry]

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

ΠΡΟΓΡΑΜΜΑ Υπολογισμός_Ε
ΣΤΑΘΕΡΕΣ
    Ν=100
ΜΕΤΑΒΛΗΤΕΣ
    ΑΚΕΡΑΙΕΣ:
   ΠΡΑΓΜΑΤΙΚΕΣ:
ΑΡΧΗ
    Ε <-- 0
    ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν
         Ε <-- Ε + 1/Παραγοντικό(i)
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΓΡΑΨΕ Ε
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Ποια είναι η είσοδος? Θα μπορούσε να θεωρηθεί σαν είσοδος του αλγορίθμου το Ν? Δεν είναι η παράμετρος εκείνη από την οποία εξαρτάται το αποτέλεσμα?
Δεν έχω πρόβλημα να υιοθετήσουμε αυτό που λέει ο Άλκης ότι καμία εντολή εκχώρησης δεν αποτελεί είσοδο. Το δικό μου πρόβλημα είναι πως αν το δεχτούμε αυτό τότε το παραπάνω πρόγραμμα θα αποτελεί αλγόριθμο? Δηλαδή την είσοδο την θεωρούμε σαν χαρακτηριστικό ή σαν προαπαιτούμενο για να είναι μια υπολογιστική διαδικασία αλγόριθμος?

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

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

[pgrontas]

Δηλαδή την είσοδο την θεωρούμε σαν χαρακτηριστικό ή σαν προαπαιτούμενο για να είναι μια υπολογιστική διαδικασία αλγόριθμος?

Νομίζω ότι αν την ορίσουμε σαν χαρακτηριστικό το ελαφραίνουμε λίγο και (προσωπικά) μου είναι πιο ευκολοχώνευτο.
Δεν είναι όμως μεγάλη αλλαγή;

ΥΓ: Όπως προαναφέρθηκε ο Knuth αυτό που λέμε εμείς κριτήρια τα ονομάζει (features) χαρακτηριστικά, αλλά αναφέρει και το important.

Besides merely being a finite set of rules that gives a sequence of operations for solving
a specific type of problem, an algorithm has five important features:

[gthal]

Το δικό μου πρόβλημα είναι πως αν το δεχτούμε αυτό τότε το παραπάνω πρόγραμμα θα αποτελεί αλγόριθμο?

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

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

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

[alkisg]

Ποια είναι η είσοδος? Θα μπορούσε να θεωρηθεί σαν είσοδος του αλγορίθμου το Ν? Δεν είναι η παράμετρος εκείνη από την οποία εξαρτάται το αποτέλεσμα?

Όχι. Όταν μιλάμε για είσοδο και έξοδο αλγορίθμου, θα πρέπει να τον σκεφτούμε σαν ένα μαύρο κουτί, που του δίνουμε είσοδο, κάνει επεξεργασία, και μας δίνει έξοδο.
Την είσοδο του αλγορίθμου την βλέπουμε έξω από το κουτί. Το εσωτερικό του κουτιού δεν το βλέπουμε καν, τον κώδικα τον έχει κρατήσει επτασφράγιστο μυστικό ο προγραμματιστής στα υπόγεια της Microsoft, και εμείς έχουμε μόνο το .exe ή το .dll.

Ο αλγόριθμος (κουτί) που έγραψες παραπάνω μας δίνει πάντα το e, χωρίς να περιμένει είσοδο από εμάς. Άρα δεν έχει είσοδο.

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

Ουσιαστικά αυτό που κάνεις είναι να λες στον χρήστη, «άνοιξε το μαύρο κουτί, πήγαινε στην τάδε γραμμή, και πείραξέ τη, και έτσι θα μεταβάλλεις την έξοδο».
Όμως έτσι ο χρήστης αλλάζει τον αλγόριθμο, το ίδιο το κουτί, όχι την είσοδο του κουτιού.
Είναι το ίδιο με το να του λες να αλλάξει κάποιον τελεστή ή κάποιον τελεστέο ή ακόμα και κάποια εντολή του αλγορίθμου. Θα αλλάξει μεν το αποτέλεσμα, αλλά η μεταβολή του ίδιου του κουτιού δεν μπορεί να θεωρηθεί είσοδος...

[gthal]

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

[evry]

Ναι αλλά εμείς πρέπει να μαθαίνουμε στα παιδιά τη φιλοσοφία του ανοικτού κώδικα, αφού θα χρησιμοποιούν και ubuntu οπότε δεν θα υπάρχουν μαύρα κουτιά.
Επίσης να σημειωθεί ότι ο Άλκης χρησιμοποίησε τη λέξη "Microsoft" για να στηρίξει ένα από τα επιχειρήματά του.

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

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

[gthal]

Εσύ τι λες evry ?
Ομολογώ ότι δεν έχω ξεκάθαρα διαμορφωμένη άποψη.

(ΥΓ. κι εγώ νομίζω πως αυτό το ερώτημα πρέπει να απαντήσουμε)

[pgrontas]

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

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

[gthal]

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

Είσοδος = από έξω προς τα μέσα
input = in και put   

[pgrontas]

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

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

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

[gthal]

Εντάξει, αν από το κουτί του Άλκη και μετά δεν έχεις πειστεί, θα πάω πάσο.
Αλλά αλήθεια, σε ένα πρόγραμμα με 2000 μεταβλητές και καμιά 400000 εκχωρήσεις πρωτογενών τιμών θα έλεγες ότι οοολα αυτά είναι είσοδος; (γιατί οποιοδήποτε και να πειράξεις, θα αλλάξει το αποτέλεσμα, δεν υπάρχει περίπτωση - αν δεν κρασάρει  )

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

Επίσης, σε μια διαδικασία, όπως τις ξέρουμε στη ΓΛΩΣΣΑ
τι θεωρείς είσοδο; τα πάντα; ό,τι μεταβλητή και ότι εκχώρηση χρησιμοποιείται στον κώδικά της;  Οι παράμετροί της δεν έχουν ειδική σημασία;

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

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

Κι εγώ με αυτή την αίσθηση μένω...

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

[pgrontas]

Αλλά αλήθεια, σε ένα πρόγραμμα με 2000 μεταβλητές και καμιά 400000 εκχωρήσεις πρωτογενών τιμών θα έλεγες ότι οοολα αυτά είναι είσοδος; (γιατί οποιοδήποτε και να πειράξεις, θα αλλάξει το αποτέλεσμα, δεν υπάρχει περίπτωση - αν δεν κρασάρει  )

Το θέμα δεν νομίζω να είναι ποσοτικό είναι ποιοτικό.

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

Δεν είναι όλα είσοδος. Είπαμε για τις δομές ελέγχου.

Επίσης, σε μια διαδικασία, όπως τις ξέρουμε στη ΓΛΩΣΣΑ
τι θεωρείς είσοδο; τα πάντα; ό,τι μεταβλητή και ότι εκχώρηση χρησιμοποιείται στον κώδικά της;  Οι παράμετροί της δεν έχουν ειδική σημασία;

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

Επειδή η συζήτηση κάνει κύκλους δεν χρειάζεται να συμφωνούμε σε όλα.

[gthal]

Ναι, πάσο.
(απλά νόμιζα ότι αυτό είναι τόσο θεμελιώδες που έπρεπε να συμφωνούμε    )

[pgrontas]

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

Ας δούμε όμως και κάτι άλλο:
Ο Γιώργος ο Παπαργύρης ρώτησε νωρίτερα: Είναι ο daemon που συνεχώς ακούει αιτήσεις αλγόριθμος;
Αναφέρθηκαν διάφορα επιχειρήματα γι' αυτό.
Ο Knuth όμως έχει σαφή και ξεκάθαρη θέση (το ανέφερε και ο Στάθης νωρίτερα)

(A procedure that has all of the characteristics of an algorithm except that it
possibly lacks finiteness may be called a computational method. Euclid originally
presented not only an algorithm for the greatest common divisor of numbers, but
also a very similar geometrical construction for the "greatest common measure"
of the lengths of two line segments; this is a computational method that does
not terminate if the given lengths are incommensurable. Another example of a
nonterminating computational method is a reactive process, which continually
interacts with its environment.)

Μήπως η πραγματική ασάφεια είναι:
Πόσο αυστηροί πρέπει να είμαστε με τα κριτήρια / χαρακτηριστικά ενός αλγορίθμου;