Τεχνικές σχεδίασης αλγορίθμων
Κεφ. 4 §4.1 · Βιβλίο 2 §2.1 · Ανάλυση προβλημάτων, Διαίρει και Βασίλευε, δυαδική αναζήτηση
Σκέψου το παιχνίδι «μάντεψε τον αριθμό από το 1 έως το 1000». Αν ρωτάς «είναι 1; είναι 2;», μπορεί να χρειαστείς 1000 ερωτήσεις. Αν ρωτάς «είναι μεγαλύτερος από 500;» και κάθε φορά κόβεις το διάστημα στη μέση, τον βρίσκεις σε 10 το πολύ.
Αυτή είναι η δύναμη μιας καλής τεχνικής σχεδίασης: το ίδιο πρόβλημα, εκατό φορές γρηγορότερα.
Ανάλυση προβλημάτων
Για να σχεδιάσουμε έναν αλγόριθμο, πρέπει πρώτα να αναλύσουμε το πρόβλημα. Η βασική τεχνική είναι η ανάλυση από πάνω προς τα κάτω (top-down): ένα σύνθετο πρόβλημα χωρίζεται σε απλούστερα υποπροβλήματα, αυτά σε ακόμη απλούστερα, μέχρι κάθε κομμάτι να λύνεται εύκολα. Οι λύσεις των κομματιών συνθέτουν τη λύση του αρχικού προβλήματος.
Η ανάλυση αυτή:
- κάνει το πρόβλημα κατανοητό, γιατί το βλέπουμε κομμάτι κομμάτι,
- επιτρέπει να δουλεύουν διαφορετικά άτομα σε διαφορετικά κομμάτια,
- οδηγεί φυσικά στα υποπρογράμματα και στον τμηματικό προγραμματισμό.
Η Επιστήμη των Υπολογιστών έχει αναπτύξει γενικές τεχνικές σχεδίασης. Στην ύλη σου περιλαμβάνεται η πιο γνωστή: η μέθοδος Διαίρει και Βασίλευε.
Η μέθοδος «Διαίρει και Βασίλευε»
Η μέθοδος Διαίρει και Βασίλευε (divide and conquer) λύνει ένα πρόβλημα σε τρία βήματα:
- Διαίρεση: το πρόβλημα χωρίζεται σε μικρότερα υποπροβλήματα του ίδιου τύπου με το αρχικό.
- Βασίλευε (κατάκτηση): τα υποπροβλήματα λύνονται — αν είναι αρκετά μικρά, άμεσα· αλλιώς εφαρμόζοντας ξανά την ίδια μέθοδο.
- Συνδυασμός: οι λύσεις των υποπροβλημάτων συνδυάζονται στη λύση του αρχικού.
Η διαφορά από την απλή ανάλυση από πάνω προς τα κάτω: εδώ τα υποπροβλήματα είναι ίδιας μορφής με το αρχικό, απλώς μικρότερα (π.χ. «ψάξε στο μισό του πίνακα» αντί για «ψάξε σε όλο»).
Ποιο βήμα της μεθόδου «Διαίρει και Βασίλευε» χαρακτηρίζεται από το ότι τα υποπροβλήματα είναι του ίδιου τύπου με το αρχικό;
Εφαρμογή: δυαδική αναζήτηση
Σε ταξινομημένο πίνακα συγκρίνουμε το κλειδί με το μεσαίο στοιχείο:
- αν είναι ίσα, βρέθηκε·
- αν το κλειδί είναι μικρότερο, συνεχίζουμε μόνο στο αριστερό μισό·
- αν είναι μεγαλύτερο, μόνο στο δεξί μισό.
Κάθε σύγκριση υποδιπλασιάζει το διάστημα αναζήτησης. Είναι «Διαίρει και Βασίλευε» όπου λύνεται μόνο το ένα από τα δύο υποπροβλήματα και δεν χρειάζεται συνδυασμός.
κατω ← 1 πανω ← Ν βρεθηκε ← ΨΕΥΔΗΣ ΟΣΟ κατω <= πανω ΚΑΙ βρεθηκε = ΨΕΥΔΗΣ ΕΠΑΝΑΛΑΒΕ μεσο ← (κατω + πανω) DIV 2 ΑΝ Α[μεσο] = κλ ΤΟΤΕ βρεθηκε ← ΑΛΗΘΗΣ ΑΛΛΙΩΣ_ΑΝ κλ < Α[μεσο] ΤΟΤΕ πανω ← μεσο - 1 ΑΛΛΙΩΣ κατω ← μεσο + 1 ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Αν στο τέλος βρεθηκε = ΨΕΥΔΗΣ, το κλειδί δεν υπάρχει (το διάστημα άδειασε: κατω > πανω).
Παράδειγμα 1: Α = [3, 8, 12, 17, 25, 31, 40, 52] (Ν = 8). Ίχνος δυαδικής αναζήτησης για κλ = 31 και για κλ = 10.
κλ = 31:
- κατω = 1, πανω = 8, μεσο = 4, Α[4] = 17 < 31 → κατω = 5
- κατω = 5, πανω = 8, μεσο = 6, Α[6] = 31 → βρέθηκε στη θέση 6 (2 συγκρίσεις)
κλ = 10:
- μεσο = 4, Α[4] = 17, 10 < 17 → πανω = 3
- κατω = 1, πανω = 3, μεσο = 2, Α[2] = 8, 10 > 8 → κατω = 3
- κατω = 3, πανω = 3, μεσο = 3, Α[3] = 12, 10 < 12 → πανω = 2
- κατω = 3 > πανω = 2 → τέλος, δεν βρέθηκε (3 συγκρίσεις)
Η σειριακή αναζήτηση θα χρειαζόταν 6 και 8 συγκρίσεις αντίστοιχα.
Πόσες συγκρίσεις χρειάζεται το πολύ η δυαδική αναζήτηση σε ταξινομημένο πίνακα 1.000.000 στοιχείων;
Μέθοδος: λύση με «Διαίρει και Βασίλευε»
- Βρες πώς το πρόβλημα χωρίζεται σε μικρότερα ίδια προβλήματα (π.χ. «αριστερό μισό» και «δεξί μισό»).
- Όρισε πότε ένα υποπρόβλημα είναι αρκετά μικρό για να λυθεί άμεσα (π.χ. ένα στοιχείο).
- Περιέγραψε πώς οι λύσεις συνδυάζονται (π.χ. το μέγιστο των δύο μισών).
- Για τη δυαδική αναζήτηση: έλεγξε ότι ο πίνακας είναι ταξινομημένος — αλλιώς δεν εφαρμόζεται.
- Στο ίχνος γράψε σε κάθε βήμα κατω, πανω, μεσο και τη σύγκριση.
Θέμα τύπου Πανελλαδικών: Σε ταξινομημένο πίνακα Τ[15] αναζητείται με δυαδική αναζήτηση μια τιμή που δεν υπάρχει και είναι μεγαλύτερη από όλα τα στοιχεία. Να βρεθούν οι διαδοχικές τιμές του μεσο και το πλήθος των συγκρίσεων.
Λύση: Αφού το κλειδί είναι μεγαλύτερο από κάθε στοιχείο, σε κάθε βήμα ισχύει κλ > Τ[μεσο], άρα κατω ← μεσο + 1.
- κατω = 1, πανω = 15: μεσο = 16 DIV 2 = 8 → κατω = 9
- κατω = 9, πανω = 15: μεσο = 24 DIV 2 = 12 → κατω = 13
- κατω = 13, πανω = 15: μεσο = 28 DIV 2 = 14 → κατω = 15
- κατω = 15, πανω = 15: μεσο = 15 → κατω = 16
- κατω = 16 > πανω = 15 → τέλος
Τιμές του μεσο: 8, 12, 14, 15 — 4 συγκρίσεις, όσες δίνει ο τύπος .
Ποια είναι απαραίτητη προϋπόθεση για τη δυαδική αναζήτηση;
Παράδειγμα 2: Ανάλυσε από πάνω προς τα κάτω το πρόβλημα «Υπολογισμός μηνιαίας μισθοδοσίας εργαζομένων».
Λύση:
- 1 Μισθοδοσία
- 1.1 Εισαγωγή στοιχείων (ώρες εργασίας, ωρομίσθιο, υπερωρίες)
- 1.2 Υπολογισμός αποδοχών
- 1.2.1 Κανονικές αποδοχές = ώρες × ωρομίσθιο
- 1.2.2 Υπερωρίες = ώρες υπερωρίας × προσαυξημένο ωρομίσθιο
- 1.3 Υπολογισμός κρατήσεων (ασφαλιστικές εισφορές, φόρος)
- 1.4 Έκδοση εκκαθαριστικού
Τα υποπροβλήματα είναι διαφορετικά μεταξύ τους — αυτό είναι γενική ανάλυση. Στη Διαίρει και Βασίλευε θα ήταν ίδια μικρότερα προβλήματα (π.χ. «μισθοδοσία των 50 πρώτων» και «των 50 επόμενων»).
Η ταξινόμηση με συγχώνευση (merge sort), ο πιο κλασικός αλγόριθμος «Διαίρει και Βασίλευε», επινοήθηκε από τον John von Neumann το 1945. Χωρίζει τον πίνακα σε δύο μισά, ταξινομεί το καθένα και συγχωνεύει τα αποτελέσματα — και για ένα εκατομμύριο στοιχεία κάνει περίπου 20 εκατομμύρια συγκρίσεις αντί για τις 500 δισεκατομμύρια της φυσαλίδας.
«Διαίρει και Βασίλευε» = Κόψε – Λύσε – Κόλλησε. Στη δυαδική αναζήτηση το «κόλλησε» λείπει: κόβεις, κρατάς το μισό που σε ενδιαφέρει και πετάς το άλλο.
Περιέγραψε πώς βρίσκεται το μέγιστο ενός πίνακα 8 στοιχείων με «Διαίρει και Βασίλευε» και μέτρησε τις συγκρίσεις. Είναι λιγότερες από τη γνωστή σειριακή μέθοδο;
Δοκίμασε πρώτα μόνος σου — μετά δες τη λύση
Διαίρεση: 8 → δύο μισά των 4 → τέσσερα ζεύγη των 2 → οκτώ μονά στοιχεία (το μέγιστο ενός στοιχείου είναι το ίδιο). Συνδυασμός: κάθε ζεύγος μέγιστων συγκρίνεται μία φορά. Συγκρίσεις: 4 (ζεύγη) + 2 (τετράδες) + 1 (τελική) = 7. Η σειριακή μέθοδος (max ← Α[1], σύγκρινε με τα υπόλοιπα 7) κάνει επίσης 7. Άρα εδώ η μέθοδος δεν κερδίζει συγκρίσεις — κάθε σύγκριση «αποκλείει» ακριβώς ένα στοιχείο και πρέπει να αποκλειστούν 7. Το «Διαίρει και Βασίλευε» δεν είναι πάντα ταχύτερο· κερδίζει όταν, όπως στη δυαδική αναζήτηση, μπορείς να πετάξεις ολόκληρα κομμάτια.
- Δυαδική αναζήτηση σε μη ταξινομημένο πίνακα: μπορεί να μη βρει στοιχείο που υπάρχει.
- μεσο ← (κατω + πανω) / 2 με πραγματική διαίρεση: ο δείκτης πίνακα πρέπει να είναι ακέραιος, άρα DIV.
- πανω ← μεσο αντί για μεσο - 1: ο αλγόριθμος μπορεί να κολλήσει σε ατέρμονη επανάληψη.
- Σύγχυση της γενικής ανάλυσης (διαφορετικά υποπροβλήματα) με τη Διαίρει και Βασίλευε (ίδια υποπροβλήματα, μικρότερα).
- Ανάλυση από πάνω προς τα κάτω: σύνθετο πρόβλημα → απλούστερα υποπροβλήματα.
- Διαίρει και Βασίλευε: διαίρεση σε μικρότερα ίδια προβλήματα, επίλυση, συνδυασμός.
- Δυαδική αναζήτηση: μόνο σε ταξινομημένο πίνακα· μεσο ← (κατω + πανω) DIV 2.
- Το πολύ συγκρίσεις: 20 για ένα εκατομμύριο στοιχεία.
- Κερδίζει όταν μπορεί να απορρίψει ολόκληρα τμήματα του προβλήματος.