Παράλληλοι Αλγόριθμοι — Σεπτέμβριος 2024

Η μεταγραφή προέρχεται από τα 2024-09-08_162037.png, IMG_6567.jpg και 2024-09-11_12.55.43_.png.

2024-09-08_162037.png

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

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

τιμή = ________

[δυσανάγνωστο] σχήμα τις κορυφές που ανήκουν σε καθένα από τα 2 [δυσανάγνωστο]

[δυσανάγνωστο] αμέρισης από την οποία προκύπτει το εύρος [δυσανάγνωστο]

[δυσανάγνωστο] ς που υπολογίσατε

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

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

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

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

IMG_6567.jpg

Στο γράφημα του σχήματος υπάρχει ταίριασμα (matching) μεγέθους 4.

[Σχήμα: γράφημα με κορυφές v1–v8. Ακμές: v1–v2, v1–v6, v1–v7, v1–v8, v2–v5, v2–v6, v3–v5, v4–v5, v5–v6.]

• [ ] Σωστό
• [ ] Λάθος

Θέμα 11ο

Στο σχήμα φαίνεται πως υπολογίζεται παράλληλα το γινόμενο δύο πινάκω [κομμένο στο δεξί άκρο] πλέγματος 4x4. Πόσα βήματα απαιτούνται για τον παράλληλο πολλαπλασιασμό δ [κομμένο στο δεξί άκρο] χρήση πλέγματος NxN

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

2024-09-11_12.55.43_.png

Θέμα 12ο

Ποιο είναι το εύρος διχοτόμησης (bisection width) στο παρακάτω δίκτυο;

[Σχήμα: πλέγμα 3 γραμμών × 4 στηλών από πράσινα τετράγωνα (κόμβοι)· οι γειτονικοί κόμβοι ενώνονται οριζόντια και κάθετα· από κάθε γραμμή εξέρχεται γραμμή προς τα αριστερά]

Σημείωση: η φωτογραφία περιέχει απαντήσεις φοιτητή (πληκτρολογημένη απάντηση στο πεδίο απάντησης και γραμμή «Απάντηση»), που δεν μεταγράφηκαν.

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

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

Προσοχή

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

AI λύσεις — 2024-09

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

Θέμα 5

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

Στην εικόνα 2024-09-08_162037.png (και καθαρότερα στο ίδιο θέμα στο 476572177_1295832211520319_1887642575773979373_n.jpg), δίνεται ένα δένδρο με κορυφές αποτελούμενες από τετράγωνα και κύκλους.

Ανάλυση δομής του γραφήματος: - Στην κορυφή υπάρχει μία στήλη από 2 τετράγωνους κόμβους (ρίζα \(s_1\) συνδεδεμένη με τον \(s_2\)). - Ο κόμβος \(s_2\) διακλαδίζεται σε 2 κυκλικούς κόμβους (\(c_1\) αριστερά και \(c_2\) δεξιά). - Κάθε κυκλικός κόμβος διακλαδίζεται σε 2 αλυσίδες των 3 τετραγώνων έκαστη: - Αριστερό υποδένδρο (ρίζας \(c_1\)): \(1\) κύκλος + \(2 \times 3 = 6\) τετράγωνα = \(7\) κορυφές. - Δεξί υποδένδρο (ρίζας \(c_2\)): \(1\) κύκλος + \(2 \times 3 = 6\) τετράγωνα = \(7\) κορυφές. - Συνολικό πλήθος κορυφών του γραφήματος: \(|V| = 2 \text{ (κορυφής)} + 7 \text{ (αριστερά)} + 7 \text{ (δεξιά)} = 16\) κορυφές (και \(|E| = 15\) ακμές, συνεκτικό δένδρο).

Υπολογισμός Εύρους Διχοτόμησης (Bisection Width): Το εύρος διχοτόμησης είναι ο ελάχιστος αριθμός ακμών που πρέπει να αφαιρεθούν ώστε το γράφημα να χωριστεί σε δύο ισοπληθή σύνολα κορυφών \(|V_1| = |V_2| = 16/2 = 8\).

1. Μπορεί να επιτευχθεί με αφαίρεση 1 ακμής; Όχι. Σε ένα δένδρο η αφαίρεση οποιασδήποτε μίας ακμής χωρίζει το δένδρο σε δύο υποδένδρα. Τα δυνατά μεγέθη υποδένδρων που προκύπτουν από την αφαίρεση οποιασδήποτε ακμής είναι:
2. Αφαίρεση \((s_1, s_2) \implies\) μεγέθη \(1\) και \(15\).
3. Αφαίρεση \((s_2, c_1)\) ή \((s_2, c_2) \implies\) μεγέθη \(7\) και \(9\).
4. Αφαίρεση ακμής προς αλυσίδα 3 κόμβων \(\implies\) μεγέθη \(3\) και \(13\).

5. Αφαίρεση εσωτερικών ακμών αλυσίδας \(\implies\) μεγέθη \(2\) και \(14\), ή \(1\) και \(15\). Κανένα υποδένδρο δεν έχει ακριβώς 8 κορυφές. Άρα το εύρος διχοτόμησης είναι αυστηρά \(> 1\).

6. Επίτευξη με 2 ακμές: Αφαιρώντας τις \(2\) ακμές:

7. την ακμή \((s_1, s_2)\)
8. την ακμή \((s_2, c_1)\) Ορίζουμε:
9. Σύνολο 1: \(\{s_1\} \cup \text{Υποδένδρο}(c_1)\), με μέγεθος \(1 + 7 = 8\) κορυφές.
10. Σύνολο 2: \(\{s_2\} \cup \text{Υποδένδρο}(c_2)\), με μέγεθος \(1 + 7 = 8\) κορυφές. Οι μόνες ακμές που συνδέουν το Σύνολο 1 με το Σύνολο 2 είναι η \((s_1, s_2)\) και η \((s_2, c_1)\), δηλαδή ακριβώς 2 ακμές. (Αντίστοιχα, αν θεωρηθούν ως επεξεργαστές μόνο τα 14 τετράγωνα, η διαμέριση \(7-7\) επιτυγχάνεται πάλι κόβοντας τις ίδιες 2 ακμές: \(1+6=7\) τετράγωνα σε κάθε πλευρά).

Συνεπώς, το ελάχιστο εύρος διχοτόμησης είναι 2.

Τιμή = 2 (Διαμέριση: Σκιασμένες οι κορυφές \(\{s_1\}\) και όλες οι \(7\) κορυφές του αριστερού υποδένδρου κάτω από το \(c_1\) συμπεριλαμβανομένου του \(c_1\), μη σκιασμένες οι υπόλοιπες 8).

Θέμα (matching, IMG_6567)

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Λάθος. Για matching μεγέθους 4 σε 8 κορυφές θα έπρεπε να καλυφθούν όλες οι κορυφές, άρα και οι \(v_3,v_4\). Όμως και οι δύο έχουν μοναδικό γείτονα το \(v_5\), οπότε δεν μπορούν να ταιριαστούν και οι δύο· το μέγιστο matching έχει μέγεθος 3.

Θέμα 11ο

Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: μέτρια

Με τον τυπικό κυματοειδή (systolic) αλγόριθμο σε πλέγμα \(N\times N\), η τελευταία πράξη ολοκληρώνεται στο βήμα \(3N-3\) (με πρώτο βήμα 0), άρα απαιτούνται \(3N-2\) βήματα. Για \(N=4\): \(3\cdot4-2=10\) βήματα.

Θέμα 12ο

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια

Για το πλέγμα \(3\times4\) (υποθέτοντας ότι οι γραμμές αριστερά δεν είναι επιπλέον ακμές προς άγνωστους κόμβους), χωρίζουμε τις 4 στήλες σε \(2+2\): οι στήλες 1–2 εναντίον των 3–4 δίνουν 6–6 κορυφές και κόβονται 3 οριζόντιες ακμές, μία ανά γραμμή. Το εύρος διχοτόμησης είναι \(3\).

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

---

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