Κεφ4 Εν 2 Flashcards
Κάθε πρόβλημα επιλύεται με μία μόνο λύση;
τις περισσότερες φορες ενα προβλημα επιλύεται με περισσότερες από μια λύσεις όπου η καθε λυση μπορεί να προέλθει από ποικίλες και διαφορετικες προσεγγίσεις, τεχνικες και μεθόδους
Γιατί πρέπει να γίνεται μία καλή ανάλυση του κάθε προβλήματος πριν από την επίλυση του;
επειδή τις περισσότερες φορές ένα πρόβλημα επιλύεται με περισσότερες απο μια λυσεις, όπου η κάθε λύση μπορεί να προέλθει από ποικίλες και διαφορετικές προσεγγίσεις, τεχνικές και μεθόδους, είναι απαραίτητο να γίνεται μία καλή ανάλυση του προβλήματος, ώστε να προτείνεται συγκεκριμένη μεθοδολογία και ακολουθία βημάτων καθώς και να προταθούν έξυπνες και αποδοτικές λύσεις
Τι περιλαμβάνει ανάλυση ενός προβλήματος σε ένα σύγχρονο
προγραμματιστικό περιβάλλον
Η ανάλυση ενός προβλήματος σε ένα σύγχρονο υπολογιστικό περιβάλλον περιλαμβάνει:
•την καταγραφή της υπάρχουσας πληροφορίας για το πρόβλημα,
•την αναγνώριση των ιδιαιτεροτήτων του προβλήματος,
•την αποτύπωση των συνθηκών και προϋποθέσεων υλοποίησής του,
και στη συνέχεια:
•την πρόταση επίλυσης με χρήση κάποιας μεθόδου,
•και την τελική επίλυση με χρήση υπολογιστικών συστημάτων.
Κατά την ανάλυση ενός προβλήματος σε ποιες ερωτήσεις θα πρέπει να δοθούν απαντήσεις;
Κατά την ανάλυση ενός προβλήματος θα πρέπει να δοθούν απαντήσεις σε κάθε μία από τις παρακάτω πέντε ερωτήσεις:
1 . Ποια είναι τα δεδομένα και ποιο το μέγεθος του προβλήματος;
- Ποιες είναι οι συνθήκες που πρέπει να πληρούνται για την επίλυση του προβλήματος
- Ποια είναι η πλέον αποδοτική μέθοδος επίλυσής του (σχεδίαση αλγορίθμου);
- Πώς θα καταγραφεί η λύση του προβλήματος; (Παράδειγμα, σε ψευδογλώσσα).
S. Ποιος είναι ο τρόπος υλοποίησης της λύσης στο συγκεκριμένο υπολογιστικό σύστημα; (Παράδειγμα, επιλογή γλώσσας προγραμματισμού)
Γιατί είναι απαραίτητη η ανάλυση ενός προβλήματος
Η ανάλυση κάθε προβλήματος είναι απαραίτητη, για να αναζητηθεί η πιο κατάλληλη μέθοδος που θα παρέχει τη ζητούμενη λύση, όσο γίνεται ταχύτερα και με το λιγότερο δυνατό κόστος σε υπολογιστικούς πόρους.
- Ποια προβλήματα ονομάζονται «συγγενή »
συγγενή είναι τα προβλήματα που μπορούν να αναλυθούν με παρόμοιο τροπο και να αντιμετωπισθούν με αντίστοιχε ς μεθόδους και τεχνικες
Υπάρχει ένας ενιαίος κανόνας που να αναφέρεται στην επίλυση όλων των προβλημάτων;
Δεν υπάρχει ένας ενιαίος κανόνας, δηλαδή μία γενική φόρμουλα που να αναφέρεται στην επίλυση του συνόλου των προβλημάτων. Απλώς υπάρχουν τα συγγενή προβλήματα, δηλαδή αυτά που μπορούν να αναλυθούν με παρόμοιο τρόπο και να αντιμετωπισθούν με αντίστοιχες μεθόδους και τεχνικές.
Γιατί παρουσιάζουν ιδιαίτερο ενδιαφέρον οι μέθοδοι ανάλυσης και επίλυσης προβλημάτων;
Οι μέθοδοι ανάλυσης και επίλυσης των προβλημάτων παρουσιάζουν ιδιαίτερο ενδιαφέρον για τους εξής λόγους:
• παρέχουν ένα γενικό πρότυπο το οποίο είναι κατάλληλο για την επίλυση προβλημάτων ευρείας κλίμακας,
•μπορούν να αναπαρασταθούν με κοινές δομές δεδομένων και ελέγχου οι οποίες υποστηρίζονται από τις περισσότερες σύγχρονες γλώσσες προγραμματισμού
• παρέχουν τη δυνατότητα καταγραφής των χρονικών και χωρικών απαιτήσεων της μεθόδου επίλυσης, για να μπορεί να γίνει επακριβής εκτίμηση των αποτελε σμάτων.
- Τι είναι η μέθοδος «διαίρει και βασίλευε»;
Η «διαίρει και βασίλευε» αποτελεί μια μέθοδο σχεδίασης αλγορίθμων στην οποία εντάσσονται οι τεχνικές που υποδιαιρούμε το αρχικό πρόβλημα, σε μικρότερα υποπροβλήματα τα οποία έχουν την ίδια τυποποίηση με το αρχικό πρόβλημα αλλά είναι μικρότερα σε μέγεθος . με τον ιδιο τρόπο, τα υπαπροβληματα αυτα μπορούν να διαιρείουν σε ακόμα μικρότερα υπο προβλήματα κοκ. ετι η επίλυση ενος προβλήματος έγκειται στη σταδιακή επίλυση των οδο το δυνατόν μικρότερων υπο προβλημάτων ωστε τελικά να προκύψει η συνολική λύση η του αρχικού ευρύτερου προβλήματος . Η προσέγγιση αυτή ονομάζεται «από πάνω προς τα κάτω» (top-down).
Τι είναι η προσέγγιση λύσης «από πάνω προς τα κατω
Η προσέγγιση λύσης εε από πάνω προς τα κάτω, είναι μια τεχνική κατά την οποία κάθε πρόβλημα διαιρεί ται σε μικρότερα επιμέρους υποπροβλήματα και κάθε ενα από αυτά τα υπο προβλήματα διαιρείται σε ακόμα απλούστερα και μικρότερα υποπροβλήματα. στο τέλος τα επιμέρους υποπροβλήματα είναι αρκετά απλα, ωστε η σταδιακή επίλυση τους, επιφέρει και τη νσυνολική λύση του αρχικού προβλήματος
Να αποδώσετε τα βήματα εφαρμογής της μεθόδου «διαίρει και βασίλευε» στη λύση ενός προβλήματος.
Η μέθοδος σχεδίασης αλγορίθμων «διαίρει και βασίλευε» μπορεί να αποδοθεί με τα επόμενα βήματα:
1. Δίνεται για λύση ένα στιγμιότυπο ενός προβλήματος.
- Το στιγμιότυπο του προβλήματος υποδιαιρεί ται σε υπο- στιγμιότυπα του ιδιου προβλήματος
- . Δίνεται ανεξάρτητη λύση σε κάθε ένα υπο-στιγμιότυπο.
- συνδυάζονται όλες οι μερικές λύσεις που βρέθηκαν για τα υπο-στιγμιότυπα, έται ώστε να δοθεί η συνολική λύση του προβλήματος
Πώς υλοποιείται η μέθοδος «διαίρει και βασίλευε» στο πλαίσιο του μαθήματος;
Στο πλαίσιο του μαθήματος η υλοποίηση της μεθόδου «διαίρει και βασίλευε» γίνεται με την επαναληπτική προσέγγιση δηλαδή με διαδοχικές επαναλήψεις.
Ποιος είναι ο μέγιστος αριθμός των συγκρίσεων που απαιτούνται για την εύρεση ενός στοιχείου σε ένα σύνολο «n » ταξινομημένων στοιχείων με τη μέθοδο «διαίρει και βασίλευε»;
Ο μέγιστος αριθμός των συγκρίσεων που απαιτούνται για την εύρεση ενός στοιχείου σε ένα σύνολο «n » ταξινομημένων στοιχείων, συμπεριλαμβανομένης και της περίπτωσης μη ύπαρξης του στοιχείου, δίνεται από το ακέραιο μέρος της πράξης log2(n) + 1) με στρογγυλοποίηση προς τα κάτω.
Για παράδειγμα, σε ένα σύνολο 100 ταξινομημένων στοιχείων (n=100), ο μέγιστος αριθμός συγκρίσεων είναι: [log2(100)+1] = [6,64+1]=[7,64]=7.
. Ποιος γνωστός αλγόριθμος εφαρμόζει τη φιλοσοφία της μεθόδου «διαίρει και βασίλευε»;
Ένας κλασικός αλγόριθμος που ακολουθεί τη φιλοσοφία της μεθόδου «διαίρει και βασίλευε» είναι η «δυαδική αναζήτηση», η οποία εφαρμόζεται μόνο στην περίπτωση ταξινομημένου συνόλου στοιχείων (
