Θέμα: ψευδογλώσσα και πίνακες

[sstergou]

Αυτό μου αρκεί Στάθη.

Λες να συμφωνήσουμε σε κάτι στο τέλος; 

[gpapargi]

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

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

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

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

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

[merlin]

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

[gpapargi]

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

[jkapsi]

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

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

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

[merlin]

Ναι Γιώργο, βασικά το δικηγόρο του διαβόλου κάνω, συμφωνώ μαζί σου.  (σόρυ Στάθη για το διάβολος    )

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

Θα ήθελα και εγώ να μου πει κάποιος την σελίδα για να μην ψάχνω.

[gpapargi]

Εννοείται... κουβέντα κάνουμε. Τουλάχιστον οι παλιοί γνωριζόμαστε μεταξύ μας και μιλάμε πάντα χωρίς σκοπιμότητες, μόνο για να καταλάβουμε τι συμβαίνει.

[bagelis]

Ναι Γιώργο, βασικά το δικηγόρο του διαβόλου κάνω, συμφωνώ μαζί σου.  (σόρυ Στάθη για το διάβολος    )

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

Θα ήθελα και εγώ να μου πει κάποιος την σελίδα για να μην ψάχνω.

σελ 90 σχολικό βιβλίο (όπως πολύ εύστοχα εντόπισε ο συνάδελφος): Υλοποιεί αλγόριθμο χρημιμοποιώντας πίνακα με άγνωστο αρχικά πλήθος στοιχείων.
Αλγόριθμος Δύναμη2
Δεδομένα // a, b //
!Σχόλιο: αποθήκευση στοιχείων πίνακα
power[1] ← a
i ← 1
pow ← 1
Όσο pow < b επανάλαβε
i ← i+1
pow ← 2* pow
power ← power[i-1] * power[i-1]
Τέλος_επανάληψης
Σελ 32 Τετράδιο Μαθητή Αραιοί Πίνακες είναι προφανές ότι το μέγεθος του πίνακα που δημιουργείται καθορίζεται κατά τη στιγμή της εκτέλεσης. Δεν γνωρίζεις από πριν τον αριθμό των μη μηδενικών στοιχείων του δισδιάστατου πίνακα.

Αντί να αποθηκεύσουμε αυτόν το δισδιάστατο πίνακα 4x5, θα θεωρήσουμε ένα μο-
νοδιάστατο πίνακα όπου θα τοποθετήσουμε μόνο τα μη μηδενικά στοιχεία, για τα ο-
ποία όμως χρειαζόμαστε τα στοιχεία των αντίστοιχων γραμμών και στηλών. Έτσι κα-
ταλήγουμε κάθε μη μηδενικό στοιχείο να αντιπροσωπεύεται από μία τριάδα στοι-
χείων, δηλαδή <γραμμή,στήλη,τιμή>. Για το λόγο αυτό δημιουργούμε ένα μονοδιά-
στατο πίνακα 18 θέσεων για τα 6 μη μηδενικά στοιχεία του αρχικού πίνακα.

[jkapsi]

Σελ 32 Τετράδιο Μαθητή Αραιοί Πίνακες είναι προφανές ότι το μέγεθος του πίνακα που δημιουργείται καθορίζεται κατά τη στιγμή της εκτέλεσης. Δεν γνωρίζεις από πριν τον αριθμό των μη μηδενικών στοιχείων του δισδιάστατου πίνακα.

Αντί να αποθηκεύσουμε αυτόν το δισδιάστατο πίνακα 4x5, θα θεωρήσουμε ένα μο-
νοδιάστατο πίνακα όπου θα τοποθετήσουμε μόνο τα μη μηδενικά στοιχεία, για τα ο-
ποία όμως χρειαζόμαστε τα στοιχεία των αντίστοιχων γραμμών και στηλών. Έτσι κα-
ταλήγουμε κάθε μη μηδενικό στοιχείο να αντιπροσωπεύεται από μία τριάδα στοι-
χείων, δηλαδή <γραμμή,στήλη,τιμή>. Για το λόγο αυτό δημιουργούμε ένα μονοδιά-
στατο πίνακα 18 θέσεων για τα 6 μη μηδενικά στοιχεία του αρχικού πίνακα.

την άσκηση με τους αραιούς την έκανα και γω. Στην ψευδογλώσσα ούτε που συζητήσαμε με τα παιδιά για το μέγεθος του πίνακα. Όταν όμως το έκανα σε πρόγραμμα με ρώτησαν τι μέγεθος να δηλώσουν τον μονοδιάστατο πίνακα. Τους είπα πως αν υπάρχει ο ελάχιστος αριθμός μηδενικών (80%) τότε το μέγιστο μέγεθος πίνακα θα είναι τουλάχιστον Α_Μ(γραμμή x στήλη x 0.2 x 3)

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

[sstergou]

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

Νομίζω λοιπόν πως σε αυτό έχετε δίκιο, δεν υπάρχει ολόιδιο παράδειγμα στο πακέτο (τουλάχιστον εγώ δεν βρίσκω ( Διάβασε Ν, Για ι από 1 μέχρι Ν)), υπάρχει όμως αυτός με την δύναμη  που κάνει κάτι χειρότερο από αυτό που υποστηρίζω πως πρέπει να δεχτούμε.

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

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

Γιώργο, Κώστα και υπόλοιποι, συμφωνείτε ότι πρόκειται για ασάφεια;

Όποτε μπαίνω στην διαδικασία της σκέψης ότι το μέγεθος είναι σταθερό και γνωστό πριν την εκτέλεση καταλήγω σε λογικό αδιέξοδο.

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

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

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

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

[jkapsi]

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

Νομίζω λοιπόν πως σε αυτό έχετε δίκιο, δεν υπάρχει ολόιδιο παράδειγμα στο πακέτο (τουλάχιστον εγώ δεν βρίσκω ( Διάβασε Ν, Για ι από 1 μέχρι Ν)), υπάρχει όμως αυτός με την δύναμη  που κάνει κάτι χειρότερο από αυτό που υποστηρίζω πως πρέπει να δεχτούμε.

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

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

Γιώργο, Κώστα και υπόλοιποι, συμφωνείτε ότι πρόκειται για ασάφεια;

Όποτε μπαίνω στην διαδικασία της σκέψης ότι το μέγεθος είναι σταθερό και γνωστό πριν την εκτέλεση καταλήγω σε λογικό αδιέξοδο.

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

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

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

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

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

Στους αραιούς πίνακες πχ:

1- Τρέχω τον 2d πίνακα και μετράω τα μη μηδενικά (έστω Ν).

2 -Ορίζω τον πίνακα δυναμικά (στην ουσία όμως είναι στατικός, δεν μπορώ να τον ξαναορίσω με Μ>Ν, αφού είναι στατική δομή δεδομένων)

3 - Ξανατρέχω τον 2d πίνακα για να γεμίσω τον μονοδιάστατο


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

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

[sstergou]

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

Το πρόβλημα όμως είναι ότι αυτό είναι απλά άποψη/πρόταση. Χωρίς επίσημη τοποθέτηση από το ΠΙ η ασάφεια (ή το πρόβλημα αν δεν σας αρέσει η λέξη) παραμένει.

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

Το θέμα φίλε jkapsi ήταν να μην εξεταστεί κάτι τέτοιο...

[merlin]

Θα ήθελα να ρωτήσω ΟΛΟΥΣ αν υπάρχουν κι άλλα παραδείγματα από το βιβλίο που δημιουργούν προβληματισμό στο συγκεκριμένο θέμα για να μπορέσουμε να τα μαζέψουμε σε αυτό το τοπικ και να τα λύνουμε ένα - ένα.

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

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

[jkapsi]

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

Το πρόβλημα όμως είναι ότι αυτό είναι απλά άποψη/πρόταση. Χωρίς επίσημη τοποθέτηση από το ΠΙ η ασάφεια (ή το πρόβλημα αν δεν σας αρέσει η λέξη) παραμένει.

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

Το θέμα φίλε jkapsi ήταν να μην εξεταστεί κάτι τέτοιο...

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

Άσε που αυτή η προσέγγιση θα βοηθούσε και τα υποπρογράμματα να "εκτοξευτούν"

ΔΙΑΔΙΚΑΣΙΑ read(Π,Ν)
...δηλώσεις μεταβλητών
...πινακας Π μεγέθους Ν

...εντολές διαβάσματος πίνακα

ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

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

[sstergou]

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

Σκεφτείτε πόσο χρήσιμο θα ήταν το εξής

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

ΠΡΟΓΡΑΜΜΑ τάδε
ΣΤΑΘΕΡΕΣ
  ΑΚΕΡΑΙΕΣ : Ν
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ : ΠΙΝ[Ν]
ΑΡΧΗ
  ΔΙΑΒΑΣΕ Ν
...

Μην ελπίζετε σε πολλά όμως . Στο μόνο που μπορούμε να ελπίζουμε είναι κάποιοι που ενδιαφέρονται να διαβάζουν αυτά που γράφουμε.

P.S. Και εγώ νέος είμαι...