Αποτίμηση Συνθήκης και Πίνακες σε Αλγόριθμο

[pgrontas]

Μία απορία που δεν ξέρω αν έχει ξανασυζητηθεί είναι η εξής:
Όπως είναι γνωστό αν η πρώτη λογική συνθήκη σε ένα ΚΑΙ είναι ψευδής τότε δεν χρειάζεται να αποτιμήσουμε την δεύτερη γιατί το αποτέλεσμα είναι ψευδές.
Το βιβλίο βέβαια δεν αναφέρει κάτι τέτοιο, οπότε εκ της εις άτοπο απαγωγής  υποθέτουμε ότι χρειάζεται να αποτιμηθούν και οι δύο (σωστά;)
Αυτό έχει ως αποτέλεσμα εκφράσεις του στυλ: Ι<=Ν ΚΑΙ (συνθήκη με Α[Ι]) να έχουν λογικό λάθος για Ν+1, παρά το γεγονός ότι η συνθήκη είναι ψευδής και δεν χρειάζεται να αποτιμηθεί η (συνθήκη με Α[Ι]).

Τι θα κάνατε αν βλέπατε ένα τέτοιο λάθος;

ΥΓ: Την απορία αυτή τη δημιούργησε ο σύμφωνος με το βιβλίο τρόπος υλοποίησης των παραπάνω από τον Στάθη.

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

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

Στο παρακάτω παράδειγμα θα έχουμε διαίρεση με το 0 ή όχι;

κ<-5
α<-0
Αν κ>=10 και κ/α >1 τότε ....


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

α<-4
Αν α>=10 και υπολογισμός_βαθμού(α)>12 τότε  ....


Ο τρόπος αποτίμησης των λογικών εκφράσεων, όπου δεν γίνεται αποτίμηση της 2ης πρότασης αν το αποτέλεσμα έχει ήδη κριθεί από την 1η πρόταση, αποτελεί συγκεκριμένο χαρακτηριστικό πολλών γλωσσών προγραμματισμού και αποκαλείται short-circuit evaluation.

Σε κάποιες γλώσσες αυτό το χαρακτηριστικό δεν υποστηρίζεται και οι λογικοί τελεστές αποτιμούν κανονικά όλες τις προτάσεις μιας λογικής έκφρασης, π.χ. fortran, vb.

Σε κάποιες άλλες το short-circuit evaluation είναι ο μόνος τρόπος αποτίμησης των λογικών εκφράσεων, π.χ. C, C++.

Στις πιο σύγχρονες γλώσσες (π.χ. σε Java, Perl, PHP, Python, Ruby, VB.NET) υποστηρίζονται και οι δύο τρόποι υπολογισμού χρησιμοποιώντας διαφορετικούς τελεστές, για παράδειγμα με τους τελεστές and και andalso, or και orelse.

Βλ. http://en.wikipedia.org/wiki/Short-circuit_evaluation

Αφού λοιπόν στο βιβλίο δεν αναφέρεται τίποτα σχετικό, εμείς θα πρέπει να θεωρήσουμε ότι ΔΕΝ γίνεται short-circuit evaluation, δηλαδή όλες οι προτάσεις αποτιμούνται κανονικά!

[pgrontas]

Νίκο όλα αυτά που ανέφερες είναι σωστά και γνωστά. Αυτό που ήθελα να συζητήσουμε είναι αν το συναντήσουμε αυτό σε αλγόριθμο, πχ. στην σειριακή αναζήτηση κάποιος βάλει το Α[ι]<>στοιχείο στο όσο, τι πρέπει να κάνουμε,
-επειδή το βιβλίο δεν ορίζει το short-circuit evaluation να το πάρουμε ως λάθος;
-είναι πολύ λεπτό σημείο και να το παραβλέψουμε;
-επειδή τον αλγόριθμο όπου δεν είναι τόσο αυστηρά τα πράγματα τον εκτελεί ο άνθρωπος μπορεί να πάρει απόφαση και να παρακάμψει την δεύτερη συνθήκη;

[sstergou]

Μου φαίνεται ότι αν ένας μαθητής/τρια συντάξει κάποιον τέτοιο αλγόριθμο το πιο πιθανό είναι απλά να του έχει ξεφύγει το ότι στην τελευταία επανάληψης βγαίνει έξω από τα όρια.
Η γνώμη μου είναι λοιπόν ότι κάτι πρέπει να κοπεί.

[alkisg]

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

Κώδικας: Αλγόριθμος

Αλγόριθμος ΕύρεσηΣτοιχείου
...
ι <- 1
Όσο ι <= 10 και Α[ι] <> στοιχείο επανάλαβε
  ...
  ι <- ι +1
τέλος_επανάληψης
...

Αυτό 9 στους 10 προγραμματιστές θα το πουν σωστό (και στις πιο πολλές γλώσσες είναι, και το γράφουν με τον συγκεκριμένο τρόπο και όχι με ξεχωριστό flag).

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

[gpapargi]

Είναι το θέμα της μερικής ή πλήρους αποτίμησης των συνθηκών. To είχαμε συζητήσει με αρκετά ενδιαφέρουσες τοποθετήσεις. Είχαν ακουστεί απόψεις και υπέρ και κατά της μερικής αποτίμησης.
https://alkisg.mysch.gr/steki/index.php?topic=752.0

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

Πάντως κάτι τέτοιο είναι τραβηγμένο για να κόψεις μονάδες, αλλά και πάλι εξαρτάται από την περίπτωση...

[P.Tsiotakis]

Αυτό έχει ως αποτέλεσμα εκφράσεις του στυλ: Ι<=Ν ΚΑΙ (συνθήκη με Α[Ι]) να έχουν λογικό λάθος για Ν+1, παρά το γεγονός ότι η συνθήκη είναι ψευδής και δεν χρειάζεται να αποτιμηθεί η (συνθήκη με Α[Ι]).

Τι θα κάνατε αν βλέπατε ένα τέτοιο λάθος;

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

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

Δεν νομίζω ότι ένας μαθητής θα έκανε κάτι τέτοιο για εντυπωσιασμό! Απλά μάλλον θα του ξέφυγε αφού δεν θα είχε σκεφτεί κάθε περίπτωση. Ούτε πιστεύω ότι ένας μαθητής θα έχει υπόψη του το short-circuit evaluation, ή τη μερική αποτίμηση συνθηκών, ή όπως τέλος πάντων το λένε!

[evry]

  Προσωπικά αν δω κάτι τέτοιο συμπεραίνω ότι ο μαθητής σίγουρα ξέρει 5 πράγματα παραπάνω από τον μέσο μαθητή και δε θα μπορούσα να του κόψω επειδή η συγκεκριμένη ΓΛΩΣΣΑ δεν επιτρέπει τον τρόπο αυτό υπολογισμού. Είναι πολύ λεπτό το ζήτημα για να μπορέσει να το βρει ένας μαθητής. Για να είμαι ειλικρινής όχι μόνο δεν θα έκοβα αλλά θα έβαζα και κάτι παραπάνω.
   Τώρα σε ποια περίπτωση θα έκοβα? Αν ο μαθητής μου έγραφε τον αλγόριθμο αναζήτησης όπως ακριβώς τον έχει το βιβλίο, δηλαδή χρησιμοποιούσε και done και pos (με τα ίδια μάλιστα ονόματα) και μαζί με αυτό το καταραμένο
Αλλιώς
   i <- i + 1
θα συμπέρανα ότι ο μαθητής απλά αντιγράφει τον αλγόριθμο του βιβλίου και δεν έχει καταλάβει πως δουλεύει (πιθανότατα)
ε εκεί θα του έκοβα. Αλλά προς θεού, όχι από αυτό, από αλλού, όλο και κάτι θα έβρισκα 

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

... Όποιος ψάχνει βρίσκει! 

[nikolasmer]

Συνάδελφοι, αν σε άσκηση ζητούνταν σειριακή σε πίνακα Ν στοιχείων και ο μαθητής έγραφε το παρακάτω:

ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ 100
ΔΙΑΒΑΣΕ Π[Ι]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Π[101]<-...!ΟΥΔΕΤΕΡΟ ΣΤΟΙΧΕΙΟ

ΔΙΑΒΑΣΕ ΚΕΥ
Ι <- 1
ΟΣΟ Ι<=100 ΚΑΙ Π[Ι]<>ΚΕΥ ΕΠΑΝΑΛΑΒΕ
Ι<-Ι+1
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

θα του το πιάναμε λάθος επειδή η άσκηση έλεγε για πίνακα 100 θέσεων; Δηλώνεις μια θέση παραπάνω και γλιτώνεις flag. Εγώ στα ίδια το βλέπω.

[P.Tsiotakis]

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

[itt]

Μου φαίνεται ότι αν ένας μαθητής/τρια συντάξει κάποιον τέτοιο αλγόριθμο το πιο πιθανό είναι απλά να του έχει ξεφύγει το ότι στην τελευταία επανάληψης βγαίνει έξω από τα όρια.
Η γνώμη μου είναι λοιπόν ότι κάτι πρέπει να κοπεί.

Συμφωνώ,αφού δεν είναι γραμμένο explicitly πως υφίσταται sce κατα το evaluation της πρώτης έκφρασης τόσο του τελεστή KAI αλλά και του Ἠ,είναι λογικό να κοπεί κάτι.Σαφέστατα και αυτό δεν προάγει ορθή προγραμματιστική τεχνική,αφού όπως ήδη γράφτηκε,στην C και στν η C++ υπάρχει sequence point μετά το evaluation της πρώτης έκφρασης στους ανάλογους τελεστές .Αν και το τι συνιστά ορθή προγραμματιστική τεχνική σε αυτό το μάθημα είναι τελείως αστὀχαστο.

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

Είναι λάθος κατεύθυνση αλλά άμα είσαι σε λάθος δρόμο ήδη,έχει σημασία που θα φτάσεις;Το overhead μιας επιπλέον θέσης σε έναν πίνακα μπορεί να είναι αμελητέο,όμως αν  χρησιμοποιηθεί σε 1000 πίνακες αποκτά άλλη διάσταση.Εφόσον όμως δεν υπάρχει ένα υφιστάμενο μοντέλο μνήμης δεν έχει νόημα η συζήτηση.

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

[P.Tsiotakis]

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

απροσδιόριστο περιεχόμενο, δεν καθορίζεται από το σχολικό βιβλίο

[petrosp13]

Πολύ απλά, δεν έχει τίποτα!

[itt]

Πολύ απλά, δεν έχει τίποτα!

Βασικά είναι πιο απλό το 

απροσδιόριστο περιεχόμενο

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

[petrosp13]

Νομίζω ότι το "δεν έχει τίποτα" δεν δημιουργεί περισσότερα ερωτήματα, ενώ το "απροσδιόριστο περιεχόμενο" δημιουργεί

[itt]

Όντως,ίσως έναν μαθητή να τον ξένιζε το "απροσδιόριστο".