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

[tanius76]

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

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

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

[o_Antonis]

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

[Γιαννούλης Γιώργος]

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

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

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

[evry]

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

Στα α,β,γ έχουμε ένα πρόβλημα Ν μεγέθους και το ανάγουμε σε ένα ίδιου τύπου πρόβλημα αλλά μεγέθους Ν-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. Να ορίζεται αναδρομική σχέση μεταξύ του προβλήματος και των υπο-προβλημάτων

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

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

[o_Antonis]

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

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

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

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

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

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

[Γιαννούλης Γιώργος]

(ας δούμε τι λέει η 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. Να ορίζεται αναδρομική σχέση μεταξύ του προβλήματος και των υπο-προβλημάτων

Το θέμα είναι ότι με τον παραπάνω ορισμό ούτε και η δυαδική αναζήτηση δεν είναι πρόβλημα διαίρει και βασίλευε, γιατί το κάθε πρόβλημα χωρίζεται μόνο σε ένα αντίστοιχο υποπρόβλημα, απλά δεν ξέρεις αν θα πάει δεξιά η αριστερά στον πίνακα.
Οπότε θεωρούμε μόνο mergesort, quicksort διαίρει και βασίλευε που δεν νομίζω ότι είναι σωστό, γιατί η λογική του διαίρει και βασίλευε υπάρχει στη δυαδική αναζήτηση.

[evry]

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

Δεν κατάλαβα που είναι η διαφωνία σου, σου multi-branch recursion?

[dimitrios67]

Ο Levitin βαζει την insertion-sort στην κατηγορία decrease-&-conquer.
"Απομείωση" κατα μια σταθερα, κατα σταθερό ορο, κατα μια μεταβλητή ποσοτητα.
Ειναι μια μορφή bottom-up recursion, οχι ομως σαν τον δυναμικο προγραμματισμό.
Brute-force ειναι μονο η bubble-sort και η selection-sort.

[Γιαννούλης Γιώργος]

Δεν κατάλαβα που είναι η διαφωνία σου, σου multi-branch recursion?

Παραθέτω την αμέσως επόμενη παράγραφο από αυτή που αναφέρεις για να γίνω πιο κατανοητός:

The name "divide and conquer" is sometimes applied to algorithms that reduce each problem to only one sub-problem, such as the binary search algorithm for finding a record in a sorted list (or its analog in numerical computing, the bisection algorithm for root finding).These algorithms can be implemented more efficiently than general divide-and-conquer algorithms; in particular, if they use tail recursion, they can be converted into simple loops. Under this broad definition, however, every algorithm that uses recursion or loops could be regarded as a "divide-and-conquer algorithm". Therefore, some authors consider that the name "divide and conquer" should be used only when each problem may generate two or more subproblems. The name decrease and conquer has been proposed instead for the single-subproblem class.

Εχουμε συνηθίσει στην τεχνική διαίρει και βασίλευε, τα υποπρόβλημα που πάμε να λύσουμε να έχουν μέγεθος που προκύπτει από διαίρεση του αρχικού μεγέθους, πχ στη δυαδική Ν/2 περιπου. Το θέμα είναι ότι η λέξη διαιρώ σημαίνει χωρίζω κάτι σε μέρη, δεν σημαίνει ούτε ότι είναι ίδιου μεγέθους, ούτε ότι το ένα μέρος δεν μπορεί να έχει μέγεθος 1.

Πάμε τώρα στον αλγόριθμο της δυαδικής αναζήτησης που είναι το καμάρι του βιβλίου στην παρουσίαση της τεχνικής διαίρει και βασίλευε. Στον παραπάνω αλγόριθμο έχουμε 1 πρόβλημα μεγέθους Ν και το ανάγουμε σε 1 πρόβλημα μεγέθους Ν/2. Συνεπώς, αφού το σχολικό δέχετε ότι ένας τέτοιος αλγόριθμος ανήκει στην κατηγορία διαίρει και βασίλευε, τότε ανήκουν και σχεδόν όλοι οι αλγόριθμοι που διδάσκουμε (max, min, αθροισμα, ταξινόμηση φυσαλίδας, ταξινόμηση επιλογής, σειριακή αναζήτηση, ...), το οποίο δεν είναι και κάτι κακό, ίσα ίσα δείχνει την ισχύ αυτής της τεχνικής.

Το πρόβλημα μου, είναι να βλέπω σε διαγωνίσματα σε Σωστό/Λάθος κάτι που ΔΕΝ αναφέρεται πουθενά στο βιβλίο.
Π.χ. Εφαρμόζει ο αλγόριθμος της σειριακής αναζήτησης την τεχνική διαίρει και βασίλευε;
Πως το ρωτάς αυτό; Δεν υπάρχει μέσα στο βιβλίο η απάντηση. Το βιβλίο αναφέρει έναν αλγόριθμο που το εφαρμόζει, αυτό δεν σημαίνει ότι όποιοι δεν αναφέρονται δεν το εφαρμόζουν. Είναι γιγαντιάιο άλμα λογικής αυτό και με αυτό διαφωνώ...

[evry]

Γιώργο έχεις δίκιο. Υπάρχει θέμα με την δυαδική αναζήτηση και το θέμα είναι ότι στην δυαδική αναζήτηση ενώ έχεις το divide δεν έχεις το conquer.
Κάποιοι συγγραφείς πράγματι δεν τη θεωρούν αντιπροσωπευτική μέθοδο διαίρει και βασίλευε.
Εμείς θα μπορούσαμε να την θεωρήσουμε μια εκφυλισμένη διαίρει και βασίλευε, με το σκεπτικό ότι χωρίζει το πρόβλημα σε δυο υποπροβλήματα (και όχι σε ένα) και η λύση στο ένα είναι trivial.
Όμως πράγματι από πλευράς ορισμού υπάρχει θέμα.
Σίγουρα πάντως δεν μπορεί να θεωρηθεί αντιπροσωπευτικό παράδειγμα διαίρει και βασίλευε!
Για παράδειγμα ο Levitin την αναφέρει στην κατηγορία των αλγορίθμων : decrease and conquer και πιο συγκεκριμένα decrease by a constant factor.
Δίνω και ένα λινκ με το .... βιβλίο !!!
https://doc.lagout.org/science/0_Computer%20Science/2_Algorithms/Introduction%20to%20the%20Design%20and%20Analysis%20of%20Algorithms%20%283rd%20ed.%29%20%5BLevitin%202011-10-09%5D.pdf
Ελπίζω να μην κάνω κάτι κακό, απλά το googlαρα και το βρήκα εκεί