Διαίρει και βασίλευε (υπολογιστές): Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μ Ρομπότ: Προσθήκη: fa:الگوریتم تقسیم و حل |
Xqbot (συζήτηση | συνεισφορές) μ Ρομπότ: Τροποποίηση: ru:Разделяй и властвуй (информатика); διακοσμητικές αλλαγές |
||
Γραμμή 1:
Στην επιστήμη των υπολογιστών, '''διαίρει και βασίλευε''' '''''(divide and conquer, D&C)''''' είναι μέθοδος επίλυσης προβλημάτων. Το πρόβλημα διαρείται σε μικρότερα υποπροβλήματα και στη συνέχεια οι λύσεις τους συνδυάζονται για να προκύψει η λύση του αρχικού προβλήματος. Η μέθοδος αποτελεί τη βάση πολλών αλγορίθμων, π.χ. στους αλγόριθμους ταξινόμησης [[merge-sort]] και [[quicksort]].<br />
Το όνομά της προέρχεται από τη γνωστή ρήση του Καίσαρα, [[divide ut regnes]] (λατινικά).
== Μέθοδος ==
Η μέθοδος χρησιμοποιεί τρία στάδια για την επίλυση ενός προβλήματος. Συγκεκριμένα:
Γραμμή 9:
# Τέλος οι λύσεις των υποπροβλημάτων συνδυάζονται σε μία ενιαία λύση στο αρχικό πρόβλημα.
== Πλεονεκτήματα ==
=== Δύσκολα προβλήματα ===
Η μέθοδος είναι ιδιαίτερα αποτελεσματική στην επίλυση δύσκολων προβλημάτων, καθώς στηρίζεται στην επίλυση μικρότερων, ευκολότερων προβλημάτων. Παράδειγμα αποτελεί το παιχνίδι των [[Πύργοι του Ανόι|Πύργων του Ανόι]].
== Μειονεκτήματα ==
=== Πολυπλοκότητα ===
Η αντιμετώπιση ορισμένων απλών, μικρών προβλημάτων με το συγκεκριμένο τρόπο (αναδρομικό - recursive) είναι δυνατόν να είναι πιο περίπλοκη και δυσνόητη από αντίστοιχη επίλυση βασιζόμενη σε απλή επανάληψη (iterative).
== Βλ. Επίσης ==
* [[Αλγόριθμος]]
* [[Αναδρομή]]
Γραμμή 26:
* [[Πύργοι του Ανόι]]
== Βιβλιογραφία ==
T.H. Cormen, C.E. Leiserson, R.L. Rivest, ''Introduction to Algorithms'', The MIT Press, 2nd Edition
Γραμμή 47:
[[pt:Divisão e conquista]]
[[ro:Divide et impera (informatică)]]
[[ru:Разделяй и властвуй (
[[sl:Deli in vladaj (računalništvo)]]
[[sr:Подели па владај (информатика)]]
|