Εισαγωγή στους Αλγόριθμους — Σεπτέμβριος 2021¶

Μεταγραφή από το αρχείο Themata_Sept21-Algo.pdf (10 σελίδες).

Themata_Sept21-Algo.pdf¶

Θέμα 1¶

1.Α-ΑΠΒ¶

Θεωρήστε το κατευθυνόμενο γράφημα G του παρακάτω σχήματος στο οποίο εκτελείται είτε μια Αναζήτηση Πρώτα κατά Βάθος (ΑΠΒ), είτε μια Αναζήτηση Πρώτα κατά Πλάτος (ΑΠΠ), καθεμία από τις οποίες αρχίζουν από την κορυφή m. Θεωρήστε επίσης ότι όταν στην ΑΠΒ ή στην ΑΠΠ πρέπει σε κάποιο βήμα να γίνει μια επιλογή κορυφής, τότε ο αλγόριθμος επιλέγει την λεξικογραφικά (αλφαβητικά) μικρότερη κορυφή.

[Σχήμα: Κατευθυνόμενο γράφημα με κορυφές m, n, p, s, t, w, r και ακμές (m,n), (m,p), (n,p), (p,r), (p,s), (p,t), (r,s), (r,w), (s,t), (t,w).]

(α) Κατηγοριοποιήστε τις ακμές του G σε μια ΑΠΒ που αρχίζει από την κορυφή m, επιλέγοντας μεταξύ των τιμών "Δ" (ακμή δένδρου), "Π" (πίσω ακμή), "Ε" (εμπρός ακμή) και "Σ" (διασυνδετική ακμή).

Στήλη Α	Κάντε την αντιστοιχία	Στήλη Β
1. Ακμή (m,n)	[Επιλογή]	Α. Δ - Δενδρική ακμή
2. Ακμή (m,p)	[Επιλογή]	Β. Π - Πίσω ακμή
3. Ακμή (n,p)	[Επιλογή]	C. Ε - Εμπρός ακμή
4. Ακμή (p,r)	[Επιλογή]	D. Σ - Διασυνδετική ακμή
5. Ακμή (p,s)	[Επιλογή]
6. Ακμή (p,t)	[Επιλογή]
7. Ακμή (r,s)	[Επιλογή]
8. Ακμή (r,w)	[Επιλογή]
9. Ακμή (s,t)	[Επιλογή]
10. Ακμή (t,w)	[Επιλογή]

1.Β-ΑΠΠ¶

(β) Κατηγοριοποιήστε τις ακμές του G σε μια ΑΠΠ που αρχίζει από την κορυφή m, επιλέγοντας μεταξύ των τιμών "Δ" (ακμή δένδρου) και "Μ" (μη δενδρική ακμή).

[Σχήμα: Κατευθυνόμενο γράφημα με κορυφές m, n, p, s, t, w, r και ακμές (m,n), (m,p), (n,p), (p,r), (p,s), (p,t), (r,s), (r,w), (s,t), (t,w).]

Στήλη Α	Κάντε την αντιστοιχία	Στήλη Β
1. Ακμή (m,n)	[Επιλογή]	Α. Δ - Δενδρική ακμή
2. Ακμή (m,p)	[Επιλογή]	Β. Μ - Μη δενδρική ακμή
3. Ακμή (n,p)	[Επιλογή]
4. Ακμή (p,r)	[Επιλογή]
5. Ακμή (p,s)	[Επιλογή]
6. Ακμή (p,t)	[Επιλογή]
7. Ακμή (r,s)	[Επιλογή]
8. Ακμή (r,w)	[Επιλογή]
9. Ακμή (s,t)	[Επιλογή]
10. Ακμή (t,w)	[Επιλογή]

Θέμα 2¶

Θεωρήστε το κατευθυνόμενο γράφημα του παρακάτω σχήματος με κόστη στις ακμές του.

[Σχήμα: Κατευθυνόμενο γράφημα με κορυφές s, b, f, e, t, a και βάρη ακμών: (s,b)=40, (s,f)=160, (s,e)=280, (s,t)=480, (s,a)=800, (b,f)=80, (b,a)=720, (f,e)=120, (f,a)=600, (e,t)=160, (e,a)=400, (t,a)=200.]

Στο παραπάνω κατευθυνόμενο γράφημα να βρείτε αποστάσεις (κόστη συντομότερων διαδρομών) από την κορυφή s προς όλες τις υπόλοιπες κορυφές εφαρμόζοντας τον αλγόριθμο του Dijkstra. Η απάντησή σας να δοθεί συμπληρώνοντας τον παρακάτω πίνακα, στον οποίο πρέπει να δώσετε: (α) τις κορυφές με την σειρά κατά την οποία οριστικοποιούνται («μονιμοποιούνται») από τον αλγόριθμο Dijkstra, (β) όλες τις προσωρινές πεπερασμένες τιμές του d(v) κάθε κορυφής v μέχρι την οριστικοποίησή τους, και (γ) την απόσταση (τελική τιμή) d(v) κάθε κορυφής v του κατευθυνόμενου γραφήματος από την s.

Προσοχή! Έστω κορυφή x με προσωρινές τιμές 10, 8 και τελική τιμή 8. Η απάντηση πρέπει να δοθεί στην εξής μορφή:

Κορυφή v	Προσωρινές τιμές	Τελική τιμή
x	10,8	8

Αν οι προσωρινές τιμές είναι παραπάνω απο μία, όπως στο παράδειγμα, πρέπει να δοθούν σε φθίνουσα σειρά, χωρισμένες με κόμμα και χωρίς κενά.

Θέμα 3¶

Θεωρήστε το μη κατευθυνόμενο γράφημα του παρακάτω σχήματος.

[Σχήμα: Μη κατευθυνόμενο γράφημα με κορυφές a, b, c, d, e, f, g, h, i, j και βάρη ακμών: (a,f)=460, (a,e)=420, (a,d)=720, (f,j)=440, (f,e)=780, (j,h)=760, (j,e)=740, (j,g)=800, (h,g)=620, (h,i)=600, (e,g)=680, (e,d)=520, (e,c)=540, (g,i)=640, (g,c)=340, (g,b)=360, (i,b)=660, (d,c)=560, (c,b)=320.]

(α) Να βρείτε το Ελάχιστο Γεννητικό Δένδρο (ΕΓΔ) του παραπάνω γραφήματος με την μέθοδο Prim θεωρώντας ως αρχική κορυφή την a. Το ΕΓΔ θα δοθεί σαν μια ακολουθία ακμών του γραφήματος με τη σειρά κατά την οποία προστίθενται οι ακμές στο ΕΓΔ, αντιστοιχίζοντας παρακάτω όσες ακμές ανήκουν στο ΕΓΔ με τη σωστή τους σειρά και τις υπόλοιπες με το ΔΑ (δεν ανήκουν).

Συγκεκριμένα, η 1η ακμή της ακολουθίας πρέπει να αντιστοιχηθεί με το Α (Θέση 1), η 2η ακμή της ακολουθίας με το Β (Θέση 2), κ.ο.κ ενώ οι ακμές που δεν ανήκουν στο ΕΓΔ πρέπει να αντιστοιχηθούν με το Τ (Δεν ανήκει στο ΕΓΔ).

Παράδειγμα: αν ίσχυε ΕΓΔ = {x, y}, {y, a}, {x, z} τότε η αντιστοίχιση θα γινόταν ως εξής: {x, y} -> Α (Θέση 1), {y, a} -> B (Θέση 2), {x, z} -> C (Θέση 3), και οι υπόλοιπες θα αντιστοιχίζονταν με το Τ (Δεν ανήκει στο ΕΓΔ).

[Οι λύσεις του Prim και του Kruskal (σελίδες 5–6 του PDF) δεν περιλαμβάνονται σε αυτό το αρχείο· θα μεταφερθούν στο 2021-09.solutions.md.]

Θέμα 4¶

Λύνουμε χρησιμοποιώντας τον τύπο:

Έστω $$a, b \in \mathbb{R}^+, b > 1, \gamma, \delta \in \mathbb{R}_0^+, g: \mathbb{R}^+ \to \mathbb{R}^+, g(n) = O(n^\gamma \log^\delta n),$$

\[T(n) = \begin{cases} g(1) &, n = 1 \\ a T(n/b) + g(n) &, n > 1 \end{cases}\]

Τότε,

\[T(n) = \begin{cases} O(n^{\log_b a} \log_b^\delta n) &, a > b^\gamma \\ O(n^\gamma \log_b^{\delta+1} n) &, a = b^\gamma \\ O(n^\gamma \log_b^\delta n) &, a < b^\gamma, \gamma > 0 \vee \delta \ge 1 \\ O(\log_b n) &, a < 1, \gamma = 0 \wedge \delta < 1 \end{cases}\]

για $n = b^k$

4.α.i¶

Ερώτηση 1 / 4 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.30 βαθμοί)

(α) Ένα πρόβλημα Π1 επιλύεται από έναν αλγόριθμο Α1 «διαίρει και βασίλευε», ο οποίος διασπά το αρχικό πρόβλημα μεγέθους n σε 216 υποπροβλήματα μεγέθους n/6, τα επιλύει και στη συνέχεια συνθέτει τις λύσεις τους σε χρόνο $2n^2 \cdot \log^5 n$.

(i) Ποια από τις παρακάτω αποτελεί την αναδρομική σχέση η οποία περιγράφει τη χρονική πολυπλοκότητα του αλγορίθμου $A_1$;

[ ] $T(n) = 216\ T(n/6) + n^2 \cdot \log^5 n$
[ ] $T(n) = 216\ T(n/6) + 2n^2 \cdot \log^4 n$
[ ] $T(n) = 6\ T(n/216) + 2n^2 \cdot \log^5 n$
[ ] $T(n) = 216\ T(n/6) + 2n^2 \cdot \log^5 n$

4.α.ii¶

(ii) Ποια από τις παρακάτω είναι η ασυμπτωτική χρονική πολυπλοκότητα (σε κλειστό τύπο) του αλγορίθμου $A_1$;

[ ] $O(n^3 \log^5 n)$
[ ] $O(n^3 \log^4 n)$
[ ] $O(n^3 \log^2 n)$
[ ] $O(n^3)$
[ ] καμία από τις προηγούμενες

4.β.i¶

(β) Ένα πρόβλημα Π2 επιλύεται από έναν αλγόριθμο Α2 «διαίρει και βασίλευε», ο οποίος διασπά το αρχικό πρόβλημα μεγέθους n σε 37 υποπροβλήματα μεγέθους n/37, τα επιλύει και στη συνέχεια συνθέτει τις λύσεις τους σε χρόνο $37 \cdot n^3 \cdot \log^7 n$.

(i) Ποια από τις παρακάτω αποτελεί την αναδρομική σχέση η οποία περιγράφει τη χρονική πολυπλοκότητα του αλγορίθμου $A_2$;

[ ] $T(n) = 37\ T(n/37) + 37 \cdot n^3 \cdot \log^7 n$
[ ] $T(n) = 37\ T(n/37) + 37 \cdot n^3$
[ ] $T(n) = 37\ T(n/37) + 37 \cdot n^3 \cdot \log^3 n$
[ ] $T(n) = 37\ T(n/37) + n^3 \cdot \log^7 n$

4.β.ii¶

(ii) Ποια από τις παρακάτω είναι η ασυμπτωτική χρονική πολυπλοκότητα (σε κλειστό τύπο) του αλγορίθμου $A_2$;

[ ] $O(n^7 \log n)$
[ ] $O(n^3 \log n)$
[ ] $O(n^3 \log^7 n)$
[ ] $O(n^3 \log^5 n)$
[ ] καμία από τις προηγούμενες

Θέμα 5¶

5.1¶

Η σιδηροδρομική εταιρεία μιας χώρας ολοκλήρωσε την κατασκευή μιας σιδηροδρομικής γραμμής και βρίσκεται τώρα στη φάση τοποθέτησης ενισχυτών ισχύος ρεύματος κατά μήκος της, έτσι ώστε οι συρμοί να έχουν την απαραίτητη ηλεκτρική ενέργεια για την κίνησή τους. Οι ενισχυτές μπορούν να τοποθετηθούν σε n συγκεκριμένες θέσεις si ($1 \le i \le n$) κατά μήκος της σιδηροδρομικής γραμμής. Κάθε ενισχυτής έχει συγκεκριμένη ένταση ενίσχυσης ισχύος ei, η οποία εξαρτάται από τη θέση στην οποία τοποθετείται. Σύμφωνα με τον κανονισμό ασφαλούς λειτουργίας, δύο ενισχυτές δεν πρέπει να τοποθετηθούν σε διαδοχικές (γειτονικές) θέσεις κατά μήκος της σιδηροδρομικής γραμμής. Στόχος λοιπόν της εταιρείας είναι η τοποθέτηση ενισχυτών σε ένα υποσύνολο των δυνατών θέσεων, έτσι ώστε να μεγιστοποιείται η συνολική ένταση ενίσχυσης ισχύος. Για παράδειγμα, θεωρήστε μια σιδηροδρομική γραμμή με n=10 θέσεις {s1, s2, s3, s4, s5, s6, s7, s8, s9, s10} και αντίστοιχες εντάσεις ενίσχυσης {e1, e2, e3, e4, e5, e6, e7, e8, e9, e10} = {50, 40, 60, 80, 70, 170, 200, 190, 90, 100}, η οποία απεικονίζεται στο παρακάτω σχήμα.

[Σχήμα: Σιδηροδρομική γραμμή με θέσεις $s_1$ έως $s_{10}$ και εντάσεις ενίσχυσης 50, 40, 60, 80, 70, 170, 200, 190, 90, 100.]

Τα υποσύνολα θέσεων $\{s_1, s_3, s_5, s_7, s_9\}$ και $\{s_1, s_4, s_7, s_{10}\}$ με συνολική ένταση ενίσχυσης 470 και 430, αντίστοιχα, αποτελούν εφικτές λύσεις (δηλαδή λύσεις που ικανοποιούν τις προϋποθέσεις τοποθέτησης).

(α) Θεωρήστε τον εξής άπληστο αλγόριθμο επίλυσης του παραπάνω προβλήματος. Επιλέγει τις θέσεις με φθίνουσα σειρά έντασης ενίσχυσης. Δηλαδή, επιλέγει πρώτα τη θέση με τη μέγιστη ενίσχυση, μετά επιλέγει την επόμενη (στη φθίνουσα σειρά) θέση που δεν είναι γειτονική με κάποια που έχει ήδη επιλεγεί, κοκ, και επιστρέφει τη συνολική ένταση ενίσχυσης που προκύπτει.

(i) Είναι αυτός ο αλγόριθμος βέλτιστος; Συμπληρώστε "ΝΑΙ" ή "ΌΧΙ" (με κεφαλαία ελληνικά χωρίς κενό ή κόμμα)

5.2¶

Ερώτηση 2 / 4 (Ελευθέρου Κειμένου — 0.20 βαθμοί)

(ii) Αν ναι, δώστε μια σύντομη απόδειξη ότι βρίσκει πάντοτε τη βέλτιστη λύση. Αν όχι, δώστε ένα αντιπαράδειγμα για το οποίο ο αλγόριθμος βρίσκει μια μη βέλτιστη λύση.

5.3¶

Ερώτηση 3 / 4 (Ελευθέρου Κειμένου — 0.40 βαθμοί)

(β) Έστω E(i) η ένταση ενίσχυσης σε μια βέλτιστη λύση για το υποπρόβλημα που περιλαμβάνει τις θέσεις s1, ..., si. Δώστε την αναδρομική σχέση ενός αλγορίθμου δυναμικού προγραμματισμού για τον υπολογισμό της E(i), με τις τιμές των αρχικών συνθηκών, αιτιολογώντας εν συντομία την απάντησή σας.

5.4¶

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

(γ) Εκτελέστε τον αλγόριθμό σας (την αναδρομική σχέση) στο παραπάνω παράδειγμα συμπληρώνοντας τις τιμές της E(i) ($1 \le i \le 10$) στον παρακάτω πίνακα.

E(1)
E(2)
E(3)
E(4)
E(5)
E(6)
E(7)
E(8)
E(9)
E(10)

E(1): [] E(2): [] E(3): [] E(4): [] E(5): []
E(6): [] E(7): [] E(8): [] E(9): []
E(10): []

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

Λύσεις (🟡 community)

Κατάσταση: 🟡 community Πηγή: σελίδες 5–6 του Themata_Sept21-Algo.pdf (λύσεις Prim και Kruskal, μορφή αντιστοίχισης)

Προσοχή

Το κλειδί Kruskal δεν αντιστοιχεί σε ερώτηση που μεταγράφεται στο 2021-09.md: το Θέμα 3 έχει μόνο το ερώτημα (α) για Prim· δεν βρέθηκε ερώτημα Kruskal.

Λύσεις — Εισαγωγή στους Αλγόριθμους — Σεπτέμβριος 2021¶

Αντιστοιχίσεις των λύσεων Prim και Kruskal για το Θέμα 3 (α) της εξέτασης, όπως εμφανίζονται στις σελίδες 5–6 του PDF. Η προέλευση δεν αναγράφεται στο αρχείο· η κατάταξη ως community είναι εκτίμηση. Οι στήλες «Θέση» δείχνουν τη σειρά προσθήκης της ακμής στο ΕΓΔ, όπως προκύπτει από τα γράμματα της αντιστοίχισης· «—» = δεν ανήκει στο ΕΓΔ.

Λύση Prim (Θέμα 3 (α), αρχική κορυφή a)¶

Σειρά προσθήκης στο ΕΓΔ: {a,e} (1), {a,f} (2), {f,j} (3), {d,e} (4), {c,e} (5), {b,c} (6), {c,g} (7), {g,h} (8), {h,i} (9).

Στήλη Α	Αντιστοιχία	Στήλη Β
1.	Τ	—
2.	Α	Θέση 1
3.	Β	Θέση 2
4.	F	Θέση 6
5.	Τ	—
6.	Τ	—
7.	Τ	—
8.	Ε	Θέση 5
9.	G	Θέση 7
10.	D	Θέση 4
11.	Τ	—
12.	Τ	—
13.	Τ	—
14.	C	Θέση 3
15.	H	Θέση 8
16.	Τ	—
17.	Τ	—
18.	I	Θέση 9
19.	Τ	—

Λύση Kruskal (ίδιο γράφημα του Θέματος 3)¶

Σειρά προσθήκης στο ΕΓΔ: {b,c} (1), {c,g} (2), {a,e} (3), {f,j} (4), {a,f} (5), {d,e} (6), {c,e} (7), {h,i} (8), {g,h} (9).

Στήλη Α	Αντιστοιχία	Στήλη Β
1.	—	—
2.	C	Θέση 3
3.	E	Θέση 5
4.	A	Θέση 1
5.	—	—
6.	—	—
7.	—	—
8.	G	Θέση 7
9.	B	Θέση 2
10.	F	Θέση 6
11.	—	—
12.	—	—
13.	—	—
14.	D	Θέση 4
15.	I	Θέση 9
16.	—	—
17.	—	—
18.	H	Θέση 8
19.	—	—

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

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