Θέμα: Εισοδος Αλγορίθμου

[ntzios kostas]

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

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

[alkisg]

Κώστα επειδή οι οδηγίες μαγειρικής δεν ικανοποιούν όλα τα "κριτήρια" των αλγορίθμων, είναι ακατάλληλοι σαν παραδείγματα, καλύτερα να μη συζητάμε γι' αυτούς αλλά για κάποιο άλλο παρόμοιο παράδειγμα των Η/Υ.

Ας πούμε λοιπόν ότι κάποιος ζητάει αλγόριθμο για το κακοδιατυπωμένο πρόβλημα του "να τυπώνει πάντα μια συγκεκριμένη σελίδα στον εκτυπωτή".
Σε αντιστοιχία με την μαγειρική, το αποτέλεσμα (=πάστα) είναι η σελίδα, τα υλικά είναι τα γράμματα και τα σχέδια που θέλουμε να έχει η σελίδα, και δουλειά του αλγορίθμου είναι να μετατρέψει αυτά τα υλικά σε δισδιάστατο πίνακα από pixels, δηλαδή να κάνει rasterize τις γραμματοσειρές, να ζωγραφίσει κύκλους και ορθογώνια κτλ. Δηλαδή με ορολογία Πληροφορικής ο αλγόριθμος είναι ένα πρόγραμμα postscript to bitmap.

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

Ο σχεδιαστής όμως του αλγορίθμου θα πρέπει να σκεφτεί διαφορετικά. Αφού θα φτιάξει που θα φτιάξει postscript to bitmap converter, δεν έχει κανένα νόημα να τον περιορίσει by hardcoding την είσοδο.

Φτιάχνει λοιπόν έναν αλγόριθμο
Αλγόριθμος ΣχεδίασεΣελίδα
Δεδομένα //postscript//
...
Αποτελέσματα //bitmap//
Τέλος ΣχεδίασεΣελίδα

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

Επομένως ο τελικός μας αλγόριθμος θα ήταν
Αλγόριθμος ΤύπωσεΣελίδα
Δεδομένα //όνομα αρχείου postscript//
..
Αποτελέσματα //bitmap//
Τέλος

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

Εδώ λοιπόν μπαίνει στο παιχνίδι το user interface του λειτουργικού, που είναι άλλος αλγόριθμος.
Συγκεκριμένα στα Windows θα κάναμε συντόμευση για το πρόγραμμα ΤύπωσεΣελίδα, και θα του δίναμε παράμετρο (=πάλι είσοδος) το όνομα αρχείου της σελίδας του πελάτη.
Δηλαδή
C:\TupwseSelida.exe C:\Users\Pelatns\Documents\Arxeio.ps

Κι αν δεν μιλάμε για Windows αλλά για μηχάνημα κατασκευής καφέ, το user interface αντιστοιχεί το κουμπάκι που πατάει ο χρήστης για να διαλέξει τι καφέ θέλει.

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

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


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

[ntzios kostas]

Όλα αυτά που είπες Άλκη είναι σωστά. Μπορεί να κρίνεις ότι ένας αλγόριθμος δεν είναι καλοσχεδιασμένος και εγώ μαζί σου, αλλά όμως παρ'όλο που είναι κακοσχεδιασμένος παραμένει αλγόριθμος.

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

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

. Στην άσκηση με το υπολογιστικό σύστημα των εξετάσεων του 2001. Αν ο μαθητής έπερνε πρωτοβουλία και έλεγε αντί για 600000 την αξία του υπολογιστή έγραφε
διάβασε αξία
χρ_τσέπη<- 5000
χρ_γονέων<-5000
όσο χρ_τσεπη< αξία επανάλαβε
....
θα έπαιρνε άριστά;

[sstergou]

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

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

Κώδικας: Text

1. Αλγόριθμος θέμα
2.    Εβδομάδες <- 7 !Υπολογισμός κάπως έτσι : την πρώτη εβδομάδα 5, την δεύτερη 15, την τρίτη 35.... οπότε 7 εβδομάδες
3.    Εμφάνισε εβδομάδες
4. Τέλος θέμα

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

[evry]

  Ναι αυτό πράγματι θα είχε πλάκα γιατί αν κατάλαβα καλά πρόκειται για το άθροισμα n όρων μια γεωμετρικής προόδου με πρώτο όρο το 5000 και λόγο 2. Το άθροισμα αυτό θα ήταν

     Σ = 5000 + 2*5000 + 2*(2*5000) + 2(*2*(2*5000) ) + ....

όμως αυτό όπως γνωρίζουν οι μαθητές είναι : Σ = 5000 * (2^ν - 1) / (2-1) = 5000*(2^ν - 1)
βάζουμε Σ = 600000 και λύνουμε ως προς ν με χρήση λογαρίθμου. Θέλουμε το ελάχιστο ν έτσι ώστε Σ >= 600000

Οπότε ο αλγόριθμος είναι απλά μια εντολή εκχώρησης. Ένας μαθητής που είναι δυνατός στα μαθηματικά θα μπορούσε να το είχε σκεφτεί.

[P.Tsiotakis]

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

[alkisg]

Επειδή βαριέμαι να ψάξω το θέμα, απαντώ στο περίπου:

ΨευτοΑλγόριθμος Άσκηση
Δεδομένα // κανένα, κάνετε λάθος που βάζετε αυτή την άσκηση //
  ΠραγματικόςΑλγόριθμοςΥπολογισμού(5000, 5000, 60000, εβδομάδες)
Αποτελέσματα // εβδομάδες //
Τέλος ʼσκηση

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


Πιστεύω ότι ένας μαθητής που θα έγραφε το παραπάνω έχει κατανοήσει καλύτερα από τους συγκεκριμένους θεματοδότες τις έννοιες των αλγορίθμων.
Είναι 100% σωστός με βάση το βιβλίο αν το γράψει έτσι, δεν μπορεί να του κόψει κανένας καμία μονάδα (εκτός από το Ψευτο- πρόθεμα και τα ψευτοδεδομένα που χαριτολογώντας έβαλα στην αρχή).

Ο ΨευτοΑλγόριθμος που ισοδυναμεί με την ψευτο-είσοδο, ισοδυναμεί επίσης με μια συντόμευση των Windows...

[Σούλας Βασίλης]

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

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

[Σούλας Βασίλης]

Έστω ότι φτιάχνουμε 2 αλγορίθμους που λύνουν την δευτεροβάθμια εξίσωση. Στον πρώτο οι συντελεστές δίνονται με εντολή διάβασε και στο δεύτερο με <-- εσωτερικά. Θα λέγαμε ότι ο πρώτος έχει 3 εισόδους και ο δεύτερος καμμία. Και οι 2 αλγόριθμοι είναι σωστοί με βάση το κριτήριο της εισόδου. Άρα αλγόριθμος χωρίς διάβασε και με <-- είναι καμμία είσοδος. Αλγόριθμος χωρίς διάβασε και χωρίς <-- δεν είναι αλγόριθμος γιατί δεν επιλύει κανένα πρόβλημα.

[P.Tsiotakis]

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

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

[Σούλας Βασίλης]

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

[Σούλας Βασίλης]

Αλγόριθμος μήνυμα
Εμφάνισε 'Καλημέρα'
Τέλος

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

[sstergou]

Νομίζω ότι κάνουμε κύκλους πάλι.

Για μένα είναι αυτονόητο ότι καμία είσοδος σημαίνει ότι δεν υπάρχει είσοδος και ότι παραβιάζεται το κριτήριο ή χαρακτηριστικό της εισόδου.

Πως είναι δυνατόν η μή ύπαρξη (καμία) να είναι τελικά ύπαρξη (μη παραβίαση του κριτηρίου).

Αν απαντηθεί αυτό νομίζω μετά πρέπει να μας βασανίσει το ερώτημα για τη Ζωή το Σύμπαν και τα Πάντα, ε Άλκη;  

[Σούλας Βασίλης]

Τώρα αν κάποιος μου πει.

Αλγόριθμος μήνυμα
Χ<--'Καλημέρα'
Εμφάνισε χ
Τέλος

είναι αυτός σωστός αλγόριθμος; Η απάντηση είναι όχι διότι χρησιμοποίησες την εντολή <-- μόνο για να πληρεί οπτικά τα κριτήρια του σωστού αλγορίθμου. Ουσιαστικά όμως πάλι δεν επιλύει πρόβλημα. Άρα παραδείγματα αλγορίθμων που έχουν βελάκια χωρίς να είναι απαραίτητα για να επιλύουν κάποιο πρόβλημα και επομένως μπορούν να εκφυλιστουν τελικά σε αλγορίθμους χωρίς βελάκια δεν είναι σωστοί αλγόριθμοι.

[alkisg]

Συνάδελφοι πάνω σε αυτό ακριβώς, δώστε μια παραπάνω εξήγηση μπας και καταλάβω τι εννοείτε:
Έστω το απλό πρόβλημα "κάντε έναν αλγόριθμο που να μετράει από το Α ως το Τ με βήμα Β".
Κάποιος το δίνει σαν (κακοδιατυπωμένη κατά την άποψή μου) άσκηση με συγκεκριμένα νούμερα:
"κάντε έναν αλγόριθμο που να μετράει από το 1 ως το 10 με βήμα 2"

Ένας μαθητής το λύνει με αναθέσεις τιμής:
Α <- 1
Τ <- 10
Β <- 2
Για ι από Α μέχρι Τ με_βήμα Β
  Εμφάνισε ι
τέλος_επανάληψης

Ένας άλλος μαθητής το λύνει χωρίς αναθέσεις τιμής:
Για ι από 1 μέχρι 10 με_βήμα 2
  Εμφάνισε ι
τέλος_επανάληψης

Τι διαφορά έχουν τα δύο παραπάνω όσον αφορά στην είσοδο, όπως την ορίζετε;

@sstergou: 42