Αλγοριθμικές Τεχνικές Επιστήμης Δεδομένων — Ιούνιος 2026¶
Μεταγραφή από τις φωτογραφίες 20260609_160810.jpg, 20260609_165452.jpg και 20260609_165522.jpg (χειρόγραφο θέμα, χωρίς εκτυπωμένη ημερομηνία).
20260609_160810.jpg¶
Θέμα 1) μη κατευθυνόμενο δίκτυο G
[Σχήμα: Μη κατευθυνόμενο γράφημα G με κόμβους A, B, C, D, E, F και ακμές (A,B), (A,C), (B,C), (C,E), (C,D), (D,E), (D,F), (E,F) [δυσανάγνωστο: η ακμή C–D ή C–E]]
Υπολογίστε ενδιαμεσότητα κάθε ακμής G, εφαρμόζοντας Girvan-Newman, και παρουσιάζοντας το αποτέλεσμα της εκτέλεσης του αλγορίθμου (δένδρο BFS με την ενδιαμεσότητα κάθε ακμής) από κάθε κορυφή του G
Θέμα 2) μη κατευθυνόμενο δίκτυο \(G=(V(G), E(G))\), κάθε ακμή \(e=(i,j)\) του \(E(G)\) έχει βάρος \(w_{ij}=1\)
[Σχήμα: Μη κατευθυνόμενο γράφημα G με κόμβους I, A, B, C, D, E, F, G, H, J και βάρη ακμών wij=1]
Μια αποκοπή του G είναι διαμέριση του \(V(G)\) σε δύο (ξένα) υποσύνολα \(S \subseteq V(G)\) και \(T=V(G)-S\). Να βρείτε την ελάχιστη κανονικοποιημένη αποκοπή του παραπάνω γραφήματος G.
Θέμα 3) 3 έγγραφα 7 λωρίδες
| \(C_1\) | \(C_2\) | \(C_3\) | |
|---|---|---|---|
| 1 | 1 | 1 | 0 |
| 2 | 0 | 1 | 1 |
| 3 | 1 | 0 | 1 |
| 4 | 1 | 1 | 0 |
| 5 | 1 | 1 | 0 |
| 6 | 0 | 0 | 1 |
| 7 | 1 | 1 | 0 |
Βρες υπογραφή κάθε εγγράφου με τυχαίο κατακερματισμό γραμμών: \(h_1(x) = x \bmod 7\), \(h_2(x) = (2x+1) \bmod 7\), \(h_3(x) = (4x+[δυσανάγνωστο]) \bmod 7\)
Να δείξετε αναλυτικά τα βήματα του υπολογισμού των υπογραφών Ομοιότητα Jaccard και ομοιότητα υπογραφών:
| 1-2 | 1-3 | 2-3 | |
|---|---|---|---|
| Υπογραφές | |||
| Έγγραφα |
Θέμα 4) σύμπαν των αντικειμένων \(U=\{1\dots 30\}\) και μια συλλογή καλαθιών που \(\forall b \in V=\{2,\dots,49,50\}\) \(B_b = \{ i \in U : b \bmod i = 0 \}\). Κάθε καλάθι περιλαμβάνει όλους τους θετικούς ακέραιους διαιρέτες του δείκτη του εκτός της μονάδας π.χ \(B_{12}=\{2,3,4,6,12\}\). Θεωρήστε επίσης ως κατώφλι στήριξης \(s > 6\) Βρείτε σύνολο συχνών αντικειμένων Βρείτε σύνολο υποψήφιων ζευγών αντικειμένων που θα εξετάσει ο APRIORI κατά το 2ο πέρασμα Βρείτε σύνολο των πραγματικά συχνών ζευγών αντικειμένων που τελικά θα εντοπίσει ο APRIORI Βρείτε σύνολο των συχνών k-συνόλων αντικειμένων για \(k \ge 3\) Βρείτε την εμπιστοσύνη όλων των κανόνων που προκύπτουν από την τριάδα \(\{2,3,6\}\) Υπόδειξη: Για κάθε \(A \subseteq U\) (δύο ή περισσότερων) θετικών ακέραιων αριθμών, ισχύει ότι όλοι οι ακέραιοι \(a \in A\) διαιρούν ακέραια τον θετικό αριθμό \(b \in V\) αν και μόνο αν το \(\text{ΕΚΠ}(A)\) τους, επίσης διαιρεί ακέραια τον \(b\). Π.χ οι 4, 6 διαιρούν ακέραια τον 24, αλλά δεν διαιρούν ακέραια τον \(18 \to \text{ΕΚΠ}(4,6)=12\)
20260609_165452.jpg¶
Θεωρήστε ένα σύμπαν 29 αντικειμένων \(U=\{2,3,4,\dots,28,29,30\}\) και μια συλλογή 49 καλαθιών που ορίζονται ως εξής: \(\forall b \in B=\{2,\dots,49,50\}, b_i=\{i \in U : b \bmod i = 0\}\). Με άλλα λόγια, κάθε καλάθι περιλαμβάνει όλους τους θετικούς ακέραιους διαιρέτες του δείκτη του, εκτός της μονάδας (που δεν είναι στο \(U\)). Π.χ. \(B_{12}=\{2,3,4,6,12\}\). Θεωρήστε επίσης ως κατώφλι στηρίγματος (απόλυτος αριθμός) το \(s=6\). Να υπολογιστούν τα εξής, εξηγώντας σύντομα τον συλλογισμό σας:
α) Το σύνολο των συχνών αντικειμένων β) Το σύνολο και (το πλήθος) των υποψήφιων ζευγών αντικειμένων που θα πρέπει να μετρήσει ο αλγόριθμος APRIORI κατά το 2ο πέρασμά του γ) Το σύνολο των πραγματικά συχνών ζευγών αντικειμένων που τελικά θα εντοπίσει ο APRIORI δ) Το σύνολο των συχνών k-συνόλων αντικειμένων για τιμές [συμπληρώθηκε από 20260609_160810.jpg: \(k \ge 3\)]
5) Έστω ότι, ως προς ένα σύμπαν αντικειμένων \(\Omega=\{0,1,2,3,4,5,6,7\}\), μας δίνονται οι εξής ροές δεδομένων: $\(S1 = \langle 6, 1, 7, 7, 1, 7, 7, 2, 1, 6, 5, 0, 6, 4, 5, 5 \rangle\)$ $\(S2 = \langle 5, 1, 5, 1, 5, 1, 5, 1, 5, 1, 5, 1, 5, 1 \rangle\)$
Στη συγκεκριμένη ροή, θα πρέπει να εκτελέσετε τον αλγόριθμο Flajolet-Martin (FM) που επιστρέφει μια εκτίμηση για το πλήθος των διαφορετικών στοιχείων. Θεωρήστε ότι ο αλγόριθμος FM χρησιμοποιεί τις εξής συναρτήσεις κατακερματισμού: - \(h_1(x) = (2x + 1) \bmod 32\) - \(h_2(x) = (3x + 7) \bmod 32\) - \(h_3(x) = 8x \bmod 32\)
Το αποτέλεσμα κάθε συνάρτησης κατακερματισμού δίνεται ως 5ψήφια δυαδική συμβολοσειρά.
α) Να προσδιοριστεί το μήκος της "ουράς" καταληκτικών μηδενικών στις δυαδικές αναπαραστάσεις των τιμών κατακερματισμού που λαμβάνει υπόψη ο αλγόριθμος FM ανά συνάρτηση κατακερματισμού για κάθε αντικείμενο, συμπληρώνοντας τον παρακάτω πίνακα.
20260609_165522.jpg¶
[Λείπει από τη φωτογραφία: η αρχή της ερώτησης για το SVM, πριν από την πρόταση που ακολουθεί]
Το υπερεπίπεδο τοποθετείται ακριβώς στη μέση μεταξύ των δύο κλάσεων.
Μητρώο με μήκος καταληκτικής ουράς για κάθε αντικείμενο του \(\Omega\)
| Hash Function | \(h_1\) Value \(h_1(a)\) | \(h_1\) Zeros Tail \(r(h_1(a))\) | -//- | -//- |
|---|---|---|---|---|
| Στοιχείο \(a_i\) | ||||
| 0 | ||||
| \(\vdots\) | ||||
| 7 |
β) Έστω ότι εκτελείται 3 φορές ο FM, χρησιμοποιώντας σε κάθε εκτέλεση και μια διαφορετική συνάρτηση κατακερματισμού από τις προαναφερθείσες συναρτήσεις \(h_1, h_2, h_3\). Για κάθε μία από τις δύο ροές S1, S2 να υπολογιστεί η εκτίμηση που θα επιστρέψει ο αλγόριθμος ανά συνάρτηση κατακερματισμού, συμπληρώνοντας τους πίνακες. Να δοθεί επίσης ο μέσος όρος και διάμεσος των εκτιμήσεων που επιστρέφονται συνδυάζοντας και τις 3 εκτιμήσεις που υπολογίσατε.
(Για S1 και S2 2 πίνακες)
| Hash Function | Για \(h_1\) | \(h_2\) | \(h_3\) | AVERAGE | MEDIAN |
|---|---|---|---|---|---|
| Τιμή FM \(2^R =\) |
Διαπιστώνετε κάποιο πρόβλημα προς κάποιες συναρτήσεις κατακερματισμού που θεώρησε ο FM; Αν έπρεπε να κάνετε χρήση μόνο μιας από αυτές για τον FM, μεταξύ συναρτήσεων κατακερματισμού της μορφής \(h(x) = (ax + b) \bmod 2^k\), τι θα προτείνατε ώστε η εκτίμηση του αλγορίθμου να είναι όσο πιο ακριβής γίνεται;
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2026-06¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: μέτρια
Υποθέτω ότι οι ακμές είναι ακριβώς: \(AB, AC, BC, CD, CE, DE, DF, EF\) (δηλαδή υπάρχουν και οι \(CD\) και \(CE\)). Χρησιμοποιώ Girvan–Newman για μη κατευθυνόμενο γράφημα· οι τιμές «πηγής» είναι πριν από τη διαίρεση με \(2\).
BFS επίπεδα ανά πηγή: - \(A:\ A\mid B,C\mid D,E\mid F\) - \(B:\ B\mid A,C\mid D,E\mid F\) - \(C:\ C\mid A,B,D,E\mid F\) - \(D:\ D\mid C,E,F\mid A,B\) - \(E:\ E\mid C,D,F\mid A,B\) - \(F:\ F\mid D,E\mid C\mid A,B\)
Συνεισφορές ενδιαμεσότητας από κάθε πηγή (σε ισομήκεις διαδρομές μοιράζεται εξίσου το βάρος):
| ακμή | \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) | άθροισμα | τελική ενδιαμεσότητα |
|---|---|---|---|---|---|---|---|---|
| \(AB\) | 1 | 1 | 0 | 0 | 0 | 0 | 2 | 1 |
| \(AC\) | 4 | 0 | 1 | 1 | 1 | 1 | 8 | 4 |
| \(BC\) | 0 | 4 | 1 | 1 | 1 | 1 | 8 | 4 |
| \(CD\) | 1.5 | 1.5 | 1.5 | 3 | 0 | 1.5 | 9 | 4.5 |
| \(CE\) | 1.5 | 1.5 | 1.5 | 0 | 3 | 1.5 | 9 | 4.5 |
| \(DE\) | 0 | 0 | 0 | 1 | 1 | 0 | 2 | 1 |
| \(DF\) | 0.5 | 0.5 | 0.5 | 1 | 0 | 2.5 | 5 | 2.5 |
| \(EF\) | 0.5 | 0.5 | 0.5 | 0 | 1 | 2.5 | 5 | 2.5 |
Άρα τελικές ενδιαμεσότητες ακμών: [ AB=1,\quad AC=4,\quad BC=4,\quad CD=4.5,\quad CE=4.5,\quad DE=1,\quad DF=2.5,\quad EF=2.5. ]
Θέμα 2¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Στην εικόνα 20260609_160810.jpg το μη κατευθυνόμενο γράφημα \(G = (V, E)\) με βάρη ακμών \(w_{ij} = 1\) διακρίνεται καθαρά:
- Κορυφές (10): \(V = \{I, A, B, C, D, E, F, G, H, J\}\).
- Ακμές (13):
- Υπογράφημα αριστερά: \((I, A), (A, B), (A, C), (B, C), (B, D), (C, D)\).
- Ακμές-γέφυρες μεταξύ των δύο συστάδων: \((D, F)\) και \((D, E)\).
- Υπογράφημα δεξιά: \((E, G), (F, G), (F, H), (G, H), (H, J)\).
- Βαθμοί κορυφών (\(d_v\)):
- \(d(I) = 1\)
- \(d(A) = 3\)
- \(d(B) = 3\)
- \(d(C) = 3\)
- \(d(D) = 4\) (συνδέεται με \(B, C, F, E\))
- \(d(E) = 2\) (συνδέεται με \(D, G\))
- \(d(F) = 3\) (συνδέεται με \(D, G, H\))
- \(d(G) = 3\) (συνδέεται με \(E, F, H\))
- \(d(H) = 3\) (συνδέεται με \(F, G, J\))
- \(d(J) = 1\)
- Συνολικός όγκος γραφήματος: \(\text{vol}(V) = \sum d_v = 2 \times 13 = 26\).
Υπολογισμός Ελάχιστης Κανονικοποιημένης Αποκοπής (Normalized Cut - NCut)¶
Ορισμός κατά Shi-Malik: $\(\text{NCut}(S, T) = \frac{\text{cut}(S, T)}{\text{vol}(S)} + \frac{\text{cut}(S, T)}{\text{vol}(T)}\)$ όπου \(T = V \setminus S\), \(\text{cut}(S, T)\) είναι το πλήθος των ακμών που διασχίζουν την αποκοπή, και \(\text{vol}(S) = \sum_{u \in S} d(u)\).
Εξετάζουμε τη φυσική διαμέριση του γραφήματος στις δύο συστάδες: $\(S = \{I, A, B, C, D\} \quad \text{και} \quad T = \{E, F, G, H, J\}\)$ - Ακμές αποκοπής: Οι μόνες ακμές που συνδέουν το \(S\) με το \(T\) είναι οι \((D, F)\) και \((D, E)\). Άρα \(\text{cut}(S, T) = 2\). - Όγκοι υποσυνόλων: - \(\text{vol}(S) = d(I) + d(A) + d(B) + d(C) + d(D) = 1 + 3 + 3 + 3 + 4 = 14\). - \(\text{vol}(T) = d(E) + d(F) + d(G) + d(H) + d(J) = 2 + 3 + 3 + 3 + 1 = 12\). - Υπολογισμός NCut: $\(\text{NCut}(S, T) = 2 \cdot \left(\frac{1}{14} + \frac{1}{12}\right) = 2 \cdot \left(\frac{6 + 7}{84}\right) = 2 \cdot \frac{13}{84} = \frac{13}{42} \approx 0.3095\)$
Έλεγχος εναλλακτικών υποψήφιων αποκοπών (επαληθεύτηκε εξαντλητικά με πρόγραμμα για όλες τις \(2^{10-1} - 1 = 511\) δυνατές αποκοπές): - Αποκοπή ακραίου κόμβου \(I\) (\(S = \{I\}\)): \(\text{cut} = 1, \; \text{vol}(S) = 1, \; \text{vol}(T) = 25 \implies \text{NCut} = 1 + \frac{1}{25} = 1.04\). - Αποκοπή ακραίου κόμβου \(J\) (\(S = \{J\}\)): \(\text{cut} = 1, \; \text{vol}(S) = 1, \; \text{vol}(T) = 25 \implies \text{NCut} = 1 + \frac{1}{25} = 1.04\). - Αποκοπή του \(D\) μαζί με τη δεξιά συστάδα (\(S = \{I, A, B, C\}\) και \(T = \{D, E, F, G, H, J\}\)): διακόπτονται οι 3 ακμές \((A, B)\) όχι αλλά \((B, D), (C, D) \implies \text{cut} = 2, \; \text{vol}(S) = 10, \; \text{vol}(T) = 16 \implies \text{NCut} = 2(1/10 + 1/16) = 0.325 > 0.3095\).
Επομένως, η ελάχιστη κανονικοποιημένη αποκοπή είναι η διαμέριση: $\(S = \{I, A, B, C, D\}, \quad T = \{E, F, G, H, J\} \quad \mu\varepsilon \quad \text{NCut} = \frac{13}{42} \approx 0.3095\)$
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Τα σύνολα γραμμών/αντικειμένων κάθε εγγράφου είναι: [ C_1={1,3,4,5,7},\quad C_2={1,2,4,5,7},\quad C_3={2,3,6}. ] Ομοιότητες Jaccard εγγράφων: [ J_{12}=\frac{|C_1\cap C_2|}{|C_1\cup C_2|}=\frac{4}{6}=\frac23, ] [ J_{13}=\frac{1}{7},\qquad J_{23}=\frac{1}{7}. ]
Για \(h_1(x)=x\bmod 7\): [ h_1(C_1)=0,\quad h_1(C_2)=0,\quad h_1(C_3)=2. ] Για \(h_2(x)=(2x+1)\bmod 7\): [ h_2(C_1)=0,\quad h_2(C_2)=1,\quad h_2(C_3)=0. ] Για \(h_3(x)=(4x+c)\bmod 7\), όπου \(c\) το δυσανάγνωστο ψηφίο, οι ελάχιστες τιμές για κάθε έγγραφο είναι:
| \(c\bmod 7\) | \(h_3(C_1)\) | \(h_3(C_2)\) | \(h_3(C_3)\) | \((s_{12},s_{13},s_{23})\) ομοιότητες υπογραφών |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | \((2/3,1/3,0)\) |
| 1 | 0 | 0 | 2 | \((2/3,1/3,0)\) |
| 2 | 0 | 1 | 0 | \((1/3,2/3,0)\) |
| 3 | 0 | 0 | 1 | \((2/3,1/3,0)\) |
| 4 | 1 | 1 | 0 | \((2/3,1/3,0)\) |
| 5 | 0 | 0 | 1 | \((2/3,1/3,0)\) |
| 6 | 1 | 0 | 0 | \((1/3,1/3,1/3)\) |
Αν π.χ. \(c=3\), τότε οι υπογραφές είναι: [ C_1=(0,0,0),\quad C_2=(0,1,0),\quad C_3=(2,0,1), ] και οι ομοιότητες υπογραφών είναι \((2/3,1/3,0)\) για τα ζεύγη \((1,2),(1,3),(2,3)\) αντίστοιχα.
Θέμα 4¶
Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: υψηλή
Το Θέμα 4 εμφανίζεται δύο φορές με διαφορετικά δεδομένα· δεν είναι ταυτόσημο. Και στις δύο περιπτώσεις η μονάδα εξαιρείται, όπως στο παράδειγμα \(B_{12}=\{2,3,4,6,12\}\). Χρησιμοποιώ το κριτήριο [ \operatorname{supp}(A) =#{b\in{2,\dots,50}: b\text{ διαιρείται από όλα τα }a\in A} =\left\lfloor\frac{50}{\operatorname{lcm}(A)}\right\rfloor . ]
Πρώτη εκδοχή (από 20260609_165452.jpg): \(U=\{2,\dots,30\}\), \(s=6\).
α) Συχνά αντικείμενα: [ F_1={2,3,4,5,6,7,8}, ] με στηρίξεις [ 25,16,12,10,8,7,6 ] αντίστοιχα.
β) Κατά το 2ο πέρασμα ο APRIORI εξετάζει όλα τα ζεύγη από το \(F_1\), άρα [ C_2=\binom{F_1}{2},\qquad |C_2|=\binom72=21. ] Είναι όλα τα ζεύγη \(\{i,j\}\) με \(2\le i<j\le 8\).
γ) Πραγματικά συχνά ζεύγη (με βάση το \(\operatorname{lcm}\)): [ F_2=\bigl{{2,3},{2,4},{2,6},{2,8},{3,6},{4,8}\bigr}. ] Οι στηρίξεις είναι αντίστοιχα [ 8,12,8,6,8,6. ]
δ) Συχνά \(k\)-σύνολα για \(k\ge3\): [ F_3=\bigl{{2,3,6},{2,4,8}\bigr}, ] με στηρίξεις \(8\) και \(6\) αντίστοιχα, και [ F_k=\varnothing\quad \text{για }k\ge4. ]
Από την τριάδα \(\{2,3,6\}\) (στήριξη \(8\)): [ \operatorname{supp}(2)=25,\quad \operatorname{supp}(3)=16,\quad \operatorname{supp}(6)=8, ] και [ \operatorname{supp}(2,3)=\operatorname{supp}(2,6)=\operatorname{supp}(3,6)=8. ] Άρα: [ \begin{array}{c|c} \text{Κανόνας} & \text{Εμπιστοσύνη}\\hline {2}\to{3,6} & \frac{8}{25}=0.32\ {3}\to{2,6} & \frac{8}{16}=0.50\ {6}\to{2,3} & \frac{8}{8}=1\ {2,3}\to{6} & \frac{8}{8}=1\ {2,6}\to{3} & \frac{8}{8}=1\ {3,6}\to{2} & \frac{8}{8}=1 \end{array} ]
Δεύτερη εκδοχή (η πρώτη διατύπωση, με \(s>6\)): λαμβάνω ακέραιο κατώφλι \(s=7\), δηλαδή στήριξη \(\ge7\).
α) [ F_1={2,3,4,5,6,7}. ] β) Όλα τα ζεύγη από το \(F_1\): [ C_2=\binom{F_1}{2},\qquad |C_2|=\binom62=15. ] γ) Πραγματικά συχνά ζεύγη: [ F_2=\bigl{{2,3},{2,4},{2,6},{3,6}\bigr}, ] με στηρίξεις \(8,12,8,8\) αντίστοιχα.
δ) [ F_3=\bigl{{2,3,6}\bigr},\qquad F_k=\varnothing\quad(k\ge4). ] Οι εμπιστοσύνες των κανόνων από την \(\{2,3,6\}\) είναι ακριβώς οι ίδιες με τον παραπάνω πίνακα, αφού οι στηρίξεις \(25,16,8,8\) δεν αλλάζουν.
Θέμα 5¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Λαμβάνω τη σύμβαση ότι για \(00000\) το μήκος καταληκτικών μηδενικών είναι \(r(00000)=5\).
Οι τιμές των συναρτήσεων κατακερματισμού και τα \(r\) φαίνονται στον πίνακα:
| \(a\) | \(h_1(a)=2a+1\) | \(r_1\) | \(h_2(a)=3a+7\) | \(r_2\) | \(h_3(a)=8a\) | \(r_3\) |
|---|---|---|---|---|---|---|
| 0 | \(1=00001\) | 0 | \(7=00111\) | 0 | \(0=00000\) | 5 |
| 1 | \(3=00011\) | 0 | \(10=01010\) | 1 | \(8=01000\) | 3 |
| 2 | \(5=00101\) | 0 | \(13=01101\) | 0 | \(16=10000\) | 4 |
| 3 | \(7=00111\) | 0 | \(16=10000\) | 4 | \(24=11000\) | 3 |
| 4 | \(9=01001\) | 0 | \(19=10011\) | 0 | \(0=00000\) | 5 |
| 5 | \(11=01011\) | 0 | \(22=10110\) | 1 | \(8=01000\) | 3 |
| 6 | \(13=01101\) | 0 | \(25=11001\) | 0 | \(16=10000\) | 4 |
| 7 | \(15=01111\) | 0 | \(28=11100\) | 2 | \(24=11000\) | 3 |
Για τη ροή \(S1\), τα διαφορετικά στοιχεία είναι [ {0,1,2,4,5,6,7}. ] Το μέγιστο \(R=\max r(h(a))\) και η εκτίμηση \(2^R\) είναι:
| \(S1\) | \(h_1\) | \(h_2\) | \(h_3\) | Average | Median |
|---|---|---|---|---|---|
| \(R\) | 0 | 2 | 5 | ||
| \(2^R\) | 1 | 4 | 32 | \(37/3\approx 12.33\) | 4 |
Για τη ροή \(S2\), τα διαφορετικά στοιχεία είναι [ {1,5}. ] Άρα:
| \(S2\) | \(h_1\) | \(h_2\) | \(h_3\) | Average | Median |
|---|---|---|---|---|---|
| \(R\) | 0 | 1 | 3 | ||
| \(2^R\) | 1 | 2 | 8 | \(11/3\approx 3.67\) | 2 |
Πρόβλημα: η \(h_1(x)=2x+1\bmod 32\) έχει άρτιο πολλαπλασιαστή \(a=2\), οπότε δίνει πάντα περιττές τιμές· εδώ μάλιστα δίνει \(r=0\) για όλα τα στοιχεία, άρα εκτίμηση \(1\). Η \(h_3(x)=8x\bmod 32\) έχει \(a=8\) άρτιο και εικόνα μόνο \(\{0,8,16,24\}\), με πολλές συγκρούσεις και μη ομοιόμορφη κατανομή. Η \(h_2(x)=3x+7\bmod 32\) έχει \(a=3\) περιττό, άρα είναι μεταθετική modulo \(32\) και είναι η καλύτερη από τις δοσμένες. Για ακριβέστερη εκτίμηση FM με συναρτήσεις \(h(x)=(ax+b)\bmod 2^k\) πρέπει \(a\) περιττός (άρα \(\gcd(a,2^k)=1\)) και \(b\) τυχαίο· από τις δοσμένες θα προτιμούσα την \(h_2\).
Θέμα SVM (αποσπασματικό από 20260609_165522.jpg)¶
Αξιοπιστία: δεν λύθηκε
Δεν λύθηκε: η μεταγραφή περιέχει μόνο τη φράση «Το υπερεπίπεδο τοποθετείται ακριβώς στη μέση μεταξύ των δύο κλάσεων» χωρίς πλήρη εκφώνηση, δεδομένα ή σχήμα για πρόβλημα SVM.