ΠΑΝΕΛΛΗΝΙΕΣ 2005 ΘΕΜΑ 1ο Α2

Ξεκίνησε από vasiko, 13 Δεκ 2005, 10:15:57 ΜΜ

« προηγούμενο - επόμενο »

vasiko

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

P.Tsiotakis


Δεν είναι ολόκληρος αλγόριθμος, είναι τμήμα αλγορίθμου και θα ακολουθήσει η έξοδος...

vasiko

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

EleniK

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

Ελένη
Ελένη Κοκκίνου
Καθηγήτρια Πληροφορικής, ΠΕ19

vasiko

Ζητώ συγνώμη αλλά είχα δει το θέμα από το site του Παναγιώτη όπου δεν υπάρχει η εντολή εξόδου και γι άυτό και η παραπάνω ερώτηση.
Θεωρήστε ότι το θέμα έληξε

P.Tsiotakis


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

Με εκτίμηση,

ΥΓ: Ελένη, μπορείς να αλλάξεις το όνομά σου σε "Έλλη" και να υπογράφεις αυτόγραφα ε;

EleniK

Παναγιώτη νομίζω ότι  το όνομα αλλάζει αλλά ο μισθός..?  :)
Πάντως έχω ακρετά πειράγματα από τ απαιδιά σχετικά με το θέμα.  8)
Ελένη Κοκκίνου
Καθηγήτρια Πληροφορικής, ΠΕ19

gpapargi

Καλημέρα

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

Στο θέμα της περατότητας με απασχολεί το εξής:

Είναι σωστό το να θεωρούμε «κριτήριο» την περατότητα αφού δεν μπορούμε πάντα να αποφανθούμε για το αν ένας αλγόριθμος τερματίζει ή όχι;
Πχ Ας υποθέσουμε ότι βάζουμε ένα υπολογιστή να ψάχνει να βρει  μια λύση μιας διοφαντικής εξίσωσης για την οποία δεν ξέρουμε αν έχει λύση ή όχι (δεν έχουμε απόδειξει ότι έχει ούτε ότι δεν έχει λύσεις). Μόλις βρει μια λύση ο υπολογιστής σταματά. Εδώ είναι φανερό ότι δεν μπορούμε να αποφανθούμε για το κριτήριο της περατότητας. Επίσης υπάρχει και το περίφημο halting problem που αποδείχτηκε άλυτο από τον Turing. Με βάση αυτά είναι σωστό να θεωρούμε ως αλγοριθμικό κριτήριο την περατότητα αφού δεν μπορούμε να αποφανθούμε πάντα για αυτή;

Βέβαια αυτή κουβέντα ξεφεύγει από το μάθημα. Το ζήτημα που μας απασχολεί για το μάθημα είναι αυτό της αποτελεσματικότητας και της εισόδου. Το ζήτημα της εξόδου και της περατότητας όπως τα θέτω είναι κυρίως «φιλοσοφικά» και δεν αφορούν τους μαθητές. Για την περατότητα τι λέτε;

alkisg

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

Όσον αφορά στο τι λέμε στους μαθητές, το θέμα έχει λήξει.

Προσωπικά όμως εγώ δεν μπορώ να δεχτώ ότι αν αφαιρέσουμε από τα Windows το κουμπί τερματισμού, τότε αυτά δεν αποτελούν αλγόριθμο! Χρονοπρογραμματισμός διεργασιών, paging, swapping, διαχείριση παραθύρων κτλ δηλαδή δεν είναι αλγόριθμοι; Ή τα ATM που θεωρητικά δεν έχουν τέλος, και αν θυμάμαι καλά υπάρχει και σαν παράδειγμα στο βιβλίο, δεν προγραμματίζονται με αλγορίθμους;

gpapargi

Για το τι θα πούμε στους μαθητές συμφωνούμε απόλυτα. Το βιβλίο είναι σαφές.

Στα υπόλοιπα να προσθέσω και τις client server εφαρμογές, όπου ο server τρέχει συνέχεια και ακούει σε κάποια συγκεκριμένη TCP port για requests από τον client. Ένα απλό telnet ή η αποστολή ενός mail προυποθέτει ότι κάποιο server process τρέχει κάπου ασταμάτητα και ακούει στην πόρτα της συγκεκριμένης εφαρμογής. Εδώ το πρόγραμμα είναι έτσι φτιαγμένο ώστε να μην σταματάει ποτέ. Και εγώ επίσης δε καταλαβαίνω γιατί δεν είναι αλγόριθμος.

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

nplatis

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

Η διατύπωση του βιβλίου (σελ. 44) σχετικά με το βήμα είναι: «το βήμα δεν μπορεί να είναι μηδέν, γιατί τότε ο βρόχος εκτελείται επ' άπειρον».

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

Αυτό το «δεν μπορεί» είναι αρκετά αόριστο, κατά τη γνώμη μου...

P.Tsiotakis


nplatis

Ευχαριστώ, είχα ψάξει λίγο αλλά δεν είχα βρει το θέμα εκείνο...
Φυσικά η κατάληξη εκείνου του θέματος είναι ότι υπάρχει ασάφεια... :o

Αλήθεια, αν υποθέσουμε ότι το βήμα 0 απαγορεύεται, θα είχαμε πρόβλημα καθοριστικότητας (όπως έγραψα) ή αποτελεσματικότητας (όπως γράφτηκε στο άλλο θέμα (https://alkisg.mysch.gr/steki/index.php?topic=1118.msg7261#msg7261));

P.Tsiotakis

δε μπορεί να είναι 0, ΓΙΑΤΙ ΣΕ ΑΥΤΗΝ ΤΗΝ ΠΕΡΙΠΤΩΣΗ εχω άπειρες επαναλήψεις.

καθαρά περατότητα

nplatis

Συγγνώμη που το συνεχίζω, απλώς η αρχική ερώτησή μου είναι στην ουσία η ίδια με αυτή που τίθεται προς το τέλος του https://alkisg.mysch.gr/steki/index.php?topic=1118.msg7261#msg7261

Το «δεν μπορεί» που λέει το βιβλίο δεν είναι ξεκάθαρο: σημαίνει «δεν επιτρέπεται» ή «επιτρέπεται αλλά οδηγεί σε μη περατότητα»;

Και η δεύτερη ερώτηση ήταν: στην περίπτωση που «δεν επιτρέπεται» (δηλ. έχουμε συντακτικό σφάλμα), υπάρχει πρόβλημα καθοριστικότητας ή αποτελεσματικότητας;

ΥΓ. Νομίζω ότι θα πρέπει να γίνει σύσταση προς το Υπουργείο, για την επόμενη αναθεώρηση του προγράμματος να υποβληθεί και πλήρης γραμματική της γλώσσας που θα χρησιμοποιηθεί, αν δεν είναι κάποια από τις καθιερωμένες :-)