Ανάλυση λειτουργίας της "Για"

Ξεκίνησε από Νίκος Αδαμόπουλος, 11 Φεβ 2009, 12:22:59 ΜΜ

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

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

Γεια σας κι από μένα

Θέτω υπό την κρίση σας μια ανάλυση για τον τρόπο λειτουργίας της Για...από...μέχρι...με_βήμα
που έχω αναρτήσει στο http://dide.ilei.sch.gr/keplinet/education/aepp_for.php και που έχουμε συμπεριλάβει στο Ενημερωτικό Δελτίο μας (για να το διαφημίσουμε και λίγο! ) στο http://dide.ilei.sch.gr/keplinet/ed/ed23_jan_2009.pdf

Με εκτίμηση

Νικόλαος Αδαμόπουλος
Υπεύθυνος ΚΕ.ΠΛΗ.ΝΕ.Τ. ΔΔΕ Ηλείας

Ταχ. Διεύθ:
   2ο ΕΠΑ.Λ. Πύργου
   (περιοχή Κοκκιλώνι)
   27100 Πύργος
Τηλ: 26210-27316
Email: plinet [at] dide.ilei.sch.gr
URL: http://dide.ilei.sch.gr/keplinet



gpapargi

Καλημέρα

Η Για και οι μετατροπές είναι μια πονεμένη ιστορία που εμένα τουλάχιστο με έχει απασχολήσει πολύ.

Αυτό που αναφέρεις στο τέλος ως δύσκολο θέμα στις εξετάσεις, είχε σχολιαστεί παλαιότερα από το στέκι. Σίγουρα θα σε ενδιαφέρει η κουβέντα. Φαίνεται πως η λύση που προτάθηκε από την επιτροπή (αλλά και όλο το θέμα) ήταν λάθος. Διάβασέ το μέχρι το τέλος.
https://alkisg.mysch.gr/steki/index.php?topic=1157.0

Το πλήθος των βημάτων της Για καθώς και η τελική τιμή του μετρητή είχε συζητηθεί και για την περίπτωση δεκαδικών αριθμών στα παρακάτω links
Απόδειξη
https://alkisg.mysch.gr/steki/index.php?topic=287.msg1953#msg1953

Συμπεράσματα:
https://alkisg.mysch.gr/steki/index.php?topic=287.msg2037#msg2037

Τέλος ένα θέμα σκοτεινό ακόμα (για μένα) είναι το πως ακριβώς προκύπτει ότι με βήμα 0 έχουμε ατέρμονα βρόχο. Δε μου αρκεί το ότι το λέει το βιβλίο. Το βιβλίο θα πρέπει να ορίσει μια μετατροπή σε Όσο μέσω της οποίας θα αποδειχτεί το ότι το πλήθος των επαναλήψεων της Για είναι άπειρο. 

sstergou

Παράθεση από: gpapargi στις 11 Φεβ 2009, 02:27:09 ΜΜ
Δε μου αρκεί το ότι το λέει το βιβλίο. Το βιβλίο θα πρέπει να ορίσει μια μετατροπή σε Όσο μέσω της οποίας θα αποδειχτεί το ότι το πλήθος των επαναλήψεων της Για είναι άπειρο.

Γιατί πρέπει η για να μετατρέπεται πάντα σε όσο;
Δεν μπορεί να είναι μια ξεχωριστή δομή που ορίζεται διαφορετικά;

Αυτή η μετατροπή δεν είναι σωστή;

Κώδικας: Ψευδογλώσσα
Για ι από 1 μέχρι 10 με_βήμα 0
Εμφάνισε ι
Τέλος_επανάληψης

ι<-1
Όσο ι<=10 επανάλαβε 
Εμφάνισε ι
ι<- ι + 0
Τέλος_επανάληψης

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

#3
Παράθεση από: gpapargi στις 11 Φεβ 2009, 02:27:09 ΜΜ
Το πλήθος των βημάτων της Για καθώς και η τελική τιμή του μετρητή είχε συζητηθεί και για την περίπτωση δεκαδικών αριθμών στα παρακάτω links

Ουπς! Ούτε που σκέφτηκα τους δεκαδικούς! Πράγματι δεν μπορεί να μπει το DIV. Ωστόσο η λογική του τύπου παραμένει η ίδια μόνο που αντί για div μπαίνει το A_M. Κατά άλλα δεν βλέπω κάποιο collision... Thnks. Θα το διορθώσω.

Και γενικά δεν βλέπω διαφορές σε σχέση με τις επικρατούσες απόψεις...

gpapargi

Είναι και το θέμα του 2001 με τη μετατροπής από Μέχρις_ότου σε Για. Για Α=1.1 και Μ=4 οι 2 ψευδοκώδικες δίνουν διαφορετικά αποτελέσματα. Είμαι βέβαιος ότι ξέφυγε το θέμα της επιτροπής.

gpapargi

Παράθεση από: sstergou στις 11 Φεβ 2009, 02:50:43 ΜΜ
Παράθεση από: gpapargi στις 11 Φεβ 2009, 02:27:09 ΜΜ
Δε μου αρκεί το ότι το λέει το βιβλίο. Το βιβλίο θα πρέπει να ορίσει μια μετατροπή σε Όσο μέσω της οποίας θα αποδειχτεί το ότι το πλήθος των επαναλήψεων της Για είναι άπειρο.

Γιατί πρέπει η για να μετατρέπεται πάντα σε όσο;
Δεν μπορεί να είναι μια ξεχωριστή δομή που ορίζεται διαφορετικά;

Αυτή η μετατροπή δεν είναι σωστή;

Κώδικας: Ψευδογλώσσα
Για ι από 1 μέχρι 10 με_βήμα 0
Εμφάνισε ι
Τέλος_επανάληψης

ι<-1
Όσο ι<=10 επανάλαβε 
Εμφάνισε ι
ι<- ι + 0
Τέλος_επανάληψης


Δες το εξής παράδειγμα:
Για ι από 5 μέχρι 1 με_βήμα 0
  Εμφάνισε ι
Τέλος_επανάληψης

Με βάση τη μετατροπή που γράφεις (δηλαδή χρήση του τελεστή <= όταν το βήμα είναι 0) έχουμε

ι<-5
Όσο ι<=1 επανάλαβε
  Εμφάνισε ι
  ι<-ι+0
Τέλος_επανάληψης

Το οποίο δεν εκτελείται καμία φορά και άρα έχουμε βήμα 0 αλλά όχι ατέρμονα βρόχο.
Γι αυτό λέω ότι το αν ο βρόχος είναι ατέρμονας ή όχι είναι κάτι που πρέπει να προκύψει μετά τη μετατροπή και όχι να το λέμε σα να είναι ορισμός.

Η ουσία είναι η εξής:
Κάθε εντολή επανάληψης πρέπει να έχει ένα σημείο που να σηματοδοτεί το τέλος της, ένα σημείο που να σηματοδοτεί την αρχή της (εκεί που θα επιστρέψει μετά το σημείο τέλους) και το σημαντικότερο: μια συνθήκη (στην αρχή ή στο τέλος) βάση της οποίας θα γίνει η διακοπή του βρόχου. Στη "Για"  δεν ξέρουμε ποια είναι αυτή η συνθήκη.

Για να το πω με άλλα λόγια:
Ποιο είναι το διάγραμμα ροής της Για σε κάθε περίπτωση βήματος έτσι ώστε να έχουμε ατέρμονα βρόχο όταν το βήμα είναι 0;

sstergou

Εγώ πάλι νομίζω ότι ο τελεστής εξαρτάται από την αρχική και την τελική τιμή και όχι από το βήμα.
Αν η αρχική τιμή είναι μικρότερη από την τελική, ο τελεστής είναι "<=" αλλιώς ο τελεστής είναι ">="

Οπότε το παράδειγμά σου
Κώδικας: Ψευδογλώσσα
Για ι από 5 μέχρι 1 με_βήμα 0
  Εμφάνισε ι
Τέλος_επανάληψης


θα το μετέτρεπα σε

Κώδικας: Ψευδογλώσσα
ι<-5
Όσο ι>=1 επανάλαβε
  Εμφάνισε ι
  ι<-ι+0
Τέλος_επανάληψης

Το οποίο δίνει επίσης ατέρμονα βρόχο.

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

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

Λοιπόν, εντάξει... Τώρα μόλις διάβασα πιο συστηματικά όλη την κουβέντα που είχε γίνει από πέρυσι για το θέμα του 2001. Η αλήθεια είναι ότι δεν την είχα υπόψη μου (το παραδέχομαι: ενώ είχα υπόψη μου το Στέκι, ωστόσο δεν το χρησιμοποιούσα. Υπόσχομαι ενεργή συμμετοχή από δω και πέρα για να μου δοθεί άφεση αμαρτιών!).

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

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

Ως προς αυτά που αναφέρονται μεταξύ sstergou και gpapargi, ακριβώς αυτό εννοούσα κι εγώ στην διατύπωση "Όμως δεν διευκρινίζεται τι θα γίνει, για παράδειγμα, στην περίπτωση: Για i από 5 μέχρι 1 με_βήμα 0. Θα έχουμε άπειρες επαναλήψεις ή δεν θα έχουμε καμία;". Άρα κι εδώ ο σκοπός του κειμένου για ελαφρό προβληματισμό επιτελείται μια χαρά :) )!!!

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

(Χο, χο, ξεκίνησε κουβέντα: μόλις είδα κι άλλο post οπότε συμπληρώνω: )

Δεν νομίζω ότι ο τελεστής αλλάζει έτσι απλά από "<=" σε ">=" επειδή θα μας βόλευε! Νομίζω ότι απλά οι συγγραφείς δεν το πολυσκέφτηκαν και για αυτό υπάρχει αυτή η ασάφεια. Μην πάμε τώρα εμείς να θεμελιώσουμε ακαδημαϊκά κάτι που απλά ξέφυγε από τους άλλους. Εδώ ακόμα και οι διαφορετικές υλοποιήσεις  μεταγλωττιστών για επίσημες - υπαρκτές γλώσσες είναι δυνατόν να συμπεριφέρονται διαφορετικά σε τέτοιες "κακοτοπιές" που απλά μπορούμε να τις αποφεύγουμε...

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

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

Παράθεση από: sstergou στις 12 Φεβ 2009, 10:15:02 ΠΜ
Εγώ πάλι νομίζω ότι ο τελεστής εξαρτάται από την αρχική και την τελική τιμή και όχι από το βήμα.
Αν η αρχική τιμή είναι μικρότερη από την τελική, ο τελεστής είναι "<=" αλλιώς ο τελεστής είναι ">="

Οπ, οπ!!! Συνάδελφοι προσοχή... Μην τα απλοποιούμε τόσο πολύ! Τότε στο παράδειγμα του βιβλίου "Για κ από 5 μέχρι 1" θα είχαμε άπειρες επαναλήψεις!!! Δεν γίνεται αυτό ούτε στις κανονικές γλώσσες...

gpapargi

Παράθεση από: sstergou στις 12 Φεβ 2009, 10:15:02 ΠΜ
Εγώ πάλι νομίζω ότι ο τελεστής εξαρτάται από την αρχική και την τελική τιμή και όχι από το βήμα.
Αν η αρχική τιμή είναι μικρότερη από την τελική, ο τελεστής είναι "<=" αλλιώς ο τελεστής είναι ">="

Υπάρχει στη σελίδα 44 στα πλάγια το παράδειγμα "Για ι από 5 μέχρι 1" που δεν εκτελείται καμία φορά.

Παράθεση από: sstergou στις 12 Φεβ 2009, 10:15:02 ΠΜ
Αλλά ακόμη και αν αποδειχτεί ότι έχεις δίκιο και πάλι δεν καταλαβαίνω γιατί ο ορισμός της για πρέπει να περνάει μέσω της όσο.

Υπάρχει το διάγραμμα ροής της Για στη σελίδα 43 του σχολικού.

Επίσης δες κάτω κάτω στο link
https://alkisg.mysch.gr/steki/index.php?topic=912.msg8645#msg8645

Πάει να εξηγήσει κάτι αλλά νομίζω ότι τα κάνει πιο πολύ σαλάτα. Ορίζει τη Για αλλιώς στη ΓΛΩΣΣΑ και αλλιώς στην ψευδογλώσσα και δεν εξηγεί πως προκύπτουν οι άπειρες επαναλήψεις στην ψευδογλώσσα με βήμα 0.

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

#10
Παράθεση από: gpapargi στις 12 Φεβ 2009, 12:06:13 ΜΜ
Επίσης δες κάτω κάτω στο link
https://alkisg.mysch.gr/steki/index.php?topic=912.msg8645#msg8645

Πάει να εξηγήσει κάτι αλλά νομίζω ότι τα κάνει πιο πολύ σαλάτα. Ορίζει τη Για αλλιώς στη ΓΛΩΣΣΑ και αλλιώς στην ψευδογλώσσα και δεν εξηγεί πως προκύπτουν οι άπειρες επαναλήψεις στην ψευδογλώσσα με βήμα 0.

Κι εγώ δεν συμφωνώ με αυτή τη διαφορετική προσέγγιση για τη ΓΛΩΣΣΑ ούτε καταλαβαίνω από πού προέκυψε... Δεν πρόκειται να την υιοθετήσω κι ούτε θεωρώ πως με αυτό θα δημιουργήσω τελικά πρόβλημα στους μαθητές...

sstergou

Παράθεση από: gpapargi στις 12 Φεβ 2009, 12:06:13 ΜΜ
Υπάρχει στη σελίδα 44 στα πλάγια το παράδειγμα "Για ι από 5 μέχρι 1" που δεν εκτελείται καμία φορά.

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

Παράθεση από: Νίκος Αδαμόπουλος στις 12 Φεβ 2009, 10:55:05 ΠΜ
Δεν νομίζω ότι ο τελεστής αλλάζει έτσι απλά από "<=" σε ">=" επειδή θα μας βόλευε! Νομίζω ότι απλά οι συγγραφείς δεν το πολυσκέφτηκαν και για αυτό υπάρχει αυτή η ασάφεια. Μην πάμε τώρα εμείς να θεμελιώσουμε ακαδημαϊκά κάτι που απλά ξέφυγε από τους άλλους.
Και εγώ τα ίδια υποστηρίζω. Έλα όμως που η επιτροπή αλλά και οι κάθε είδους υπεύθυνοι μας τραβάνε προς τα πίσω

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

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

Κώδικας: Ψευδογλώσσα
Για μ από αρχή μέχρι τελος με_βήμα β
Τέλος_επανάληψης


Κώδικας: Ψευδογλώσσα
μ <- αρχή
Όσο ΣυνθήκηΓια(μ, τέλος, β) επανάλαβε
μ <- μ + β
Τέλος_επανάληψης

Αλγόριθμος ΣυνθήκηΓια(αρχή, τέλος, β)
βήμαΘετικό <- β > 0
βήμαΑρνητικό <- β <0
απομακρύνεται <- (αρχή < τέλος και βήμαΑρνητικό) ή (αρχή > τέλος και βήμαΘετικό)
Αν απομακρύνεται τότε
  ΣυνθήκηΓια <- ψευδής
αλλιώς
  Αν βήμαΘετικό τότε
    ΣυνθήκηΓια <- αρχή <= τέλος
  αλλιώς 
    ΣυνθήκηΓια <- αρχή >= τέλος
Τέλος_αν
Τέλος ΣυνθήκηΓια


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

P.Tsiotakis

Προσωπικά, απο το σχολικό βιβλίο έχω καταλάβει το παρακάτω:

Αν βήμα = 0 τότε  ! πρώτα αυτός ο έλεγχος
  Άπειρες επαναλήψεις
Αλλιώς_αν β >0 τότε
  Αν τελική >= αρχική τότε
     κάποιες επαναλήψεις
  Αλλιώς
     ΚΑΜΙΑ επανάληψη
  Τέλος_αν
Αλλιώς
  Αν τελική <= αρχική τότε
     κάποιες επαναλήψεις
  Αλλιώς
     ΚΑΜΙΑ επανάληψη
  Τέλος_αν
Τέλος_αν

και οφείλω να πω οτι είναι ιδιαίτερα απλός αλγόριθμος

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

Παράθεση από: sstergou στις 12 Φεβ 2009, 05:13:21 ΜΜ
Και εγώ τα ίδια υποστηρίζω. Έλα όμως που η επιτροπή αλλά και οι κάθε είδους υπεύθυνοι μας τραβάνε προς τα πίσω

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

Άρα μέχρι στιγμής συμφωνούμε όλοι:
1. Υπάρχει ασάφεια στο τι κάνει το "Για ι από 5 μέχρι 1 με_βήμα 0".
2. Η μετατροπή "Για ι από 5 μέχρι 1 με_βήμα 0" σε Όσο μάς απασχολεί μόνο κατά την υλοποίηση ενός διερμηνευτή ή μεταγλωττιστή.
3. Πιστεύουμε (και ελπίζουμε) ότι κανένα σοβαρό μέλος επιτροπής εξετάσεων δεν θα βάλει θέμα πάνω σε αυτήν την κακοτοπιά...

Από κει και πέρα πιστεύω ότι:
1. Δεν υπάρχει λόγος να εμπλέξουμε τους μαθητές πάνω σε αυτό και να τους αγχώνουμε...
2. Ας μην βλέπουμε το δέντρο και χάνουμε το δάσος, ή με άλλα λόγια: εμάς μας νοιάζει περισσότερο το πώς θα διδάξουμε τους αλγορίθμους (σε μαθητές ας μην ξεχνάμε) και λιγότερο η θεωρητική (ακαδημαϊκή) τακτοποίηση του θέματος. Δηλαδή εμένα προσωπικά δεν με χαλάει κιόλας η συγκεκριμένη ασάφεια. Ας είναι το κερασάκι που ομορφαίνει την τούρτα! Αν δεν υπήρχε κι αυτό τότε τι θα βρίσκαμε για να κουβεντιάζουμε και να προβληματιζόμαστε; Τίποτα στην ζωή δεν είναι πλήρως τακτοποιημένο. Και οι άνθρωποι αρρωσταίνουν, και το περιβάλλον χάνει την ισορροπία του, και οι μηχανές χαλάνε, και οι υπολογιστές έχουν πεπερασμένα όρια για τους αριθμούς, και τα λογισμικά δεν καλύπτουν όλες τις δυνατές καταστάσεις και κολλάνε, και τα προϊόντα δεν είναι πλήρως συμβατά με τα πρότυπα........

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

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

P.Tsiotakis

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

ps: Γνωριστήκαμε στην Πάτρα;

Στο μέλλον θα μιλάμε στον ενικό  :)