Εισαγωγή στους Αλγόριθμους — Οκτώβριος 2024 — ηλεκτρονική εξέταση¶

Μεταγραφή από τα τέσσερα στιγμιότυπα της ηλεκτρονικής εξέτασης της 10/10/2024.

Screenshot_2024-10-10_at_7.00.46_PM.png¶

Ερώτηση 1 / 4 (Συμπλήρωση Κενών (Χαλαρή Ταυτοποίηση) — 3 βαθμοί)

Σύγκριση ρυθμών αύξησης

Στην άσκηση που ακολουθεί, ο αριθμός "α" υπολογίζεται διαιρώντας τα τελευταία 2 ψηφία του ΑΜ σας με το 4 και προσθέτοντας στο υπόλοιπο τον αριθμό 1. $$a = ((AM \bmod 100) \bmod 4) + 1$$

Έστω ένας υπολογιστής που εκτελεί $2^6$ στοιχειώδεις λειτουργίες ανά δευτερόλεπτο. Αν για την επίλυση ενός προβλήματος μεγέθους $n$, έχετε δύο αλγόριθμους $A_1$ και $A_2$ όπου ο αριθμός στοιχειωδών λειτουργιών τους είναι $T(A_1) = an \log_2 n$ και $T(A_2) = 2^a \sqrt{n}$ αντίστοιχα, τότε: - Ποιος είναι ο πραγματικός χρόνος εκτέλεσης των $A_1$ και $A_2$ για $n = 2^4$; - Για κάθε έναν από τους $A_1$ και $A_2$ ποια είναι η μέγιστη τιμή του $n$ για την οποία ο υπολογιστής θα δώσει αποτέλεσμα σε α − δευτερόλεπτα υπολογισμού;

Η παράμετρος α που αντιστοιχεί στο ΑΜ μου είναι []. Ο πραγματικός χρόνος εκτέλεσης του Αλγορίθμου 1 είναι [] δευτερόλεπτα. Ο πραγματικός χρόνος εκτέλεσης του Αλγορίθμου 2 είναι [] δευτερόλεπτα. Η μέγιστη τιμή του n για τον Α1 για την οποία ο υπολογιστής θα δώσει αποτέλεσμα σε λιγότερο από α - δευτερόλεπτα είναι []. Η μέγιστη τιμή του n για τον Α2 για την οποία ο υπολογιστής θα δώσει αποτέλεσμα σε λιγότερο από α - δευτερόλεπτα είναι [____].

Screenshot_2024-10-10_at_7.14.58_PM.png¶

Ερώτηση 2 / 4 (Συμπλήρωση Κενών (Χαλαρή Ταυτοποίηση) — 1.5 βαθμοί)

Ταξινόμηση ρυθμών αύξησης

Στην άσκηση που ακολουθεί, ο αριθμός "α" υπολογίζεται διαιρώντας τα τελευταία 2 ψηφία του ΑΜ σας με το 4 και προσθέτοντας στο υπόλοιπο τον αριθμό 1. $$a = ((AM \bmod 100) \bmod 4) + 1$$

Να ταξινομηθούν οι παρακάτω συναρτήσεις σε αύξουσα σειρά ως προς τον ρυθμό αύξησης. $f_1(n) = an \log n \quad f_4(n) = n(n + a)$ $f_2(n) = 6n^a \quad f_5(n) = a^n$ $f_3(n) = a^2 n \quad f_6(n) = \sqrt[a+1]{an}$

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

Η τιμή του α που αντιστοιχεί στο ΑΜ μου είναι [] Στα παρακάτω κενά εισάγετε έναν αριθμό από το 1 ως το 6. (π.χ. 4 για την συνάρτηση f4(n)) Δίνεται η αύξουσα διάταξη: [] < [] < [] < [] < [] < [____]

Screenshot_2024-10-10_at_7.24.09_PM.png¶

[Λείπει από τη φωτογραφία: επικεφαλίδα ερώτησης (αριθμός και τύπος)]

Να βρεθεί το κατώτερο άνω ασυμπτωτικό φράγμα για τις παρακάτω συναρτήσεις. $$f(n) = 5\log_a a^n + 3\sqrt{n}$$ $$g(n) = n(an + a^8)$$ $$h(n) = a \cdot \log n + 3n + 1$$ $$k(n) = 3\sqrt{n} + a \cdot (\log n + 1)$$ $$m(n) = n \cdot (\log n^a + 1)$$

[Λείπει από τη φωτογραφία: τυχόν συνέχεια της ερώτησης μετά τη συνάρτηση m(n), το στιγμιότυπο τελειώνει εκεί]

Screenshot_2024-10-10_at_7.30.54_PM.png¶

[Λείπει από τη φωτογραφία: επικεφαλίδα ερώτησης (αριθμός και τύπος)]

Πολυπλοκότητα απλών αλγορίθμων

Στην άσκηση που ακολουθεί, ο αριθμός "α" υπολογίζεται διαιρώντας τα τελευταία 2 ψηφία του ΑΜ σας με το 4 και προσθέτοντας στο υπόλοιπο τον αριθμό 1. $$a = ((AM \bmod 100) \bmod 4) + 1$$

Δίνεται το παρακάτω τμήμα κώδικα.

s1 = 0 ;
s2 = a ;
for i = 0 to n {
    for j = 1 to n {
        s1 = s1 + 1 ;
        s2 = s2 + a ;
    }
}
c = s1 + s2 ;

- Πόσες επαναλήψεις εκτελούνται στο παραπάνω τμήμα κώδικα; - Ποια είναι η ασυμπτωτική πολυπλοκότητα του αλγορίθμου; - Ας υποθέσουμε ότι n=6. Ποια θα είναι η τιμή του c μετά το πέρας της εκτέλεσης του κώδικα;

Η τιμή του α που αντιστοιχεί στο ΑΜ μου είναι [] Το πλήθος των επαναλήψεων που εκτελούνται στο παραπάνω τμήμα κώδικα είναι [] Η ασυμπτωτική πολυπλοκότητα του αλγορίθμου είναι [] c = []

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2024-10¶

Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.

Ερώτηση 1 (σύγκριση ρυθμών αύξησης)¶

Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή

Λύση 1: Ρυθμός $2^6=64$ πράξεις/δευτ. Για $n=2^4=16$: - $A_1$: $a\cdot16\cdot4=64a$ πράξεις ⇒ $a$ δευτερόλεπτα. - $A_2$: $2^a\cdot\sqrt{16}=4\cdot2^a$ πράξεις ⇒ $2^{a+2}/64=$ $2^{a-4}$ δευτ. (a=1: 1/8, a=2: 1/4, a=3: 1/2, a=4: 1).

Μέγιστο $n$ σε $a$ δευτερόλεπτα = $64a$ πράξεις: - $A_1$: $a\,n\log_2 n\le64a\iff n\log_2 n\le64$ ⇒ $n=16$ (ισότητα, ανεξάρτητο του $a$). Αν η εκφώνηση απαιτεί αυστηρά «λιγότερο από», $n=15$ ($15\log_2 15\approx58.6$). - $A_2$: $2^a\sqrt n\le64a\iff n\le(64a/2^a)^2$: a=1: 1024, a=2: 4096, a=3: 576, a=4: 256.

Λύση 3 (τρίτη γνώμη): Η παράμετρος είναι $a = ((AM \bmod 100) \bmod 4) + 1 \in \{1, 2, 3, 4\}$. Ο υπολογιστής εκτελεί $R = 2^6 = 64$ πράξεις ανά δευτερόλεπτο.

Πραγματικός χρόνος εκτέλεσης για $n = 2^4 = 16$:
Αλγόριθμος $A_1$: $T(A_1) = an \log_2 n = a \cdot 16 \cdot \log_2(16) = 16 \cdot 4 \cdot a = 64a$ πράξεις. Χρόνος: $t_1 = \frac{64a}{64} = \mathbf{a}$ δευτερόλεπτα (για $a=1$: 1 s, $a=2$: 2 s, $a=3$: 3 s, $a=4$: 4 s).
Αλγόριθμος $A_2$: $T(A_2) = 2^a \sqrt{n} = 2^a \sqrt{16} = 4 \cdot 2^a = 2^{a+2}$ πράξεις. Χρόνος: $t_2 = \frac{2^{a+2}}{2^6} = 2^{a-4}$ δευτερόλεπτα.
- $a=1$: $2^{-3} = 0.125\text{ s}$ ($1/8\text{ s}$)
- $a=2$: $2^{-2} = 0.25\text{ s}$ ($1/4\text{ s}$)
- $a=3$: $2^{-1} = 0.5\text{ s}$ ($1/2\text{ s}$)
- $a=4$: $2^0 = 1\text{ s}$
Μέγιστη τιμή του $n$ για εκτέλεση σε $\le a$ δευτερόλεπτα ($64a$ πράξεις):
Για τον $A_1$: $an \log_2 n \le 64a \iff n \log_2 n \le 64$. Για $n = 16$: $16 \log_2 16 = 16 \cdot 4 = 64 \le 64$. Άρα $n = \mathbf{16}$ (ανεξάρτητα από το $a$). Αν η έκφραση «λιγότερο από $a$» εκληφθεί ως αυστηρή ανισότητα $< 64a$, τότε $n = 15$ (αφού $15 \log_2 15 \approx 58.6$).
Για τον $A_2$: $2^a \sqrt{n} \le 64a \iff \sqrt{n} \le \frac{64a}{2^a} \iff n \le \left(\frac{64a}{2^a}\right)^2 = a^2 \cdot 2^{12-2a}$.
- $a=1$: $\sqrt{n} \le 32 \implies n = 32^2 = \mathbf{1024}$.
- $a=2$: $\sqrt{n} \le \frac{128}{4} = 32 \implies n = 32^2 = \mathbf{1024}$.
- $a=3$: $\sqrt{n} \le \frac{192}{8} = 24 \implies n = 24^2 = \mathbf{576}$.
- $a=4$: $\sqrt{n} \le \frac{256}{16} = 16 \implies n = 16^2 = \mathbf{256}$.

Η λύση Α υπέπεσε σε αριθμητικό σφάλμα στον υπολογισμό του $n$ για $a=2$ δίνοντας 4096 αντί του ορθού 1024, ενώ η λύση Β έκανε σωστά όλους τους υπολογισμούς.

Ερώτηση 2 (ταξινόμηση ρυθμών αύξησης)¶

Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή

Λύση 1: Ρυθμοί: $f_1=\Theta(n\log n)$, $f_2=\Theta(n^a)$, $f_3=\Theta(n)$, $f_4=\Theta(n^2)$, $f_5=a^n$, $f_6=\Theta(n^{1/(a+1)})$. - a=1: $f_5$ (σταθερά 1) < $f_6$ < $f_2\sim f_3$ ($\Theta(n)$) < $f_1$ < $f_4$ ⇒ 5 < 6 < 2, 3 < 1 < 4. - a=2: 6 < 3 < 1 < 2 ~ 4 < 5 ($f_2,f_4=\Theta(n^2)$). - a=3: 6 < 3 < 1 < 4 < 2 < 5. - a=4: 6 < 3 < 1 < 4 < 2 < 5.

Λύση 3 (τρίτη γνώμη): Οι συναρτήσεις και οι ρυθμοί αύξησής τους είναι: - $f_1(n) = an \log n = \Theta(n \log n)$ - $f_2(n) = 6n^a = \Theta(n^a)$ - $f_3(n) = a^2 n = \Theta(n)$ - $f_4(n) = n(n+a) = n^2 + an = \Theta(n^2)$ - $f_5(n) = a^n$ - $f_6(n) = \sqrt[a+1]{an} = \Theta(n^{\frac{1}{a+1}})$

Επειδή $a \ge 1$, $\frac{1}{a+1} \le \frac{1}{2} < 1$, άρα η $f_6$ είναι πάντοτε υπογραμμική και επομένως αυστηρά βραδύτερη από τη γραμμική $f_3(n)$. Η $f_3(n) = \Theta(n)$ είναι αυστηρά βραδύτερη από την $f_1(n) = \Theta(n \log n)$.

Για $a \in \{2, 3, 4\}$:
$f_5(n) = a^n$ είναι εκθετική ($2^n, 3^n, 4^n$), άρα ταχύτερη όλων των πολυωνυμικών.
Για $a=2$: $f_4(n) = n^2 + 2n$ και $f_2(n) = 6n^2$. Για κάθε $n \ge 1$ ισχύει $n^2 + 2n < 6n^2 \iff 2n < 5n^2$, άρα $f_4(n) < f_2(n)$.
Για $a=3, 4$: $f_4(n) = \Theta(n^2) < f_2(n) = \Theta(n^a)$ ($n^3$ ή $n^4$). Συνεπώς, για $a \in \{2, 3, 4\}$ η σειρά είναι μονοσήμαντη: $$f_6 < f_3 < f_1 < f_4 < f_2 < f_5$$ Στα κενά: [6] < [3] < [1] < [4] < [2] < [5].
Για $a = 1$: $f_5(n) = 1^n = 1 = \Theta(1)$ (σταθερή), $f_6(n) = \sqrt{n}$, $f_3(n) = n < f_2(n) = 6n$, $f_1(n) = n \log n$, $f_4(n) = n^2 + n$. Στα κενά: [5] < [6] < [3] < [2] < [1] < [4].

Η λύση Α άφησε ακαθόριστη τη σύγκριση μεταξύ $f_2$ και $f_4$ για $a=2$ γράφοντας $f_2 \sim f_4$, ενώ η λύση Β προσδιόρισε ορθά τη διάταξη $f_4 < f_2$ συμπληρώνοντας συγκεκριμένα τα κενά.

Ερώτηση (χωρίς αριθμό) — κατώτερο άνω ασυμπτωτικό φράγμα¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν

$f(n)=5\log_a a^n+3\sqrt n=5n+3\sqrt n$ ⇒ $O(n)$.
$g(n)=an^2+a^8n$ ⇒ $O(n^2)$.
$h(n)=a\log n+3n+1$ ⇒ $O(n)$.
$k(n)=3\sqrt n+a(\log n+1)$ ⇒ $O(\sqrt n)$.
$m(n)=n(a\log n+1)$ ⇒ $O(n\log n)$.

Ερώτηση (χωρίς αριθμό) — πολυπλοκότητα απλού αλγορίθμου¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν

Ο εξωτερικός βρόχος εκτελείται $n+1$ φορές ($i=0..n$), ο εσωτερικός $n$ φορές ($j=1..n$). - Επαναλήψεις του εσωτερικού σώματος: $n(n+1)=n^2+n$. - Ασυμπτωτική πολυπλοκότητα: $\Theta(n^2)$. - Για $n=6$: $s_1=42$, $s_2=a+42a$, άρα $c=42+43a$: a=1: 85, a=2: 128, a=3: 171, a=4: 214.

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή