Ασκηση με Υπερβαση μεγέθους πίνακα

[olga_ath]

Καλησπέρα

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


Ευχαριστώ προκαταβολικά

Ολγα

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

Δηλαδή, τι ακριβώς θέλεις να εξετάζει; 

[evry]

Εννοείς κάτι τέτοιο;

Ένας μαθητής έγραψε τον παρακάτω αλγόριθμο για να ελέγξει πόσα στοιχεία έχουν τη μέγιστη τιμή
σε έναν ταξινομημένο πίνακα α[Ν] σε φθίνουσα σειρά.
Ποιο αλγοριθμικό κριτήριο δεν πληρούν οι παρακάτω εντολές και γιατί?
Τροποποιήστε τις έτσι ώστε να ικανοποιούνται όλα τα κριτήρια


Δεδομένα // α, Ν //
θέση <- 1
Όσο α[θέση]=α[1] και θέση <= Ν Επανάλαβε
   θέση <- θέση + 1
Τέλος_Επανάληψης
Εμφάνισε  θέση-1

[pgrontas]

Η προσπέλαση της θέσης Ν+1 ενός πίνακα Ν θέσεων είναι συντακτικό λάθος. Σ ή Λ.

[sstergou]

Νομίζω είναι ένα ξεκάθαρο λογικό λάθος.

[manpap]

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

Αν θες κάτι πιο απλό:
Δίνεται ...
Για ι απο 1 μεχρι Ν
Αν α[ι-1]+α[ι+1]=α[ι] τοτε
  γραψε α[ι-1], α[ι], α[ι+1]
τελοσ_αν
τελοσ_επαναληψης

Γενικά τονίζω στους μαθητές μετά την ολοκλήρωση μιας άσκησης να ελέγχουν τους δείκτες που χρησιμοποιούν να ανήκουν στο [1,Ν] και να τροποποιούν τα όρια της επανάληψης ή να βάζουν αν μέσα...

[gthal]

Η προσπέλαση της θέσης Ν+1 ενός πίνακα Ν θέσεων είναι συντακτικό λάθος. Σ ή Λ.

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

[meteo_xampos]

Μια παρόμοια άσκηση που έχει ο Παναγιώτης ο Τσιωτάκης στο βιβλίο του (νομίζω στο κεφάλαιο 46 με τη σειριακή αναζήτηση)...
Δόθηκε σε ένα μαθητή το εξής πρόβλημα: 'Να γράψετε αλγόριθμο ο οποίος θα ψάχνει ένα όνομα,  που δίνεται σαν είσοδος από το πληκτρολόγιο, σε ένα πίνακα αλφαριθμητικών 5 θέσεων, και να εκτυπώνει κατάλληλο μήνυμα, ανάλογα με το αν βρέθηκε ή όχι'.

Αλγόριθμος Αναζήτηση
Δεδομένα //ΠΙΝ//
Διάβασε ον
ι <- 1
Όσο (ΠΙΝ[ι] <> ον) ΚΑΙ (ι<=5) επανάλαβε
   ι <- ι+1
Τέλος_επανάληψης
Αν (ι<=5) τότε
   Εμφάνισε 'Δεν υπάρχει το όνομα που δώσατε προς αναζήτηση'
Αλλιώς
   Εμφάνισε 'Υπάρχει το όνομα που δώσατε προς αναζήτηση'
Τέλος_Αν

Είναι σωστός ο παραπάνω αλγόριθμος;

[evry]

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

Αλγόριθμος Αναζήτηση
Δεδομένα //ΠΙΝ//
Διάβασε ον
ι <- 1
ΔενΒρέθηκε <- Αληθής
Όσο  ΔενΒρέθηκε επανάλαβε
        ΔενΒρέθηκε <- (Πιν[ι] <> ον)
         ι <- ι+1
Τέλος_επανάληψης

Αν Βρέθηκε τότε
   Εμφάνισε 'Δεν υπάρχει το όνομα που δώσατε προς αναζήτηση'
Αλλιώς
   Εμφάνισε 'Υπάρχει το όνομα που δώσατε προς αναζήτηση'
Τέλος_Αν

[olga_ath]

Αγαπητοί συνάδελφοι δεν ξέρω πως να σας ευχαριστήσω για τις άμεσες και πλήρεις απαντήσεις  .
Αυτό ακριβώς έψαχνα. Θα δώσω ολες τις ασκήσεις στους μαθητές δίνοντας ιδιαίτερη έμφαση στις ασκήσεις ανάπτυξης .
Πιστευετε ότι βοηθάει τους μαθητές ο παρακάτω παραλληλισμός : Η προσπέλαση της θέσης Ν+1 ενός πίνακα Ν θέσεων είναι λογικό λάθος με την ίδια λογική που η χρήση αναφοράς σε μεταβλητή που δεν έχει αρχικοποιηθεί ειναι επίσης λογικό λάθος και παραβιάζει το κριτήριο της καθοριστικότητας.

Με αφορμή αυτό μπορούμε να γενικευσουμε και να πούμε ότι τα λογικά λάθη παραβιάζουν την καθοριστικότητα ?

Ευχαριστώ και πάλι

[sstergou]

Η γενίκευση αυτή δεν ισχύει.

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

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

[sstergou]

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

Σε πολλές γλώσσες η προσπέλαση τέτοιων στοιχείων δεν οδηγεί σε απαραίτητα σε κάποιο μήνυμα λάθους. Αυτό που συμβαίνει είναι ότι αντί για κάποια χρήσιμη τιμή αναφέρεσαι σε "σκουπίδια". Ο τρόπος με τον οποίο αναφερόμαστε σε στοιχεία πίνακα (ακόμη και πέρα των ορίων) είναι καθορισμένος. Εάν υπήρχε πρόβλημα καθοριστικότητας όπως στην περίπτωση της διαίρεσης τότε ο Η/Υ δεν θα είχε κανένα περιθώριο από το να αναφέρει το λάθος.

[pgrontas]

Πάντως εγώ στην πρόταση που έκανα δεν το συσχέτισα με καθοριστικότητα. Συμφωνώ με το Στάθη στο ότι δεν είναι δόκιμη η γενίκευση των λογικών λαθών προς την κατεύθυνση της καθοριστικότητας.
Αυτό που θεωρώ πολύ ενδιαφέρον πάντως είναι ότι και οι ίδιες οι γλώσσες προγραμματισμού εξελίσσονται.
Για παράδειγμα, σε αρκετές σύγχρονες γλώσσες οι αριθμητικές τιμές αρχικοποιούνται στο μηδέν είτε το θες είτε όχι, ενώ το περιβάλλον εκτέλεσης δεν επιτρέπει την προσπέλαση έξω από τα όρια του πίνακα (ακριβώς για να μην προσπελάσεις σκουπίδια, που κάποιος μπορεί να τα εκμεταλλευτεί για να σου περάσει ιό).
Κάποιες συμπεριφορές δηλαδή που εμείς λέμε ότι παραβιάζουν την καθοριστικότητα έχουν επιλυθεί ή πιο απλά ήταν αιτία για bugs  αυτόματα από το περιβάλλον εκτέλεσης. Σε κάνει να σκέφτεσαι ποια είναι τα όρια του ανθρώπινου εκτελεστή - ιδεατής μηχανής μιας ψευδογλώσσας...

[Βρακόπουλος Αθανάσιος Λ.]

Αλγόριθμος Αναζήτηση
Δεδομένα //ΠΙΝ//
Διάβασε ον
ι <- 1
Όσο (ΠΙΝ[ι] <> ον) ΚΑΙ (ι<5) επανάλαβε
   ι <- ι+1
Τέλος_επανάληψης
Αν ΠΙΝ[ι] <> ον τότε
   Εμφάνισε 'Δεν υπάρχει το όνομα που δώσατε προς αναζήτηση'
Αλλιώς
   Εμφάνισε 'Υπάρχει το όνομα που δώσατε προς αναζήτηση'
Τέλος_Αν