Θέμα: Όρια πίνακα

[P.Tsiotakis]

Ας υποθέσουμε ότι σε έναν αλγόριθμο χρησιμοποιείται ένας πίνακας ακεραίων Χ[10].

Οι παρακάτω εντολές παραβιάζουν το κριτήριο της καθοριστικότητας, σωστά;

κ <-  0
Εμφάνισε Χ[κ]
...
κ <-  11
Εμφάνισε Χ[κ]


Τσιωτάκης Παναγιώτης

[evry]

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

Κώδικας: [Επιλογή]

i <-- 1
Όσο (i <= N) ΚΑΙ (Α[i] > 0) Επανάλαβε
    i <-- i + 1
Τέλος_Επανάληψης

Το παραπάνω τμήμα κώδικα ουσιαστικά ελέγχει αν όλα τα στοιχεία ένος πίνακας Ν αριθμών είναι θετικοί. Θα σταματήσει όταν βρει αρνητικό ή μηδενικό στοιχείο. Το χρησιμοποιώ συχνά στη C γιατί βαριέμαι να ορίζω λογικές μεταβλήτες. Στη Γλώσσα δεν είναι όμως το ίδιο. Είναι ένα καλό παράδειγμα για την αναγκαιότητα της μεταβλητής - φρουρού ή σημαίας.

[P.Tsiotakis]

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

Παναγιώτης

[gpapargi]

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

ι< - 0                           
Αρχή_επανάληψης
   ι<- ι+1                 ! Πριν κάνεις οτιδήποτε μπες εντός ορίων του πίνακα
   εντολές
Μέχρις_ότου ι=ν

Δηλαδή αρχή επανάληψης και αύξηση μετρητή στην αρχή του βρόχου. Θα επεξεργαστείς και το τελευταίο στοιχείο α[ν] και μετά θα τερματίσει ο βρόχος. Ο τρόπος αυτός δεν είναι ισοδύναμος με τη σάρωση με Για/Όσο που έχει μετρητή στο τέλος. Αυτό θέλει προσοχή. Αλλά ότι και να γίνει δεν βγαίνεις από τα όρια αρκεί η αύξηση του μετρητή να είναι το πρώτο πράγμα που κάνεις μέσα στο βρόχο.

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

[EleniK]

Σχετικά με το να βγουν εκτός ορίων, μπήκε θέμα το 2005 στα ημερήσια. Συγκεκριμένα το 3ο θέμα (με τον ελεγχο για τρεχων μέσο) ο ένας πίνακας ήταν μέχρι Ν και ο άλλος μέχρι Ν-1. Αρκετά παιδιά τότε είχαν βάλει στη δομη  επαναληψης μέχρι Ν, οποτε και ειχαν βγει εκτος οριων πίνακα. Βέβαια παρομοιο θέμα με αυτο που προτείνει ο Ευριπίδης θα ήταν ωραίο για υποερωτημα στο 1ο θέμα. Οπως εκεινο με το βήμα 0 που ρωτούσε ποιο κριτήριο παραβιάζει. Και επειδή αρκετοι διεστραμμένοι κυκλοφορούν, ποτέ δεν ξέρεις :-))

[Katerina m]

Σχετικά με το παράδειγμα που δίνει ο Ευρυπίδης όπως επισημαίνει και ο ίδιος στη Γλωσσα δεν ισχυεί κάτι τέτοιο αλλά στη C είναι σωστό.
Αν δηλαδή το γράψει κάποιος σε μια άσκηση που ζητάει αλγόριθμο και όχι πρόγραμμα είναι σωστό ή όχι?

[alkisg]

Παιδιά, το παράδειγμα του Ευριπίδη είναι σίγουρο ότι είναι λάθος στη ΓΛΩΣΣΑ;
Ουσιαστικά είναι η επιλογή "Να γίνεται πλήρης αποτίμηση των λογικών εκφράσεων" του Διερμηνευτή:
https://alkisg.mysch.gr/help/Bon8eia.htm#epilogesGlwssa

Δηλαδή αν η ΓΛΩΣΣΑ κάνει μερική αποτίμηση λογικών εκφράσεων (partial boolean evaluation), τότε είναι σωστό (όπως και στις περισσότερες γλώσσες). Αν όχι, τότε προσπελαύνεται το Α[Ν+1] και φυσικά είναι λάθος.

Έχετε δει να αναφέρεται κάτι σχετικό στο βιβλίο; Ή "εννοείται" ότι γίνεται πλήρης αποτίμηση των λογικών εκφράσεων;

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

Νομίζω ότι στο συγκεκριμένο, ό,τι ισχύει για τη ΓΛΩΣΣΑ θα πρέπει να ισχύει και για τους αλγορίθμους.

[Sergio]

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

Προσωπικά ακολουθώ την προσέγγιση που δίνεται στα παραδείγματα που δώθηκαν σε αυτό το post.  Ίσως είναι σκόπιμο η πλήρης αποτίμηση να είναι η default επιλογή για το διερμηνευτή.

Πάντως συμφωνώ ότι ΓΛΩΣΣΑ και ΨΕΥΔΟΓΛΩΣΣΑ δε έχουν λόγο να διαφέρουν σε αυτό το σημείο.

[evry]

    Πιστεύω οτι η γενική ιδέα είναι ο αλγόριθμος που γράφουμε να είναι σωστός ανεξαρτήτου υλοποίησης της Γλώσσας όποτε αυτό είναι δυνατό. Και πιστεύω ότι στη συγκεκριμένη περίπτωση θα έπρεπε να υποθέσουμε ότι έχουμε πλήρη αποτίμηση των λογικών εκφράσεων όχι μόνο επειδή δεν αναφέρεται κάτι διαφορετικό στο βιβλίο αλλά και επειδή είναι αυτό που ταιριάζει περισσότερο στο πνεύμα του μαθήματος.
    Γενικά η μερική αποτίμηση των λογικών εκφράσεων,βοηθάει πολλές φορές στην απόδοση του αλγορίθμου, όμως μπορεί να δημιουργήσει πολλά προβλήματα αν χρησιμοποιούμε μέσα στη λογική έκφραση τίποτα κόλπα χ++ ή χ=getchar() ή γενικότερα εκφράσεις που έχουν παρενέργειες σε άλλες μεταβλητές. Για αυτό και στη Java που κάποιοι θεωρούν μια πιο safe C++ έχει και τις δύο περιπτώσεις με διαφορετικούς συμβολισμούς, νομίζω && και & αν θυμάμαι καλά

[gpapargi]

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

ι<- 1
Όσο α[ι] <> key και ι<=ν επανάλαβε
   ι<-ι+1
Τέλος_επανάληψης

Υποθέτω πως θα δώσει λάθος αφού η αποτίμηση θα γίνει από αριστερά προς τα δεξιά και θα έχουμε απόπειρά προσπέλασης του α[ν+1].

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

Πέρα από αυτό, από ότι καταλαβαίνω η λογική της μερικής αποτίμησης είναι η εξής:
Αφού ξέρουμε ότι η παράσταση (Ψευδής ΚΑΙ οτιδήποτε) μας κάνει Ψευδής τότε ποιος ο λόγος να ασχολούμαστε με το τι είναι αυτό το «οτιδήποτε»; Μπορεί το «οτιδήποτε» να είναι καμιά μεγάλη παρένθεση και ποιος ο λόγος να την υπολογίζουμε τζάμπα;
Ανάλογο είναι και το σκεπτικό σύμφωνα με το οποίο εμείς οι άνθρωποι βλέποντας κάτι της μορφής (0 * οτιδήποτε) λέμε απευθείας ότι το αποτέλεσμα είναι 0 (το 0 είναι το απορροφητικό στοιχείο του πολλαπλασιασμού).

Αλλά το πράγμα είναι πιο σύνθετο και εδώ θέλω να σταθούμε. Αν το «οτιδήποτε» οποιοσδήποτε αριθμός τότε είμαστε σωστοί. Αλλά αν το οτιδήποτε είναι πχ η αλφαριθμητική τιμή «ΑΒΓ» τότε το 0 * «ΑΒΓ» δεν έχει νόημα γιατί δεν ορίζεται ο πολλαπλασιασμός αριθμού με χαρακτήρες.

Επιστρέφοντας στο (Ψευδής ΚΑΙ οτιδήποτε) θα έλεγα ότι μπορούμε να πούμε ότι κάνει Ψευδής αν είμαστε σίγουροι ότι το «οτιδήποτε» είναι κάποια λογική τιμή. Εδώ το α[ν+1] είναι κάτι που δεν υπάρχει. Άρα η συνθήκη key<>α[ν+1] δεν ορίζεται.  ʼρα το (Ψευδής και οτιδήποτε) δεν ορίζεται επίσης αφού ο τελεστής «και» πρέπει να δρα πάνω σε 2 καλώς ορισμένες λογικές τιμές (που ανήκουν στο σύνολο των επιτρεπτών τιμών μιας λογικής μεταβλητής).

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

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

ΥΓ
Ένα ενδιαφέρον ερώτημα είναι τι γίνεται στην περίπτωση που έχουμε πίνακα λογικών τιμών που δεν έχει αρχικοποιηθεί. Εκεί αν πεις (Ψευδής και α[1]) με το α[1] δηλωμένο λογικό το πράγμα αλλάζει. Το α[1] υπάρχει και έχει απροσδιόριστο περιεχόμενο που όμως είναι υποχρεωμένο να είναι λογικό αφού έτσι δηλώθηκε. Θα αποφύγω εντέχνως να απαντήσω για την ώρα λέγοντας ότι αν δικάζουμε τη μερική αποτίμηση θα πρέπει να την ελέγχουμε σε όσο γίνεται πιο ακραίες συνθήκες όπως αυτές που ανέφερα παραπάνω :-)

[alkisg]

Αν κάνουμε μερική αποτίμηση  αλλάζοντας τη σειρά στη σύνθετη συνθήκη τότε θα προκύψει λάθος ή όχι;

Yeap, θα προκύψει λάθος.

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

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

Κώδικας: ΓΛΩΣΣΑ

1. έγινεΚάτιΜεΤοΧ <- ΨΕΥΔΗΣ
2. ΑΝ Συνάρτηση1(χ) ΤΟΤΕ
3.   ΑΝ Συνάρτηση2(χ) ΤΟΤΕ
4.     ΑΝ Συνάρτηση3(χ) ΤΟΤΕ
5.       ΑΝ Συνάρτηση4(χ) ΤΟΤΕ
6.         ΑΝ Συνάρτηση5(χ) ΤΟΤΕ        
7.           ΔιαδικασίαΠουΚάνειΚάτιΜεΤοΧ(χ)
8.           έγινεΚάτιΜεΤοΧ <- ΑΛΗΘΗΣ
9.         ΤΕΛΟΣ_ΑΝ
10.       ΤΕΛΟΣ_ΑΝ
11.     ΤΕΛΟΣ_ΑΝ
12.   ΤΕΛΟΣ_ΑΝ
13. ΤΕΛΟΣ_ΑΝ
14. ΑΝ όχι ΈγινεΚάτιΜεΤοΧ ΤΟΤΕ
15.   ΓΡΑΨΕ 'Δεν μπορεί να γίνει κάτι με το χ'
16. ΤΕΛΟΣ_ΑΝ

Ο αντίστοιχός του με μερική αποτίμηση είναι:

Κώδικας: ΓΛΩΣΣΑ

1. ΑΝ Συνάρτηση1(χ) ΚΑΙ Συνάρτηση2(χ) ΚΑΙ Συνάρτηση3(χ) ΚΑΙ Συνάρτηση4(χ) ΚΑΙ Συνάρτηση5(χ) ΤΟΤΕ        
2.   ΔιαδικασίαΠουΚάνειΚάτιΜεΤοΧ(χ)
3. ΑΛΛΙΩΣ
4.   ΓΡΑΨΕ 'Δεν μπορεί να γίνει κάτι με το χ'
5. ΤΕΛΟΣ_ΑΝ

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

Αλλά αν το οτιδήποτε είναι πχ η αλφαριθμητική τιμή «ΑΒΓ» τότε το 0 * «ΑΒΓ» δεν έχει νόημα γιατί δεν ορίζεται ο πολλαπλασιασμός αριθμού με χαρακτήρες.

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

Εδώ το α[ν+1] είναι κάτι που δεν υπάρχει. Άρα η συνθήκη key<>α[ν+1] δεν ορίζεται.

Όλα αυτά είναι μέρος του ορισμού της μερικής αποτίμησης. Οι λογικοί τελεστές αλλάζουν έννοια και κατά περίπτωση μπορεί να πάρουν την σημασιολογία μιας δεύτερης ΑΝ: ΑΝ (ι <= Ν) ΤΟΤΕ ΑΝ (Α[ι] > 0) ...
Εφόσον ο προγραμματιστής κατανοεί ότι το ΚΑΙ που γράφει ισοδυναμεί με "ΤΟΤΕ ΑΝ" δεν υπάρχει πρόβλημα καθοριστικότητας.

Εκεί αν πεις (Ψευδής και α[1]) με το α[1] δηλωμένο λογικό το πράγμα αλλάζει.

Γιώργο σ' αυτό δε βλέπω καμία απολύτως διαφορά με τους ακεραίους. Αν θεωρείς ότι το α[1] είναι ή ΑΛΗΘΗΣ ή ΨΕΥΔΗΣ, τότε και το α[1] με α=ακέραιος θα πρέπει να είναι ..., -2, -1, 0, 1, 2, ... δηλαδή στο πεδίο ορισμού του. Δεν έχει σημασία που το πεδίο ορισμού των λογικών μεταβλητών είναι πιο μικρό από αυτό των ακεραίων. Αντίστοιχα, αν θεωρείς ότι ένας μη αρχικοποιημένος ακέραιος ...δεν είναι ακέραιος, το ίδιο θα πρέπει να ισχύει και για τις λογικές μεταβλητές.

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

[gpapargi]

Άλκη νομίζω πως δεν διαφωνούμε επί της ουσίας. Νομίζω πως η μόνη διαφορά είναι ότι ο καθένας εξετάζει το θέμα από διαφορετική οπτική γωνία. Εγώ το βλέπω  μαθηματικά το θέμα ενώ εσύ το βλέπεις από τη μεριά της υλοποίησης. Γι αυτό σε ενδιαφέρει και το ότι το 0 * «ΑΒΓ» είναι λάθος υπό  διαφορετική έννοια (syntax error) από ότι την προσπέλαση του α[ν+1] (runtime error), ενώ εγώ απλά είπα ότι δεν είναι καλώς ορισμένες παραστάσεις.

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

Αυτή είναι η ένστασή μου στο θέμα της μερικής αποτίμησης.

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

[manpap]

Να ξαναγυρίσουμε στο αρχικό ερώτημα
Συμφωνώ για τα παραδείγματα που δόθηκαν και τα οποία πραβιάζουν την καθοριστικότητα.
Θα ήθελα όμως να ρωτήσω επιπλέον:
Στην εντολή Α[0]<- 15, ποιο κριτήριο παραβιάζεται, τελικά; Μήπως η αποτελεσματικότητα; Το λάθος είναι συντακτικό και θα το εντοπίσει ο μετταγλωττιστής, άρα είναι μη εκτελέσιμη εντολή άρα παραβιάζει αποτελεσματικότητα;
Περιμένω τη γνώμη σας

[evry]

 Το λάθος δεν είναι συντακτικό, η σύνταξη είναι μια χαρά, και φυσικά ούτε σημασιολογικό αφού και έλεγχο τύπων να κάνεις πάλι μια χαρά είναι. Είναι καθαρά λογικό λάθος. Τώρα αν κάποιοι μεταγλωττιστές έχουν προνοήσει και επειδή γνωρίζουν τα ορια σε στατικούς πίνακες κάνουν τον έλεγχο σε compile-time αυτό δε σημαίνει ότι το λάθος δεν είναι λογικό.
    Σκέψου για παράδειγμα να μπορούσες να ορίσεις δυναμικό πίνακα. Θα μπορούσε ο μεταγλωττιστής να βρει το λάθος σε χρόνο μεταγλώττισης;

[xazlag]

Οι παρακάτω εντολές παραβιάζουν το κριτήριο της καθοριστικότητας, σωστά;

κ <-  0
Εμφάνισε Χ[κ]
...
κ <-  11
Εμφάνισε Χ[κ]

γιατι δεν παραβιάζεται η αποτελεσματικότητα;