Αλγόριθμοι και Συνδυαστική Βελτιστοποίηση — Φεβρουάριος 2022¶
Η μεταγραφή προέρχεται από το αρχείο FEB22.ALCO.pdf (6 σελίδες).
FEB22.ALCO.pdf¶
ΤΜΗΜΑ ΜΗΧ/ΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ
ΑΛΓΟΡΙΘΜΟΙ & ΣΥΝΔΥΑΣΤΙΚΗ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ
ΕΞΕΤΑΣΗ ΦΕΒΡΟΥΑΡΙΟΥ 2022 – 16.02.2022
Διάρκεια Εξέτασης: 2 ώρες
ΘΕΜΑ 1 (1.5 μονάδες).
Θεωρήστε το παρακάτω κατευθυνόμενο γράφημα G, στο οποίο οι αριθμοί που συσχετίζονται με τις ακμές του αναπαριστούν κόστος. Παρατηρήστε ότι όλες οι διαδρομές από την κορυφή s στην κορυφή t έχουν το ίδιο κόστος (520). Θεωρήστε τώρα την εκτέλεση του αλγορίθμου Dijkstra στο G με αρχική κορυφή την s.
[Σχήμα: Κατευθυνόμενο γράφημα με κόμβους s, x, u, y, z, v, w, t και βάρη ακμών: (s,x)=280, (s,u)=80, (s,y)=200, (x,z)=160, (u,z)=360, (u,v)=160, (u,w)=200, (y,w)=80, (z,t)=80, (v,t)=280, (w,t)=240]
(α) [0.6] Ποια διαδρομή θα υπολογίσει ως συντομότερη από την s στην t ο αλγόριθμος Dijkstra;
(β) [0.3] Πόσες επαναλήψεις θα εκτελέσει ο κύριος βρόχος while του αλγορίθμου Dijkstra;
(γ) [0.6] Ποια είναι η πρώτη επανάληψη του βρόχου while κατά την οποία η ετικέτα της κορυφής t θα λάβει την τιμή 520;
ΤΜΗΜΑ ΜΗΧ/ΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ
ΑΛΓΟΡΙΘΜΟΙ & ΣΥΝΔΥΑΣΤΙΚΗ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ
ΕΞΕΤΑΣΗ ΦΕΒΡΟΥΑΡΙΟΥ 2022 – 16.02.2022
ΘΕΜΑ 2 (1.5 μονάδες).
Θεωρήστε το δίκτυο G του παρακάτω σχήματος όπου οι αριθμοί δίπλα σε κάθε ακμή αναπαριστούν τη χωρητικότητα της ακμής.
[Σχήμα: Δίκτυο ροής με κόμβους s, x, a, b, y, t και χωρητικότητες ακμών: (s,x)=120, (x,y)=60, (y,t)=120, (s,a)=200, (a,t)=200, (s,b)=200, (b,t)=200, (a,b)=100, (b,a)=100]
(α) [0.8] Ποια είναι η πρώτη s-t διαδρομή διέλευσης (s-t admissible path) που θα θεωρήσει ο αλγόριθμος συντομότερης διαδρομής επαύξησης (shortest augmenting path) αν εφαρμοστεί στο G; Αν υπάρχουν περισσότερες από μία πρώτες s-t διαδρομές διέλευσης, τότε να τις αναφέρετε όλες.
(β) [0.7] Ποια είναι η τιμή της μέγιστης s-t ροής στο G;
ΤΜΗΜΑ ΜΗΧ/ΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ
ΑΛΓΟΡΙΘΜΟΙ & ΣΥΝΔΥΑΣΤΙΚΗ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ
ΕΞΕΤΑΣΗ ΦΕΒΡΟΥΑΡΙΟΥ 2022 – 16.02.2022
ΘΕΜΑ 3 (1.5 μονάδες).
Θεωρήστε το παρακάτω δίκτυο G, στο οποίο οι αριθμοί που συσχετίζονται με τις ακμές του αναπαριστούν χωρητικότητα.
[Σχήμα: Δίκτυο ροής με κόμβους s, b, a, t και χωρητικότητες ακμών: (s,b)=12, (b,s)=8, (s,a)=10, (b,t)=10, (a,t)=12]
Θεωρήστε την εκτέλεση του αλγορίθμου προροής-προώθησης (preflow-push) στο παραπάνω δίκτυο G.
(α) [0.6] Κατασκευάστε το τελικό υπολειπόμενο δίκτυο μετά τον τερματισμό του αλγορίθμου προροής-προώθησης.
(β) [0.3] Ποια είναι η τιμή της ελάχιστης αποκοπής στο G;
(γ) [0.6] Ποια είναι η τελική ετικέτα d(b) της κορυφής b μετά το τέλος της εκτέλεσης του αλγορίθμου;
ΤΜΗΜΑ ΜΗΧ/ΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ
ΑΛΓΟΡΙΘΜΟΙ & ΣΥΝΔΥΑΣΤΙΚΗ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ
ΕΞΕΤΑΣΗ ΦΕΒΡΟΥΑΡΙΟΥ 2022 – 16.02.2022
ΘΕΜΑ 4 (1.5 μονάδες).
Θεωρήστε το παρακάτω δίκτυο, στο οποίο οι αριθμοί που συσχετίζονται με τις ακμές του αναπαριστούν χωρητικότητα.
[Σχήμα: Δίκτυο ροής με κόμβους s, a, b, v, u, t και χωρητικότητες ακμών: (s,a)=30, (a,b)=16, (a,v)=8, (b,u)=16, (b,v)=4, (v,u)=14, (u,t)=32]
(α) [0.5] Ποια είναι η τιμή της μέγιστης s-t ροής ;
(β) [0.5] Ποια είναι η ελάχιστη s-t αποκοπή;
(γ) [0.5] Κατασκευάστε το υπολειπόμενο δίκτυο μετά την προώθηση 4 μονάδων ροής κατά μήκος της διαδρομής (s,a,b,v,u,t).
ΤΜΗΜΑ ΜΗΧ/ΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ
ΑΛΓΟΡΙΘΜΟΙ & ΣΥΝΔΥΑΣΤΙΚΗ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ
ΕΞΕΤΑΣΗ ΦΕΒΡΟΥΑΡΙΟΥ 2022 – 16.02.2022
ΘΕΜΑ 5 (1 μονάδα).
Προσδιορίστε ποιες από τις ακόλουθες προτάσεις είναι αληθείς και ποιες ψευδείς. Δικαιολογήστε την απάντησή σας είτε δίνοντας την απόδειξη όταν η πρόταση είναι αληθής, είτε δίνοντας ένα αντιπαράδειγμα όταν η πρόταση είναι ψευδής.
(α) Αν όλα τα κόστη ενός κατευθυνόμενου γραφήματος είναι διαφορετικά, τότε το δένδρο συντομότερων διαδρομών (με ρίζα μια οποιαδήποτε αρχική κορυφή s) είναι μοναδικό.
(β) Έστω \(G\) ένα κατευθυνόμενο γράφημα με θετικά κόστη ακμών, και έστω \(G'\) η μη κατευθυνόμενη εκδοχή του \(G\), δηλ. το \(G'\) προκύπτει αν απαλείψουμε (ή αγνοήσουμε) την κατεύθυνση κάθε ακμής του \(G\). Τότε, για οποιεσδήποτε δύο κορυφές u και v, ισχύει ότι \(\delta_{G'}(u,v) = \delta_G(u,v)\), δηλαδή η απόσταση των u και v παραμένει ίδια και στα δύο γραφήματα.
ΤΜΗΜΑ ΜΗΧ/ΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ
ΑΛΓΟΡΙΘΜΟΙ & ΣΥΝΔΥΑΣΤΙΚΗ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ
ΕΞΕΤΑΣΗ ΦΕΒΡΟΥΑΡΙΟΥ 2022 – 16.02.2022
ΘΕΜΑ 6 (3 μονάδες).
(α) [2.0] Δίνεται το γραμμικό πρόγραμμα \(\Pi\): $\(\min 4x_1 - 2x_2 + 3x_3 - x_4\)$ υπό τις συνθήκες \(\Sigma\): $\(x_1 \ge 0,\ x_2 \ge 0,\ x_3 \ge 0,\ x_4 \ge 0\)$ $\(x_1 + x_2 + x_3 - 2x_4 = 1\)$ $\(3x_1 + 3x_2 + 3x_3 + x_4 = 10\)$
Βρείτε τη βέλτιστη λύση του \(\Pi\), δηλαδή το \(z = \min (4x_1 - 2x_2 + 3x_3 - x_4)\) υπό τις συνθήκες \(\Sigma\), καθώς και ένα διάνυσμα \((x_1, x_2, x_3, x_4)\) που αντιστοιχεί στη βέλτιστη λύση. Αιτιολογήστε την απάντησή σας.
\(\underline{\text{Υπόδειξη}}\): Χρησιμοποιήστε γεωμετρική λύση (όχι simplex).
(β)[1.0] Έστω ένα γράφημα \(G\) που είναι ένας κύκλος \(n\) κορυφών. Απαντήστε στα παρακάτω ερωτήματα αιτιολογώντας την απάντησή σας.
(\(\beta\)1) [0.3] Είναι το \(G\) διμερές γράφημα όταν το \(n\) είναι άρτιος;
(\(\beta\)2) [0.3] Είναι το \(G\) διμερές γράφημα όταν το \(n\) είναι περιττός;
(\(\beta\)3) [0.4] Για το \(G\) με \(n\) κορυφές, \(n\) άρτιο, βρείτε:
(ι) Το πλήθος των ακμών του μέγιστου ταιριάσματος (maximum cardinality matching) του \(G\).
(ιι) Το πλήθος κορυφών της ελάχιστης κάλυψης κορυφών (minimum vertex cover) του \(G\).
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2022-02.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):2025-01-26_172947.png,157.png,Screenshot_388.png,6a_Feb22.jpg,feb_22_suggested-solutions.pdf
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: προτεινόμενες λύσεις φοιτητή (ανέβηκαν στο Discord στις 2023-01-31 με τον τίτλο «δικές μου προτεινόμενες λύσεις»)· η φωτογραφία 6a_Feb22.jpg είναι μερική λύση φοιτητή (Discord 2024-06-03)
Προσοχή
Θέμα 2: το σχήμα της λύσης γράφει χωρητικότητα 170 στις ακμές (s,x) και (y,t), ενώ το Θέμα 2 έχει 120 και στις δύο. Οι αποκοπές 520 και 460 της λύσης συμφωνούν με το 120, άρα πρόκειται για σφάλμα στο σχήμα της λύσης ή στην ανάγνωση του αρχείου. Θέμα 3: το σχήμα της λύσης γράφει (s,b)=18, (b,s)=2, (a,t)=10, (t,a)=2, ενώ το Θέμα 3 έχει (s,b)=12, (b,s)=8, (a,t)=12. Η τιμή ελάχιστης αποκοπής 20 συμφωνεί και με τις δύο εκδοχές (αποκοπή {s,b} | {a,t}: 10+10 = 20). Θέμα 4(α): η λύση γράφει c({s,a,b,v},{u,t}) = 40 και c({s,a,b,u},{v,t}) = 30. Με τις χωρητικότητες του θέματος οι τιμές είναι 30 (ακμές (b,u)=16, (v,u)=14) και 40 (ακμές (a,v)=8, (u,t)=32) αντίστοιχα, άρα φαίνεται να έχουν αντιστραφεί. Η ελάχιστη αποκοπή 24 δεν επηρεάζεται. Θέμα 6: η μερική λύση της 6a_Feb22.jpg χρησιμοποιεί αντικειμενική συνάρτηση με +2x_2, ενώ το Θέμα 6(α) έχει −2x_2, άρα η λύση δεν απαντά στο ίδιο ερώτημα. Η λύση είναι επίσης ημιτελής (τελειώνει πριν από το τελικό αποτέλεσμα).
Λύσεις — Αλγόριθμοι και Συνδυαστική Βελτιστοποίηση — Φεβρουάριος 2022¶
Λύσεις που ανέβασαν φοιτητές για τα Θέματα 1–6 της εξέτασης Φεβρουαρίου 2022. Δεν είναι επίσημες ούτε έχουν ελεγχθεί από τον διδάσκοντα. Οι μεταγραφές προέρχονται από αυτόματη ανάγνωση των αρχείων· τα σχήματα των λύσεων μεταφέρονται όπως αναγράφονται (βλ. warnings για ασυμφωνίες).
feb_22_suggested-solutions.pdf¶
Φεβρουάριος 2022
Θέμα 1.α)
| \(d(s)\) | \(d(x)\) | \(d(u)\) | \(d(y)\) | \(d(z)\) | \(d(v)\) | \(d(w)\) | \(d(t)\) | \(S\) | |
|---|---|---|---|---|---|---|---|---|---|
| 0. | 0 | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) | \(-\) |
| 1. | 0 | 280 | 80 | 200 | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) | \(s\) |
| 2. | 0 | 280 | 80 | 200 | 440 | 240 | 280 | \(\infty\) | \(s, u\) |
| 3. | 0 | 280 | -//- | -//- | 440 | 240 | 280 | \(\infty\) | \(s, u, y\) |
| 4. | 0 | 280 | -//- | -//- | 440 | -//- | 280 | 520 | \(s, u, y, v\) |
| 5. | 0 | 280 | -//- | -//- | 440 | -//- | -//- | 520 | \(s, u, y, v, w\) |
| 6 | 0 | -//- | -//- | -//- | 440 | -//- | -//- | 520 | \(s, u, y, v, w, x\) |
| 7. | 0 | -//- | -//- | -//- | -//- | -//- | -//- | 520 | \(s, u, y, v, w, x, z\) |
| 8. | 0 | -//- | -//- | -//- | -//- | -//- | -//- | -//- | \(s, u, y, v, w, x, z, t\) |
\(\Sigma.\Delta. (s, t) \to s, u, v, t\)
β) 8 επαναλήψεις
γ) Η 4η επανάληψη
Θέμα 2α)
[Σχήμα: Δίκτυο ροής με κόμβους s, x, y, a, b, t. Χωρητικότητες/ακμές: (s,x): 170, (s,a): 200, (s,b): 200, (x,y): 60, (y,t): 170, (a,t): 200, (b,t): 200, (a,b): 100, (b,a): 100. Ετικέτες κόμβων / αποστάσεις: s:2, x:2, y:1, a:1, b:1, t:0]
\(1^\eta\) s-t διαδρ. επαυξ. \(\Rightarrow\) s-a-t / s-b-t
2β) Αποκοπές: \(c(\{s\}, \{a, b, x, y, t\}) = 520\) \(\to c(\{s, x\}, \{a, b, y, t\}) = 460\) \(c(\{s, a\}, \{b, x, y, t\}) = 820\) \(c(\{s, b\}, \{a, x, y, t\}) = 620\) \(c(\{s, x, y\}, \{a, b, t\}) = 520\) \(c(\{s, x, a\}, \{b, y, t\}) = 560\) \(c(\{s, x, b\}, \{a, y, t\}) = 560\) \(\to c(\{s, a, b\}, \{x, y, t\}) = 460\) \(c(\{s, a, b, x, y\}, \{t\}) = 520\)
Ελάχιστη αποκοπή = 460 \(\Downarrow\) Μέγιστη ροή s-t
Θέμα 3α)
[Σχήμα: Κατευθυνόμενο γράφημα με κόμβους s, a, b, t. Ακμές και χωρητικότητες/κόστη: (s,b): 18, (b,s): 2, (b,t): 10, (s,a): 10, (a,t): 10, (t,a): 2. Τιμές δίπλα στους κόμβους: s:4, b:5, a:1, t:0]
| s | -22 | -22 | -22 | -20 |
| a | 10 | 0 | 0 | 0 |
| b | 12 | 12 | 2 | 0 |
| t | 0 | 10 | 20 | 20 |
β) Τιμή ελ. αποκοπής = \(|f_{max}| = 20\)
γ) \(d(b) = 5\)
Θέμα 4α) Αποκοπές: \(c(\{s\}, \{a, b, u, v, t\}) = 30\) Ελ. Αποκοπή \(\to c(\{s, a\}, \{b, u, v, t\}) = 24\) \(c(\{s, a, b\}, \{u, v, t\}) = 28\) \(c(\{s, a, v\}, \{b, u, t\}) = 30\) \(c(\{s, a, b, v\}, \{u, t\}) = 40\) \(c(\{s, a, b, u\}, \{v, t\}) = 30\) \(c(\{s, a, b, u, v\}, \{t\}) = 32\)
γ)
[Σχήμα: Δίκτυο ροής με κόμβους s, a, b, v, u, t. Ακμές με τιμές ροής/χωρητικότητας: (s,a): 26/4, (a,b): 12/4, (a,v): 8/4, (b,u): 16, (v,b): 0/4, (v,u): 10, (u,t): 28/4]
Θέμα 5α) Αντιπαράδειγμα:
[Σχήμα: Γράφημα με κόμβους s, a, b και ακμές με βάρη: (s,a): 5, (s,b): 3, (b,a): 2]
Προκύπτουν 2 Δέντρα Σ.Δ.
1)
[Σχήμα: Δέντρο 1: s -> 3 -> b -> a]
[Σχήμα: Δέντρο 2: s -> 5 -> a, s -> 3 -> b]
Άρα Λάθος
β) Αντιπαράδειγμα:
[Σχήμα: Γράφημα G με κόμβους s, a, b, ακμές (a,s) βάρος 1, (s,b) βάρος 2, (b,a) βάρος 2. \(d_G(s,a)=4\)]
[Σχήμα: Γράφημα G' με κόμβους s, a, b, ακμές (s,a): 1, (s,b): 2, (b,a): 2. \(d_{G'}(s,a)=1\)]
Άρα Λάθος
6a_Feb22.jpg¶
\(\min 4x_1 + 2x_2 + 3x_3 - x_4\)
\(x_1, x_2, x_3, x_4 \ge 0\)
\(x_1 + x_2 + x_3 - 2x_4 = 1\)
\(3x_1 + 3x_2 + 3x_3 + x_4 = 10\)
\(\cdot x_1 + x_2 + x_3 - 2x_4 = 1 \Rightarrow x_3 = 1 - x_1 - x_2 + 2x_4 = 1 - (x_1 + x_2) + 2x_4 \quad (1)\)
\(\cdot 3x_1 + 3x_2 + 3x_3 + x_4 = 10 \Rightarrow 3x_3 + x_4 = 10 - 3x_1 - 3x_2 \Rightarrow 3x_3 = 10 - 3(x_1 + x_2) - x_4\)
\((1) \Rightarrow 3 \cdot [1 - (x_1 + x_2) + 2x_4] = 10 - 3(x_1 + x_2) - x_4 \Rightarrow\)
\(\Rightarrow 3 - 3(x_1 + x_2) + 6x_4 = 10 - 3(x_1 + x_2) - x_4 \Rightarrow 3 + 6x_4 = 10 - x_4 \Rightarrow 7x_4 = 7 \Rightarrow\)
\(\Rightarrow x_4 = 1 \quad (2) \quad (x_4 \ge 0 \text{ ισχύει})\)
άρα
\(x_1 + x_2 + x_3 - 2x_4 = 1 \stackrel{(2)}{\Rightarrow} x_1 + x_2 + x_3 = 3\)
\(3x_1 + 3x_2 + 3x_3 + x_4 = 10 \stackrel{(2)}{\Rightarrow} 3x_1 + 3x_2 + 3x_3 = 9 \Rightarrow x_1 + x_2 + x_3 = 3\)
\(\rightarrow\) Ο μόνος περιορισμός: \(x_3 = 3 - x_1 - x_2\).
\(Z = 4x_1 + 2x_2 + 3(3 - x_1 - x_2) - 1 = x_1 - x_2 + 8\).
νέο πρόβλημα: \(\min x_1 - x_2 + 8\)
\(x_1, x_2 \ge 0 \rightsquigarrow x_1 + x_2 \ge 0\)
\(\cdot x_1 + x_2 = 0 \rightsquigarrow \begin{bmatrix} 0 \\ 0 \end{bmatrix}\)
[Σχήμα: Διάγραμμα αξόνων \(x_1, x_2\) με ένδειξη σημείου \((0,0)\)]