Μέθοδος Διαίρει και Βασίλευε
(Δυαδική Αναζήτηση)

Η «Διαίρει και Βασίλευε» αποτελεί μια μέθοδο σχεδίασης αλγορίθμων στην οποία εντάσσονται οι τεχνικές που υποδιαιρούν ένα πρόβλημα σε μικρότερα υποπροβλήματα, που έχουν την ίδια τυποποίηση με το αρχικό πρόβλημα, αλλά είναι μικρότερα σε μέγεθος. Με όμοιο τρόπο, τα υποπροβλήματα αυτά μπορούν να διαιρεθούν σε ακόμη μικρότερα υποπροβλήματα κ.ο.κ. Έτσι η επίλυση ενός προβλήματος έγκειται στη σταδιακή επίλυση των όσο το δυνατόν μικρότερων υποπροβλημάτων, ώστε τελικά να προκύψει η συνολική λύση του αρχικού ευρύτερου προβλήματος. Η προσέγγιση αυτή ονομάζεται «από πάνω προς τα κάτω».

Βήματα Μεθόδου Διαίρει και Βασίλευε

Η μέθοδος σχεδίασης αλγορίθμων «Διαίρει και Βασίλευε» μπορεί να αποδοθεί με τα επόμενα βήματα:
1. Δίνεται για επίλυση ένα στιγμιότυπο ενός προβλήματος.
2. Το στιγμιότυπο του προβλήματος υποδιαιρείται σε υπο-στιγμιότυπα του ίδιου προβλήματος.
3. Δίνεται ανεξάρτητη λύση σε κάθε ένα υπο-στιγμιότυπο.
4. Συνδυάζονται όλες οι μερικές λύσεις που βρέθηκαν για τα υπο-στιγμιότυπα, έτσι ώστε να δοθεί η συνολική λύση του προβλήματος.

Δυαδική αναζήτηση

Στο πλαίσιο του μαθήματος η υλοποίηση της μεθόδου «Διαίρει και Βασίλευε» γίνεται με την επαναληπτική προσέγγιση δηλαδή με διαδοχικές επαναλήψεις. Ο μέγιστος αριθμός των συγκρίσεων – επαναλήψεων που απαιτούνται για την εύρεση ενός στοιχείου σε ένα σύνολο «n» ταξινομημένων στοιχείων, συμπεριλαμβανομένης και της περίπτωσης μη ύπαρξης του στοιχείου, δίνεται από το ακέραιο μέρος του [log2(n)+1] (με στρογγυλοποίηση προς τα κάτω).

Ένας κλασικός αλγόριθμος που ακολουθεί τη φιλοσοφία της μεθόδου «Διαίρει και Βασίλευε» είναι η «Δυαδική αναζήτηση», η οποία εφαρμόζεται μόνο στην περίπτωση ταξινομημένου συνόλου στοιχείων, δηλαδή σε ταξινομημένους πίνακες.

Απόδειξη / Αλγόριθμος Δυαδικής Αναζήτησης:

αρχη <- 1
τελος <- 100
βρεθηκε <- ΨΕΥΔΗΣ
Διάβασε χ
ΟΣΟ αρχη <=τελος ΚΑΙ βρεθηκε=ΨΕΥΔΗΣ ΕΠΑΝΑΛΑΒΕ
μεση <- (αρχη + τελος) div 2
ΑΝ Α[μέση] < χ ΤΟΤΕ
αρχη <- μεση + 1
ΑΛΛΙΩΣ_ΑΝ Α[μέση] >χ ΤΟΤΕ
τελος <- μεση – 1
ΑΛΛΙΩΣ βρεθηκε <- ΑΛΗΘΗΣ
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΝ βρεθηκε = ΨΕΥΔΗΣ ΤΟΤΕ
ΓΡΑΨΕ “Δεν βρεθηκε”
ΑΛΛΙΩΣ
ΓΡΑΨΕ “βρεθηκε το στοιχείο “, χ , “στη θέση”, μεση
ΤΕΛΟΣ_ΑΝ

Ανάλυση προβλημάτων

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

Η ανάλυση ενός προβλήματος σε ένα σύγχρονο υπολογιστικό περιβάλλον περιλαμβάνει:
1) την καταγραφή της υπάρχουσας πληροφορίας για το πρόβλημα,
2) την αναγνώριση των ιδιαιτεροτήτων του προβλήματος,
3) την αποτύπωση των συνθηκών και προϋποθέσεων υλοποίησής του και στη συνέχεια:
4) την πρόταση επίλυσης με χρήση κάποιας μεθόδου, και
5) την τελική επίλυση με χρήση υπολογιστικών συστημάτων.

Συγγενή Προβλήματα

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

Σωστό / Λάθος Ερωτήσεις Θεωρίας Μέθοδος Διαίρει και Βασίλευε:

1. Η ανάλυση ενός προβλήματος σε ένα σύγχρονο υπολογιστικό περιβάλλον περιλαμβάνει την εισαγωγή και την εξαγωγή δεδομένων.
2. Η μέθοδος Διαίρει και Βασίλευε είναι μία μέθοδος σχεδίασης αλγορίθμων
3. Μειονεκτήματα των μεθόδων ανάλυσης προβλημάτων είναι ότι εντοπίζει την πλέον κατάλληλη και αποδοτική λύση

4. Υπάρχει ενιαίος κανόνας που να αναφέρεται στην επίλυση όλων των προβλημάτων

5. Ένας κλασικός αλγόριθμος που ακολουθεί τη φιλοσοφία της μεθόδου Διαίρει και Βασίλευε είναι η Δυαδική αναζήτηση

Απαντήσεις Θεωρίας Μέθοδος Διαίρει και Βασίλευε:

Οι απαντήσεις για τις παραπάνω ερωτήσεις τύπου Σωστό/ Λάθος είναι οι παρακάτω:
1. Λ, 2. Σ, 3. Λ, 4. Λ, 5. Σ
Αν θέλετε και άλλες ερωτήσεις τύπου Σωστού / Λάθους ή γενικότερα ερωτήσεις θεωρίας στην ύλη της πληροφορικής Γ λυκείου στο κεφάλαιο Μέθοδος Διαίρει και Βασίλευε Δυαδική Αναζήτηση μπορείτε να δείτε από τα τεστ, διαγωνίσματα και θεωρίες που έχουμε δημιουργήσει για να σας δώσουν την δυνατότητα να καταφέρετε υψηλό βαθμό στις πανελλαδικές εξετάσεις.

Ερωτήσεις Ανάπτυξης Θεωρίας Δυαδικής Αναζήτησης

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

1. Να αναφέρετε τι γνωρίζετε για την μέθοδο σχεδίασης αλγορίθμων “Διαίρει και Βασίλευε”

Η «Διαίρει και Βασίλευε» αποτελεί μια μέθοδο σχεδίασης αλγορίθμων στην οποία εντάσσονται οι τεχνικές που υποδιαιρούν ένα πρόβλημα σε μικρότερα υποπροβλήματα. Με όμοιο τρόπο, τα υποπροβλήματα αυτά μπορούν να διαιρεθούν σε ακόμη μικρότερα υποπροβλήματα κ.ο.κ. Έτσι η επίλυση ενός προβλήματος έγκειται στη σταδιακή επίλυση των όσο το δυνατόν μικρότερων υποπροβλημάτων, ώστε τελικά να προκύψει η συνολική λύση του αρχικού ευρύτερου προβλήματος. Η προσέγγιση αυτή ονομάζεται «από πάνω προς τα κάτω» (top-down).

2. Ποια είναι τα βήματα της μεθόδου Διαίρει και Βασίλευε;

α) Δίνεται για επίλυση ένα στιγμιότυπο ενός προβλήματος.

β) Υποδιαιρείται το στιγμιότυπο σε υποστιγμιότυπα του ίδιου προβλήματος.

γ) Δίνεται ανεξάρτητη λύση σε κάθε ένα υποστιγμιότυπο.

δ) Συνδυάζονται όλες οι λύσεις που βρέθηκαν έτσι ώστε να δοθεί η λύση του προβλήματος.

3. Ποια βήματα περιλαμβάνει η ανάλυση ενός προβλήματος σε ένα προγραμματιστικό περιβάλλον;

1) Καταγραφή υπάρχουσας πληροφορίας,

2) Αναγνώριση ιδιαιτεροτήτων προβλήματος,

3) Αποτύπωση συνθηκών και προυποθέσεων υλοποίησης,

4) Πρόταση επίλυσης με κάποια μέθοδο και

5) Επίλυση με υπολογιστικό σύστημα

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