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

[evry]

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

[bagelis]

όχι, δεν είναι το ίδιο.....

φαντάσου να έχεις την εντολή create_table(name, N) αλλά χωρίς την εντολή dispose(name, N).

Διάβασε Μ
Για ι από 1 μέχρι Μ
     Διάβασε Ν
     Για ξ από 1 μέχρι Ν   //εδώ την πρώτη φορά μπορώ να παίξω με πίνακα Ν θέσεων (create_table(A, N))
          Διάβασε Α[ι]       //την δεύτερη φορά όμως δεν μπορώ να ξανακάνω το ίδιο (create_table(A, N)),       
                                  //χτυπάει, ο Α είναι ήδη πιασμένος, δεν υπάρχει dispose για να μπορέσεις μετά να
                                  //ξανακάνεις ορισμό
     Τέλος_Επανάληψης
Τέλος_Επανάληψης

[evry]

ένα λεπτό, αυτό που μόλις περιέγραψες δεν είναι δυναμική εκχώρηση μνήμης?

[bagelis]

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

τέτοιο πράγμα όμως (ευτυχώς) δεν έχουμε....

[bagelis]

ένα λεπτό, αυτό που μόλις περιέγραψες δεν είναι δυναμική εκχώρηση μνήμης?

όχι Ευριπίδη, αυτό που λένε (και επαναλαμβάνω, αν το έχω καταλάβει καλά) είναι ότι ο πίνακας ορίζεται στατικά σε συνεχόμενες θέσεις μνήμης κατά την εκτέλεση.
Δηλαδή ότι ο πίνακας έχει τις ακόλουθες ιδιότητες:
1) create_table(name, N)
2) fetch_element(name, i)
3) update_element(name, i,x)
μόνο αυτές, κατά συνέπεια άπαξ και τον όρισες δεν μπορείς να τον ξαναορίσεις....Κάποιος το έγραψε αυτό κάπου εδώ μέσα, δεν είναι δικό μου...
Στο δικό σου παράδειγμα ο πίνακας επαναορίζεται συνέχεια....

αν βοηθάει στην άποψη αυτή δείτε και αυτο: http://www.itl.nist.gov/div897/sqg/dads/HTML/array.html

[evry]

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

[merlin]

...
Παπαργύρης, Ντζιος, Merlin, Βραχνός -> Στατικοί πίνακες σημαίνει γνωστό μέγεθος κατά τη μεταγλώττιση. ΜΟΝΟ!...:-) Σωστά;
Και πως δικαιολογούνται τα αδικαιολόγητα παραδείγματα του βιβλίου ρε παιδιά; Ειδικά αυτό με τη δύναμη είναι all the money...

....

Νομίζω ότι απάντησα για το θέμα της δύναμης. Αν θέλετε όμως πέστε μου το λάθος, γιατί είναι και μια ώρα δύσκολη...
Πιστεύω ότι είναι προφανές, ο πίνακας που δημιουργείται είναι μεγέθους b (του εκθέτη της δύναμης a^b), όχι b+1, ΠΑΝΤΑ b. Επίσης το b είναι στην γραμμή Δεδομένα  //a,b//

Για να το πω απλούστερα, δοθείσας δύναμης a^b με τα a και b γνωστά, ξέρω ακριβώς τον πίνακα που θα χρειαστώ για να υλοποιηθεί η δύναμη. Θα χρειαστούν το ΠΟΛΥ b κουτάκια.
Θα μου πείτε, βάζεις πάνω όριο και χρησιμοποιείς όσα κουτάκια θέλεις. Το ξέρω,  τι να κάνω, αφού μόνο στατικούς πίνακες ξέρω (με την έννοια του βιβλίου). Το πάνω όριο όμως μου το βάζει η εκφώνηση, δεν πρέπει να αυτοσχεδιάσω εγώ. Γιατί στον αυτοσχεδιασμό οι μαθητές θα κάνουν περισσότερα λάθη από όσα θα αποφεύγουν.

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

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

Αδαμόπουλος, Γροντάς -> Πιστοί στη στατικότητα αλλά δέχονται και ένα άνω φράγμα ρε παιδί μου! Έτσι για να δικαιολογήσουν τα ευτράπελα του βιβλιου και των εξετάσεων :-)
Και αν δε ξέρουμε το όριο; Ή δε γίνεται να αποφύγουμε τους πίνακες; Π.Χ. να βρεθεί το πλήθος των κόκκων άμμου που έχουν όγκο μεγαλύτερο από τον μέσο όρο;! 

... Πάντως μερικές σελίδες πίσω είχα καταγράψει και τα εξής: https://alkisg.mysch.gr/steki/index.php?topic=2953.msg29311#msg29311 . Επομένως μπορώ να στηρίξω και άλλες απόψεις...

Όσον αφορά τους κόκκους άμμου σκέφτομαι να πατεντάρω την άσκηση... 

[merlin]

Όσον αφορά τους κόκκους άμμου σκέφτομαι να πατεντάρω την άσκηση... 

Θέλω να σου έρθει κάποιος μαθητής με δηλωμένο πίνακα μεγέθους   ΜάζαΓης/ΜάζαΠρωτονίου και να σου κάνει τους τυφλοσούρτες!!!

Εγώ θα πατεντάρω τη λύση!!

[gthal]

Α, βλέπω κι άλλους ξενύχτες! 

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

Λοιπόν, εγώ έχω πάψει πια να πολυδιαβάζω και να γράφω για το θέμα.
Ο μόνος λόγος που ξαναδιάβασα προσεκτικά ήταν γιατί μπήκε κι ο Ευριπίδης και δεν είχα ακούσει τη γνώμη του.
Ε, λοιπόν, μετά από 5 (ή 6 ?) μέρες, κατάφερε να τουμπάρει κι εμένα (όπως και το Στάθη, απ' ότι κατάλαβα)!
Ο Ευριπίδης πρόσθεσε αυτό το μαγικό "δεν μπορούμε στην ψευδογλώσσα (του βιβλίου, όχι γενικά στην ψευδογλώσσα)" .
Μπορώ να δεχθώ αυτή τη σύμβαση. Το βιβλίο προσπαθεί να διδάξει αυτή την ψευδογλώσσα, στην οποία δεχόμαστε πως ο ορισμός πίνακα δεν μπορεί να γίνεται κατά την "εκτέλεσή" της. (για να γλιτώσουμε από χειρότερα κακά)
Και η οποία, σημειωτέον, δεν είναι υπαρκτή ούτε πραγματική  (τώρα, το ποια είναι η χρησιμότητά της αρχίζει πλέον να με απασχολεί πάρα πολύ έντονα - θα αναπτύξω σκέψεις αλλού - πιθανότατα να έχει ξανασυζητηθεί βέβαια)

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

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

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

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

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

Α, και να μην ξεχάσω : Θωμά συγχαρητήριά για την καταπληκτική εργασία/διατριβή   είναι σούπερ!!
(εννοώ αυτό https://alkisg.mysch.gr/steki/index.php?topic=2953.msg29561#msg29561

[alkisg]

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

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

• Δημιουργία σε O(f(ram)) - εννοώ ότι συνήθως εξαρτάται από το μέγεθος της διαθέσιμης μνήμης και όχι από το μέγεθος του πίνακα.
• Καταστροφή επίσης σε Ο(f(ram)).
• Προσπέλαση στοιχείου σε O(1).
• Μετακίνηση ή αλλαγή μεγέθους του πίνακα σε Ο(n).

Άρα, δεν μπορούμε να θεωρήσουμε ισοδύναμους τους πίνακες της javascript και τα associative arrays της perl και της python με τους πίνακες των αλγορίθμων, αφού δεν έχουν εγγυημένη προσπέλαση σε Ο(1). Δεν θα χρησιμοποιούσα λοιπόν παραδείγματα από αυτές τις γλώσσες σε παραλληλισμό με αλγορίθμους, αφού η πολυπλοκότητα ενός προγράμματος javascript που χρησιμοποιεί πίνακες δεν είναι η ίδια με την πολυπλοκότητα ενός αλγορίθμου που χρησιμοποιεί πίνακες.

Επίσης, το παράδειγμα με τα συνεχή resize που έδωσε ο Ευριπίδης, θέλει O(n) λόγω του resize του πίνακα στο εσωτερικό της επανάληψης. Επομένως, σαν λύση, είναι χειρότερη από κάποια που δουλεύει σε Ο(1) και δεν θα τη διάλεγε κάποιος που ενδιαφέρεται για την πολυπλοκότητα ή τις ανάγκες σε RAM του αλγορίθμου του.

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

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

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

Χμ... διορθώνω λίγο το παραπάνω...:

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

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

ΔΙΑΔΙΚΑΣΙΑ αβγ(Ν)
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Ν, Α[Ν]
...
ΑΡΧΗ
...

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

[mixman66]

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

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

[gpapargi]

Είσαι χρόνια μπροστά!!! 

Παπαργύρης, Ντζιος, Merlin, Βραχνός -> Στατικοί πίνακες σημαίνει γνωστό μέγεθος κατά τη μεταγλώττιση. ΜΟΝΟ!...:-) Σωστά;
Και πως δικαιολογούνται τα αδικαιολόγητα παραδείγματα του βιβλίου ρε παιδιά; Ειδικά αυτό με τη δύναμη είναι all the money...

Όχι δεν είναι αυτό η στατικότητα. Αυτό είναι που λέει το βιβλίο και δεν είναι σωστό. Στη C επιτρέπεται κατά την εκτέλεση να γνωστοποιηθεί το μέγεθος και πάλι ο πίνακας να είναι στατικός. Θα σχολιάσω αναλυτικά τα 2 παραδείγματα που ανέφερε ο Βαγγέλης  (ύψωση σε δύναμη και αραιοί) σε επόμενο post. Θεωρώ ότι δεν υπάρχει ασάφεια.  Το θέμα είναι να καταλάβουμε πως λειτουργεί το Δεδομένα //α//

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

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

Γιώργο αυτό που λες (ή πας να πεις) νομίζω έχει σχέση με αυτό που προσπαθώ να αναπτύξω στο παραπάνω μήνυμά μου και στο https://alkisg.mysch.gr/steki/index.php?topic=2953.msg29311#msg29311 για τα Δεδομένα // // .  Τι λες; Θα ήθελα τη γνώμη σου...