Το Στέκι των Πληροφορικών

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

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

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

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

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

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

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

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

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

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

http://courses.csail.mit.edu/6.006/fall09/lecture_notes/lecture08.pdf (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 (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]

Παράθεση από: 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]

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

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

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

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

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

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

Παράθεση από: 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

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

Οκ, καλύφθηκα. Συμφωνούμε  :)

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