Ανάκτηση Πληροφορίας — Σεπτέμβριος 2020¶
Μεταγραφή των σελίδων 3–5 του αρχείου themata.pdf (Σεπτέμβριος 2020).
themata.pdf (σελ. 3-5)¶
ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ ΚΑΙ ΠΛΗΡΟΦΟΡΙΚΗΣ ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΑΣ ΑΝΑΚΤΗΣΗ ΠΛΗΡΟΦΟΡΙΑΣ ΕΞΕΤΑΣΕΙΣ ΣΕΠΤΕΜΒΡΙΟΥ 2020¶
Διδάσκων: [όνομα παραλείπεται] ΔΙΑΡΚΕΙΑ 1:30
ΘΕΜΑ 1 ( Μονάδες 3.5 )
α. Εξηγήστε πως τεχνικές του μοντέλου διανυσματικού χώρου, θα μπορούσαν να χρησιμοποιηθούν για να πραγματοποιήσουν τον εντοπισμό, σε μία συλλογή κειμένων, λέξεων που είναι παρόμοιες (συνώνυμες ή σχεδόν συνώνυμες) με βάση τον τρόπο χρήσης τους.
β. Μία μεταμηχανή αναζήτησης διαχειρίζεται ερωτήματα χρησιμοποιώντας άλλες μηχανές και συγχωνεύοντας (με κάποια πολιτική) τα αποτελέσματά τους. Έστω λοιπόν μία μεταμηχανή που για ένα ερώτημα ρωτάει k μηχανές αναζήτησης και συγχωνεύει τις λίστες αποτελεσμάτων τους. Παρουσιάστε κατάλληλες πολιτικές συγχώνευσης για την παραγωγή του τελικού αποτελέσματος, αξιοποιώντας και ύπαρξη συστάδων ανάμεσα στα κείμενα.
ΘΕΜΑ 2 ( Μονάδες 3.5 )
α. Θεωρώντας ότι ο αριθμός των επιστρεφόμενων κειμένων είναι 40, σχεδιάστε τα γραφήματα ανάκλησης ακρίβειας, για τα ακόλουθα ερωτήματα (δίνονται ο αριθμός των σχετικών κειμένων και η θέση τους στο αποτέλεσμα):
Αριθμός: 10, θέση: 1, 3, 4, 6, 7, 10, 15, 22, 30, 39
Αριθμός: 10, θέση: 1, 2, 4, 6, 8, 10, 12, 16, 21, 27.
Με βάση τα δύο προκύπτοντα γραφήματα συγκρίνετε μεταξύ τους τις δύο μηχανές.
β. Θεωρήστε ότι έχουμε μία συλλογή κειμένων και όρων που περιγράφεται από τον ακόλουθο πίνακα:
| Data | Algorithm | Graph | List | Tree | Pointer | Array | |
|---|---|---|---|---|---|---|---|
| Doc1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
| Doc2 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
| Doc3 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| Doc4 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| Doc5 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| Doc6 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| Doc7 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
Σχεδιάστε το ανεστραμμένο αρχείο το οποίο θα πρέπει να δημιουργηθεί για την αποθήκευση της πληροφορίας που δίνει ο συγκεκριμένος πίνακας. Χρησιμοποιείστε το ανεστραμμένο αρχείο που έχετε δημιουργήσει για να απαντησετε στο ερώτημα: “εντόπισε τα κείμενα που περιέχουν τους όρους Data και Graph.”
ΘΕΜΑ 3 ( Μονάδες 3)¶
Στην πολυγλωσσική ανάκτηση πληροφορίας επιδιώκεται η ανάκτηση κειμένων σε πολυγλωσσικές συλλογές με τη δυνατότητα οι ερωτήσεις να γίνονται σε περισσότερες της μίας γλώσσες. Προτείνετε τρόπους επέκτασης των κλασσικών μοντέλων και τεχνικών δεικτοδότησης για την υλοποίηση ενός πολυγλωσσικού συστήματος ανάκτησης.
ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ ΚΑΙ ΠΛΗΡΟΦΟΡΙΚΗΣ ΑΝΑΚΤΗΣΗ ΠΛΗΡΟΦΟΡΙΑΣ ΕΞΕΤΑΣΕΙΣ ΣΕΠΤΕΜΒΡΙΟΥ 2020 Διδάσκων: [όνομα παραλείπεται] ΔΙΑΡΚΕΙΑ 1:30¶
ΘΕΜΑ 1 (Μονάδες 3.5)
α Στην πολυγλωσσική ανάκτηση πληροφορίας, επιδιώκεται η ανάκτηση κειμένων σε μία πολυγλωσσική συλλογή, με τη δυνατότητα οι ερωτήσεις να γίνονται σε περισσότερες της μίας διαφορετικές γλώσσες. Προτείνετε τρόπους επέκτασης των κλασσικών μοντέλων, για την υλοποίηση ενός πολυγλωσσικού συστήματος.
β. Εξηγήστε πως τεχνικές του μοντέλου διανυσματικού χώρου, θα μπορούσαν να χρησιμοποιηθούν για να πραγματοποιήσουν τον εντοπισμό, σε μία συλλογή κειμένων, λέξεων που είναι παρόμοιες (συνώνυμες ή σχεδόν συνώνυμες) με βάση τον τρόπο χρήσης τους.
γ. Θεωρώντας ότι ο αριθμός των επιστρεφόμενων κειμένων είναι 30, σχεδιάστε τα γραφήματα ανάκλησης ακρίβειας, για τα ακόλουθα ερωτήματα (δίνονται ο αριθμός των σχετικών κειμένων και η θέση τους στο αποτέλεσμα) :
Μηχανή1 Αριθμός: 10, Θέση: 1, 2, 3, 8, 12, 16, 19, 24, 27, 30
Μηχανή2 Αριθμός: 10, Θέση: 1, 3, 6, 7, 8, 11, 12, 13, 17, 28.
Με βάση τα δύο προκύπτοντα γραφήματα συγκρίνετε μεταξύ τους τις δύο μηχανές.
ΘΕΜΑ 2 ( Μονάδες 3.5 )
α) Εξηγήστε πως μία δομή ανεστραμμένων αρχείων θα μπορούσε να διαχειριστεί δυναμικές πράξεις ένθεσης και/ή διαγραφής και προσδιορίστε τα προβλήματα που ενδεχομένως ανακύπτουν σε μία προσπάθεια δυναμοποίησης.
β) Λόγω του μεγάλου όγκου δεδομένων που έχουν να χειριστούν οι μηχανές ψαξίματος στον παγκόσμιο ιστό, συχνά διατηρούν δύο ανεστραμμένα αρχεία, ένα που περιέχει πληροφορία για όλα τα κείμενα και αποθηκεύεται στο δίσκο και ένα μικρότερου μεγέθους που περιέχει ένα υποσύνολο της συνολικής πληροφορίας και αποθηκεύεται στην κύρια μνήμη. Τα δύο αυτά ανεστραμμένα αρχεία λειτουργούν με τη λογική ότι σε δοθέν ερώτημα, πρώτα θα ερωτηθεί η δομή στην κύρια μνήμη και αν η απάντηση δεν είναι ικανοποιητική θα ερωτηθεί και η δομή στον δίσκο. Προτείνετε πολιτικές δημιουργίας και ενημέρωσης της δομής ανεστραμμένων αρχείων της κύριας μνήμης, υποθέτοντας ότι η μηχανή ακολουθεί ένα συνδυασμό μοντέλου διανυσματικού χώρου, και μίας link μετρικής (ανεξάρτητης περιεχομένου), στη βαθμολόγηση των ιστοσελίδων.
ΘΕΜΑ 3 ( Μονάδες 3)
Θεωρήστε τον ακόλουθο πίνακα κειμένων-όρων με 6 κείμενα και 3 όρους (t1 ως t3) που περιέχουν συχνότητες εμφανίσεων όρων, καθώς και το ερώτημα q , με τα επιδεικνυόμενα βάρη όρων.
| t1 | t2 | t3 | |
|---|---|---|---|
| d1 | 2 | 1 | 2 |
| d2 | 0 | 3 | 1 |
| d3 | 1 | 1 | 1 |
| d4 | 0 | 2 | 1 |
| d5 | 2 | 0 | 0 |
| d6 | 1 | 2 | 2 |
| q | 1 | 2 | 1 |
α) Μετατρέψτε κάθε διάνυσμα στο αντίστοιχο της tf-idf μετρικής και υπολογίστε τη διάταξη των κειμένων χρησιμοποιώντας τη μετρική συνημιτόνου του μοντέλου διανυσματικού χώρου.
β) Εξηγήστε πως το Boolean Model θα μπορούσε να απαντήσει σε καθένα από τα επόμενα ερωτήματα:
-- t1 OR t2
-- t2 AND t3
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2020-09.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):anaktisiphoto1.PNG,84090f953a8b230a8e6a2b4805c0dc46.png,retrieve.PNG,20210130_142707.jpg,20210130_142743.jpg,20210130_142825.jpg,20210130_142833.jpg,20210130_142839.jpg,20210130_142855.jpg,20210130_155245.jpg,20210130_155326.jpg
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: χειρόγραφες λύσεις φοιτητή σε φωτογραφίες (πηγή δεν ορίζεται)
Προσοχή
Οι δύο παραλλαγές του Σεπτεμβρίου 2020 δεν έχουν διαχωριστεί στο αρχείο συνεδρίας· οι λύσεις του Θέματος 3 (tf-idf) αντιστοιχούν στη δεύτερη παραλλαγή (σελ. 4–5). 20210130_142707: η ανάλυση χρησιμοποιεί N = 9 (d1–d9)· ο πίνακας της παραλλαγής έχει 6 κείμενα (N = 6). Το idf_1 = log(9/4) = 0,33 δεν συμφωνεί με το log(6/4) = 0,176 που χρησιμοποιεί η λύση 20210130_142825. 20210130_142855: Sim(d4, q) = 0,00868 / (0,08064 · 0,1653) ≈ 0,651 και όχι 0,5924 όπως γράφεται· η κατάταξη {d3, d1, d6, d5, d4, d2} δεν αλλάζει, αφού το d4 μένει πέμπτο. 20210130_142839: τα w_{2,9} και w_{3,9} γράφονται 0,0796 και 0,0597· με log(6/5) = 0,0792 προκύπτουν 0,0792 και 0,0594 (διαφορά στρογγύλευσης). Δεν υπάρχει λύση στις φωτογραφίες για το Θέμα 1, για το Θέμα 2 α (ανάκληση–ακρίβεια, πολιτικές συγχώνευσης), για το πολυγλωσσικό ερώτημα του Θέματος 3 της παραλλαγής 1 ή για το Boolean ερώτημα της παραλλαγής 2. Το Scan-converted.pdf (βλ. 2020-06.solutions.md) περιέχει επίσης μερική λύση tf-idf του Σεπτεμβρίου 2020 με N = 6.
Λύσεις — Ανάκτηση Πληροφορίας — Σεπτέμβριος 2020¶
Χειρόγραφες λύσεις φοιτητή, μεταγραφή από φωτογραφίες. Δεν είναι επίσημες. Το Θέμα 2 β αφορά την παραλλαγή με τον πίνακα Data/Graph (σελ. 3) και το Θέμα 3 (tf-idf) την παραλλαγή με τον πίνακα t1–t3 (σελ. 4–5).
20210130_142707.jpg¶
[Σχήμα: κόκκινο πλαίσιο πάνω δεξιά με κείμενο "Άσκηση tf-idf" / "Σεπτέμβριος 2020" / "Μεθοδολογία" (εν μέρει επικαλυμμένο: [δυσανάγνωστο]) "+ Επίλυση"]
1) Βρίσκω
[Σχήμα: σημειώσεις περιθωρίου με βέλη: "αριθμός εμφάνισης του i-όρου στο j-κείμενο" προς \(\text{freq}_{ij}\)· "μέγιστη συχνότητα εμφάνισης" προς \(\max \text{freq}_{ij}\)· "όρος" προς τον δείκτη i· "κείμενο" προς τον δείκτη j]
2) Υπολογίζω \(\text{idf}_i\) για το i-οστό όρο
[Σχήμα: σημειώσεις περιθωρίου με βέλη: "συνολικός αριθμός κειμένων συλλογής (\(d_1 - d_9\))" προς \(N\)· "ο αριθμός των κειμένων στα οποία να εμφανίζεται ο όρος \(t_1\)" προς \(n_1\)]
3) Υπολογίζω βάρος i-όρου στο κείμενο j
4) Υπολογίζω διάνυσμα
20210130_142743.jpg¶
5) Υπολογίζουμε διάνυσμα \(\bar{q} = (w_{1,q}, w_{2,q}, w_{3,q}, \ldots, w_{t,q})\) που δείχνει τα βάρη των όρων [δυσανάγνωστο]
6) Χρησιμοποιούμε μετρική συνημιτόνου για τον υπολογισμό [δυσανάγνωστο] του κειμένου \(d_j\) [διαγραμμένη λέξη] στο ερώτημα \(q\)
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
20210130_142825.jpg¶
Βήμα ①
Πίνακας \(f_{ij}\) (γραμμές: έγγραφα \(d_1\)–\(d_6\); στήλες: όροι \(f_1\), \(f_2\), \(f_3\))
| \(f_1\) | \(f_2\) | \(f_3\) | |
|---|---|---|---|
| \(d_1\) | 2 | 1 | 2 |
| \(d_2\) | 0 | 3 | 1 |
| \(d_3\) | 1 | 1 | 1 |
| \(d_4\) | 0 | 2 | 1 |
| \(d_5\) | 2 | 0 | 0 |
| \(d_6\) | 1 | 2 | 2 |
Βήμα ②
Πίνακας \(f_{ij}\): \(f_{ij} / \max_j f_{ij}\)
| \(d_1\) | \(d_2\) | \(d_3\) | \(d_4\) | \(d_5\) | \(d_6\) | |
|---|---|---|---|---|---|---|
| \(f_{1j}\) | 1 | 0 | 1 | 0 | 1 | 0,5 |
| \(f_{2j}\) | 0,5 | 1 | 1 | 1 | 0 | 1 |
| \(f_{3j}\) | 1 | 0,33 | 1 | 0,5 | 0 | 1 |
Βήμα ③
Πίνακας \(idf_i\), \(i = 1, \dots, 3\):
\(idf_1 = \log_{10} \dfrac{N}{n_1} = \log_{10} \dfrac{6}{4} = 0{,}176\)
\(idf_2 = \log_{10} \dfrac{N}{n_2} = \log_{10} \dfrac{6}{5} = 0{,}0792\)
\(idf_3 = \log_{10} \dfrac{N}{n_3} = \log_{10} \dfrac{6}{5} = 0{,}0792\)
Βήμα ④
[διαγραμμένη γραμμή: \(\bar{d}_1 = (w_{11}, w_{12}, w_{13})\)]
όπου \(w_{ij} = f_{ij} \cdot \log \dfrac{N}{n_i}\)
Άρα
\(w_{11} = f_{11} \cdot \log_{10} \dfrac{N}{n_1} = 1 \cdot 0{,}176 = 0{,}176\)
\(w_{21} = f_{21} \cdot \log_{10} \dfrac{N}{n_2} = 0{,}5 \cdot 0{,}0796 = 0{,}0398\)
\(w_{31} = f_{31} \cdot \log_{10} \dfrac{N}{n_3} = 1 \cdot 0{,}0796 = 0{,}0796\)
Άρα
20210130_142833.jpg¶
Σημείωση: η φωτογραφία είναι χειρόγραφη, περιέχει μόνο λύση (χωρίς τυπωμένα ερωτήματα) και είναι τραβηγμένη περιστρεμμένη κατά 90 μοίρες. Ορισμένα ψηφία είναι δυσανάγνωστα. Στο επάνω δεξιό μέρος φαίνεται ένδειξη «Σελίδα 1 από 3» σε άλλο φύλλο που βρίσκεται κάτω από το χειρόγραφο.
\(\bar{d}_2 = (w_{1,2},\ w_{2,2},\ w_{3,2})\)
\(= \left(f_{12}\log\frac{N}{n_1},\ f_{22}\log\frac{N}{n_2},\ f_{32}\log\frac{N}{n_3}\right)\)
\(= (0 \cdot 0{,}176 [\text{δυσανάγνωστο}],\ 1 \cdot 0{,}0792,\ 0{,}33 \cdot 0{,}0792)\)
\(\bar{d}_2 = (0,\ 0{,}0792,\ 0{,}026136)\)
\(\bar{d}_3 = (w_{1,3},\ w_{2,3},\ w_{3,3})\)
\(= \left(f_{13}\log\frac{N}{n_1},\ f_{23}\log\frac{N}{n_2},\ f_{33}\log\frac{N}{n_3}\right)\)
\(= (1 \cdot 0{,}176,\ 1 \cdot 0{,}0792,\ 1 \cdot 0{,}0792)\)
\(\bar{d}_3 = (0{,}176,\ 0{,}0792,\ 0{,}0792)\)
\(\bar{d}_4 = (w_{1,4},\ w_{2,4},\ w_{3,4})\)
\(= \left(f_{14}\log\frac{N}{n_1},\ f_{24}\log\frac{N}{n_2},\ f_{34}\log\frac{N}{n_3}\right)\)
\(= (0,\ 1 \cdot 0{,}0792,\ 0{,}5 \cdot 0{,}0792)\)
\(\bar{d}_4 = (0,\ 0{,}0792,\ 0{,}0398)\)
20210130_142839.jpg¶
\(\bar d_5 = (w_{1,5},\ w_{2,5},\ w_{3,5})\)
\(= \left(f_{1,5}\log\frac{N}{n_1},\ 0,\ 0\right)\)
[χειρόγραφη σημείωση με βέλος από το τελευταίο μέρος της γραμμής: άρα \(f_{25},\ f_{35} = 0\)]
[πλαισιωμένο] \(\bar d_5 = (0{,}176,\ 0,\ 0)\)
\(\bar d_6 = (w_{1,6},\ w_{2,6},\ w_{3,6})\)
\(= \left(f_{1,6}\log\frac{N}{n_1},\ f_{2,6}\log\frac{N}{n_2},\ f_{3,6}\log\frac{N}{n_3}\right)\)
\(= (0{,}5 \cdot 0{,}176,\ 1 \cdot 0{,}0796,\ 1 \cdot 0{,}0796)\)
[πλαισιωμένο] \(\bar d_6 = (0{,}088,\ 0{,}0796,\ 0{,}0796)\)
Βήμα 5
\(\bar q = (w_{1,9},\ w_{2,9},\ w_{3,9})\) από πίνακα \(f_{ij}\) στο [Βήμα 2]
\(w_{i,9} = \left(0{,}5 + 0{,}5 \cdot \frac{\mathrm{freq}_{i,9}}{\max\mathrm{freq}_{i,9}}\right) \cdot \log\frac{N}{n_i}\)
[χειρόγραφο σημάδι ✓ δίπλα στον τύπο]
\(w_{1,9} = \left(0{,}5 + 0{,}5 \cdot \frac{0{,}5}{1}\right) \cdot \log\frac{6}{4} = \left(0{,}5 + [\text{διαγραμμένο, δυσανάγνωστο}]\,/\,0{,}23\right) \cdot 0{,}176 =\)
\(\Rightarrow\) [πλαισιωμένο] \(w_{1,9} = 0{,}132\)
\(w_{2,9} = \left(0{,}5 + 0{,}5 \cdot \frac{1}{1}\right) \cdot \log_{10}\frac{6}{5} = 1 \cdot 0{,}0796 \Rightarrow\) [πλαισιωμένο] \(w_{2,9} = 0{,}0796\)
\(w_{3,9} = \left(0{,}5 + 0{,}5 \cdot \frac{0{,}5}{1}\right) \cdot \log_{10}\frac{6}{5} = 0{,}75 \cdot 0{,}0796 \Rightarrow\) [πλαισιωμένο] \(w_{3,9} = 0{,}0597\)
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
20210130_142855.jpg¶
[Σχήμα: χειρόγραφη λύση σε φωτογραφία περιστρεμμένη κατά 90 μοίρες. Έξι υπολογισμοί ομοιότητας Sim(d̄ᵢ, q̄), καθένας με πλαίσιο γύρω από το τελικό αποτέλεσμα και αριθμό κατάταξης δίπλα του (1 έως 6).]
- \(\text{Sim}(\bar d_1,\bar q)=\dfrac{0,031522}{0,1972\cdot 0,1653}\Rightarrow \text{Sim}(\bar d_1,\bar q)=0,967\) [δίπλα: 2]
- \(\text{Sim}(\bar d_2,\bar q)=\dfrac{0,00786}{0,0834\cdot 0,1653}\Rightarrow \text{Sim}(\bar d_2,\bar q)=0,57\) [δίπλα: 6]
- \(\text{Sim}(\bar d_3,\bar q)=\dfrac{0,0343}{0,20862\cdot 0,1653}\Rightarrow \text{Sim}(\bar d_3,\bar q)=0,9946\) [δίπλα: 1]
- \(\text{Sim}(\bar d_4,\bar q)=\dfrac{0,00868}{0,08064\cdot 0,1653}\Rightarrow \text{Sim}(\bar d_4,\bar q)=0,5924\) [δίπλα: 5]
- \(\text{Sim}(\bar d_5,\bar q)=\dfrac{0,02323}{0,176\cdot 0,1653}\Rightarrow \text{Sim}(\bar d_5,\bar q)=0,7985\) [δίπλα: 4]
- \(\text{Sim}(\bar d_6,\bar q)=\dfrac{0,0227}{0,14288\cdot 0,1653}\Rightarrow \text{Sim}(\bar d_6,\bar q)=0,96113\) [δίπλα: 3]
Τα [δυσανάγνωστο] φθίνουσα σειρά
\(\{d_3, d_1, d_6, d_5, d_4, d_2\}\)
Σημείωση: αρκετά ψηφία των αριθμών είναι δυσανάγνωστα σε αυτή τη φωτογραφία (ιδίως στον αριθμητή της Sim(d̄2, q̄), στον αριθμητή της Sim(d̄3, q̄) και στον αριθμητή της Sim(d̄4, q̄)). Η μεταγραφή τους είναι ενδεικτική και πρέπει να ελεγχθεί με το πρωτότυπο. Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
20210130_155245.jpg¶
Θέμα 2 β (κυκλωμένο με κόκκινο μελάνι, επάνω δεξιά) · ir 1_3 (υπογραμμισμένο με κόκκινο μελάνι)
[Σχήμα: χειρόγραφος πίνακας με στήλες όρου, n_i και λίστα εγγράφων d_j]
| όρος | n_i | λίστα εγγράφων |
|---|---|---|
| algorithm | 4 | [d2, d3, d6, d7] |
| array | 5 | [d1, d4, d5, d6, d7] |
| data | 4 | [d1, d2, d3, d6] |
| graph | 3 | [d1, d3, d5] |
| list | 4 | [d1, d3, d5, d7] |
| pointer | 5 | [d2, d4, d5, d6, d7] |
| tree | 1 | [d5] |
[Σχήμα: επτά χειρόγραφα κουτιά "όρος | n_i" με βέλη προς αριθμούς εγγράφων, δηλαδή ανεστραμμένες λίστες]
- algorithm | 4 → 2 → 3 → 6 → 7
- array | [δυσανάγνωστο] → 1 → 4 → 5 → 6 → 7
- data | 4 → 1 → 2 → 3 → 6
- graph | 3 → 1 → 3 → 5
- list | 4 → 1 → 3 → [δυσανάγνωστο] → 7
- pointer | 5 → 2 → 4 → 5 → 6 → 7
- tree | 1 → 5
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
20210130_155326.jpg¶
[Σχήμα: πάνω στη γραμμή Data βέλος "i ↓" πάνω από το \(d_1\)· κάτω από τη γραμμή Graph βέλος "j ↑" κάτω από το \(d_1\)· στην πάνω αριστερή γωνία τμήμα εκτυπωμένου πίνακα, περιστραμμένο και δυσανάγνωστο]
Data → \(d_1\) → \(d_2\) → \(d_3\) → \(d_{[δυσανάγνωστο]}\)
Graph → \(d_1\) → \(d_3\) → \(d_5\)
2 προσπελάσεις i's
Για 1 ~~[δυσανάγνωστο]~~ άρα \(\{d_1\}\)
αυτών προσπελάσεις
-
\(i \to 2\), \(j \to 3\) → [δυσανάγνωστο]: αυξάνω τον μικρότερο
-
\(i \to 3\), \(j \to 3\) → [δυσανάγνωστο] → \(\{d_1, d_3\}\), αυξάνω και τους 2
-
\(i \to 6\), \(j \to 5\) → [δυσανάγνωστο]: τέλος αρχείων
Άρα οι όροι Data και Graph συναντώνται ταυτόχρονα στα \(\{d_1, d_3\}\)