Τεχνητή Νοημοσύνη — Σεπτέμβριος 2024

IMG_2791.jpg

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ, ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΓΡΑΠΤΗ ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ "ΤΕΧΝΗΤΗ ΝΟΗΜΟΣΥΝΗ", 19 ΣΕΠΤΕΜΒΡΙΟΥ 2024 ΟΝΟΜΑΤΕΠΩΝΥΜΟ: [παραλείπεται] ΑΜ: [παραλείπεται] ΕΤΟΣ: 5ο ΔΙΔΑΣΚΟΝΤΕΣ: Σ. ΛΥΚΟΘΑΝΑΣΗΣ, Δ. ΚΟΥΤΣΟΜΗΤΡΟΠΟΥΛΟΣ, ΔΙΑΡΚΕΙΑ ΕΞΕΤΑΣΗΣ: 2 ΩΡΕΣ

Ερώτηση 1 Τι σημαίνει ότι ο αλγόριθμος \(A^*\) είναι βέλτιστα αποδοτικός (optimally efficient); - [ ] α. Ότι βρίσκει πάντα τη βέλτιστη λύση. - [ ] β. Ότι βρίσκει πάντα τη βέλτιστη λύση με τα λιγότερα βήματα. - [ ] γ. Ότι δεν υπάρχει άλλος βέλτιστος αλγόριθμος, με την ίδια ευρετική, που να επεκτείνει λιγότερους κόμβους. - [ ] δ. Ότι δεν υπάρχει άλλος βέλτιστος αλγόριθμος, με την ίδια ευρετική, που να βρίσκει συντομότερο μονοπάτι στο στόχο.

Ερώτηση 2 Στο γράφημα αναζήτησης του διπλανού σχήματος αρχικός κόμβος είναι ο \(S\), τελικοί οι \(G_1\), \(G_2\) και οι αριθμοί δίπλα στις ακμές είναι τα κόστη μετάβασης. Αν εφαρμόσουμε UCS ποιος στόχος θα βρεθεί πρώτος και ποιο θα είναι το κόστος του μονοπατιού; - [ ] α. \(G_1\), κόστος 7 - [ ] β. \(G_1\), κόστος 4 - [ ] γ. \(G_2\), κόστος 3 - [ ] δ. \(G_2\), κόστος 4

[Σχήμα: Γράφημα αναζήτησης με αρχικό κόμβο S. Ακμές: S->A (1), S->B (1), S->G1 (7), A->C (1), A->B (2), B->G2 (3), C->G2 (1).]

Ερώτηση 3 Στο γράφημα αναζήτησης του διπλανού σχήματος αρχικός κόμβος είναι ο \(S\), τελικοί οι \(G_1\), \(G_2\) και οι αριθμοί δίπλα στις ακμές είναι τα κόστη μετάβασης. Αν εφαρμόσουμε BFS ποιος στόχος θα βρεθεί πρώτος και ποιο θα είναι το κόστος του μονοπατιού; - [ ] α. \(G_1\), κόστος 7 - [ ] β. \(G_1\), κόστος 4 - [ ] γ. \(G_2\), κόστος 3 - [ ] δ. \(G_2\), κόστος 4

[Σχήμα: Το ίδιο γράφημα αναζήτησης με την Ερώτηση 2.]

Ερώτηση 4 Αν σε ένα πρόβλημα αναζήτησης εφαρμόσουμε τη μέθοδο \(A^*\) με ευρετική συνάρτηση την \(h(n) = 0\), για κάθε κόμβο \(n\), τότε αυτή εκφυλίζεται στη μέθοδο της ... - [ ] α. ... αναζήτησης πρώτα σε βάθος. - [ ] β. ... αναζήτησης πρώτα σε πλάτος. - [ ] γ. ... αναζήτησης ομοιόμορφου κόστους. - [ ] δ. ... άπληστης αναζήτησης. - [ ] ε. ... αναζήτησης επαναληπτικής εκβάθυνσης.

Ερώτηση 5 Η εφαρμογή του \(A^*\) στο γράφημα αριστερά κατέληξε στο δέντρο δεξιά. Τα κόστη μετάβασης φαίνονται στις ακμές του γράφου. Στο δέντρο απεικονίζονται μερικοί (αλλά όχι όλοι) από τους κόμβους που αναπτύχθηκαν και οι αριθμοί αντιπροσωπεύουν τιμές της \(f\). Αρχική κατάσταση είναι η \(A\) και τελική η \(G\). Έστω πως χρησιμοποιήθηκε το ευρετικό: \(\{h(A)=5, h(B)=6, h(C)=3, h(D)=3, h(E)=2\}\). Ποια είναι η σειρά ανάπτυξης των κόμβων που φαίνονται στο δέντρο; - [ ] α. \(A\ D\ B\ E\ G\) - [ ] β. \(A\ B\ D\ E\ G\) - [ ] γ. \(A\ D\ E\ B\ G\) - [ ] δ. \(A\ D\ E\ G\ B\)

[Σχήμα: Αριστερά κατευθυνόμενος γράφος με κόμβους A, B, C, D, E, G και βάρη: A->B (1), B->A (2), A->D (3), B->D (4), B->C (6), D->E (3), E->G (2), C->G (3). Δεξιά δέντρο αναζήτησης με κόμβους A, B (f=7), D (f=6), E (f=8) και G· ο αριθμός δίπλα στο G είναι κομμένος από την άκρη της φωτογραφίας (φαίνεται «8»), η τιμή f του A δεν είναι γραμμένη.]

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

IMG_2792.jpg

2

Ερώτηση 6 Θεωρήστε δύο παραδεκτά ευρετικά \(h_1\) και \(h_2\) που χρησιμοποιούνται στον αλγόριθμο \(A^*\) και για τα οποία ισχύει \(2 \cdot h_1(s) \le h_2(s)\) για κάθε κόμβο \(s\). Ποιο από τα παρακάτω ισχύει; - [ ] α. Ο \(A^*\) που χρησιμοποιεί το \(h_1\) θα βρει λύση κόστους κάτω από το μισό σε σχέση με τον \(A^*\) που χρησιμοποιεί το \(h_2\). - [ ] β. Ο \(A^*\) που χρησιμοποιεί το \(h_2\) θα βρει λύση κόστους κάτω από το μισό σε σχέση με τον \(A^*\) που χρησιμοποιεί το \(h_1\). - [ ] γ. Ο \(A^*\) που χρησιμοποιεί το \(h_1\) θα αναπτύξει λιγότερους από τους μισούς κόμβους σε σχέση με τον \(A^*\) που χρησιμοποιεί το \(h_2\). - [ ] δ. Ο \(A^*\) που χρησιμοποιεί το \(h_2\) θα αναπτύξει λιγότερους από τους μισούς κόμβους σε σχέση με τον \(A^*\) που χρησιμοποιεί το \(h_1\). - [ ] ε. Ο \(A^*\) που χρησιμοποιεί το \(h_1\) θα αναπτύξει περισσότερους κόμβους από αυτόν που χρησιμοποιεί το \(h_2\).

Ερώτηση 7 Για ένα πρόβλημα αναζήτησης, δίνεται μια παραδεκτή ευρετική συνάρτηση \(h\). Υπό ποιές προϋποθέσεις θα μπορούσε να είναι η \(\sqrt{h}\) πιο πληροφορημένη; - [ ] α. Αν \(h(n) \le 1\), για κάθε κόμβο \(n\) του χώρου καταστάσεων του προβλήματος. - [ ] β. Αν \(h(n) \ge 1\), για κάθε κόμβο \(n\) του χώρου καταστάσεων του προβλήματος. - [ ] γ. Αν \(h(n) \le 1\), για κάποιο κόμβο \(n\) του χώρου καταστάσεων του προβλήματος. - [ ] δ. Αν \(h(n) \ge 1\), για κάποιο κόμβο \(n\) του χώρου καταστάσεων του προβλήματος. - [ ] ε. Αν \(h(n) = 1\), για κάποιο κόμβο \(n\) του χώρου καταστάσεων του προβλήματος.

Ερώτηση 8 Για ένα πρόβλημα αναζήτησης, δίνονται δύο παραδεκτές ευρετικές συναρτήσεις \(h_1\) και \(h_2\). Πότε λέμε ότι η \(h_1\) είναι περισσότερο πληροφορημένη από την (κυριαρχεί επάνω στην) \(h_2\); - [ ] α. Όταν ισχύει \(h_1(n) < h_2(n)\), για κάθε κόμβο \(n\) του χώρου καταστάσεων του προβλήματος. - [ ] β. Όταν ισχύει \(h_1(n) \ge h_2(n)\), για κάθε κόμβο \(n\) του χώρου καταστάσεων του προβλήματος. - [ ] γ. Όταν ισχύει \(h_1(n) > h_2(n)\), για τουλάχιστον ένα κόμβο \(n\) του χώρου καταστάσεων του προβλήματος. - [ ] δ. Όταν ισχύει \(h_1(n) \le h_2(n)\), για τουλάχιστον τους μισούς κόμβους \(n\) του χώρου καταστάσεων του προβλήματος.

Ερώτηση 9 Ένα ρομπότ κινείται σε ένα ορθογώνιο πλέγμα, στο οποίο κάποιες από τις θέσεις του είναι εμπόδια. Το ρομπότ μπορεί να κινηθεί είτε κατακόρυφα, παράλληλα με τον \(Y\) άξονα, είτε οριζόντια, παράλληλα με τον \(X\) άξονα. Οι κατακόρυφες κινήσεις έχουν κόστος 1 και οι οριζόντιες έχουν κόστος 0. Αν η τρέχουσα θέση του ρομπότ είναι η \((X_R, Y_R)\) και η θέση-στόχος είναι η \((X_G, Y_G)\), τότε ποια ευρετική συνάρτηση \(h\) θα επιλέγατε να χρησιμοποιήσετε σε συνδυασμό με τη μέθοδο \(A^*\), για να εγγυηθείτε την εύρεση βέλτιστης λύσης; Σημειώστε ότι με \((X_i, Y_i)\) συμβολίζουμε τη θέση στο πλέγμα που βρίσκεται στην \(X_i\) στήλη και στην \(Y_i\) γραμμή. - [ ] α. \(h = |X_R - X_G| + |Y_R - Y_G|\) - [ ] β. \(h = |X_R - Y_R| + |X_G - Y_G|\) - [ ] γ. \(h = |Y_R - Y_G|\) - [ ] δ. \(h = \sqrt{(X_R - X_G)^2 + (Y_R - Y_G)^2}\)

Ερώτηση 10 Όταν η μέθοδος αναζήτησης \(A^*\) εφαρμοσθεί σε πρόβλημα με μοναδιαία κόστη ακμών και τιμή της ευρετικής συνάρτησης \(h = 0\) για κάθε κόμβο, ... - [ ] α. ... ενδέχεται να παγιδευτεί σε κύκλο. - [ ] β. ... εκφυλίζεται στην αναζήτηση σε πλάτος. - [ ] γ. ... εκφυλίζεται στην άπληστη αναζήτηση. - [ ] δ. ... ενδέχεται να επιστρέψει μη βέλτιστη λύση.

Ερώτηση 11 Επιλέξτε τις προτάσεις που είναι σωστές. - [ ] α. Η αναρρίχηση λόφων μπορεί γενικά να αποφεύγει ένα τοπικό βέλτιστο, όταν υπάρχουν πολλά βέλτιστα. - [ ] β. Η προσομοιωμένη ανόπτηση με θετική, σταθερή θερμοκρασία σε όλες τις επαναλήψεις ταυτίζεται με την αναρρίχηση λόφων. - [ ] γ. Η προσομοιωμένη ανόπτηση επιλέγει μια κατάσταση τυχαία και μπορεί να μεταβεί σε αυτήν ακόμα αν είναι χειρότερη. - [ ] δ. Στην επαναληπτική τοπική αναζήτηση (iterative LS) ο αλγόριθμος χρησιμοποιεί διαφορετικές αρχικές καταστάσεις κάθε φορά που επιλέγονται τυχαία.

IMG_2793.jpg

3

Ερώτηση 12 Εφαρμόστε την ευρετική του Εγγύτερου Γείτονα (Nearest Neighbor) για να λύσετε ένα στιγμιότυπο του προβλήματος TSP για έξι πόλεις (\(A, B, C, D, E, F\)) με βάση τον διπλανό πίνακα γειτνίασης. Ποια διαδρομή βρίσκει ο αλγόριθμος ξεκινώντας από την \(A\); - [ ] α. A-E-C-D-B-F-A - [ ] β. A-B-D-E-C-F-A - [ ] γ. A-D-E-F-B-C-A - [ ] δ. A-B-C-D-E-F-A

	A	B	C	D	E	F
A	0	10	20	30	40	50
B	10	0	31	21	51	41
C	20	31	0	12	59	100
D	30	21	12	0	5	8
E	40	51	59	5	0	69
F	50	41	100	8	69	0

Ερώτηση 13 Αν στην προσομοιωμένη ανόπτηση η θερμοκρασία \(T \rightarrow \infty\) ο αλγόριθμος: - [ ] α. Θα τερματίσει αμέσως χωρίς να κάνει αναζήτηση. - [ ] β. Συμπεριφέρεται σαν BFS. - [ ] γ. Συμπεριφέρεται σαν hill climbing. - [ ] δ. Θα επιλέγει τυχαία μια κατάσταση σε κάθε επανάληψη. - [ ] ε. κανένα από τα παραπάνω

Ερώτηση 14 Ο αλγόριθμος WA* (weighted A*) χρησιμοποιεί ως συνάρτηση κόστους την \(f(n) = g(n) + w h(n)\), όπου \(w\) θετική σταθερά \(>1\). Ως αποτέλεσμα: - [ ] α. Ο WA* είναι γενικά ταχύτερος από τον A*. - [ ] β. Ο WA* είναι γενικά αργότερος από τον A*. - [ ] γ. Ο WA* δεν είναι εγγυημένο ότι θα βρει βέλτιστη λύση, ακόμα κι αν η \(h(n)\) είναι παραδεκτή. - [ ] δ. Ο WA* είναι εγγυημένο ότι θα βρει βέλτιστη λύση, αν η \(h(n)\) είναι παραδεκτή.

Ερώτηση 15 Σε σύγκριση με την αναζήτηση κατά πλάτος, η επαναληπτική εκβάθυνση (IDS): - [ ] α. Είναι βέλτιστη και πλήρης, όπως ο BFS. - [ ] β. Απαιτεί λιγότερη μνήμη. - [ ] γ. Απαιτεί λιγότερο χρόνο. - [ ] δ. Λειτουργεί μόνο αν το βάθος της λύσης είναι μικρό.

Ερώτηση 16 Έστω ότι εφαρμόζεται ο αλγόριθμος \(k\)-means με \(k = 4\) για ένα τρισδιάστατο σύνολο παραδειγμάτων. Σε κάποιο βήμα του αλγορίθμου τα κέντρα των τεσσάρων ομάδων είναι τα \(\mu_1 = (0,0,0)\), \(\mu_2 = (1,1,1)\), \(\mu_3 = (-1,-1,-1)\) και \(\mu_4 = (0,0,0.5)\). Σε ποια ομάδα θα καταταγεί το παράδειγμα \(x = (0.1, 0.1, 0.6)\); - [ ] α. Στην ομάδα 1. - [ ] β. Στην ομάδα 2. - [ ] γ. Στην ομάδα 3. - [ ] δ. Στην ομάδα 4.

Ερώτηση 17 Ένα σύνολο δεδομένων περιέχει σημεία στο καρτεσιανό επίπεδο. Τα σημεία της κλάσης \(X\) ορίζονται ως εξής: \(\{x<5, y>5\}\). Τα σημεία της κλάσης \(Y\) ορίζονται ως εξής: \(\{x>5, y<5\}\). Ποιο είναι το μικρότερο δέντρο απόφασης για το διαχωρισμό των δύο κλάσεων; - [ ] α. 1 εσωτερικός κόμβος και 2 φύλλα - [ ] β. 3 εσωτερικοί κόμβοι και 4 φύλλα - [ ] γ. 1 εσωτερικός κόμβος και 4 φύλλα - [ ] δ. 1 φύλλο

Ερώτηση 18 Ένας νευρώνας έχει 4 εισόδους με διάνυσμα βαρών \([1,2,3,4]\), μηδενική πόλωση και λογιστική συνάρτηση ενεργοποίησης. Ποια είναι η έξοδός του αν εφαρμοστεί η είσοδος \((1,0,1,-1)\); - [ ] α. -1 - [ ] β. 1 - [ ] γ. 0.5 - [ ] δ. 0.75

IMG_2794.jpg

4

Ερώτηση 19 Γιατί δεν είναι καλή ιδέα να χρησιμοποιούμε γραμμικές συναρτήσεις ενεργοποίησης στους νευρώνες του κρυμμένου επιπέδου σ' ένα νευρωνικό δίκτυο εμπρόσθιας τροφοδότησης που εκπαιδεύεται με οπισθοδιάδοση του λάθους; - [ ] α. Γιατί οι συναρτήσεις είναι μεν συνεχείς αλλά δεν είναι φθίνουσες. - [ ] β. Γιατί δεν μπορούμε να υπολογίσουμε τις παραγώγους τους. - [ ] γ. Γιατί ένα πολυεπίπεδο δίκτυο με συναρτήσεις τέτοιου τύπου δεν θα ήταν πιο ισχυρό από ένα δίκτυο χωρίς κρυμμένο επίπεδο. - [ ] δ. Γιατί οι συναρτήσεις τέτοιου τύπου δεν επιφέρουν αλλαγές στα βάρη στους νευρώνες του κρυμμένου επιπέδου.

Ερώτηση 20 Η σιγμοειδής συνάρτηση ενεργοποίησης \(f(x)=1/(1+e^{-x})\) έχει παράγωγο και μέγιστη κλίση αντίστοιχα: - [ ] α. \(f(x)\) και 1 - [ ] β. \(1-f(x)\) και 0,75 - [ ] γ. \(2f(x)(1-f(x))\) και 0,50 - [ ] δ. \(f(x)(1-f(x))\) και 0,25

Ερώτηση 21 Έστω ένα πολυεπίπεδο perceptron με αρχιτεκτονική \(2-3-2-1\). Πόσες ελεύθερες παραμέτρους (βάρη και πολώσεις) έχει το δίκτυο; - [ ] α. 14 - [ ] β. 18 - [ ] γ. 20 - [ ] δ. 22

Ερώτηση 22 Ποιο είδος ΤΝΔ είναι κατάλληλο για επίλυση προβλημάτων ομαδοποίησης (clustering); - [ ] α. Ένα κλασσικό MLP (ΤΝΔ εμπρόσθιας τροφοδότησης). - [ ] β. Ένα απλό perceptron. - [ ] γ. ΤΝΔ ανταγωνιστικής μάθησης. - [ ] δ. Κανένα από τα εναλλακτικά που δίνονται.

Ερώτηση 23 Ποιο από τα παρακάτω είναι ΣΩΣΤΟ; - [ ] α. Η πόλωση ενός νευρώνα είναι το βάρος μιας σύνδεσης με είσοδο ίση με -1. - [ ] β. Το XOR είναι ένα γραμμικά διαχωρίσιμο πρόβλημα ταξινόμησης - [ ] γ. Η εκπαίδευση ενός νευρώνα με ελαχιστοποίηση του σφάλματος εκπαίδευσης τερματίζει πάντα αν ο ρυθμός μάθησης είναι μικρός. - [ ] δ. Η εκπαίδευση του perceptron με διόρθωση σφάλματος τερματίζει πάντα αν ο ρυθμός μάθησης είναι μικρός.

Ερώτηση 24 Έστω ένας νευρώνας δύο εισόδων \(x_1\) και \(x_2\), με λογιστική συνάρτηση ενεργοποίησης, και τιμές βαρών \(w_1=1, w_2=-1\). Για εισόδους \(x_1=4\) και \(x_2=2\), η έξοδος του νευρώνα είναι 0.5. Ποια είναι η τιμή της πόλωσης \(w_0\) του νευρώνα; - [ ] α. 0 - [ ] β. -2 - [ ] γ. 2 - [ ] δ. -1

Ερώτηση 25 Έστω το πρόβλημα του πλανόδιου πωλητή για 20 πόλεις και ότι επιζητούμε την επίλυσή του με γενετικό αλγόριθμο. Η μικρότερη απ' ευθείας απόσταση ανάμεσα σε δύο πόλεις είναι \(1/10\) (μονάδες απόστασης) και η μεγαλύτερη είναι 10. Για να χρησιμοποιήσουμε τη μέθοδο της ποινής, πρέπει να έχουμε μία πλασματική τιμή απόστασης ανάμεσα σε (κάθε δύο) πόλεις που δεν συνδέονται απ' ευθείας. Ποια από τις παρακάτω τιμές είναι η πιο ενδεδειγμένη; - [ ] α. -10000 - [ ] β. 0 - [ ] γ. 1 - [ ] δ. 100 - [ ] ε. 1000

IMG_2799.jpg

5

Ερώτηση 26 Αν εκτελέσουμε διασταύρωση μονού σημείου ανάμεσα στα άτομα 1.3.2.4.4.2.1 και 2.7.5.1.4.2.1, ποιο από τα παρακάτω άτομα είναι αδύνατον να προκύψει μόνο από διασταύρωση; - [ ] α. 1.3.5.1.4.2.1 - [ ] β. 2.7.2.4.4.2.1 - [ ] γ. 1.3.2.1.4.2.1 - [ ] δ. 2.7.5.4.4.2.1 - [ ] ε. 1.3.2.4.4.7.1

Ερώτηση 27 Ποια από τις παρακάτω προτάσεις είναι ορθή στην εξέλιξη με γενετικούς αλγόριθμους; - [ ] α. Ένας καλός γονέας, αν επιλεχθεί, παράγει εγγυημένα τουλάχιστον ένα απόγονο, που είναι τουλάχιστον τόσο καλός όσο και ο γονέας. - [ ] β. Οι τιμές της συνάρτησης αξιολόγησης, για καθένα από τους απογόνους ενός ζεύγους γονέων, θα βρίσκονται εντός του διαστήματος τιμών που ορίζεται από τις τιμές της συνάρτησης αξιολόγησης για τους γονείς. - [ ] γ. Η παραγωγή ενός καλού απόγονου είναι απόδειξη ότι κάποιος γονέας ήταν τουλάχιστον τόσο καλός όσο και ο απόγονος. - [ ] δ. Η παραγωγή ενός καλού απόγονου μπορεί να οφείλεται αποκλειστικά σε μετάλλαξη.

Ερώτηση 28 Έστω ένα σχήμα το οποίο στην αρχική γενιά ενός γενετικού αλγορίθμου ταιριάζει με το 50% των ατόμων του πληθυσμού. Πότε είναι πιο πιθανό το σχήμα αυτό να εξαφανιστεί από τον πληθυσμό σε λίγες γενιές; - [ ] α. Όταν έχει μικρή τάξη και μικρό οριστικό μήκος. - [ ] β. Όταν έχει μικρή τάξη και μεγάλο οριστικό μήκος. - [ ] γ. Όταν έχει μεγάλη τάξη και μικρό οριστικό μήκος. - [ ] δ. Όταν έχει μεγάλη τάξη και μεγάλο οριστικό μήκος.

Ερώτηση 29 Θέλουμε να χρησιμοποιήσουμε γενετικούς αλγόριθμους για να υπολογίσουμε τους ακέραιους \(a, b, c, d\), που παίρνουν τιμές στο διάστημα \([-1000..1000]\) και ικανοποιούν την εξίσωση \(ax^6+bx^4+cx^2+d=0\), για \(x=1\) και για \(x=2\). Πόσα bits χρειάζονται για την αναπαράσταση ενός ατόμου; - [ ] α. 320 - [ ] β. 44 - [ ] γ. 2001 - [ ] δ. 10

Ερώτηση 30 Έστω οι μεταβλητές \(X, Y\) και \(Z\), με πεδία \(D_X = D_Y = D_Z = \{1,2,3\}\) και περιορισμούς \(X<Y\) και \(Y<Z\). Ποια θα είναι τα πεδία των μεταβλητών μετά την εφαρμογή του αλγορίθμου AC-3; - [ ] α. \(D_X = \{1,2,3\}, D_Y = \{1,2,3\}, D_Z = \{1,2,3\}\) - [ ] β. \(D_X = \{1\}, D_Y = \{2\}, D_Z = \{3\}\) - [ ] γ. \(D_X = \{1,2\}, D_Y = \{2,3\}, D_Z = \{1,2,3\}\) - [ ] δ. \(D_X = \{1\}, D_Y = \{1,2\}, D_Z = \{1,2,3\}\)

Ερώτηση 31 Ποιος από τους παρακάτω αλγορίθμους ΔΕΝ αποτελεί αλγόριθμο επίλυσης ενός προβλήματος ικανοποίησης περιορισμών; - [ ] α. Συνέπειας κόμβου - [ ] β. Συνέπειας τόξου - [ ] γ. Συνέπειας δέντρου - [ ] δ. Συνέπειας μονοπατιού

Ερώτηση 32 Έστω οι μεταβλητές \(X, Y, Z\) και \(W\), με πεδία \(D_X = D_Y = D_Z = D_W = \{1,2,3\}\) και περιορισμούς \(X \neq Y\), \(Y \neq Z\), \(Z \neq W\) και \(Y \neq W\). Θέλουμε να επιλύσουμε το πρόβλημα χρησιμοποιώντας αναζήτηση με ευρετικό το «μέγιστο αριθμό περιορισμών». Με ποια μεταβλητή θα ξεκινήσουμε την απόδοση τιμής; - [ ] α. \(X\) - [ ] β. \(Y\) - [ ] γ. \(Z\) - [ ] δ. \(W\)

IMG_2800.jpg

6

Ερώτηση 33 Έστω οι μεταβλητές \(X, Y, Z\) και \(W\), με πεδία \(D_X = D_Y = D_Z = D_W = \{1,2,3\}\) και περιορισμούς \(X \neq Y\), \(X \neq Z\), \(X \neq W\), \(Y \neq Z\), \(Y \neq W\), και \(Z \neq W\). Ποια θα είναι τα πεδία των μεταβλητών μετά την εφαρμογή του αλγορίθμου AC-3; - [ ] α. \(D_X = \{\}, D_Y = \{\}, D_Z = \{\}, D_W = \{\}\) - [ ] β. \(D_X = \{1\}, D_Y = \{2\}, D_Z = \{3\}, D_W = \{1,2,3\}\) - [ ] γ. \(D_X = \{1,2,3\}, D_Y = \{1,2,3\}, D_Z = \{1,2,3\}, D_W = \{1,2,3\}\) - [ ] δ. \(D_X = \{1\}, D_Y = \{2\}, D_Z = \{3\}, D_W = \{\}\)

Ερώτηση 34 Ποια από τις παρακάτω δηλώσεις αναπαρίσταται καλύτερα από την πρόταση \(\forall y\ ([\forall x\ (\text{student}(x) \Rightarrow \text{likes}(x,y))] \Rightarrow \forall z\ (\text{teaches}(z,y) \Rightarrow \text{excellent}(z)))\) - [ ] α. Αν όλα τα μαθήματα αρέσουν σ' όλους τους φοιτητές, τότε όλοι οι καθηγητές είναι εξαιρετικοί εκπαιδευτικοί. - [ ] β. Αν κάποιο μάθημα αρέσει σ' όλους τους φοιτητές, τότε οι καθηγητές που το διδάσκουν είναι εξαιρετικοί εκπαιδευτικοί. - [ ] γ. Αν υπάρχει ένα μάθημα που αρέσει σ' όλους τους φοιτητές, τότε όλοι οι καθηγητές που διδάσκουν κάποιο μάθημα είναι εξαιρετικοί εκπαιδευτικοί. - [ ] δ. Αν σ' όλους τους φοιτητές αρέσουν όλα τα μαθήματα, τότε όσοι καθηγητές διδάσκουν κάποιο μάθημα είναι εξαιρετικοί εκπαιδευτικοί.

Ερώτηση 35 Έστω \(S\) ένα σύνολο από clauses, και \(P(x)\), \(Q(y)\) δύο κατηγορήματα που εμφανίζονται στο \(S\). Επιπλέον θεωρήστε πως κατά την αναγωγή στο \(S\) παράγεται το clause \(\{\neg P(x), \neg Q(x)\}\). Ποια από τις παρακάτω προτάσεις είναι αληθής; - [ ] α. Το \(S\) συνεπάγεται ταυτολογικά το \(\exists x\ (\neg P(x) \wedge \neg Q(x))\). - [ ] β. Το \(S\) συνεπάγεται ταυτολογικά το \(\forall x\ (\neg P(x) \wedge \neg Q(x))\). - [ ] γ. Το \(S\) συνεπάγεται ταυτολογικά το \(\exists x\ (P(x) \wedge Q(x))\). - [ ] δ. Το \(S\) συνεπάγεται ταυτολογικά το \(\exists x\ (\neg P(x) \vee \neg Q(x))\).

Ερώτηση 36 Ποια από τις παρακάτω προτάσεις κατηγορηματικής λογικής ΔΕΝ αναπαριστά το «Ο \(x\) είναι παππούς του \(y\), αν ο \(x\) είναι πατέρας κάποιου \(z\) και ο \(z\) είναι γονέας του \(y\).»; - [ ] α. \(\forall x\ \forall y\ \forall z\ ((\pi\alpha\tau\epsilon\rho\alpha\varsigma(x,z) \wedge \gamma o\nu\epsilon\alpha\varsigma(z,y)) \Rightarrow \pi\alpha\pi\pi o\upsilon\varsigma(x,y))\) - [ ] β. \(\forall x\ \forall y\ \forall z\ (\pi\alpha\pi\pi o\upsilon\varsigma(x,y) \Rightarrow (\pi\alpha\tau\epsilon\rho\alpha\varsigma(x,z) \wedge \gamma o\nu\epsilon\alpha\varsigma(z,y)))\) - [ ] γ. \(\forall x\ \forall y\ (\exists z\ (\pi\alpha\tau\epsilon\rho\alpha\varsigma(x,z) \wedge \gamma o\nu\epsilon\alpha\varsigma(z,y)) \Rightarrow \pi\alpha\pi\pi o\upsilon\varsigma(x,y))\) - [ ] δ. \(\neg \exists x\ \exists y\ \exists z\ (\pi\alpha\tau\epsilon\rho\alpha\varsigma(x,z) \wedge \gamma o\nu\epsilon\alpha\varsigma(z,y) \wedge \neg \pi\alpha\pi\pi o\upsilon\varsigma(x,y))\)

Ερώτηση 37 Ποιος από τους παρακάτω ισχυρισμούς ΔΕΝ είναι ορθός; - [ ] α. Κάθε σειρά από βήματα αναγωγής τερματίζει έχοντας παράγει την κενή πρόταση. - [ ] β. Κάποιες αναγωγές παράγουν την κενή πρόταση. - [ ] γ. Κάποιες αναγωγές δεν παράγουν την κενή πρόταση. - [ ] δ. Καμία αναγωγή δεν μπορεί να χρησιμοποιήσει την κενή πρόταση.

Ερώτηση 38 Από τι αποτελείται ένα πρόγραμμα Prolog; - [ ] α. Δηλώσεις και εντολές - [ ] β. Γεγονότα και κανόνες - [ ] γ. Συναρτήσεις - [ ] δ. Δηλώσεις, εντολές, γεγονότα, κανόνες και συναρτήσεις

Ερώτηση 39 Η κενή λίστα στην Prolog συμβολίζεται με: - [ ] α. NULL - [ ] β. [[]] - [ ] γ. [] - [ ] δ. [_]

IMG_2801.jpg

7

Ερώτηση 40 Ποιες τιμές παίρνουν οι μεταβλητές στο ερώτημα Prolog: ?- [X,a,S] = [b,A,[c,d]]. - [ ] α. Οι μεταβλητές δεν παίρνουν καμία τιμή, καθώς το ερώτημα δεν μπορεί να αποδειχθεί. - [ ] β. \(X = b\) και \(S = c\) και \(A = a\). - [ ] γ. \(X = b\) και \(S = c,d\) και \(A = a\). - [ ] δ. \(X = b\) και \(S = [c,d]\) και \(A = a\).

Ερώτηση 41 Η ερώτηση Prolog ?- length([[]],N). έχει ως απάντηση την: - [ ] α. \(N=0\). - [ ] β. \(N=1\). - [ ] γ. true. - [ ] δ. false.

Ερώτηση 42 Σ' ένα πρόβλημα συμπλήρωσης σταυρόλεξου, δίνεται ένα πλέγμα \(NXN\), όπου θα πρέπει να συμπληρωθούν \(M\) λέξεις-θέσεις με διάφορα μήκη από ένα δεδομένο σύνολο λέξεων \(D\). Στην προσπάθεια να αναπαραστήσουν το πρόβλημα ως πρόβλημα ικανοποίησης περιορισμών, 4 μαθητές πρότειναν τα παρακάτω. Επιλέξτε την καλύτερη σωστή πρόταση. - [ ] α. Ορίζω \(NXN\) μεταβλητές με πεδίο ορισμού για κάθε μια το \(D\). - [ ] β. Ορίζω \(M\) μεταβλητές με πεδίο ορισμού για κάθε μια το \(D\). - [ ] γ. Ορίζω \(M\) μεταβλητές με πεδίο ορισμού για κάθε μια το υποσύνολο του \(D\) με λέξεις ίδιου μήκους με τη λέξη-θέση που αντιπροσωπεύει. - [ ] δ. Ορίζω \(N\) μεταβλητές με πεδίο ορισμού για κάθε μια το \(D\).

Ερώτηση 43 Τι αναπαριστά η πρόταση \(\forall x \forall y \forall z (\neg \text{Φοιτητής}(x) \vee \neg \text{Αμάξι}(y) \vee \neg \text{Ανήκει}(y,x) \vee (\text{Πατέρας}(z,x) \Rightarrow \text{Έμπορος}(z)))\): - [ ] α. Όσοι φοιτητές έχουν αμάξι, έχουν πατέρα έμπορο. - [ ] β. Όλοι όσοι δεν είναι φοιτητές ή δεν έχουν αμάξι, έχουν πατέρα έμπορο. - [ ] γ. Αν ο πατέρας κάποιου είναι έμπορος, τότε είτε δεν είναι φοιτητής είτε δεν έχει αμάξι. - [ ] δ. Αν ο πατέρας κάποιου είναι έμπορος, τότε δεν είναι φοιτητής και έχει αμάξι.

Ερώτηση 44 Σ' ένα γράφο περιορισμών - [ ] α. Οι κόμβοι παριστάνουν περιορισμούς και οι ακμές μεταβλητές - [ ] β. Οι κόμβοι παριστάνουν μεταβλητές και οι ακμές περιορισμούς. - [ ] γ. Οι κόμβοι παριστάνουν πεδία τιμών και οι ακμές μεταβλητές. - [ ] δ. Οι ακμές είναι πάντα μονής κατεύθυνσης.

Ερώτηση 45 Δίνεται ένα σύνολο δεδομένων με δύο δυαδικά χαρακτηριστικά \(X_1\), \(X_2\) και \(Y\) δυαδική ετικέτα κλάσης. Με βάση το σύνολο αυτό κατασκευάζουμε δέντρο απόφασης που αποτελείται μόνο από 3 κόμβους: Τη ρίζα και δύο παιδιά. Σε κάθε φύλλο ανατίθεται η κλάση πλειοψηφίας του σχετικού συνόλου δειγμάτων. Σε περίπτωση ισοβαθμίας προτιμάται \(Y=0\). Ποια θα είναι η ακρίβεια ταξινόμησης του δέντρου στο σύνολο εκπαίδευσης;

\(X_1\)	0	0	1	1
\(X_2\)	0	1	0	1
\(Y\)	1	1	1	0

• [ ] α. 0%
• [ ] β. 25%
• [ ] γ. 50%
• [ ] δ. 75%
• [ ] ε. 100%

Ερώτηση 46 Έχουμε ένα σύνολο δεδομένων το οποίο περιέχει 8 σημεία που χαρακτηρίζονται ως \(X\) και 8 σημεία που χαρακτηρίζονται ως \(Y\). Τα διαχωρίζουμε σε 2 υποσύνολα, καθένα από τα οποία περιέχει 4 σημεία \(X\) και 4 σημεία \(Y\). Ποια ήταν η αρχική ποσότητα πληροφορίας, \(I_0\), και ποιο ήταν το κέρδος πληροφορίας από το διαχωρισμό, \(I_G\); - [ ] α. \(I_0 = 1\text{ bit}, I_G = 0\text{ bits}\) - [ ] β. \(I_0 = 1\text{ bit}, I_G = 1\text{ bit}\) - [ ] γ. \(I_0 = 2\text{ bits}, I_G = 2\text{ bits}\) - [ ] δ. \(I_0 = 0\text{ bits}, I_G = 1\text{ bit}\)

IMG_2802.jpg

8

Ερώτηση 47 Σε ένα σύνολο 16 παραδειγμάτων, τα 8 ανήκουν στην κλάση \(C_1\) και τα υπόλοιπα 8 στην κλάση \(C_2\). Πόση είναι η εντροπία του συνόλου; - [ ] 1. 0.00 - [ ] 2. 0.25 - [ ] 3. 0,50 - [ ] 4. 1.00

Ερώτηση 48 Ποιος είναι ο κυριότερος λόγος για το κλάδεμα ενός δέντρου απόφασης; - [ ] α. Για εξοικονόμηση χρόνου κατά τον έλεγχο. - [ ] β. Για εξοικονόμηση χώρου αποθήκευσης του δέντρου απόφασης. - [ ] γ. Για μείωση του σφάλματος εκπαίδευσης. - [ ] δ. Για αποφυγή υπερεκπαίδευσης. - [ ] ε. Για αύξηση του κέρδους πληροφορίας στη ρίζα του δέντρου απόφασης.

Ερώτηση 49 Δίδεται η παρακάτω βάση κανόνων. R1: if A and B then C R2: if C and D then E R3: if A and I then ¬H R4: if A and ¬D then E R5: if C and ¬D then I R6: if E and I then ¬H R7: if E and H then ¬G R8: if E and ¬H then G

Ζητείται να εξαχθεί το G, αν το αρχικό περιεχόμενο της μνήμης εργασίας είναι \(\text{ME} = \{A, B, \neg D, E\}\). \((\alpha)\) Αν χρησιμοποιηθεί αλυσίδωση προς τα εμπρός (forward chaining) και ως στρατηγική ελέγχου η εξής: ο πρώτος υποψήφιος κανόνας που συναντάται πυροδοτείται (σειρά αναγραφής), ενώ ο ίδιος κανόνας πυροδοτείται μόνο μια φορά. \((\beta)\) Αν χρησιμοποιηθεί ως στρατηγική ελέγχου η προσφατότητα και δευτερευόντως η σειρά αναγραφής, τότε: - [ ] α. Το G εξάγεται σε λιγότερα βήματα με τη μέθοδο \((\alpha)\). - [ ] β. Το G εξάγεται σε λιγότερα βήματα με τη μέθοδο \((\beta)\). - [ ] γ. Θα κάνουν τα ίδια βήματα επειδή όλοι οι κανόνες έχουν το ίδιο πλήθος συνθηκών. - [ ] δ. Εξαρτάται από τη δευτερεύουσα στρατηγική.

Ερώτηση 50 Στο σχήμα απεικονίζεται μια ιεραρχία πλαισίων. Ποιος από τους παρακάτω αλγορίθμους μπορεί να δώσει απάντηση ναι στο ερώτημα, αν πετά ο Γκάρυ; - [ ] α. Εύρεση τιμής με κατά πλάτος αναζήτηση - [ ] β. Εύρεση τιμής με χρήση απόστασης συλλογισμού - [ ] γ. Αλγόριθμος τύπου N - [ ] δ. Αλγόριθμος τύπου Z

[Σχήμα: Ιεραρχία πλαισίων: Πτηνό: Πετά: +τιμές: ναι, όχι, +ευλ. υπόθεση: ναι Από το Πτηνό εξαρτώνται: Στρουθοκάμηλος (Πετά: τιμή: όχι) και Κατοικίδιο - Πτηνό. Από τη Στρουθοκάμηλο εξαρτάται το Ροζ - Στρουθοκάμηλος. Από το Ροζ - Στρουθοκάμηλος και το Κατοικίδιο - Πτηνό εξαρτάται το πλαίσιο Γκάρυ: Πετά: ?]

Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις → 2024-09.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας): IMG_8866.jpg, IMG_8868.jpg, IMG_8870.jpg, IMG_8871.jpg, IMG_4007.jpg, IMG_4003.JPG, IMG_4004.JPG, IMG_4005.JPG, IMG_4006.JPG, IMG_4008.JPG, Screenshot_7.png, Screenshot_2.png

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

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: migrated from previous_exams.md (Antigravity, 2026-10)

Προσοχή

Η αρίθμηση του παλιού αρχείου για την ενότητα των φωτογραφιών IMG_4003–IMG_4008 διαφέρει από την αρίθμηση της εξέτασης· οι λύσεις αντιστοιχίστηκαν με βάση το κείμενο της ερώτησης (παλιά → εδώ: 4→5, 5→4, 28→27, 29→28, 35→37, 36→35, 37→36, 38→39, 39→38, 42→44, 43→42, 44→43, 45→48, 46→45, 47→46, 48→47). Η ερώτηση 27 εδώ (γενετικοί αλγόριθμοι, «ορθή πρόταση») αντιστοιχεί στο παλιό 28. Ερώτηση 35: η απάντηση του παλιού αρχείου δεν δηλώνει γράμμα επιλογής· γράφει «Ένα clause {¬P(x), ¬Q(x)} αναπαριστά τη διάζευξη ∀x (¬P(x) ∨ ¬Q(x))». Η αντιστοίχιση με συγκεκριμένη επιλογή πρέπει να ελεγχθεί.

Λύσεις — Τεχνητή Νοημοσύνη — Σεπτέμβριος 2024

Λύσεις AI μεταφερμένες αυτούσιες από το παλιό previous_exams.md (χωρίς επαλήθευση). Η αντιστοίχιση με την αρίθμηση της εξέτασης έγινε με βάση το κείμενο των ερωτήσεων.

Ερώτηση 1

Σωστή Απάντηση: γ. Ο \(A^*\) με συνεπή ευρετική εγγυάται ότι κανένας άλλος βέλτιστος αλγόριθμος δεν επεκτείνει λιγότερους κόμβους (optimal efficiency).

Ερώτηση 2

Σωστή Απάντηση: α. Ο BFS ερευνά ανά επίπεδα βάθους. Στο επίπεδο 1 βρίσκονται οι \(\{A, B, G_1\}\). Εφόσον ο \(G_1\) βρίσκεται στο βάθος 1 (άμεσος απόγονος του \(S\)), ανακαλύπτεται πρώτος με κόστος διαδρομής \(S \to G_1 = 7\).

Ερώτηση 3

Σωστή Απάντηση: γ. Ο UCS αναπτύσσει κόμβους με αύξον πραγματικό κόστος \(g(n)\): 1. \(S \to A\) (\(g=1\)), \(S \to B\) (\(g=1\)) 2. Επέκταση \(A\): παράγει \(C\) (\(g=1+1=2\)) και \(G_2\) (\(g=1+2=3\)) 3. Επέκταση \(C\): παράγει \(G_2\) (\(g=2+1=3\)) 4. Ο στόχος \(G_2\) αφαιρείται από το μέτωπο με ελάχιστο κόστος \(g(G_2) = 3\).

Ερώτηση 4

Σωστή Απάντηση: γ. Εφόσον \(f(n) = g(n) + h(n) = g(n) + 0 = g(n)\), η αναζήτηση καθοδηγείται αποκλειστικά από το πραγματικό κόστος διαδρομής \(g(n)\), που αποτελεί τον ορισμό του Uniform Cost Search.

Ερώτηση 5

Σωστή Απάντηση: α. Σειρά ανάπτυξης \(A \to D \to B \to E \to G\) (μετά την επέκταση του \(D\), ο κόμβος \(B\) έχει \(f=7 < f(E)=8\), οπότε αναπτύσσεται ο \(B\) πριν τον \(E\)).

Ερώτηση 27

Σωστή Απάντηση: β.

Ερώτηση 28

Σωστή Απάντηση: δ. Μεγάλη τάξη (πολλά καθορισμένα bits) αυξάνει την πιθανότητα αλλοίωσης από μετάλλαξη, και μεγάλο οριστικό μήκος αυξάνει δραματικά την πιθανότητα διακοπής από διασταύρωση (crossover disruption).

Ερώτηση 34

Σωστή Απάντηση: β. Για κάθε μάθημα \(y\), εάν όλοι οι φοιτητές \(x\) συμπαθούν το \(y\), τότε όποιος \(z\) διδάσκει το \(y\) είναι εξαιρετικός.

Ερώτηση 35

Σωστή Απάντηση: Ένα clause \(\{\neg P(x), \neg Q(x)\}\) αναπαριστά τη διάζευξη \(\forall x (\neg P(x) \lor \neg Q(x))\).

Ερώτηση 36

Σωστή Απάντηση: β. Η πρόταση β αντιστρέφει τη συνεπαγωγή και απαιτεί ο \(x\) να είναι πατέρας κάθε \(z\) που είναι γονέας του \(y\).

Ερώτηση 37

Σωστή Απάντηση: α. Δεν οδηγεί κάθε διαδρομή αναγωγής στην κενή πρόταση (αν επιλεγούν μη αποδοτικά βήματα ή το σύνολο δεν είναι μη ικανοποιήσιμο).

Ερώτηση 38

Σωστή Απάντηση: β. Γεγονότα και κανόνες.

Ερώτηση 39

Σωστή Απάντηση: γ. []

Ερώτηση 40

Σωστή Απάντηση: δ. Μέσω ενοποίησης (unification): \(X = b\), \(A = a\), \(S = [c, d]\).

Ερώτηση 41

Σωστή Απάντηση: β. \(N = 1\) (η εξωτερική λίστα περιέχει ένα στοιχείο, την κενή λίστα []).

Ερώτηση 42

Σωστή Απάντηση: γ. Ορίζονται \(M\) μεταβλητές (μία για κάθε λέξη-θέση) με πεδίο τιμών τις λέξεις του λεξικού \(D\) που έχουν ακριβώς το αντίστοιχο μήκος.

Ερώτηση 43

Σωστή Απάντηση: α. Χρησιμοποιώντας την ισοδυναμία \(\neg A \lor \neg B \lor C \equiv (A \land B) \implies C\): «Αν ο \(x\) είναι φοιτητής και του ανήκει αμάξι \(y\), τότε αν ο \(z\) είναι πατέρας του \(x\), ο \(z\) είναι έμπορος».

Ερώτηση 44

Σωστή Απάντηση: β. Οι κόμβοι αναπαριστούν τις μεταβλητές και οι ακμές τους περιορισμούς μεταξύ τους.

Ερώτηση 45

Σωστή Απάντηση: δ. 75% - Αν επιλεγεί το \(X_1\) ως ρίζα: - Για \(X_1=0\): δείγματα \(\{ (0,0), (0,1) \}\) με ετικέτες \(\{1, 1\} \implies\) πρόβλεψη \(Y=1\) (\(2/2\) σωστά). - Για \(X_1=1\): δείγματα \(\{ (1,0), (1,1) \}\) με ετικέτες \(\{1, 0\} \implies\) ισοβαθμία, ανατίθεται \(Y=0\) (\(1/2\) σωστό). - Συνολική ακρίβεια: \(3 / 4 = 75\%\).

Ερώτηση 46

Σωστή Απάντηση: α. - Αρχική εντροπία: \(I_0 = -\frac{8}{16}\log_2\frac{8}{16} - \frac{8}{16}\log_2\frac{8}{16} = 1\text{ bit}\). - Εντροπία κάθε υποσυνόλου: \(I(S_1) = I(S_2) = 1\text{ bit}\). - Υπολειπόμενη εντροπία: \(I_{rem} = \frac{8}{16}(1) + \frac{8}{16}(1) = 1\text{ bit}\). - Κέρδος πληροφορίας: \(I_G = I_0 - I_{rem} = 1 - 1 = 0\text{ bits}\).

Ερώτηση 47

Σωστή Απάντηση: 4. 1.00 bit (μέγιστη αβεβαιότητα λόγω ισοκατανομής 50%-50%).

Ερώτηση 48

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

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

---

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