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

Ιουλίου 6, 2008

Ταξινόμηση

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

Έστω A ένας m \times n πίνακας πραγματικών αριθμών. Πρώτα ταξινομούμε κάθε γραμμή του πίνακα σε αύξουσα σειρά. Έπειτα ταξινομούμε κάθε στήλη του σε αύξουσα σειρά. Δείξτε ότι μετά το δεύτερο αυτό βήμα οι γραμμές εξακολουθούν να είναι ταξινομημένες σε αύξουσα σειρά.

Advertisements

9 Σχόλια »

  1. Θα δείξουμε ότι υπάρχει αλγόριθμος ο οποίος διατάσει σε αύξουσα σειρά τα στοιχεία του πίνακα ανά στήλες και διατηρεί την αύξουσα διάταξη ανά γραμμές.
    Έστω ότι υπάρχει ένας τέτοιος αλγόριθμος για πίνακες 2*n οι γραμμές των οποίων είναι διατεταγμένες σε αύξουσα σειρά. Δείχνουμε ότι υπάρχει για πίνακες m*n για κάθε m επαγωγικά:

    m=1. Προφανές
    m=2. Εξ’υποθέσεως
    Έστω ότι υπάρχει για m*n και ένας (m+1)*n πίνακας οι γραμμές του οποίου είναι διατεταγμένες σε αύξουσα σειρά. Εφαρμόζουμε τον αλγόριθμο που υπάρχει από την υπόθεση της επαγωγής στις τελευταίες m γραμμές του πίνακα. Κατόπιν, εφαρμόζουμε τον αλγόριθμο στις πρώτες 2 γραμμές του νέου πίνακα και, τέλος, εφαρμόζουμε ξανά τον αλγόριθμο στις τελευταίες m γραμμές του πίνακα που έχει προκύψει.
    Είναι εύκολο να διαπιστώσουμε ότι μετά από αυτήν τη διαδικασία τα στοιχεία των στηλών του πίνακα που προέκυψε είναι διατεταγμένα σε αύξουσα σειρά. Επειδή έχουμε υποθέσει επίσης ότι η αύξουσα σειρά των στοιχείων των γραμμών του πίνακα διατηρείται, έχουμε τελειώσει. ( Αρκεί, βέβαια, να δείξουμε την ύπαρξη ενός τέτοιου αλγορίθμου για 2*n πίνακες.)
    Έστω Π ένας 2*n πίνακας: Ξεκινώντας από τα δεξιά, βρίσκουμε το μέγιστο υποπίνακα (διαστάσεων 2*ν΄) του Π τ.ω. τα στοιχεία της πρώτης γραμμής να είναι όλα μεγαλύτερα ( ή ίσα, αλλά στο εξής θα παραλείπουμε αυτήν την περίπτωση μιας και τότε ο ισχυρισμός μας θα ισχύει πάντα) από τα αντίστοιχα στοιχεία της δεύτερης γραμμής. Ύστερα, ανταλλάσσουμε τις γραμμές του υποπίνακα αυτού. Είναι προφανές ότι οι στήλες του πίνακα Π μέρχι το σημείο αυτό είναι τώρα καλά διατεταγμένες. Αρκεί να δείξουμε ότι στο «σημείο της αλλάγής» δε δημιουργείται πρόβλημα στη διάταξη των σειρών. Πράγματι, αφού επιλέξαμε τον μέγιστο υποπίνακα με την ιδιότητα αυτή, στο σημείο αλλαγής έχουμε την εξής εικόνα:
    x1 x2
    y1 y2 , με x1<x2, y1<y2, x1y2 (1)
    Μετά την αλλαγή έχουμε την εξής εικόνα:
    x1 y2
    y1 x2
    Επίσης, από τις σχέσεις (1) παίρνουμε ότι x1<y1<y2 και y1<y2<x2, άρα η καλή διάταξη των γραμμών δε χαλάει.
    Κατόπιν, συνεχίζοντας από το σημείο αλλαγής και κινούμενοι προς τα αριστερά, βρίσκουμε το μέγιστο υποπίνακα του Π τ.ω. τα στοιχεία της πρώτης γραμμής να είναι όλα μικρότερα από τα αντίστοιχα στοιχεία της δεύτερης γραμμής.Τα στοιχεία αυτού του υποπίνακα τα αφήνουμε όπως είναι. Όπως και προηγουμένως, παίρνουμε την εξής εικόνα:
    x1 x2
    y1 y2 , με x1<x2, y1y1, x2<y2 (2)
    Επειδή τα στοιχεία x1,y1 θα αλλάξουν θέση (σύμφωνα με το προηγούμενο βήμα του αλγορίθμου), θα προκύψει η εξής εικόνα:
    y1 x2
    x1 y2
    Από τις σχέσεις (2) παίρνουμε ότι y1<x1<x2 και x1<x2<y2, επομένως η καλή διάταξη των γραμμών πάλι διατηρείται. Επαγωγικά, κάποια στιγμή θα εξαντλήσουμε τις στήλες του πίνακα και θα έχουμε πετύχει την ποθητή διάταξη.

    Μου αρέσει!

    Σχόλιο από sonzi — Ιουλίου 7, 2008 @ 7:57 μμ

  2. Μπερδεύτηκα λίγο με την επαγωγή και με το
    μέγιστο υποπίνακα ίσως γιατί το σκέφτομαι
    αλλιώς. θα προσπαθήσω να το διατυπώσω.

    Αρχικά υποθέτουμε ότι οι γραμμές έχουν
    διαταχτεί.
    Παίρνουμε τώρα τις 2 πρώτες γραμμές. Εστω ότι
    πριν τη διάταξη των έχουμε:
    α(1,1) > α(1,2) και α(2,1) > α(2,2).

    Εχουμε τις παρακάτω περιπτώσεις:
    1) α(1,1) > α(2,1) και α(1,2) > α(2,2)
    2) α(1,1) > α(2,1) και α(1,2) < α(2,2)
    3) α(1,1) α(2,2)
    4) α(1,1) < α(2,1) και α(1,2) α'(1,2) και α'(2,1) > α'(2,2).
    όπου α’ τα νέα διατεταγμένα στοιχεία.
    Εν συνεχεία διατάσουμε τα α(1,3) και α(2,3)
    και εδώ έχουμε μόνο δύο περιπτώσεις να
    τσεκάρουμε αφού τα α'(2,1) και α'(2,2)
    είναι ήδη διατεταγμένα.
    Αφού το κάνουμε και αυτό εύκολα
    διαπιστώνουμε ότι ισχύει:
    α'(1,1) > α'(1,3) και α'(2,1) > α'(2,3)
    από τη μεταβατική ιδιότητα.

    Συνεχίζουμε έτσι για όλες τις υπο-στήλες
    των δύο πρώτων γραμμών. Αρα ο
    υποπίνακας 2*n είναι τώρα σωστά
    διατεταγμένος.
    Η διαδικασία συνεχίζεται διαδοχικά παίρνοντας
    την 1η γραμμή με την 3η, μετά την 1η με την
    4η κ.ο.κ. Οταν εξαντλήσουμε τα ζευγάρια
    της 1η γραμμής με όλες τις υπόλοιπες, τότε
    η πρώτη γραμμή θα έχει το μέγιστο στοιχείο
    κάθε στήλης.
    Επαναλαμβάνουμε τη διαδικασία από την αρχή
    παίρνοντας τα ζευγάρια της 2ης γραμμής με
    όλες τις παρακάτω για να τοποθετήσουμε τα
    αμέσως μεγαλύτερα στοιχεία κάθε στήλης στη
    2η γραμμή κ.ο.κ.

    Μου αρέσει!

    Σχόλιο από xatzial — Ιουλίου 7, 2008 @ 9:29 μμ

  3. Μερικές γραμμές εμφανίζονται κομμένες
    Ελπίζω να φανεί:

    Εχουμε τις παρακάτω περιπτώσεις:
    1) α(1,1) > α(2,1) και α(1,2) > α(2,2)
    2) α(1,1) > α(2,1) και α(1,2) < α(2,2)
    3) α(1,1) α(2,2)
    4) α(1,1) < α(2,1) και α(1,2) α'(1,2) και α'(2,1) > α'(2,2).
    όπου α’ τα νέα διατεταγμένα στοιχεία.

    Μου αρέσει!

    Σχόλιο από xatzial — Ιουλίου 7, 2008 @ 9:33 μμ

  4. Δε φαίνεται, και δεν έχω ιδέα γιατί συμβαίνει αυτό.

    Εν πάσει περιπτώσει αυτό που εννοώ είναι
    ότι και στις 4 περιπτώσεις καταλήγουμε σε
    διάταξη που είναι η ίδια για τα νέα στοιχεία (α’) όπως
    στα παλιά δηλαδή α'(1,1) μεγαλύτερο από το
    α'(1,2) και α'(2,1) μεγαλύτερο από το α'(2,2).

    Μου αρέσει!

    Σχόλιο από xatzial — Ιουλίου 7, 2008 @ 9:39 μμ

  5. sonzi και xatzial:

    Είμαι απείρως μπλεγμένος με τις απαντήσεις σας. Αυτό πιθανότατα οφείλεται στο ότι το θέμα είναι κάπως περίπλοκο αλλά και στο μικρό καύσωνα που επικρατεί αυτή τη στιγμή και κάνει το μυαλό μου να μη συνεργάζεται.

    Αλλά αυτό που κυρίως με μπλέκει είναι ότι και στις δύο απαντήσεις σας η έμφαση είναι στον τρόπο ταξινόμησης. Όμως, όπως και να αποφασίσει κανείς να ταξινομήσει τις γραμμές και μετά τις στήλες το αποτέλεσμα είναι το ίδιο, και είτε αυτό που ζητάω ισχύει με κάθε τρόπο ταξινόμησης είτε με κανένα. Προς τι λοιπόν η μελέτη του τρόπου ταξινόμησης;

    Μήπως θα μπορούσατε να επαναδιατυπώσετε τις αποδείξεις σας με πιο καθαρό τρόπο;

    Ακολουθεί μια υπόδειξη στο επόμενο σχόλιο.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 8, 2008 @ 5:38 μμ

  6. Υπόδειξη:

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

    Ορισμός:
    Στην επόμενη πρόταση ως μέθοδος (αύξουσας) ταξινόμησης θεωρείται μόνο όποια μέθοδος κάνει μόνο μια ακολουθία από τις ακόλουθες πράξεις: κοιτάει δύο στοιχεία της λίστας τα 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.

    Αποδείξτε αυτή την απίθανη πρόταση. Η απόδειξη (με την εις άτοπον απαγωγή) είναι πολύ απλή.

    Μετά εφαρμόστε την ιδέα αυτή και στο πρόβλημά μας.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 8, 2008 @ 5:46 μμ

  7. Το μπλέξιμο ήταν αναμενόμενο…
    Διατυπώνω ξανά την πρόταση μου.

    Εφάρμοσα την bubblesort αρχικά
    σε δύο στοιχεία: στα α[1,ι] και α[2,ι] για κάθε
    στήλη: Είπα λοιπόν ότι σε οποιαδήποτε
    περίπτωση η διάταξη των νέων α[1,1] με το α[1,2]
    και του α[2,1] με το α[2,2] δε χαλάει με τον
    παραπάνω τρόπο. Χρησιμοποίησα μετά
    τα νέα διατεταγμένα στοιχεία α[1,2] και α[2,2]
    για να δείξω ότι η διάταξη τους αντίστοιχα
    με τα νέα α[1,3] και α[2,3]
    εξακολουθεί να διατηρείται.
    Συμπέρανα ότι και η διάταξη των
    α[1,1] με το α[1,3] και των α[2,1] με το
    α[2,3] διατηρείται από τη μεταβατική
    ιδιότητα.
    Συνεπώς συνεχίζοντας δε χαλάει
    η διάταξη των 2 πρώτων γραμμών.

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

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

    Μου αρέσει!

    Σχόλιο από xatzial — Ιουλίου 8, 2008 @ 8:21 μμ

  8. Η λέξη bubblesort στο ποστ μου άκυρη.
    Απλά διαλέγω τις γραμμές με τη σειρά
    που έχει γράψει τα ζεύγη ο κύριος
    Kolountzakis.

    Μου αρέσει!

    Σχόλιο από xatzial — Ιουλίου 8, 2008 @ 8:36 μμ

  9. xatzial:

    Πολύ σωστά.

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

    Παρ’ όλα αυτά θα ήθελα και μια λύση του θεωρήματος της υπόδειξής μου, οπότε το κάνω χωριστό πρόβλημα.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 8, 2008 @ 9:33 μμ


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: