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

[alkisg]

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

Νομίζω ότι το έχουμε ξανασυζητήσει και είχαμε πει και τα σχετικά παραδείγματα των Fortan και C που το δέχονται. Μια χαρά τα λες.

Να πω όμως εδώ πάλι με άλλα λόγια ότι το συντακτικό δεν είναι σημαντικό και στην ψευδογλώσσα δεν (πρέπει να) μας ενδιαφέρει. Οι πίνακες είναι απλά μια δομή από το οπλοστάσιό μας από το οποίο κάθε φορά θα πρέπει να επιλέγουμε την καλύτερη ανάλογα με το πρόβλημά μας.
Αν θέλει κάποιος να κάνει resize τους πίνακες κατά την εκτέλεση, δικαίωμά του, εφόσον βέβαια του το επιτρέπει η γλώσσα του, ενώ ο ψευδοκώδικας (θα πρέπει να) τα επιτρέπει όλα. Απλά θα πρέπει να μετρήσει το κάθε resize στην τελική πολυπλοκότητα του προγράμματος. Όταν δει ότι το πρόγραμμά του χρειάζεται ένα μήνα για να εκτελεστεί ενώ μια καλύτερη υλοποίηση χρειάζεται ένα λεπτό, ε, θα πρέπει να συμπεράνει ότι το resize στους πίνακες είναι μη αποδοτικό (O(n)) και θα έπρεπε να είχε διαλέξει κάποια άλλη δομή (οι χρόνοι δεν είναι φανταστικοί, είναι από έναν διαγωνισμό που είχαμε κάνει στο experts-exchange σε Delphi για πρόσθεση strings == resize πινάκων).

Η πολυπλοκότητα είναι ο λόγος πίσω από όλα αυτά, όχι το συντακτικό.

[evry]

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

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

Ευχαριστώ γιώργο, καταραμένο i, το διόρθωσα

Άλκη τα associative arrays τα πρότεινα σαν αλγοριθμικό εργαλείο, δηλαδή θα έλυνε πολλά προβλήματα στην ψευδογλώσσα και θα ήταν πολύ καλή η αναπαράσταση του αλγορίθμου αν έλεγες π.χ.   Βαθμός["Μανόλης"] και εννοούσες ο βαθμός του Μανόλη και όχι ότι ο μαθητής με όνομα Ονομα[κ]="Μανόλης" έχει βαθμό Βαθμό[κ].

ΥΓ Αν θυμάσαι κάποτε είχαμε κάποια διαφωνία για την javascript , είχα πει ότι είναι λίγο "άρπα-κόλλα" γλώσσα και εσύ με είχες βάλει στη θέση μου.
Επειδή αυτόν τον καιρό για κάποιον λόγο ασχολήθηκα αρκετά με PHP/Javascript κατάλαβα  πόσο δίκιο είχες τότε (με βοήθησε και εκείνο το κορυφαίο tutorial που μου είχες υποδείξει )

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

Νομίζω ότι το έχουμε ξανασυζητήσει και είχαμε πει και τα σχετικά παραδείγματα των Fortan και C που το δέχονται. Μια χαρά τα λες.
......

Συνεχίζοντας το σκεπτικό μου, θα μπορούσε το θέμα Γ να υλοποιηθεί στη ΓΛΩΣΣΑ ως εξής:

Στο κύριο πρόγραμμα διαβάζει το πλήθος των αθλητών Ν και καλεί διαδικασία (με παράμετρο Ν) που θα κάνει όλα τα άλλα με τοπικούς πίνακες μεγέθους Ν!!!!! Έτσι έχουμε υλοποίηση σε ΓΛΩΣΣΑ, χωρίς παραβίαση της στατικότητας και χωρίς αυθαίρετα άνω όρια.... Δεν θα ήταν όλοι ευχαριστημένοι έτσι;   Άσε που αλγόριθμο ζήταγε!!!!!

[mixman66]

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

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

... αλγόριθμο ζήταγε!!!!!

!!!

[alkisg]

Άλκη τα associative arrays τα πρότεινα σαν αλγοριθμικό εργαλείο, δηλαδή θα έλυνε πολλά προβλήματα στην ψευδογλώσσα και θα ήταν πολύ καλή η αναπαράσταση του αλγορίθμου αν έλεγες π.χ.   Βαθμός["Μανόλης"] και εννοούσες ο βαθμός του Μανόλη και όχι ότι ο μαθητής με όνομα Ονομα[κ]="Μανόλης" έχει βαθμό Βαθμό[κ].

...και μετά ένας μαθητής θα έβγαινε και θα έλεγε:
"μα γιατί κύριε μας λέτε για σειριακές, δυαδικές αναζητήσεις και μας σπάτε τα νεύρα; απλά βάζω όλα τα strings σαν keys ενός associative array και το index σαν values, και έχω αναζήτηση σε O(1)!
...έχω τον πίνακα names[], και κάνω
for (ί = 0; i < length(names); i++)
    assoc[names[ί]] = ί
Αυτό λοιπόν το κάνω μια φορά, και στη συνέχεια κάνω αναζητήσεις σε Ο(1) απλά γράφοντας
    assoc[requested_name] ==> μου δίνει το index ί.
".

Άντε μετά να του εξηγήσεις ότι δεν πέτυχε αναζήτηση σε Ο(1) αλλά ότι από πίσω υπάρχουν hash tables και buckets και διάφορα άλλα.

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

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

[sstergou]

Περιμένω εναγωνίως να ακούσω τον ορισμό της στατικότητας του Γιώργου

Μέχρι τότε, δεν ξέρω αν ο 'Αλκης διάβασε τα προηγούμενα μηνύματα και αναφέρω :

Οι πίνακες που προτείνω είναι στατικοί.

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

Η προσπέλασή τους έχει πολυπλοκότητα Ο(1) όπως και στους υπάρχοντες.

Η μόνη διαφορά τους είναι ότι το μέγεθός τους ορίζεται ΜΙΑ φορά κατά είτε κατά την εκτέλεση είτε κατά την μεταγλώττιση και από κει και πέρα δεν αλλάζει.

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

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

Άλκη ποιο το πρόβλημα μιας τέτοιας δομής;

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

Το αν οι associative arrays (και γενικότερα οποιαδήποτε δομή υλοποιείται εσωτερικά με hash table ή άλλη δομή αναζήτησης) είναι χρήσιμες για την ψευδογλώσσα είναι μια άλλη κουβέντα.

[merlin]

Συνεχίζοντας το σκεπτικό μου, θα μπορούσε το θέμα Γ να υλοποιηθεί στη ΓΛΩΣΣΑ ως εξής:

Στο κύριο πρόγραμμα διαβάζει το πλήθος των αθλητών Ν και καλεί διαδικασία (με παράμετρο Ν) που θα κάνει όλα τα άλλα με τοπικούς πίνακες μεγέθους Ν!!!!! Έτσι έχουμε υλοποίηση σε ΓΛΩΣΣΑ, χωρίς παραβίαση της στατικότητας και χωρίς αυθαίρετα άνω όρια.... Δεν θα ήταν όλοι ευχαριστημένοι έτσι;   Άσε που αλγόριθμο ζήταγε!!!!!

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

Αλγόριθμος ΕίμαιΠολύΜπροστά
Διάβασε πλήθος
νέος αθλητής !κατά αντιστοιχία με το new athl (όπου athl ένα structure με πεδία το επίδοση και το επόμενοςΔείκτης)
ακολουθεί αρχικοποίηση λίστας, και για κάθε μια επίδοση ταξινόμηση κατά τα γνωστά με προσθήκη κόμβου εκεί που πρέπει, να μην τα γραφω κλπ κλπ

Φυσικά δεν θα έδινα σημασία αν την διεύθυνση μνήμης την απέδιδε με & ή %, το υποπεδίο με τελεία ή δεξί βελάκι, το τέλος της λίστας με NULL, NIL, κενό.

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

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

Για μένα, το συμβόλαιο είναι καθαρό και παρά το γεγονός ότι είναι περιοριστικό και "άχαρο", νομίζω ότι ακολουθείται πιστά στο βιβλίο. Γι' αυτό το λόγο ΑΠΟΦΕΥΓΟΝΤΑΙ να αναλυθούν συγκεκριμένα θέματα, να λυθεί έστω και μια άσκηση με διάβασε στην αρχή και χρησιμοποίηση πίνακα στη συνέχεια.
Ξέρετε, πολλές φορές θέλουμε να μάθουμε στα παιδιά να χρησιμοποιούν ΜΟΝΟ χειροπρίονο και να τους "κρύψουμε" το αλυσιδοπρίονο.

[jkapsi]

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

Αλγόριθμος ΕίμαιΠολύΜπροστά
Διάβασε πλήθος
νέος αθλητής !κατά αντιστοιχία με το new athl (όπου athl ένα structure με πεδία το επίδοση και το επόμενοςΔείκτης)
ακολουθεί αρχικοποίηση λίστας, και για κάθε μια επίδοση ταξινόμηση κατά τα γνωστά με προσθήκη κόμβου εκεί που πρέπει, να μην τα γραφω κλπ κλπ

Φυσικά δεν θα έδινα σημασία αν την διεύθυνση μνήμης την απέδιδε με & ή %, το υποπεδίο με τελεία ή δεξί βελάκι, το τέλος της λίστας με NULL, NIL, κενό.

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

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

Για μένα, το συμβόλαιο είναι καθαρό και παρά το γεγονός ότι είναι περιοριστικό και "άχαρο", νομίζω ότι ακολουθείται πιστά στο βιβλίο. Γι' αυτό το λόγο ΑΠΟΦΕΥΓΟΝΤΑΙ να αναλυθούν συγκεκριμένα θέματα, να λυθεί έστω και μια άσκηση με διάβασε στην αρχή και χρησιμοποίηση πίνακα στη συνέχεια.
Ξέρετε, πολλές φορές θέλουμε να μάθουμε στα παιδιά να χρησιμοποιούν ΜΟΝΟ χειροπρίονο και να τους "κρύψουμε" το αλυσιδοπρίονο.

Ας αλλάξει λοιπόν το βιβλίο να ησυχάσουμε όλοι.

Είτε να αφαιρεθούν τα παραδείγματα που δημιουργούν σύγχηση...
είτε να γίνεται να ορίζουμε στατικούς πίνακες τη στιγμή της εκτέλεσης (δεσμευσε Α[Ν] ή κάπως αλλιώς)

Συμφωνείτε;
Το πιο σημαντικό είναι να εξαφανιστούν οι ασάφειες!

[evry]

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

Άλκη έχεις δίκιο σε αυτό που λες με τα associative arrays, τελικά από ότι φαίνεται η λύση είναι να μπει η πολυπλοκότητα στο μάθημα σε διασθητικό πάντα επίπεδο και εφόσον το μάθημα κατέβει και μια τάξη. Έτσι θα ξεκαθαρίσουν πολλά πράγματα και θα είμαστε και συνεπείς επιστημονικά.

@merlin συμφωνώ απόλυτα μαζί σου, να ξαναθυμίσω ότι μου έτυχε παρόμοια λύση μαθητή στο θέμα Γ5 σε ελεύθερο κείμενο!!!

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

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

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

[sstergou]

Συμφωνείτε;
Το πιο σημαντικό είναι να εξαφανιστούν οι ασάφειες!

Αυτό είναι αυτονόητο συνάδελφε. Εννοείται συμφωνώ.

[gthal]

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

Τι πλεονεκτήματα μπορεί να έχει Στάθη; Πού το ανέφερες;

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

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

[evry]

Το παράδειγμα αυτό δεν είναι το ίδιο με το να διαβάσεις το μέγεθος, αυτό είναι πιο Light. Στο παράδειγμα αυτό έχουμε έναν δυναμικό πίνακα, ο οποίος δεν φαίνεται με μια πρώτη ματιά να έχει κάποιο πάνω όριο.
   Το πάνω όριο εξαρτάται από την είσοδο του αλγορίθμου και με μια πρόχειρη ματιά πρέπει να είναι log του b με βάση a. Το όριο είναι πιο κάτω αλλά αυτό είναι σίγουρα το μεγαλύτερο δυνατό.

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

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

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

[sstergou]

Τα ξαναγράφω και προσθέτω μερικά ακόμη:

1) Κατάργηση των άνω ορίων (τα οποία είναι δούρειος ίππος)
2) Οι ασκήσεις με άγνωστο πλήθος στοιχείων δεν λύνονται με πίνακες (δεν υπάρχουν άνω όρια)
3) Τμηματικός προγραμματισμός που έχει νόημα
4) Απαλείφονται οι παρερμηνείες και τα προβλήματα από τα παραδείγματα του βιβλίου
5) Συμβαδίζουμε με την πληροφορική και χρησιμοποιούμε σωστά τον όρο στατική δομή
6) Ξεκάθαρη αντιμετώπιση στο θέμα των πινάκων
7) Ο(1) στην προσπέλαση και γενικά διατήρηση της ήδη υπάρχουσας συμπεριφοράς.

Πάρτε κόσμε, σε πολύ καλή τιμή, τα καλύτερα και τα φθηνότερα. 

Τα είχα αναφέρει εδώ :
https://alkisg.mysch.gr/steki/index.php?topic=2953.msg29581#msg29581

[evry]

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

Τα ξαναγράφω και προσθέτω μερικά ακόμη:

1) Κατάργηση των άνω ορίων (τα οποία είναι δούρειος ίππος)
2) Οι ασκήσεις με άγνωστο πλήθος στοιχείων δεν λύνονται με πίνακες (δεν υπάρχουν άνω όρια)
3) Τμηματικός προγραμματισμός που έχει νόημα
4) Απαλείφονται οι παρερμηνείες και τα προβλήματα από τα παραδείγματα του βιβλίου
5) Συμβαδίζουμε με την πληροφορική και χρησιμοποιούμε σωστά τον όρο στατική δομή
6) Ξεκάθαρη αντιμετώπιση στο θέμα των πινάκων
7) Ο(1) στην προσπέλαση και γενικά διατήρηση της ήδη υπάρχουσας συμπεριφοράς.

Πάρτε κόσμε, σε πολύ καλή τιμή, τα καλύτερα και τα φθηνότερα. 

Τα είχα αναφέρει εδώ :
https://alkisg.mysch.gr/steki/index.php?topic=2953.msg29581#msg29581