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

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

<< < (2/2)

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

--- Παράθεση από: evry στις 02 Ιουν 2020, 11:22:44 πμ ---(ας δούμε τι λέει η 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:

--- Παράθεση από: Γιαννούλης Γιώργος στις 22 Ιουν 2020, 02:31:55 μμ ---Το θέμα είναι ότι με τον παραπάνω ορισμό ούτε και η δυαδική αναζήτηση δεν είναι πρόβλημα διαίρει και βασίλευε, γιατί το κάθε πρόβλημα χωρίζεται μόνο σε ένα αντίστοιχο υποπρόβλημα, απλά δεν ξέρεις αν θα πάει δεξιά η αριστερά στον πίνακα.

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

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

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

--- Παράθεση από: evry στις 22 Ιουν 2020, 03:35:43 μμ ---Δεν κατάλαβα που είναι η διαφωνία σου, σου 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αρα και το βρήκα εκεί >:D

Πλοήγηση

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

[*] Προηγούμενη σελίδα

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