Θέμα: Εναλλακτική επίλυση άσκησης

[olga_ath]

Χαίρεται

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

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

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

Κατα την ταπεινή μου γνώμη από διδακτικής απόψεως αυτό μπερδευει τους μαθητές οι οποίοι δεν μπορούν να κατανοήσουν πως θα είναι ο πίνακας με μερικά κελιά σε απροσδιόριστη μορφή και δυσκολευομαι και η ίδια να εξηγήσω αποδοτικά γιατί το κάνουμε αυτό. Μερικές φορές σκέφτομαι ότι έρχεται σε αντίθεση με ότι εξήγησα στην αρχή της διδασκαλία των αδερφών κεφαλαίων 3-9 ότι δλδ πρέπει όλα τα στοιχεία ενός πίνακα να έχουν τον ίδιο τύπο δεδομένων. Τώρα όμως που ορισμένα στοιχεία είναι απροσδιόριστα δεν παραβιάζεται αυτή η αρχή;

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

Σας ευχαριστώ όλους εκ των προτέρων

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

Το ότι ένας πίνακας έχει απροσδιόριστες τιμές δεν σημαίνει ότι δεν θα είναι του ίδιου τύπου.

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

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

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

Αλγόριθμος θετικοί
Δεδομένα // Ν //

Για ι από 1 μέχρι Ν
   Διάβασε Α[ι]
Τέλος_επανάληψης

top<-0
Για ι από 1 μέχρι Ν
    Αν Α[ι]>0 τότε
        top<-top+1
        B[top]=A[ι]
   Τέλος_αν
Τέλος_επανάληψης

Αποτελέσματα // Β, top //
Τέλος θετικοί

Το έκανα να θυμίζει στοίβα  - top είναι το πλήθος των θετικών στον πίνακα Β

[olga_ath]

Σας ευχαριστώ πάρα πολύ για την κατατοπιστική απάντηση !

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

[pgrontas]

Μια πολύ ωραία ερώτηση είναι η εξής:

Ποιο το παιδαγωγικό ώφελος της ύπαρξης απροσδιόριστων τιμών πριν την πρώτη ανάθεση;
Μήπως αυτό συμβαίνει επειδή έτσι δούλευε η Pascal και η C;
Μήπως θα μπορούσαμε να έχουμε μία προκαθορισμένη τιμή ανά τύπο δεδομένων;

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

[sstergou]

Επίσης δεν είναι απαραίτητο ο νέος πίνακας να έχει Ν στοιχεία.
Έχω την εντύπωση ότι στο παράδειγμα του Νίκου έχει όσα στοιχεία όσα και οι θετικοί αριθμοί καθώς δεν ορίζουμε πουθενά το μέγεθός του.

[olga_ath]

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

Αν υπάρχει κάποια καλύτερη προσέγγιση θα χαρώ πολύ να την ακούσω.

Τέλος κατά τη γνώμη μου το πόσα στοιχεία θα έχει ο νέος πίνακας έστω Κ  με 0=< Κ=< Ν ειναι αρκετά ξεκάθαρο για τα παιδιά.

[sstergou]

Ναι αυτό που λες ισχύει* όταν γράφεις προγράμματα σε ΓΛΩΣΣΑ.

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

* Μπορεί να ισχύει, όπως ανέφερε ο pgrontas.

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

Μια πολύ ωραία ερώτηση είναι η εξής:

Ποιο το παιδαγωγικό ώφελος της ύπαρξης απροσδιόριστων τιμών πριν την πρώτη ανάθεση;
Μήπως αυτό συμβαίνει επειδή έτσι δούλευε η Pascal και η C;
Μήπως θα μπορούσαμε να έχουμε μία προκαθορισμένη τιμή ανά τύπο δεδομένων;

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

Υπάρχουν κάποια υπέρ και κάποια κατά... Όντως είναι ωραίο θέμα για συζήτηση, οπότε Παναγιώτη βρες έναν κατάλληλο τίτλο και άνοιξε νέο θέμα...!

[P.Tsiotakis]

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

Αυτή είναι και η φιλοσοφία του παραδείγματος 2, όπου ο πίνακας Χ δηλώνεται με 100 θέσεις, αλλά τελικά χρησιμοποιούνται λιγότερες (Ν). Όλες οι επεξεργασίες στον πίνακα (η τελική τιμή του Για) καταλήγουν στο Ν και όχι στο 100.

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

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

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

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

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

[pgrontas]

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

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

[sstergou]

Σε αυτό το σημείο η συζήτηση συνεχίστηκε με θέμα την αυτόματη αρχικοποίηση μεταβλητών.
Η συνέχεια της συζήτησης  σε αυτό το θέμα

[sstergou]

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

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

Το σίγουρο Παναγιώτη είναι ότι οι συγγραφείς είχαν αυτή την πρόθεση (στο παρόν σημείο δεν κρίνω την χρησιμότητας αυτής της τακτικής). Το εξέφρασαν όμως με λάθος τρόπο. Οι πίνακες λοιπόν είναι στατική δομή.
Μακάρι να το είχαν φτιάξει έτσι ώστε να μην διαφωνούμε τώρα. Όμως αυτό το χαρακτηριστικό παραμένει ιδεατό μέχρι να περάσουμε στην ΓΛΩΣΣΑ. Το πιο σωστό λοιπόν θα ήταν να ειπωθεί το εξής (χωρίς να χαλάσουμε την φιλοσοφία). "Οι πίνακες είναι στατική δομή δεδομένων, αυτό σημαίνει ότι το μέγεθός τους θα πρέπει να είναι γνωστό κατά την έναρξη της εκτέλεσης του αλγορίθμου". Και είμαστε όλοι εντάξει χωρίς αναφορές σε μεταγλωττίσεις κλπ. Για να είναι όμως αυτό συνεπές θα πρέπει να αλλαχτεί και η εντολή Δεδομένα // ΠΙΝ, Ν// και να γίνει Δεδομένα //ΠΙΝ[Ν]// .

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

Μήπως στις προτάσεις να βάζαμε και αυτό;

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

[sstergou]

Αλγόριθμος θετικοί
Δεδομένα // Ν //

Για ι από 1 μέχρι Ν
   Διάβασε Α[ι]
Τέλος_επανάληψης

top<-0
Για ι από 1 μέχρι Ν
    Αν Α[ι]>0 τότε
        top<-top+1
        B[top]=A[ι]
   Τέλος_αν
Τέλος_επανάληψης

Αποτελέσματα // Β, top //
Τέλος θετικοί

Το έκανα να θυμίζει στοίβα  - top είναι το πλήθος των θετικών στον πίνακα Β

Δηλαδή Νίκο εδώ από έναν πίνακα με Ν στοιχεία έφτιαξες έναν με top στοιχεία; Δήλωσες πουθενά ότι έχει top στοιχεία; Ξέρουμε πόσο είναι το top από πριν ή πρέπει να τρέξουμε τον αλγόριθμο; Είναι αυτό σωστό;

[evry]

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

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

[sstergou]

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

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

 Εξάλλου όπως έχω ξαναπεί δεν έχει σχέση το αν μια δομή είναι στατική ή όχι με το αν το μέγεθός της είναι γνωστό την στιγμή του προγραμματισμού. Πολλές γλώσσες δεν έχουν πίνακες με την μορφή που περιγράφονται στο βιβλίο. Να θυμίσω τις λίστες της lisp, τα hashes της php και πολλών άλλων γλωσσών όπως της python. Οι σχεδιαστές αυτών των γλωσσών προτίμησαν την ευελιξία που δίνουν δυναμικές υλοποιήσεις έναντι της απόδοσης κατά την προσπέλαση μιας τιμής. Και μη μου πείτε ότι στην ψευδογλώσσα μας νοιάζει η απόδοση περισσότερο από την python?

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

Θέλω να πω ότι ο ορισμός του βιβλίου είναι άκαιρος και μη χρήσιμος και επιβάλλει μη παιδαγωγικούς περιορισμούς αφού σκοπός δεν είναι "η εκμάθηση μιας συγκεκριμένης γλώσσας" αν και όσο περνάει ο καιρός καταλαβαίνω ότι μάλλον ο σκοπός μας είναι να μάθουν οι μαθητές την BASIC του '80.

Στο θέμα της απόδοσης των πινάκων. Βρίσκουμε τους μέγιστους με ταξινόμηση, κάνουμε αναζήτηση με Για και πολλά άλλα παραδείγματα άλλα σοβαρά και άλλα όχι, και μας πειράζει η εσωτερική υλοποίηση των πινάκων και αν ο υπολογιστής αντί για 0.01 ms θα κάνει 0.02 για να πάρει ένα στοιχείο; Γιατί; Το πως υλοποιούνται οι πίνακες θα έπρεπε να μας νοιάζει;