Τεχνικές Σχεδίασης Αλγορίθμων Θεωρία Πληροφορική Γ Λυκείου ΑΕΠΠ
Όταν μας δίνεται ένα πρόβλημα, και πριν ασχοληθούμε με την κωδικοποίηση και τον προγραμματισμό, πρέπει προκαταρκτικά να κάνουμε μία θεωρητική μελέτη του προβλήματος. Μία καλή ιδέα είναι να προσπαθήσουμε να διαπιστώσουμε αν το δεδομένο πρόβλημα μπορεί να αντιμετωπιστεί με βάση κάποιες γενικές μεθοδολογίες ανάπτυξης αλγορίθμων. Για αυτό και το κεφάλαιο υπάρχει στις πανελλαδικές εξετάσεις αναφέροντας τις τεχνικές σχεδίασης αλγορίθμων, με έμφαση στη Μέθοδο Διαίρει και Βασίλευε. Πολύ καλές επιλογές για το Θέμα Α και Θέμα Β στις πανελλήνιες εξετάσεις είτε ως σωστό λάθος είτε σαν πιθανή συμπλήρωση κενών της δυαδικής αναζήτησης.
Σε αυτή τη σελίδα θα δείτε την ανάλυση προβλημάτων, τις μεθόδους σχεδίασης αλγορίθμων και τη μέθοδο «Διαίρει και Βασίλευε», με κλασικό παράδειγμα τη δυαδική αναζήτηση. Θα βρείτε επίσης ερωτήσεις Σωστό / Λάθος, ερωτήσεις ανάπτυξης, πολλαπλής επιλογής και αντιστοίχισης. Όλα βασισμένα στο επίπεδο των εξετάσεων που θα πρέπει να έχετε για να γράψετε καλά στις πανελλήνιες εξετάσεις στο μάθημα της πληροφορικής Γ λυκείου (ΑΕΠΠ).
4.1 Ανάλυση προβλημάτων Κεφάλαιο Θεωρίας ΑΕΠΠ
Ο αλγόριθμος αποσκοπεί στην επίλυση ενός προβλήματος. Είναι πιθανόν ένα πρόβλημα να μην επιλύεται με μία μόνο λύση αλλά με περισσότερες. Γενικά, η λύση σε ένα πρόβλημα μπορεί να προέλθει από ποικίλες και διαφορετικές προσεγγίσεις, τεχνικές και μεθόδους. Έτσι, είναι απαραίτητο να γίνεται μία καλή ανάλυση του κάθε προβλήματος και να προτείνεται συγκεκριμένη μεθοδολογία και ακολουθία βημάτων. Βασικός στόχος μας είναι η πρόταση έξυπνων και αποδοτικών λύσεων.
Τι περιλαμβάνει η ανάλυση ενός προβλήματος
Η ανάλυση ενός προβλήματος σε ένα σύγχρονο υπολογιστικό περιβάλλον περιλαμβάνει:
- την καταγραφή της υπάρχουσας πληροφορίας για το πρόβλημα,
- την αναγνώριση των ιδιαιτεροτήτων του προβλήματος,
- την αποτύπωση των συνθηκών και προϋποθέσεων υλοποίησής του,
και στη συνέχεια:
- την πρόταση επίλυσης με χρήση κάποιας μεθόδου, και
- την τελική επίλυση με χρήση υπολογιστικών συστημάτων.
Ποιες ερωτήσεις πρέπει να απαντηθούν
Κατά την ανάλυση ενός προβλήματος θα πρέπει να δοθεί απάντηση σε κάθε μία από τις επόμενες ερωτήσεις:
- Ποια είναι τα δεδομένα και το μέγεθος του προβλήματος;
- Ποιες είναι οι συνθήκες που πρέπει να πληρούνται για την επίλυση του προβλήματος;
- Ποια είναι η πλέον αποδοτική μέθοδος επίλυσής του (σχεδίαση αλγορίθμου);
- Πώς θα καταγραφεί η λύση του προβλήματος (π.χ. σε ψευδογλώσσα);
- Ποιος είναι ο τρόπος υλοποίησης στο συγκεκριμένο υπολογιστικό σύστημα (π.χ. επιλογή γλώσσας προγραμματισμού);
Παράδειγμα θεωρητικό ανάλυσης προβλήματος ΑΕΠΠ
Ένας ταχυδρομικός διανομέας πρέπει να ξεκινήσει από ένα χωριό, να επισκεφθεί έναν αριθμό γειτονικών χωριών για να μοιράσει επιστολές και να επιστρέψει στο χωριό από όπου ξεκίνησε, περνώντας μόνο μία φορά από κάθε χωριό. Το πρόβλημα είναι να βρεθεί η καλύτερη διαδρομή, ώστε να διανύσει το μικρότερο δυνατό αριθμό χιλιομέτρων. Στο σχήμα του βιβλίου υπάρχουν 4 χωριά (κόμβοι), 6 οδικές αρτηρίες (συνδέσεις) και οι χιλιομετρικές αποστάσεις τους. Ο διανομέας ξεκινά από το χωριό 1.
| Ανάλυση | Βήματα | Συνολική απόσταση |
|---|---|---|
| Α) Πρώτη ανάλυση | 1. Καταγραφή όλων των αποστάσεων μεταξύ των χωριών. 2. Ταξινόμηση των συνδέσεων κατά αύξουσα χιλιομετρική απόσταση. 3. Επιλογή κάθε φορά της μετάβασης προς το πλησιέστερο χωριό. | 36 χιλιόμετρα |
| Β) Διαφορετική ανάλυση | 1. Καταγραφή όλων των αποστάσεων μεταξύ των χωριών. 2. Εύρεση σειράς επίσκεψης με στόχο την ελαχιστοποίηση της συνολικής απόστασης και όχι της κάθε φορά απόστασης. | 30 χιλιόμετρα |
Συγγενή προβλήματα Θεωρία ΑΕΠΠ
Γιατί ενδιαφέρουν οι μέθοδοι ανάλυσης και επίλυσης - Ορισμός ΑΕΠΠ
- παρέχουν ένα γενικό πρότυπο κατάλληλο για την επίλυση προβλημάτων ευρείας κλίμακας,
- μπορούν να αναπαρασταθούν με κοινές δομές δεδομένων και ελέγχου, που υποστηρίζονται από τις περισσότερες σύγχρονες γλώσσες προγραμματισμού,
- παρέχουν τη δυνατότητα καταγραφής των χρονικών και «χωρικών» απαιτήσεων της μεθόδου επίλυσης, ώστε να μπορεί να γίνει επακριβής εκτίμηση των αποτελεσμάτων.
4.2 Μέθοδοι σχεδίασης αλγορίθμων Κεφάλαιο Θεωρίας ΑΕΠΠ
Οι μέθοδοι λύσης ενός προβλήματος που προκύπτουν από την ανάλυσή του οδηγούν στη σχεδίαση ενός αλγορίθμου, που συνιστά την ακολουθία βημάτων που πρέπει να ακολουθηθούν για να επιλυθεί το πρόβλημα. Υπάρχουν μερικές τεχνικές που συχνά χρησιμοποιούνται σε πληθώρα προβλημάτων. Οι τεχνικές αυτές έχουν τυποποιηθεί λόγω των κοινών χαρακτηριστικών τους, κάτι που διευκολύνει την ένταξη ενός προβλήματος στην αντίστοιχη κατηγορία επίλυσής του.
Τι χρειάζεται να υποστηρίζει κάθε τεχνική σχεδίασης αλγορίθμων στο ΑΕΠΠ
- να αντιμετωπίζει με το δικό της τρόπο τα δεδομένα,
- να έχει τη δική της ακολουθία εντολών,
- να διαθέτει τη δική της αποδοτικότητα.
Οι τυποποιημένες κατηγορίες τεχνικών
Στη βιβλιογραφία αναφέρονται αρκετές τυποποιημένες κατηγορίες τεχνικών. Στο σχολικό βιβλίο εξετάζονται οι εξής:
- Μέθοδος Διαίρει και Βασίλευε
- Μέθοδος δυναμικού προγραμματισμού
- Άπληστη μέθοδος
Αυτό δεν σημαίνει ότι κάθε πρόβλημα μπορεί να επιλυθεί με μία από τις γνωστές τεχνικές. Υπάρχουν πολλά προβλήματα που απαιτούν την εφαρμογή μίας νέας αντίληψης. Συχνά οι μέθοδοι που εφαρμόζονται σε αυτά ονομάζονται ευριστικές τεχνικές.
Μέθοδος Διαίρει και Βασίλευε Θεωρία ΑΕΠΠ
Με όμοιο τρόπο, τα υποπροβλήματα αυτά μπορούν να διαιρεθούν σε ακόμη μικρότερα υποπροβλήματα κ.ο.κ. Έτσι η επίλυση ενός προβλήματος έγκειται στη σταδιακή επίλυση των όσο το δυνατόν μικρότερων υποπροβλημάτων, ώστε τελικά να προκύψει η συνολική λύση του αρχικού ευρύτερου προβλήματος. Η προσέγγιση αυτή ονομάζεται «από πάνω προς τα κάτω» (top-down).
Βήματα της μεθόδου Διαίρει και Βασίλευε Γ Λυκείου ΑΕΠΠ
- Δίνεται για επίλυση ένα στιγμιότυπο ενός προβλήματος.
- Το στιγμιότυπο του προβλήματος υποδιαιρείται σε υπο-στιγμιότυπα του ίδιου προβλήματος.
- Δίνεται ανεξάρτητη λύση σε κάθε ένα υπο-στιγμιότυπο.
- Συνδυάζονται όλες οι μερικές λύσεις που βρέθηκαν για τα υπο-στιγμιότυπα, έτσι ώστε να δοθεί η συνολική λύση του προβλήματος.
Δυαδική αναζήτηση Θεωρία και Παράδειγμα ΑΕΠΠ
Ένας κλασικός αλγόριθμος που ακολουθεί τη φιλοσοφία της μεθόδου «Διαίρει και Βασίλευε» είναι η «Δυαδική αναζήτηση», η οποία εφαρμόζεται μόνο στην περίπτωση ταξινομημένου συνόλου στοιχείων, δηλαδή σε ταξινομημένους πίνακες. Είναι πολύ πιθανό στις πανελλαδικές εξετάσεις της πληροφορικής Γ λυκείου, να ζητηθεί σαν συμπλήρωση κενών ή σαν διόρθωση λαθών στο Θέμα Β του ΑΕΠΠ. Θα πρέπει λοιπόν να ξέρετε τον αλγόριθμο της δυαδικής αναζήτησης ώστε να μπορέσετε να απαντήσετε σε οποιοδήποτε θέμα ζητηθεί στις εξετάσεις.
Παράδειγμα Δυαδικής Αναζήτησης Θεωρία ΑΕΠΠ
Έστω ένας ηλεκτρονικός τηλεφωνικός κατάλογος, δηλαδή ένας πίνακας με n ονόματα και έναν αριθμό τηλεφώνου για κάθε όνομα, ταξινομημένος κατά αύξουσα αλφαβητική τάξη ως προς τα ονόματα. Τα ονόματα και τα τηλέφωνα είναι αποθηκευμένα σε δύο πίνακες, names[1..n] και phones[1..n]. Ζητείται το τηλέφωνο που αντιστοιχεί σε δεδομένο όνομα. Όταν δοθεί ένα όνομα, υπάρχουν 3 περιπτώσεις:
- το όνομα βρίσκεται στη μεσαία θέση του πίνακα names,
- το όνομα βρίσκεται σε μία θέση στο πρώτο μισό του πίνακα names,
- το όνομα βρίσκεται σε μία θέση στο δεύτερο μισό του πίνακα names.
Λύση στο Παράδειγμα Δυαδικής Αναζήτησης στη Θεωρία ΑΕΠΠ
Στον πίνακα πέντε θέσεων αναζητείται το όνομα Δανάη. Η αναζήτηση χρειάζεται τρεις προσπάθειες:
| Προσπάθεια | Θέση που ελέγχεται | Όνομα στη θέση | Σύγκριση και συνέχεια |
|---|---|---|---|
| 1η | 3η (η μεσαία) | Κατερίνα | Η Δανάη είναι λεξικογραφικά μικρότερη, άρα η αναζήτηση περιορίζεται στο πρώτο μισό (2 θέσεις). |
| 2η | 1η | Γιάννης | Η Δανάη είναι λεξικογραφικά μεγαλύτερη, άρα η αναζήτηση περιορίζεται στη 2η θέση. |
| 3η | 2η | Δανάη | Βρέθηκε το τηλέφωνο της Δανάης. |
Ο αλγόριθμος της δυαδικής αναζήτησης
! Ο πίνακας Α έχει 100 στοιχεία, ταξινομημένα κατά αύξουσα σειρά
αρχη <- 1
τελος <- 100
βρεθηκε <- ΨΕΥΔΗΣ
ΔΙΑΒΑΣΕ χ
ΟΣΟ αρχη <= τελος ΚΑΙ βρεθηκε = ΨΕΥΔΗΣ ΕΠΑΝΑΛΑΒΕ
μεση <- (αρχη + τελος) DIV 2
ΑΝ Α[μεση] < χ ΤΟΤΕ
αρχη <- μεση + 1
ΑΛΛΙΩΣ_ΑΝ Α[μεση] > χ ΤΟΤΕ
τελος <- μεση - 1
ΑΛΛΙΩΣ
βρεθηκε <- ΑΛΗΘΗΣ
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΝ βρεθηκε = ΨΕΥΔΗΣ ΤΟΤΕ
ΓΡΑΨΕ 'Δεν βρέθηκε'
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Βρέθηκε το στοιχείο ', χ, ' στη θέση ', μεση
ΤΕΛΟΣ_ΑΝ
Ο αλγόριθμος αυτός αντιμετωπίζει και την περίπτωση της ανεπιτυχούς αναζήτησης, όταν το αναζητούμενο στοιχείο δεν υπάρχει στον πίνακα.
Ερώτηση, πόσες συγκρίσεις χρειάζεται η δυαδική αναζήτησηστη θεωρία
Στο πλαίσιο του μαθήματος η υλοποίηση της μεθόδου «Διαίρει και Βασίλευε» γίνεται με την επαναληπτική προσέγγιση, δηλαδή με διαδοχικές επαναλήψεις. Ο μέγιστος αριθμός των συγκρίσεων (επαναλήψεων) που απαιτούνται για την εύρεση ενός στοιχείου σε ένα σύνολο n ταξινομημένων στοιχείων, συμπεριλαμβανομένης και της περίπτωσης μη ύπαρξης του στοιχείου, δίνεται από το ακέραιο μέρος του [log2(n) + 1], με στρογγυλοποίηση προς τα κάτω.
| Πλήθος στοιχείων n | log2(n) + 1 | Μέγιστος αριθμός συγκρίσεων |
|---|---|---|
| 5 | περίπου 3.32 | 3 |
| 100 | περίπου 7.64 | 7 |
| 1000 | περίπου 10.97 | 10 |
Σωστό / Λάθος και ασκήσεις θεωρίας ΑΕΠΠ Τεχνικές Σχεδίασης Αλγορίθμων
Ερωτήσεις Σωστό / Λάθος Τεχνικές Σχεδίασης Αλγορίθμων
Απαντήστε πρώτα μόνοι σας και μετά ελέγξτε τις απαντήσεις στον πίνακα.
- Η ανάλυση ενός προβλήματος σε ένα σύγχρονο υπολογιστικό περιβάλλον περιλαμβάνει την εισαγωγή και την εξαγωγή δεδομένων.
- Η μέθοδος Διαίρει και Βασίλευε είναι μία μέθοδος σχεδίασης αλγορίθμων.
- Μειονέκτημα των μεθόδων ανάλυσης προβλημάτων είναι ότι εντοπίζουν την πλέον κατάλληλη και αποδοτική λύση.
- Υπάρχει ενιαίος κανόνας που να αναφέρεται στην επίλυση όλων των προβλημάτων.
- Ένας κλασικός αλγόριθμος που ακολουθεί τη φιλοσοφία της μεθόδου Διαίρει και Βασίλευε είναι η δυαδική αναζήτηση.
- Η δυαδική αναζήτηση μπορεί να εφαρμοστεί και σε μη ταξινομημένο πίνακα.
- Η προσέγγιση της μεθόδου Διαίρει και Βασίλευε ονομάζεται «από κάτω προς τα επάνω».
- Στη μέθοδο Διαίρει και Βασίλευε τα υποπροβλήματα έχουν την ίδια τυποποίηση με το αρχικό πρόβλημα.
- Ο τρόπος που λειτουργεί η δυαδική αναζήτηση είναι ανάλογος με αυτόν της μεθόδου της διχοτόμησης.
- Κάθε πρόβλημα επιλύεται πάντοτε με μία μόνο λύση.
| Α/Α | Απάντηση | Γιατί |
|---|---|---|
| 1 | Λάθος | Η ανάλυση περιλαμβάνει την καταγραφή της πληροφορίας, την αναγνώριση των ιδιαιτεροτήτων, την αποτύπωση των συνθηκών, την πρόταση επίλυσης και την τελική επίλυση. |
| 2 | Σωστό | Η Διαίρει και Βασίλευε είναι μία από τις μεθόδους σχεδίασης αλγορίθμων. |
| 3 | Λάθος | Το να εντοπίζεται η πλέον κατάλληλη και αποδοτική λύση είναι πλεονέκτημα και όχι μειονέκτημα. |
| 4 | Λάθος | Δεν υπάρχει ενιαίος κανόνας. Υπάρχουν μόνο συγγενή προβλήματα, που αντιμετωπίζονται με αντίστοιχες μεθόδους. |
| 5 | Σωστό | Η δυαδική αναζήτηση είναι κλασικός αλγόριθμος της μεθόδου Διαίρει και Βασίλευε. |
| 6 | Λάθος | Η δυαδική αναζήτηση εφαρμόζεται μόνο σε ταξινομημένο σύνολο στοιχείων. |
| 7 | Λάθος | Η προσέγγιση αυτή ονομάζεται «από πάνω προς τα κάτω» (top-down). Η προσέγγιση «από κάτω προς τα επάνω» ανήκει στον δυναμικό προγραμματισμό. |
| 8 | Σωστό | Τα υποπροβλήματα έχουν την ίδια τυποποίηση με το αρχικό, αλλά είναι μικρότερα σε μέγεθος. |
| 9 | Σωστό | Και στις δύο μεθόδους σε κάθε βήμα εξαιρείται από την έρευνα το μισό τμήμα. |
| 10 | Λάθος | Είναι πιθανόν ένα πρόβλημα να μην επιλύεται με μία μόνο λύση αλλά με περισσότερες. |
Ερωτήσεις ανάπτυξης Τεχνικές Σχεδίασης Αλγορίθμων ΑΕΠΠ
Οι λύσεις είναι γραμμένες όπως θα ζητηθούν στις πανελλήνιες εξετάσεις της Πληροφορικής Γ Λυκείου ΑΕΠΠ. Να είστε προσεκτικοί γιατί τις ερωτήσεις ανάπτυξης τις θέλουν στις εξετάσεις ακριβώς όπως είναι στη θεωρία της Πληροφορικής ΑΕΠΠ Γ λυκείου.
1. Να αναφέρετε τι γνωρίζετε για τη μέθοδο σχεδίασης αλγορίθμων «Διαίρει και Βασίλευε».
2. Ποια είναι τα βήματα της μεθόδου Διαίρει και Βασίλευε;
β) Υποδιαιρείται το στιγμιότυπο σε υποστιγμιότυπα του ίδιου προβλήματος.
γ) Δίνεται ανεξάρτητη λύση σε κάθε ένα υποστιγμιότυπο.
δ) Συνδυάζονται όλες οι λύσεις που βρέθηκαν, έτσι ώστε να δοθεί η λύση του προβλήματος.
3. Ποια βήματα περιλαμβάνει η ανάλυση ενός προβλήματος σε ένα προγραμματιστικό περιβάλλον;
2) Αναγνώριση ιδιαιτεροτήτων του προβλήματος,
3) Αποτύπωση συνθηκών και προϋποθέσεων υλοποίησης,
4) Πρόταση επίλυσης με κάποια μέθοδο και
5) Επίλυση με υπολογιστικό σύστημα.
4. Να περιγράψετε τη μέθοδο της δυαδικής αναζήτησης και να δώσετε ένα παράδειγμα.
Παράδειγμα: στον τηλεφωνικό κατάλογο των πέντε θέσεων αναζητείται η Δανάη. Ελέγχεται η 3η θέση (Κατερίνα), οπότε η αναζήτηση περιορίζεται στο πρώτο μισό. Ελέγχεται η 1η θέση (Γιάννης), οπότε η αναζήτηση περιορίζεται στη 2η θέση, όπου βρίσκεται η Δανάη (τρεις προσπάθειες).
5. Για ποιους λόγους οι μέθοδοι ανάλυσης και επίλυσης προβλημάτων παρουσιάζουν ιδιαίτερο ενδιαφέρον;
• Μπορούν να αναπαρασταθούν με κοινές δομές δεδομένων και ελέγχου, που υποστηρίζονται από τις περισσότερες σύγχρονες γλώσσες προγραμματισμού.
• Παρέχουν τη δυνατότητα καταγραφής των χρονικών και «χωρικών» απαιτήσεων της μεθόδου επίλυσης, ώστε να γίνεται επακριβής εκτίμηση των αποτελεσμάτων.
Ερωτήσεις πολλαπλής επιλογής Τεχνικές Σχεδίασης Αλγορίθμων ΑΕΠΠ
Σε κάθε ερώτηση να επιλέξετε τη σωστή απάντηση. Υπάρχει μόνο μία σωστή επιλογή. Παραπάνω από 1 επιλογές στη πληροφορική Γ Λυκείου ΑΕΠΠ αν υπάρχουν στις εξετάσεις θα ζητηθεί και θα αναφερθεί ξεκάθαρα στην εκφώνηση των εξετάσεων.
1. Ποια είναι η προσέγγιση της μεθόδου Διαίρει και Βασίλευε;
- Από κάτω προς τα επάνω
- Από πάνω προς τα κάτω
- Τυχαία
- Από μέσα προς τα έξω
2. Ποιο είναι το τελευταίο βήμα της μεθόδου Διαίρει και Βασίλευε;
- Δίνεται για επίλυση ένα στιγμιότυπο του προβλήματος.
- Το στιγμιότυπο υποδιαιρείται σε υπο-στιγμιότυπα.
- Δίνεται ανεξάρτητη λύση σε κάθε υπο-στιγμιότυπο.
- Συνδυάζονται οι μερικές λύσεις για τη συνολική λύση.
3. Η δυαδική αναζήτηση εφαρμόζεται μόνο σε:
- μη ταξινομημένους πίνακες
- ταξινομημένους πίνακες
- δισδιάστατους πίνακες
- στοίβες
4. Ποιος είναι ο μέγιστος αριθμός συγκρίσεων της δυαδικής αναζήτησης σε 100 ταξινομημένα στοιχεία;
- 6
- 7
- 50
- 100
5. Ποιο από τα παρακάτω ΔΕΝ περιλαμβάνεται στην ανάλυση ενός προβλήματος σε σύγχρονο υπολογιστικό περιβάλλον;
- Η καταγραφή της υπάρχουσας πληροφορίας
- Η αναγνώριση των ιδιαιτεροτήτων του προβλήματος
- Η τελική επίλυση με υπολογιστικά συστήματα
- Η εισαγωγή και η εξαγωγή δεδομένων
| Ερώτηση | Σωστή απάντηση | Γιατί |
|---|---|---|
| 1 | β | Η προσέγγιση ονομάζεται «από πάνω προς τα κάτω» (top-down). Η προσέγγιση «από κάτω προς τα επάνω» ανήκει στον δυναμικό προγραμματισμό. |
| 2 | δ | Στο τέλος συνδυάζονται όλες οι μερικές λύσεις, ώστε να δοθεί η συνολική λύση του προβλήματος. |
| 3 | β | Η δυαδική αναζήτηση εφαρμόζεται μόνο σε ταξινομημένο σύνολο στοιχείων. |
| 4 | β | Το ακέραιο μέρος του [log2(100) + 1] είναι 7, αφού log2(100) είναι περίπου 6.64. |
| 5 | δ | Η ανάλυση περιλαμβάνει τα βήματα α, β και γ, καθώς και την αποτύπωση των συνθηκών και την πρόταση επίλυσης. Η εισαγωγή και η εξαγωγή δεδομένων δεν είναι βήμα της ανάλυσης. |
Άσκηση Αντιστοίχισης Τεχνικές Σχεδίασης Αλγορίθμων ΑΕΠΠ
Να αντιστοιχίσετε κάθε έννοια της στήλης Α με την περιγραφή της στη στήλη Β. Στη στήλη Β υπάρχουν δύο περιγραφές που περισσεύουν.
| Στήλη Α | Στήλη Β |
|---|---|
| 1. Διαίρει και Βασίλευε | α. Εύρεση μιας ρίζας της εξίσωσης f(x) = 0 σε ένα διάστημα [a, b]. |
| 2. Δυαδική αναζήτηση | β. Μέθοδος σχεδίασης αλγορίθμων με προσέγγιση από πάνω προς τα κάτω. |
| 3. Συγγενή προβλήματα | γ. Κλασικός αλγόριθμος της μεθόδου, που εφαρμόζεται μόνο σε ταξινομημένο σύνολο στοιχείων. |
| 4. Μέθοδος της διχοτόμησης | δ. Προσέγγιση από κάτω προς τα επάνω, με προσωρινή αποθήκευση των υπο-αποτελεσμάτων. |
| 5. Ευριστικές τεχνικές | ε. Προβλήματα που μπορούν να αναλυθούν με παρόμοιο τρόπο και να αντιμετωπιστούν με αντίστοιχες μεθόδους. |
| – | στ. Μέθοδοι για προβλήματα που απαιτούν μία νέα αντίληψη και δεν επιλύονται με τις γνωστές τεχνικές. |
| – | ζ. Επιλογή σε κάθε βήμα της τρέχουσας βέλτιστης επιλογής. |
| Στήλη Α | Αντιστοιχία | Γιατί |
|---|---|---|
| 1. Διαίρει και Βασίλευε | β | Υποδιαιρεί το πρόβλημα σε μικρότερα υποπροβλήματα, με προσέγγιση «από πάνω προς τα κάτω». |
| 2. Δυαδική αναζήτηση | γ | Ακολουθεί τη φιλοσοφία της μεθόδου και εφαρμόζεται μόνο σε ταξινομημένους πίνακες. |
| 3. Συγγενή προβλήματα | ε | Δεν υπάρχει ενιαίος κανόνας, αλλά υπάρχουν προβλήματα που αναλύονται με παρόμοιο τρόπο. |
| 4. Μέθοδος της διχοτόμησης | α | Βρίσκει μια ρίζα της εξίσωσης f(x) = 0 στο διάστημα [a, b], εξαιρώντας σε κάθε επανάληψη το μισό διάστημα. |
| 5. Ευριστικές τεχνικές | στ | Εφαρμόζονται σε προβλήματα που απαιτούν νέα αντίληψη. Οι περιγραφές δ (δυναμικός προγραμματισμός) και ζ (άπληστη μέθοδος) περισσεύουν. |
Αν θέλετε περισσότερες ερωτήσεις τύπου ανάπτυξης ή γενικότερα ερωτήσεις θεωρίας στην ύλη της Πληροφορικής Γ Λυκείου στο κεφάλαιο Τεχνικές Σχεδίασης Αλγορίθμων, δείτε τα τεστ, τα διαγωνίσματα και τις θεωρίες που έχουμε δημιουργήσει, για να καταφέρετε τον καλύτερο δυνατό βαθμό στις πανελλήνιες εξετάσεις.
Συχνές ερωτήσεις για τη θεωρία ΑΕΠΠ στις Τεχνικές Σχεδίασης Αλγορίθμων
Τι περιλαμβάνει η ανάλυση ενός προβλήματος;
Η ανάλυση ενός προβλήματος σε σύγχρονο υπολογιστικό περιβάλλον περιλαμβάνει την καταγραφή της υπάρχουσας πληροφορίας, την αναγνώριση των ιδιαιτεροτήτων του προβλήματος, την αποτύπωση των συνθηκών και προϋποθέσεων υλοποίησής του, την πρόταση επίλυσης με κάποια μέθοδο και την τελική επίλυση με υπολογιστικά συστήματα.
Σε ποιες ερωτήσεις πρέπει να απαντήσουμε κατά την ανάλυση ενός προβλήματος;
Ποια είναι τα δεδομένα και το μέγεθος του προβλήματος, ποιες συνθήκες πρέπει να πληρούνται, ποια είναι η πλέον αποδοτική μέθοδος επίλυσης, πώς θα καταγραφεί η λύση (π.χ. σε ψευδογλώσσα) και ποιος είναι ο τρόπος υλοποίησης στο συγκεκριμένο υπολογιστικό σύστημα.
Υπάρχει ενιαίος κανόνας για την επίλυση όλων των προβλημάτων;
Όχι. Δεν υπάρχει μία γενική φόρμουλα για την επίλυση του συνόλου των προβλημάτων. Υπάρχουν όμως συγγενή προβλήματα, δηλαδή προβλήματα που μπορούν να αναλυθούν με παρόμοιο τρόπο και να αντιμετωπιστούν με αντίστοιχες μεθόδους και τεχνικές.
Ποιες τεχνικές σχεδίασης αλγορίθμων εξετάζει το σχολικό βιβλίο;
Το σχολικό βιβλίο εξετάζει τρεις τυποποιημένες τεχνικές: τη μέθοδο Διαίρει και Βασίλευε, τη μέθοδο του δυναμικού προγραμματισμού και την άπληστη μέθοδο. Δεν υπάρχει αλγόριθμος για τη σχεδίαση αλγορίθμων, και η καταλληλότερη τεχνική επιλέγεται συγκρίνοντας τα χαρακτηριστικά κάθε τεχνικής.
Τι είναι η μέθοδος Διαίρει και Βασίλευε;
Είναι μέθοδος σχεδίασης αλγορίθμων που υποδιαιρεί ένα πρόβλημα σε μικρότερα υποπροβλήματα, με την ίδια τυποποίηση με το αρχικό πρόβλημα, αλλά μικρότερα σε μέγεθος. Η επίλυση προκύπτει από τη σταδιακή επίλυση των μικρότερων υποπροβλημάτων. Η προσέγγιση ονομάζεται «από πάνω προς τα κάτω» (top-down).
Ποια είναι τα βήματα της μεθόδου Διαίρει και Βασίλευε;
Πρώτα δίνεται για επίλυση ένα στιγμιότυπο του προβλήματος. Μετά το στιγμιότυπο υποδιαιρείται σε υπο-στιγμιότυπα του ίδιου προβλήματος. Έπειτα δίνεται ανεξάρτητη λύση σε κάθε υπο-στιγμιότυπο. Στο τέλος συνδυάζονται όλες οι μερικές λύσεις, ώστε να δοθεί η συνολική λύση.
Τι είναι η δυαδική αναζήτηση και πότε εφαρμόζεται;
Η δυαδική αναζήτηση είναι κλασικός αλγόριθμος της μεθόδου Διαίρει και Βασίλευε. Ελέγχει τη μεσαία θέση ενός πίνακα και συνεχίζει στο πρώτο ή στο δεύτερο μισό, ανάλογα με τη σύγκριση. Εφαρμόζεται μόνο σε ταξινομημένο σύνολο στοιχείων, δηλαδή σε ταξινομημένο πίνακα.
Πόσες συγκρίσεις χρειάζεται το πολύ η δυαδική αναζήτηση;
Ο μέγιστος αριθμός συγκρίσεων για n ταξινομημένα στοιχεία δίνεται από το ακέραιο μέρος του [log2(n) + 1]. Για 5 στοιχεία είναι 3, για 100 στοιχεία είναι 7 και για 1000 στοιχεία είναι 10.
Τι σχέση έχει η δυαδική αναζήτηση με τη μέθοδο της διχοτόμησης;
Ο τρόπος λειτουργίας της δυαδικής αναζήτησης είναι ανάλογος με αυτόν της μεθόδου της διχοτόμησης (ή του Bolzano), που βρίσκει μια ρίζα της εξίσωσης f(x) = 0 σε ένα διάστημα [a, b]. Και στις δύο μεθόδους σε κάθε επανάληψη εξαιρείται από την έρευνα το μισό τμήμα.

