Γενικό Λύκειο > Ταξινόμηση

Απορία βαθμολόγησης στην ταξινόμηση

(1/8) > >>

chzisi:
Πως θα βαθμολογούσατε ένα ερώτημα 3ου θέματος στο οποίο απαιτείται η χρήση ταξινόμησης για την εύρεση της απάντησης, και η ταξινόμηση δίνεται από το μαθητή με την εξής μορφη:
Για ι από 2 μέχρι 20
   Για j από 20 μέχρι 2 με βήμα -1
..... (σωστό όλο το παρακάτω)

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

Laertis:
Πόσο πιάνει όλο το θέμα ; Εγώ δε θα έδινα όλες τις μονάδες, μόνο και μόνο επειδή δουλεύει. Είναι που είναι αργή η ταξινόμηση φυσσαλίδας...

evry:
Από την στιγμή που η απόδοση είναι εκτός ύλης δε νομίζω ότι δικαιούμαστε να κόψουμε. Από εκεί και πέρα ακόμα και να θέλαμε να κόψουμε πάλι δεν θα μπορούσαμε γιατί η διαφορά στην απόδοση δεν είναι τόσο μεγάλη. Δηλαδή στον αργό αλγόριθμο η συνάρτηση πολυπλοκότητας είναι T(N) = N*(N-1) = N^2 - N = O(N^2) ενώ στην γρήγορη έκδοση είναι πάλι T(N) = N*(N+1)/2 = O(N^2). Δηλαδή ναι μεν είναι πιο αργή αλλά δεν είναι τόσο πιο αργή ώστε να κόψουμε, η πολυπλοκότητα είναι η ίδια. Δεν είναι το ίδιο π.χ. με  την εύρεση μεγίστου με ταξινόμηση.

Φυσικά υπάρχει και ένα άλλο σημαντικό θέμα: Αυτοί/ες που χρησιμοποιούν την "σωστή" έκδοση με το i έχουν καταλάβει γιατί βάζουμε i και όχι 2? :-\

Laertis:
Ακόμα κι αν κατάλαβαν όμως Ευριπίδη εσύ θα τους βαθμολογήσεις το ίδιο με όσους βάλουν λάθος την τιμή τερματισμού.
Η λογική ότι δουλεύει δεν χάνει μονάδες, με προβληματίζει αφάνταστα.
Και αφού η απόδοση φίλε Ευριπίδη δεν μας αφορά, γιατί η εύρεση μέγιστης τιμής σε μονοδιάστατο με ταξινόμηση φυσσαλίδας  πρέπει να χάσει μονάδες;  Με ποιό μέτρο ορίζεις το πότε πρέπει και πότε δεν πρέπει να κόβονται μόρια ; Προφανώς με καθαρά προσωπικό.

evry:
Γιώργο καταρχήν χαίρομαι που διαφωνούμε για ακόμα ένα θέμα >:D
Το κριτήριο για το αν θα έκοβα δεν είναι προσωπικό. Το εξήγησα και αφορά την πολυπλοκότητα, δηλαδή στην μια περιπτώση έχεις κάποιες περιττές συγκρίσεις αλλά ο αλγόριθμός σου είναι ίδιας τάξης ενώ στην περίπτωση μέγιστο/ταξινόμηση έχεις αλγόριθμο μεγαλύτερης τάξης.
Επίσης δεν είπα ότι θα έκοβα από καμία από τις δυο λύσεις αφού δεν ζητείται αποδοτική/βέλτιστη λύση. Η δεύτερη περίπτωση είναι σαφώς χειρότερη από την 1η και ίσως εκεί να είχες ένα πιο ισχυρό επιχείρημα να κόψεις. Αυτό είναι όλο.
Κανονικά όμως δε νομίζω ότι μπορείς να κόψεις σε καμία περίπτωση αφού δίνεται αλγόριθμος σωστός ως προς την ορθότητά του.

Πλοήγηση

[0] Λίστα μηνυμάτων

[#] Επόμενη σελίδα

Μετάβαση στην πλήρη έκδοση