Παράλληλοι Αλγόριθμοι — Ιούνιος 2020¶
Η μεταγραφή προέρχεται από τα στιγμιότυπα Screenshot_265.png, 2023-09-07_165735.jpg, IMG_2783.png, received_261117816566146.webp και 158.png· το κείμενο των ερωτήσεων είναι αυτό που φαίνεται στα στιγμιότυπα. Οι διπλές φωτογραφίες 920.png, a_29.png και 2024-04-08_7.34.28_.PNG επιβεβαιώνουν την ερώτηση 17 και 16.
Screenshot_265.png¶
Παράλληλοι Αλγόριθμοι: γραπτή εξέταση 6/2020
Ερώτηση 9 / 20 (Συμπλήρωση Κενών (Αυστηρή Ταυτοποίηση) — 1 βαθμός)
Για την ταξινόμηση της ακολουθίας \(\langle 5,9,3,1,4,6,4,2 \rangle\) χρησιμοποιούμε τον αλγόριθμο εναλλαγής άρτιων-περιττών θέσεων (odd even transposition sort) σε γραμμικό πλέγμα. Ποιο είναι το περιεχόμενο των επεξεργαστών του πλέγματος μετά την εκτέλεση του Βήματος 3;
Πληκτρολογήστε την απάντηση σας με τη μορφή a b c ή a,b,c ή a, b, c
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
2023-09-07_165735.jpg¶
Παράλληλοι Αλγόριθμοι: γραπτή εξέταση 6/2020
Ερώτηση 10 / 20 (Συμπλήρωση Κενών (Αυστηρή Ταυτοποίηση) — 1 βαθμός)
Πόσα – το πολύ – bits έχει το άθροισμα N αριθμών των k bits;
Πληκτρολογήστε την απάντηση σας χωρίς κενά.
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
IMG_2783.png¶
[κομμένο στην εικόνα: επάνω μέρος της οθόνης, χωρίς αριθμό ερώτησης]
Δώστε αριθμητική τιμή για τη διάμετρο του παρακάτω δικτύου/γράφηματος.
[Σχήμα: δίκτυο/γράφημα με πράσινα σημειωμένους κόμβους, ευθείες και καμπύλες ακμές· ακριβής δομή δεν διακρίνεται με βεβαιότητα]
Παράλληλοι Αλγόριθμοι: γραπτή εξέταση Ιουνίου 2020 Υπολειπόμενος χρόνος: 11:10
Ερώτηση 14 / 20 (Συμπλήρωση Κενών (Αυστηρή Ταυτοποίηση) — 1 βαθμός)
Χρησιμοποιείται ο αλγόριθμος Carry-Lookahead για την πρόσθεση δύο αριθμών των N bits. Στο παρακάτω στιγμιότυπο ποια θα είναι η τιμή στη θέση X;
| S,P,G | s | p | g | s | g | s | p | p | s |
|---|---|---|---|---|---|---|---|---|---|
| CARRY | X |
[Η επόμενη ερώτηση της ίδιας φωτογραφίας (αριθμός δεν φαίνεται) είναι διαφορετική από την ερώτηση 14.]
Στο γράφημα του σχήματος υπάρχει ταίριασμα (matching) μεγ
[Λείπει από τη φωτογραφία: η συνέχεια της πρότασης μετά τη λέξη «μεγ» και το υπόλοιπο της ερώτησης, κομμένα στο κάτω μέρος του κάδρου]
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
received_261117816566146.webp¶
[Στιγμιότυπο της πλατφόρμας eClass. Παραλείπονται: ο σύνδεσμος του virtual room, ο μετρητής χρόνου και τα κουμπιά πλοήγησης.]
Παράλληλοι Αλγόριθμοι: γραπτή εξέταση Ιουνίου 2020
Ερώτηση 16 / 20 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 1 βαθμός)
Ποιο είναι το μέγιστο μέγεθος ουράς που δημιουργεί ο βασικός άπληστος (greedy) αλγόριθμος δρομολόγησης για ένα-προς-ένα προβλήματα δρομολόγησης όταν εκτελείται σε \(N \times N\) πλέγμα επεξεργαστών;
- [ ] \(N\)
- [ ] \(1\)
- [ ] \(2N/3-1\)
- [ ] \(2N-2\)
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
158.png¶
Ερώτηση 17 / 20 (Συμπλήρωση Κενών (Αυστηρή Ταυτοποίηση) — 1 βαθμός)
Δίνεται NxN πλέγμα, ένα-προς-ένα πρόβλημα δρομολόγησης και ο παρακάτω αλγόριθμος δρομολόγησης που βασίζεται στην ταξινόμηση:
Φάση 1.α: ταξινόμησε snakelike τα πακέτα με βάση τη στήλη προορισμού
Φάση 1.β: ταξινόμησε τα πακέτα σε column-major διάταξη με βάση τη στήλη προορισμού
Φάση 2: στείλε τα πακέτα στη σωστή στήλη
Φάση 3: στείλε τα πακέτα στη σωστή γραμμή
Ο αλγόριθμος αυτός εκτελείται για το στιγμιότυπο του σχήματος. Ποιο είναι το περιεχόμενο του επεξεργαστή στο κόκκινο πλαίσιο μετά την ολοκλήρωση της Φάσης 2 του αλγορίθμου;
[Σχήμα: δύο πλέγματα 4×4. Αριστερό με τίτλο "Αρχικά" (τιμές στον πίνακα παρακάτω). Δεξιό με τίτλο "Μετά τη Φάση 2", κενό, με κόκκινο πλαίσιο στο κελί της 3ης γραμμής και της 3ης στήλης.]
Αρχικά:
| 1,3 | 2,1 | 4,3 | 1,1 |
|---|---|---|---|
| 3,4 | 2,4 | ||
| 4,1 | 2,3 | 4,2 | |
| 2,2 | 3,3 |
Πληκτρολογήστε την απάντηση σας με τη μορφή a b ή a,b ή a, b
Σημείωση: στιγμιότυπο οθόνης της πλατφόρμας eClass· μεταγράφεται μόνο η εκφώνηση. Η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: φωτογραφία χειρόγραφης λύσης φοιτητή (προέλευση δεν καταγράφεται)
Προσοχή
Η φωτογραφία είναι μερικώς δυσανάγνωστη (επικεφαλίδες σχημάτων και ένα κελί στο πάνω δεξιά μέρος)· η μεταγραφή δεν έχει επαληθευτεί με το πρωτότυπο. Η λύση είναι κοινοτική (χειρόγραφη, φοιτητή)· η αντιστοίχισή της με την ερώτηση 17 βασίζεται στο περιεχόμενο (πλέγμα 4×4) και δεν επιβεβαιώνεται από επικεφαλίδα.
Λύσεις — Παράλληλοι Αλγόριθμοι — Ιούνιος 2020¶
355050383_913301029771033_5914886162306643944_n.jpg¶
[Σχήμα (πάνω αριστερά, χωρίς επικεφαλίδα): πλέγμα 4×4 με κελιά όπως γράφονται στη φωτογραφία· τα κενά κελιά είναι χωρίς περιεχόμενο· το πάνω δεξιά κελί [δυσανάγνωστο]]
| 1,3 | 2,1 | 4,3 | [δυσανάγνωστο] |
|---|---|---|---|
| 3,4 | 2,4 | ||
| 4,1 | 2,3 | 4,2 | |
| 2,2 | 3,3 |
[Σχήμα (πάνω δεξιά, κυκλωμένο 1, επικεφαλίδα [δυσανάγνωστη]): πλέγμα 4×4 με κελιά όπως γράφονται· βέλη ← και → δίπλα στη δεξιά στήλη [δυσανάγνωστα ως προς τη θέση τους]]
| 1,1 | 1,3 | 2,1 | 4,3 |
|---|---|---|---|
| 3,4 | 2,4 | 0 | 0 |
| 0 | 2,3 | 4,1 | 4,2 |
| 3,3 | 2,2 | 0 | 0 |
[Σχήμα (μέση αριστερά, κυκλωμένο 2, επικεφαλίδα [δυσανάγνωστη]): πλέγμα 4×4 με κελιά όπως γράφονται]
| 0 | 1,3 | 0 | 0 |
|---|---|---|---|
| 1,1 | 2,2 | 0 | 0 |
| 3,3 | 2,3 | 2,1 | 4,2 |
| 3,4 | 2,4 | 4,1 | 4,3 |
[Σχήμα (κάτω αριστερά, κυκλωμένο 3, επικεφαλίδα [δυσανάγνωστη]): πλέγμα 3 γραμμών × 4 στηλών· δεξιά των γραμμών βέλη ← → ← → [δυσανάγνωστα ως προς την αντιστοίχισή τους]]
| 0 | 0 | 0 | 1,3 |
|---|---|---|---|
| 2,2 | 2,1 | 0 | 0 |
| 4,2 | 3,3 | 2,3 | 2,2 |
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.