Κεφάλαιο 05.1 – Σελίδα 102 – ΑΝΑΠΤΥΞΗ ΕΦΑΡΜΟΓΩΝ ΣΕ ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΟ ΠΕΡΙΒΑΛΛΟΝ Γ΄ ΛΥΚΕΙΟΥ – Απαντήσεις – Λύσεις

Ερωτήσεις - Θέματα για συζήτηση

Ερώτηση 1 (σελ. 102)

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

Σκέψη / Μεθοδολογία: Κλειστή ερώτηση απαρίθμησης — τα τρία ερωτήματα δίνονται ρητά στην αρχή του §5.1.

Λύση:

Ανατρέχουμε στην αρχή του §5.1 και απαριθμούμε τα τρία ερωτήματα που τίθενται.

Απάντηση: Τα πρωταρχικά ερωτήματα είναι: (1) πώς υπολογίζεται ο χρόνος εκτέλεσης ενός αλγορίθμου, (2) πώς μπορούν να συγκριθούν μεταξύ τους οι διάφοροι αλγόριθμοι, και (3) πώς μπορεί να γνωρίζει κανείς αν ένας αλγόριθμος είναι «βέλτιστος».

Πρόσεξε:

• Να αναφερθούν και τα τρία ερωτήματα, όχι μόνο το πρώτο.

Ερώτηση 2 (σελ. 102)

Τι είναι και πώς μπορεί να εκφρασθεί η χειρότερη περίπτωση ενός αλγορίθμου;

Σκέψη / Μεθοδολογία: Ανατρέχουμε στον ορισμό του §5.1.1: η χειρότερη περίπτωση αφορά το μέγιστο κόστος εκτέλεσης, και εκφράζεται με τον αριθμό βασικών πράξεων.

Λύση:

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

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

Πρόσεξε:

• Να αναφερθεί τόσο ο ορισμός (μέγιστο κόστος) όσο και ο τρόπος έκφρασης (μέτρηση βασικών πράξεων).

Ερώτηση 3 (σελ. 102)

Να περιγραφεί το μέγεθος της εισόδου ενός αλγορίθμου και να δοθεί ένα παράδειγμα αναγνώρισης και καταγραφής αυτού του μεγέθους.

Σκέψη / Μεθοδολογία: Δίνουμε τον ορισμό από το §5.1.2 και χρησιμοποιούμε τον Πίνακα 5.1 ως έτοιμο παράδειγμα αναγνώρισης μεγέθους εισόδου σε τρεις κατηγορίες προβλημάτων.

Λύση:

1. Ορίζουμε το μέγεθος εισόδου ως τη μεταβλητή (ή τις μεταβλητές) που εκφράζουν το πλήθος των δεδομένων που δίνονται στον αλγόριθμο.
2. Δίνουμε παράδειγμα από τον Πίνακα 5.1: στην ΤΑΞΙΝΟΜΗΣΗ το μέγεθος είναι το πλήθος των αντικειμένων προς ταξινόμηση, στην ΑΝΑΖΗΤΗΣΗ το πλήθος των στοιχείων του πίνακα, στον ΠΟΛΛΑΠΛΑΣΙΑΣΜΟ το πλήθος των ψηφίων των αριθμών.

Απάντηση: Το μέγεθος εισόδου ενός αλγορίθμου είναι η μεταβλητή (ή οι μεταβλητές) που εκφράζει το πλήθος των δεδομένων που δίνονται ως είσοδος και καθορίζει τη συμπεριφορά/το κόστος του αλγορίθμου. Παράδειγμα: στην αναζήτηση σε πίνακα, το μέγεθος εισόδου είναι το πλήθος n των στοιχείων του πίνακα· στην ταξινόμηση είναι το πλήθος των αντικειμένων προς ταξινόμηση· στον πολλαπλασιασμό είναι το πλήθος των ψηφίων των αριθμών.

Πρόσεξε:

• Το παράδειγμα πρέπει να δείχνει ρητά ποια μεταβλητή παίζει τον ρόλο του n.

Ερώτηση 4 (σελ. 102)

Από ποιους κύριους παράγοντες εξαρτάται ο χρόνος εκτέλεσης ενός αλγορίθμου;

Σκέψη / Μεθοδολογία: Κλειστή ερώτηση απαρίθμησης — οι πέντε παράγοντες δίνονται ρητά στο §5.1.4.

Λύση:

Ανατρέχουμε στη λίστα παραγόντων του §5.1.4 και τους απαριθμούμε.

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

Πρόσεξε:

• Να αναφερθούν και οι πέντε παράγοντες.

Ερώτηση 5 (σελ. 102)

Ποιες είναι οι απαραίτητες προϋποθέσεις για να είναι δυνατή η σύγκριση μεταξύ δύο προγραμμάτων αλγορίθμων;

Σκέψη / Μεθοδολογία: Κλειστή ερώτηση απαρίθμησης — οι τέσσερις προϋποθέσεις δίνονται ρητά στο §5.1.4.

Λύση:

Ανατρέχουμε στις τέσσερις προϋποθέσεις του §5.1.4 και τις απαριθμούμε.

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

Πρόσεξε:

• Να αναφερθούν και οι τέσσερις προϋποθέσεις.

Ερώτηση 6 (σελ. 102)

Να ορισθεί η αποδοτικότητα αλγορίθμων.

Σκέψη / Μεθοδολογία: Το βιβλίο δεν δίνει μονολεκτικό τυπικό ορισμό, αλλά περιγράφει την αποδοτικότητα μέσω σύγκρισης δύο αλγορίθμων με το ίδιο αποτέλεσμα — συνθέτουμε τον ορισμό από αυτή την περιγραφή.

Λύση:

1. Θεωρούμε δύο αλγόριθμους Α και Β που δίνουν το ίδιο αποτέλεσμα.
2. Ορίζουμε ότι ο Β είναι αποδοτικότερος του Α αν πετυχαίνει το ίδιο αποτέλεσμα σε λιγότερο χρόνο ή με χρήση λιγότερης μνήμης.
3. Προσθέτουμε την προϋπόθεση ότι η σύγκριση γίνεται με τα ίδια δεδομένα και τις ίδιες συνθήκες.

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

Πρόσεξε:

• Δεν υπάρχει μονολεκτικός ορισμός στο βιβλίο — αξιολογείται η σύνδεση με τη σύγκριση χρόνου/μνήμης υπό τις ίδιες συνθήκες.