Προβλήματα Μαθηματικών

Ιουλίου 8, 2008

Ταξινόμηση (2)

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 9:40 μμ

Παρακάτω μελετάμε μεθόδους (αλγορίθμους) ταξινόμησης, κατ’ αύξουσα σειρά, μιας λίστας αριθμών x_j, j=1,2,\ldots,n.

Παρακάτω ως μέθοδος (αύξουσας) ταξινόμησης θεωρείται μόνο όποια μέθοδος κάνει μόνο μια ακολουθία από τις ακόλουθες πράξεις: κοιτάει δύο στοιχεία της λίστας τα x_i και x_j, με j>i και τα εναλλάσσει αν και μόνο αν x_i >x_j.

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

(1,2), (1,3), … ,(1,n), (2,3), (2,4), … ,(2,n) (3,4) … (n-1,n).

Αυτό είναι το λεγόμενο bubblesort, η πρώτη ουσιαστικά μέθοδος ταξινόμησης που μαθαίνει κανείς.

Δείξτε ότι μια μέθοδος ταξινόμησης αριθμητικών λιστών δουλεύει αν και μόνο αν δουλεύει όταν κάθε θέση της λίστας περιέχει 0 ή 1.

Advertisements

14 Σχόλια »

  1. Υπόδειξη:

    Αν είναι f:{\mathbb R}\to {\mathbb R} μια αύξουσα συνάρτηση (όχι κατ’ανάγκη γνήσια αύξουσα) τότε μια μέθοδος ταξινόμησης όπως αυτές που μελετάμε θα κάνει ακριβώς τις ίδιες εναλλαγές στη λίστα f(x_j) όπως στη λίστα x_j.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 10, 2008 @ 3:39 μμ

  2. Κάθομαι και διαβάζω το πρόβλημα και δεν μπορώ να καταλάβω τι ζηταέι. Μπορείτε να γίνετε πιο σαφής. Η υπόδειξη είναι λογική και κατανοητή αλλά το » κάθε θέση της λίστας περιέχει το 0 ή το 1 » δεν το καταλαβαίνω.

    Μου αρέσει!

    Σχόλιο από Κλάδος Μανούσος — Σεπτεμβρίου 1, 2008 @ 2:37 πμ

  3. Οι λίστες των οποίων τα περιεχόμενα είναι 0 ή 1 είναι ένα γνήσιο υποσύνολο όλων των αριθμητικών λιστών. Για παράδειγμα η λίστα 0, 1, 1, 0, 1 (με 5 στοιχεία), της οποίας η ταξινομημένη μορφή είναι 0, 0, 1, 1, 1, είναι μια τέτοια λίστα.

    Αυτό που ζητώ είναι να δείξετε ότι αν μια μέθοδος ταξινόμησης (όπως αυτές που περιγράφω παραπάνω, που στηρίζεται δηλ. σε ζεύγη συγκρίσεων) δουλεύει σωστά σε 0-1 λίστες τότε δουλεύει σωστά σε όλες τις λίστες.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 1, 2008 @ 7:46 πμ

  4. Καλημέρα σας,

    Πολύ ωραία τώρα κατάλαβα τι εννοείτε.

    Μου αρέσει!

    Σχόλιο από Κλάδος Μανούσος — Σεπτεμβρίου 1, 2008 @ 10:40 πμ

  5. Να παραθέσω μια σύντομη απάντηση πολύ πρόχειρη. Εδω καλούμαστε να απόδείξουμε το ευθύ και το αντίστροφο. Δηλαδή να αποδείξουμε πως αν μια μέθοδος ταξινόμησης δουλεύει σε λίστες τυχαίων αριθμών δουλεύει και σε λίστες 0-1 αριθμών. Και αν δουλεύει σε λίστες 0-1 αριθμών τότε δουλευει και σε λίστες τυχαίων αριθμών.

    Ευθύ:

    «Οι λίστες των οποίων τα περιεχόμενα είναι 0 ή 1 είναι ένα γνήσιο υποσύνολο όλων των αριθμητικών λιστών. Για παράδειγμα η λίστα 0, 1, 1, 0, 1 (με 5 στοιχεία), της οποίας η ταξινομημένη μορφή είναι 0, 0, 1, 1, 1, είναι μια τέτοια λίστα.» Άρα είμαστε οκ…

    Αντίστροφο:

    Επειδή οι μέθοδοι ταξινόμησης που αναφέρατε κάνουν σύγκριση ζευγών έχουμε 4 δυνατές περιπτώσεις ζυεγών:

    1)0-0
    2)0-1
    3)1-0
    4)1-1

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

    \forall i,j με j>i τότε έχουμε 3 περιπτώσεις

    1) x_j>x_i
    2) x_jx_i με \forall i,j με j>i

    Αντίθετα στην δεύτερη περίπτωση αντιστοιχίζουμε το 1 στο x_i και το 0 στο x_j. Η μέθοδος ταξινόμησης όταν βρεί ζεύγος 1 – 0 θα το αλλάξει οπότε αλλάζει και το x_ji

    Ενώ στην τρίτη περίπτωση που έχουμε ισότητα αντιστοιχούμε στα x_i,x_j τον ίδιο αριθμό (0 ή 1). Η μέθοδος ταξινόμησης δεν θα κάνει αλλαγή σε καμία περίπτώση οπότε δεν θα κάνει και στα x_i,x_j.

    Μου αρέσει!

    Σχόλιο από Κλάδος Μανούσος — Σεπτεμβρίου 1, 2008 @ 11:17 πμ

  6. Δεν ξέρω τι έγινε στο αντίστροφο και μου έκοψε πράγματα…οπότε το ξαναπαραθέτω…

    Αντίστροφο:

    Επειδή οι μέθοδοι ταξινόμησης που αναφέρατε κάνουν σύγκριση ζευγών έχουμε 4 δυνατές περιπτώσεις ζυεγών:

    1)0-0
    2)0-1
    3)1-0
    4)1-1

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

    \forall i,j με j>i έχουμε 3 περιπτώσεις

    1) x_j>x_i
    2) x_jx_i

    Αντίθετα στην δεύτερη περίπτωση αντιστοιχίζουμε το 1 στο x_i και το 0 στο x_j. Η μέθοδος ταξινόμησης όταν βρεί ζεύγος 1 – 0 θα το αλλάξει οπότε αλλάζει και το x_j<x_i

    Ενώ στην τρίτη περίπτωση που έχουμε ισότητα αντιστοιχούμε στα x_i,x_j τον ίδιο αριθμό (0 ή 1). Η μέθοδος ταξινόμησης δεν θα κάνει αλλαγή σε καμία περίπτώση οπότε δεν θα κάνει και στα x_i,x_j.

    Μου αρέσει!

    Σχόλιο από Κλάδος Μανούσος — Σεπτεμβρίου 1, 2008 @ 11:23 πμ

  7. Ξανά μου έκοψε….

    Μου αρέσει!

    Σχόλιο από Κλάδος Μανούσος — Σεπτεμβρίου 1, 2008 @ 11:23 πμ

  8. Αντίστροφο:

    Επειδή οι μέθοδοι ταξινόμησης που αναφέρατε κάνουν σύγκριση ζευγών έχουμε 4 δυνατές περιπτώσεις ζυεγών:

    1)0-0
    2)0-1
    3)1-0
    4)1-1

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

    \forall i,j με j>i έχουμε 3 περιπτώσεις

    1) x_j>x_i
    2) x_j<x_i
    3) x_j=x_i

    Αν χρησιμοποιήσουμε μια συνάρτηση f όπως αυτή της υπόδειξης τοτε μπορούμε να κάνουμε τις κάτοθι αντιστοιχίες:

    Στην πρώτη περίπτωση αντιστοιχίζουμε το 0 στο x_i και το 1 στο x_j. Η μέθοδος ταξινόμησης όταν βρεί ζεύγος 0 – 1 δεν θα το αλλάξει οπότε δεν αλλάζει και το x_j<x_i

    Αντίθετα στην δεύτερη περίπτωση αντιστοιχίζουμε το 1 στο $late x_i$ και το 0 στο x_j. Η μέθοδος ταξινόμησης όταν βρεί ζεύγος 1 – 0 θα το αλλάξει οπότε αλλάζει και το x_j<x_i

    Ενώ στην τρίτη περίπτωση που έχουμε ισότητα αντιστοιχούμε στα x_i,x_j τον ίδιο αριθμό (0 ή 1). Η μέθοδος ταξινόμησης δεν θα κάνει αλλαγή σε καμία περίπτώση οπότε δεν θα κάνει και στα x_i,x_j.

    Μου αρέσει!

    Σχόλιο από Κλάδος Μανούσος — Σεπτεμβρίου 1, 2008 @ 11:31 πμ

  9. Ενα λάθος έκει που λέω :

    «Στην πρώτη περίπτωση αντιστοιχίζουμε το 0 στο x_i και το 1 στο x_j. Η μέθοδος ταξινόμησης όταν βρεί ζεύγος 0 – 1 δεν θα το αλλάξει οπότε δεν αλλάζει και το x_jx_i«

    Μου αρέσει!

    Σχόλιο από Κλάδος Μανούσος — Σεπτεμβρίου 1, 2008 @ 11:34 πμ

  10. Κάποιος από τους admin ας στρώσει τα post πάλι γιατί έγινε χαμός

    Ενα λάθος έκει που λέω :

    “Στην πρώτη περίπτωση αντιστοιχίζουμε το 0 στο x_i και το 1 στο x_j. Η μέθοδος ταξινόμησης όταν βρεί ζεύγος 0 – 1 δεν θα το αλλάξει οπότε δεν αλλάζει και το x_jx_i

    Μου αρέσει!

    Σχόλιο από Κλάδος Μανούσος — Σεπτεμβρίου 1, 2008 @ 11:35 πμ

  11. Με συγχωρείτε δεν μπορώ αλλο τα νεύρα μου…το λάθος είναι εκεί που λέει στην πρώτη μέθοδο αντιστοιχίζουμε…στο τέλος που γράφω x_j<x_i δεν είναι μικτρότερο αλλά μεγαλύτερο…

    Μου αρέσει!

    Σχόλιο από Κλάδος Μανούσος — Σεπτεμβρίου 1, 2008 @ 11:37 πμ

  12. Λείπει κάτι βασικό από το επιχείρημά σου. Πώς ορίζεται αυτή η f; Γιατί σίγουρα το επιχείρημα δε δουλεύει αν πάρεις μια τυχαία τέτοια συνάρτηση.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 2, 2008 @ 1:09 μμ

  13. Έστω ότι υπάρχει μια μέθοδος αύξουσας ταξινόμησης με την οποία ταξινομείται σωστά κάθε πίνακας που περιέχει μόνο 0 και 1 αλλά υπάρχει ένας τουλάχιστον πίνακας που δεν ταξινομείται σωστά.
    Έστω a_1,a_2,...,a_n τα στοιχεία ενός τέτοιου πίνακα πριν τη ταξινόμηση.
    Έστω επίσης b_1,b_2,...,b_n τα στοιχεία του μετά τη λανθασμένη ταξινόμηση και c_1,c_2,...,c_n τα στοιχεία του σε αύξουσα σειρά.
    Θεωρούμε το ελάχιστο i για το οποίο το b_i\neq c_i. Για αυτό το i θα υπάρχει τουλάχιστον ένα k>i τέτοιο ώστε το b_k < b_i.
    Ορίζουμε την συνάρτηση f ώστε κάθε στοιχείο μικρότερο του b_i να το στέλνει στο 0 και κάθε στοιχείο μεγαλύτερο ή ίσο του b_i να το στέλνει στο 1.
    Κάνοντας ταξινόμηση με αυτή τη μέθοδο στον πίνακα με στοιχεία f(a_1),f(a_2),...,f(a_n) θα πάρουμε τον πίνακα με στοιχεία f(b_1),f(b_2),...,f(b_n) για τον οποίο όμως ισχύει ότι k>i αλλά f(b_k)=0<1=f(b_i), άρα η μέθοδος τον ταξινόμησε λάθος. Αυτό όμως είναι άτοπο γιατί υποθέσαμε ότι η μέθοδος ταξινομεί σωστά κάθε πίνακα που περιέχει μόνο 0 και 1. Συνεπώς ισχύει το ζητούμενο.

    Μου αρέσει!

    Σχόλιο από steliosdes — Νοέμβριος 12, 2008 @ 6:21 μμ

  14. Σωστά.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Νοέμβριος 12, 2008 @ 11:08 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: