συγχώνευση πινάκων

Ξεκίνησε από Αλεξόπουλος Ανδρέας, 28 Νοε 2007, 01:59:35 ΜΜ

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

Αλεξόπουλος Ανδρέας

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

Να γραφεί αλγόριθμος που να διαβάζει δυο μονοδιάστατους πίνακες ακεραίων Α και Β με διαστάσεις Μ και Ν αντίστοιχα και να συγχωνεύει τους πίνακες σε έναν καινούριο πίνακα Γ.

δεδομένου ότι οι πίνακες Α και Β δεν είναι απαραίτητα ταξινομημένοι, η εκφώσηση είναι λάθος, σωστά;

Β) σε συνέχεια του προηγούμενου, αν απλώς θέλουμε να ενώσουμε δυο πίνακες (δηλαδή να "κολλήσουμε" τον Β μετά από τον Α), ποια είναι η σωστή εκφώνηση για την άσκηση; χρησιμοποιώντας το ρήμα "ενώνω" είμαστε σωστοί ή πρέπει να το περιγράψουμε την λειτουργία αυτή με άλλο τρόπο;

ευχαριστώ,
Ανδρέας.

gpapargi

Παράθεση από: aalexop στις 28 Νοε 2007, 01:59:35 ΜΜ
Να γραφεί αλγόριθμος που να διαβάζει δυο μονοδιάστατους πίνακες ακεραίων Α και Β με διαστάσεις Μ και Ν αντίστοιχα και να συγχωνεύει τους πίνακες σε έναν καινούριο πίνακα Γ.

Θα έλεγα "μέγεθος Μ και Ν" και όχι "διαστάσεις Μ και Ν" γιατί η διάσταση είναι 1 για τους μονοδιάστατους και 2 για τους δισδιάστατους.

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

Αλεξόπουλος Ανδρέας

Παράθεση από: gpapargi στις 29 Νοε 2007, 12:37:24 ΜΜ
Θα έλεγα "μέγεθος Μ και Ν" και όχι "διαστάσεις Μ και Ν" γιατί η διάσταση είναι 1 για τους μονοδιάστατους και 2 για τους δισδιάστατους.

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

σ' ευχαριστώ για την απάντηση και για την παρατήρηση πως το σωστό είναι μέγεθος και όχι διάσταση. Άρα η εκφώνηση όπως την έγραψα στο ερώτημα Α δεν είναι σωστή και καλό είναι να αποφεύγεται.

P.Tsiotakis

Σελίδα 55:
Συγχώνευση: δυο ή περισσότερες δομές συνενώννται σε μια ενιαία δομή.

Σελίδα 200:
Συγχώνευση: η δημιουργία απο τα στοιχεία δυο ή περισσοτέρων ταξινομημένων πινάκων ενός άλλου, που είναι και αυτός ταξινομημένος.

Σελ 94 βιβλίου καθηγητή:
Ειδικότερα έχει μελετηθεί το πρόβλημα της συγχώνευσης δυο, τριών ή τεσσάρων ταξινομημένων πινάκων σε ένα τρίτο ταξινομημένο πίνακα. Θεωρείται οτι στην είσοδο δίνονται ταξινομημένοι πίνακες... Στη συνέχεια δίνεται ένας απλός (??) αλγόριθμος ...

Δηλαδή το παρακάτω δεν είναι συγχώνευση;


3.2.Ασκ9  http://users.kor.sch.gr/ptsiotakis/aepp/aepp_ask3_2.htm

Απ΄όσο θυμάμαι οι δισδιάστατοι πίνακες, δεν ταξινομούνται;

Αν θέλετε μπορούμε να το λέμε συνένωση, στο εξής...

Michael

Χαίρομαι που τίθεται έτσι το ζήτημα, γιατί πραγματικά είναι ένα από τα ερωτήματα που με απασχολούν εδώ και αρκετό καιρό.
Από το σχολικό βιβλίο καταλαβαίνω ότι η λειτουργία της συγχώνευσης πινάκων, δεν ταυτίζεται με αυτό που θα μπορούσαμε να ονομάσουμε "συνένωση". Από την άλλη, το βιβλίο δεν αναφέρει καμία επεξεργασία "συνένωσης" μη ταξινομημένων πινάκων. Που σημαίνει ότι αν τη συγχώνευση (πινάκων) τη δούμε με τη στενή έννοια του ορισμού του σχολικού βιβλίου, τότε προκύπτει το συμπέρασμα ότι η "συνένωση" αταξινόμητων πινάκων είναι αδύνατη ( :o), και σε κάθε περίπτωση, εκτός ύλης... Έχω άδικο?

alkisg

Προσωπική γνώμη: Το "συγχώνευση" δεν αναφέρεται μονοσήμαντα σε ταξινομημένες δομές. Όταν συγχωνεύονται δύο εταιρίες, δεν είναι αναγκαστικά ταξινομημένες. :)
Σύμφωνοι, επειδή ο όρος merge απαντάται κυρίως μαζί με το sort, θα απέφευγα να τη χρησιμοποιήσω όταν δεν τίθεται θέμα ταξινόμησης και θα χρησιμοποιούσα κάποια παραπλήσια λέξη, π.χ. συνένωση. Αλλά δεν θα θεωρούσα προφανές το "να συγχωνευτούν δύο πίνακες", θα το έλεγα αναλυτικά, "να συγχωνευτούν δύο ταξινομημένοι πίνακες σε έναν τρίτο ταξινομημένο πίνακα".

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

gpapargi

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

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

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

Για το θέμα της ταξινόμησης μονοδιάστατων από ότι θυμάμαι ʼλκη πέρυσι δεν υπήρχε διαφωνία ως προς τον ορισμό της συνάρτησης ταξινόμησης (πχ αν θα ταξινομήσουμε ανάλογα με το ποιος έχει τη μεγαλύτερη τιμή f(x)=x ή ποιος έχει το μεγαλύτερο τετράγωνο f(x)=x^2),  αλλά ως προς τη διάταξη των κελιών του πίνακα.
Το θέμα είναι ενδιαφέρον αλλά νομίζω ότι κινδυνεύουμε να απομακρυνθούμε από αυτό που συζητάμε τώρα. Η αρχική έντασή μου τότε ήταν ότι στα κελιά του δισδιάστατου πίνακα δεν υπάρχει ούτε η φυσική διάταξη (δεν ξέρουμε αν προηγείται το α[1,2] ή το α[2,1] και πρέπει να οριστεί) ενώ στους μονοδιάστατους υπάρχει τουλάχιστον η φυσική διάταξη (το α[1] προηγείται του α[2]) έστω κι αν αυθαιρετούμε που τη θεωρούμε δεδομένη (αυτό ήταν το θέμα συζήτησης τότε και είναι μάλλον ανοικτό).

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

Michael

Σύμφωνοι, όμως, μεταξύ σοβαρού και αστείου, ας κάνω για λίγο το συνήγορο του διαβόλου.
Ξεκινώ κατ' αρχήν με την υπόθεση ότι ούτε στο βιβλίο, ούτε στο τετράδιο μαθητή υπάρχει αλγόριθμος "συνένωσης" αταξινόμητων πινάκων (μπορεί και να υπάρχει, απλώς δεν θυμάμαι αυτή τη στιγμή να έχω δει κάτι τέτοιο).
Στη σελ.55, η συγχώνευση δομών δεδομένων δείχνει να ταυτίζεται με τη "συνένωση". Όμως στη σελ.200 η συγχώνευση σε κάποιες συγκεκριμένες δομές δεδομένων (πίνακες), δείχνει να παίρνει μια πιο ειδική μορφή (πρέπει να είναι ταξινομημένοι).
Από τη στιγμή που ως αναγνώστης του σχολικού βιβλίου δεν βλέπω να υπάρχει κάποια επεξεργασία "συνένωσης" αταξινόμητων πινάκων, βγάζω το συμπέρασμα ότι η απλή "συνένωση", ίσως και να ορίζεται για όλες τις υπόλοιπες δομές δεδομένων, όχι πάντως για τους πίνακες. Άρα, αν στις εξετάσεις μου ζητήσουν να "συνενώσω" πίνακες, θα έχω το δικαίωμα να ζητήσω διευκρίνηση από την επιτροπή εξετάσεων σχετικά με το τι ακριβώς εννοούν με το "συνένωση". Δεν πρόκειται για κάποια γνωστή επεξεργασία...
Από την άλλη, αν μου ζητήσουν να "συγχωνεύσω" αταξινόμητους πίνακες, υπάρχει δρόμος "εντός ύλης"! Θα "εννοούν" ότι πρέπει να ταξινομήσω τον Α, να ταξινομήσω τον Β, και μετά να τους συγχωνεύσω με τον "επίσημο" αλγόριθμο συγχώνευσης  :D!

MichaelP

Αγαπητοί,
Επειδή πραγματικά έχω μπερδευτεί, παρακαλώ τους παλαιότερους του forum, να επαναλάβουν τη σκέψη τους με σαφήνεια (χωρίς απαραίτητα αιτιολογία) για τα παρακάτω:

1. Κατά τη γνώμη τους, η διαδικασία συγχώνευσης (όσων αφορά σε πίνακες) είναι διαδικασία που επιτρέπεται να πραγματοποιηθεί ΜΟΝΟ και ΑΠΟΚΛΕΙΣΤΙΚΑ σε ταξινομημένους πίνακες (μονοδιάστατους, δισδιάστατους κτλ) --> (ΝΑΙ / ΟΧΙ)?
2.  Ο τελικός πίνακας πρέπει να είναι απαραίτητα ταξινομημένος -->(ΝΑΙ / ΟΧΙ)?
3. Αν ο τελικός πίνακας πρέπει να είναι ταξινομημένος και προερχόμενος από δύο ταξινομημένους πίνακες, γιατί η διαδικασία ταξινόμησης του τελικού πίνακα, πρέπει να γίνει με κάποιο "νόμιμο ή "επίσημο" αλγόριθμο ταξινόμησης ?

Προσωπική Άποψη:

Αγαπητοί,
Κατά την ταπεινή μου άποψη, το πραγματικό πρόβλημα ξεκινά από το γεγονός ότι το σχολικό βιβλίο αφήνει ασαφές και σκοτεινό το εν' λόγω ζήτημα. Αν δεν υπήρχε αυτή η (2-3 γραμμών) αναφορά στη σελίδα 200, όλοι θα συγχωνεύαμε τους πίνακες εντελώς αταξινόμητους και μετά στον τελικό πίνακα θα κάναμε ότι θέλαμε (ταξινόμηση, αναστροφή, διαγωνιοποίηση κτλ). Πραγματικά αδυνατώ να κατανοήσω την πραγματική ωφέλεια από την ταξινόμηση πριν ή ακόμα και μετά τη συγχώνευση, όταν δεν είναι απαραίτητο σε κάποια ύστερη λειτουργία του προγράμματος που αναπτύσσουμε. Ας μην ξεχνάμε ότι η ουσία είναι η ανάπτυξη ενός αποδοτικού κώδικα. Αν είναι απαραίτητο, για τη βελτίωση της αποδοτικότητας του κώδικα, η ταξινόμηση του πίνακα (πχ έπεται αναζήτηση), τότε να την κάνουμε 101 φορές. Αλλά δεν καταλαβαίνω την ουσία της τυπολαγνίας που μας καταβάλει στο αν ο τελικός ή οι αρχικοί πίνακες (!) πρέπει να είναι ή όχι ταξινομημένοι. Πραγματικά, μήπως γνωρίζεται κάποιο μαθηματικό θεώρημα που να λέει ότι η συγχώνευση πινάκων απαιτεί ταξινομημένους αρχικούς πίνακες? Προσωπικά δεν γνωρίζω κάτι σχετικό (δεν ξέρω αν ο Cantor έχει κάτι να μας πεί).
Στα μαθηματικά αυτή η τυπολατρία έχει πολύ σοβαρό ΚΑΙ ΟΥΣΙΑΣΤΙΚΟ νόημα : Αν δεν ακολουθηθούν οι νόμοι και οι κανόνες των θεωρημάτων των μαθηματικών τότε είναι μαθηματικά βέβαιο ότι θα οδηγηθούμε σε λογικά σφάλματα και θα προκύψουν εσφαλμένα ΕΠΙΚΥΝΔΥΝΑ πορίσματα.
Το ίδιο δεν ισχύει στον προγραμματισμό γιατί πολύ απλά δεν υπάρχουν δεδομένοι δρόμοι (γενικά θεωρήματα) ανάπτυξης αλγορίθμων.
Αν οι παλαιότεροι έχουν να προσθέσουν κάτι, θα χαρώ να τους ξανακούσω, παρότι πράγματι έχουν ειπωθεί αρκετά.

Πολλά συγχαρητήρια για το Forum, για τα θέματα που συζητάτε όπως και στον ʼλκη για τη "Γλώσσα".

Με τιμή
Μιχάλης Π.

gpapargi

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

Το να τους κολλήσεις (τον ένα μετά τον άλλο) είναι αντίστοιχο με τη λειτουργία των strings που λέγεται concatenation (συνένωση).

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

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

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

pgrontas

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