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

[gthal]

Θωμά, καλά τα λες, αλλά επιμένω ότι χρησιμοποιείς σαν να είναι ταυτόσημες τις έννοιες δεδομένα και είσοδος.
Στο πρώτο διάγραμμα, το βέλος από τη γελαστή φατσούλα μέχρι το Ι/Ο (άντε, μέχρι τη CPU) δεν είναι συνέχεια του υπόλοιπου. Το πρώτο κομμάτι για μένα λέγεται είσοδος και θα μου άρεσε να το φαντάζομαι άλλο χρώμα - ας πούμε πράσινο. Το υπόλοιπο μπλε βέλος δείχνει τη ροή των δεδομένων (άσχετα αν προήλθαν από είσοδο, ή προηγούμενους υπολογισμούς). Στο δεύτερο διάγραμμα, πολύ σωστά, δεν υπάρχει πράσινο βέλος.

Αν είσοδος δεν είναι ότι έρχεται απ' έξω αλλά κάθε εκχώρηση/αρχικοποίηση, τότε θα υποστηρίζετε, φαντάζομαι και αυτό που προκύπτει με συμμετρική λογική:
Έξοδος δεν είναι ότι βγαίνει προς τα έξω. Άρα κάθε αποτέλεσμα, ακόμα και ενδιάμεσο, είναι έξοδος.
Έτσι λοιπόν, στην εντολή S<-S+οτιδήποτε  μέσα στο βρόχο, το S είναι έξοδος ως μερικό αποτέλεσμα, και είναι είσοδος ως ενδιάμεσο δεδομένο για την επόμενη επανάληψη.
Επίσης το S<-0 είναι είσοδος (ως αρχικοποίηση) και έξοδος (ως ενδιάμεσο αποτέλεσμα)  !!!
Και οτιδήποτε μέσα στον αλγόριθμο, θα είναι είσοδος ή έξοδος ή και τα δύο !!! Τίποτα δεν γλιτώνει   
Φαύλος κύκλος, και ποιο το νόημα ? ?
Τι κερδίζουμε με αυτό το σκεπτικό ?
Σπαταλάμε τους χαρακτηρισμούς είσοδο και έξοδο.
Και τελικά πώς θα ονομάσουμε τα δεδομένα που πράγματι έρχονται απ' έξω και πως τα αποτελέσματα που θα δοθούν προς τα έξω ? 

Ουφ! Μπήκα πάλι στον πειρασμό να επιχειρηματολογήσω αλλά δεν πιστεύω, αλήθεια, ότι μπορώ να προσφέρω άλλο στην κουβέντα.
Θα παρακολουθώ μόνο για ορισμούς.
Ίσως να είμαι ξεροκέφαλος (  )  γι αυτό θα περιμένω να δω έναν ορισμό που δε θα συνδέει την είσοδο με το "απ' έξω"  και την έξοδο με το "προς τα έξω"  ώστε να αλλάξω γνώμη   

[gpapargi]

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

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

Έστω ότι θέλουμε να κατασκευάσουμε ένα αλγόριθμο που διαβάζει ένα φυσικό αριθμό και βρίσκει το άθροισμα των διαιρετών του. Να ο αλγόριθμος:

Διάβασε ν
S<-0
Για ι απο 1 μέχρι ν
  Αν ν mod ι = 0 τότε
    S<-S+ι
  Tέλος_αν
Τελος_επαναληψης
Εμφάνισε S

Το ερώτημα είναι: «Ποια είναι η είσοδος;»

Η μια άποψη λέει ότι είσοδος είναι μόνο το ν. Η άλλη άποψη είναι ότι είσοδος είναι το ν, το S<-0 και το ι<-1.

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

[tom]

Η μια άποψη λέει ότι είσοδος είναι μόνο το ν. Η άλλη άποψη είναι ότι είσοδος είναι το ν, το S<-0 και το ι<-1.

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

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

Κώδικας: [Επιλογή]

Αλγόριθμος επιτόκιο
   ποσό<-1500
   Για κ από 1 μέχρι 10
      ποσό<-ποσό +ποσό*4/100
   Τέλος_επανάληψης
   Εμφάνισε ποσό
Τέλος επιτόκιο
Άντε ας μη μπλέκουμε είσοδο σε cpu κλπ και γενικά εσωτερικές διεργασίες του αλγορίθμου.

Στο πλαίσιο του διδακτικού πακέτου δε χρειάζεται τίποτα άλλο πιο φιλοσοφημένο.
Άντε Σάββατο είναι. Πρέπει να πάμε και για κανένα ποτάκι  Αν βρούμε καμία έγκυρη πηγή που λέει κάτι άλλο το ξαναβλέπουμε...

[gpapargi]

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

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

Εδώ κάποια θέματα είναι τα εξής:

Τι συμβαίνει ως προς την περατότητα για ένα daemon που τρέχει στο background (σαν το mail server) και ακούει αιτήσεις, τις εξυπηρετεί και γυρίζει σε  listening mode;

Πριν βιαστεί κάποιος να πει ότι τερματίζει ας δει κάτι σχετικό:

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

Διάβασε ν
Όσο 1<2 επανάλαβε
  ! εντολές που ελέγχουν αν ο ν είναι πρώτος
  Διάβασε ν
Τελος_επαναληψης

Εδώ τι γίνεται ως προς την περατότητα; Υπάρχει διάφορα με τον daemon;

Υπάρχει ταύτιση του αλγορίθμου και του process (πρόγραμμα);

Εδώ έχει ενδιαφέρον να δούμε απόψεις

[sstergou]

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

Οπότε κατά την γνώμη μου υπάρχουν δύο πράγματα που μπορούμε να δεχτούμε στο συγκεκριμένο θέμα :
1)Η περατότητα είναι κριτήριο και κάθε αλγόριθμος (έτσι όπως τον εννοεί ο knuth) πρέπει να τερματίζει.
2)Η περατότητα είναι χαρακτηριστικό και υπάρχουν αλγόριθμοι που δεν τερματίζουν (όπως δαίμονες)

Δεν έχω πρόβλημα με κανένα από τα δύο.

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

[tom]

Υπάρχουν αναφορές στη  βιβλιογραφία  για αλγόριθμους που δεν τερματίζουν γιατί δεν θέτουν στη συνθήκη ένα ερώτημα με απάντηση Ναι/Όχι αλλά απαιτούν την δημιουργία αντικειμένου/εμφάνιση μιας κατάστασης (αναφ. 1), οι οποίοι αλγόριθμοι, αργότερα ονομάστηκαν υπολογιστικές διαδικασίες (αναφ. 2).
Επίσης έχει αποδειχτεί ότι δεν μπορεί να υπάρξει γενικός αλγόριθμος που να αποδεικνύει ότι δεδομένου ενός προγράμματος και μιας/περισσότερων εισόδων, ότι κάμια στιγμή το πρόγραμμα θα σταματήσει ή θα εκτελείται για πάντα (αναφ. 3).

Αλλά αυτά ξεφεύγουν πιστεύω από το πλαίσιο του μαθήματος Α.Ε.Π.Π.

οπότε συμφωνώ με το εξής:

1)Η περατότητα είναι κριτήριο και κάθε αλγόριθμος (έτσι όπως τον εννοεί ο knuth) πρέπει να τερματίζει.

1. Kleene, Stephen C. (First Edition 1952). Introduction to Metamathematics (Tenth Edition 1991 ed.). North-Holland Publishing Company. ISBN 0720421039. 
2. Knuth, Donald (1997). Fundamental Algorithms, Third Edition. Reading, Massachusetts: Addison-Wesley. ISBN 0201896834.
3. Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230–265.

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

Θα πρότεινα να το σπάσουμε το θέμα. Να πάει αλλού η περατότητα. Κάτω από τα αλγοριθμικά αλλά ως υποενότητα.

Επίσης προτείνω να βάλουμε το καταστάλαγμα των απόψεων για την είσοδο ως τελευταία απάντηση και να πάρουμε το ρίσκο και να κλειδώσουμε το θέμα (; . Ήταν σε διαβούλευση τόσο καιρό... οπότε... οι απόψεις ειπώθηκαν νομίζω.

Σ

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

Για την ιστορία νομίζω ότι είναι χρήσιμο να αναφέρω ότι το Διδακτικό πακέτο Β* που έχει καταργηθεί
1. αναφέρει βιβλιογραφικά τον Knuth.
2. "μιλάει" για εκείνα τα χαρακτηριστικά που θεωρούνται απαραίτητα προκειμένου να θεωρήσουμε έναν αλγόριθμο πλήρη, να μπορεί δηλαδή να επιλύσει ένα πρόβλημα αποτελεσματικά,

Με άλλα λόγια μιλάει για χαρακτηριστικά και πληρότητα αλγορίθμου.

Ας δούμε τώρα πως μετέφρασαν-ερμήνευσαν τα χαρακτηριστικά:

1. Είσοδος: Κάθε αλγοριθμος δέχεται ένα σύνολο μεταβλητών εισόδου (που μπορεί να είναι και το κενό σύνολο), οι οποίες αποτελούν τα δεδομένα του αλγορίθμου.

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

2. Έξοδος: Από κάθε αλγόριθμο περιμένουμε ένα αποτέλεσμα, δηλαδή με κάθε αλγόριθμο σχετίζονται μία ή περισσότερες μεταβλητές εξόδου ή αποτελέσματα.

Ακολουθεί παράδειγμα ικανοποίησης.

3. Περατότητα: Κάθε αλγόριθμος πρέπει να προσδιορίζει τη λύση ενός προβλήματος μετά την εκτέλεση πεπερασμένου αριθμού εντολών σε πεπερασμένο χρόνο.

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

Άρα λείπει το ζήτημα υπολογιστικής διαδικασίας κ.τ.λ.

4. Καθοριστικότητα: Οι εντολές ενός αλγορίθμου θα πρέπει να είναι επακριβώς και αυστηρώς καθορισμένες, έτσι που η εκτέλεσή τους να γίνεται χωρίς καμία αμφιβολία και να μην απαιτούνται πρόσθετες επεξηγήσεις.

Δεν υπάρχει παράδειγμα. Το χαρακτηρίζει υποκειμενικό...

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

και συνεχίζει...

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

* με πλάγια ό,τι λέει το βιβλίο μαθητή του Διδακτικού Πακέτου Β.

[evry]

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

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

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

Εντάξει!

Νομίζω ότι είναι λίγο άκαιρο το σχόλιο για το βιβλίο. Γράφτηκε το 1999... 

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

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

[evry]

To 1999!!!! ένα έτος πριν το 2000 δεν υπήρχε η επιστήμη της πληροφορικής? Τα τελευταία 10 χρόνια εμφανίστηκε στην πλανήτη? Το βιβλία του Knuth υπάρχουν από το 1973.

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

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

Ωραία τα λες. Συμφωνούμε όλοι. Μπράβο που υπερασπίζεσαι την επιστήμη της πληροφορικής.

Πάμε παρακάτω;

[tom]

Κοιτάξτε τι βρήκα και θυμήθηκα μια παλιά κουβέντα μας...

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

"Εισαγωγή στη Σύγχρονη Επιστήμη των Υπολογιστών". Les Goldschlager, Andrew Lister, σελ. 85

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

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

Θα προτιμούσα το δεύτερο διότι υπήρξαν στο παρελθόν θέματα εξετάσεων...