Θέμα: Θεμα Γ χρηση πινακων απολυτα σωστη !!!

[Άρης Κεσογλίδης]

(Εντάξει, έβαλα κενά πριν και μετά το i )

[evry]

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

Όπως επίσης για αναζήτηση, αν γίνει με ΟΣΟ ή με ΓΙΑ.
Δηλαδή αν θέλει να κάνει ένας μαθητής αναζήτηση και γράψει:

done ←  Ψευδής
ΓΙΑ  i  ΑΠΟ  1  ΜΕΧΡΙ  ν
      ΑΝ  Α[ i ] = Κey  ΤΟΤΕ
            done ← Αληθής
      ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΠΟΤΕΛΕΣΜΑΤΑ //done//

..είναι επιστημονικά τεκμηριωμένη λύση; Ναι.
Θα κάνει περισσότερη ώρα να φτάσει στο αποτέλεσμα.
Εδώ κόβουν μονάδες, ναι ή όχι;

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

[pgrontas]

.

Ωραία...και στο βιβλίο επίσης λέει (αλλά κυρίως το λέει η ΛΟΓΙΚΗ) ότι μαθαίνουμε να χρησιμοποιούμε πίνακες για να έχουμε τα δεδομένα αποθηκευμένα και να τα ξαναχρησιμοποιήσουμε όποτε θέλουμε.
Δηλαδή πόσο πιθανό είναι να κάνατε μία εφαρμογή για να κρατάτε στατιστικά στοιχεία και με το που εισάγατε τα στοιχεία μετά την εκτέλεση χάνονταν;; ΚΑΘΟΛΟΥ ΠΙΘΑΝΟ.

Όπως και το 2010 μιλούσαμε για σχολικούς αγώνες, ΚΛΑΣΣΙΚΗ περίπτωση για να κρατήσεις τα στοιχεία, γιατί όποιος έχει να κάνει το πρόγραμμα για σχολικούς αγώνες θα ξέρει από την αρχή πόσοι θα συμμετέχουν.

Όπως και εδώ με την αγορά των προϊόντων δεν θα πάρει κανένας ούτε 1000 προϊόντα ούτε 10000 και τέτοια...

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

Όπως επίσης για αναζήτηση, αν γίνει με ΟΣΟ ή με ΓΙΑ.

Δηλαδή αν θέλει να κάνει ένας μαθητής αναζήτηση και γράψει:

done ←  Ψευδής
ΓΙΑ  i  ΑΠΟ  1  ΜΕΧΡΙ  ν
      ΑΝ  Α[ i ] = Κey  ΤΟΤΕ
            done ← Αληθής
      ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΠΟΤΕΛΕΣΜΑΤΑ //done//

..είναι επιστημονικά τεκμηριωμένη λύση; Ναι.
Θα κάνει περισσότερη ώρα να φτάσει στο αποτέλεσμα.
Εδώ κόβουν μονάδες, ναι ή όχι;

Στο συγκεκριμένο έχεις κάποιο δίκιο. Διαισθητικά όλοι ξέρουμε ότι ο αλγόριθμος με την ΓΙΑ είναι πιο 'κακός' από τον αλγόριθμο με την ΟΣΟ, στην περίπτωση με το πολύ μία εμφάνιση κάθε στοιχείου. Όμως και ο Ευριπίδης έχει δίκιο όταν λέει ότι η απόδοση τους είναι ίδια.

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

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

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

[Άρης Κεσογλίδης]

@ Evry: Δεν καταλαβαίνω τι εννοείς "να τον τεκμηριώσω επιστημονικά τον αλγόριθμο".
Το κομμάτι που κάνει αναζήτηση με ΓΙΑ ξέρουμε ότι μας κάνει τη δουλειά.

Επομένως αν έχουμε έναν πίνακα με 1000 στοιχεία και κάνουμε αναζήτηση με ΓΙΑ, μπορεί να υπάρχει το στοιχείο π.χ. στις 100 πρώτες θέσεις και να κάνουμε 900 περιττές επαναλήψεις.

Αν ένας πελάτης αγοράσει 100 προϊόντα στο Θέμα 4, και εμείς δημιουργήσουμε έναν πίνακα (ΑΝ ήταν σε ΓΛΩΣΣΑ) με 1000 στοιχεία, θα δεσμεύαμε 900 θέσεις περισσότερες στη μνήμη.

Γιατί το 2ο μας πειράζει και το 1ο δεν μας πειράζει;
Αυτό ρωτάω εγώ. Άσχετα με τάξεις μεγέθους απόδοσης και πολυπλοκότητες.

Διδάσκουμε στα παιδιά τον Δομημένο Προγραμματισμό και στο κεφάλαιο 10, που στην ουσία εκεί θέλουμε να φτάσουμε, όπως το καταλαβαίνω εγώ...τον ΤΜΗΜΑΤΙΚΟ Προγραμματισμό.
Με πλεονεκτήματα της πιο εύκολης ανάπτυξης του αλγορίθμου και το Προγράμματος, πιο εύκολο στην κατανόηση και στην διόρθωση των λαθών.

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

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

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

[itt]

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

Mα δεν σε ενδιαφέρει εσένα που γράφεις τον αλγόριθμο σε ψευδοκώδικα πώς υλοποιεί η δομή το interface. Αυτό προσπαθώ να πω. Ο στατικός πίνακας δεν θα δουλεύει ακόμα και εαν υλοποιεί το interface, όπως δεν δουλεύει το απλό dictionary σε multithreaded κώδικα και ας υλοποιεί το interface.  Το πρόβλημα που προκύπτει είναι όταν πας να μεταφράσεις τον ψευδοκώδικα σε μια γλώσσα όπου δεν υπάρχουν dynamic memory allocation semantics, οπότε και είναι αδύνατο να λειτουργήσει ο ψευδοκώδικας. Αυτό που κάνουμε όμως είναι να ανεβάζουμε στο abstracted layer του ψευδοκώδικα, ανησυχίες που δεν θα έπρεπε να υπάρχουν εκεί.

Όμως από την άλλη έγραψες αυτό

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

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

To αστείο της υπόθεσης είναι , ότι ειδικά στην άσκηση του '10,  το να χρησιμοποιείς πίνακα, είναι πολύ πιο κοντά στο optimization που κάνει κάποιος σε τέτοιες περιπτώσεις στην πραγματικότητα.

[Άρης Κεσογλίδης]

To αστείο της υπόθεσης είναι , ότι ειδικά στην άσκηση του '10,  το να χρησιμοποιείς πίνακα, είναι πολύ πιο κοντά στο optimization που κάνει κάποιος σε τέτοιες περιπτώσεις στην πραγματικότητα.

Αυτό ακριβώς.

[evry]

Τι εννοείς?
η λύση με πίνακες είχε πολυπλοκότητα Ο(n^2) ενώ χωρίς πίνακες είχε Ο(n).
Χρησιμοποιείς σε τέτοιες περιπτώσεις πίνακα όταν έχεις καλύτερη πολυπλοκότητα όχι για να τα κάνεις χειρότερα.

To αστείο της υπόθεσης είναι , ότι ειδικά στην άσκηση του '10,  το να χρησιμοποιείς πίνακα, είναι πολύ πιο κοντά στο optimization που κάνει κάποιος σε τέτοιες περιπτώσεις στην πραγματικότητα.

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

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

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

Επίσης αυτό που λες με το Interface δε συμφωνώ καθόλου. Όταν χρησιμοποιείς ένα interface αυτό έχει καποια specifications. Αν ανάλογα με την υλοποίηση αλλάζουν τα specifications (γεμίζει ο πίνακας και κρεμάει) τότε κάτι δεν πάει καλά.

[evry]

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

@ Evry: Δεν καταλαβαίνω τι εννοείς "να τον τεκμηριώσω επιστημονικά τον αλγόριθμο".
Το κομμάτι που κάνει αναζήτηση με ΓΙΑ ξέρουμε ότι μας κάνει τη δουλειά.

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

ΥΓ. Παρεμπιπτόντως έστειλαν οδηγία για το Β2. Όλες οι λύσεις σωστές, όπως πάντα άλλωστε.

[Άρης Κεσογλίδης]

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

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

[Αθανάσιος Πέρδος]

η λύση με πίνακες είχε πολυπλοκότητα Ο(n^2) ενώ χωρίς πίνακες είχε Ο(n).
Χρησιμοποιείς σε τέτοιες περιπτώσεις πίνακα όταν έχεις καλύτερη πολυπλοκότητα όχι για να τα κάνεις χειρότερα.

Από που προκύπτει ακριβώς αυτό;

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

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

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

[evry]

Νάσο μιλάω για το θέμα Γ του 2010.
Στη μια περίπτωση έβρισκες τη θέση ενώ τα διάβαζες άρα πολυπλοκότητα O(n)
ενώ στη δεύτερη έκανες πρώτα ταξινόμηση και μετά αναζήτηση, άρα πολυπλοκότητα O(n^2+n) = O(n^2)

Από που προκύπτει ακριβώς αυτό;

[evry]

Δηλαδή εσύ μπορεί να διαφωνείς και με την ταξινόμηση της φυσαλίδας, έτσι όπως τα λες.

Ναι διαφωνώ, απόδειξέ μου ότι δουλεύει

Δηλαδή δεν είναι τίποτα επιστημονικά τεκμηριωμένο;

Αν δεν το αποδείξεις, όχι δεν είναι

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

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

[Άρης Κεσογλίδης]

@Evry.

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

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

Διαφωνείς με τη φυσαλίδα, διαφωνείς με όλα όσα διδάσκεις... Στους μαθητές σου τι λες;
"Αυτός είναι ο τρόπος ταξινόμησης της φυσαλίδας. Δεν είναι επιστημονικά τεκμηριωμένος, αλλά εσείς θα το μάθετε";

Τι γίνεται στον Προγραμματισμό, "πειραματική παρατήρηση" και "εικασία" για το ότι ισχύει , χωρίς να μπορούμε να το τεκμηριώσουμε; Τι απαντάς στον μαθητή που σε ρωτάει;

[Αθανάσιος Πέρδος]

Νάσο μιλάω για το θέμα Γ του 2010.
Στη μια περίπτωση έβρισκες τη θέση ενώ τα διάβαζες άρα πολυπλοκότητα O(n)
ενώ στη δεύτερη έκανες πρώτα ταξινόμηση και μετά αναζήτηση, άρα πολυπλοκότητα O(n^2+n) = O(n^2)

Δεν ήταν υποχρεωτικό να κάνεις ταξινόμηση. Με μια μόνο αναζήτηση αν κρατούσες αρχικά την επίδοση του πρωταθλητή μετρούσες πόσοι ήταν καλύτεροι οπότε η θέση του ήταν η τιμή του μετρητή + 1 άρα πολυπλοκότητα Ο(n).

Για μένα η χρήση πίνακα για την αποθήκευση όλων των δεδομένων στο συγκεκριμένο θέμα είναι επιτρεπτή ή όχι από την ερμηνεία που δίνει κάποιος στα γραφόμενα της σελίδας 56. Όλα τα άλλα είναι απλά για να συζητάμε.     

[evry]

ναι βρε Νάσο, αυτή ήταν η πρώτη λύση με πολυπλοκότητα Ο(n), αυτό λέω
όλοι όσοι πήραν πίνακες, επέλεξαν αυτό τον δρόμο για να κάνουν ταξινόμηση, άρα O(n^2)
Αυτοί που έκαναν την έξυπνη σκέψη που λες δεν χρειάστηκε να πάρουν πίνακες.

Δεν ήταν υποχρεωτικό να κάνεις ταξινόμηση. Με μια μόνο αναζήτηση αν κρατούσες αρχικά την επίδοση του πρωταθλητή μετρούσες πόσοι ήταν καλύτεροι οπότε η θέση του ήταν η τιμή του μετρητή + 1 άρα πολυπλοκότητα Ο(n).