Εισαγωγή στους Αλγόριθμους — Ιανουάριος 2025¶
Μεταγραφή από δύο στιγμιότυπα της εξέτασης Ιανουαρίου 2025 (σελίδα 3/6 και Θέμα 6).
Screenshot_20250128_143121_Samsung_Notes.jpg¶
ΘΕΜΑ 3 (2 μονάδες). Μια ομάδα μηχανικών υπολογιστών εργάζεται για την επίλυση δύο υπολογιστικών προβλημάτων \(\Pi_1\) και \(\Pi_2\), για καθένα από τα οποία έχει δημιουργήσει έναν αλγόριθμο «διαίρει και βασίλευε». Συγκεκριμένα: - Τον αλγόριθμο \(A_1\) που διασπά το αρχικό πρόβλημα μεγέθους \(n\) σε 9 υποπροβλήματα μεγέθους \(n/3\), τα επιλύει και στη συνέχεια συνθέτει τις λύσεις τους σε χρόνο \(6 \cdot n^2\). - Τον αλγόριθμο \(A_2\) που διασπά το αρχικό πρόβλημα μεγέθους \(n\) σε 125 υποπροβλήματα μεγέθους \(n/5\), τα επιλύει και στη συνέχεια συνθέτει τις λύσεις τους σε χρόνο \(25n^2 \cdot \log^2 n\). (α) [1.4] Να διατυπώσετε τις αναδρομικές εξισώσεις που δίνουν τον χρόνο εκτέλεσης των αλγορίθμων \(A_1\) και \(A_2\), και στη συνέχεια με εφαρμογή του Βασικού Θεωρήματος των αναδρομών να βρείτε τον κλειστό τύπο κάθε αναδρομής σε ασυμπτωτικό συμβολισμό εξηγώντας αναλυτικά την εφαρμογή του. (β) [0.6] Χρησιμοποιώντας την απάντηση του (α) σαν πρόβλεψη, να αποδείξετε τον κλειστό τύπο του αλγορίθμου \(A_1\) με επαγωγή (μέθοδος αντικατάστασης ή σωστής πρόβλεψης) προσδιορίζοντας επακριβώς τις σταθερές. Ως αρχική συνθήκη, ισχύει ότι \(T(x) = 1, \forall x < 1\).
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
Screenshot_2025-01-26-17-15-10-39_572064f74bd5f9fa804b05334aa4f912.jpg¶
ΘΕΜΑ 6 (1.5 μονάδες). (i) Στο κατευθυνόμενο γράφημα του παρακάτω σχήματος να δώσετε τους χρόνους ανακάλυψης (πρώτης επίσκεψης) και εγκατάλειψης σε μία Αναζήτηση Πρώτα κατά Βάθος (ΑΠΒ), η οποία αρχίζει από την κορυφή a. Κατά την εκτέλεση της ΑΠΒ σε κάθε κορυφή, οι εξερχόμενες ακμές θα πρέπει να εξετάζονται με λεξικογραφική σειρά. Για παράδειγμα, αν μια κορυφή x έχει τις εξερχόμενες ακμές {(x,y), (x,s), (x,t), (x,p)}, τότε η ΑΠΒ θα τις εξετάσει με τη σειρά (x,p), (x,s), (x,t), (x,y). Οι χρόνοι ανακάλυψης και εγκατάλειψης να γραφούν πάνω στο σχήμα, στο εσωτερικό κάθε κορυφής, αριστερά ο χρόνος ανακάλυψης και δεξιά ο χρόνος εγκατάλειψης. (ii) Να κατηγοριοποιήσετε τις ακμές του κατευθυνόμενου γραφήματος σύμφωνα με την ΑΠΒ του ερωτήματος (i). Η κατηγοριοποίηση να γραφεί δίπλα σε κάθε ακμή του σχήματος χρησιμοποιώντας τα γράμματα "Δ" (ακμή δένδρου), "Π" (πίσω ακμή), "Ε" (εμπρός ακμή) και "Σ" (διασυνδετική ακμή).
Απάντηση:
[Σχήμα: Κατευθυνόμενο γράφημα με κορυφές a, d, g, f, h, e, i, c, j, b. Κάθε κορυφή περιέχει μια διαγώνιο slash '/' για την αναγραφή των χρόνων ανακάλυψης/εγκατάλειψης. Κατευθυνόμενες ακμές συνδέουν τις κορυφές.]
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2025-01¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 3¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
(α) Α₁: \(T(n)=9T(n/3)+6n^2\). Εδώ \(a=9,\ b=3\), \(n^{\log_3 9}=n^2\) και \(f(n)=6n^2=\Theta(n^2)\), άρα περίπτωση 2 του Βασικού Θεωρήματος: \(T(n)=\Theta(n^2\log n)\).
Α₂: \(T(n)=125T(n/5)+25n^2\log^2 n\). Εδώ \(n^{\log_5 125}=n^3\). Η \(f(n)=25n^2\log^2 n=O(n^{3-\varepsilon})\) (π.χ. \(\varepsilon=1/2\), γιατί \(\log^2 n=O(n^{1/2})\)), άρα περίπτωση 1: \(T(n)=\Theta(n^3)\).
(β) Θεωρούμε \(T(n)=9T(n/3)+6n^2\) για \(n\ge1\) και \(T(x)=1\) για \(x<1\). Ισχυρισμός: \(6n^2\log_3 n\le T(n)\le 6n^2\log_3 n+15n^2\) για \(n\ge1\) (άρα \(\Theta(n^2\log n)\)).
Βάση (\(1\le n<3\)): \(T(n)=9\cdot1+6n^2\). Άνω: \(9+6n^2\le15n^2\) διότι \(n^2\ge1\) και \(\log_3 n\ge0\). Κάτω: \(9+6n^2\ge6n^2\log_3 n\) διότι \(\log_3 n<1\).
Επαγωγικό βήμα (\(n\ge3\), ισχύει για \(n/3\ge1\)): \(T(n)\le9\left[6\tfrac{n^2}{9}(\log_3 n-1)+15\tfrac{n^2}{9}\right]+6n^2=6n^2\log_3 n-6n^2+15n^2+6n^2=6n^2\log_3 n+15n^2\). \(T(n)\ge9\cdot6\tfrac{n^2}{9}(\log_3 n-1)+6n^2=6n^2\log_3 n\).
Άρα οι σταθερές είναι \(c=6\), \(d=15\): \(T(n)=\Theta(n^2\log n)\).
Θέμα 6¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Στην πρωτότυπη εικόνα Screenshot_2025-01-26-17-15-10-39_572064f74bd5f9fa804b05334aa4f912.jpg απεικονίζεται το κατευθυνόμενο γράφημα των 10 κορυφών (\(a, b, c, d, e, f, g, h, i, j\)). Η διάταξη των κορυφών και των κατευθυνόμενων ακμών είναι πανομοιότυπη με εκείνη της εξεταστικής Ιουνίου 2024.
Οι εξερχόμενες ακμές κάθε κορυφής σε λεξικογραφική σειρά είναι: - \(a: (a, f), (a, g)\) - \(b: \emptyset\) (καμία εξερχόμενη) - \(c: (c, b), (c, e), (c, h), (c, j)\) - \(d: (d, a)\) - \(e: (e, h)\) - \(f: (f, d), (f, e)\) - \(g: (g, e), (g, f)\) - \(h: (h, e), (h, g)\) - \(i: (i, c), (i, h)\) - \(j: (j, b), (j, i)\)
(i) Χρόνοι Ανακάλυψης \(d[u]\) και Εγκατάλειψης \(f[u]\) στην ΑΠΒ¶
Η Αναζήτηση Πρώτα κατά Βάθος (ΑΠΒ) ξεκινά από την κορυφή \(a\), εξετάζοντας τις εξερχόμενες ακμές με λεξικογραφική σειρά:
- Επίσκεψη \(a\): \(d[a] = 1\). Εξερχόμενες: \((a, f), (a, g)\). Πρώτη είναι η \((a, f)\).
- Επίσκεψη \(f\): \(d[f] = 2\). Εξερχόμενες: \((f, d), (f, e)\). Πρώτη είναι η \((f, d)\).
- Επίσκεψη \(d\): \(d[d] = 3\). Εξερχόμενη: \((d, a)\). Το \(a\) είναι γκρίζο (ενεργό στο μονοπάτι), οπότε δεν επανεπισκέπτεται. Ολοκλήρωση \(d \implies f[d] = 4\).
- Επιστροφή στο \(f\): Επόμενη εξερχόμενη ακμή η \((f, e)\).
- Επίσκεψη \(e\): \(d[e] = 5\). Εξερχόμενη: \((e, h)\).
- Επίσκεψη \(h\): \(d[h] = 6\). Εξερχόμενες: \((h, e), (h, g)\). Το \(e\) είναι γκρίζο. Επόμενη είναι η \((h, g)\).
- Επίσκεψη \(g\): \(d[g] = 7\). Εξερχόμενες: \((g, e), (g, f)\). Τόσο το \(e\) όσο και το \(f\) είναι γκρίζα (ενεργά). Ολοκλήρωση \(g \implies f[g] = 8\).
- Επιστροφή στο \(h\): Ολοκλήρωση \(h \implies f[h] = 9\).
- Επιστροφή στο \(e\): Ολοκλήρωση \(e \implies f[e] = 10\).
- Επιστροφή στο \(f\): Ολοκλήρωση \(f \implies f[f] = 11\).
- Επιστροφή στο \(a\): Επόμενη εξερχόμενη ακμή η \((a, g)\) (το \(g\) είναι μαύρο/ολοκληρωμένο). Ολοκλήρωση \(a \implies f[a] = 12\).
Συνέχιση της ΑΠΒ για τις μη επισκεφθείσες κορυφές κατά αλφαβητική σειρά: 12. Κορυφή \(b\): \(d[b] = 13\). Δεν έχει εξερχόμενες ακμές \(\implies f[b] = 14\). 13. Κορυφή \(c\): \(d[c] = 15\). Εξερχόμενες: \((c, b)\) (μαύρο), \((c, e)\) (μαύρο), \((c, h)\) (μαύρο), \((c, j)\) (λευκό). 14. Επίσκεψη \(j\): \(d[j] = 16\). Εξερχόμενες: \((j, b)\) (μαύρο), \((j, i)\) (λευκό). 15. Επίσκεψη \(i\): \(d[i] = 17\). Εξερχόμενες: \((i, c)\) (\(c\) γκρίζο), \((i, h)\) (μαύρο). Ολοκλήρωση \(i \implies f[i] = 18\). 16. Επιστροφή στο \(j\): Ολοκλήρωση \(j \implies f[j] = 19\). 17. Επιστροφή στο \(c\): Ολοκλήρωση \(c \implies f[c] = 20\).
Πίνακας Χρόνων Ανακάλυψης και Εγκατάλειψης (\(d / f\)):¶
- \(a\): \(1 / 12\)
- \(b\): \(13 / 14\)
- \(c\): \(15 / 20\)
- \(d\): \(3 / 4\)
- \(e\): \(5 / 10\)
- \(f\): \(2 / 11\)
- \(g\): \(7 / 8\)
- \(h\): \(6 / 9\)
- \(i\): \(17 / 18\)
- \(j\): \(16 / 19\)
(ii) Κατηγοριοποίηση των Ακμών του Γραφήματος¶
Σύμφωνα με τους κανόνες ταξινόμησης της ΑΠΒ: - Ακμές Δένδρου («Δ»): - \((a, f)\) - \((f, d)\) - \((f, e)\) - \((e, h)\) - \((h, g)\) - \((c, j)\) - \((j, i)\) - Πίσω Ακμές («Π» — προς ενεργό πρόγονο / γκρίζο κόμβο): - \((d, a)\) - \((h, e)\) - \((g, e)\) - \((g, f)\) - \((i, c)\) - Εμπρός Ακμές («Ε» — προς απόγονο στο δένδρο ΑΠΒ / μαύρο κόμβο με \(d[u] < d[v]\)): - \((a, g)\) - Διασυνδετικές Ακμές («Σ» — cross edges / προς μαύρο κόμβο με \(d[u] > d[v]\)): - \((c, b)\) - \((c, e)\) - \((c, h)\) - \((j, b)\) - \((i, h)\)