Πληροφορική · Β΄ Λυκείου
Θεωρητική πληροφορική
Διάρκεια 45΄ · 100 μονάδες
Θέμα Α25 μονάδες
Στις ερωτήσεις 1–4 να επιλέξεις τη σωστή απάντηση. Στην ερώτηση 5 να χαρακτηρίσεις κάθε πρόταση ως Σωστή ή Λανθασμένη.
- 1.
- 2.
- 3.
- 4.
- 5.
Χαρακτήρισε κάθε πρόταση ως Σωστή (Σ) ή Λανθασμένη (Λ).(5 μονάδες)
Θέμα Β25 μονάδες
Να απαντήσεις και να αιτιολογήσεις.
- 1.
Να κατατάξεις ως επιλύσιμο, ανοικτό ή άλυτο καθένα από τα προβλήματα και να αιτιολογήσεις: (α) η ταξινόμηση αριθμών· (β) η εικασία Collatz· (γ) ένα πρόγραμμα που δέχεται οποιοδήποτε πρόγραμμα με τα δεδομένα του και απαντά πάντα σωστά αν θα τερματίσει.(12 μονάδες)
- 2.
Ο αλγόριθμος του Ευκλείδη λέει: «Όσο ο δεν είναι , αντικατάστησε το ζεύγος με το . Στο τέλος τύπωσε το ». Να τον εκτελέσεις για , και να εξηγήσεις γιατί τερματίζει για κάθε είσοδο φυσικών αριθμών.(13 μονάδες)
Θέμα Γ25 μονάδες
Δίνεται η συνάρτηση σε Python:
def mystery(n): steps = 0 i = 1 while i < n: i = i * 2 steps += 1 return steps- α)
Τι επιστρέφει το
mystery(16); Να γράψεις τις τιμές τουi.(6 μονάδες) - β)
Τι επιστρέφει το
mystery(1000);(6 μονάδες) - γ)
Ποια είναι η τάξη πολυπλοκότητας της συνάρτησης; Να αιτιολογήσεις.(6 μονάδες)
- δ)
Πόσες επαναλήψεις προστίθενται όταν το διπλασιάζεται; Να το επαληθεύσεις με το
mystery(2000).(7 μονάδες)
- α)
Θέμα Δ25 μονάδες
Η συνάρτηση ελέγχει αν δύο διαφορετικά στοιχεία μιας λίστας έχουν άθροισμα ίσο με
target, δοκιμάζοντας κάθε ζεύγος.def has_pair(items, target): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] + items[j] == target: return True return False- α)
Ποια είναι η χειρότερη περίπτωση για τη συνάρτηση, και πόσες συγκρίσεις
items[i] + items[j] == targetγίνονται τότε για λίστα στοιχείων;(6 μονάδες) - β)
Ποια είναι η τάξη πολυπλοκότητας; Να αιτιολογήσεις.(6 μονάδες)
- γ)
Για η συνάρτηση χρειάζεται s στη χειρότερη περίπτωση. Πόσο περίπου θα χρειαστεί για ; Πόσο θα χρειαζόταν ένας αλγόριθμος με τον ίδιο χρόνο για ;(6 μονάδες)
- δ)
Ένας άλλος αλγόριθμος δοκιμάζει όλα τα υποσύνολα της λίστας, δηλαδή κάνει βήματα. Πόσο θα χρειαζόταν για σε υπολογιστή που κάνει βήματα το δευτερόλεπτο; Τι δείχνει αυτό για τα προβλήματα που είναι επιλύσιμα;(7 μονάδες)
- α)
Καλή επιτυχία!