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

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

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

pgrontas

Νομίζω ότι το πρόβλημα στο συγκεκριμένο παράδειγμα αφορά μόνο την υλοποίηση σε ΓΛΩΣΣΑ. Σε αλγόριθμο γίνεται ή σε μια γλώσσα που επιτρέπει να δημιουργείς έναν πίνακα on the fly, όποτε τον χρειαστείς.
Στον τελικό δισδιάστατο θα αποθηκεύσεις μόνο αυτά που χρειάζεσαι ως απάντηση. Και γιατί στο τέλος χρησιμοποιείς δισδιάστατο; Επειδή θέλεις να αναλύσεις τα δεδομένα σε δύο διαστάσεις - όχι για ταξινόμηση.

Παράθεση από: alkisg στις 17 Μαρ 2008, 10:22:06 ΠΜ
Επειδή από την εκφώνηση πρέπει να θυμηθείς τα δεδομένα για περαιτέρω επεξεργασία σε άλλα υποερωτήματα (π.χ. υποερώτημα β).

Έτσι θα αναγκαστείς να δηλώσεις Μ μονοδιάστατους πίνακες. Δεν μπορείς όμως να δηλώσεις Μ, πρέπει να δηλώσεις συγκεκριμένο αριθμό.
Έτσι δηλώνεις 10 μονοδιάστατους πίνακες, τον Α1, τον Α2, τον Α3 κτλ. Δεν θα τους χρησιμοποιήσεις όμως όλους, αλλά τους Μ πρώτους από αυτούς.

Πώς μπορείς όμως να κάνεις επανάληψη με διαφορετικά ονόματα μεταβλητών; Δεν μπορείς. Χρειάζεσαι δισδιάστατο πίνακα.

Για ακριβώς τον ίδιο λόγο που χρειάζεσαι μονοδιάστατους (=μαθητές), όταν το πρόβλημα έχει και δεύτερη διάσταση (=τμήματα), χρειάζεσαι δισδιάστατους.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

alkisg

Το να πεις ότι δεν χρειαζόμαστε δισδιάστατους αν μπορούμε να δημιουργήσουμε μονοδιάστατους on the fly,
είναι το ίδιο με το να λες ότι δεν χρειαζόμαστε μονοδιάστατους πίνακες αν η γλώσσα που χρησιμοποιούμε μας επιτρέπει να δημιουργούμε μεταβλητές on the fly.

Η απώλεια μνήμης με τη χρήση δισδιάστατου είναι ακριβώς ίδια με την απώλεια μνήμης μονοδιάστατου: εφόσον μας λένε ότι το πολύ θα έχουμε Μ*Ν βαθμούς, η στατική μας δομή πρέπει να έχει Μ*Ν θέσεις.

Αλλάζω την εκφώνηση και δίνω πλέον συγκεκριμένα νούμερα Μ και Ν:
έχουμε ακριβώς 100 τμήματα με ακριβώς 100 μαθητές το κάθε ένα.

Δεν είναι προφανές ότι πρέπει να χρησιμοποιηθεί δισδιάστατος;
Δεν είναι προφανές ότι χρειαζόμαστε ταξινόμηση δισδιάστατου, έστω ανά στήλη;


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

Για τη (γ) υποπερίπτωση όπου στα παραδείγματα μέχρι στιγμής οι γραμμές/στήλες δεν έχουν παρά μόνο χωρική έννοια, αν και πάλι χρειάζεται ταξινόμηση δισδιάστατου, επιφυλάσσομαι να ποστάρω παράδειγμα με "φυσική" έννοια αν και όταν βρω κάποιο.

pgrontas

Παράθεση από: alkisg στις 17 Μαρ 2008, 11:10:39 ΠΜ
Το να πεις ότι δεν χρειαζόμαστε δισδιάστατους αν μπορούμε να δημιουργήσουμε μονοδιάστατους on the fly,
είναι το ίδιο με το να λες ότι δεν χρειαζόμαστε μονοδιάστατους πίνακες αν η γλώσσα που χρησιμοποιούμε μας επιτρέπει να δημιουργούμε μεταβλητές on the fly.
Όχι γιατί θα κρατήσεις όσα θες από τον κάθε μονοδιάστατο.


Παράθεση από: alkisg στις 17 Μαρ 2008, 11:10:39 ΠΜ
Δεν είναι προφανές ότι χρειαζόμαστε ταξινόμηση δισδιάστατου, έστω ανά στήλη;

Εφόσον κάθε 'στήλη' ταξινομείται ΑΝΕΞΑΡΤΗΤΑ, είναι προφανές για μένα ότι δεν χρειάζεται δισδιάστατος.

Όπως είπα και πριν διαφωνούμε. Η διαφωνία μας νομίζω δεν είναι τεχνικό θέμα αλλά είναι θέμα διαφορετικής φιλοσοφίας που έχουμε στην χρησιμότητα ενός δισδιάστατου. Δεν είναι κακό.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

gpapargi

Καλημέρα

Επιτέλους μια θεωρητική κουβέντα με συμμετοχή.

Λοιπόν επειδή η συζήτηση άναψε το ΣΚ δεν την έχω παρακολουθήσει, αλλά έψαχνα μια αφορμή να γράψω μερικές σκέψεις που έκανα μετά την περυσινή κουβέντα.

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

Ας ξεχάσουμε για λίγο τους πίνακες και ας μιλήσουμε μόνο για την έννοια της ταξινόμησης.
Για να υπάρχει ταξινόμηση ν στοιχείων καταρχήν πρέπει να υπάρχει ένα κριτήριο ως προς το οποίο θα συγκριθούν τα στοιχεία. Η πιο απλή περίπτωση είναι να συγκρίνουμε τις τιμές τους. Αλλά δεν υπάρχει λόγος  να περιοριστούμε μόνο σε απλή σύγκριση των τιμών. Μπορεί να θέλουμε να συγκρίνουμε τα τετράγωνα των αριθμών ή τους κύβους τους ή γενικά την τιμή που έχουν μέσω μιας τυχαίας συνάρτησης f. Αυτή η συνάρτηση που αποτελεί το κριτήριο ως προς το οποίο θα γίνει η σύγκριση είναι η ordering function (συνάρτηση διάταξης) που λέει το βιβλίο στον ορισμό της σελίδας 66.

Πχ αν θέλουμε να ταξινομήσουμε τα στοιχεία ανάλογα με το ποιο έχει το μικρότερο ημίτονο τότε η ordering function f είναι η f(x) = ημ(x). Για κάθε αριθμό βρίσκουμε το ημίτονό του και αυτά τα ημίτονα των αριθμών είναι που συγκρίνουμε τελικά και κατατάσσουμε τους αριθμούς.     Αν θέλουμε μια απλή αύξουσα ταξινόμηση (δηλαδή απλώς να συγκρίνουμε τις τιμές των στοιχείων) τότε ουσιαστικά επιλέγουμε σαν ordering function την f(x) = x. Δηλαδή η τιμή (εικόνα) κάθε αριθμού μέσω της ordering function είναι ο ίδιος του ο εαυτός και έτσι πετυχαίνουμε απλά να συγκρίνουμε τις τιμές των στοιχείων (κι ας είναι μέσω της f). Αν θέλουμε να κάνουμε φθίνουσα ταξινόμηση απλά επιλέγουμε σαν ordering function την f(x) = -x και τελικά συγκρίνουμε τα στοιχεία ως προς το πιο έχει τον μικρότερο αντίθετο (άρα ως προς το ποιο είναι το μεγαλύτερο). Η χρήση της ordering function είναι πολύ βολική γιατί δεν χάνουμε αυτά που έχουμε (αύξουσα/φθίνουσα ταξινόμηση) και κερδίζουμε τη δυνατότητα να έχουμε επιλογή ως προς το κριτήριο ταξινόμησης.

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

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

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

Ένα πολύ βασικό στοιχείο που πρέπει να κρατήσουμε είναι το ότι άλλο πράγμα η ordering function δηλαδή το κριτήριο με βάση το οποίο θα ταξινομήσουμε τα στοιχεία (και το βιβλίο τη λέει συνάρτηση διάταξης) και άλλο πράγμα η διάταξη των αποθηκευτικών χώρων. Το ένα καθορίζει ποιο από τα στοιχεία είναι το πρώτο, ενώ το άλλο  καθορίζει σε πιο από τα σημεία θα αποθηκευτεί το πρώτο στοιχείο.

Πάμε τώρα στους πίνακες.

Αν έχουμε ορίσει την ordering function το μόνο που μας μένει είναι η διάταξη των αποθηκευτικών χώρων. Σε ένα μονοδιάστατο πίνακα τα κελιά είναι διατεταγμένα από μόνα τους, οπότε μπορούμε να χρησιμοποιήσουμε τη διάταξη των κελιών του πίνακα σαν διάταξη των αποθηκευτικών χώρων των στοιχείων μας. Κάποιος μπορεί να πει ότι είναι κάπως αυθαίρετο το να χρησιμοποιήσουμε την υπάρχουσα φυσική διάταξη των κελιών του μονοδιάστατου. Γιατί να μη βάλουμε το πρώτο στοιχείο της ταξινόμησης στην πέμπτη θέση του πίνακα, το δεύτερο στην όγδοη κλπ. Σωστό. Αλλά αν χρησιμοποιήσουμε ένα μονοδιάστατο πίνακα για να κρατήσουμε τη διάταξη των κελιών, τότε θα χρησιμοποιηθεί σε αυτόν τον πίνακα-ευρετήριο η φυσική διάταξη του μονοδιάστατου.  Ο μόνος τρόπος να μη χρησιμοποιηθεί η φυσική διάταξη του μονοδιάστατου είναι να ταξινομήσουμε χωρίς εντολή επανάληψης (αλλά με διαδοχικές Αν… τότε αντιμετάθεσε… όσες φορές χρειαστεί. Δηλαδή σαν να μην έχουμε πίνακα αλλά στοιχεία αποθηκευμένα σε μεταβλητές.   

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

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

Εννοείται πως πέρα από αυτά θα πρέπει να υπάρχει και φυσικό νόημα σε ότι γίνεται, πράγμα που επιμελώς παρέκαμψα παραπάνω. Δίνω 2 παραδείγματα:

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

Παράδειγμα 2.
Αν έχουμε σχολική παρέλαση μαθητών βάζουμε τον πιο ψηλό μπρος και αριστερά, τον δεύτερο δίπλα, μετά πας στη δεύτερη γραμμή κλπ Εδώ είναι σα να έχεις μονοδιάστατο αποθηκευμένο σε δισδιάστατο. Δεν έχει κάποια ειδική σημασία η στήλη ή η γραμμή. Μόνο το ύψος μετράει. Έχεις εσωτερική δομή μονοδιάστατου και το φυσικό πρόβλημα σου επιβάλει πίνακα 2 διαστάσεων αφού δε γίνεται οι μαθητές να κάνουν παρέλαση ο ένας πίσω από τον άλλον.

Για μένα τα κρίσιμα σημεία είναι 2:

Το πρώτο είναι να συμφωνήσουμε στο ότι η ordering function δεν ορίζει τη διάταξη κελιών αλλά το κριτήριο με βάση με το οποίο θα γίνει σύγκριση (πχ συγκρίνουμε τα ημίτονά των στοιχείων). Η διάταξη των αποθηκευτικών χώρων είναι κάτι άλλο (επίσης αναγκαίο) και είναι άλλη η συνάρτηση που το καθορίζει αυτό (ενδεχομένως και με τη βοήθεια πίνακα ή και αλγεβρικά).

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

Δεν πλατειάζω άλλο για την ώρα. Έχω ετοιμάσει και παράδειγμα ταξινόμησης μονοδιάστατου με ordering function αλλά φυσική διάταξη κελιών, με διάταξη κελιών διαφορετική της φυσικής αλλά ordering function την f(x)=x και τέλος την πιο σύνθετη περίπτωση με  ordering function κάποια τυχαία f(x)και διάταξη κελιών διαφορετική της φυσικής και ορισμένη μέσω του πίνακα διάταξη_κελιών ή κάποια αλγεβρική g(i). Μάλλον σε επόμενο μήνυμα.

alkisg

#49
Γιώργο συμφωνώ σε όλα, εκτός από αυτό:

Παράθεση από: gpapargi στις 17 Μαρ 2008, 11:44:37 ΠΜ
Ο μόνος τρόπος να μη χρησιμοποιηθεί η φυσική διάταξη του μονοδιάστατου είναι να ταξινομήσουμε χωρίς εντολή επανάληψης (αλλά με διαδοχικές Αν… τότε αντιμετάθεσε… όσες φορές χρειαστεί.

Μπορώ κάλλιστα να χρησιμοποιήσω συνάρτηση διάταξης (εννοώ για τη σειρά τοποθέτησης των στοιχείων, όχι τη συνάρτηση ταξινόμησης). Στο παράδειγμα με τα ονόματα και τα τηλέφωνα,
https://alkisg.mysch.gr/steki/index.php?topic=1240.
η συνάρτηση διάταξης είναι 2*i - 1.
(συμφωνώ κι εγώ όμως ότι θα έπρεπε να χρησιμοποιηθεί δισδιάστατος σ' αυτήν την περίπτωση).

Επίσης θα μπορούσα να χρησιμοποιήσω οποιαδήποτε ένα-προς-ένα και επί συνάρτηση από το [1..Ν] στο [1..Ν], όσα δηλαδή είναι τα στοιχεία του πίνακα.

Φυσικά όλα αυτά όταν το υπαγορεύει το πρόβλημα, όχι αυθαίρετα.

Αλλά ακόμα και μονοδιάστατο-ευρετήριο να χρησιμοποιήσουμε, πάλι ένα-προς-ένα και επί συνάρτηση είναι. Ένας σοβαρός λόγος να χρησιμοποιηθεί αυτή η τεχνική είναι αν τα δεδομένα μας είναι πολύ μεγάλα, και δεν θέλουμε να τα κάνουμε συνεχώς swap, οπότε κάνουμε swap τα στοιχεία του ευρετηρίου.
Π.χ. θέλω να ταξινομήσω ένα μονοδιάστατο από εγγραφές, που έχουν πεδία
όνομα
εικόνα 10Mb

Είναι πολύ πιο λογικό να χρησιμοποιηθεί ευρετήριο (εφόσον δεν έχουμε δυναμικές δομές δεδομένων, δηλαδή η εικόνα να είναι pointer).

Anyway, λεπτομέρεια είναι. Go on!

sstergou

#50
Αυτό το οποίο κωδικοποίησα είναι ταξινόμηση δισδιάστατου πίνακα; (όχι δισδιάστατη ταξινόμηση)
Αν όχι τι είναι ;
Δεν λέω πως είναι, απλα ρωτάω τη γνώμη σας.
:)
Δείτε λίγο αν έχετε χρόνο, και μην βαρέσετε για τυχόν bugs  :), έγινε αρκετά βιαστικά.

Υπάρχει και το αρχείο εισόδου, δεν θα χρειαστεί να γράψετε τίποτε!

http://users.sch.gr/sstergou/sort2d.glo

edit:Περίεργο σε εμένα κατέβαινε.
Έψαξα λίγο δεν μπόρεσα να βρω πως μπαίνει attachment. Τεσπα, τώρα μάλλον διορθώθηκε

alkisg

#51
Στάθη δεν κατεβαίνει το αρχείο, πιθανώς επειδή έχει ελληνική επέκταση και οι browsers δεν τα πάνε και πολύ καλά με τα ελληνικά URL.

Δοκίμασε να το ανεβάσεις εδώ σαν συνημμένο, το SMF το στέλνει με διαφορετικό τρόπο (όχι με URL αλλά σαν http attachment) ή άλλαξέ του την επέκταση σε .glo

edit: απλά πατάς το "Πρόσθετες επιλογές" για να επισυνάψεις αρχείο. Σχετικό θέμα.
Στο ανέβασα εγώ, άμα δεν το θες το σβήνεις.

pgrontas

Γιώργο τα έγραψες πολύ σωστά με τρόπο που κανείς δεν μπορεί να διαφωνήσει.

Ιδιαίτερη σημασία για μένα έχει το παράδειγμα 1. Αυτό κυρίως είχα στο μυαλό μου όταν έλεγα ότι η ταξινόμηση σε δισδιάστατο δεν έχει νόημα. Και νομίζω ότι πλέον έχουμε συμφωνήσει σε αυτό.
Παράθεση από: gpapargi στις 17 Μαρ 2008, 11:44:37 ΠΜ
Μπορούμε όμως να ταξινομήσουμε αλφαβητικά τα ονόματα αντιμεταθέτοντας ολόκληρες τις γραμμές.
To παραπάνω όμως δεν είναι ταξινόμηση των στοιχείων του δισδιάστατου, γιατί η συνάρτηση διάταξης ορίζεται σε στοιχεία εξωτερικά του πίνακα (Υποθέτω ότι ο πίνακας περιέχει βαθμούς και τα ονόματα είναι σε εξωτερικό). Είναι απλά αντιμετάθεση τους για να συμβαδίζουν με την σειρά των δεδομένων που ταξινομούνται.

Το παράδειγμα 2 εγώ το βλέπω λίγο διαφορετικά. Βλέπω μόνο την μονοδιάστατη δομή των υψών που συγκρίνονται. Η διάταξη της παρέλασης, δεν είναι αυτοσκοπός, αλλά προκύπτει αν πάρεις τα ταξινομημένα ύψη και τα χωρίσεις σε 5 άδες πχ. (σε ν-αδες). Η διάταξη σε γραμμές και στήλες προκύπτει ως αποτέλεσμα αυτού του χωρισμού (δεν είναι ο πρωταρχικός μας στοχος). Το ίδιο ισχύει και στο παράδειγμα με τα γάλατα που έφερε ο Άλκης το ΣΚ. Νομίζω όμως οι απόψεις μας είναι ισοδύναμες - και παραδέχομαι ότι αυτό μπορεί να θεωρηθεί ταξινόμηση δισδιάστατου αν ορίσεις την διάταξη των θέσεων του δισδιάστατου, όπως πολύ σωστά έγραψες.

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

gpapargi

Από τη στιγμή που κατέληξα στα παραπάνω (περίπου 1 μήνα μετά την περυσινή κουβέντα) νομίζω πως όλα μπήκαν στη θέση τους, τουλάχιστο μέσα στο μυαλό μου.

Υπάρχουν 2 διαφορετικά πράγματα. Σχηματικά, το ένα είναι η καμπύλη που διατρέχει τα στοιχεία με τη σειρά. Το άλλο είναι το σχήμα που σχηματίζουν οι αποθηκευτικοί χώροι. Μια που είμαστε σε προγραμματιστικά περιβάλλοντα φανταζόμαστε πίνακες που «έχουν σχήμα» ευθύγραμμου τμήματος (μονοδιάστατοι), ορθογωνίου παραλληλογράμμου (δισδιάστατοι), ορθογωνίου παραλληλεπιπέδου (τρισδιάστατοι) και αυτό κάπως περιορίζει τη φαντασία μας σε «τετραγωνισμένα» σχήματα. Μπορούμε να φανταστούμε τους πίνακες να διαλύονται και να απλώνονται τα κελιά τους σε τυχαίες θέσεις. Αυτομάτως γίνεται κατανοητό ότι η ταξινόμηση αφορά τη μονοδιάστατη καμπύλη που διατρέχει τα στοιχεία και όχι το σχήμα που φτιάχνουν οι αποθηκευτικοί χώροι. Ένα παραστατικό παράδειγμα της καμπύλης που σκέφτηκα είναι το ακροβατικό αεροπλάνο που αφήνει καπνό πίσω του. Η καμπύλη που σχηματίζει ο καπνός του είναι μονοδιάστατη, αλλά είναι «embedded» (δε βρήκα καλύτερη λέξη)  μέσα στον τρισδιάστατο χώρο.

Λόγω του ότι είμαστε σε προγραμματιστικό περιβάλλον θα πρέπει να προσγειώσουμε την κουβέντα στους πίνακες με τα «κολλημένα» κελιά τους και τις «ορθές» γωνίες τους. Για μένα λοιπόν για να έχουμε ταξινόμηση σε πίνακα θα πρέπει εκτός από την ordering function (κριτήριο με βάση το οποίο κάνουμε τις συγκρίσεις) να έχουμε και μια διάταξη στα κελιά μας. Σε πίνακα 2 διαστάσεων που θέλουμε να ταξινομήσουμε στη σειρά α[1,1], α[1,2]… α[1,ν], α[2,1] κλπ φαντάζομαι την καμπύλη να ενώνει τα στοιχεία της πρώτης γραμμής και μετά να πηγαίνει από κάτω ενώνοντας το α[1,ν] με το α[2,1]. Εναλλακτικά μπορούμε να φανταστούμε τον πίνακα να αποσυναρμολογείται και να ξανασυναρμολογείται έτσι ώστε η δεύτερη γραμμή να κολλήσει δίπλα στην πρώτη φτιάχνοντας τελικά ένα μονοδιάστατο πίνακα. Δηλαδή από μαθηματική άποψη το θέμα είναι τοπολογικό (τι συνδέεται με τι αδιαφορώντας για ακριβές σχήμα και αποστάσεις στην καμπύλη) και όχι γεωμετρικό (όπου μας νοιάζει το ακριβές σχήμα και οι αποστάσεις)
Σε ταξινόμηση κάθε στήλης χωριστά, έχουμε πολλές διαφορετικές καμπύλες, μια ανά στήλη.

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

Νομίζω πως στην ουσία συμφωνούμε.

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

Φυσικά συμφωνώ στο ότι μια τέτοια συνάρτηση διάταξης κελιών είναι 1 προς 1 και επί από το [1..Ν] στο [1..Ν].  Και μάλιστα είναι ακολουθία (περιορισμός της στο [1..Ν]) αφού παίζουμε με ακεραίους.

alkisg

Επομένως συμφωνούμε όλοι ότι εφόσον οριστούν
α) Μια σειρά προσπέλασης των στοιχείων ενός δισδιάστατου πίνακα, και
β) Μια συνάρτηση ταξινόμησης (ordering function) f(A[i,j])
τότε ορίζεται και η ταξινόμηση δισδιάστατου πίνακα;

Πολύ θετικό αυτό, αυτός εξάλλου είναι και ο σκοπός που ξεκίνησε το θέμα.




Γιώργο συνεχίζουμε να διαφωνούμε σχετικά με τη διάταξη κελιών σε μονοδιάστατο, αλλά δεν αξίζει τον κόπο καν να το συζητήσουμε, είναι ...φιλοσοφικό! Εγώ θεωρώ ότι σε ένα ευρετήριο "χρησιμοποιούμε" τη φυσική διάταξη των κελιών του ευρετηρίου όσο και τη φυσική διάταξη των ακεραίων σε ένα μετρητή, δηλαδή χωρίς να είναι μέρος της ταξινόμησης: και ο μετρητής πάει από το 1 ως το Ν, και τα κελιά από το 1 ως το Ν.
Η "καμπύλη" που περνάει από όλα τα στοιχεία που μας ενδιαφέρει είναι αυτή η καμπύλη που περνάει από τον πίνακα των δεδομένων (=ονόματα, εικόνες κτλ), όχι αυτή που περνάει από το ευρετήριο. Αυτή είναι η σειρά της ταξινόμησης. Στο ευρετήριο και ζιγκ-ζαγκ να έκανε η καμπύλη δεν θα μας ενδιέφερε, αρκεί και μόνο στον πίνακα δεδομένων να πέρναγε από τα στοιχεία με τη σωστή σειρά ώστε να είναι ταξινομημένα
(και φυσικά αρκεί να καταφέρναμε και τον μετρητή i να κάνει τα ίδια ζιγκ-ζαγκ)! :)

gpapargi

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

Υπάρχουν 2 πράγματα: ο ένα είναι το φυσικό μοντέλο και το δεύτερο είναι η αφηρημένη δομή δεδομένων του δισδιάστατου πίνακα.
Για το φυσικό μοντέλο τα πάντα εξαρτώνται καθαρά από το φυσικό πρόβλημα. Πχ αν σε πίνακα οι γραμμές συμβολίζουν μαθητές και οι στήλες μαθήματα τότε δεν έχει νόημα να γίνει ταξινόμηση. Η φυσική περιγραφή θα καθορίσει αν κάτι έχει νόημα.

Εγώ θεωρώ ότι η κουβέντα μας αφορά την αφηρημένη δομή δεδομένων του δισδιάστατου πίνακα απαλλαγμένη τελείως από οποιαδήποτε φυσική περιγραφή.
Αν οριστεί:
1) συνάρτηση ταξινόμησης (ordering function) f(A[i,j])
2) συνάρτηση διάταξης κελιών g(i,j) που είναι 1-1 και επί και της δίνεις συντεταγμένες του κελιού στον πίνακα 2 διαστάσεων και σου δίνει τη διάταξη του κελιού

Τότε ΝΑΙ μπορεί να οριστεί η ταξινόμηση πάνω στην ΑΔΔ του δισδιάστατου πίνακα.

Για την υλοποίηση μπορεί να χρησιμοποιηθεί ένας αλγόριθμος ταξινόμησης μονοδιάστατου πίνακα. Για να βρεθεί η θέση του στοιχείου του πίνακα 2 διαστάσεων που θα μπει πχ στον αλγόριθμο φυσαλίδας θα χρειαστεί η αντίστροφη συνάρτηση της g, η g-1, που της δίνεις αριθμό και σου επιστρέφει το ζεύγος συντεταγμένων του δισδιάστατου πίνακα. (Επειδή είναι 1-1 και επί υπάρχει η g-1 ).

Για να απαντήσουμε και στην bookitsa… δεν είναι σωστό να λέμε «ταξινομήστε τον δισδιάστατο πίνακα». Θα πρέπει να ορίσουμε σε ποια θέση του δισδιάστατου πίνακα θα μπει το πρώτο στοιχείο, σε ποια το δεύτερο κλπ. Δεν είναι δεδομένο ότι η ταξινόμηση θα γίνει κατά γραμμές. Μπορεί να γίνει κατά στήλες, ή ζιγκ ζαγκ ή σπειροειδώς ή τελείως τυχαία μέσω μιας οποιασδήποτε διάταξης των κελιών του δισδιάστατου. Εννοείται πως το να ταξινομηθεί κάθε στήλη χωριστά σε πίνακα α[ν,μ] δεν είναι μια ταξινόμηση αλλά μ διαφορετικές ταξινομήσεις. Σε ένα πίνακα α[ν,μ] (που έχει δηλαδή ν*μ στοιχεία) υπάρχουν (ν*μ)! (δηλαδή ν επί μ παραγοντικό = 1*2*3*.. * … ν*μ) διαφορετικές διατάξεις κελιών… όσες είναι όλες οι διαφορετικές μεταθέσεις που γίνονται σε ν*μ στοιχεία. Το να κάνουμε ταξινόμηση κατά γραμμή (επειδή έτσι διαβάζει ο άνθρωπος ένα βιβλίο) λύνουμε μια πολύ ειδική και... κυρίως... μια πολύ πολύ βολική περίπτωση του προβλήματος.

Το τελευταίο θέμα που συζητάμε 2 μας Άλκη (η λεπτομέρεια) και σχετίζεται με αυτά είναι το εξής:
Για να ταξινομήσουμε μονοδιάστατο πίνακα πρέπει να ορίσουμε και εκεί διάταξη κελιών; Αυθαιρετούμε αν δεχτούμε τη φυσική σειρά; Όντως είναι λεπτομέρεια… δε μας χαλάσει τη συνταγή στα παραπάνω. Πιστεύω πως δεν αυθαιρετούμε γιατί η διάταξη των κελιών ενός μονοδιάστατου είναι ορισμένη όπως ακριβώς είναι ορισμένη και διάταξη στους ακεραίους. Η φυσική διάταξη είναι συνυφασμένη με τη δομή του μονοδιάστατου. Αδύνατον να γίνει χρήση επαναληπτικής εντολής χωρίς αυτή. Αν το θεωρήσουμε αυθαίρετο, τότε είναι αδύνατο να έχουμε ένα καλώς ορισμένο πρόβλημα σε όλα τα επίπεδα, αφού θα αυθαιρετήσουμε στο ευρετήριο. Για να έχουμε καλώς ορισμένο πρόβλημα θα πρέπει να έχουμε μια άποψη/γνώμη που να μας δίνει τρόπο να ορίσουμε ένα πρόβλημα «καλώς» σε όλα τα επίπεδα. Και στη συνάρτηση διάταξης των κελιών του δισδιάστατου κάναμε χρήση της φυσικής διάταξης του μονοδιάστατου. Ίσως φανεί λίγο περίεργο αυτό που θα πω αλλά θεωρώ πως στον μονοδιάστατο πίνακα το α[1] είναι πριν το α[2], ενώ στο δισδιάστατο το α[1,1] δεν είναι πριν το α[1,2]. Το ίδιο ακριβώς συμβαίνει και στους αριθμούς: Στην ευθεία των πραγματικών το 1 είναι πριν το 2, αλλά στο επίπεδο το (1,0) δεν είναι πριν το (2,0).


Παράθεση από: alkisg στις 18 Μαρ 2008, 03:13:38 ΜΜ
Πολύ θετικό αυτό, αυτός εξάλλου είναι και ο σκοπός που ξεκίνησε το θέμα.

Πράγματι... αισθάνομαι και εγώ ότι μετά από πολύ κόπο φτάσαμε σε μια άποψη που εμένα τουλάχιστο με ικανοποιεί.

pgrontas

Εγώ είμαι διστακτικός στο να συμφωνήσω, γιατί θεωρώ ότι ο κύριος λόγος ύπαρξης ενός δισδιάστατου πίνακα είναι το φυσικό μοντέλο (η διαφορά φιλοσοφίας που είπα νωρίτερα), και κατά συνέπεια ένα ΝΑΙ στην αρχική ερώτηση μπορεί να είναι υπεραπλουστευτικό.

Πάντως αν δούμε εντελώς αφηρημένα τον δισδιάτατο πίνακα, σίγουρα είναι δυνατή η ταξινόμηση του μέσω της συνάρτησης διάταξης των κελιών.
(άλλωστε η συνάρτηση διάταξης κελιών μπορεί να θεωρηθεί ως ένας γρήγορος τρόπος μετατροπής του σε μονοδιάστατο >:D).

Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

gpapargi

Παράθεση από: pgrontas στις 19 Μαρ 2008, 12:08:38 ΜΜ
Πάντως αν δούμε εντελώς αφηρημένα τον δισδιάτατο πίνακα, σίγουρα είναι δυνατή η ταξινόμηση του μέσω της συνάρτησης διάταξης των κελιών.

Αυτό συζητάμε. Την ταξινόμηση στην αφηρημένη δομή δεδομένων του δισδιάστατου πίνακα

Παράθεση από: pgrontas στις 19 Μαρ 2008, 12:08:38 ΜΜ
(άλλωστε η συνάρτηση διάταξης κελιών μπορεί να θεωρηθεί ως ένας γρήγορος τρόπος μετατροπής του σε μονοδιάστατο  >:D).

Κανένα απολύτως πρόβλημα. Είναι όπως στη φυσική μπορείς να επιλέξεις το σύτημα αναφοράς που σε βολεύει να περιγράψεις καλύτερα ένα φαινόμενο. Αν θέλεις μπορείς να θεωρήσεις ακίνητη τη γη και κινούμενο το αυτοκίνητο, ή αν είναι πιο βολικό μπορείς να λύσεις το πρόβλημα στο σύτημα αναφοράς του αυτοκινήτου θεωρώντας το ακίνητο και τη γη κινουμενη. Υπάρχουν προβλήματα συνάντησης κινητών που λύνονται πολύ απλούστερα στο δεύτερο σύστημα αναφοράς.

Παράθεση από: pgrontas στις 19 Μαρ 2008, 12:08:38 ΜΜ
Εγώ είμαι διστακτικός στο να συμφωνήσω, γιατί θεωρώ ότι ο κύριος λόγος ύπαρξης ενός δισδιάστατου πίνακα είναι το φυσικό μοντέλο (η διαφορά φιλοσοφίας που είπα νωρίτερα), και κατά συνέπεια ένα ΝΑΙ στην αρχική ερώτηση μπορεί να είναι υπεραπλουστευτικό.

Είμαι υπέρ του να συνδυάζουμε και τα 2 και κακίζω με κάθε ευκαιρία τους μαθηματικούς στην Ελλάδα που έχουν αποκόψει τα μαθηματικά από τα φυσικά προβλήματα στα οποία αναδεικνύονται.
Προσοχή όμως. Είναι 2 διαφορετικά πράγματα. Και είναι πολύ βολικό να ξέρουμε πιο ακριβώς είναι το αφηρημένο μαθηματικό μοντέλο (εδώ η επεξεργασία της αφηρημένης δομής δεδομένων) που κρύβεται πίσω από το φυσικό μας πρόβλημα. Αυτό μας οδηγεί στο να μπορούμε να λύνουμε μονομιάς πολλά προβλήματα που αν και δείχνουν διαφορετικά (στη φυσική περιγραφή) έχουν ακριβώς το ίδιο αφηρημένο μαθηματικό μοντέλο από πίσω τους.

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

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

Έχουμε λοιπόν 2 διαφορετικά φυσικά μοντέλα (το ένα μαθητές, μαθήματα και βαθμούς και το άλλο πόλεις, ημερες και θερμοκρασίες) που έχουν όμως ακριβώς το ίδιο μοντέλο πίσω τους. Και οι 2 ερωτήσεις κάνουν ακριβώς την ίδια επεξεργασία δηλαδή εύρεση μέσου όρου κατά γραμμή. Τα 2 προβλήματα είναι ισομορφικά... είναι το ίδιο πρόβλημα. Αν λύσεις το ένα λύνεις και το άλλο.

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

Στη φυσική αυτό είναι πολύ συχνό φαινόμενο. Βλέπεις 2 τελείως διαφορετικά φαινόμενα που... παραδόξως... περιγράφονται από την ίδια διαφορική εξίσωση (πχ ταλαντώσεις και κυκλώματα RLC αν θυμάμαι καλά). Τρομερά χρήσιμο ως προς τις κρυμμένες ιδιότητες του συστήματος. 

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

alkisg

Γιώργο συνέχισα στο παλιό μας θέμα
https://alkisg.mysch.gr/steki/index.php?topic=794.msg8414#msg8414
απλά για το χαβαλέ, αν έχεις όρεξη το συζητάμε εκεί...

Δεν ήθελα να χαλάσουμε το παρόν θέμα, το οποίο έχει πιο άμεση σχέση με το μάθημα.

pgrontas

Γιώργο, κανένας δεν είναι ενάντια στην χρήση αφηρημένων μοντέλων.

Το πρόβλημα είναι ότι μπορούν να μας μπερδέψουν κάποιες φορές, αν χάσουμε την επαφή με την πραγματικότητα. Στο παράδειγμα μας, το αφαιρετικό μοντέλο του δισδιάστατου πίνακα ταξινομείται, αλλά δεν συμβαίνει το ίδιο με όλους τους δισδιάστατους πίνακες που μπορεί να συναντήσεις στα διάφορα προβλήματα (πχ. μαθητές -  μαθήματα - βαθμοί).

Στην περίπτωση αυτή μπορεί να θεωρηθεί ότι το μοντέλο παρουσιάζει 'διαρροή' (o όρος είναι δανεισμένος από αυτό το πολύ γλαφυρό άρθρο   http://www.joelonsoftware.com/articles/LeakyAbstractions.html)

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

Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson