Γενικό Λύκειο > Θεωρία

Μέθοδος Διαίρει και βασίλευε. Ερώτηση?

(1/2) > >>

tanius76:
Καλησπέρα σας !
Αν μπει η παρακάτω ερώτηση :
Τι γνωρίζετε για τη μέθοδο σχεδίασης αλγορίθμων «Διαίρει και Βασίλευε»

Είναι λάθος αν γράψει κάποιος ακριβώς τα ίδια με την Ιεραρχική Σχεδίαση Προγράμματος, που βρίσκεται στο πράσινο Βιβλίο στο κεφάλαιο 6, 6.4.1

Ποια είναι η γνώμη σας;



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

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

Προσωπικά η απάντηση που δίνω σε όλα τα παραπάνω είναι Σωστό. Στα α,β,γ έχουμε ένα πρόβλημα Ν μεγέθους και το ανάγουμε σε ένα ίδιου τύπου πρόβλημα αλλά μεγέθους Ν-1. Στο δ έχουμε ένα πρόβλημα Ν και το ανάγουμε σε ένα πρόβλημα λίγο λιγότερο από Ν/2.

Εσείς πως θα απαντάγατε στις παραπάνω ερωτήσεις;

evry:
Με το σκεπτικό σου όλα τα προβλήματα βασίζονται στην τεχνική Διαίρει και Βασίλευε.
Από τους αλγορίθμους ταξινόμησης η Merge Sort και QuickSort βασίζονται σε αυτή τη μέθοδο, όχι οι αλγόριθμοι που αναφέρεις


--- Παράθεση από: Γιαννούλης Γιώργος στις 02 Ιουν 2020, 11:02:47 πμ ---Στα α,β,γ έχουμε ένα πρόβλημα Ν μεγέθους και το ανάγουμε σε ένα ίδιου τύπου πρόβλημα αλλά μεγέθους Ν-1.

--- Τέλος παράθεσης ---

Φυσικά το λάθος δεν είναι δικό σου αλλά του βιβλίου ή για την ακρίβεια του συμπληρωματικού υλικού που δεν δίνει αυστηρό ορισμό. Με βάση τον ορισμό του βιβλίου οριακά έχεις δίκιο.
Ποιος είναι όμως ο ορισμός της μεθόδου αυτής?

(ας δούμε τι λέει η wikipedia και όχι κάποιο επιστημονικό βιβλίο αλγορίθμων)
In computer science, divide and conquer is an algorithm design paradigm based on multi-branched recursion. A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

Άρα για να πούμε ότι μια μέθοδος βασίζεται στην τεχνική διαίρει και βασίλευε πρέπει να ισχύουν τα παρακάτω:
1. Το πρόβλημα να χωρίζεται σε δύο ή περισσότερα  υπο-προβλήματα του ίδιου τύπου (και μεγέθους ?) (ταιριάζει για τη σχολική πραγματικότητα) (το related type ας το αφήσουμε προς το παρόν)
2. Να ορίζεται αναδρομική σχέση μεταξύ του προβλήματος και των υπο-προβλημάτων

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

Φυσικά υπάρχει και η άλλη άποψη: Να ακολουθούμε τις αντιεπιστημονικές ... "εκτιμήσεις" (για να μην χρησιμοποιήσω άλλη λέξη) που γράφουν τα βιβλία και όταν μας ρωτάνε γιατί ισχύει κάτι να απαντάμε ότι ...... το λέει στο βιβλίο.

ApoAntonis:
Σε συνέχεια των παραπάνω, γενικά στην βιβλιογραφία, για να ενταχθεί κάποιος αλγόριθμος στην κατηγορία διαίρει και βασίλευε,
πρέπει να διατυπώνεται αναδρομικά.
Ποιός αλγόριθμος μας δίνεται αναδρομικά στο βιβλίο; Κανένας.
Τελείωσε εδώ η κουβέντα; Όχι αφού ο "δικός μας" ορισμός δεν το απαιτεί αυτό.

Δεν το απαιτεί, φαντάζομαι, επειδή αυτό που αναφέρεται στην αναδρομή είναι ένα μικρό μπάχαλο.

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

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

Μια λύση είναι να <<γράψουμε>> βιβλία που να ανταποκρίνονται καλύτερα στο είδος των εξετάσεων που γνωρίζουμε. Η άλλη λύση είναι να μην γράφουμε ερωτήσεις κλειστού τύπου γιατί το έχουμε παρακάνει.

Bonus:
Σε κάποιον πίνακα Ν θέσεων, θα ψάξω το ζητούμενο
πρώτα στις άρτιες και έπειτα στις περιττές θέσεις. Είναι ή δεν είναι σειριακή αναζήτηση;

Πλοήγηση

[0] Λίστα μηνυμάτων

[#] Επόμενη σελίδα

Μετάβαση στην πλήρη έκδοση