Παράλληλοι Αλγόριθμοι — Ιούνιος 2023¶
Η μεταγραφή προέρχεται από τα στιγμιότυπα Screenshot_2.png, received_286754653920788.webp, SmartSelect_20230625_204716_Microsoft_365_Office.jpg και Screenshot_1.png.
Screenshot_2.png¶
[Πάνω από το στιγμιότυπο, πληκτρολογημένο:]
Δώστε αριθμητική τιμή για τη διάμετρο του παρακάτω δικτύου/γραφήματος
[Στιγμιότυπο οθόνης ηλεκτρονικής εξέτασης (Open eClass):]
Ερώτηση 3 / 20 (Συμπλήρωση Κενών (Αυστηρή Ταυτοποίηση) — 1 βαθμός)
Δώστε αριθμητική τιμή για τη διάμετρο του παρακάτω δικτύου/γραφήματος.
[Σχήμα: γράφημα/δίκτυο με πράσινους κόμβους (τετράγωνα) και καμπύλες ή ευθείες ακμές, φωτογραφημένο υπό γωνία· χωρίς αριθμητικές ετικέτες· η ακριβής τοπολογία δεν είναι αναγνώσιμη]
Σημείωση: το πεδίο απάντησης της ηλεκτρονικής φόρμας περιέχει πληκτρολογημένη απάντηση φοιτητή· δεν μεταγράφεται.
received_286754653920788.webp¶
Ερώτηση 7 / 20 (Πολλαπλής Επιλογής ([δυσανάγνωστο]) — 1 βαθμός)
Δίνεται 9x9 πλέγμα και 7 πακέτα προς δρομολόγηση με χρήση του άπληστου αλγορίθμου δρομολόγησης (greedy routing algorithm). Ποιο είναι το μέγιστο μέγεθος ουράς που μπορεί να σχηματιστεί;
- [ ] 4
- [ ] 3
- [ ] N
- [ ] N-2
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
SmartSelect_20230625_204716_Microsoft_365_Office.jpg¶
Ερώτηση 10 / 20 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 1 βαθμός)
Πόσα το πολύ βήματα απαιτεί ο αλγόριθμος Carry-Lookahead για την άθροιση δύο N-bit αριθμών;
- [ ] \(N+1\)
- [ ] \(2\log N+1\)
- [ ] \(\log N\)
- [ ] \(2N-1\)
Screenshot_1.png¶
Το πρόβλημα δρομολόγησης που φαίνεται στο σχήμα οδηγεί στη δημιουργία ουρών μεγέθους
[Λείπει από τη φωτογραφία: η συνέχεια της πρότασης μετά τη λέξη «μεγέθους»]
[Σχήμα: κατευθυνόμενο γράφημα σε σχήμα Y. Στον αριστερό κλάδο οι κόμβοι (μέσα σε τετράγωνα) είναι d_N, d_2, d_1 με ετικέτες b_N, b_2, b_1 έξω από αυτούς. Στον δεξιό κλάδο οι κόμβοι (μέσα σε τετράγωνα) είναι c_N, c_2, c_1 με ετικέτες a_N, a_2, a_1. Οι δύο κλάδοι συγκλίνουν σε κεντρικό κόμβο με ετικέτα [δυσανάγνωστο]. Από τον κεντρικό κόμβο συνεχίζει κατακόρυφη αλυσίδα κόμβων με ετικέτες [δυσανάγνωστο: c_1 ή r_1], d_1, [δυσανάγνωστο: c_2 ή r_2], d_2, ..., [δυσανάγνωστο]_N, d_N (το πρώτο γράμμα των ετικετών της αλυσίδας δεν είναι βέβαιο). Τα βέλη δείχνουν την κατεύθυνση των ακμών, και οι τελείες δηλώνουν παραλείψεις.]
- [ ] 2N/3-1
- [ ] \(\sqrt{N}\)
- [ ] 1
Σημείωση: το στιγμιότυπο είναι περικομμένο στο κάτω μέρος. Δεν φαίνονται επιλογές πέρα από τις παραπάνω.
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2023-06.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):rn_image_picker_lib_temp_bf7046c4-0423-47d5-9d9b-8eff643a4f66.jpg
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: φωτογραφία χειρόγραφης λύσης φοιτητή (μπλε μελάνι, προέλευση δεν καταγράφεται)
Προσοχή
Η φωτογραφία φέρει επικεφαλίδα «Q6K Ιουν 2023», ενώ το 2023-06.md μεταγράφει μόνο τις ερωτήσεις 3, 7 και 10· η αντιστοίχιση με ερώτηση της εξέτασης δεν επαληθεύεται. Η φωτογραφία είναι περικομμένη στο πάνω άκρο και έχει δυσανάγνωστα σημεία· οι τιμές των κελιών δεν έχουν ελεγχθεί.
Λύσεις — Παράλληλοι Αλγόριθμοι — Ιούνιος 2023¶
rn_image_picker_lib_temp_bf7046c4-0423-47d5-9d9b-8eff643a4f66.jpg¶
[Σχήμα (στο πάνω άκρο, κομμένο): κύκλοι με ετικέτες 3,1 · 3,2 · 3,3 · 3,4, συνδεδεμένοι οριζόντια με γραμμές, και κάθετες συνδέσεις προς τα πάνω. Μπλε μελάνι.]
Q6K Ιουν 2023
| c,1 | a,2 | b,4 | c,4 |
|---|---|---|---|
| c,2 | b,3 | b,2 | a,1 |
| c,3 | a,2 | d,4 | d,3 |
| a,3 | b,1 | d,1 | a,4 |
[Σχήμα: βέλος από τον αριστερό πίνακα στον δεξιό]
| c,1 | b,3 | b,2 | d,4 |
|---|---|---|---|
| c,2 | b,1 | b,4 | d,3 |
| a,3 | a,2 | d,4 | a,1 |
| c,3 | d,2 | d,1 | c,4 |
Μετά τον [δυσανάγνωστο]: Χρώματα: (c,1), (b,3), (b,2), (d,4)
β: (c,2), (b,1), (b,4), (d,3)
γ: (a,3), (a,2), (d,4), (a,1)
δ: (c,3), (d,2), (d,1), (c,4)