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

Εισαγωγή στους Αλγόριθμους — Νοέμβριος 2024 — ηλεκτρονική εξέταση (απόσπασμα)

Μεταγραφή από τα στιγμιότυπα του κουίζ Νοεμβρίου 2024 (ερωτήσεις 3, 6 και μία ακόμη).

PXL_20241121_190521227.jpg

Ερώτηση 3 / 10 (Επιλογή από προκαθορισμένες απαντήσεις — 1 βαθμός)

Τοπολογική Διάταξη - ΙΙΙ Να εξετάσετε εάν το παρακάτω γράφημα έχει ή όχι τοπολογική διάταξη.

[Σχήμα: Κατευθυνόμενο γράφημα με κορυφές a, b, c, d, e, f, g, h, i, j, k, l, m, n και κατευθυνόμενες ακμές]

--- Επιλογή ---

[Λείπει από τη φωτογραφία: οι επιλογές του αναπτυσσόμενου μενού]

PXL_20241121_191428575.jpg

[Λείπει από τη φωτογραφία: η αρχή της λέξης «Ερώτηση» και του τίτλου «Ισχυρά» (ορατά: «ώτηση 6 / 10», «υρά συνεκτικές συνιστώσες - Ι»)]

Ερώτηση 6 / 10 (Επιλογή από προκαθορισμένες απαντήσεις — 2 βαθμοί)

Ισχυρά συνεκτικές συνιστώσες - Ι Βρείτε τις ισχυρά συνεκτικές συνιστώσες του παρακάτω γραφήματος.

[Σχήμα: Κατευθυνόμενο γράφημα με κορυφές a, b, c, d, e, f, g, h, i, j, k, m, n και κατευθυνόμενες ακμές]

[Λείπει από τη φωτογραφία: η ετικέτα «α)» στην αρχή της πρώτης υποερώτησης] Πόσες είναι οι ισχυρά συνεκτικές συνιστώσες ; --- Επιλογή --- β) Πόσες κορυφές έχει η μεγαλύτερη ισχυρά συνεκτική συνιστώσα ; --- Επιλογή ---

Notes_241123_120410_fe4.jpg

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

[Λείπει από τη φωτογραφία: ... ο χρόνος ανακάλυψης ή/και ο χρόνος εγκατάλειψης ... (ορατό: «ο χρόνος ανακάλυψης ή/και ο χρόνος εγκατάλειψης και έχει αντικατασταθεί με κάποιο γράμμα. Σε ορισμένους κόμβους έχει»)]

[Λείπει από τη φωτογραφία: τμήμα της πρότασης (ορατό: «...χίστε τους χρόνους ανακάλυψης/εγκατάλειψης που λείπουν από το παρακάτω σχήμα με το κατάλληλο γράμμα έτσι ώστε η εκτέλεση του ...μου να είναι σωστή.»)]

[Λείπει από τη φωτογραφία: τμήμα του παραδείγματος (ορατό: «Παράδειγμα: Στον κόμβο a, ο χρόνος ανακάλυψης είναι 1, ενώ ο χρόνος εγκατάλειψης έχει αντικατασταθεί με το γράμμα Δ. Επομένως, πρέπει να ... χίσετε το γράμμα Δ με κάποιον αριθμό από την δοθείσα λίστα.»)]

[Σχήμα: Κατευθυνόμενο γράφημα με κόμβους και χρόνους ανακάλυψης/εγκατάλειψης: d: A / B, b: 2 / Γ, a: 1 / Δ, c: E / Z, i: H / Θ, k: 21 / I, l: K / 23, f: Λ / 8, e: 6 / M, h: 13 / N, j: Ξ / Π, m: P / Σ, n: T / Y, g: Φ / 10]

--- Επιλογή --- , B = --- Επιλογή --- , Γ = --- Επιλογή --- , Δ = --- Επιλογή --- , E = --- Επιλογή --- , Z = --- Επιλογή --- H = --- Επιλογή --- , Θ = --- Επιλογή --- , I = --- Επιλογή --- , K = --- Επιλογή --- , Λ = --- Επιλογή --- M = --- Επιλογή --- , N = --- Επιλογή --- , Ξ = --- Επιλογή --- , Π = --- Επιλογή --- , P = --- Επιλογή --- , Σ = --- Επιλογή --- T = --- Επιλογή --- , Y = --- Επιλογή --- , Φ = --- Επιλογή ---

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

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

Προσοχή

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

AI λύσεις — 2024-11

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

Ερώτηση 3

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Στην εικόνα PXL_20241121_190521227.jpg, το κατευθυνόμενο γράφημα αποτελείται από 14 κορυφές \(\{a, b, c, d, e, f, g, h, i, j, k, l, m, n\}\) και τις ακόλουθες κατευθυνόμενες ακμές: - \((a, e), (a, l), (a, f)\) - \((b, c), (b, e), (b, i)\) - \((d, c), (d, g), (d, n)\) - \((c, f), (c, j), (c, g)\) - \((g, f)\) - \((e, h)\) - \((f, i), (f, m)\) - \((i, h)\) - \((m, j)\) - \((j, l), (j, k)\) - \((k, n)\)

Ένα κατευθυνόμενο γράφημα έχει τοπολογική διάταξη (topological sort) αν και μόνο αν είναι Κατευθυνόμενο Ακυκλικό Γράφημα (DAG), δηλαδή δεν περιέχει κανέναν κατευθυνόμενο κύκλο. Εξετάζοντας τις ακμές ανά ιεραρχικά επίπεδα (topological levels): - Επίπεδο 0 (μηδενικός βαθμός εισόδου / πηγές): \(\{a, b, d\}\) - Επίπεδο 1: \(c\) (από \(b, d\)), \(e\) (από \(a, b\)) - Επίπεδο 2: \(g\) (από \(d, c\)) - Επίπεδο 3: \(f\) (από \(a, c, g\)) - Επίπεδο 4: \(i\) (από \(b, f\)), \(m\) (από \(f\)) - Επίπεδο 5: \(j\) (από \(c, m\)) - Επίπεδο 6: \(h\) (από \(e, i\)), \(l\) (από \(a, j\)), \(k\) (από \(j\)) - Επίπεδο 7: \(n\) (από \(d, k\))

Όλες οι κατευθυνόμενες ακμές πηγαίνουν αποκλειστικά από κορυφές χαμηλότερου επιπέδου σε κορυφές υψηλότερου επιπέδου. Δεν υπάρχει καμία οπισθοδρομική ακμή, συνεπώς το γράφημα είναι DAG.

Απάντηση: Ναι (το γράφημα έχει τοπολογική διάταξη, π.χ. \(a, b, d, e, c, g, f, i, m, h, j, l, k, n\)).

Ερώτηση 6

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Στην εικόνα PXL_20241121_191428575.jpg, το κατευθυνόμενο γράφημα έχει 13 κορυφές \(\{a, b, c, d, e, f, g, h, i, j, k, m, n\}\) με τις εξής κατευθυνόμενες ακμές: - \((a, e), (e, b), (b, a)\) - \((b, c), (b, f)\) - \((c, d), (c, f)\) - \((d, j)\) - \((j, c), (j, m)\) - \((f, g), (f, h), (f, i)\) - \((g, d), (g, i)\) - \((h, i)\) - \((i, m), (m, i)\) - \((n, d), (n, k)\) - \((k, n), (k, j)\)

Οι Ισχυρά Συνεκτικές Συνιστώσες (Strongly Connected Components - SCC) είναι: 1. \(\mathbf{\{a, b, e\}}\) (3 κορυφές): σχηματίζουν τον κύκλο \(a \to e \to b \to a\). 2. \(\mathbf{\{k, n\}}\) (2 κορυφές): σχηματίζουν τον αμφίδρομο κύκλο \(k \leftrightarrow n\). 3. \(\mathbf{\{c, d, f, g, j\}}\) (5 κορυφές): είναι αμοιβαία προσβάσιμες μέσω των κύκλων \(c \to d \to j \to c\) και \(c \to f \to g \to d \to j \to c\). 4. \(\mathbf{\{h\}}\) (1 κορυφή): προσεγγίζεται από το \(f\) και οδηγεί στο \(i\), χωρίς επιστροφή. 5. \(\mathbf{\{i, m\}}\) (2 κορυφές): σχηματίζουν τον αμφίδρομο κύκλο \(i \leftrightarrow m\), χωρίς ακμές εξόδου προς άλλες συνιστώσες.

Απαντήσεις: - α) Πόσες είναι οι ισχυρά συνεκτικές συνιστώσες; 5 - β) Πόσες κορυφές έχει η μεγαλύτερη ισχυρά συνεκτική συνιστώσα; 5 (η συνιστώσα \(\{c, d, f, g, j\}\))

Ερώτηση χωρίς αριθμό (χρόνοι ανακάλυψης/εγκατάλειψης)

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Στην εικόνα Notes_241123_120410_fe4.jpg, εκτελείται ο αλγόριθμος Αναζήτησης κατά Βάθος (DFS) στο κατευθυνόμενο γράφημα των 14 κορυφών. Οι χρόνοι ανακάλυψης \(d[u]\) και εγκατάλειψης \(f[u]\) κυμαίνονται από 1 έως 28 (\(2 \times 14\)).

Βήματα εκτέλεσης DFS:

  1. Δένδρο με ρίζα το \(a\):
  2. \(d[a] = 1\)
  3. Επίσκεψη στο \(b\): \(d[b] = 2\)
  4. Από \(b\) επίσκεψη στο \(d\): \(d[d] = 3 \implies \mathbf{A = 3}\)
  5. Στο \(d\): η ακμή \((d, a)\) είναι οπίσθια ακμή (back edge). Τέλος \(d\): \(f[d] = 4 \implies \mathbf{B = 4}\)
  6. Επιστροφή στο \(b\): τέλος \(b\): \(f[b] = 5 \implies \mathbf{\Gamma = 5}\)
  7. Επιστροφή στο \(a\): επίσκεψη στο \(e\): \(d[e] = 6\)
    • Από \(e\) επίσκεψη στο \(f\): \(d[f] = 7 \implies \mathbf{\Lambda = 7}\)
    • Τέλος \(f\): \(f[f] = 8\) (δοσμένο)
    • Από \(e\) επίσκεψη στο \(g\): \(d[g] = 9 \implies \mathbf{\Phi = 9}\)
    • Τέλος \(g\): \(f[g] = 10\) (δοσμένο)
    • Η ακμή \((e, a)\) είναι οπίσθια και η \((e, b)\) διασταύρωσης. Τέλος \(e\): \(f[e] = 11 \implies \mathbf{M = 11}\)
  8. Επιστροφή στο \(a\): επίσκεψη στο \(c\): \(d[c] = 12 \implies \mathbf{E = 12}\)
    • Από \(c\) επίσκεψη στο \(h\): \(d[h] = 13\) (δοσμένο)
    • Από \(h\) (ακμή \((h, g)\) διασταύρωσης), επίσκεψη στο \(j\): \(d[j] = 14 \implies \mathbf{\Xi = 14}\)
    • Στο \(j\): η ακμή \((j, h)\) είναι οπίσθια ακμή. Τέλος \(j\): \(f[j] = 15 \implies \mathbf{\Pi = 15}\)
    • Επιστροφή στο \(h\): τέλος \(h\): \(f[h] = 16 \implies \mathbf{N = 16}\)
    • Επιστροφή στο \(c\): επίσκεψη στο \(i\): \(d[i] = 17 \implies \mathbf{H = 17}\)
    • Στο \(i\): ακμές προς \(h, j\) (διασταύρωσης) και προς \(a\) (οπίσθια). Τέλος \(i\): \(f[i] = 18 \implies \mathbf{\Theta = 18}\)
    • Επιστροφή στο \(c\): τέλος \(c\): \(f[c] = 19 \implies \mathbf{Z = 19}\)

  9. Επιστροφή στο \(a\): τέλος \(a\): \(f[a] = 20 \implies \mathbf{\Delta = 20}\)

  10. Δένδρο με ρίζα το \(k\):

  11. \(d[k] = 21\) (δοσμένο)
  12. Από \(k\) (ακμή \((k, j)\) διασταύρωσης), επίσκεψη στο \(l\): \(d[l] = 22 \implies \mathbf{K = 22}\)
  13. Τέλος \(l\): \(f[l] = 23\) (δοσμένο)
  14. Επιστροφή στο \(k\): επίσκεψη στο \(m\): \(d[m] = 24 \implies \mathbf{P = 24}\)
    • Από \(m\) (ακμή \((m, j)\) διασταύρωσης), επίσκεψη στο \(n\): \(d[n] = 25 \implies \mathbf{T = 25}\)
    • Στο \(n\): η ακμή \((n, l)\) είναι διασταύρωσης. Τέλος \(n\): \(f[n] = 26 \implies \mathbf{Y = 26}\)
    • Επιστροφή στο \(m\): τέλος \(m\): \(f[m] = 27 \implies \mathbf{\Sigma = 27}\)
  15. Επιστροφή στο \(k\): τέλος \(k\): \(f[k] = 28 \implies \mathbf{I = 28}\)

Συνολική αντιστοίχιση:

  • \(A = 3\)
  • \(B = 4\)
  • \(\Gamma = 5\)
  • \(\Delta = 20\)
  • \(E = 12\)
  • \(Z = 19\)
  • \(H = 17\)
  • \(\Theta = 18\)
  • \(I = 28\)
  • \(K = 22\)
  • \(\Lambda = 7\)
  • \(M = 11\)
  • \(N = 16\)
  • \(\Xi = 14\)
  • \(\Pi = 15\)
  • \(P = 24\)
  • \(\Sigma = 27\)
  • \(T = 25\)
  • \(Y = 26\)
  • \(\Phi = 9\)

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

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