Αποστολέας Θέμα: Νεοι αλγοριθμοι ταξινομησης  (Αναγνώστηκε 2730 φορές)

tsak

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 183
Νεοι αλγοριθμοι ταξινομησης
« στις: 14 Αύγ 2015, 11:01:25 μμ »
Καλησπερα σε ολους. Θεωρειτε οτι υπαρχει περιπτωση να ζητηθεί με κάποιον τρόπο συγκεκριμένος αλγόριθμος ταξινομησης σε άσκηση ?  Σε μια άσκηση που απαιτείται ταξινόμηση δεν εχει την ελευθερία ο μαθητής να επιλέξει όποιον αλγόριθμο ταξινομησης επιθυμεί?

itt

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 429
  • Real stupidity beats ΑΙ any time
Απ: Νεοι αλγοριθμοι ταξινομησης
« Απάντηση #1 στις: 14 Αύγ 2015, 11:54:27 μμ »
Εαν ζητηθεί αλγόριθμος ταξινόμησης με συγκεκριμένη πολυπλοκότητα τότε θα πρέπει να επιλέξει από αυτούς που την παρουσιάζουν.
« Τελευταία τροποποίηση: 15 Αύγ 2015, 01:41:15 πμ από itt »

petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2313
Απ: Νεοι αλγοριθμοι ταξινομησης
« Απάντηση #2 στις: 15 Αύγ 2015, 01:52:18 πμ »
Μα στην νέα ύλη ορίζεται οτι ο μαθητής δεν θα ασχολείται με υπολογισμό πολυπλοκότητας
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

itt

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 429
  • Real stupidity beats ΑΙ any time
Απ: Νεοι αλγοριθμοι ταξινομησης
« Απάντηση #3 στις: 15 Αύγ 2015, 06:56:59 μμ »
Θυμόμουν που το ανέφερες σε ένα ποστ σου σε άλλο thread και υπέθεσα ότι είναι στην ύλη. Λάθος κατάλαβα τότε.

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 947
Απ: Νεοι αλγοριθμοι ταξινομησης
« Απάντηση #4 στις: 26 Νοέ 2015, 01:07:09 μμ »
Πλην της quicksort, οι άλλοι 3 αλγόριθμοι που (ακόμα υποθέτουμε ότι) θα "μάθουμε" είναι O(n2) , σωστά ?
Θα μπορούσαμε να πούμε λοιπόν ότι είναι το ίδιο αποδοτικοί ή όχι αποδοτικοί.
Παρόλα αυτά η φυσαλίδα είναι σημαντικά πιο αργή από τους δύο άλλους.
Πώς θα μπορούσε αυτό να το εκτιμήσει κανείς apriori, αν όχι μέσω του υπολογισμού της τάξης τους? ? ?
(Τελικά αυτός ο big-O συμβολισμός δε μου έχει κάτσει καθόλου. Ή κάτι δεν έχω καταλάβει ή βγαίνει έξω από τα όρια του ντετερμινισμού για το δικό μου αισθητήριο... ??? )
« Τελευταία τροποποίηση: 26 Νοέ 2015, 11:54:48 μμ από gthal »
Φιλικά,
Γιώργος Θαλασσινός

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3530
  • to Iterate is human to Recurse divine
Απ: Νεοι αλγοριθμοι ταξινομησης
« Απάντηση #5 στις: 27 Νοέ 2015, 10:36:03 πμ »
Και η quicksort Ο(n2) είναι  ;).
https://en.wikipedia.org/wiki/Quicksort. Απλά αυτό είναι πολύ σπάνιο να συμβεί, που σημαίνει ότι πρακτικά είναι πολύ γρήγορη, θεωρητικά όμως .... στα ίδια
 Όταν μιλάμε για πολυπλοκότητα χωρίς να διευκρινίζουμε εννοούμε την πολυπλοκότητα στην χειρότερη περίπτωση.
Στη μέση περίπτωση είναι O(nlogn) ενώ για παράδειγμα η πολυπλοκότητα της MergeSort είναι O(nlogn) στην χειρότερη περιπτωση.

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

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

Στις ταξινομήσεις για να εξηγήσεις τι συμβαίνει θα πρέπει να μελετήσεις τη συμπεριφορά των αλγορίθμων για διάφορες περιπτώσεις συνόλων δεδομένων, π.χ. σχεδόν ταξινομημένων πινάκων κλπ.
Για παράδειγμα η ταξινόμηση με επιλογή θα κάνει πάντα Ο(n2) ενώ η φυσαλίδα για κάποια σύνολα μπορεί να κάνει Ο(n) .
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

iomil

  • Θαμώνας
  • ***
  • Μηνύματα: 24
Απ: Νεοι αλγοριθμοι ταξινομησης
« Απάντηση #6 στις: 10 Δεκ 2015, 10:42:41 μμ »
Καλησπέρα! Να πω κι εγώ τον πόνο μου;;
Στις νέες μεθόδους ταξινόμησης θα πρέπει να ασχοληθούμε και με την περίπτωση που έχουμε παράλληλους πίνακες με μη μοναδικά στοιχεία;;