Παράλληλοι Αλγόριθμοι — Φεβρουάριος 2025 (γραπτή)¶

Η μεταγραφή προέρχεται από τις πέντε φωτογραφίες της γραπτής εξέτασης Φεβρουαρίου 2025, με τη σειρά των ερωτήσεων (1-6, 7-11, 12-17, 18-20, 21).

476745714_1161216502197419_2454755405158331382_n.jpg¶

ΠΑΡΑΛΛΗΛΟΙ ΑΛΓΟΡΙΘΜΟΙ ΓΡΑΠΤΗ ΕΞΕΤΑΣΗ ΦΕΒΡΟΥΑΡΙΟΥ 2025

AM: __________________

ΟΝΟΜΑΤΕΠΩΝΥΜΟ: __________________

Διάρκεια εξέτασης: 2 ώρες Βαθμολόγηση: όλες οι ερωτήσεις είναι ισοδύναμες (5 μονάδες έκαστη, άριστα το 100, μία ερώτηση bonus) και προσμετρώνται μόνον οι σωστές απαντήσεις (δεν υπάρχει "αρνητική βαθμολογία") Απαντήσεις: Μη ευκρινείς απαντήσεις δεν θα ληφθούν υπόψιν.

ΕΡΩΤΗΣΕΙΣ

Για την ταξινόμηση Ν αριθμών σε γραμμικό πλέγμα με Ν επεξεργαστές εφαρμόζουμε αλγόριθμο που εξελίσσεται σε 2 Φάσεις. Κατά την Φάση 1, κάθε επεξεργαστής δέχεται είσοδο από τους γειτονικούς του, συγκρίνει την είσοδο με την τιμή που έχει αποθηκευμένη, περνάει τη μεγαλύτερη τιμή στο δεξιότερο γείτονά του και αποθηκεύει τοπικά τη μικρότερη τιμή. Κατά τη Φάση 2, πραγματοποιείται εξαγωγή των ταξινομημένων αριθμών από το πλέγμα.

Η Φάση 1 ολοκληρώνεται σε το πολύ __________________ βήματα.
Η Φάση 2 – χωρίς τη χρήση επιπλέον υλικού – απαιτεί στην καλύτερη περίπτωση __________________ επιπλέον βήματα.

Για τον παραπάνω παράλληλο αλγόριθμο, υπολογίστε την επιτάχυνση (speed-up) που πετυχαίνει, το παραγόμενο έργο και την αποδοτικότητά του.

Επιτάχυνση (speed-up) = __________________
Έργο (work) = __________________
Αποδοτικότητα (efficiency) = __________________
Δίνονται δύο παράλληλοι αλγόριθμοι που λύνουν ένα πρόβλημα μεγέθους M Ο πρώτος εκτελείται σε M βήματα σε υπολογιστή με M επεξεργαστές και ο δεύτερος σε $\sqrt{M}$ βήματα σε υπολογιστή με $M^2$ επεξεργαστές. Ποιος αλγόριθμος θα εκτελεστεί γρηγορότερα σε υπολογιστή με N επεξεργαστές;

Ένας απλός αλγόριθμος ταξινόμησης λίστας N αριθμών σε γραμμικό πλέγμα με N επεξεργαστές λειτουργεί ως εξής: κάθε επεξεργαστής δέχεται είσοδο από τον αριστερό του γείτονα, συγκρίνει την είσοδο με την τιμή που έχει τοπικά αποθηκευμένη, προωθεί τη μεγαλύτερη τιμή στο δεξιό του γείτονα και αποθηκεύει τοπικά τη μικρότερη τιμή.

1

476572177_1295832211520319_1887642575773979373_n.jpg¶

[Σχήμα: δίκτυο ταξινόμησης αποτελούμενο από διαδοχικά μπλοκ]

Με τον αλγόριθμο αυτό, για την ταξινόμηση Ν k-bit αριθμών χρειάζονται

__________________ word-βήματα
__________________ bit-βήματα
Στο γράφημα του σχήματος

το (ελάχιστο) εύρος διχοτόμησης (bisection width) είναι

τιμή = __________________

υποδείξτε στο σχήμα τις κορυφές που ανήκουν σε καθένα από τα 2 σύνολα της διαμέρισης από την οποία προκύπτει το εύρος διχοτόμησης που υπολογίσατε κορυφές στο σύνολο 1: μη σκιασμένες στο σχήμα κορυφές στο σύνολο 2: σκιασμένες στο σχήμα

[Σχήμα: δέντρο με κυκλικούς και τετράγωνους κόμβους σε επίπεδα]

Ποια είναι η διάμετρος του γραφήματος στο σχήμα;

Διάμετρος = __________________

[Σχήμα: γράφημα αποτελούμενο από κύβο (υπερκύβο 3D) συνδεδεμένο μέσω δύο ενδιάμεσων κόμβων με πλήρες γράφημα 5 κόμβων]

Επιθυμούμε να αθροίσουμε N δυαδικούς αριθμούς μεγέθους N bits ο καθένας σε γραμμικό πλέγμα. Το γραμμικό πλέγμα πρέπει να περιέχει τουλάχιστον __________________ επεξεργαστές.

2

476578505_594410456759015_1085197383100723536_n.jpg¶

Χρησιμοποιούμε τον παράλληλο αλγόριθμο για την εύρεση του μικρότερου από μια ακολουθία αριθμών (σχήμα α) ως υπορουτίνα για την παράλληλη ταξινόμηση της ακολουθίας αριθμών 5,1,7,6 (σχήμα β).

[Σχήμα: (α) διαγράμματα συγκρίσεων και κατακόρυφη στήλη 3 επεξεργαστών, (β) πίνακας bit και πλέγμα $4 \times 3$ επεξεργαστών]

(α)

(β)

Η ταξινόμηση ολοκληρώνεται μετά από __________________ βήματα.

Εκτελείται ο αλγόριθμος Carry-Lookahead για την άθροιση δύο αριθμών των N bits ο καθένας. Η τιμή στην αριστερότερη θέση στην s-p-g ακολουθία στα φύλλα του δέντρου που χρησιμοποιείται για την πρόβλεψη του κρατουμένου είναι __________________
Ποιες είναι οι τιμές στις θέσεις (a) και (b) στην ακολουθία κρατουμένων με δεδομένη την παρακάτω s-p-g ακολουθία;

Τιμή στη θέση (a): __________________ Τιμή στη θέση (b): __________________

S-P-G	$x_{16}$	$x_{15}$	$x_{14}$	$x_{13}$	$x_{12}$	$x_{11}$	$x_{10}$	$x_9$	$x_8$	$x_7$	$x_6$	$x_5$	$x_4$	$x_3$	$x_2$	$x_1$
S-P-G	s	g	p	p	g	p	s	s	p	p	s	g	p	p	p	s
CARRY	(a)	(b)

Για τον παράλληλο πολλαπλασιασμό σε γραμμικό πλέγμα δύο αριθμών των 256 bits ο καθένας - με χρήση του παράλληλου αλγόριθμου για τον υπολογισμό της συνέλιξης (η λειτουργία του οποίου σκιαγραφείται στο σχήμα) - απαιτούνται πλέγμα με __________________ επεξεργαστές και __________________ βήματα.

[Σχήμα: γραμμικό πλέγμα επεξεργαστών με είσοδο $a_3, a_2, a_1$ από αριστερά και $b_3, b_2, b_1$ από δεξιά]

Πόσα βήματα το πολύ απαιτεί ο αλγόριθμος ταξινόμησης Shearsort για την ταξινόμηση $N^2$ αριθμών σε NxN πλέγμα επεξεργαστών; __________________

17. (α) Υποδείξτε δεξιά στο σχήμα την τοποθέτηση των δεδομένων για τον παράλληλο υπολογισμό του γινο[δυσανάγνωστο] διανύσματος x με 4 στοιχεία [x1, x2, x3, x4] και του πίνακα A 4 x 4 που φαίνεται αριστερά στο σχήμα γραμμικού πλέγματος με 4 επεξεργαστές.

3

476333643_640909195086434_2129664546912098817_n.jpg¶

a11	a12	a13	a14
a21	a22	a23	a24
a31	a32	a33	a34
a41	a42	a43	a44

[Σχήμα: 4 επεξεργαστές σε γραμμή με κατακόρυφα βέλη εισόδου και οριζόντιο βέλος προς τα δεξιά]

(β) Πόσα βήματα απαιτούνται για τον πολλαπλασιασμό αυτό; __________________

18. (α) Υποδείξτε δεξιά στο σχήμα την τοποθέτηση των δεδομένων για τον παράλληλο υπολογισμό του γινομένου ενός διανύσματος x με 4 στοιχεία [x1, x2, x3, x4] και του πίνακα A 4 x 4 που φαίνεται αριστερά στο σχήμα με χρήση δακτυλίου με 4 επεξεργαστές.

a11	a12	a13	a14
a21	a22	a23	a24
a31	a32	a33	a34
a41	a42	a43	a44

[Σχήμα: δακτύλιος 4 επεξεργαστών με βέλη εισόδου A από πάνω και διάνυσμα x]

(β) Πόσα βήματα απαιτούνται για τον πολλαπλασιασμό αυτό; __________________

Εκτελούμε τον (βέλτιστο) παράλληλο αλγόριθμο ταξινόμησης των Schnorr και Shamir σε πλέγμα 128x128. Αριθμούμε τις στήλες του πλέγματος από αριστερά προς τα δεξιά με τους αριθμούς 0 έως 127. Τα δεδομένα της στήλης 17 μεταφέρονται στη στήλη __________________ μετά το “ανακάτεμα” (unshuffle) κατά τη $2^\eta$ φάση του αλγορίθμου.
Υπολογίστε και καταγράψτε 4 ξένα μεταξύ τους πλήρη ταιριάσματα (perfect matchings) στο γράφημα του σχήματος.

Ταίριασμα 1: {__________________}

Ταίριασμα 2: {__________________}

Ταίριασμα 3: {__________________}

Ταίριασμα 4: {__________________}

[Σχήμα: διμερές γράφημα με κόμβους A, B, C, D στα αριστερά και 1, 2, 3, 4 στα δεξιά και ακμές μεταξύ τους]

4

476392728_640653641661789_8066318022394221417_n.jpg¶

Για το στιγμιότυπο δρομολόγησης που φαίνεται στο σχήμα χρησιμοποιούμε τον παράλληλο αλγόριθμο δρομολόγησης που βασίζεται στην ταξινόμηση. Τοποθετήστε τα πακέτα στο πλέγμα όπως φαίνονται μετά το τέλος κάθε φάσης.

Αρχικά
(3.3)		(2.1)	(3.4)
(1.4)		(4.3)
	(3.1)	(1.1)	(2.2)
(2.4)	(4.2)	(2.3)	(1.2)

Μετά τη Φάση 2				Μετά τη Φάση 3

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2025-02¶

Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.

Θέμα 1¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια

Η Φάση 1 (παράλληλη ταξινόμηση με ανταλλαγές σε γραμμικό πλέγμα) ολοκληρώνεται σε το πολύ $N$ βήματα.

Θέμα 2¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια

Χωρίς επιπλέον υλικό, η εξαγωγή των $N$ ταξινομημένων στοιχείων από το πλέγμα απαιτεί στην καλύτερη περίπτωση $N$ επιπλέον βήματα (ένα στοιχείο ανά βήμα).

Θέμα 3¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια

Θεωρώντας ως σειριακό χρόνο τον βέλτιστο $O(N\log N)$ και συνολικό παράλληλο χρόνο $T_p=2N$, η επιτάχυνση είναι [ S=\frac{N\log N}{2N}=\frac{\log N}{2}. ]

Θέμα 4¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια

Το παραγόμενο έργο είναι [ W=p\,T_p=N\cdot 2N=2N^2. ]

Θέμα 5¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια

Η αποδοτικότητα είναι [ E=\frac{S}{p}=\frac{\log N}{2N}. ]

Θέμα 6¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

Με $N$ επεξεργαστές, ο χρόνος του 1ου είναι $T_1=\max(M, M^2/N)$ και του 2ου $T_2=\max(\sqrt{M}, M^{5/2}/N)$. Συγκρίνοντας: - Αν $N<M^{3/2}$, γρηγορότερος είναι ο 1ος αλγόριθμος. - Αν $N>M^{3/2}$, γρηγορότερος είναι ο 2ος αλγόριθμος. - Αν $N=M^{3/2}$, είναι ισοδύναμοι. (Υπόθεση τέλειου καταμερισμού/επικάλυψης.)

Θέμα 7¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια

Word-βήματα: $N$ (ή $O(N)$).

Θέμα 8¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια

Bit-βήματα: $Nk$ (ή $O(Nk)$), αφού κάθε σύγκριση $k$-bit αριθμών κοστίζει $O(k)$ bit-βήματα και γίνονται $N$ γύροι.

Θέμα 9¶

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

τιμή = 2

Αιτιολόγηση: Από το δέντρο του σχήματος στην εικόνα 476572177_1295832211520319_1887642575773979373_n.jpg: - Στην κορυφή υπάρχει ρίζα αποτελούμενη από 2 τετράγωνους κόμβους σε σειρά. - Από τον κάτω κόμβο της ρίζας ξεκινούν 2 κλάδοι προς 2 κυκλικούς κόμβους (αριστερό και δεξιό). - Κάθε κυκλικός κόμβος διακλαδίζεται σε 2 αλυσίδες των 3 τετραγώνων η καθεμία (άρα $2 \times 3 = 6$ τετράγωνοι κόμβοι κάτω από κάθε κυκλικό κόμβο). - Το συνολικό πλήθος των κόμβων του γραφήματος είναι $V = 2 \text{ (ρίζα)} + 2 \text{ (κύκλοι)} + 4 \times 3 \text{ (τετράγωνα φύλλων)} = 16$ κόμβοι. - Μία ισομερής διχοτόμηση (bisection) απαιτεί διαμέριση σε δύο υποσύνολα $V_1, V_2$ με $|V_1| = |V_2| = 8$ κόμβους. - Κόβοντας μόνο μία ακμή του δέντρου δεν προκύπτει ποτέ υποδέντρο μεγέθους ακριβώς 8 (τα μεγέθη υποδέντρων είναι 1, 2, 3, 7 ή 9). - Επιλέγοντας ως $V_1$ τον αριστερό κυκλικό κόμβο μαζί με τους 6 απογόνους του και τον κάτω τετράγωνο κόμβο της ρίζας ($1 + 6 + 1 = 8$ κόμβοι), οι ακμές που συνδέουν το $V_1$ με το υπόλοιπο δέντρο $V_2$ είναι ακριβώς 2: 1. Η ακμή μεταξύ του κάτω και του άνω τετραγώνου της ρίζας. 2. Η ακμή μεταξύ του κάτω τετραγώνου της ρίζας και του δεξιού κυκλικού κόμβου. - Επομένως, το ελάχιστο εύρος διχοτόμησης είναι 2. - Υπόδειξη διαμέρισης: - Κορυφές στο σύνολο 1 (μη σκιασμένες): ο αριστερός κυκλικός κόμβος, οι $2 \times 3 = 6$ τετράγωνοι απόγονοί του, και ο κάτω τετράγωνος κόμβος της ρίζας (σύνολο 8). - Κορυφές στο σύνολο 2 (σκιασμένες): ο δεξιός κυκλικός κόμβος, οι $2 \times 3 = 6$ τετράγωνοι απόγονοί του, και ο άνω τετράγωνος κόμβος της ρίζας (σύνολο 8).

Θέμα 10¶

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Διάμετρος = 7

Αιτιολόγηση: Από το γράφημα του σχήματος στην εικόνα 476572177_1295832211520319_1887642575773979373_n.jpg: - Το γράφημα αποτελείται από: 1. Έναν 3-διάστατο υπερκύβο $Q_3$ (8 κορυφές, διάμετρος $D_{Q_3} = 3$). 2. Μία κορυφή $v_{\text{cube}}$ του υπερκύβου συνδέεται με ενδιάμεσο κόμβο $u_1$ (1 ακμή). 3. Ο $u_1$ συνδέεται με τον $u_2$ (1 ακμή). 4. Ο $u_2$ συνδέεται με κορυφή $v_{K_5}$ ενός πλήρους γραφήματος $K_5$ με 5 κορυφές (1 ακμή). 5. Στο πλήρες γράφημα $K_5$, οποιαδήποτε άλλη κορυφή απέχει απόσταση ακριβώς 1 από την $v_{K_5}$. - Η μέγιστη απόσταση συντομότερου μονοπατιού (διάμετρος) επιτυγχάνεται μεταξύ της αντιδιαμετρικής κορυφής του $Q_3$ ως προς την $v_{\text{cube}}$ και οποιασδήποτε άλλης κορυφής του $K_5$: $$D = 3 \text{ (εντός } Q_3 \text{)} + 1 \text{ (cube } \to u_1 \text{)} + 1 \text{ (} u_1 \to u_2 \text{)} + 1 \text{ (} u_2 \to v_{K_5} \text{)} + 1 \text{ (εντός } K_5 \text{)} = 7$$

Θέμα 11¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια

Για την άθροιση $N$ δυαδικών αριθμών μεγέθους $N$ bits σε γραμμικό πλέγμα, απαιτούνται τουλάχιστον $N^2$ επεξεργαστές (ένας ανά bit, στο bit-level μοντέλο).

Θέμα 12¶

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Η ταξινόμηση ολοκληρώνεται μετά από 11 βήματα.

Αιτιολόγηση: Σύμφωνα με τη θεωρία του μαθήματος για την ταξινόμηση $N$ αριθμών μεγέθους $k$ bits σε $k \times N$ πλέγμα επεξεργαστών στο bit model (με χρήση της υπορουτίνας εύρεσης ελαχίστου με pipeline): - Εδώ έχουμε $N = 4$ αριθμούς (5, 1, 7, 6) και $k = 3$ bits (αφού $5=101_2, 1=001_2, 7=111_2, 6=110_2$, και το πλέγμα στο σχήμα $\beta$ έχει 3 γραμμές και 4 στήλες). - Ο συνολικός αριθμός βημάτων για την πλήρη ταξινόμηση και εξαγωγή των $N$ αριθμών των $k$ bits δίνεται από τον τύπο: $$T = 3N + k - 4 = 3 \times 4 + 3 - 4 = 12 + 3 - 4 = 11 \text{ βήματα}$$ (Σημείωση: η Φάση 1 εισαγωγής/σύγκρισης απαιτεί $2N + k - 2 = 9$ βήματα, και η ολοκλήρωση/εξαγωγή $3N + k - 4 = 11$ βήματα).

Θέμα 13¶

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

s (ή stop)

Αιτιολόγηση: Στον αλγόριθμο Carry-Lookahead (αλγόριθμο πρόβλεψης κρατουμένου) για την άθροιση δύο αριθμών $N$ bits: - Τα φύλλα του δέντρου παίρνουν τιμές $s$ (stop), $p$ (propagate), ή $g$ (generate). - Για την εκκίνηση του υπολογισμού προθεμάτων της ακολουθίας κρατουμένων, επειδή το αρχικό εισερχόμενο κρατούμενο είναι μηδέν ($c_0 = 0$), τοποθετείται αρχικό στοιχείο $s$ (stop). - Στο δέντρο πρόβλεψης κρατουμένου, η ακραία τιμή που αντιστοιχεί σε μηδενικό κρατούμενο τίθεται πάντοτε ίση με s (stop).

Θέμα 14¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια

Θεωρώντας ότι η γραμμή CARRY δίνει το κρατούμενο εξόδου της αντίστοιχης θέσης (με αρχικό κρατούμενο εισόδου $0$ στο $x_1$): - (a) στη θέση $x_{16}$: $0$ - (b) στη θέση $x_{15}$: $1$ (Αν ζητείται το κρατούμενο εισόδου, τότε (a)=$1$, (b)=$1$.)

Θέμα 15¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια

Χρησιμοποιώντας τον παράλληλο αλγόριθμο συνέλιξης σε γραμμικό πλέγμα για δύο αριθμούς 256 bits: απαιτούνται $2\cdot256-1=511$ επεξεργαστές και $511$ βήματα (ή $512$ αν μετρηθεί και το τελικό βήμα εξόδου).

Θέμα 16¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

Το Shearsort απαιτεί το πολύ [ N\left(2\lceil \log_2 N\rceil+1\right) ] βήματα, δηλαδή $O(N\log N)$.

Θέμα 17¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια

(α) Τοποθέτηση: Κάθε επεξεργαστής $P_i$ του γραμμικού πλέγματος 4 θέσεων αποθηκεύει την $i$-οστή γραμμή του πίνακα $A$: $P_1=(a_{11},a_{12},a_{13},a_{14})$, $P_2=(a_{21},\ldots,a_{24})$, $P_3=(a_{31},\ldots,a_{34})$, $P_4=(a_{41},\ldots,a_{44})$. Το διάνυσμα $x=[x_1,x_2,x_3,x_4]$ εισέρχεται από αριστερά και ολισθαίνει προς τα δεξιά, ένα στοιχείο ανά βήμα, με κάθε $P_i$ να πολλαπλασιάζει το τρέχον $x_j$ με το αντίστοιχο $a_{ij}$ και να αθροίζει. (β) Απαιτούνται $2N-1=7$ βήματα για $N=4$.

Θέμα 18¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια

(α) Τοποθέτηση: Κάθε επεξεργαστής $P_i$ του δακτυλίου 4 θέσεων αποθηκεύει την $i$-οστή γραμμή του $A$. Τα στοιχεία του $x$ αρχικά κατανέμονται ένα ανά επεξεργαστή ($x_i$ στον $P_i$) και κυκλοφορούν στον δακτύλιο. Σε κάθε βήμα, κάθε $P_i$ πολλαπλασιάζει το $x$ που δέχεται με το αντίστοιχο στοιχείο της γραμμής του και αθροίζει. (β) Απαιτούνται $N=4$ βήματα.

Θέμα 19¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια

Υποθέτοντας ότι στη 2η φάση ($\eta=1$) το unshuffle είναι δεξιά κυκλική ολίσθηση του 7-bit δυαδικού δείκτη της στήλης κατά 1 bit, η στήλη $17=0010001_2$ μεταφέρεται στη στήλη $1001000_2=72$. (Αν το unshuffle οριστεί ως αριστερή ολίσθηση, θα ήταν $34$.)

Θέμα 20¶

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Αιτιολόγηση: Από το διμερές γράφημα στην εικόνα 476333643_640909195086434_2129664546912098817_n.jpg: - Αριστερές κορυφές: $A, B, C, D$. - Δεξιές κορυφές: $1, 2, 3, 4$. - Κάθε κορυφή έχει βαθμό ακριβώς 4 (4-κανονικό διμερές πολυγράφημα). Συγκεκριμένα: - Η κορυφή $A$ συνδέεται με: 1, 3, και διπλή ακμή με το 2. - Η κορυφή $B$ συνδέεται με: 1, 3, και διπλή ακμή με το 2. - Η κορυφή $C$ συνδέεται με: 1, 3, και διπλή ακμή με το 4. - Η κορυφή $D$ συνδέεται με: 1, 3, και διπλή ακμή με το 4. - Τέσσερα ξένα μεταξύ τους πλήρη ταιριάσματα που καλύπτουν όλες τις ακμές του γραφήματος είναι:

Ταίριασμα 1: {(A, 2), (B, 1), (C, 4), (D, 3)}

Ταίριασμα 2: {(A, 2), (B, 3), (C, 4), (D, 1)}

Ταίριασμα 3: {(A, 1), (B, 2), (C, 3), (D, 4)}

Ταίριασμα 4: {(A, 3), (B, 2), (C, 1), (D, 4)}

(Όπου οι δύο ακμές $(A,2)$ και $(B,2)$ χρησιμοποιούνται από μία φορά στα ταιριάσματα 1 & 2 και 3 & 4 αντίστοιχα, και ομοίως οι διπλές ακμές $(C,4)$ και $(D,4)$).

Θέμα 21¶

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Αιτιολόγηση: Από το στιγμιότυπο δρομολόγησης $4 \times 4$ στην εικόνα 476392728_640653641661789_8066318022394221417_n.jpg: Κάθε πακέτο συμβολίζεται ως $(r.c)$ όπου $r$ είναι η γραμμή προορισμού και $c$ η στήλη προορισμού. Τα 12 ενεργά πακέτα ταξινομημένα κατά στήλη προορισμού (και γραμμή προορισμού) είναι: - Προορισμός στήλη 1: (1.1), (2.1), (3.1) - Προορισμός στήλη 2: (1.2), (2.2), (4.2) - Προορισμός στήλη 3: (2.3), (3.3), (4.3) - Προορισμός στήλη 4: (1.4), (2.4), (3.4)

Μετά τη Φάση 1 (Ταξινόμηση κατά στήλες / column-major):¶

Τα πακέτα διατάσσονται σε column-major σειρά κατά στήλη προορισμού, ώστε σε κάθε γραμμή να υπάρχει το πολύ ένα πακέτο για κάθε στήλη προορισμού:

(1.1)	(2.2)	(4.3)
(2.1)	(4.2)	(1.4)
(3.1)	(2.3)	(2.4)
(1.2)	(3.3)	(3.4)

Μετά τη Φάση 2 (Αποστολή στη σωστή στήλη κατά μήκος των γραμμών):¶

Κάθε πακέτο μετακινείται οριζόντια στη στήλη προορισμού του:

(1.1)	(2.2)	(4.3)
(2.1)	(4.2)		(1.4)
(3.1)		(2.3)	(2.4)
	(1.2)	(3.3)	(3.4)

Μετά τη Φάση 3 (Αποστολή στη σωστή γραμμή κατά μήκος των στηλών):¶

Κάθε πακέτο μετακινείται κατακόρυφα στην τελική θέση $(r.c)$:

(1.1)	(1.2)		(1.4)
(2.1)	(2.2)	(2.3)	(2.4)
(3.1)		(3.3)	(3.4)
	(4.2)	(4.3)

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

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

S-P-G	\(x_{16}\)	\(x_{15}\)	\(x_{14}\)	\(x_{13}\)	\(x_{12}\)	\(x_{11}\)	\(x_{10}\)	\(x_9\)	\(x_8\)	\(x_7\)	\(x_6\)	\(x_5\)	\(x_4\)	\(x_3\)	\(x_2\)	\(x_1\)
S-P-G	s	g	p	p	g	p	s	s	p	p	s	g	p	p	p	s
CARRY	(a)	(b)