Σε συζήτηση με τους μαθητές σχετικά με κάποια θέματα των πανελληνίων εξετάσεων έπεσε στο τραπέζι η άποψη ότι στο πρώτο θέμα στο υποερώτημα Α2 εκτός από το κριτήριο της περατότητας παραβιάζεται και το κριτήριο της εξόδου. Μάλιστα δύο από τους μαθητές ήταν κάθετοι ότι θα το έγραφαν στην απάντησή τους οπωσδήποτε.
Ποια είναι η άποψή σας;
Δεν είναι ολόκληρος αλγόριθμος, είναι τμήμα αλγορίθμου και θα ακολουθήσει η έξοδος...
Αυτή ήταν και η δική μου απάντηση αλλά νομίζω έχουν ένα δίκιο οι μαθητές όταν λένε ότι αφού στην εκφώνηση δεν αναφέρεται ότι είναι τμήμα αλγόρίθμου είναι λογικό να σκεφτούν ότι δεν ικανοποιείται και το κριτήριο της εξόδου.
Νομίζω ότι επειδή η εκφώνηση αναφέρει ποιο κριτήριο δεν ικανοποιείται θα απαντούσα μόνο την περατότητα. Η έξοδος υπάρχει σαν εντολή (εμφάνισε), αλλά το γεγονός ότι τελικά δεν θα έχει έξοδο είναι νομίζω συνέπεια της μη ύπαρξης περατότητας και μόνο.
Ελένη
Ζητώ συγνώμη αλλά είχα δει το θέμα από το site του Παναγιώτη όπου δεν υπάρχει η εντολή εξόδου και γι άυτό και η παραπάνω ερώτηση.
Θεωρήστε ότι το θέμα έληξε
Ok, είχα ξεχάσει το Εμφάνισε S ( :o ), αλλά δεν αλλάζει κάτι κατά τη γνώμη μου. Είναι τμήμα αλγορίθμου και είναι σαφές οτι η επιτροπή θεμάτων επιθυμεί να συζητηθεί η περατότητα. Αν ήταν σωστός ο βρόχος Για το συζητάγαμε
Με εκτίμηση,
ΥΓ: Ελένη, μπορείς να αλλάξεις το όνομά σου σε "Έλλη" και να υπογράφεις αυτόγραφα ε;
Παναγιώτη νομίζω ότι το όνομα αλλάζει αλλά ο μισθός..? :)
Πάντως έχω ακρετά πειράγματα από τ απαιδιά σχετικά με το θέμα. 8)
Καλημέρα
Γενικά οι κουβέντες γύρω από τα αλγοριθμικά κριτήρια δεν είναι οι αγαπημένες μου.
Με την είσοδο έχει υπάρξει διαφωνία ως προς το αν υπάρχουν αλγόριθμοι χωρίς είσοδο. Με την έξοδο πέρυσι είχα υποστηρίξει την άποψη ότι είναι δυνατό να υπάρξει αλγόριθμος χωρίς έξοδο. Με την αποτελεσματικότητα. .. εκεί κι αν υπάρχει μπέρδεμα. Το βιβλίο του Knuth το οποίο χρησιμοποιείται σαν αναφορά πάνω στα αλγοριθμικά κριτήρια λέει ότι αποτελεσματικότητα σημαίνει να είναι δυνατό η ίδια δουλειά να γίνει με μολύβι και χαρτί, δηλαδή να είναι γνωστός ο αλγόριθμος. Με βάση αυτά, η εντολή «Λύσε τη δευτεροβάθμια» δεν παραβιάζει την αποτελεσματικότητα αφού αλγόριθμος λύσης της δευτεροβάθμιας είναι γνωστός.
Στο θέμα της περατότητας με απασχολεί το εξής:
Είναι σωστό το να θεωρούμε «κριτήριο» την περατότητα αφού δεν μπορούμε πάντα να αποφανθούμε για το αν ένας αλγόριθμος τερματίζει ή όχι;
Πχ Ας υποθέσουμε ότι βάζουμε ένα υπολογιστή να ψάχνει να βρει μια λύση μιας διοφαντικής εξίσωσης για την οποία δεν ξέρουμε αν έχει λύση ή όχι (δεν έχουμε απόδειξει ότι έχει ούτε ότι δεν έχει λύσεις). Μόλις βρει μια λύση ο υπολογιστής σταματά. Εδώ είναι φανερό ότι δεν μπορούμε να αποφανθούμε για το κριτήριο της περατότητας. Επίσης υπάρχει και το περίφημο halting problem που αποδείχτηκε άλυτο από τον Turing. Με βάση αυτά είναι σωστό να θεωρούμε ως αλγοριθμικό κριτήριο την περατότητα αφού δεν μπορούμε να αποφανθούμε πάντα για αυτή;
Βέβαια αυτή κουβέντα ξεφεύγει από το μάθημα. Το ζήτημα που μας απασχολεί για το μάθημα είναι αυτό της αποτελεσματικότητας και της εισόδου. Το ζήτημα της εξόδου και της περατότητας όπως τα θέτω είναι κυρίως «φιλοσοφικά» και δεν αφορούν τους μαθητές. Για την περατότητα τι λέτε;
Το βιβλίο στον ορισμό της περατότητας αναφέρει ότι μια διαδικασία που δεν τελειώνει μετά από έναν συγκεκριμένο αριθμό βημάτων δεν αποτελεί αλγόριθμο, αλλά λέγεται απλά υπολογιστική διαδικασία.
Όσον αφορά στο τι λέμε στους μαθητές, το θέμα έχει λήξει.
Προσωπικά όμως εγώ δεν μπορώ να δεχτώ ότι αν αφαιρέσουμε από τα Windows το κουμπί τερματισμού, τότε αυτά δεν αποτελούν αλγόριθμο! Χρονοπρογραμματισμός διεργασιών, paging, swapping, διαχείριση παραθύρων κτλ δηλαδή δεν είναι αλγόριθμοι; Ή τα ATM που θεωρητικά δεν έχουν τέλος, και αν θυμάμαι καλά υπάρχει και σαν παράδειγμα στο βιβλίο, δεν προγραμματίζονται με αλγορίθμους;
Για το τι θα πούμε στους μαθητές συμφωνούμε απόλυτα. Το βιβλίο είναι σαφές.
Στα υπόλοιπα να προσθέσω και τις client server εφαρμογές, όπου ο server τρέχει συνέχεια και ακούει σε κάποια συγκεκριμένη TCP port για requests από τον client. Ένα απλό telnet ή η αποστολή ενός mail προυποθέτει ότι κάποιο server process τρέχει κάπου ασταμάτητα και ακούει στην πόρτα της συγκεκριμένης εφαρμογής. Εδώ το πρόγραμμα είναι έτσι φτιαγμένο ώστε να μην σταματάει ποτέ. Και εγώ επίσης δε καταλαβαίνω γιατί δεν είναι αλγόριθμος.
Νομίζω πως αυτός που έκανε το διαχωρισμό σε αλγορίθμους και υπολογιστικές διαδικασίες είχε στο νου του κυρίως αριθμητική επίλυση μαθηματικών προβλημάτων.
Ξαναδίνοντας πρόσφατα αυτό το διαγώνισμα σε μαθητές μου, μου δημιουργήθηκε η απορία αν το κριτήριο που παραβιάζεται θα μπορούσε να είναι η καθοριστικότητα αντί για την περατότητα.
Η διατύπωση του βιβλίου (σελ. 44) σχετικά με το βήμα είναι: «το βήμα δεν μπορεί να είναι μηδέν, γιατί τότε ο βρόχος εκτελείται επ' άπειρον».
Με αυτή τη διατύπωση δεν είναι σαφές κατά πόσον η χρήση βήματος 0 είναι συντακτικό σφάλμα (άρα θα είχαμε πρόβλημα καθοριστικότητας) [αναδιατύπωση του βιβλίου: το βήμα δεν επιτρέπεται να είναι μηδέν, καθώς αν επιτρεπόταν κάτι τέτοιο θα είχαμε πρόβλημα περατότητας] ή όχι [αναδιατύπωση του βιβλίου: το βήμα δεν έχει νόημα να είναι μηδέν, καθώς τότε θα υπάρχει πρόβλημα περατότητας].
Αυτό το «δεν μπορεί» είναι αρκετά αόριστο, κατά τη γνώμη μου...
δες λίγο τη συζήτηση:
https://alkisg.mysch.gr/steki/index.php?topic=1118.0
Ευχαριστώ, είχα ψάξει λίγο αλλά δεν είχα βρει το θέμα εκείνο...
Φυσικά η κατάληξη εκείνου του θέματος είναι ότι υπάρχει ασάφεια... :o
Αλήθεια, αν υποθέσουμε ότι το βήμα 0 απαγορεύεται, θα είχαμε πρόβλημα καθοριστικότητας (όπως έγραψα) ή αποτελεσματικότητας (όπως γράφτηκε στο άλλο θέμα (https://alkisg.mysch.gr/steki/index.php?topic=1118.msg7261#msg7261));
δε μπορεί να είναι 0, ΓΙΑΤΙ ΣΕ ΑΥΤΗΝ ΤΗΝ ΠΕΡΙΠΤΩΣΗ εχω άπειρες επαναλήψεις.
καθαρά περατότητα
Συγγνώμη που το συνεχίζω, απλώς η αρχική ερώτησή μου είναι στην ουσία η ίδια με αυτή που τίθεται προς το τέλος του https://alkisg.mysch.gr/steki/index.php?topic=1118.msg7261#msg7261
Το «δεν μπορεί» που λέει το βιβλίο δεν είναι ξεκάθαρο: σημαίνει «δεν επιτρέπεται» ή «επιτρέπεται αλλά οδηγεί σε μη περατότητα»;
Και η δεύτερη ερώτηση ήταν: στην περίπτωση που «δεν επιτρέπεται» (δηλ. έχουμε συντακτικό σφάλμα), υπάρχει πρόβλημα καθοριστικότητας ή αποτελεσματικότητας;
ΥΓ. Νομίζω ότι θα πρέπει να γίνει σύσταση προς το Υπουργείο, για την επόμενη αναθεώρηση του προγράμματος να υποβληθεί και πλήρης γραμματική της γλώσσας που θα χρησιμοποιηθεί, αν δεν είναι κάποια από τις καθιερωμένες :-)