Ταξινόμηση σε δισδιάστατους πίνακες???

Ξεκίνησε από bookitsa, 14 Μαρ 2008, 04:14:54 ΜΜ

« προηγούμενο - επόμενο »

bookitsa

Γεια σας..
Έβαλα σε τεστ μια ερώτηση Σ-Λ από το βιβλίο του κυρίου Τσιωτάκη που έχει ως εξής:
Η ταξινόμηση της φυσαλίδας μπορεί να εφαρμοστεί και σε δισδιάστατους πίνακες.
Από τις απαντήσεις στο πίσω μέρος του βιβλίου είδα ότι είναι λάθος, γεγονός που το ήξερα, γιατί και στο σχολικό βιβλίο η ταξινόμηση λαμβάνει χώρα σε μονοδιάστατους πίνακες.
Καποια παιδιά λοιπόν αντέδρασαν στο λάθος γιατί μου είπαν ότι σε φροντιστήρια έχουν κάνει την ταξινόμηση και σε δισδιάστατους πίνακες.
Είναι αυτό δυνατόν?

sstergou

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

Ένας αντίστοιχος δισδιάστατος πίνακας με  50 γραμμές και 10 στήλες μπορεί να χρησιμοποιηθεί για να αποθηκέυσεις τους βαθμούς 50 φοιτητών στα 10 μαθήματα. Τι θα κάνεις αν θες να ταξινομήσεις τους βαθμούς του κάθε φοιτητή ώστε να φαίνονται σε φθίνουσα σειρά;
Θα ταξινομήσεις τον δισδιάστατο ανά γραμμή με όποια μέθοδο ταξινόμησης μονοδιάστατου θες αφού κάθε γραμμή του δισδιάστατου είναι ένας μονοδιάστατος πίνακας.

Το ίδιο μπορεί να γίνει και με τις στήλες.

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

evry


  Η ταξινόμηση των γραμμών ενός πίνακα δυο διαστάσεων δε νομίζω ότι είναι σωστή, διότι έτσι χαλάς τον πίνακα, δηλαδή πριν την ταξινόμηση ξέρεις ότι οι βαθμοί του φοιτητή i στα 10 μαθήματα είναι Β[i,1], Β[i,2], Β[i,3], ..., Β[i,10] και ότι οι βαθμοί όλων των φοιτητών στο τυχαίο j μάθημα είναι Β[1, j], Β[2, j], Β[3, j], ..., Β[50, j]. Μετά την ταξινόμηση όμως,  η τυχαία στήλη j του πίνακα δεν θα έχει τους βαθμούς των φοιτητών στο j μάθημα αλλά τον j-οστό μεγαλύτερο βαθμό κάθε φοιτητή. Έτσι χαλάς τη σημασιολογία του πίνακα και δεν ξέρεις μετά ο κάθε βαθμός ποιου μαθήματος είναι.
    Δηλαδή η ταξινόμηση σε πίνακα δυο διαστάσεων εκτός του ότι δεν είναι ορισμένη στο βιβλίο δεν έχει και νόημα ορισμού γενικότερα, δε μπορώ να φανταστώ κάποια εφαρμογή της γενικότερα.
   Όσον αφορά το πρόβλημα στο οποίο αναφέρεσαι, δηλαδή την ταξινόμηση των βαθμών των φοιτητών σε φθίνουσα σειρά είναι απλή ταξινόμηση της κάθε γραμμής του πίνακα σαν να πρόκειται για μονοδιάστατο. Ωστόσο όπως είπα και πριν χαλάς τη σημασία που έχει ο πίνακας.
  Από την άλλη όλα είναι θέμα ορισμού..

Παράθεση από: sstergou στις 14 Μαρ 2008, 04:29:14 ΜΜ
Ένας αντίστοιχος δισδιάστατος πίνακας με  50 γραμμές και 10 στήλες μπορεί να χρησιμοποιηθεί για να αποθηκέυσεις τους βαθμούς 50 φοιτητών στα 10 μαθήματα. Τι θα κάνεις αν θες να ταξινομήσεις τους βαθμούς του κάθε φοιτητή ώστε να φαίνονται σε φθίνουσα σειρά;
Θα ταξινομήσεις τον δισδιάστατο ανά γραμμή με όποια μέθοδο ταξινόμησης μονοδιάστατου θες αφού κάθε γραμμή του δισδιάστατου είναι ένας μονοδιάστατος πίνακας.

Το ίδιο μπορεί να γίνει και με τις στήλες.

Η ταξινόμηση φυσσαλίδας έτσι όπως είναι ορισμένη στο βιβλίο χρησιμοποιείται μόνο σε μονοδιάστατους πίνακες. Με μια μικρή τροποποίηση όμως μπορείς να την χρησιμοποιήσεις για να ταξινομήσεις κάθε γραμμή του δισδιάστατου.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

alkisg

Άλλο καθημερινό παράδειγμα:
Ανοίγουμε τον τηλεφωνικό κατάλογο του ΟΤΕ και βλέπουμε ότι πρόκειται για δισδιάστατο πίνακα πολλών γραμμών και 5 στηλών ταξινομημένων ανά ονοματεπώνυμο, με παράλληλο πίνακα τηλεφώνων.
Μάλιστα αν κάποιος θέλει μπορεί να θεωρήσει τις σελίδες ως τρίτη διάσταση, εκφράζοντάς τον έτσι με 3σδιάστατο πίνακα.

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

Αν έχεις όρεξη διάβασε και αυτά:
https://alkisg.mysch.gr/steki/index.php?topic=310.0
https://alkisg.mysch.gr/steki/index.php?topic=794.0

sstergou

Παράθεση από: evry στις 14 Μαρ 2008, 05:15:31 ΜΜ
  Η ταξινόμηση των γραμμών ενός πίνακα δυο διαστάσεων δε νομίζω ότι είναι σωστή, διότι έτσι χαλάς τον πίνακα, δηλαδή πριν την ταξινόμηση ξέρεις ότι οι βαθμοί του φοιτητή i στα 10 μαθήματα είναι .....και ότι οι βαθμοί όλων των φοιτητών στο τυχαίο j μάθημα είναι......Μετά την ταξινόμηση όμως,  η τυχαία στήλη j του πίνακα δεν θα έχει τους βαθμούς των φοιτητών στο j μάθημα αλλά τον j-οστό μεγαλύτερο βαθμό κάθε φοιτητή

Το ίδιο όμως συμβαίνει και με τους μονοδιάστατους.

Όταν αντιμεταθέτεις στοιχεία των οποίων η θέση σημαίνει κάτι, πρέπει να κάνεις και κάποια πράγματα παραπάνω. Στο προηγούμενο παράδειγμα η θέση δεν σημαίνει τίποτε, μάλλον έπρεπε να το τονίσω.

Νομίζω πως η ταξινόμηση ανα γραμμή/στήλη έχει νόημα και στους δισδιάστατους, άσχετα με το το ότι είναι έξω από την ύλη.

bookitsa

Ουσιαστικά απ'ότι καταλαβαίνω στην ταξινόμηση δισδιάστατων πινάκων αναφερόμαστε στην ταξινόμηση γραμμής ή στήλης, δηλαδή και πάλι σε ταξινόμηση μονοδιάστατου πίνακα.Οπότε στο ερώτημά μου απαντάμε ότι γίνεται η ταξινόμηση σε δισδιάστατους πίνακες?Να το πιάσω σωστό δηλαδή στα παιδιά?

evry

  Άλκη στην περίπτωση του τηλεφωνικού καταλόγου που λες, αν υποθέσουμε ότι ο κατάλογος δεν είναι ταξινομημένος και τον ταξινομήσουμε με βάση το όνομα όπως λες, τότε δεν ταξινομούμε όπως λέει ο sstergou αλλά πρέπει σε κάθε αντιμετάθεση να αλλάζουμε και τα τηλέφωνα, δηλαδή τα τηλέφωνα να ακολουθούν το όνομα, σαν να είχαμε μια παράλληλη ταξινόμηση 5 πινάκων, όπως είπες.
    Το παράδειγμα που ψάχνω είναι μια ταξινόμηση κάθε γραμμής ή στήλης του πίνακα ξεχωριστά. Δηλαδή στην πρώτη στήλη να είναι τα ελάχιστα ή μέγιστα κάθε γραμμής κλπ. Στην περίπτωση του τηλεφωνικού καταλόγου αυτό δεν ισχύει.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

alkisg

Το ερώτημα της bookitsa δεν είναι συγκεκριμένα για την περίπτωση που έθεσε ο Στάθης, αλλά γενικά, αν υφίσταται ταξινόμηση σε δισδιάστατους. Προφανώς και υφίσταται, αρκεί να ορίσουμε πως τη θέλουμε.

Τώρα για την περίπτωση που είπε ο Στάθης:
α) Παράδειγμα που να παίζει ρόλο η θέση:
Θέλουμε να ταξινομήσουμε τις βαθμολογίες των μαθητών ενός σχολείου ανά τμήμα. Έχουμε λοιπόν ένα δισδιάστατο πίνακα βαθμολογιών όπου οι γραμμές εκφράζουν τους μαθητές και οι στήλες τα τμήματα. Έχουμε κι έναν παράλληλο δισδιάστατο πίνακα με τα ονόματα.
Έτσι κάνουμε ταξινομήσεις ανά στήλη, και επειδή έχουμε και παράλληλο πίνακα, σε κάθε αντιμετάθεση βαθμολογιών αντιμεταθέτουμε και τα ονόματα.
Το να χρησιμοποιήσουμε μονοδιάστατους δεν θα βόλευε, γιατί αν είχαμε 10 τμήματα θα έπρεπε να γράφουμε 10 φορές τον ίδιο κώδικα, ενώ τώρα ξεμπερδεύουμε με μια τρίτη ΓΙΑ (2 ΓΙΑ για κάθε φυσαλίδα + 1 ακόμα για όλες τις στήλες).

β) Παράδειγμα που να μην παίζει ρόλο η θέση:
Μας δίνουν κάμποσες βαλίτσες (=γραμμές) και κάμποσα από αυτά τα καροτσάκια που τις μεταφέρουν οι αχθοφόροι (=στήλες) και μας ζητάνε να τις ταξινομήσουμε ώστε η πιο βαριά να πάει κάτω, χωρίς να τους αλλάξουμε καροτσάκι γιατί θα αλλάξει ο προορισμός της βαλίτσας και δεν το θέλουμε. Ο δισδιάστατος πίνακας δηλαδή περιέχει μόνο τα βάρη των βαλιτσών.

pgrontas

Παράθεση από: alkisg στις 14 Μαρ 2008, 05:20:51 ΜΜ
Ανοίγουμε τον τηλεφωνικό κατάλογο του ΟΤΕ και βλέπουμε ότι πρόκειται για δισδιάστατο πίνακα πολλών γραμμών και 5 στηλών ταξινομημένων ανά ονοματεπώνυμο, με παράλληλο πίνακα τηλεφώνων.
Θα διαφωνήσω σε αυτό. Ο κατάλογος του ΟΤΕ είναι ΜΟΝΟΔΙΑΣΤΑΤΟΣ πίνακας εγγραφών. Άσχετα αν οι εγγραφές έχουν μπει χωρικά σε στήλες και σελίδες για να μην σέρνουμε μια ουρά από χαρτί.

Για μένα ταξινόμηση σε δισδιάστατο γενικά δεν υφίσταται γιατί δεν μπορείς να ορίσεις συνάρτηση διάταξης.
Έστω ένας πίνακας με βαθμολογίες μαθητών σε μαθήματα (Γραμμές μαθητές - Στήλες μάθημα).
Δεν έχει νόημα - δεν είναι λογικό - να συγκρίνεις την βαθμολογία του μαθητή I στο μάθημα J με την βαθμολογία του μαθητή Κ στο  μάθημα Λ.
Αν απλά πεις ότι συγκρίνεις βαθμολογίες, τότε ουσιαστικά καταργείς τις δύο διαστάσεις (μαθητής -μάθημα) και τις μετατρέπεις σε μία - βαθμολογίες.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

sstergou

Παράθεση από: pgrontas στις 14 Μαρ 2008, 06:35:04 ΜΜ
Για μένα ταξινόμηση σε δισδιάστατο γενικά δεν υφίσταται γιατί δεν μπορείς να ορίσεις συνάρτηση διάταξης.

Μα γιατί όχι!

Παράθεση από: pgrontas στις 14 Μαρ 2008, 06:35:04 ΜΜ
Δεν έχει νόημα - δεν είναι λογικό - να συγκρίνεις την βαθμολογία του μαθητή I στο μάθημα J με την βαθμολογία του μαθητή Κ στο  μάθημα Λ.
Αν απλά πεις ότι συγκρίνεις βαθμολογίες, τότε ουσιαστικά καταργείς τις δύο διαστάσεις (μαθητής -μάθημα) και τις μετατρέπεις σε μία - βαθμολογίες.

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

Στην ουσία δεν μιλάμε για δισδιάστατο αλλά για πολλούς μονοδιάστατους......

Άμα η ταξινόμηση αναφέρεται στην αντιμετάθεση ολόκληρων γραμμών ; Δηλαδή για να χρησιμοποιήσω παράδειγμα παρόμοιο με του ʼλκη:
Έχω 30 αχθοφόρους με 20 βαλίτσες ο καθένας και έρχονται φορτηγά τα οποία φορτώνονται και ξαναφεύγουν. Αυτό που θέλω να κάνω είναι να φορτώνονται πρώτα οι βαλίτσες του αχθοφόρου που έχει υπό την ευθύνη του τα περισσότερα κιλά.
Οπότε σύμφωνα με τον ορισμό του βιβλίου, έχω τα στοιχεία a1,a2,an τα οποία αναφέρονται στους μονοδιάστατους πίνακες των αχθοφόρων
και ορίζω σαν συνάρτηση διάταξης την f όπου f(a1) θα είναι το άθροισμα των κιλών των βαλιτσών του πρώτου αχθοφόρου κοκ.

Ομοίως μπορώ να ορίσω για οποιαδήποτε διάσταση.

sstergou

#10
Παράδειγμα με φοιτητές 2η έκδοση  :D
Γραμμές=φοιτητές, στήλες=μαθήματα

Κώδικας: Ψευδογλώσσα
Για ι από 1 μέχρι 10
  Διάβασε ΌνομαΜαθήματος[ι]
Τέλος_επανάληψης

Για ι από 1 μέχρι 30
  Για j από 1 μέχρι 10
    Διάβασε Βαθμοί[ι,j]
    ΌνοματαΜαθημάτωνΦοιτητή[ι,j] <- ΌνομαΜαθήματος[j]
  Τέλος_επανάληψης
Τέλος_επανάληψης

Για κ από 1 μέχρι 30
  Για ι από 2 μέχρι 10
    Για j από 10 μέχρι ι με_βήμα -1
      Αν Βαθμοί[κ, j-1] < Βαθμοί[κ, j] τότε
        αντιμετάθεσε Βαθμοί[κ, j-1], [κ, j]
        αντιμετάθεσε ΌνοματαΜαθημάτωνΦοιτητή[κ, j-1], ΌνοματαΜαθημάτωνΦοιτητή[κ, j]
      τέλος_αν
    Τέλος_επανάληψης
  Τέλος_επανάληψης
Τέλος_επανάληψης

Για ι από 1 μέχρι 30
  Για j από 1 μέχρι 10
    Εμφάνισε Βαθμοί[ι, j], " στο μάθημα ", ΌνοματαΜαθημάτωνΦοιτητή[ι, j]
  Τέλος_επανάληψης
Τέλος_επανάληψης


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

P.Tsiotakis

Παράθεση από: bookitsa στις 14 Μαρ 2008, 05:53:18 ΜΜ
Ουσιαστικά απ'ότι καταλαβαίνω στην ταξινόμηση δισδιάστατων πινάκων αναφερόμαστε στην ταξινόμηση γραμμής ή στήλης, δηλαδή και πάλι σε ταξινόμηση μονοδιάστατου πίνακα.

Αυτή ακριβώς είναι η φιλοσοφία της ερώτησης. Η ταξινόμηση φυσαλίδας εφαρμόζεται σε μονοδιάστατους πίνακες. Δεν εφαρμόζεται σε δισδιάστατους πίνακες γενικά.
Εφαρμόζεται σε ΜΙΑ διάσταση ενός δισδιάστατου πίνακα (ή προς τη γραμμή ή ως προς τη στήλη, όλες τις γραμμές/στήλες ή και μόνο μια γραμμή/στήλη). Γι αυτό και απαντάται ως Λάθος.

Ο δισδιάστατος πίνακας Κ[Μ, Ν] δεν ταξινομείται, καθώς τα ΜxN στοιχεία του πως θα διαταχθούν;

Εγώ θα την έκοβα στο διαγώνισμα. Μερικές Σ/Λ ερωτήσεις στην προετοιμασία μπαίνουν για να μας θυμίζουν κάτι. Μετά τη συζήτηση στην τάξη, θα το θυμούνται οι μαθητές. Και κυρίως θα θυμούνται πως πρέπει να διαβάζουν την ερώτηση και να σκέφτονται.

Άλλο παράδειγμα είναι και η άσκηση 8 στο http://users.kor.sch.gr/ptsiotakis/aepp/aepp_ask3_4.htm
αλλά και το θέμα 4, στα περσινά θέματα του ΟΕΦΕ

sstergou

Αν ταξινομήσω τους φοιτητές ανάλογα με το μέσο όρο και τους βαθμούς τους κατά φθίνουσα σειρά τότε τι γίνεται;

Πόσες διαστάσεις έχω;

Η εντολή

SELECT * FROM users ORDERBY firstname τι κάνει; Δεν ταξινομεί δισδιάστατο πίνακα;

:D ;D >:( 8) :'(

P.Tsiotakis

Στη ΓΛΩΣΣΑ η εντολή   SELECT * FROM users ORDERBY firstname

παραβιάζει την καθοριστικότητα και την αποτελεσματικότητα

:D :o :laugh: ;D :o

sstergou