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

[gpapargi]

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

[Σπύρος Δουκάκης]

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

ΣΔ

[Σπύρος Δουκάκης]

Τα αλγοριθμικά κριτήρια θέλουν αναδιατύπωση. Κάποια σχόλια αναφέρονται παρακάτω:

Ο όρος «κριτήρια» είναι αρκετά αυστηρός γιατί σημαίνει ότι αν κάποιο τμήμα κώδικα δεν έχει είσοδο τότε δεν αποτελεί αλγόριθμο. Πχ σε ένα  τμήμα κώδικα που υπολογίζει το άθροισμα 1^3 + 2^3 +3^3 +…100^3 δεν υπάρχει είσοδος αλλά είναι υπερβολικό να λέμε ότι δεν είναι αλγόριθμος.
Επίσης υπάρχουν προγράμματα που δεν έχουν έξοδο αλλά απλώς ξεκινούν άλλα προγράμματα (startup scripts).
Ο Knuth δίνει τον όρο «features» δηλαδή χαρακτηριστικά (για την είσοδο και την έξοδο) και όχι κριτήρια. Αυτό σημαίνει ότι αν κάποιο κομμάτι κώδικα δεν τα πληρεί τότε  δε σημαίνει ότι δεν είναι αλγόριθμος.

Επίσης αυτό που περιγράφει το βιβλίο ως κριτήριο της αποτελεσματικότητας δεν είναι σαφές. Στο βιβλίο του Knuth εννοείται κάτι άλλο από αυτό που φαίνεται στο σχολικό βιβλίο.
Στην αποτελεσματικότητα δεν έχει γίνει σωστή μεταφορά του όρου «effectiveness» από τα αγγλικά. Μεταφράστηκε σαν «αποτελεσματικότητα» αλλά το νόημα είναι κάτι σαν «πραγματοποιησιμότητα». Δηλαδή χρησιμοποιείται η ερμηνεία «πραγματοποιώ» της λέξης effect.

Effectiveness σημαίνει να είναι οι λειτουργίες απλές έτσι ώστε να μπορούν να εκτελεστούν ακριβώς και σε πεπερασμένο χρονικό διάστημα από κάποιον με μολύβι και χαρτί. Παραδείγματα παραβίασης του effectiveness (από το βιβλίο του Knuth) είναι το να έχεις μια συνθήκη της μορφής
Αν η ε έχει λύση
όπου η «ε» είναι μια εξίσωση που ζητούμε μόνο ακέραια λύση (διοφαντική) για την οποία δεν ξέρουμε αν υπάρχει λύση.

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

Πρόταση: Να αναθεωρηθούν τα κριτήρια σύμφωνα με τον Knuth ή να αφαιρεθεί η είσοδος, έξοδος και αποτελεσματικότητα και να παραμείνει η περατότητα και η καθοριστικότητα που είναι «καλώς ορισμένες».

[gpapargi]

Εννοείται ότι το παραπάνω κείμενο με εκφράζει απόλυτα και θα ήθελα να προσθέσω κάτι στο σκετικό με το οποίο διατυπώθηκε η πρόταση: Οι συγγραφική ομάδα προσπάθησε να μεταφέρει τα αλγοριθμικά κριτήρια από τον Knuth. Η προσωπική μου άποψη είναι ότι δεν κατάλαβε καλά το νόημα και τη μετέφερε με λάθος τρόπο.
 
Κατά συνέπεια θεωρώ ότι η πιο σωστή κίνηση που μπορούμε να κάνουμε είναι να διαβάσουμε προσεκτικά τον Knuth και να καταλάβουμε τι θέλει να πει. Η πρότασή μας πρέπει να είναι αυτό που εννοεί ο Knuth διότι αυτή ήταν η πρόθεση της συγγραφικής ομάδας.

Διαφορετικά θα πρέπει να δοθούν έγκυρες πηγές από την βιβλιογραφία.

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

Δόξα σοι ο Θεός (ο Knuth εννοώ  ) 

[sstergou]

Νομίζω το πρόβλημα το έχουμε στην είσοδο και την αποτελεσματικότητα.

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

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

[pgrontas]

Για την πραγματοποιησιμότητα συμφωνώ.
Για την είσοδο μια συζήτηση είχε γίνει εδώ (https://alkisg.mysch.gr/steki/index.php?topic=1569.0) με ένα εύστοχο σχόλιο από τον Γιώργο τον Νικολακάκη προς το τέλος.
Προσωπικά νομίζω ότι δεν έχει σχέση με τα αποτελέσματα. Πχ. αν έχεις μια συνάρτηση που πάντα επιστρέφει την τιμή 1 δεν μπορούμε να πούμε πως το 1 είναι η είσοδος;
Ή αν έχεις έναν αλγόριθμο που ξεκινάει ένα script δεν μπορούμε να πούμε πως ο προσδιορισμός του script είναι η είσοδος (έστω και αν είναι hardcoded).
Θεωρώ ότι η είσοδος πρέπει να αποτελεί κριτήριο (έστω και ενσωματωμένη) και μπορεί να συνδυαστεί με το σχήμα που έχουν οι μαθητές στο μυαλό τους Δεδομένα->Επεξεργασία->Πληροφορία.

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

[sstergou]

Τη θυμάμαι την κουβέντα.

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

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

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

Για την έξοδο συμφωνώ, δεν είναι απαραίτητα τιμή.

[ntzios kostas]

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

Ο όρος «κριτήρια» είναι αρκετά αυστηρός γιατί σημαίνει ότι αν κάποιο τμήμα κώδικα δεν έχει είσοδο τότε δεν αποτελεί αλγόριθμο. Πχ σε ένα  τμήμα κώδικα που υπολογίζει το άθροισμα 1^3 + 2^3 +3^3 +…100^3 δεν υπάρχει είσοδος αλλά είναι υπερβολικό να λέμε ότι δεν είναι αλγόριθμος.
Επίσης υπάρχουν προγράμματα που δεν έχουν έξοδο αλλά απλώς ξεκινούν άλλα προγράμματα (startup scripts).
Ο Knuth δίνει τον όρο «features» δηλαδή χαρακτηριστικά (για την είσοδο και την έξοδο) και όχι κριτήρια. Αυτό σημαίνει ότι αν κάποιο κομμάτι κώδικα δεν τα πληροί τότε  δε σημαίνει ότι δεν είναι αλγόριθμος.

[sstergou]

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

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

 

[Σπύρος Δουκάκης]

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

Κριτήρια που πρέπει να ικανοποιεί ένας αλγόριθμος

να γίνει

Χαρακτηριστικά που πρέπει να έχει ένας αλγόριθμος.

Για την είσοδο.

Έχουμε κοιτάξει ορισμό του Knuth που λέει An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins. Προσπάθησα να εντοπίσω ένα ΔΙΚΟ του παράδειγμα με zero input αλλά δεν βρήκα... Μήπως να του τηλεφωνήσουμε;;

Πάντως στο άρθρο The Interactive Nature of Computing: Refuting the Strong Church–Turing Thesis των Dina Goldin and Peter Wegner (2008) λέει

In his definition of algorithms, Knuth was consistent with the mathematical function based foundations of the theory of computation. He explicitly specified that algorithms are closed; no new input is accepted once the computation has begun: ‘‘An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins.’’ Knuth distinguished algorithms from arbitrary computation that may involve I/O.

το οποίο νομίζω ότι μας απαντάει και σε άλλο ανοικτό θέμα...

Με τον ορισμό του Στάθη συμφωνούμε;

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

ΣΔ

[gpapargi]

Με τον ορισμό του Στάθη συμφωνούμε;

Εγώ συμφωνώ αρκεί να μη λέμε τη λέξη ορισμός. Είναι βαριά λέξη και κρίνεται πιο αυστηρά. Δεν υπάρχει λόγος να το αποκαλέσουμε ορισμό και να εισάγουμε περιττή αυστηρότητα. Και για μένα για να είναι κάτι είσοδος πρέπει να είναι αρχικά έξω από τον αλγόριθμο και στη συνέχει να μπει μέσα. Η εντολή χ<-2 δεν είναι είσοδος.

[pgrontas]

Εγώ συμφωνώ αρκεί να μη λέμε τη λέξη ορισμός. Είναι βαριά λέξη και κρίνεται πιο αυστηρά. Δεν υπάρχει λόγος να το αποκαλέσουμε ορισμό και να εισάγουμε περιττή αυστηρότητα. Και για μένα για να είναι κάτι είσοδος πρέπει να είναι αρχικά έξω από τον αλγόριθμο και στη συνέχει να μπει μέσα. Η εντολή χ<-2 δεν είναι είσοδος.

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

[gpapargi]

Πάντως στο άρθρο The Interactive Nature of Computing: Refuting the Strong Church–Turing Thesis των Dina Goldin and Peter Wegner (2008) λέει

In his definition of algorithms, Knuth was consistent with the mathematical function based foundations of the theory of computation. He explicitly specified that algorithms are closed; no new input is accepted once the computation has begun: ‘‘An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins.’’ Knuth distinguished algorithms from arbitrary computation that may involve I/O.

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

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

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

[gpapargi]

Μια άλλη λέξη που μου ήρθε για το effectiveness είναι η «εφικτότητα». Δεν ξέρω αν υπάρχει κοινή ρίζα στο εφικτό και το effect. Είδα κάτι τέτοιο στο λεξικό αλλά καλό είναι να πει τη γνώμη του κάποιος φιλόλογος/γλωσσολόγος.

Το ουσιαστικό ερώτημα που θέλω να θέσω για να είμαστε σίγουροι ότι εννοούμε το ίδιο πράγμα είναι το εξής:  Η εντολή «Λύσε τη δευτεροβάθμια» ή «ταξινόμησε τον πίνακα» ικανοποιεί το effectiveness  ή όχι;

Για μένα Ναι. Για να παραβιάζεται το effectiveness θα πρέπει να μην μπορεί να εκτελεστεί η εντολή με το χέρι. Πρέπει να υπάρχει κάτι το ανέφικτο. Αφού η δευτεροβάθμια λύνεται με το χέρι και ο πίνακας ταξινομείται με το χέρι με  χαρτί και μολύβι τότε η εντολή είναι effective.
Το ότι δεν μπορεί να εκτελεστεί από τον υπολογιστή οφείλεται στο ότι αυτός που εκτελεί τον αλγόριθμο δεν ξέρει τι να κάνει σε αυτή την περίπτωση. Άρα λέω καθοριστικότητα. Η εντολή είναι άγνωστο σύμβολο. Κάθε άγνωστο σύμβολο θα έλεγα ότι παραβιάζει την καθοριστικότητα. Αν αντικατασταθεί με υποπρόγραμμα θα εκτελεστεί κανονικά. Ενώ κατά τη δική μου κατανόηση, κάτι που παραβιάζει το effectiveness δεν μπορεί να εκτελεστεί ούτε αν αντικατασταθεί με υποπρόγραμμα. Υπάρχει κάτι το ανέφικτο.

Δηλαδή δίνω έμφαση στο αν μπορεί να εκτελεστεί με χαρτί και μολύβι δηλαδή με το χέρι.