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

Ξεκίνησε από pgrontas, 07 Δεκ 2009, 09:48:39 ΜΜ

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

pgrontas

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

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

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


Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

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

Θα πρέπει να είναι σαφές από την ίδια τη γλώσσα προγραμματισμού με ποιον τρόπο γίνεται η αποτίμηση μιας λογικής έκφρασης σε τέτοιες περιπτώσεις... γιατί τα πράγματα μπορεί να γίνουν κρίσιμα! Ειδικά, όταν υπάρχει περίπτωση στη 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

#2
Νίκο όλα αυτά που ανέφερες είναι σωστά και γνωστά. Αυτό που ήθελα να συζητήσουμε είναι αν το συναντήσουμε αυτό σε αλγόριθμο, πχ. στην σειριακή αναζήτηση κάποιος βάλει το Α[ι]<>στοιχείο στο όσο, τι πρέπει να κάνουμε,
-επειδή το βιβλίο δεν ορίζει το short-circuit evaluation να το πάρουμε ως λάθος;
-είναι πολύ λεπτό σημείο και να το παραβλέψουμε;
-επειδή τον αλγόριθμο όπου δεν είναι τόσο αυστηρά τα πράγματα τον εκτελεί ο άνθρωπος μπορεί να πάρει απόφαση και να παρακάμψει την δεύτερη συνθήκη;
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

sstergou

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

alkisg

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


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

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

gpapargi

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

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

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

P.Tsiotakis

Παράθεση από: pgrontas στις 07 Δεκ 2009, 09:48:39 ΜΜ

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

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

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

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

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

evry

  Προσωπικά αν δω κάτι τέτοιο συμπεραίνω ότι ο μαθητής σίγουρα ξέρει 5 πράγματα παραπάνω από τον μέσο μαθητή και δε θα μπορούσα να του κόψω επειδή η συγκεκριμένη ΓΛΩΣΣΑ δεν επιτρέπει τον τρόπο αυτό υπολογισμού. Είναι πολύ λεπτό το ζήτημα για να μπορέσει να το βρει ένας μαθητής. Για να είμαι ειλικρινής όχι μόνο δεν θα έκοβα αλλά θα έβαζα και κάτι παραπάνω.
   Τώρα σε ποια περίπτωση θα έκοβα? Αν ο μαθητής μου έγραφε τον αλγόριθμο αναζήτησης όπως ακριβώς τον έχει το βιβλίο, δηλαδή χρησιμοποιούσε και done και pos (με τα ίδια μάλιστα ονόματα) και μαζί με αυτό το καταραμένο
Αλλιώς
   i <- i + 1
θα συμπέρανα ότι ο μαθητής απλά αντιγράφει τον αλγόριθμο του βιβλίου και δεν έχει καταλάβει πως δουλεύει (πιθανότατα)
ε εκεί θα του έκοβα. Αλλά προς θεού, όχι από αυτό, από αλλού, όλο και κάτι θα έβρισκα  >:D
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

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


nikolasmer

Συνάδελφοι, αν σε άσκηση ζητούνταν σειριακή σε πίνακα Ν στοιχείων και ο μαθητής έγραφε το παρακάτω:
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ 100
ΔΙΑΒΑΣΕ Π[Ι]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Π[101]<-...!ΟΥΔΕΤΕΡΟ ΣΤΟΙΧΕΙΟ

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


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

P.Tsiotakis

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

itt

Παράθεση από: sstergou στις 08 Δεκ 2009, 12:46:12 ΜΜ
Μου φαίνεται ότι αν ένας μαθητής/τρια συντάξει κάποιον τέτοιο αλγόριθμο το πιο πιθανό είναι απλά να του έχει ξεφύγει το ότι στην τελευταία επανάληψης βγαίνει έξω από τα όρια.
Η γνώμη μου είναι λοιπόν ότι κάτι πρέπει να κοπεί.

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

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

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

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

P.Tsiotakis

Παράθεση από: itt στις 06 Μαΐου 2013, 01:15:18 ΠΜ
Έχω και μια ερώτηση.Αν δεν  αρχικοποιηθεί αυτή η θέση του πίνακα,τι περιέχει;Το ουδέτερο στοιχείο της άλγεβρας του τύπου του πίνακα;Καθορίζεται απο το βιβλίο αυτό;

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