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

Ξεκίνησε από gthal, 30 Μαΐου 2010, 02:23:04 ΜΜ

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

evry

#105
Βασικά το πρόβλημά μου είναι ότι δεν ξέρω σε ποια ομάδα ανήκω, θα το βρούμε στην πορεία. Λοιπόν πως αντιλαμβάνομαι εγώ το όλο θέμα. (Ελπίζω να μην πω πράγματα που έχουν επαναληφθεί αλλά δεν μπορούσα να παρακολουθήσω τα Posts τις τελευταίες μέρες λόγω εξεταστικής)
Θεωρώ ότι τα παρακάτω δεν είναι τα ίδια
   
       Διάβασε M, N                           Δεδομένα Μ,Ν

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

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

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

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


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

Ποιο είναι όμως το μέγεθος του πίνακα? Προφανώς είναι η μέγιστη τιμή του Ν. Ας το συμβολίσουμε κάτι σαν max{Ni}. Πότε καθορίζεται αυτή η τιμή? Αν υποθέσουμε ότι το μέγιστο Ν είναι και το τελευταίο που δίνεται (Μ-οστό) αυτό σημαίνει ότι αρκετά στοιχεία του πίνακα θα έχουν πάρει τιμές πριν γίνει γνωστό το μέγεθός του!!!! Άρα ο πίνακας είναι δυναμικός και όχι στατικός.

Το ξαναλέω: Ο πίνακας θα ξεκινήσει να χρησιμοποιείται και ακόμα δεν θα έχει καθοριστεί το μέγεθος του. Έτσι λοιπόν αποδεικνύεται ότι δεν είναι δυνατόν να διαβάζει ο αλγόριθμος το μέγεθος του πίνακα μέσα στο σώμα του. (Υπάρχει φυσικά και η περίπτωση να έχω κάνει λάθος στο συλλογισμό μου). Το παράδειγμα αυτό το έστειλα πρώτα στον Στάθη και αφού πέρασε από αυτόν που είναι ο υπέρμαχος της δυναμικότητας μου φαίνεται ότι είναι ισχυρό  :).
Θα ήθελα πολύ να ακούσω τις απόψεις σας
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

tom

Είναι καθαρά δυναμικός πίνακας.

Οπότε είμαστε στην περίπτωση:

Παράθεση από: sstergou στις 02 Ιουν 2010, 10:56:12 ΜΜ
Άγνωστο μέγεθος που δεν μπορείς να το μάθεις κατά την εκτέλεση; Και να χρειάζεται και πίνακας για να το λύσεις; Θα έλεγα δυναμικές δομές αλλά είναι εκτός ύλης. Μπορούμε απλά να πούμε ότι δεν λύνονται με πίνακες.

Η θέση σου είναι κοινή και στις τρεις ομάδες. Για να σε εντάξω σε κάποια θέλω και άλλα στοιχεία.  :)
Θωμάς Σκυλογιάννης

- Ζήσε σα να' ταν να πεθάνεις αύριο. Μάθε σα να' ταν να ζεις για πάντα.
                                                                                     Μαχάτμα Γκάντι

pgrontas

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

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

sstergou

Ευριπίδη, νομίζω παρόμοιο παράδειγμα έδωσε και ο Κώστας.
https://alkisg.mysch.gr/steki/index.php?topic=2953.msg29465#msg29465

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

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

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

Ένα παράδειγμα είναι το : https://alkisg.mysch.gr/steki/index.php?topic=2953.msg29506#msg29506

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

tom

Παράθεση από: pgrontas στις 02 Ιουν 2010, 11:42:35 ΜΜ
Μάλλον με εκφράζει καλύτερα, το όχι πίνακας  όταν μπορούμε να υπολογίσουμε αυτό που θέλουμε με ένα πέρασμα ή όταν έχουμε άγνωστο πλήθος.
Τα υπόλοιπα αύριο.
Έτερον εκάτερον. Αυτό που λες όλοι το θέλουν. Η καλύτερη λύση είναι η απλούστερη. Παρ΄όλα αυτά το διόρθωσα και σε άλλαξα κατηγορία!
Θωμάς Σκυλογιάννης

- Ζήσε σα να' ταν να πεθάνεις αύριο. Μάθε σα να' ταν να ζεις για πάντα.
                                                                                     Μαχάτμα Γκάντι

evry

Παράθεση από: sstergou στις 02 Ιουν 2010, 11:43:01 ΜΜ
Ευριπίδη, νομίζω παρόμοιο παράδειγμα έδωσε και ο Κώστας.
https://alkisg.mysch.gr/steki/index.php?topic=2953.msg29465#msg29465
Σου είπα έχω χάσει επεισόδια

Παράθεση
Επίσης δεν είμαι δυναμικομάχος  :angel: (υποστηρικτής της δυναμικότητας) αλλά υποστηρίζω την άποψη ότι, αν είχαμε στατικούς πίνακες με μέγεθος καθοριζόμενο κατά την εκτέλεση (το μέγεθος να καθορίζεται μια φορά και από κει και πέρα να μην αλλάζει, πράγμα εφικτό) θα κερδίζαμε πάρα πολλά διδακτικά, θα είμασταν εντάξει με την επιστήμη, θα μέναμε στο πνεύμα του βιβλίου, θα διαγράφαμε τα άνω όρια (πράγμα που τώρα δεν μπορούμε να το κάνουμε και που θεωρώ ότι είναι αντιεπιστημονικό) και εν τέλει δεν θα χάναμε τίποτε.
Είμαι απόλυτα σύμφωνος με τα παραπάνω
Η γνώμη μου σε αυτό είναι πως αν βάλεις στο παιχνίδι ακόμα και δυναμικούς πίνακες πρέπει μετά να βάλεις και λίγο απόδοση αλγόριθμου (μη βαράτε) ώστε να μπορείς να τον υποχρεώσεις να ακολουθήσει τον δρόμο που εσύ θέλεις. Για παράδειγμα στο θέμα Γ5 θα του έλεγες θέλω αλγόριθμο Ο(n) και θα έληγε η ιστορία. Αυτό φυσικά προυποθέτει ότι το μάθημα θα διδάσκεται και στην Β Λυκειου.
Νομίζω το τέλειο θα ήταν να έκαναν τα παιδιά στην Β λυκειου μια γλώσσα σαν την python (θεωρείται καλή για εισαγωγή) δηλαδή καθαρό προγραμματισμό και στην Γ να έκαναν πραγματική αλγοριθμική.

Παράθεση
Ένα άλλο είναι ο αλγόριθμος που δημιουργεί μονοδιάστατο συμπυκνωμένο από αραιό (sparse) δισδιάστατο (δεν υπάρχει στο πακέτο αλλά φαντάζομαι το έχουμε λύσει σαν άσκηση) καθώς επίσης και όλες οι ασκήσεις στις οποίες δημιουργείται κάποιος πίνακας του οποίου το μέγεθος δεν είναι γνωστό πριν την εκτέλεση (όπως το θέμα της ομάδας διαγωνισμάτων με την κωδικοποίηση RLE).
Για το θέμα του αραιού πίνακα είμαι σίγουρος ότι το πλήθος των μη μηδενικών στοιχείων θα θεωρείται δεδομένο, είναι άκομψο αλλά δεν μπορώ να σκεφτώ άλλη επιλογή.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

tom

Παράθεση από: evry στις 02 Ιουν 2010, 11:54:28 ΜΜ
Είμαι απόλυτα σύμφωνος με τα παραπάνω

Να σε βάλω στην αντίστοιχη ομάδα ;)
Θωμάς Σκυλογιάννης

- Ζήσε σα να' ταν να πεθάνεις αύριο. Μάθε σα να' ταν να ζεις για πάντα.
                                                                                     Μαχάτμα Γκάντι

evry

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

οπότε αυτή τη στιγμή συγκλίνω με Παπαργύρη - Ντζιό

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

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

Παράθεση από: tom στις 02 Ιουν 2010, 11:56:42 ΜΜ
Να σε βάλω στην αντίστοιχη ομάδα ;)

Νομίζω πάντως ότι το πιο ισχυρό επιχείρημα που έχει η ομάδα που υποστηρίζει ότι μπορεί να δοθεί το μέγεθος του πίνακα ενώ εκτελείται ο αλγόριθμος είναι ότι η ψευδογλώσσα πρέπει να είναι αρκετά γενική ώστε να μπορεί να κωδικοποιηθεί σε όσον το δυνατόν περισσότερες γλώσσες προγραμματισμού
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

tom

Παράθεση από: evry στις 03 Ιουν 2010, 12:07:08 ΠΜ
Νομίζω πάντως ότι το πιο ισχυρό επιχείρημα που έχει η ομάδα που υποστηρίζει ότι μπορεί να δοθεί το μέγεθος του πίνακα ενώ εκτελείται ο αλγόριθμος είναι ότι η ψευδογλώσσα πρέπει να είναι αρκετά γενική ώστε να μπορεί να κωδικοποιηθεί σε όσον το δυνατόν περισσότερες γλώσσες προγραμματισμού
Σωστό. Σε έβαλα στην ομάδα που θέλεις  :)

Παράθεση από: evry στις 03 Ιουν 2010, 12:07:08 ΠΜ
Αυτό που υποστηρίζει ο Στάθης και εσύ είναι το ιδανικό που θα θέλαμε να ισχύει , έλα όμως που δεν ισχύει αυτό.

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

- Ζήσε σα να' ταν να πεθάνεις αύριο. Μάθε σα να' ταν να ζεις για πάντα.
                                                                                     Μαχάτμα Γκάντι

evry

Ναι βρε το θέμα είναι ότι εμείς δεν κάνουμε αυτή την ιδανική ψευδογλώσσα, αλλά την άλλη τη στρυφνή του βιβλίου
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

sstergou

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

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

Κουβέντα να γίνεται...

evry

όταν λέω δυναμικούς εννοώ δυναμικούς όπως στην Python, perl , php, javascript κλπ
Για παράδειγμα θεωρώ ότι σε μια ψευδογλώσσα ταιριάζουν πολύ τα associative arrays (έχουμε ξεφύγει ε?)

edit: πάντως στα πλαίσια του μαθήματος συμφωνώ με αυτό που είπε ο Γροντάς προηγουμένως
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

tom

Παράθεση από: evry στις 03 Ιουν 2010, 12:20:01 ΠΜ
Ναι βρε το θέμα είναι ότι εμείς δεν κάνουμε αυτή την ιδανική ψευδογλώσσα, αλλά την άλλη τη στρυφνή του βιβλίου

Σε αυτό συμφωνώ με το Στάθη.

Παράθεση από: sstergou στις 02 Ιουν 2010, 01:42:46 ΜΜ
Δεν θα είχα πρόβλημα επίσης να δεχτώ ότι στην ψευδογλώσσα, αυτού του βιβλίου, το μέγεθος πρέπει να είναι γνωστό πριν την εκτέλεση. Αυτό όμως δεν συμβαδίζει με τα παραδείγματα του πακέτου. Σε αυτό δεν φταίμε εμείς!
Θωμάς Σκυλογιάννης

- Ζήσε σα να' ταν να πεθάνεις αύριο. Μάθε σα να' ταν να ζεις για πάντα.
                                                                                     Μαχάτμα Γκάντι

evry

πότε και που είναι αυτό ?

Παράθεση από: tom στις 02 Ιουν 2010, 09:55:05 ΜΜ

Προτείνω συγκέντρωση για ούζα, στο πλαίσιο του πανελλήνιου διαγωνισμού ρομποτικής! Τότε θα αποφασίσω! Μέχρι τότε  :-X

What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

bagelis

Παράθεση από: evry στις 02 Ιουν 2010, 11:07:35 ΜΜ
Διάβασε Μ
Για ι από 1 μέχρι Μ
    Διάβασε Ν
    Για ι από 1 μέχρι Ν             
        Διάβασε Α[ι]
    Τέλος_Επανάληψης
Τέλος_Επανάληψης


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

Θα ήθελα πολύ να ακούσω τις απόψεις σας
Ευριπίδη, όχι δεν είναι το ίδιο γιατί ο ίδιος πίνακας επαναορίζεται πολλές φορές. Δεν μπορείς να ισχυριστείς ότι θα έχει μέγεθος max(N) γιατί σύμφωνα με τη θεώρηση ο πίνακας μπορεί να οριστεί μόνο μία φορά. Το μαχ(Ν) το μαθαίνεις μετά από Μ επαναλήψεις και άρα μετά από Μ ορισμούς του πίνακα...
Αν έχω καταλάβει καλά με βάση τον αφηρημένη δομή πίνακας μπορείς να ορίσεις ΜΙΑ φορά τον πίνακα, άρα πρέπει να το κάνεις στο πρώτο διάβασμα του Ν. Μετά δεν μπορείς να το ξανακάνεις.
Πάνω σε αυτή την άποψη, και με όσα διάβασα εδώ, έχω στο μυαλό μου ένα αόρατο
create_table(name, N) το οποίο μπορείς να το κάνεις μόνο μία φορά και έτσι δεσμεύει ένα συνεχόμενο χώρο μνήμης με μέγεθος Ν. Άπαξ και το έκανες τέλος.
Έτσι όπως το λές εσύ πιάνει και τις ασκήσεις με τιμή φρουρό, αφού μπορείς να το επαναορίζεις συνέχεια...