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

Ξεκίνησε από che, 17 Απρ 2008, 06:09:39 ΜΜ

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

che

Αγαπητοί συνάδελφοι θα ήθελα την άποψη σας σχετικά με το εξής:

Αν υποθέσουμε ότι πρέπει να συγχωνεύσουμε δύο μονοδιάστατους πίνακες Α[6],Β[4], οι οποίοι είναι ήδη ταξινομημένοι (σε αύξουσα σειρά), με σκοπό την δημιουργία πίνακα Γ[10] , ο οποίος θα είναι επίσης ταξινομημένος.

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

Δεν μπορώ να απαντήσω όμως στο εξής ερώτημα που θέτω συχνά στον εαυτό μου .... ;D. Αν κάποιος μαθητής παρουσιάσει την εξής λύση:

για ι από 1 μέχρι 6
Γ[ι] <-- Α[ι]
τέλος_επανάληψης

για ι από 1 μέχρι 4
Γ[ι+6] <-- Β[ι]
τέλος_επανάληψης

και μετά φυσαλίδα στον Γ για να τον ταξινομήσει ....


Ποιό θα είναι το βαθμολογικό κόστος (αν αυτό υπάρχει τελικά)? Και αν υπάρχει , δεν πέφτουμε σε αντίφαση όταν τα θέματα αναφέρουν το γνωστό "ΟΠΟΙΑΔΗΠΟΤΕ ΕΠΙΣΤΗΜΟΝΙΚΑ ΑΠΟΔΕΔΕΙΓΜΕΝΗ ΛΥΣΗ ΕΊΝΑΙ ΑΠΟΔΕΚΤΗ", αλλά τελικά μας ωθούν σε μία λύση την οποία την έχουν 'θαμμένη' στο τετράδιο εργασιών?

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

Ευχαριστώ πολύ 

petrosp13

Εγώ διδάσκω και τους 2 και τους θεωρώ εξίσου σωστούς, παρατηρώντας απλά ότι ο πρώτος είναι σαφώς πιο γρήγορος και καλύτερος σε πολυπλοκότητα
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

evry


  Ναι μόνο που ο δεύτερος τρόπος με την ταξινόμηση δεν νομίζω ότι μπορεί να θεωρηθεί συγχώνευση.Μπορεί να παράγει το ίδιο αποτέλεσμα αλλά η λειτουργία της συγχώνευσης αναφέρεται στον πρώτο αλγόριθμο. Γενικότερα στη βιβλιογραφία όταν λέμε συγχώνευση εννοούμε τον πρώτο αλγόριθμο ο οποίος εκμεταλλεύεται το γεγονός ότι οι δύο πίνακες είναι ταξινομημένοι.
http://en.wikipedia.org/wiki/Merge_algorithm
Άρα δεν ξέρω κατά πόσο είναι σωστό να λες στους μαθητές ότι και οι δυο είναι αλγόριθμοι συγχώνευσης απλά ο ένας είναι πιο αποδοτικός.

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

andreas_p

Καλημέρα.

Το δεύτερο (ναι μεν λειτουργεί) , αλλά  ΔΕΝ είναι συγχώνευση.


Ο ορισμός της συγχώνευσης δίνεται ξεκάθαρα  στο τέλος του  9ου Κεφ.


Ανδρέας

evry

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

Παράθεση από: andreas_p στις 18 Απρ 2008, 09:43:36 ΠΜ
Καλημέρα.

Το δεύτερο (ναι μεν λειτουργεί) , αλλά  ΔΕΝ είναι συγχώνευση.
Ο ορισμός της συγχώνευσης δίνεται ξεκάθαρα  στο τέλος του  9ου Κεφ.

Ανδρέας
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

petrosp13

Στο κεφάλαιο 9 του βιβλίου αναφέρει:

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


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

Επίσης, το τετράδιο μαθητή αναφέρει στο παράδειγμα 3:

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

Άρα, ο αλγόριθμος αυτός είναι ένας αλγόριθμος και όχι ο αλγόριθμος συγχώνευσης.

ʼλλωστε, προγραμματισμός σημαίνει ελευθερία
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

gpapargi

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

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

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

Αν αυτό δεν προκύπτει από το βιβλίο τότε αποφεύγουμε το θέμα.

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

evry


Το σκεπτικό που λες με βάση το σχολικό βιβλίο έχει κάποια λογική για κάποιον ο όποιος δεν έχει ξαναδεί αλγόριθμο συγχώνευσης όπως οι περισσότεροι μαθητές.  Αν όμως ξέρεις ότι υπάρχει μια μέθοδος ταξινόμησης που λέγεται merge sort τα πράγματα αλλάζουν
  Γιατί όμως η merge sort λέγεται αλγόριθμος ταξινόμησης με συγχώνευση? Υπάρχουν πολλές Merge sort? και γιατί είναι τόσο γνωστή? μήπως γιατί έχει πολυπλοκότητα O(nlogn) που είναι η καλύτερη? Αυτό το nlogn προκύπτει από το γεγονός ότι χρησιμοποιούμε συγχώνευση και δεν αντιγράφουμε και μετά ταξινομούμε δυο ήδη ταξινομημένες λίστες. Δηλαδή αν σε κάθε βήμα της Merge sort αντιγράφεις και μετά ταξινομείς τους πίνακες αυτός θεωρείται Merge sort? Άσχετα με το τι λέει το βιβλίο ή το τετράδιο μαθητή στην επιστημονική κοινότητα ο όρος συγχώνευση σημαίνει κάτι συγκεκριμένο και όχι την συνένωση πινάκων και στη συνέχεια την ταξινόμηση του τελικού πίνακα.
http://en.wikipedia.org/wiki/Merge_sort
Επίσης όποιο σοβαρό βιβλίο αλγορίθμων και να ανοίξεις δε νομίζω να δεις πουθενά τη λέξη συγχώνευση και από κάτω τον αλγόριθμο αντιγράφω και ταξινομώ εκτός αν τον έχει ως παράδειγμα προς αποφυγήν. Και τέλος δεν μπορώ να καταλάβω γιατί χρησιμοποιούμε το βιβλίο ως ευαγγέλιο, μόνο αυτό υπάρχει στον κόσμο? ʼλλα βιβλία και πηγές δεν υπάρχουν?
http://en.wikipedia.org/wiki/Merge_algorithm
   Φυσικά το βιβλίο δεν λέει πουθενά ότι κάτι τέτοιο είναι συγχώνευση, αυτό το "ένας απλός αλγόριθμος συγχώνευσης" δε σημαίνει ότι αυτό που περιγράφεις είναι συγχώνευση, αλλά ότι η λειτουργία της συγχώνευσης μπορεί να υλοποιηθεί και με κάποιον πιο πολύπλοκο τρόπο. Επειδή όμως το μάθημα είναι πανελλαδικώς εξεταζόμενο πολλές φορές προσπαθούμε να ερμηνεύσουμε το γράμμα και όχι το πνεύμα του βιβλίου.

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

  Αλήθεια αν μπορούσαμε απλά να αντιγράψουμε και να ταξινομήσουμε δυο πίνακες σε έναν τότε γιατί αυτοί να είναι ταξινομημένοι? Δε μπορούμε να κάνουμε το ίδιο και σε μη ταξινομημένους πίνακες? Γιατί λοιπόν το βιβλίο ορίζει την συγχώνευση μόνο σε ταξινομημένους πίνακες? Μήπως γιατί ο αλγόριθμος εκμεταλλεύεται το γεγονός ότι είναι ταξινομημένοι?

  Ο αλγόριθμος της συγχώνευσης δεν είναι απλά ένας ακόμα αλγόριθμος με λίγο καλύτερη πολυπλοκότητα για να κάνουμε ταξινόμηση αλλά μια πολύ βασική λειτουργία που έχει μεγάλη εφαρμογή στις δευτερεύουσες δομές δεδομένων. Πως γίνεται η ταξινόμηση αρχείων τα οποία είναι πολύ μεγάλα για να τα φορτώσουμε ολόκληρα στη μνήμη? Το αρχείο χωρίζεται σε κομμάτια, κάθε ένα από αυτά ταξινομείται στη μνήμη και στη συνέχεια γίνεται συγχώνευση των κομματιών σε μεγαλύτερα τα οποία γράφονται στον δίσκο.
βλέπε http://en.wikipedia.org/wiki/External_sort

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

petrosp13

Είμαι ο πρώτος που δεν στηρίζεται στο σχολικο βιβλίο. Σε κανένα μάθημα, ούτε καν στο πρώτο της γνωριμίας με τα παιδιά δεν τους λέω να το φέρουν
Αλλά, εφ'όσον η λογική αυτού του φόρουμ είναι να φωτίσουμε κάποια σημεία με αποδείξεις, αυτό έκανα κι εγώ
Σε Ν άλλες συζητήσεις εδώ, υπάρχουν αναφορές σε κομμάτια του βιβλίου για το τι εκείνο ορίζει και τι όχι
Από αυτό κατάλαβα ότι το σχολικό βιβλίο θεωρείται βασικό σε πολλά πράγματα, ως προς το τι αναφέρει και τι όχι
Αν ο σκοπός μας είναι η διδασκαλία της αλγοριθμικής, τότε αυτό το βιβλίο είναι σχεδόν άχρηστο και αυτό είμαι ο πρώτος που το υποστηρίζω
Το να μου καταλογίζετε ότι στην ουσία μένω προσκολλημένος στο συγκεκριμένο βιβλίο είναι τουλάχιστον άδικο, γιατί δεν το χρησιμοποιώ ποτέ
Συμφωνώ ότι ο αλγόριθμος συγχώνευσης είναι αυτός που έχει το τετράδιο μαθητή
Αυτό σημαίνει ότι δεν μπορώ ή δεν πρέπει να παρουσιάσω και έναν άλλο τρόπο, τονίζοντας ότι είναι σαφώς χειρότερος σε πολυπλοκότητα, αλλά ο οποίος δουλεύει εξίσου και σε αταξινόμητους πίνακες, αν και δεν ορίζεται έτσι η συγχώνευση;
Καλώς ή κακώς, είμαστε καθηγητές σε παιδιά που δίνουν Πανελλαδικές εξετάσεις, πολλά από τα οποία δεν συμπαθούν και δεν καταλαβαίνουν και πολλά από το μάθημα
Δεν είμαστε καθηγητές σε φοιτητές Πληροφορικής που θα αρπάξουν κάθε δύσκολο αλγόριθμο για να τον εφαρμόσουν
Συνεπώς, η παρουσίαση της αλγοριθμικής που κάνουμε στα παιδιά δεν έχει σε μεγάλο βαθμό ούτε ακαδημαϊκό ούτε και ρομαντικό χαρακτήρα. Μάλλον πρακτικό χαρακτήρα έχει για να πετύχουν τον στόχο τους, δηλαδή να γράψουν καλά στις Πανελλαδικές εξετάσεις.
Είμαι ο πρώτος που δεν θα ασχολιόταν καθόλου με τον "μπακάλικο" (όπως τον ονομάζω) τρόπο, αν το μάθημα δεν είχε τόσο σημαντικό χαρακτήρα, αν είχα παραπάνω ώρες την εβδομάδα για να μπορέσω να περάσω καλύτερα δύσκολους αλγορίθμους όπως αυτός που έχει το τετράδιο μαθητή, αν έκανα πραγματικά το κέφι μου χωρίς άγχος χρόνου και επιτυχίας και αν πίστευα ότι το κοινό που θα με ακούει να παρουσιάζω τον αλγόριθμο δεν θα είχε τρομακτικές δυσκολίες να τον αφομοιώσει.
Όπως και να το κάνουμε, ο εναλλακτικός αλγόριθμος είναι και πιο εύπεπτος και πιο "σίγουρος". Παρουσιάζω και τους 2 και τους αφήνω στην κρίση των παιδιών.

Αυτή είναι η γνώμη μου και συγνώμη αν κούρασα με το μακροσκελές post μου
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

alkisg

Παράθεση από: evry στις 18 Απρ 2008, 03:36:27 ΜΜ
Γιατί όμως η merge sort λέγεται αλγόριθμος ταξινόμησης με συγχώνευση? Υπάρχουν πολλές Merge sort? και γιατί είναι τόσο γνωστή? μήπως γιατί έχει πολυπλοκότητα O(nlogn) που είναι η καλύτερη?

Άσχετα με τη συζήτηση, και ΑΝ τα θυμάμαι σωστά, ο merge sort έχει O(nlogn) σε μη ταξινομημένους πίνακες.
Στην περίπτωση που συζητάμε το merging δύο ήδη ταξινομημένων πινάκων χρειάζεται μόνο O(N), ή Ο(N+M) για τους τυπολάτρες.
Δηλαδή είναι ασύγκριτα πιο γρήγορο από το να τους ενώσεις και να τους ταξινομήσεις εξ' αρχής.

Θα έχει πολύ γέλιο πάντως αν κάποτε μπει το κεφάλαιο 5 εντός της διδακτέας ύλης. Θα πρέπει να αλλαχθεί ο τρόπος διδασκαλίας των υπόλοιπων κεφαλαίων(!)  ;D

evry


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

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

gpapargi

Υπάρχει κάτι που νομίζω ότι μας διαφεύγει.

Όταν οι συγγραφείς έγραφαν το βιβλίο δεν είχαν στο νου τους ότι θα φτάναμε ποτέ στο σημείο να αγνοούμε στο μάθημα την ποιότητα του αλγορίθμου. Οι άνθρωποι… όταν έγραφαν για συγχώνευση έλεγαν αυτό που θα έλεγε ο καθένας: ότι έχεις 2 ταξινομημένους πίνακες και φτιάχνεις τρίτο επίσης ταξινομημένο. Αυτό αρκεί για να καταλάβεις πως θα το κάνεις.

Που να φανταζόντουσαν ότι θεωρείται λύση και το «κόλλημα με ξαναταξινόμηση»  λόγω του ότι δε μετράει το πλήθος των βημάτων στο μάθημά μας; Αυτό όμως είναι "τοπικής" σημασίας. Ισχύει μόνο για τη ΑΕΠΠ. Δεν ισχύει παραέξω. (Ισχύει βέβαια και για τα ιδιωτικά ΙΕΚ).

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

Αν ανοίξεις τους ασκούς του Αιόλου, μετά δεν πρέπει να απορείς για αυτά που θα δεις.