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

Γενικό Λύκειο => Γ΄ Λυκείου => Μήνυμα ξεκίνησε από: pgrontas στις 10 Φεβ 2010, 05:41:06 μμ

Τίτλος: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού πακέ
Αποστολή από: pgrontas στις 10 Φεβ 2010, 05:41:06 μμ
Για να έχουμε όλες τις ασάφειες μαζεμένες ας συζητήσουμε και το θέμα της συγχώνευσης πινάκων:

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

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

Η άποψη μου είναι ότι η συγχώνευση δεν αφορά μόνο ταξινομημένους πίνακες και επιπλέον δεν είναι ισοδύναμη με την συνένωση. Περιλαμβάνει δηλαδή και κάποια επιπλέον επεξεργασία (πχ. τελικός πίνακας χωρίς διπλά στοιχεία ή ταξινομημένος) η οποία ορίζεται κατά περίπτωση.
Τι γνώμη έχετε;
Τίτλος: Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
Αποστολή από: sstergou στις 10 Φεβ 2010, 06:18:08 μμ
Προτείνω αυτό που περιγράφεται εδώ :
http://en.wikipedia.org/wiki/Merge_algorithm

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

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

Δε βρίσκω λόγο να παρεκκλίνουμε από αυτό γιατί ο όρος merge είναι κάτι που έχει συγκεκριμένη σημασία στην πληροφορική και θα ήταν ασυνεπές να διδάξουμε κάτι άλλο.
Τίτλος: Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
Αποστολή από: Laertis στις 10 Φεβ 2010, 08:41:28 μμ
Συμφωνώ με τον Στάθη. Ας κρατήσουμε τον όρο συνένωση για το απλό "κόλλημα" δύο πινάκων.
Τίτλος: Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
Αποστολή από: tom στις 10 Φεβ 2010, 08:45:15 μμ
Συμφωνώ με το Στάθη. Και εγώ ύστερα από μια σύντομη αναζήτηση στο δίκτυο αυτό βρήκα. Ότι ο όρος "συγχώνευση" αναφέρεται σε ταξινομημένες λίστες.

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]


Τίτλος: Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
Αποστολή από: poursali στις 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 στις 10 Φεβ 2010, 09:24:08 μμ
συμφωνω εν μερει. Ο προβληματισμος μου ειναι ο εξης. Αν δωσεις τους παραπανω πινακες Α, Β και πεις "καντε συγχωνευση" το θεωρεις αρκετο για να τους παρουσιασει κανεις ταξινομημενους? νομιζω ειναι καλο να αναφερεται σε συνδυασμο ή με την αναφορα οτι θα πρεπει το αποτελεσμα να ειναι ταξινομημενο ή εστω να υπονοειται απο τη φυση του προβληματος που τιθεται.

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

Τίτλος: Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
Αποστολή από: gthal στις 11 Φεβ 2010, 05:31:49 μμ
Νομίζω συμφωνούμε όλοι ως προς τον όρο συνένωση.

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

Γι αυτό, στο παράδειγμα του @tom  την merge(Α, Β) δεν θα την έλεγα συγχώνευση (οι Α, Β δεν είναι ταξινομημένοι). Εδώ έχουμε :
concat(A, B)-->Γ
bubblesort(Γ)-->Γ'
Τίτλος: Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
Αποστολή από: tom στις 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
Τίτλος: Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
Αποστολή από: evry στις 11 Φεβ 2010, 10:23:40 μμ

  Σχετικά με τη συγχώνευση νομίζω ότι θα πρέπει να την δεχθούμε όπως ισχύει στην βιβλιογραφία, μια και η λειτουργία αυτή έχει μεγάλη σημασία για την πληροφορική γενικότερα. Δηλαδή ότι μιλάμε αποκλειστικά για ταξινομημένους πίνακες.
Τίτλος: Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
Αποστολή από: gthal στις 11 Φεβ 2010, 11:21:21 μμ
Οκ, καλύφθηκα. Συμφωνούμε  :)
Τίτλος: Απ: Συγχώνευση - Συνένωση Πινάκων (Ασάφεια διδακτικού π
Αποστολή από: tom στις 17 Φεβ 2010, 10:25:28 πμ
Για αυτή την ασάφεια νομίζω έχουμε καταλήξει. Με τις άλλες να δούμε τι θα γίνει... :)