Θέμα: Θέμα Α

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

μου ορίζεις το επιστημονικά αποδεκτός?

Αν "τρέξω" τον κώδικα και κάνω αντικατάσταση το i σε κάθε επανάληψη, αντιμετατίθενται τα σωστά στοιχεία

Αν το "τρέξω" σημαίνει εκτέλεση με χαρτί και μολύβι, μιας και μιλάμε για αλγορίθμους καλύπτεται και το κριτήριο της αποτελεσματικότητας, άρα επιστημονικά αποδεκτό. Άλλη μία γκρίζα ζώνη που δεν την ακουμπάει κανείς. Όμως φαντάζομαι δεν αμφισβητεί κανείς την επιστημονικότητα του Knuth ο οποίος έθεσε το συγκεκριμένο κριτήριο. (http://en.wikipedia.org/wiki/Algorithm_characterizations#1968.2C_1973_Knuth.27s_characterization)

[evry]

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

Αν το "τρέξω" σημαίνει εκτέλεση με χαρτί και μολύβι, μιας και μιλάμε για αλγορίθμους καλύπτεται και το κριτήριο της αποτελεσματικότητας, άρα επιστημονικά αποδεκτό. Άλλη μία γκρίζα ζώνη που δεν την ακουμπάει κανείς. Όμως φαντάζομαι δεν αμφισβητεί κανείς την επιστημονικότητα του Knuth ο οποίος έθεσε το συγκεκριμένο κριτήριο. (http://en.wikipedia.org/wiki/Algorithm_characterizations#1968.2C_1973_Knuth.27s_characterization)

Για αυτό υπάρχει η απόδειξη η οποία όμως δεν είναι στην ύλη μας.

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

Ο Knuth τον οποίο ανέφερες δε μιλάει για κριτήρια αλλά για features, δηλαδή χαρακτηριστικά. δεν είναι το ίδιο. Μπορεί στο μάθημα μας να τα λέμε κριτήρια αλλά αυτό είναι λάθος διότι οι συγγραφείς έχουν μεταφράσει λάθος το feature σε κριτήριο.
Για παράδειγμα στον αρχικό αυστηρό ορισμό του αλγορίθμου στο βιβλίο του o Knuth δεν συμπεριλαμβάνει την αποτελεσματικότητα. Με βάση αυτόν τον ορισμό υπάρχουν αλγόριθμοι που δεν πληρούν το "κριτήριο" της αποτελεσματικότητας, όπως αναφέρει και ο ίδιος ο Knuth στο βιβλίο του.

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

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

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

Ο Knuth τον οποίο ανέφερες δε μιλάει για κριτήρια αλλά για features, δηλαδή χαρακτηριστικά. δεν είναι το ίδιο. Μπορεί στο μάθημα μας να τα λέμε κριτήρια αλλά αυτό είναι λάθος διότι οι συγγραφείς έχουν μεταφράσει λάθος το feature σε κριτήριο.
Για παράδειγμα στον αρχικό αυστηρό ορισμό του αλγορίθμου στο βιβλίο του o Knuth δεν συμπεριλαμβάνει την αποτελεσματικότητα. Με βάση αυτόν τον ορισμό υπάρχουν αλγόριθμοι που δεν πληρούν το "κριτήριο" της αποτελεσματικότητας, όπως αναφέρει και ο ίδιος ο Knuth στο βιβλίο του.

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

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

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

[PE19]

προς βαθμολογητές:
στο Α2, πόσες μονάδες θα δίνατε στην απάντηση:

ΧΑΡΑΚΤΗΡΑΣ                 ΑΛΗΘΗΣ (αλφαριθμητική)
ΠΡΑΓΜΑΤΙΚΟΣ               -2 (πραγματικός)
ΛΟΓΙΚΟΣ                        ΑΛΗΘΗΣ (λογική)
ΛΟΓΙΚΟΣ                        ΨΕΥΔΗΣ (λογικη)
ΑΚΕΡΑΙΟΣ                       4 (ακέραιος)

[andreas_p]

Όλες !

[anasta]

Γιατί να γίνει έτσι όπως το γράφεις και όχι έτσι;
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ 5
   Β <-- Α [ A[ Ι ] ]
   Α [ A [ Ι ] ] <-- Α [ Ι ]
   Α [ Ι ] <-- Β
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

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

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

[merlin]

είτε το γράψεις έτσι, είτε αλλιώς ΔΕΝ δουλεύει.
μόνο με διαδικασία δουλεύει κ μόνο για τον συγκεκριμένο πίνακα.
.....

Κοίταξέ το λίγο καλύτερα, δουλεύει μια χαρά έτσι. Παίζει ρόλο η σειρά.

[elf]

Και μια και μιλαμε για επιστημονικά αποδεκτές λύσεις. Σε ένα γραπτό με πολύ μικρή βαθμολογία βλέπω για λύση στο Α3α:
Α[3] <- 3 + Α[..]    3+3 = 6 άρα  6
Α[9] <- Α[..] -2      9-2 = 7 κοκ στα επόμενα 2.
Προφανώς δεν μπορεί να προσθέτει δείκτες και περιεχόμενο, αλλά έχω μείνει να το κοιτάω γιατί βγαίνει σωστό!!!
Και βγαίνει πάντα σωστό γιατί περιεχόμενο του Α[ x ]   είναι ή πρέπει να γίνει 11-x, οπότε μετά την εκτέλεση της εντολής
Α[ m ] <- A[ x ] +/- n
   θα ισχύει
11- m = 11 -x +/- n, δηλαδή  x = m +/- n
Εσείς θα το δεχόσασταν ως σωστό;;

[evry]

Τελικά από ότι μου έχουν πει οι συνάδελφοι που βαθμολογούν η λύση που έχει εμφανιστεί σε 3-4 γραπτά (από 1500) είναι

Για i από 1 μέχρι 5
    Αντιμετάθεσε Α[6-i],  A[5+i]
ΤΕ

Ξεκινάει τις αντιμεταθέσεις από μέσα προς τα έξω

[Καρκαμάνης Γεώργιος]

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

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

Τι να πώ, τελικά η λέξη "περιεχόμενο" ήταν μάλλον άγνωστη για τα παιδιά.