Πριν γράψουμε κώδικα αναλύουμε το πρόβλημα και διαλέγουμε μέθοδο. Το κεφάλαιο παρουσιάζει τρεις τεχνικές σχεδίασης αλγορίθμων: διαίρει και βασίλευε (δυαδική αναζήτηση), δυναμικό προγραμματισμό (υπολογισμός δύναμης) και άπληστη μέθοδο (ρέστα με τα λιγότερα νομίσματα).
Γ΄ Λυκείου · Πληροφορική · 15 λεπτά
Το μάθημα είναι στο σχολικό βιβλίο. Δεν το αντιγράφουμε εδώ. Άνοιξε το επίσημο
κεφάλαιο και γύρνα για την εξάσκηση.
Η σύνοψη, οι όροι και οι ασκήσεις γράφτηκαν με τη βοήθεια τεχνητής νοημοσύνης από το
σχολικό βιβλίο και μπορεί να έχουν λάθη. Πηγή είναι πάντα το βιβλίο: ό,τι σου φαίνεται περίεργο,
έλεγξέ το εκεί. Βρήκες λάθος; Γράψε μας στο aporia@signmak.com.
Σχεδιάγραμμα
Δική μας σύνοψη της ενότητας, για επανάληψη. Πηγή είναι πάντα το βιβλίο.
Τι έγινε
Η ανάλυση ενός προβλήματος καταγράφει τα δεδομένα και το μέγεθός του, τις συνθήκες, την πιο αποδοτική μέθοδο, τον τρόπο καταγραφής της λύσης (π.χ. ψευδογλώσσα) και την υλοποίηση.
Παράδειγμα ταχυδρομικού διανομέα σε 4 χωριά: αν πηγαίνει κάθε φορά στο πλησιέστερο χωριό γράφει 36 km, ενώ με στόχο τη μικρότερη συνολική διαδρομή γράφει 30 km.
Καμία συνταγή δεν φτιάχνει από μόνη της αλγορίθμους· διαλέγουμε την καταλληλότερη τεχνική, και για προβλήματα χωρίς γνωστή τεχνική χρησιμοποιούμε ευριστικές μεθόδους.
Διαίρει και βασίλευε (top-down): χωρίζουμε το στιγμιότυπο σε υπο-στιγμιότυπα, τα λύνουμε ανεξάρτητα και συνδυάζουμε· κλασικό παράδειγμα η δυαδική αναζήτηση σε ταξινομημένο πίνακα.
Η μέθοδος της διχοτόμησης βρίσκει ρίζα της f(x) = 0 στο [a, b] όταν f(a)·f(b) < 0, κόβοντας το διάστημα στη μέση.
Δυναμικός προγραμματισμός (bottom-up): για προβλήματα βελτιστοποίησης, από το μικρότερο στιγμιότυπο προς το μεγαλύτερο, με αποθήκευση σε πίνακα· π.χ. η δύναμη a^b με αποθηκευμένες δυνάμεις αντί για b πολλαπλασιασμούς.
Άπληστη μέθοδος: σε κάθε βήμα η τρέχουσα βέλτιστη επιλογή· με τα νομίσματα του ευρώ (από 1/1/2002) δίνει τον ελάχιστο αριθμό τεμαχίων για ένα ποσό.
Ποια η διαφορά top-down και bottom-up προσέγγισης;
Στο διαίρει και βασίλευε (top-down) σπάμε το πρόβλημα σε μικρότερα ίδιου τύπου, τα λύνουμε χωριστά και συνδυάζουμε τις λύσεις. Στον δυναμικό προγραμματισμό (bottom-up) λύνουμε πρώτα τα μικρότερα στιγμιότυπα, κρατάμε τα αποτελέσματα σε πίνακα και χτίζουμε από αυτά τα μεγαλύτερα.
Πώς δουλεύει η δυαδική αναζήτηση;
Σε ταξινομημένο πίνακα ελέγχουμε το μεσαίο στοιχείο. Αν δεν είναι αυτό που ψάχνουμε, συνεχίζουμε μόνο στο πρώτο ή στο δεύτερο μισό, ανάλογα με τη σύγκριση, ώσπου να το βρούμε. Θυμίζει τη μέθοδο της διχοτόμησης (Bolzano) για τη ρίζα της f(x) = 0.
Τι κάνει η άπληστη μέθοδος;
Σε κάθε βήμα διαλέγει την καλύτερη επιλογή της στιγμής, π.χ. το μεγαλύτερο νόμισμα που χωράει στο ποσό. Συνήθως προσεγγίζει τη βέλτιστη λύση· στο πρόβλημα των νομισμάτων του ευρώ βρίσκει πράγματι τον ελάχιστο αριθμό κερμάτων και χαρτονομισμάτων.
Ανοίγει το μενού κοινοποίησης του κινητού σου. Αν δεν υπάρχει, αντιγράφεται ο σύνδεσμος.
Νέα από το aporia.gr Νέες ενότητες και ό,τι βρίσκουμε στα θέματα των Πανελληνίων, στη σελίδα μας στο Facebook.