Παράλληλοι Αλγόριθμοι — Ιούνιος 2025 (γραπτή)

Η μεταγραφή προέρχεται από τις τέσσερις σελίδες IMG_20250626_150017.jpg έως IMG_20250626_150113.jpg· οι λύσεις (PXL_20260129_*) δεν μεταγράφονται εδώ.

IMG_20250626_150017.jpg

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

[πεδία ΑΜ και ονοματεπώνυμου παραλείπονται]

Χρειάζομαι βεβαίωση συμμετοχής στην εξέταση ☐

Διάρκεια εξέτασης: 2 ώρες

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

Απαντήσεις: Μη ευκρινείς απαντήσεις δεν θα ληφθούν υπόψιν.

ΕΡΩΤΗΣΕΙΣ

1. Δίνονται δύο παράλληλοι αλγόριθμοι που λύνουν ένα πρόβλημα μεγέθους \(M\). Ο πρώτος εκτελείται σε \(M\) βήματα σε υπολογιστή με \(M\) επεξεργαστές και ο δεύτερος σε \(\sqrt{M}\) βήματα σε υπολογιστή με \(M^2\) επεξεργαστές. Ποιος αλγόριθμος θα εκτελεστεί γρηγορότερα σε υπολογιστή με \(N\) επεξεργαστές;

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

1. Η Φάση 1 ολοκληρώνεται σε το πολύ ________ βήματα.

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

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

1. Επιτάχυνση (speed-up) = ________

2. Έργο (work) = ________

3. Αποδοτικότητα (efficiency) = ________

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

IMG_20250626_150052.jpg

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

Με τον αλγόριθμο αυτό, για την ταξινόμηση 128 αριθμών των 16 bit ο καθένας χρειάζονται

1. _____ word-βήματα

2. _____ bit-βήματα

3. Πόσα φύλλα έχει πλήρες τριαδικό δέντρο με 514 κορυφές; _____

4. Στο γράφημα του σχήματος

[Σχήμα: γράφημα με 6 κόμβους (κύκλοι) σε 3 γραμμές των 2 κόμβων. Ακμές: οριζόντια στην πάνω, τη μεσαία και την κάτω γραμμή· κάθετες ακμές ανάμεσα στις γραμμές σε κάθε στήλη· δύο διαγώνιες που διασταυρώνονται ανάμεσα στη μεσαία και την κάτω γραμμή]

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

τιμή = _____

(η αριθμητική τιμή ΔΕΝ λαμβάνεται υπόψιν αν δεν υποδεικνύεται διαμέριση)

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

κορυφές στο σύνολο 1: μη σκιασμένες στο σχήμα

κορυφές στο σύνολο 2: σκιασμένες στο σχήμα

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

[Σχήμα: αριστερά τρισδιάστατος κύβος σε προοπτική· δύο μικροί κύκλοι ενώνουν τον κύβο με γράφημα δεξιά· δεξιά γράφημα με έξι κύκλους διατεταγμένους σε κύκλο, πυκνά συνδεδεμένους]

διάμετρος = _____

(η αριθμητική τιμή ΔΕΝ λαμβάνεται υπόψιν αν δεν υποδεικνύεται μονοπάτι)

υποδείξτε στο σχήμα μονοπάτι από το οποίο προκύπτει η διάμετρος που υπολογίσατε

IMG_20250626_150100.jpg

[Λείπει από τη φωτογραφία: το αρχικό «Χ» της πρώτης λέξης]

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

[Σχήμα (α): αριστερά ομάδα πλάγιων ωοειδών σχημάτων με μικρούς αριθμούς (0, 1, 2, 3, ορισμένοι [δυσανάγνωστοι])· δεξιά κατακόρυφη στήλη τριών τετραγώνων συνδεδεμένων μεταξύ τους]

[Σχήμα (β): πάνω οι τιμές 5, 1, 7, 6· από κάτω τρεις σειρές ψηφίων: 1 0 1 1 / 0 0 1 1 / 1 1 1 0· δεξιά πλέγμα τετραγώνων 3 σειρών × 4 στηλών συνδεδεμένων μεταξύ τους]

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

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

Εκτελείται ο αλγόριθμος Carry-Lookahead για την άθροιση δύο αριθμών των N bits ο καθένας.

14. Η τιμή στην δεξιότερη θέση στην s-p-g ακολουθία στα φύλλα του δέντρου που χρησιμοποιείται για την πρόβλεψη του κρατουμένου είναι __________.

15. Ποιες είναι οι τιμές στις θέσεις (a) και (b) στην ακολουθία κρατουμένων με δεδομένη την παρακάτω s-p-g ακολουθία;

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

S-P-G		x16	x15	x14	x13	x12	x11	x10	x9	x8	x7	x6	x5	x4	x3	x2	x1
S-P-G		s		p	p		p	s	s	p	p	s		p	p	p	s
CARRY					(a)				(b)

16. Υπολογίζουμε παράλληλα τη συνέλιξη δύο διανυσμάτων \(\bar{a} = (a_N, \ldots, a_1)\) και \(\bar{b} = (b_N, \ldots, b_1)\) μέσω της σχέσης

\[y_k = \sum_{i+j=k+1} a_i b_j\]

λαμβάνοντας ως αποτέλεσμα ένα νέο διάνυσμα \(\bar{y} = (y_{2N-1}, \ldots, y_1)\).

Για τον παράλληλο υπολογισμό της συνέλιξης δύο διανυσμάτων των 256 bit το καθένα απαιτούνται πλέγμα με __________ επεξεργαστές και __________ βήματα.

IMG_20250626_150113.jpg

17.

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

[Λείπει από τη φωτογραφία: τα τελικά γράμματα της λέξης «γινομένου» και της λέξης που αρχίζει με «χ» (δεξί άκρο της σελίδας)]

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

[Σχήμα (δεξιά): τέσσερα τετράγωνα (επεξεργαστές) σε σειρά, με βέλος εισόδου από επάνω προς καθένα· διαδοχικά τετράγωνα συνδέονται με βέλη προς τα δεξιά· το τελευταίο τετράγωνο συνδέεται με βρόχο που επιστρέφει στην αρχή της σειράς· στο αριστερό μέρος υπάρχει ετικέτα «A» με βέλος προς τα κάτω, στο δεξί μέρος του βρόχου ετικέτα «x».]

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

18.

Σε έναν αλγόριθμο ταξινόμησης που είναι oblivious και χρησιμοποιεί μόνο συγκρίσεις και μεταθέσεις δίνεται η είσοδος 5,3,1,4,2 και η εσφαλμένη έξοδος του αλγορίθμου είναι 1,2,4,3,5. Με βάση το 0-1 Λήμμα, σε ποια 0-1 ακολουθία αντιστοιχίζεται η έξοδος του αλγορίθμου; ______________

19.

Εκτελούμε τον (βέλτιστο) παράλληλο αλγόριθμο ταξινόμησης των Schnorr και Shamir σε πλέγμα 64x64. Αριθμούμε τις στήλες του πλέγματος από αριστερά προς τα δεξιά με τους αριθμούς 0 έως 63. Τα δεδομένα της στήλης 27 μεταφέρονται στη στήλη ______________ μετά το "ανακάτεμα" (unshuffle) κατά τη 2^η φάση του αλγορίθμου.

20.

Εφαρμόζουμε την τεχνική για τον υπολογισμό κάτω φράγματος για snakelike ταξινόμηση σε πλέγμα. Έχουμε πλέγμα με 256 στοιχεία. Η αρίθμηση γραμμών και στηλών ξεκινάει από την τιμή 1. Πόσες τιμές στο "τρίγωνο" πρέπει να είναι 0 ώστε η τιμή 183 να πάει στη στήλη 1; (α) ______________ ή (β) ______________

21.

Στο γράφημα του σχήματος, υποδείξτε, αν υπάρχουν, ένα μη πλήρες και ένα πλήρες ταίριασμα.

[Σχήμα: γράφημα με κορυφές A, B, C, D (αριστερή στήλη) και E, F, G (δεξιά στήλη). Ακμές, όπως διακρίνονται στη φωτογραφία: A–E, A–F, B–G, C–G, C–F, C–E (η C–E εμφανίζεται διακεκομμένη), D–F.]

μη πλήρες ταίριασμα
δεν υπάρχει μη πλήρες ταίριασμα
πλήρες ταίριασμα
δεν υπάρχει πλήρες ταίριασμα

Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις → 2025-06.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας): PXL_20260129_1659153952.jpg, PXL_20260129_1659197192.jpg, PXL_20260129_1659294562.jpg, PXL_20260129_1659345292.jpg

Λύσεις (🟡 community)

Κατάσταση: 🟡 community Πηγή: φωτογραφίες λύσεων από το Discord (Ιαν. 2026)

Προσοχή

Στο Discord (Φεβ. 2026) φοιτητής επισημαίνει ότι στην απάντηση 12 (3N+k−4) το k θα έπρεπε να είναι 3 και όχι 4, άρα 11 βήματα αντί για 12· η απάντηση δεν διορθώθηκε. Στην απάντηση 8 γράφεται «255 · 2 log 16 = 6 · 255», ενώ το 2·log₂16 είναι 8, όχι 6· ασυνέπεια αριθμητικής. Στην απάντηση 18 η μεταγραφή της φωτογραφίας γράφει είσοδο «5, 3, 1, 4, 20», ενώ η εκφώνηση στο 2025-06.md γράφει «5,3,1,4,2»· με είσοδο 5,3,1,4,2 και κατώφλι 4 η έξοδος 1,2,4,3,5 δίνει 0 0 1 0 1, άρα η απάντηση συμφωνεί με την εκφώνηση του 2025-06.md. Στο Discord (Φεβ. 2026) φοιτητής αναφέρει ότι «στις λύσεις Μ σίγουρα υπάρχουν λάθη»· οι λύσεις δεν έχουν ελεγχθεί με τον διδάσκοντα.

Λύσεις — Παράλληλοι Αλγόριθμοι — Ιούνιος 2025

PXL_20260129_1659153952.jpg

[ Παράλληλοι Αλγόριθμοι Γραπτή Εξέταση Ιουνίου 2025 ]

1 Δίνονται δυο παράλληλοι αλγ. που λύνουν ένα πρόβλημα μεγέθους Μ. Ο πρώτος εκτελείται σε Μ βήματα σε υπολογιστή με Μ επεξεργαστές και ο δεύτερος σε \(\sqrt{M}\) βήματα σε υπολογιστή με \(M^2\) επεξεργαστές. Ποιος αλγόρ. θα εκτελεστεί πιο γρήγορα σε Η/Υ με Ν επεξεργαστές;

• Προσομοιώνω τον 2ο αλγ: \(P_2 = M^2\) σε αλγ που τρέχει σε \(P_2 = N\) επεξ.: » Αν \(P_2 < P_1 \Rightarrow N < M^2\) τότε ο χρόνος που χρειάζεται ο αλγ 2 στο δίκτυο των Ν επεξεργαστών είναι: \(\sqrt{M} \cdot \lceil \frac{M^2}{N} \rceil\) βήματα

» Αν \(P_2 \ge P_1 \Rightarrow N \ge M^2\) τότε ο χρόνος που χρειάζεται ο αλγ 2 στο δίκτυο των Ν επεξ. είναι: \(\sqrt{M}\) βήματα

• Προσομοιώνω τον 1ο αλγ: \(P_1 = M\) σε αλγ που τρέχει σε \(P_2 = N\) επεξ: » Αν \(P_2 < P_1 \Rightarrow N < M\) τότε ο χρόνος που χρειάζεται ο αλγ 1 στο N-δίκτυο επεξ. είναι: \(M \cdot \lceil \frac{M}{N} \rceil\) βήματα.

» Αν \(P_2 \ge P_1 \Rightarrow N \ge M\) τότε ο χρ. \(M\) βήματα.

Σύντομη απάντηση: \(W = P \cdot T\): \(W_1 = M^2 \quad W_2 = M^{2.5} \quad T \approx \frac{W}{N}\) Άρα ο αλγ. 2 συμφέρει μόνο όταν \(T_2 < T_1 \Rightarrow \frac{M^{2.5}}{N} < M \Leftrightarrow N > M^{1.5}\) Άρα για \(N < M^{1.5}\) επιλέγουμε τον 1ο Αλγ., ενώ για \(N > M^{1.5}\) επιλέγουμε τον 2ο Αλγ.

Συνοπτικά: στο δίκτυο των Ν επεξ. 1) Ο Αλγ 1 εκτελείται σε χρόνο \(\approx \frac{M^2}{N}\) (για \(N < M\)) και \(M\) (για \(N \ge M\)) 2) Ο Αλγ 2 εκτελείται σε χρόνο \(\approx \frac{M^{2.5}}{N}\) (για \(N < M^2\)) και \(\sqrt{M}\) (για \(N \ge M^2\))

[Σχήμα: άξονας με σημεία 0, \(N_A\), \(M\), \(N_B\), \(M^2\), \(N_\Gamma\), \(R\)]

Διακρίνω περιπτώσεις • \(N = N_A\): \(N \in (1, M) \quad N < M\) και \(N < M^2\) Ο Αλγ. 1 τρέχει πιο γρήγορα

• \(N = N_\Gamma\): \(N \in [M^2, +\infty) \quad N > M\) και \(N > M^2\) Ο Αλγ 2 τρέχει πιο γρήγορα.

• \(N = N_B\): \(N \in [M, M^2) \quad N > M\) και \(N < M^2\) Ο αλγ 1 τρέχει σε \(M\) βήματα Ο αλγ 2 τρέχει σε \(\frac{M^{2.5}}{N}\) βήματα \(\frac{M}{\frac{M^{2.5}}{N}} > 1 \Rightarrow M > \frac{M^{2.5}}{N} \Rightarrow M^{1.5} < N\) » Αν \(N > M^{1.5}\) τότε τρέχει πιο γρήγορα ο αλγ. 2 » Αν \(N < M^{1.5}\) -- || -- 1 » Αν \(N = M^{1.5}\) τότε τρέχουν το ίδιο.

Τελικά: • Αν \(N < M^{1.5}\) Ο Αλγ. 1 τρέχει πιο γρήγορα • Αν \(N > M^{1.5}\) Ο Αλγ 2 τρέχει πιο γρήγορα.

(1)

PXL_20260129_1659197192.jpg

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

[2] Η Φάση 1 ολοκληρώνεται το πολύ σε \(\underline{2N-1}\) βήματα

[3] Η Φάση 2 - χωρίς τη χρήση επιπλέον υλικού - απαιτεί στην καλ. περ. \(\underline{N}\) επιπ. βήματα

[4] Επιτάχυνση (speed-up) = \(S = \frac{\Gamma}{T} = \frac{N \log N}{3N-1} = O(\log N)\)

[5] Έργο (work) = \(W = T \cdot P = (3N-1)N = O(N^2)\)

[6] Αποδοτικότητα (efficiency) = \(E = \frac{\Gamma}{W} = \frac{\Gamma}{P \cdot T} = \frac{S}{P} \quad E = \frac{O(N \log N)}{O(N^2)} \Rightarrow E = O(\frac{\log N}{N})\)

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

[Σχήμα: 5 συνδεδεμένα ορθογώνια μπλοκ επεξεργασίας / ταξινόμησης]

Με τον αλγ. αυτό, για την ταξινόμηση \(\underset{N}{128}\) αριθμών των \(\underset{k}{16\text{ bit}}\) ο καθένας χρειάζονται:

[7] \(2 \cdot 128 - 1 = \underline{255}\) word-βήματα \(\Big\} \text{μόνο για την φάση 1.}\)

[8] \(255 \cdot 2 \log 16 = 6 \cdot 255\text{ bit-βήματα}\)

[9] Πόσα φύλλα έχει ένα πλήρες τριαδικό δένδρο με 514 κορυφές; \(m = 3\), \(n = 514\), \(i = \# \text{εσ. κορ.}\), \(l = \# \text{φύλλων}\).

\(\left. \begin{array}{l} n = 3 \cdot i + 1 \\ n = l + i \end{array} \right\} \begin{array}{l} n = 3i + 1 \\ i = n - l \end{array} \Big\} n = 3(n-l) + 1 \Leftrightarrow n = 3n - 3l + 1 \Rightarrow 3l = 2n + 1 \Rightarrow l = \frac{2n+1}{3} \Rightarrow l = \frac{2 \cdot 514 + 1}{3} = \frac{1029}{3} \Rightarrow \underline{l = 343}\)

[10] Στο γράφημα του σχήματος, το (ελάχιστο) εύρος διχοτόμησης είναι \(\text{τιμή} = \underline{4}\) \(\hookrightarrow \text{ελ. αριθμός ακμών που πρέπει να αφαιρέσουμε από το } G\text{, ώστε να χωριστεί στη μέση}\)

[Σχήμα: κύβος 8 κορυφών με 4 κυκλωμένες κορυφές]

[11] Ποιά είναι η διάμετρος του γραφήματος; \(\text{διάμετρος} = \underline{8} \rightarrow \text{μέγιστη απόσταση μεταξύ οποιωνδήποτε 2 κόμβων}\)

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

(2)

PXL_20260129_1659294562.jpg

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

[12] Η ταξινόμηση ολοκληρώνεται μετά από \(3N+k-4 = 3 \cdot 4 + 4 - 4 = \underline{12}\) βήματα

[13] Αν επιθυμούμε να αθροίσουμε 512 δυαδικούς αριθμούς μεγέθους 512 bits ο καθένας σε γραμμικό πλέγμα, το γραμμικό πλέγμα πρέπει να περιέχει τουλάχιστον \(\underline{521}\) επεξεργαστές. Αν πάρουμε χειρότερη περίπτωση, όλοι άσσοι, το μέγιστο άθρ που προκύπτει \(= 512 \cdot (2^{512} - 1) \approx 2^9 \cdot 2^{512} = 2^{521}\)

[14] Εκτελείται ο αλγ. Carry-Lookahead για την άθροιση δυο αριθμών N bits ο καθένας. Η τιμή στη δεξιότερη θέση στην s-p-g ακολουθία στα φύλλα του δένδρου που χρησιμοποιείται για την πρόβλεψη κρατουμένου είναι: \(\underline{\text{s}}\)

[15] Ποιες είναι οι τιμές στις θέσεις (a) και (b) στην ακ. κρατ. με δεδομένη την παρακάτω s-p-g ακολουθία

SPG	\(x_{16}\)	\(x_{15}\)	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
s-p-g	s		p	p		p	s	g	p	p	s		p	p	p	s
carry				(a)				(b)

\(\text{carry}(b) = 0\) \(\text{carry}(a) = \text{carry}(x_{12})\)

[16] Υπολογίζουμε παράλληλα τη συνέλιξη δυο διαν. \(\vec{a}, \vec{b}\) των N bits μέσω της σχέση \(y_k = \sum_{i+j = k+1} a_i b_j\) και παίρνουμε \(\vec{y} = (y_{2n-1}, \ldots, y_1)\). Για τον παράλληλο υπολ. της συνέλιξης δυο 256 bit διαν. το καθένα, απαιτούνται πλέγμα με \(\underline{2N = 512}\) επεξ. και \(\underline{3N-1 = 767}\) βήματα

[17] α) Υποδείξτε δεξιά στο σχήμα την τοποθέτηση των δεδομένων για τον παράλληλο υπολ. του γιν. διανύσματος x με 4 στοιχεία \([x_1, x_2, x_3, x_4]\) και του πίνακα \(A\) \(4 \times 4\) με χρήση δακτυλίου με 4 επεξ.

\(a_{11} \quad a_{12} \quad a_{13} \quad a_{14}\) \(a_{21}\) \(a_{31}\) \(a_{41} \qquad \qquad a_{44}\)

[Σχήμα: δακτύλιος 4 επεξεργαστών με κυκλική μεταφορά στοιχείων διανύσματος \(\vec{x}\) και εισόδους στηλών του πίνακα \(A\)]

β) Πόσα βήματα απαιτούνται για τον πολλ/σμο αυτόν; \(\underline{4}\)

PXL_20260129_1659345292.jpg

[18] Σε έναν αλγ. ταξ. που είναι oblivious και χρησιμοποιεί μόνο συγκρίσεις και μεταθέσεις δίνεται η είσοδος 5, 3, 1, 4, 20 και η εσφ. έξοδος του αλγ είναι 1, 2, 4, 3, 5. Με βάση το 0-1 Λήμμα, σε ποια 0-1 ακ. αντιστοιχίζεται η έξ. του αλγ;

0 0 1 0 1

[19] Εκτελούμε τον (βέλτιστο) παραλ. αλγ. ταξ. Schnorr Shamir σε πλέγμα 64x64. Αριθμ. τις στήλες του πλέγματος από αριστερά προς τα δεξιά με τους αριθμ. 0 έως 63. Τα δεδομένα της στήλης 27 μεταφέρονται στη στήλη \(\underline{29}\) μετά το "άνω κάτω" (unshuffle) κατά τη 2η φάση του αλγ.

\(27: \quad 1\; 1\; 0\; 1\; 1\)
\(x_5\; x_4\; x_3\; x_2\; x_1\)
\(1\; 1\; 1\; 0\; 1 = 29\)

[20] Εφαρμόζουμε την τεχνική για τον υπολογισμό κάτω φράγματος για snakelike ταξινόμηση σε πλέγμα. Έχουμε πλέγμα με 256 στοιχεία. Η αρίθμηση γραμμών και στηλών ξεκινάει από την τιμή 1. Πόσες τιμές στο "τρίγωνο" πρέπει να είναι 0, ώστε η τιμή 183 να πάει στη στήλη 1; α) \(\underline{9}\) ή β) \(\underline{10}\)

[Σχήμα: τετράγωνο πλέγμα \(\sqrt{N} \times \sqrt{N}\) με αποκομμένο τρίγωνο πάνω αριστερά διαστάσεων \(2 N^{\frac{1}{4}} \times 2 N^{\frac{1}{4}}\)]

\(\sqrt{N} = 16\)
\(N^{\frac{1}{4}} = 256^{\frac{1}{4}} = 4\)
\(2 N^{\frac{1}{4}} = 8\)
Το τριγωνάκι έχει \(\frac{(2 N^{\frac{1}{4}})(2 N^{\frac{1}{4}})}{2}\)
έχει 32 στοιχεία (0 και 256)

• Snakelike ταξ.
Περιττές γρ \((1, 3, \ldots) \leftarrow\)
Άρτιες \((2, 4, \ldots) \rightarrow\)
• Χωρίς την παρέμβαση του τριγώνου, η τιμή 183 θα καταλάμβανε την 183 θέση στην ταξινομημένη σειρά
• Ζητάμε η τιμή 183 να βρεθεί στη στήλη 1.
\(i \times 16\)
Γραμμή 12 (άρτια) \(12 \times 16 = 192\)
Γραμμή 13 (περιττή) \(12 \times 16 + 1 = 193\)

Νέα θέση = Αρχική \(+ k\)
\(183 + k =\) Στόχος

• Για να πάμε στη θέση 192: \(183 + k = 192 \Rightarrow \underline{k = 9}\)
• Για να πάμε στη θέση 193: \(\underline{k = 10}\)

[21]

[Σχήμα: Διμερές γράφημα με κόμβους αριστερά A, B, C, D και δεξιά 6, F, E. Ακμές: A-(F, E), B-(6, E), C-(6, F, E), D-F]

Δεν υπάρχει πλήρες ταίριασμα
γιατί \(|V|_G = 7\) περιττός αριθμός

Μη πλήρες:
B - 6
D - F
A - E

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

---

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