Το Στέκι των Πληροφορικών

Γενικό Λύκειο => Γ΄ Λυκείου => Μήνυμα ξεκίνησε από: tsak στις 14 Αύγ 2015, 11:01:25 μμ

Τίτλος: Νεοι αλγοριθμοι ταξινομησης
Αποστολή από: tsak στις 14 Αύγ 2015, 11:01:25 μμ
Καλησπερα σε ολους. Θεωρειτε οτι υπαρχει περιπτωση να ζητηθεί με κάποιον τρόπο συγκεκριμένος αλγόριθμος ταξινομησης σε άσκηση ?  Σε μια άσκηση που απαιτείται ταξινόμηση δεν εχει την ελευθερία ο μαθητής να επιλέξει όποιον αλγόριθμο ταξινομησης επιθυμεί?
Τίτλος: Απ: Νεοι αλγοριθμοι ταξινομησης
Αποστολή από: itt στις 14 Αύγ 2015, 11:54:27 μμ
Εαν ζητηθεί αλγόριθμος ταξινόμησης με συγκεκριμένη πολυπλοκότητα τότε θα πρέπει να επιλέξει από αυτούς που την παρουσιάζουν.
Τίτλος: Απ: Νεοι αλγοριθμοι ταξινομησης
Αποστολή από: petrosp13 στις 15 Αύγ 2015, 01:52:18 πμ
Μα στην νέα ύλη ορίζεται οτι ο μαθητής δεν θα ασχολείται με υπολογισμό πολυπλοκότητας
Τίτλος: Απ: Νεοι αλγοριθμοι ταξινομησης
Αποστολή από: itt στις 15 Αύγ 2015, 06:56:59 μμ
Θυμόμουν που το ανέφερες σε ένα ποστ σου σε άλλο thread και υπέθεσα ότι είναι στην ύλη. Λάθος κατάλαβα τότε.
Τίτλος: Απ: Νεοι αλγοριθμοι ταξινομησης
Αποστολή από: gthal στις 26 Νοέ 2015, 01:07:09 μμ
Πλην της quicksort, οι άλλοι 3 αλγόριθμοι που (ακόμα υποθέτουμε ότι) θα "μάθουμε" είναι O(n2) , σωστά ?
Θα μπορούσαμε να πούμε λοιπόν ότι είναι το ίδιο αποδοτικοί ή όχι αποδοτικοί.
Παρόλα αυτά η φυσαλίδα είναι σημαντικά πιο αργή από τους δύο άλλους.
Πώς θα μπορούσε αυτό να το εκτιμήσει κανείς apriori, αν όχι μέσω του υπολογισμού της τάξης τους? ? ?
(Τελικά αυτός ο big-O συμβολισμός δε μου έχει κάτσει καθόλου. Ή κάτι δεν έχω καταλάβει ή βγαίνει έξω από τα όρια του ντετερμινισμού για το δικό μου αισθητήριο... ??? )
Τίτλος: Απ: Νεοι αλγοριθμοι ταξινομησης
Αποστολή από: evry στις 27 Νοέ 2015, 10:36:03 πμ
Και η quicksort Ο(n2) είναι  ;).
https://en.wikipedia.org/wiki/Quicksort (https://en.wikipedia.org/wiki/Quicksort). Απλά αυτό είναι πολύ σπάνιο να συμβεί, που σημαίνει ότι πρακτικά είναι πολύ γρήγορη, θεωρητικά όμως .... στα ίδια
 Όταν μιλάμε για πολυπλοκότητα χωρίς να διευκρινίζουμε εννοούμε την πολυπλοκότητα στην χειρότερη περίπτωση.
Στη μέση περίπτωση είναι O(nlogn) ενώ για παράδειγμα η πολυπλοκότητα της MergeSort είναι O(nlogn) στην χειρότερη περιπτωση.

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

Η συγκριτική ταξινόμηση.... ταξινομήσεων λοιπόν πρέπει να μείνει έξω από την ενότητα της απόδοσης αλγορίθμων.
Καλύτερα να δείχνουμε στα παιδιά κραυγαλέα παραδείγματα όπως
σειριακή / δυαδική
άθροισμα στοιχείων κυρίας διαγωνίου με διπλή και μονή (Α[ι,ι]) επανάληψη
Υπολογισμό αθροίσματος των πρώτων ν αριθμών με επανάληψη και με τον τύπο κλπ

Στις ταξινομήσεις για να εξηγήσεις τι συμβαίνει θα πρέπει να μελετήσεις τη συμπεριφορά των αλγορίθμων για διάφορες περιπτώσεις συνόλων δεδομένων, π.χ. σχεδόν ταξινομημένων πινάκων κλπ.
Για παράδειγμα η ταξινόμηση με επιλογή θα κάνει πάντα Ο(n2) ενώ η φυσαλίδα για κάποια σύνολα μπορεί να κάνει Ο(n) .
Τίτλος: Απ: Νεοι αλγοριθμοι ταξινομησης
Αποστολή από: iomil στις 10 Δεκ 2015, 10:42:41 μμ
Καλησπέρα! Να πω κι εγώ τον πόνο μου;;
Στις νέες μεθόδους ταξινόμησης θα πρέπει να ασχοληθούμε και με την περίπτωση που έχουμε παράλληλους πίνακες με μη μοναδικά στοιχεία;;