Αποστολέας Θέμα: ψευδογλώσσα και πίνακες  (Αναγνώστηκε 26159 φορές)

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Απ: ψευδογλώσσα και πίνακες
« Απάντηση #105 στις: 02 Ιούν 2010, 11:07:35 μμ »
Βασικά το πρόβλημά μου είναι ότι δεν ξέρω σε ποια ομάδα ανήκω, θα το βρούμε στην πορεία. Λοιπόν πως αντιλαμβάνομαι εγώ το όλο θέμα. (Ελπίζω να μην πω πράγματα που έχουν επαναληφθεί αλλά δεν μπορούσα να παρακολουθήσω τα Posts τις τελευταίες μέρες λόγω εξεταστικής)
Θεωρώ ότι τα παρακάτω δεν είναι τα ίδια
   
       Διάβασε M, N                           Δεδομένα Μ,Ν

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

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

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

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


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

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

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

tom

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 488
Απ: ψευδογλώσσα και πίνακες
« Απάντηση #106 στις: 02 Ιούν 2010, 11:33:43 μμ »
Είναι καθαρά δυναμικός πίνακας.

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

Άγνωστο μέγεθος που δεν μπορείς να το μάθεις κατά την εκτέλεση; Και να χρειάζεται και πίνακας για να το λύσεις; Θα έλεγα δυναμικές δομές αλλά είναι εκτός ύλης. Μπορούμε απλά να πούμε ότι δεν λύνονται με πίνακες.

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

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

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1316
  • There are always possibilities...
Απ: ψευδογλώσσα και πίνακες
« Απάντηση #107 στις: 02 Ιούν 2010, 11:42:35 μμ »
tom, δεν με έχεις βάλει σωστά!!! Το άνω όριο δεν μου αρέσει καθόλου.
Ούτε και στους δυναμικούς πίνακες μπορώ να πω ότι ανήκω, αν και μου αρέσουν στις διάφορες γλώσσες, γιατί θεωρώ ότι κακομαθαίνουν τους μαθητές.
Πάντως από όλα τα πράγματα που ακούστηκαν οι περιγραφές του merlin με εξέφρασαν περισσότερο.
Επίσης γενικά το στατικό,δυναμικό μου φαίνεται λεπτομέρεια υλοποίησης, αν και μπορώ να το δεχτώ στα πλαίσια του μαθήματος.
Μάλλον με εκφράζει καλύτερα, το όχι πίνακας  όταν μπορούμε να υπολογίσουμε αυτό που θέλουμε με ένα πέρασμα ή όταν έχουμε άγνωστο πλήθος.
Τα υπόλοιπα αύριο.

A man provided with paper, pencil, and rubber, and subject to strict discipline is in effect a universal machine - Alan Turing

sstergou

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 983
  • Program or be Programmed
    • pseudoglossa.gr
Απ: ψευδογλώσσα και πίνακες
« Απάντηση #108 στις: 02 Ιούν 2010, 11:43:01 μμ »
Ευριπίδη, νομίζω παρόμοιο παράδειγμα έδωσε και ο Κώστας.
http://alkisg.mysch.gr/steki/index.php?topic=2953.msg29465#msg29465

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

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

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

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

Ένα άλλο είναι ο αλγόριθμος που δημιουργεί μονοδιάστατο συμπυκνωμένο από αραιό (sparse) δισδιάστατο (δεν υπάρχει στο πακέτο αλλά φαντάζομαι το έχουμε λύσει σαν άσκηση) καθώς επίσης και όλες οι ασκήσεις στις οποίες δημιουργείται κάποιος πίνακας του οποίου το μέγεθος δεν είναι γνωστό πριν την εκτέλεση (όπως το θέμα της ομάδας διαγωνισμάτων με την κωδικοποίηση RLE).
Στάθης Στέργου - sstergouATgmailDOTcom - http://www.pseudoglossa.gr

tom

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 488
Απ: ψευδογλώσσα και πίνακες
« Απάντηση #109 στις: 02 Ιούν 2010, 11:48:28 μμ »
Μάλλον με εκφράζει καλύτερα, το όχι πίνακας  όταν μπορούμε να υπολογίσουμε αυτό που θέλουμε με ένα πέρασμα ή όταν έχουμε άγνωστο πλήθος.
Τα υπόλοιπα αύριο.
Έτερον εκάτερον. Αυτό που λες όλοι το θέλουν. Η καλύτερη λύση είναι η απλούστερη. Παρ΄όλα αυτά το διόρθωσα και σε άλλαξα κατηγορία!
Θωμάς Σκυλογιάννης

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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Απ: ψευδογλώσσα και πίνακες
« Απάντηση #110 στις: 02 Ιούν 2010, 11:54:28 μμ »
Ευριπίδη, νομίζω παρόμοιο παράδειγμα έδωσε και ο Κώστας.
http://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

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 488
Απ: ψευδογλώσσα και πίνακες
« Απάντηση #111 στις: 02 Ιούν 2010, 11:56:42 μμ »
Είμαι απόλυτα σύμφωνος με τα παραπάνω

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

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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Απ: ψευδογλώσσα και πίνακες
« Απάντηση #112 στις: 03 Ιούν 2010, 12:07:08 πμ »
όχι γιατί θα το παίξω κατάσκοπος. Αυτό που υποστηρίζει ο Στάθης και εσύ είναι το ιδανικό που θα θέλαμε να ισχύει , έλα όμως που δεν ισχύει αυτό. Δηλαδή  στη συγκεκριμένη ψευδογλώσσα του βιβλίου υπάρχουν περιορισμοί, στην πραγματικότητα φέρνει προς μια γλώσσα προγραμματισμού χωρίς αυστηρή σύνταξη. Για παράδειγμα
   Στατικοί πίνακες
    Δεν μπορούμε να πειράξουμε τον μετρητή μέσα στην Για και άλλα

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

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

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

Να σε βάλω στην αντίστοιχη ομάδα ;)

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

tom

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 488
Απ: ψευδογλώσσα και πίνακες
« Απάντηση #113 στις: 03 Ιούν 2010, 12:14:17 πμ »
Νομίζω πάντως ότι το πιο ισχυρό επιχείρημα που έχει η ομάδα που υποστηρίζει ότι μπορεί να δοθεί το μέγεθος του πίνακα ενώ εκτελείται ο αλγόριθμος είναι ότι η ψευδογλώσσα πρέπει να είναι αρκετά γενική ώστε να μπορεί να κωδικοποιηθεί σε όσον το δυνατόν περισσότερες γλώσσες προγραμματισμού
Σωστό. Σε έβαλα στην ομάδα που θέλεις  :)

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

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

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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Απ: ψευδογλώσσα και πίνακες
« Απάντηση #114 στις: 03 Ιούν 2010, 12:20:01 πμ »
Ναι βρε το θέμα είναι ότι εμείς δεν κάνουμε αυτή την ιδανική ψευδογλώσσα, αλλά την άλλη τη στρυφνή του βιβλίου
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

sstergou

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 983
  • Program or be Programmed
    • pseudoglossa.gr
Απ: ψευδογλώσσα και πίνακες
« Απάντηση #115 στις: 03 Ιούν 2010, 12:25:03 πμ »
Ευριπίδη, επειδή δεν είμαι σίγουρος για το τι εννοείς δυναμικούς πίνακες, για τη ιστορία αναφέρω ότι εγώ δεν προτείνω να υιοθετήσουμε δυναμικούς πίνακες αλλά στατικούς που το μέγεθός τους καθορίζεται μια φορά και δεν αλλάζει κατά την εκτέλεση.

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

Κουβέντα να γίνεται...
Στάθης Στέργου - sstergouATgmailDOTcom - http://www.pseudoglossa.gr

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Απ: ψευδογλώσσα και πίνακες
« Απάντηση #116 στις: 03 Ιούν 2010, 12:28:40 πμ »
όταν λέω δυναμικούς εννοώ δυναμικούς όπως στην Python, perl , php, javascript κλπ
Για παράδειγμα θεωρώ ότι σε μια ψευδογλώσσα ταιριάζουν πολύ τα associative arrays (έχουμε ξεφύγει ε?)

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

tom

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 488
Απ: ψευδογλώσσα και πίνακες
« Απάντηση #117 στις: 03 Ιούν 2010, 12:32:45 πμ »
Ναι βρε το θέμα είναι ότι εμείς δεν κάνουμε αυτή την ιδανική ψευδογλώσσα, αλλά την άλλη τη στρυφνή του βιβλίου

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

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

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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Απ: ψευδογλώσσα και πίνακες
« Απάντηση #118 στις: 03 Ιούν 2010, 12:48:23 πμ »
πότε και που είναι αυτό ?


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

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

bagelis

  • Ομάδα διαγωνισμάτων 2009
  • *
  • Μηνύματα: 511
Απ: ψευδογλώσσα και πίνακες
« Απάντηση #119 στις: 03 Ιούν 2010, 12:55:56 πμ »
Διάβασε Μ
Για ι από 1 μέχρι Μ
    Διάβασε Ν
    Για ι από 1 μέχρι Ν             
        Διάβασε Α[ι]
    Τέλος_Επανάληψης
Τέλος_Επανάληψης


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

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