Παράλληλοι Αλγόριθμοι — Ιούνιος 2024¶
Η μεταγραφή προέρχεται από τα στιγμιότυπα του ηλεκτρονικού διαγωνίσματος Ιουνίου 2024 και τη φωτογραφία IMG_2270.jpg.
2024-06-25_224917.png¶
Ερώτηση 1 / 20 (Συμπλήρωση Κενών (Αυστηρή Ταυτοποίηση) — 1 βαθμός)
Πόσα βήματα απαιτούνται για την εκτέλεση του πολλαπλασιασμού διανύσματος με πίνακα στο παρακάτω σχήμα;
[Σχήμα: διάταξη στοιχείων πίνακα σε 4 στήλες (από αριστερά προς τα δεξιά). Στήλη 1 (από κάτω προς τα πάνω): a11, a12, a13, a14. Στήλη 2: a21, a22, a23, a24. Στήλη 3: a31, a32, a33, a34. Στήλη 4: a41, a42, a43, a44. Κάθε επόμενη στήλη ξεκινά μία θέση πιο ψηλά. Κάτω από κάθε στήλη υπάρχει βέλος που δείχνει σε ένα πράσινο ορθογώνιο· τα 4 ορθογώνια φέρουν την ετικέτα "x4x3x2x1" στα αριστερά τους.]
ΠΡΟΣΟΧΗ: πληκτρολογήστε μόνο τη ζητούμενη αριθμητική τιμή χωρίς κενά - σε κάθε άλλη περίπτωση (όπως π.χ., παράθεση κενών ή συμβόλων ή σχολίων ή κάθε μορφής επεξηγήσεων που ΔΕΝ ζητούνται) η απάντηση δεν θα ληφθεί υπόψιν
Πλήθος βημάτων = ______________
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
Screenshot_7.png¶
Ερώτηση 7 / 20 (Συμπλήρωση Κενών (Αυστηρή Ταυτοποίηση) — 1 βαθμός)
Κανένας αλγόριθμος δεν μπορεί να πραγματοποιήσει snakelike ταξινόμηση σε διδιάστατο πλέγμα (mesh) διαστάσεων \(N \times N\) σε λιγότερα από \(L\) βήματα.
ΠΡΟΣΟΧΗ: πληκτρολογήστε μόνον τη ζητούμενη τιμή με λατινικούς χαρακτήρες, χωρίς κενά - σε κάθε άλλη περίπτωση (όπως π.χ. παράθεση κενών ή συμβόλων ή σχολίων ή κάθε μορφής επεξηγήσεων που ΔΕΝ ζητούνται) η απάντηση δεν θα ληφθεί υπόψιν
\(L =\) ________
Screenshot_2024-06-25_190101.png¶
Ερώτηση 7 / 20 (Πολλαπλής Επιλογής (Πολλαπλές Απαντήσεις) — 0.99 βαθμοί)
Ποιες ιδιότητες πρέπει να έχει ένα γράφημα για να είναι δέντρο;
- [ ] Να μην περιέχει κύκλο
- [ ] Να είναι συνεκτικό
- [ ] Να είναι μη κατευθυνόμενο
- [ ] Να περιέχει κύκλο
- [ ] Να μην είναι συνεκτικό
- [ ] Να είναι κατευθυνόμενο
- [ ] Να έχει ρίζα
- [ ] Να έχει φύλλα
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
Screenshot_from_2024-06-25_14-35-33.png¶
Ερώτηση 19 / 20 (Συμπλήρωση Κενών (Αυστηρή Ταυτοποίηση)) — 1 βαθμός
Δώστε αριθμητική τιμή για τη διάμετρο του παρακάτω δικτύου/γραφήματος.
[Σχήμα: δενδρική δομή με ρίζα στην κορυφή, κλαδιά προς τα κάτω και κόκκινους κόμβους· στο κάτω άκρο σειρά ορθογώνιων κουτιών. Το πλήθος των κόμβων δεν διακρίνεται με βεβαιότητα.]
[πεδίο απάντησης (συμπλήρωση κενού)]
Σημείωση: στο πεδίο απάντησης της εικόνας υπάρχει τιμή που έχει γράψει φοιτητής· δεν μεταγράφηκε.
Screenshot_from_2024-06-25_14-47-21.png¶
Ποια είναι η διάμετρος του γραφήματος του σχήματος;
[Σχήμα: κόμβοι A, B, C, D σε γραμμή, με ακμές A–B, B–C και C–D. Ο κόμβος D συνδέεται με τους κόμβους E, F, n και G. Μεταξύ των E, F, n και G υπάρχουν ακμές, και η ακμή ανάμεσα στους κόμβους n και G φέρει τις τελείες «...». Η αγκύλη κάτω από τους κόμβους E, F, n, G φέρει την ετικέτα «Πλήρες γράφημα με n κορυφές». Ορισμένες ακμές από το D είναι διακεκομμένες.]
Σημείωση: το γράμμα της ετικέτας του πλήθους κορυφών (n ή η) είναι δυσδιάκριτο στη μικρή εικόνα.
IMG_2270.jpg¶
Σε πόσα βήματα μπορούν να δρομολογηθούν k μεταθέσεις (όπου k δύναμη του 2) σε γραμμικό πλέγμα με N επεξεργαστές
[Σχήμα: φωτογραφία οθόνης εγγράφου· κάτω από το κείμενο υπάρχει στιγμιότυπο ηλεκτρονικής εξέτασης με μπάρα πλοήγησης ερωτήσεων (1 έως 20) και κουμπιά πλοήγησης] [δυσανάγνωστο: επικεφαλίδα, αριθμός ερώτησης και κείμενο των επιλογών του στιγμιότυπου]
- [ ] [δυσανάγνωστο: 4 επιλογές απάντησης]
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
Screenshot_2024-06-26_143259.png¶
Θέμα 35ο
Offline αλγόριθμος δρομολόγησης
Ένας offline αλγόριθμος δρομολόγησης Α εκτελείται για ένα-προς-ένα προβλήματα δρομολόγησης σε N x N πλέγμα.
Εξελίσσεται ως εξής:
Φάση 1: αναδιάταξε τα πακέτα σε κάθε στήλη ώστε το πολύ ένα πακέτο σε κάθε γραμμή να έχει προορισμό μία στήλη
Φάση 2: σε κάθε γραμμή δρομολόγησε κάθε πακέτο στη σωστή στήλη
Φάση 3: σε κάθε στήλη δρομολόγησε κάθε πακέτο στη σωστή γραμμή
Ποια από τα παρακάτω στιγμιότυπα αντιστοιχούν σε κάποιο που προκύπτει μετά την εκτέλεση της Φάσης 1 του Α;
- [ ] Επιλογή 1 (πίνακας):
| c1 | b3 | b2 | c4 |
|---|---|---|---|
| c3 | a2 | b4 | a4 |
| a3 | d2 | d1 | a1 |
| c2 | b1 | d4 | d3 |
- [ ] Επιλογή 2 (πίνακας):
| c1 | b3 | b2 | c4 |
|---|---|---|---|
| a3 | b1 | b4 | a1 |
| c2 | d2 | d4 | d3 |
| c3 | a2 | d1 | a4 |
- [ ] Επιλογή 3 (πίνακας):
| c1 | b3 | b2 | c4 |
|---|---|---|---|
| c3 | b1 | d4 | d3 |
| c2 | a2 | d1 | a4 |
| a3 | d2 | b4 | a1 |
- [ ] Επιλογή 4 (πίνακας):
| c1 | b3 | b2 | c4 |
|---|---|---|---|
| c2 | b1 | d4 | d3 |
| c3 | a2 | d1 | a4 |
| a3 | d2 | b4 | a1 |
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
2024-06-26_4.51.00_.png¶
Σημείωση: στο πάνω άκρο της φωτογραφίας φαίνεται το πεδίο «L =» της Ερώτησης 7 (βλ. Screenshot_7.png).
Θέμα 42ο
Carry-Lookahead
Χρησιμοποιείται ο αλγόριθμος Carry-Lookahead για την πρόσθεση δύο αριθμών των N bits. Συμπληρώστε την πρώτη (S-P-G), δεύτερη (CARRY, κρατούμενο) και τελευταία γραμμή (SUM, άθροισμα) του παρακάτω πίνακα.
[Σχήμα: πίνακας με γραμμές S-P-G, CARRY, N1, N2, SUM· τα γράμματα X, Y, Z είναι κόκκινες επισημάνσεις στο στιγμιότυπο]
| S-P-G | X | ||||||||||||||||
| CARRY | Y | ||||||||||||||||
| N1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | |
| N2 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | |
| SUM | Z |
- [ ] X=S, Y=1, Z=1
- [ ] X=P, Y=1, Z=0
- [ ] X=S, Y=0, Z=1
- [ ] X=G, Y=0, Z=1
- [ ] X=P, Y=0, Z=0
- [ ] X=G, Y=1, Z=1
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
IMG_2525.png¶
Θέμα 25ο
Στο γράφημα του σχήματος υπάρχει ταίριασμα (matching) μεγέθους 2.
[Σχήμα: γράφημα με κορυφές v1–v8. Ακμές: v1–v2, v1–v6, v1–v7, v1–v8, v2–v5, v2–v6, v3–v5, v4–v5, v5–v6.]
- [ ] Σωστό
- [ ] Λάθος
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2024-06.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):Screenshot_from_2024-06-22_16-51-24.png,IMG_0311.png,IMG_2524.png
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: φωτογραφία λύσης «Θέμα 7ο» από φοιτητή (προέλευση δεν καταγράφεται)
Προσοχή
Η ερώτηση (πλέγμα 9×9, 7 πακέτα, άπληστος αλγόριθμος δρομολόγησης, επιλογές 4, 3, N, N−2) δεν μεταγράφεται στο 2024-06.md· η διατύπωσή της υπάρχει μόνο στη φωτογραφία της λύσης και δεν έχει επαληθευτεί με το πρωτότυπο. Η απάντηση «3» είναι μία από τις επιλογές· ο υπολογισμός (2/3)·9 − 3 προϋποθέτει √N = 9 (N = 81 επεξεργαστές), το οποίο δεν αναφέρεται ρητά στη φωτογραφία. Ο τύπος (2/3)√N − 3 της φωτογραφίας περιγράφει το μέγεθος ουράς στη χειρότερη περίπτωση, σύμφωνα με το απόσπασμα του βιβλίου που παρατίθεται στη φωτογραφία· η λύση δεν εξηγεί γιατί η τιμή αυτή είναι το ακριβές μέγιστο για τα συγκεκριμένα 7 πακέτα. Παρόμοια ερώτηση για τον greedy αλγόριθμο με άλλες επιλογές (N, 1, 2N/3−1, 2N−2) υπάρχει στο 2020-06.md (ερώτηση 16)· δεν πρόκειται για την ίδια ερώτηση. Η λύση είναι κοινοτική (φωτογραφία φοιτητή)· η αντιστοίχισή της με την εξέταση Ιουνίου 2024 βασίζεται στην ένδειξη «Θέμα 7ο» και δεν επιβεβαιώνεται.
Λύσεις — Παράλληλοι Αλγόριθμοι — Ιούνιος 2024¶
IMG_2524.png¶
Θέμα 7ο
Δίνεται 9*9 πλέγμα και 7 πακέτα προς δρομολόγηση με χρήση άπληστου αλγορίθμου δρομολόγησης Ο τύπος είναι \(\frac{2}{3} * \sqrt{N} - 3\).
Δίνεται 9x9 πλέγμα και 7 πακέτα προς δρομολόγηση με χρήση του άπληστου αλγορίθμου δρομολόγησης (greedy routing algorithm). Ποιο είναι το μέγιστο μέγεθος ουράς που μπορεί να σχηματιστεί;
- [ ] 4
- [ ] 3
- [ ] N
- [ ] N-2
Δηλαδή έχουμε \(\frac{2}{3} * 9 - 3 = 3\).
Although the basic greedy algorithm is optimal in terms of worst-case running time, the maximum queue size can be as large as \(\frac{2}{3}\sqrt{N} - 3\) in the worst case. To see why, consider the routing problem where the packets
Λήμμα 8. Το μέγιστο μέγεθος ουράς κόμβου που δημιουργεί ο άπληστος αλγόριθμος δρομολόγησης σε διδιάστατο πλέγμα επεξεργαστών είναι \(O(\sqrt{N})\).