Ψηφοφορία

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

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

Αποστολέας Θέμα: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού πακέ  (Αναγνώστηκε 3375 φορές)

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1429
  • There are always possibilities...
Για να έχουμε όλες τις ασάφειες μαζεμένες ας συζητήσουμε και το θέμα της συγχώνευσης πινάκων:

Μία πολύ ωραία συζήτηση είχε γίνει εδώ, μετά από ερώτηση συναδέλφου
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

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 983
  • Program or be Programmed
    • pseudoglossa.gr
Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
« Απάντηση #1 στις: 10 Φεβ 2010, 06:18:08 μμ »
Προτείνω αυτό που περιγράφεται εδώ :
http://en.wikipedia.org/wiki/Merge_algorithm

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

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

Δε βρίσκω λόγο να παρεκκλίνουμε από αυτό γιατί ο όρος merge είναι κάτι που έχει συγκεκριμένη σημασία στην πληροφορική και θα ήταν ασυνεπές να διδάξουμε κάτι άλλο.
Στάθης Στέργου - sstergouATgmailDOTcom - http://www.pseudoglossa.gr

Laertis

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 1524
  • Sky's the limit
    • ΑΣΚΗΣΕΙΣ-ΘΕΜΑΤΑ ΑΕΠΠ
Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
« Απάντηση #2 στις: 10 Φεβ 2010, 08:41:28 μμ »
Συμφωνώ με τον Στάθη. Ας κρατήσουμε τον όρο συνένωση για το απλό "κόλλημα" δύο πινάκων.
Νικολακάκης Γιώργος
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής
http://users.sch.gr/gnikola

tom

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 488
Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
« Απάντηση #3 στις: 10 Φεβ 2010, 08:45:15 μμ »
Συμφωνώ με το Στάθη. Και εγώ ύστερα από μια σύντομη αναζήτηση στο δίκτυο αυτό βρήκα. Ότι ο όρος "συγχώνευση" αναφέρεται σε ταξινομημένες λίστες.

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

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 920
    • Στέφανος-Κων/νος Πουρσαλίδης
Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
« Απάντηση #4 στις: 10 Φεβ 2010, 09:04:27 μμ »
Οπότε η γνώμη μου...

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

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

Α=[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

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 488
Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
« Απάντηση #5 στις: 10 Φεβ 2010, 09:24:08 μμ »
συμφωνω εν μερει. Ο προβληματισμος μου ειναι ο εξης. Αν δωσεις τους παραπανω πινακες Α, Β και πεις "καντε συγχωνευση" το θεωρεις αρκετο για να τους παρουσιασει κανεις ταξινομημενους? νομιζω ειναι καλο να αναφερεται σε συνδυασμο ή με την αναφορα οτι θα πρεπει το αποτελεσμα να ειναι ταξινομημενο ή εστω να υπονοειται απο τη φυση του προβληματος που τιθεται.

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

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

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

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 946
Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
« Απάντηση #6 στις: 11 Φεβ 2010, 05:31:49 μμ »
Νομίζω συμφωνούμε όλοι ως προς τον όρο συνένωση.

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

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

tom

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 488
Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
« Απάντηση #7 στις: 11 Φεβ 2010, 06:05:22 μμ »
Γι αυτό, στο παράδειγμα του @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
« Τελευταία τροποποίηση: 11 Φεβ 2010, 06:22:41 μμ από tom »
Θωμάς Σκυλογιάννης

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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3525
  • to Iterate is human to Recurse divine
Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
« Απάντηση #8 στις: 11 Φεβ 2010, 10:23:40 μμ »

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

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 946
Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
« Απάντηση #9 στις: 11 Φεβ 2010, 11:21:21 μμ »
Οκ, καλύφθηκα. Συμφωνούμε  :)
Φιλικά,
Γιώργος Θαλασσινός

tom

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 488
Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
« Απάντηση #10 στις: 17 Φεβ 2010, 10:25:28 πμ »
Για αυτή την ασάφεια νομίζω έχουμε καταλήξει. Με τις άλλες να δούμε τι θα γίνει... :)
Θωμάς Σκυλογιάννης

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