Τεχνικές Σχεδίασης Αλγορίθμων Θεωρία
Πληροφορική Γ Λυκείου ΑΕΠΠ

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

Σε αυτή τη σελίδα θα δείτε την ανάλυση προβλημάτων, τις μεθόδους σχεδίασης αλγορίθμων και τη μέθοδο «Διαίρει και Βασίλευε», με κλασικό παράδειγμα τη δυαδική αναζήτηση. Θα βρείτε επίσης ερωτήσεις Σωστό / Λάθος, ερωτήσεις ανάπτυξης, πολλαπλής επιλογής και αντιστοίχισης. Όλα βασισμένα στο επίπεδο των εξετάσεων που θα πρέπει να έχετε για να γράψετε καλά στις πανελλήνιες εξετάσεις στο μάθημα της πληροφορικής Γ λυκείου (ΑΕΠΠ).

4.1 Ανάλυση προβλημάτων Κεφάλαιο Θεωρίας ΑΕΠΠ

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

Τι περιλαμβάνει η ανάλυση ενός προβλήματος

Η ανάλυση ενός προβλήματος σε ένα σύγχρονο υπολογιστικό περιβάλλον περιλαμβάνει:

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

και στη συνέχεια:

  1. την πρόταση επίλυσης με χρήση κάποιας μεθόδου, και
  2. την τελική επίλυση με χρήση υπολογιστικών συστημάτων.

Ποιες ερωτήσεις πρέπει να απαντηθούν

Κατά την ανάλυση ενός προβλήματος θα πρέπει να δοθεί απάντηση σε κάθε μία από τις επόμενες ερωτήσεις:

  1. Ποια είναι τα δεδομένα και το μέγεθος του προβλήματος;
  2. Ποιες είναι οι συνθήκες που πρέπει να πληρούνται για την επίλυση του προβλήματος;
  3. Ποια είναι η πλέον αποδοτική μέθοδος επίλυσής του (σχεδίαση αλγορίθμου);
  4. Πώς θα καταγραφεί η λύση του προβλήματος (π.χ. σε ψευδογλώσσα);
  5. Ποιος είναι ο τρόπος υλοποίησης στο συγκεκριμένο υπολογιστικό σύστημα (π.χ. επιλογή γλώσσας προγραμματισμού);

Παράδειγμα θεωρητικό ανάλυσης προβλήματος ΑΕΠΠ

Ένας ταχυδρομικός διανομέας πρέπει να ξεκινήσει από ένα χωριό, να επισκεφθεί έναν αριθμό γειτονικών χωριών για να μοιράσει επιστολές και να επιστρέψει στο χωριό από όπου ξεκίνησε, περνώντας μόνο μία φορά από κάθε χωριό. Το πρόβλημα είναι να βρεθεί η καλύτερη διαδρομή, ώστε να διανύσει το μικρότερο δυνατό αριθμό χιλιομέτρων. Στο σχήμα του βιβλίου υπάρχουν 4 χωριά (κόμβοι), 6 οδικές αρτηρίες (συνδέσεις) και οι χιλιομετρικές αποστάσεις τους. Ο διανομέας ξεκινά από το χωριό 1.

Δύο διαφορετικές αναλύσεις του ίδιου προβλήματος
ΑνάλυσηΒήματαΣυνολική απόσταση
Α) Πρώτη ανάλυση1. Καταγραφή όλων των αποστάσεων μεταξύ των χωριών. 2. Ταξινόμηση των συνδέσεων κατά αύξουσα χιλιομετρική απόσταση. 3. Επιλογή κάθε φορά της μετάβασης προς το πλησιέστερο χωριό.36 χιλιόμετρα
Β) Διαφορετική ανάλυση1. Καταγραφή όλων των αποστάσεων μεταξύ των χωριών. 2. Εύρεση σειράς επίσκεψης με στόχο την ελαχιστοποίηση της συνολικής απόστασης και όχι της κάθε φορά απόστασης.30 χιλιόμετρα
Η ανάλυση κάθε προβλήματος είναι απαραίτητη, ώστε να αναζητηθεί η πλέον κατάλληλη μέθοδος που παρέχει τη ζητούμενη λύση όσο γίνεται ταχύτερα και με το λιγότερο δυνατό κόστος σε υπολογιστικούς πόρους.

Συγγενή προβλήματα Θεωρία ΑΕΠΠ

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

Γιατί ενδιαφέρουν οι μέθοδοι ανάλυσης και επίλυσης - Ορισμός ΑΕΠΠ

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

4.2 Μέθοδοι σχεδίασης αλγορίθμων Κεφάλαιο Θεωρίας ΑΕΠΠ

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

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

Τι χρειάζεται να υποστηρίζει κάθε τεχνική σχεδίασης αλγορίθμων στο ΑΕΠΠ

  • να αντιμετωπίζει με το δικό της τρόπο τα δεδομένα,
  • να έχει τη δική της ακολουθία εντολών,
  • να διαθέτει τη δική της αποδοτικότητα.

Οι τυποποιημένες κατηγορίες τεχνικών

Στη βιβλιογραφία αναφέρονται αρκετές τυποποιημένες κατηγορίες τεχνικών. Στο σχολικό βιβλίο εξετάζονται οι εξής:

  • Μέθοδος Διαίρει και Βασίλευε
  • Μέθοδος δυναμικού προγραμματισμού
  • Άπληστη μέθοδος

Αυτό δεν σημαίνει ότι κάθε πρόβλημα μπορεί να επιλυθεί με μία από τις γνωστές τεχνικές. Υπάρχουν πολλά προβλήματα που απαιτούν την εφαρμογή μίας νέας αντίληψης. Συχνά οι μέθοδοι που εφαρμόζονται σε αυτά ονομάζονται ευριστικές τεχνικές.

Μέθοδος Διαίρει και Βασίλευε Θεωρία ΑΕΠΠ

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

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

Βήματα της μεθόδου Διαίρει και Βασίλευε Γ Λυκείου ΑΕΠΠ

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

Δυαδική αναζήτηση Θεωρία και Παράδειγμα ΑΕΠΠ

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

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

Έστω ένας ηλεκτρονικός τηλεφωνικός κατάλογος, δηλαδή ένας πίνακας με n ονόματα και έναν αριθμό τηλεφώνου για κάθε όνομα, ταξινομημένος κατά αύξουσα αλφαβητική τάξη ως προς τα ονόματα. Τα ονόματα και τα τηλέφωνα είναι αποθηκευμένα σε δύο πίνακες, names[1..n] και phones[1..n]. Ζητείται το τηλέφωνο που αντιστοιχεί σε δεδομένο όνομα. Όταν δοθεί ένα όνομα, υπάρχουν 3 περιπτώσεις:

  1. το όνομα βρίσκεται στη μεσαία θέση του πίνακα names,
  2. το όνομα βρίσκεται σε μία θέση στο πρώτο μισό του πίνακα names,
  3. το όνομα βρίσκεται σε μία θέση στο δεύτερο μισό του πίνακα names.

Λύση στο Παράδειγμα Δυαδικής Αναζήτησης στη Θεωρία ΑΕΠΠ

Στον πίνακα πέντε θέσεων αναζητείται το όνομα Δανάη. Η αναζήτηση χρειάζεται τρεις προσπάθειες:

Τα βήματα της δυαδικής αναζήτησης του ονόματος Δανάη
ΠροσπάθειαΘέση που ελέγχεταιΌνομα στη θέσηΣύγκριση και συνέχεια
1η3η (η μεσαία)ΚατερίναΗ Δανάη είναι λεξικογραφικά μικρότερη, άρα η αναζήτηση περιορίζεται στο πρώτο μισό (2 θέσεις).
2η1ηΓιάννηςΗ Δανάη είναι λεξικογραφικά μεγαλύτερη, άρα η αναζήτηση περιορίζεται στη 2η θέση.
3η2ηΔανάηΒρέθηκε το τηλέφωνο της Δανάης.

Ο αλγόριθμος της δυαδικής αναζήτησης

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

Ο αλγόριθμος αυτός αντιμετωπίζει και την περίπτωση της ανεπιτυχούς αναζήτησης, όταν το αναζητούμενο στοιχείο δεν υπάρχει στον πίνακα.

Ερώτηση, πόσες συγκρίσεις χρειάζεται η δυαδική αναζήτησηστη θεωρία

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

Μέγιστος αριθμός συγκρίσεων στη δυαδική αναζήτηση
Πλήθος στοιχείων nlog2(n) + 1Μέγιστος αριθμός συγκρίσεων
5περίπου 3.323
100περίπου 7.647
1000περίπου 10.9710

Σωστό / Λάθος και ασκήσεις θεωρίας ΑΕΠΠ Τεχνικές Σχεδίασης Αλγορίθμων

Ερωτήσεις Σωστό / Λάθος Τεχνικές Σχεδίασης Αλγορίθμων

Απαντήστε πρώτα μόνοι σας και μετά ελέγξτε τις απαντήσεις στον πίνακα.

  1. Η ανάλυση ενός προβλήματος σε ένα σύγχρονο υπολογιστικό περιβάλλον περιλαμβάνει την εισαγωγή και την εξαγωγή δεδομένων.
  2. Η μέθοδος Διαίρει και Βασίλευε είναι μία μέθοδος σχεδίασης αλγορίθμων.
  3. Μειονέκτημα των μεθόδων ανάλυσης προβλημάτων είναι ότι εντοπίζουν την πλέον κατάλληλη και αποδοτική λύση.
  4. Υπάρχει ενιαίος κανόνας που να αναφέρεται στην επίλυση όλων των προβλημάτων.
  5. Ένας κλασικός αλγόριθμος που ακολουθεί τη φιλοσοφία της μεθόδου Διαίρει και Βασίλευε είναι η δυαδική αναζήτηση.
  6. Η δυαδική αναζήτηση μπορεί να εφαρμοστεί και σε μη ταξινομημένο πίνακα.
  7. Η προσέγγιση της μεθόδου Διαίρει και Βασίλευε ονομάζεται «από κάτω προς τα επάνω».
  8. Στη μέθοδο Διαίρει και Βασίλευε τα υποπροβλήματα έχουν την ίδια τυποποίηση με το αρχικό πρόβλημα.
  9. Ο τρόπος που λειτουργεί η δυαδική αναζήτηση είναι ανάλογος με αυτόν της μεθόδου της διχοτόμησης.
  10. Κάθε πρόβλημα επιλύεται πάντοτε με μία μόνο λύση.
Απαντήσεις των ερωτήσεων Σωστό / Λάθος Τεχνικές Σχεδίασης Αλγορίθμων
Α/ΑΑπάντησηΓιατί
1ΛάθοςΗ ανάλυση περιλαμβάνει την καταγραφή της πληροφορίας, την αναγνώριση των ιδιαιτεροτήτων, την αποτύπωση των συνθηκών, την πρόταση επίλυσης και την τελική επίλυση.
2ΣωστόΗ Διαίρει και Βασίλευε είναι μία από τις μεθόδους σχεδίασης αλγορίθμων.
3ΛάθοςΤο να εντοπίζεται η πλέον κατάλληλη και αποδοτική λύση είναι πλεονέκτημα και όχι μειονέκτημα.
4ΛάθοςΔεν υπάρχει ενιαίος κανόνας. Υπάρχουν μόνο συγγενή προβλήματα, που αντιμετωπίζονται με αντίστοιχες μεθόδους.
5ΣωστόΗ δυαδική αναζήτηση είναι κλασικός αλγόριθμος της μεθόδου Διαίρει και Βασίλευε.
6ΛάθοςΗ δυαδική αναζήτηση εφαρμόζεται μόνο σε ταξινομημένο σύνολο στοιχείων.
7ΛάθοςΗ προσέγγιση αυτή ονομάζεται «από πάνω προς τα κάτω» (top-down). Η προσέγγιση «από κάτω προς τα επάνω» ανήκει στον δυναμικό προγραμματισμό.
8ΣωστόΤα υποπροβλήματα έχουν την ίδια τυποποίηση με το αρχικό, αλλά είναι μικρότερα σε μέγεθος.
9ΣωστόΚαι στις δύο μεθόδους σε κάθε βήμα εξαιρείται από την έρευνα το μισό τμήμα.
10ΛάθοςΕίναι πιθανόν ένα πρόβλημα να μην επιλύεται με μία μόνο λύση αλλά με περισσότερες.

Ερωτήσεις ανάπτυξης Τεχνικές Σχεδίασης Αλγορίθμων ΑΕΠΠ

Οι λύσεις είναι γραμμένες όπως θα ζητηθούν στις πανελλήνιες εξετάσεις της Πληροφορικής Γ Λυκείου ΑΕΠΠ. Να είστε προσεκτικοί γιατί τις ερωτήσεις ανάπτυξης τις θέλουν στις εξετάσεις ακριβώς όπως είναι στη θεωρία της Πληροφορικής ΑΕΠΠ Γ λυκείου.

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

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

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

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

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

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

4. Να περιγράψετε τη μέθοδο της δυαδικής αναζήτησης και να δώσετε ένα παράδειγμα.

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

Παράδειγμα: στον τηλεφωνικό κατάλογο των πέντε θέσεων αναζητείται η Δανάη. Ελέγχεται η 3η θέση (Κατερίνα), οπότε η αναζήτηση περιορίζεται στο πρώτο μισό. Ελέγχεται η 1η θέση (Γιάννης), οπότε η αναζήτηση περιορίζεται στη 2η θέση, όπου βρίσκεται η Δανάη (τρεις προσπάθειες).

5. Για ποιους λόγους οι μέθοδοι ανάλυσης και επίλυσης προβλημάτων παρουσιάζουν ιδιαίτερο ενδιαφέρον;

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

Ερωτήσεις πολλαπλής επιλογής Τεχνικές Σχεδίασης Αλγορίθμων ΑΕΠΠ

Σε κάθε ερώτηση να επιλέξετε τη σωστή απάντηση. Υπάρχει μόνο μία σωστή επιλογή. Παραπάνω από 1 επιλογές στη πληροφορική Γ Λυκείου ΑΕΠΠ αν υπάρχουν στις εξετάσεις θα ζητηθεί και θα αναφερθεί ξεκάθαρα στην εκφώνηση των εξετάσεων.

1. Ποια είναι η προσέγγιση της μεθόδου Διαίρει και Βασίλευε;

  1. Από κάτω προς τα επάνω
  2. Από πάνω προς τα κάτω
  3. Τυχαία
  4. Από μέσα προς τα έξω

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

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

3. Η δυαδική αναζήτηση εφαρμόζεται μόνο σε:

  1. μη ταξινομημένους πίνακες
  2. ταξινομημένους πίνακες
  3. δισδιάστατους πίνακες
  4. στοίβες

4. Ποιος είναι ο μέγιστος αριθμός συγκρίσεων της δυαδικής αναζήτησης σε 100 ταξινομημένα στοιχεία;

  1. 6
  2. 7
  3. 50
  4. 100

5. Ποιο από τα παρακάτω ΔΕΝ περιλαμβάνεται στην ανάλυση ενός προβλήματος σε σύγχρονο υπολογιστικό περιβάλλον;

  1. Η καταγραφή της υπάρχουσας πληροφορίας
  2. Η αναγνώριση των ιδιαιτεροτήτων του προβλήματος
  3. Η τελική επίλυση με υπολογιστικά συστήματα
  4. Η εισαγωγή και η εξαγωγή δεδομένων
Απαντήσεις Τεχνικές Σχεδίασης Αλγορίθμων θεωρία ΑΕΠΠ
ΕρώτησηΣωστή απάντησηΓιατί
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]. Και στις δύο μεθόδους σε κάθε επανάληψη εξαιρείται από την έρευνα το μισό τμήμα.