Μετάβαση στο περιεχόμενο

Θεωρητική πληροφορική

Διαγώνισμα στις ενότητες: Η επιστήμη των υπολογιστών · Προβλήματα και υπολογισιμότητα · Πολυπλοκότητα αλγορίθμων.

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

Πληροφορική · Β΄ Λυκείου

Θεωρητική πληροφορική

Διάρκεια 45΄ · 100 μονάδες

Θέμα Α25 μονάδες

Στις ερωτήσεις 1–4 να επιλέξεις τη σωστή απάντηση. Στην ερώτηση 5 να χαρακτηρίσεις κάθε πρόταση ως Σωστή ή Λανθασμένη.

  1. 1.
    Το κριτήριο που απαιτεί κάθε εντολή ενός αλγορίθμου να είναι απλή και εκτελέσιμη στην πράξη λέγεται:(5 μονάδες)
  2. 2.
    Η εικασία του Goldbach (κάθε άρτιος μεγαλύτερος του 22 είναι άθροισμα δύο πρώτων) είναι πρόβλημα:(5 μονάδες)
  3. 3.
    Ένας αλγόριθμος κάνει 5n2+100n+35n^2 + 100n + 3 βήματα. Η τάξη του είναι:(5 μονάδες)
  4. 4.
    Πόσες συγκρίσεις χρειάζεται στη χειρότερη περίπτωση η δυαδική αναζήτηση σε ταξινομημένο πίνακα 40004000 στοιχείων;(5 μονάδες)
  5. 5.

    Χαρακτήρισε κάθε πρόταση ως Σωστή (Σ) ή Λανθασμένη (Λ).(5 μονάδες)

    • Πρόταση αα)Η θέση Church–Turing είναι θεώρημα που έχει αποδειχθεί.
    • Πρόταση ββ)Ο Turing όρισε τη μηχανή του (1936) πριν χτιστεί ηλεκτρονικός υπολογιστής γενικής χρήσης.
    • Πρόταση γγ)Πρόβλημα απόφασης είναι εκείνο που η απάντησή του είναι ναι ή όχι.
    • Πρόταση δδ)Ένας αλγόριθμος O(n)O(n) είναι γρηγορότερος από έναν O(n2)O(n^2) για κάθε μέγεθος εισόδου.
    • Πρόταση εε)Δεδομένα είναι ό,τι προκύπτει από την επεξεργασία της πληροφορίας.

Θέμα Β25 μονάδες

Να απαντήσεις και να αιτιολογήσεις.

  1. 1.

    Να κατατάξεις ως επιλύσιμο, ανοικτό ή άλυτο καθένα από τα προβλήματα και να αιτιολογήσεις: (α) η ταξινόμηση 10 00010\,000 αριθμών· (β) η εικασία Collatz· (γ) ένα πρόγραμμα που δέχεται οποιοδήποτε πρόγραμμα με τα δεδομένα του και απαντά πάντα σωστά αν θα τερματίσει.(12 μονάδες)

  2. 2.

    Ο αλγόριθμος του Ευκλείδη λέει: «Όσο ο bb δεν είναι 00, αντικατάστησε το ζεύγος (a,b)(a, b) με το (b,a mod b)(b, a \bmod b). Στο τέλος τύπωσε το aa». Να τον εκτελέσεις για a=84a = 84, b=36b = 36 και να εξηγήσεις γιατί τερματίζει για κάθε είσοδο φυσικών αριθμών.(13 μονάδες)

Θέμα Γ25 μονάδες

  1. Δίνεται η συνάρτηση σε Python:

    def mystery(n):
        steps = 0
        i = 1
        while i < n:
            i = i * 2
            steps += 1
        return steps
    1. α)

      Τι επιστρέφει το mystery(16); Να γράψεις τις τιμές του i.(6 μονάδες)

    2. β)

      Τι επιστρέφει το mystery(1000);(6 μονάδες)

    3. γ)

      Ποια είναι η τάξη πολυπλοκότητας της συνάρτησης; Να αιτιολογήσεις.(6 μονάδες)

    4. δ)

      Πόσες επαναλήψεις προστίθενται όταν το nn διπλασιάζεται; Να το επαληθεύσεις με το mystery(2000).(7 μονάδες)

Θέμα Δ25 μονάδες

  1. Η συνάρτηση ελέγχει αν δύο διαφορετικά στοιχεία μιας λίστας έχουν άθροισμα ίσο με 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
    1. α)

      Ποια είναι η χειρότερη περίπτωση για τη συνάρτηση, και πόσες συγκρίσεις items[i] + items[j] == target γίνονται τότε για λίστα 88 στοιχείων;(6 μονάδες)

    2. β)

      Ποια είναι η τάξη πολυπλοκότητας; Να αιτιολογήσεις.(6 μονάδες)

    3. γ)

      Για n=2000n = 2000 η συνάρτηση χρειάζεται 0,50{,}5 s στη χειρότερη περίπτωση. Πόσο περίπου θα χρειαστεί για n=8000n = 8000; Πόσο θα χρειαζόταν ένας αλγόριθμος O(n)O(n) με τον ίδιο χρόνο για n=2000n = 2000;(6 μονάδες)

    4. δ)

      Ένας άλλος αλγόριθμος δοκιμάζει όλα τα υποσύνολα της λίστας, δηλαδή κάνει 2n2^n βήματα. Πόσο θα χρειαζόταν για n=50n = 50 σε υπολογιστή που κάνει 10910^9 βήματα το δευτερόλεπτο; Τι δείχνει αυτό για τα προβλήματα που είναι επιλύσιμα;(7 μονάδες)

Καλή επιτυχία!

9 κλειστές απαντήσεις είναι ακόμα κενές.

Όλες οι ενότητες