Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού πακέ

Ξεκίνησε από pgrontas, 10 Φεβ 2010, 05:41:06 ΜΜ

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

Η συγχώνευση (merge)

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

pgrontas

Για να έχουμε όλες τις ασάφειες μαζεμένες ας συζητήσουμε και το θέμα της συγχώνευσης πινάκων:

Μία πολύ ωραία συζήτηση είχε γίνει εδώ, μετά από ερώτηση συναδέλφου
https://alkisg.mysch.gr/steki/index.php?topic=1147.0
Όλες οι ιδέες έχουν εκφραστεί εκεί.

Ανακεφαλαιώνοντας, τα ερωτήματα που υπάρχουν είναι:
-Η συγχώνευση αφορά μόνο ταξινομήμενους πίνακες;
-Οι όροι συγχώνευση και συνένωση είναι ισοδύναμοι - μπορώ να ονομάσω συγχώνευση το κόλλημα δύο πινάκων - τον έναν μετά το άλλο (συνένωση-concatenation,appending) ή η συγχώνευση είναι κάτι επιπλέον.

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

sstergou

Προτείνω αυτό που περιγράφεται εδώ :
http://en.wikipedia.org/wiki/Merge_algorithm

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

Το ίδιο αναφέρεται και στο βιβλίο του knuth ότι δηλαδή μιλάμε για ταξινομημένες λίστες.

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

Laertis

Συμφωνώ με τον Στάθη. Ας κρατήσουμε τον όρο συνένωση για το απλό "κόλλημα" δύο πινάκων.
Νικολακάκης Γιώργος
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής
http://users.sch.gr/gnikola

tom

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

http://courses.csail.mit.edu/6.006/fall09/lecture_notes/lecture08.pdf

http://www.cs.rpi.edu/~musser/gp/algorithm-concepts/merge-algorithms-screen.pdf

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


Οπότε η γνώμη μου...

Όταν λέμε συγχώνευση να εννοούμε την δημιουργία ταξηνομημένης λίστας/δομής

Όταν λέμε συνένωση να εννοούμε την παράθεση των στοιχείων μιας λίστας/δομής πίσω από τα στοιχεία της άλλης:

Α=[12, 7, 48, 3] Β=[11, 2, 9, 60]

merge(Α, Β) --> Γ[2, 3, 7, 9, 11, 12, 48, 60]
concat(A, B) -->Γ[12, 7, 48, 3, 11, 2, 9, 60]
concat(Β, Α) --> Γ[11, 2, 9, 60, 12, 7, 48, 3]


Θωμάς Σκυλογιάννης

- Ζήσε σα να' ταν να πεθάνεις αύριο. Μάθε σα να' ταν να ζεις για πάντα.
                                                                                     Μαχάτμα Γκάντι

poursali

Παράθεση από: tom στις 10 Φεβ 2010, 08:45:15 ΜΜ
Οπότε η γνώμη μου...

Όταν λέμε συγχώνευση να εννοούμε την δημιουργία ταξηνομημένης λίστας/δομής

Όταν λέμε συνένωση να εννοούμε την παράθεση των στοιχείων μιας λίστας/δομής πίσω από τα στοιχεία της άλλης:

Α=[12, 7, 48, 3] Β=[11, 2, 9, 60]

merge(Α, Β) --> Γ[2, 3, 7, 9, 11, 12, 48, 60]
concat(A, B) -->Γ[12, 7, 48, 3, 11, 2, 9, 60]
concat(Β, Α) --> Γ[11, 2, 9, 60, 12, 7, 48, 3]

συμφωνω εν μερει. Ο προβληματισμος μου ειναι ο εξης. Αν δωσεις τους παραπανω πινακες Α, Β και πεις "καντε συγχωνευση" το θεωρεις αρκετο για να τους παρουσιασει κανεις ταξινομημενους? νομιζω ειναι καλο να αναφερεται σε συνδυασμο ή με την αναφορα οτι θα πρεπει το αποτελεσμα να ειναι ταξινομημενο ή εστω να υπονοειται απο τη φυση του προβληματος που τιθεται.
μετρον αριστον
είμαι τζαμπατζής, χρησιμοποιώ λίνουξ

tom

Παράθεση από: poursali στις 10 Φεβ 2010, 09:04:27 ΜΜ
συμφωνω εν μερει. Ο προβληματισμος μου ειναι ο εξης. Αν δωσεις τους παραπανω πινακες Α, Β και πεις "καντε συγχωνευση" το θεωρεις αρκετο για να τους παρουσιασει κανεις ταξινομημενους? νομιζω ειναι καλο να αναφερεται σε συνδυασμο ή με την αναφορα οτι θα πρεπει το αποτελεσμα να ειναι ταξινομημενο ή εστω να υπονοειται απο τη φυση του προβληματος που τιθεται.

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

Θωμάς Σκυλογιάννης

- Ζήσε σα να' ταν να πεθάνεις αύριο. Μάθε σα να' ταν να ζεις για πάντα.
                                                                                     Μαχάτμα Γκάντι

gthal

Νομίζω συμφωνούμε όλοι ως προς τον όρο συνένωση.

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

Γι αυτό, στο παράδειγμα του @tom  την merge(Α, Β) δεν θα την έλεγα συγχώνευση (οι Α, Β δεν είναι ταξινομημένοι). Εδώ έχουμε :
concat(A, B)-->Γ
bubblesort(Γ)-->Γ'
Φιλικά,
Γιώργος Θαλασσινός

tom

#7
Παράθεση από: gthal στις 11 Φεβ 2010, 05:31:49 ΜΜ
Γι αυτό, στο παράδειγμα του @tom  την merge(Α, Β) δεν θα την έλεγα συγχώνευση (οι Α, Β δεν είναι ταξινομημένοι). Εδώ έχουμε :
concat(A, B)-->Γ
bubblesort(Γ)-->Γ'
Έχεις δίκιο. Βιάστηκα και παρουσίασα τους  πίνακες αταξινόμητους. 

Εννοούσα αυτό:

Α=[3, 7, 12, 48] Β=[2, 9, 11, 60]

merge(Α, Β) --> Γ[2, 3, 7, 9, 11, 12, 48, 60]
concat(A, B) -->Γ[3, 7, 12, 48, 2, 9, 11, 60]
concat(Β, Α) --> Γ[2, 9, 11, 60, 3, 7, 12, 48]

Βέβαια νομίζω ότι προέκυψε νέα περίπτωση... :)
Οπότε την παραπάνω περίπτωση πως θα την έλεγε κάποιος ;) :D
Θωμάς Σκυλογιάννης

- Ζήσε σα να' ταν να πεθάνεις αύριο. Μάθε σα να' ταν να ζεις για πάντα.
                                                                                     Μαχάτμα Γκάντι

evry


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

gthal

Φιλικά,
Γιώργος Θαλασσινός

tom

Για αυτή την ασάφεια νομίζω έχουμε καταλήξει. Με τις άλλες να δούμε τι θα γίνει... :)
Θωμάς Σκυλογιάννης

- Ζήσε σα να' ταν να πεθάνεις αύριο. Μάθε σα να' ταν να ζεις για πάντα.
                                                                                     Μαχάτμα Γκάντι