Συγχωρέστε μου το crosspost, αντιλαμβάνομαι ότι το παρακάτω μήνυμα δεν ταιριάζει στη ροή της συζήτησης, αλλά πιστεύω ότι κάτι έχει να προσθέσει. Ήδη ο gpapargi μου έχει απαντήσει (κι εγώ σ' αυτόν) στο γνωστό τεράστιο thread!
Εκτός από τους βασικούς τύπους δεδομένων, οι περισσότερες γλώσσες προγραμματισμού διαθέτουν και δομημένους τύπους δεδομένων. Από τους πιο συνηθισμένους αυτούς τύπους δεδομένων είναι ο πίνακας. Αλλά ποιος είναι ο ορισμός του πίνακα; Η πιο συνηθισμένη απάντηση στο ερώτημα αυτό είναι ότι: "ο πίνακας είναι ένα σύνολο διαδοχικών θέσεων μνήμης". Από την απάντηση αυτή αντιλαμβάνεται κανείς τη σύγχυση που υπάρχει μεταξύ μιας δομής δεδομένων και της παράστασής της. Είναι γεγονός ότι οι πίνακες σχεδόν πάντα υλοποιούνται σε διαδοχικές θέσεις μνήμης, αλλά αυτό δε σημαίνει ότι δε θα μπορούσε να αρθεί ο περιορισμός αυτός. Υιοθετώντας την προσέγγιση του Αφηρημένου Τύπου Δεδομένων για τη μελέτη του πίνακα θα πρέπει να καταρχήν να δοθεί ο ορισμός του.
Ορισμός: Ένας πίνακας είναι μια συλλογή στοιχείων του ιδίου τύπου και ένα σύνολο δεικτών.
Οι βασικές πράξεις του ΑΤΔ πίνακα είναι:
1. Δημιουργία: Δημιουργεί ένα κενό πίνακα.
2. Καταχώρηση: Η πράξη αυτή ορίζει μια απεικόνιση από το σύνολο των δεικτών στο σύνολο των στοιχείων. Δέχεται ως δεδομένα το όνομα του πίνακα, μαι τιμή για το δείκτη (ή τους δείκτες) και μια τιμή ενός στοιχείου του.
3. Ανάκτηση: Η πράξη αυτή χρησιμοποιεί την παραπάνω απεικόνιση. Δέχεται ως δεδομένα ένα πίνακα και ένα δείκτη (ή ένα σύνολο δεικτών) και επιστρέφει την πιο πρόσφατη τιμή του στοιχείου που καταχωρήθηκε, ή λάθος.
Διαπιστώνουμε, λοιπόν, ότι ένας πίνακας είναι μια απεικόνιση με την κανονική μαθηματική έννοια, όπου η απεικόνιση αυτή ολοκληρώνεται όταν η πράξη της καταχώρησης έχει εκτελεστεί για κάθε τιμή του σύνολου των δεικτών. Η πράξη της δημιουργίας πραγματοποιείται, από πλευράς προγραμματισμού, στις δηλώσεις του προγράμματος.
Δομές Δεδομένων, Νικόλαος Μισυρλής, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών 1993
Από την πρώτη στιγμή που διάβασα το επιχείρημα ότι ο πίνακας είναι μια στατική δομή δεδομένων και γι' αυτό δεν μπορεί να λυθεί το συγκεκριμένο πρόβλημα του θέματος Γ με πίνακες κάτι μ' ενοχλούσε διαισθητικά, αλλά δεν μπορούσα να το εντοπίσω. Χρειάστηκε να καταφύγω στις πανεπιστημιακές σημειώσεις μου για να μπορέσω να το περιορίσω.
Όπως έχουν γράψει τόσοι και τόσοι εδώ μέσα, η ψευδογλώσσα είναι ένα βοηθητικό εργαλείο με πολλές ασάφειες που υπάρχει για να διευκολυνθεί αυτός που θέλει να διατυπώσει έναν αλγόριθμο με περισσότερη σαφήνεια από τη φυσική γλώσσα, ούτως ώστε να μην παραβαίνει κάποιο από τα κριτήρια των αλγορίθμων.
Με αυτή τη λογική, και με βάση αυτά που μάθαμε στο πανεπιστήμιο και μας δίδαξε η εμπειρία, οι πίνακες στην ψευδογλώσσα είναι ένας Αφηρημένος Τύπος Δεδομένων, ένα μαθηματικό μοντέλο, ένας τρόπος οργάνωσης των δεδομένων μας σε μια μαθηματική απεικόνιση που έχει έναν δείκτη για κάθε δεδομένο. Απ' αυτήν την άποψη, ειλικρινά δεν μπορώ να βρω κανένα επιστημονικό λάθος στο να φτιάξουμε αλγορίθμους που χρησιμοποιούν εκατομμύρια, ή δισεκατομμύρια ή τρισεκατομμύρια στοιχεία. Μπορεί ο αλγόριθμος να είναι ένας κακός αλγόριθμος, αλλά για να τον απορρίψουμε, θα πρέπει -ορθώς- να επικαλεστούμε την απόδοση του αλγορίθμου.
Έτσι, για παράδειγμα, στην υπόθεση ότι έχουμε έναν πίνακα με 6 δισεκατομμύρια στοιχεία, άρα χωράει όλο τον ανθρώπινο πληθυσμό, άρα μπορούμε να διαβάσουμε τους λιγοστούς μαθητές που συμμετέχουν στο διαγωνισμό, ειλικρινά, δε βλέπω κανένα λογικό πρόβλημα. Ναι, ο αλγόριθμος είναι αναποτελεσματικός, ναι αν πάω να τον υλοποιήσω σε μια από τις βασικές γλώσσες προγραμματισμού θα βρεθώ αντιμέτωπος με τον περιορισμό ότι το index του πίνακα (ακόμα κι αν έχω τεράστια μνήμη RAM) με περιορίζει στις 65000 τόσες θέσεις. Αν όμως, πήγαινα να υλοποιήσω τον αλγόριθμο σε κάποια υπαρκτή γλώσσα προγραμματισμού, πιθανότατα να (α) να μην είχα πρόβλημα και με μικρό πίνακα όπως έχουν ήδη εξηγήσει άλλοι συνάδελφοι βασισμένοι στο χώρο του προβλήματος ή (β) να χρησιμοποιούσα μια άλλη δομή δεδομένων, π.χ. δυναμικό πίνακα, συνδεδεμένη λίστα, αρχείο στο δίσκο κλπ, κλπ. Ο αλγόριθμος όμως, σε ψευδογλώσσα, που κάνει χρήση πίνακα, δεν έχει κανένα λογικό λάθος.
(Να κάνω μια μικρή παρένθεση εδώ, για τις μομφές συναδέλφων του στυλ "τι σόι καθηγητές είστε εσείς να διδάσκετε τέτοια πράγματα στους μαθητές σας". Για μένα το βιβλίο δεν είναι ιερό κείμενο, δεν είναι ευαγγέλιο. Έχω την επιστημονική μου κατάρτιση και την πείρα μου ως προγραμματιστής και σ' αυτά καταφεύγω για να διδάξω τους μαθητές μου. Έτσι, όταν με ρωτάνε γιατί να μην κάνω αυτή την άσκηση με πίνακα, καταφεύγω σε επιχειρήματα που έχουν να κάνουν με την απόδοση του αλγορίθμου, έστω κι αν είναι εκτός ύλης. Τα παιδιά μπορούν να καταλάβουν τη διαφορά.)
Κι εδώ αναμασιέται το επιχείρημα περί συντέλειας του κόσμου μαθήματος διότι "αν είναι να λύνουμε όλες τις ασκήσεις με πίνακες, πώς θα διδάξουμε το μάθημα". Αυτό κύριοι συνάδελφοι, δεν είναι επιστημονικό επιχείρημα. Θεολογικό, υπαρξιακό, παιδαγωγικό, φιλοσοφικό ή ό,τι άλλο θέλετε, ίσως. Επιστημονικό όμως, δεν είναι! Μου θυμίζει την αντίδραση των θρησκόληπτων, ότι δεν μπορεί να είναι σωστή η Θεωρία της Εξέλιξης, γιατί αυτό θα σήμαινε ότι καταγόμαστε απ' τις μαϊμούδες και αυτό δεν μπορεί να γίνει αποδεκτό αφού μας έπλασε ο Κύριος. Κυκλικός, λαθεμένος συλλογισμός. Μη πέσουμε στην ίδια παγίδα.
Συνεπώς, ναι, τίθεται ένα σοβαρό εκπαιδευτικό πρόβλημα. Με δεδομένες τις ασάφειες της ψευδογλώσσας και τις αντιφάσεις του βιβλίου, πώς διδάσκουμε λύση ασκήσεων χωρίς πίνακα;
Πρώτα απ' όλα, δε νομίζω ότι ήρθε η συντέλεια του κόσμου μαθήματος. Π.χ. δε νομίζω ότι μπορούμε να φτιάξουμε αλγόριθμο που να χρησιμοποιεί πίνακα για να υπολογίσει τα ψηφία του π. Δεν έχει άνω όριο το μέγεθος ενός τέτοιου πίνακα, όσο παράλογα μεγάλα μεγέθη κι αν σκεφτούμε. Χώρος, λοιπόν, για έξυπνες ασκήσεις που δείχνουν τις αρετές της Δομής Επανάληψης υπάρχει. Ας μη φέρνουμε την καταστροφή.
Από κει και πέρα, αφού ενδιαφερόμαστε όλοι πραγματικά για το μάθημα, θα έπρεπε να απαιτήσουμε την απόσυρση του διδακτικού πακέτου με ένα νέο, πολύ πιο σαφές και αυστηρό. Μέχρι να γίνει αυτό, είμαι υπέρμαχος της άποψης ότι στην Τεχνολογική Κατεύθυνση της Γ' Λυκείου, θα έπρεπε να διδάσκουμε μόνο τη ΓΛΩΣΣΑ, αφού φροντίσουμε να την περάσουμε από έναν compiler ώστε να εξαλείψουμε και τις τελευταίες ασάφειές της.
Ας μη ξεχνάμε τον προορισμό του μαθήματος: Καλά όλα αυτά περί αλγοριθμικής σκέψεις, αλλά πρόκειται για μάθημα Κατεύθυνσης, όχι Γενικής Παιδείας, που πρωτίστως, έχει σκοπό να προετοιμάσει τους μελλοντικούς φοιτητές και σπουδαστές Πληροφορικής και Πολυτεχνείων για τη χρήση του προγραμματισμού μέσα στο πλαίσιο των σπουδών τους. Αν είναι να σχεδιάσουμε ένα μάθημα Γενικής Παιδείας με βάση τα πιθανά οφέλη της αλγοριθμικής σκέψης, έχω να πω δυο μόνο πράγματα: (α) ο μέσος πολίτης που ξέρει μαθηματικά έχει ήδη καλλιεργήσει την αλγοριθμική του σκέψη -θυμηθείτε μόνο την ετυμολογία της λέξης αλγόριθμος- και, (β) το τρέχον διδακτικό πακέτο -που είναι ούτως ή άλλως για τα σκουπίδια- θα πρέπει να αντικατασταθεί με ένα νέο εξ ολοκλήρου.