Προτεραιότητα ελέγχου παράστασης σε επανάληψη

Ξεκίνησε από nekis, 14 Νοε 2005, 10:43:12 ΠΜ

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

nekis

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


  Γράψε 'δωστε τον αριθμο προς αναζητηση'
  Διάβασε αριθμ
  σημαια <-- Ψευδής
  θεση  <--0
  ι  <-- 1
  Όσο (σημαια = Ψευδής) και (ι <=10)  και α[ι] < αριθμ επανάλαβε
    Αν α[ι] = αριθμ τότε
      σημαια <-- Αληθής
      θεση <-- ι
    τέλος_αν
    ι <-- ι + 1
  τέλος_επανάληψης
  Γράψε σημαια, θεση

Ας υποθέσουμε ότι έχουμε σαν είσοδο το πίνακα  15 23 45 64 75 90 και στην είσοδο δίνουμε την τιμή 100 δηλ δίνουμε είσοδο δεξιά του πίνακα. Σε αυτή την περίπτωση θα έχουμε στην τελευταία επανάληψη το ι να παίρνει την τιμή 11.
Η απορία μου έχει ως εξής:
Η συνθήκη του όσο θα βγει ψευδής, λόγω του ότι ι=11, ή ο μεταγλωττιστής θα ελέγξει ότι το α[ι] για ι=11 είναι εκτός ορίου του πίνακα και θα δώσει μήνυμα λάθους;
Η άποψή μου είναι ότι εφόσον έχω τελεστές ΚΑΙ και έχουμε ορίσει ότι οι πράξεις εκτελούνται από αριστερά προς τα δεξιά θα βγει false πριν ελέγξει το α[ι] < αριθμ, αλλά και πάλι δεν είμαι  απολύτως βέβαιος για τα γραφόμενα.
Παρακαλώ για τις αποψεις σας

Ν.Κυριακου

oldman

Στο συγεκριμένο παράδειγμα η σύνθετη συνθήκη της ΟΣΟ θα είναι από την αρχή ψευδής, αφού η συνθήκη α<αριθμ θα είναι ψευδής για i=1 (100<15), οπότε η επανάληψη θα τελειώσει!!!

Vang

Ελέγχεται όλη η συνθήκη για να βγεί αν είναι αληθής ή ψευδής.  Ο υπολογιστής δεν είναι άνθρωπος για να "σκεφτεί" ότι επειδή υπάρχει ο λογικός σύνδεσμος "και" η συνθήκη θα είναι ψευδής όταν ο ένας παράγοντας είναι ψευδής.   Θα γίνει λοιπόν κανονικά όλος ο έλεγχος της συνθήκης και φυσικά θα εμφανιστεί μήνυμα λάθους .
Συμπληρωματικά έχω απορία πως έφτασες σε αυτό το σημείο της ύλης μήπως δεν έκανες παράλληλα με το κεφάλαιο 2 τα κεφάλαια 7και 8;

Φιλικά

oldman

Μη λάβετε υπόψη το προηγούμενο μήνυμα. Εκ παραδρομής εξέτασα ανάποδα την ανισότητα!!! Προφανώς δεν ισχύουν αυτά που γράφτηκαν.
Ευχαριστώ

amanou

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

Πόσο μάλλον εδω που η προσέγγιση είναι πιο αλγοριθμική και χωρίς την άμεση εξάρτηση του προγραμματιστικού περιβάλλοντος. Πιστεύω ότι η συνθήκη θα γίνει ψευδής λόγω της  σύγκρισης ι < = 10 οπότε εφόσων υπάρχουν μεταξύ τους οι λογικοί τελεστές και θα γίνει όλη η παράσταση ψευδής και θα σταματήσει.
Πιστεύω ότι μια τέτοια λύση είναι σωστή και δεν έχει πρόβλημα. Αλλά δες και άλλη μια λύση που τροποποιεί κάπως και ξεφεύγει από αυτό που σου δημιουργεί το πρόβλημα :

Γράψε 'δωστε τον αριθμο προς αναζητηση'
  Διάβασε αριθμ
  σημαια <-- Ψευδής
  θεση  <--0
  ι  <-- 1
  Όσο (σημαια = Ψευδής) και (ι <=10) επανάλαβε
      Αν α[ι] = αριθμ τότε
        σημαια <-- Αληθής
        θεση <-- ι
      αλλιώς_αν  α[ι] < αριθμ τότε
         σημαια <-- Αληθής
      τέλος_αν
       ι <-- ι + 1
  τέλος_επανάληψης
  Αν θέση <>0 τότε
    εμφάνισε " βρίσκετε στην θέση " , θέση
 αλλιώς
    εμφάνισε " δεν βρέθηκε"
 τέλος_αν
 
 
Οπότε όταν συμβεί αυτό που θέλουμε να αποφύγουμε τότε η σημαία γίνεται αληθής αλλά η θέση θα έχει την αρχική της θέση δηλαδή το 0 οπότε έτσι το διαχωρίζεις από την περίπτωση που έχεις βρει την τιμή που ψάχνεις μέσα στον πίνακα.

Φιλικά,

Αντώνης Μανουσάκης
Ηλεκτρονικός Μηχανικός &
Μηχανικός Η/Υ
Αντώνης Μανουσάκης

Ηλεκτρονικός και Μηχανικός Η/Υ

P.Tsiotakis

Εγώ θα γενικεύσω το αρχικό ερώτημα και θα ισχυριστώ οτι ο παρακάτω αλγόριθμος είναι σωστός :o  :

Αλγόριθμος Παράδειγμα
  Διάβασε β
  α <- 5
  Αν (α >= 2) ή (β >= γ) τότε
    δ <- α * β
  Αλλιώς
    δ <- α / 0 ! ναι καλά είδατε, διαίρεση με το μηδέν
  Τέλος_αν
  Αποτελέσματα // δ //
Τέλος Παράδειγμα

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

2. Αφού η συνθήκη είναι σίγουρα αληθής, δεν θα μεταβούμε ποτέ στο Αλλιώς και έτσι δεν μας ενδιαφέρει που γίνεται διαίρεση με το μηδέν

Σωστά;

alkisg

Σε πολλές μοντέρνες γλώσσες προγραμματισμού υπάρχουν διάφοροι έλεγχοι. Έλεγχοι που καταλήγουν σε runtime errors με τερματισμό του προγράμματος.

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

Επίσης σε πολλές γλώσσες υπάρχει επιλογή για πλήρης αποτίμηση λογικών συνθηκών ή όχι. Αν είναι ενεργή, τότε ελέγχεται και το δεύτερο μέρος του
ΑΝ Ψευδής ΚΑΙ "...κάτι άλλο..." ΤΟΤΕ
Αν η πλήρης αποτίμηση λογικών συνθηκών είναι ανενεργή, τότε δεν ελέγχεται.

Αυτό γίνεται με οδηγίες προς τον compiler μέσα από τον source κώδικα ή με επιλογές στα μενού.

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

Anyway, my point is, ότι δεν είναι αυτονόητα αυτά τα ζητήματα. Αν κάποιος έχει εντοπίσει κάτι από το βιβλίο καλό θα ήταν να το παραθέσει...

nekis

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

P.Tsiotakis

Άλκη, η FORTRAN αρχικοποιεί (μηδενίζει) τις μεταβλητές, άρα δεν τίθεται θέμα αν το παράδειγμα εκτελεστεί σε FORTRAN.

Το παράδειγμα που έγραψα σε ψευδογλώσσα - ΑΕΠΠ Γ λυκείου (όχι σε κάποια γλώσσα προγραμματισμού) είναι σωστό ή όχι;

ΥΓ: Ανάλυση για το θέμα υπάρχει και στην ιστοσελίδα http://users.kor.sch.gr/ptsiotakis/aepp/aepp_anal_2_2.htm
με παρόμοιο παράδειγμα

alkisg

#9
Παναγιώτη δεν παίζει ρόλο το συγκεκριμένο παράδειγμα της Fortran, ΟΚ, ας πούμε ότι αρχικοποιεί τις μεταβλητές σε μηδέν, ενώ κάνει ΠΛΗΡΗ αποτίμηση λογικών συνθηκών, οπότε το παράδειγμά σου είναι σωστό στην Fortran.

Η Pascal σε {$O-} state αν θυμάμαι καλά επίσης κάνει ΠΛΗΡΗ αποτίμηση και φυσικά δεν αρχικοποιεί τις μεταβλητές σε 0, οπότε σε Pascal το παράδειγμά σου (μπορεί να) είναι λάθος. Παραδείγματα από γλώσσες προγραμματισμού μπορούμε να βρούμε όσα θέλουμε, δεν είναι εκεί το ζήτημα.

"Το παράδειγμα που έγραψα σε ψευδογλώσσα - ΑΕΠΠ Γ λυκείου (όχι σε κάποια γλώσσα προγραμματισμού) είναι σωστό ή όχι; "

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

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

Sergio

#10
Θα πρότεινα να μην παρασυρθούμε σε συζήτηση σχετικά με εναλλακτικές υλοποιήσεις σε διάφορες γνωστές γλώσσες προγραμματισμού.  Νομίζω ότι είναι σκόπιμο να παραμένουμε στο πνέυμα του μαθήματος γιατί τελικά παρασυρόμαστε και καταλήγουμε να συζητάμε άλλα.

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

Όλοι μας γνωρίζουμε ότι η πλήρης αποτίμηση των λογικών εκφράσεων είναι συνήθως θέμα ρυθμίσεων του compiler (εφόσον δεν είναι ορισμένο κάτι στο standard της γλώσσας).  Στα πλαίσια του διδακτικού πακέτου όμως δε δίνεται (ούτε και υπάρχει λόγος να δίνεται) τέτοια διάσταση.  Το διδακτικό πακέτο ορίζει τους λογικούς τελεστές Η & ΚΑΙ ως δυαδικούς τελεστές στον πίνακα αλήθειας της σελίδας 39.  Νομίζω ότι πρέπει να επιμείνουμε και να αρκεστούμε σε αυτό, το οποίο προδιαγράφει την αποτίμηση και των δύο λογικών εκφράσεων πριν τον υπολογισμό του αποτελέσματος της εφαρμογής του λογικού τελεστή.

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

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

Πρόσφατα μαθητής μου έδωσε παρόμοια λύση σε αλγόριθμο εύρεσης του μικρότερου από Ν αριθμούς:

[glossa]
ΔΙΑΒΑΣΕ Ν
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν
  ΔΙΑΒΑΣΕ τιμή
  ΑΝ ι = 1 ή τιμή < ελάχιστο ΤΟΤΕ
    ελάχιστο <-- τιμή
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
[/glossa]


κρίνοντάς την ως προσφερότερη σε σχέση με τη διαδεδομένη λύση :

[glossa]
ΔΙΑΒΑΣΕ Ν
ΔΙΑΒΑΣΕ τιμή
ελάχιστο <-- τιμή
ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ Ν  ! ή ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙΟ Ν-1
  ΔΙΑΒΑΣΕ τιμή
  ΑΝ τιμή < ελάχιστο ΤΟΤΕ
    ελάχιστο <-- τιμή
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
[/glossa]

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

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

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

Στο παραπάνω παράδειγμα αντιπρότεινα ως ενδεδειγμένη την λύση:

[glossa]
ΔΙΑΒΑΣΕ Ν
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν
  ΔΙΑΒΑΣΕ τιμή
  ΑΝ ι = 1 ΤΟΤΕ
    ελάχιστο <-- τιμή
  ΑΛΛΙΩΣ
    ΑΝ τιμή < ελάχιστο ΤΟΤΕ
      ελάχιστο <-- τιμή
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
[/glossa]


ή την:

[glossa]
ΔΙΑΒΑΣΕ Ν
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν
  ΔΙΑΒΑΣΕ τιμή
  ΑΝ ι = 1 ΤΟΤΕ
    ελάχιστο <-- τιμή
  ΤΕΛΟΣ_ΑΝ
  ΑΝ τιμή < ελάχιστο ΤΟΤΕ
    ελάχιστο <-- τιμή
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
[/glossa]


που δεν έχει τέτοιες ... παγίδες.

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


ΜΣΦΧ
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

P.Tsiotakis

Αγαπητοί φίλοι,

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

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

Περιμένω πάντως με ανυπομονησία τη μέρα που θα έχω και γω τέτοια εμπειρία με μαθητή μου

Με εκτίμηση,

potato

   Το παράδειγμα του κυρίου Τσιωτάκη, πρώτον δε τίθεται σαν ερώτημα σε μια γλώσσα που δεν έχει μεταγλωττιστή. Από εκεί και πέρα το αν θα πετάξει error ο compiler ή όχι είναι θέμα υλοποιησής του. Όλοι οι γνωστοί compilers σήμερα το πετούν πάντως. Τώρα, αν υπάρχει κάποιος που δεν το πετάει τότε το γ έχει μια τιμή και αυτή είναι undefined( δηλαδή, μπορεί να είναι οποιαδήποτε και κατεπέκταση μπορεί και να συμβεί και οτιδήποτε απο την εκτέλεση του).
   Όπως προείπα, δεν τίθεται τέτοιο θέμα και για μένα παρόμοια αναφορά στο μάθημα απλά ΑΠΑΓΟΡΕΥΕΤΑΙ  :) (και εδώ είναι που χρησιμοποιείται την εξουσίας σας και τους λέτε... ΠΑΝΤΑ ΑΡΧΙΚΟΠΟΙΗΣΗ ΠΡΙΝ ΤΗ ΧΡΗΣΗ ΓΙΑΤΙ ΕΤΣΙ ΘΕΛΟΥΜΕ.) :police:
Be open source. Knowledge belongs to the world.