Μάθημα : ΠΛΗΡΟΦΟΡΙΚΗ Γ' ΛΥΚΕΙΟΥ

Ενότητες • [ΒΙΒΛΙΟ 2]: [2.1]

Η μέθοδος «Διαίρει και Βασίλευε» αφορά τη διάσπαση ενός προβλήματος σε δύο ή περισσότερα υποπροβλήματα (διαίρει) έως ότου φτάσουμε σε απλά υποπροβλήματα που λύνονται αυτόνομα (βασίλευε). Κατόπιν, οι λύσεις στα υποπροβλήματα συνδυάζονται μεταξύ τους, με σκοπό να δώσουν τη λύση σε ένα μεγαλύτερο πρόβλημα.

Να παρουσιασθεί η έννοια της μεθόδου «Διαίρει και βασίλευε» και να διδαχθεί η ανάλυση και η επίλυση του σχετικού παραδείγματος από την ενότητα 2.1 του βιβλίου [ΒΙΒΛΙΟ 2]. Να τονισθεί ότι η μέθοδος «Διαίρει και βασίλευε» είναι μία γενική μέθοδος που χρησιμοποιείται κυρίως για την αναζήτηση ενός στοιχείου σε διατεταγμένο σύνολο στοιχείων. Στο πλαίσιο του μαθήματος παρουσιάζεται μέσα από την υλοποίηση του αλγόριθμου της «Δυαδικής αναζήτησης», η οποία εφαρμόζεται σε ταξινομημένα στοιχεία.

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

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