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

IMG_20220915_110853.jpg

ΘΕΜΑ 1° (Μονάδες 20) Α) Δίνεται ο ακόλουθος χάρτης, όπου μπορεί κανείς να πλοηγηθεί στα λευκά τετράγωνα και όπου τα μαύρα τετράγωνα είναι εμπόδια. Είστε στο τετράγωνο \(A\) και θέλετε να μετακινηθείτε στο τετράγωνο \(T\).

[Σχήμα: Πλέγμα συντεταγμένων \(x, y\) μεγέθους \(5 \times 5\). Γραμμή 5: \((1,5)\), \((2,5)\), \(A\), \((4,5)\), \((5,5)\) Γραμμή 4: \((1,4)\), \((2,4)\), [μαύρο εμπόδιο], \((4,4)\), \((5,4)\) Γραμμή 3: \((1,3)\), \((2,3)\), [μαύρο εμπόδιο], \((4,3)\), \((5,3)\) Γραμμή 2: \((1,2)\), \((2,2)\), [μαύρο εμπόδιο], \((4,2)\), \((5,2)\) Γραμμή 1: \((1,1)\), \((2,1)\), \(T\), \((4,1)\), \((5,1)\) Το σημείο εκκίνησης \(A\) βρίσκεται στη θέση \((3,5)\) και ο στόχος \(T\) στη θέση \((3,1)\). Η στήλη \(x=3\) για \(y=2, 3, 4\) είναι μαύρα τετράγωνα (εμπόδια).]

Να αντιστοιχίσετε κάθε μία από τις ακόλουθες σειρές επίσκεψης τετραγώνων με έναν από τους αλγόριθμους αναζήτησης: κατά-Βάθος, κατά-Πλάτος, \(\text{A}^*\). Δικαιολογήστε σύντομα την αντιστοίχισή σας. Η σειρά επίσκεψης κατά την αναζήτηση δεν ταυτίζεται κατ' ανάγκη με το τελικό μονοπάτι. [10]

1. \(A, (4,5), (5,5), (5,4), (5,3), (5,2), (5,1), (4,1), T\)
2. \(A, (2,5), (4,5), (2,4), (4,4), (2,3), (4,3), (2,2), (4,2), (2,1), (4,1), T\)
3. \(A, (2,5), (4,5), (1,5), (2,4), (5,5), (4,4), (1,4), (2,3), (5,4), (4,3), (1,3), (2,2), (5,3), (4,2), (1,2), (2,1), (5,2), (4,1), (1,1), T\)
4. \(A, (2,5), (2,4), (2,3), (2,2), (2,1), (1,1), (1,2), (1,3), (1,4), (1,5), T\)

Β) Έστω \(h_1\) και \(h_2\) δύο παραδεκτές (admissible) ευρετικές συναρτήσεις για την εφαρμογή του αλγορίθμου \(\text{A}^*\) σε ένα πρόβλημα. Επιχειρηματολογήστε σύντομα για το ποιες από τις παρακάτω συναρτήσεις είναι επίσης παραδεκτές ευρετικές συναρτήσεις για το ίδιο πρόβλημα: [10]

\[h_1 + h_2 \qquad (h_1 + h_2)/2 \qquad h_1 h_2 \qquad \sqrt{h_1 h_2} \qquad h_1 / h_2 \qquad h_1 / (1 + h_2) \qquad h_2 / h_1 \qquad h_2 / (1 + h_1)\]

ΘΕΜΑ 2° (Μονάδες 20) Έστω μια απλοποιημένη εκδοχή του προβλήματος 5-Βασιλισσών, όπου σε κάθε στήλη και σε κάθε γραμμή μπορεί να υπάρχει μόνο μία βασίλισσα. Επίσης, ο τελεστής μετάβασης είναι η ανταλλαγή δύο γειτονικών στηλών μεταξύ τους. Για παράδειγμα, ο τελεστής \(\text{swap}(1,2)\) σημαίνει την ανταλλαγή των στηλών 1 και 2. Α) Πόσες είναι οι συνολικές καταστάσεις; [5] Β) Να ορίσετε κατάλληλη συνάρτηση αξιολόγησης/κόστους. Στη συνέχεια, να εκτελέσετε τοπική αναζήτηση από την αρχική κατάσταση που φαίνεται στο σχήμα. Να προσδιορίσετε την τελική κατάσταση και να αναφέρετε αν αποτελεί λύση στο πρόβλημα. [10]

[Σχήμα: Σκακιέρα \(5 \times 5\) με 5 βασίλισσες: Στήλη 1: γραμμή 3 (από κάτω) Στήλη 2: γραμμή 4 Στήλη 3: γραμμή 2 Στήλη 4: γραμμή 5 Στήλη 5: γραμμή 1]

Αν στην προσομοιωμένη ανόπτηση η θερμοκρασία \(T \to \infty\) ο αλγόριθμος συμπεριφέρεται

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

i) κατάβαση κλίσης με επιλογή του καλύτερου ii) κατάβαση κλίσης με τυχαία επιλογή...

IMG_20220915_100030.jpg

(στοχαστική) iii) κατάβαση κλίσης με επιλογή του \(1^{\text{ου}}\) καλύτερου iv) τυχαία επανεκκίνηση v) κανένα από τα παραπάνω. Να τεκμηριώσετε την επιλογή σας. [5]

ΘΕΜΑ 3° (μονάδες 15) Δίνεται η εξής περιγραφή: «Τα ζώα έχουν δέρμα, χρώμα και κάποιο είδος κίνησης. Τα πουλιά είναι ζώα που έχουν φτερά, ράμφος, ουρά και πετούν. Τα ψάρια είναι κι αυτά ζώα που έχουν λέπια, βράγχια και ουρά, αλλά δεν πετούν. Τα καναρίνια είναι πουλιά συνήθως χρώματος κίτρινου. Οι στρουθοκάμηλοι είναι πουλιά, αλλά δεν πετούν, περπατούν. Ο Τουΐτι είναι καναρίνι. Η Στέφυ είναι στρουθοκάμηλος. Ο Τσίου είναι ένα λευκό καναρίνι.»

Α) Να αναπαρασταθεί η γνώση με πλαίσια. [10] Β) Εξηγείστε πώς βρίσκεται η απάντηση στο ερώτημα «Τι χρώμα έχει ο Τουΐτι;» με βάση τον (1) αλγόριθμο βασισμένο στην απόσταση συλλογισμού, (2) τον αλγόριθμο τύπου Ν, και (3) τον αλγόριθμο τύπου Ζ. [5]

ΘΕΜΑ 4° (μονάδες 20) Δίνεται η παρακάτω βάση κανόνων με συντελεστές βεβαιότητας (με πλάγια γραφή εμφανίζονται οι μεταβλητές):

R1	R4
if is(shape, round) then assert(fruit, mandarin) (0.4)	if is(shape, round)  and is(color, red) then assert(fruit, apple) (0.7)
R2	R5
if is(shape, round) then assert(fruit, apple) (0.3)	if is(shape, round)  and is(color, red)  and is(size, small) then assert(fruit, apple) (0.5)
R3	R6
if is(shape, round)  and is(surface, weasand) then assert(fruit, mandarin) (0.8)	if is(shape, round)  and is(size, small) then assert(fruit, mandarin) (0.6)

Δίνονται τα εξής δεδομένα διαδοχικά: “is(shape, round)”, “is(surface, weasand) (-0.5)”, “is(color, red) (0.8)”, “is(size, small) (0.4)”. Περιγράψτε τα βήματα εξαγωγής συμπεράσματος όταν μας ενδιαφέρει η τιμή της μεταβλητής fruit. Ποια τιμή θα επιστραφεί;

ΘΕΜΑ 5° (μονάδες 25) Δίνεται η εξής περιγραφή: «Όλα οι οργανισμοί τρώνε κάποιο είδος τροφής, ενώ και τα ίδια μπορούν να αποτελέσουν τροφή για κάποιον άλλο οργανισμό. Όλα τα ζώα και όλα τα φυτά είναι οργανισμοί. Τα φυτοφάγα ζώα τρώνε μόνο φυτά. Τα σαρκοβόρα ζώα τρώνε άλλα ζώα, ενώ τα παμφάγα ζώα τρώνε και φυτά και άλλα ζώα. Τα σαρκοβόρα και τα παμφάγα ζώα τρώνε τα μικρότερα από αυτά ζώα. Ο σκύλος είναι ένα είδος παμφάγου ζώου.»

Α) Να αναπαρασταθεί η γνώση με προτάσεις ΚΛΠΤ. Δεν είναι απαραίτητο να καταγράψετε όλα τα βήματα. [15] Β) Να μετατρέψετε τη γνώση από ΚΛΠΤ σε Προτασιακή Μορφή. Δεν είναι απαραίτητο να καταγράψετε όλα τα βήματα. [10]

ΚΑΛΗ ΕΠΙΤΥΧΙΑ!

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

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

Προσοχή

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

AI λύσεις — 2022-09

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

Θέμα 1

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

Α) Εμπόδια: \((3,2),(3,3),(3,4)\). Αρχή \(A=(3,5)\), στόχος \(T=(3,1)\). Ευρετική για A*: απόσταση Manhattan.

• Σειρά 3 = κατά-Πλάτος (BFS): επισκέπτεται ανά επίπεδο: πρώτα όλα τα τετράγωνα σε βήματα 1 από το \(A\) (\((2,5),(4,5)\)), μετά σε βήματα 2 (\((1,5),(2,4),(5,5),(4,4)\)) κ.ο.κ., ισορροπημένα αριστερά και δεξιά, μέχρι το \(T\).
• Σειρά 2 = A*: με \(f=g+h\) τα \((2,5)\) και \((4,5)\) έχουν \(f=1+5=6\), τα \((2,4),(4,4)\) έχουν \(f=2+4=6\) κ.ο.κ. Όλα τα τετράγωνα των στηλών 2 και 4 έχουν \(f=6\) (το κόστος της βέλτιστης διαδρομής), ενώ τα \((1,5)\), \((5,5)\) κλπ. έχουν \(f=8\) και δεν επισκέπτονται ποτέ. Το μοτίβο «εναλλάξ στήλες 2 και 4, προς τα κάτω» ταιριάζει μόνο στον A*.
• Σειρές 1 και 4 = κατά-Βάθος (DFS): η αναζήτηση προχωρά όσο πιο βαθιά γίνεται σε έναν κλάδο. Η σειρά 1 πηγαίνει δεξιά ως το \((5,5)\), κατεβαίνει στο \((5,1)\) και φτάνει στο \(T\) από το \((4,1)\). Η σειρά 4 πηγαίνει αριστερά, κατεβαίνει στο \((2,1)\), ανεβαίνει από τη στήλη 1 και φτάνει στο \(T\) (διαφορετική προτεραιότητα στις κινήσεις). Οι τρεις αλγόριθμοι καλύπτουν τέσσερις σειρές, άρα δύο σειρές αντιστοιχούν στον DFS.

Β) Υποθέτω \(h_1,h_2\ge 0\) και \(h^*\) το πραγματικό κόστος. Παραδεκτή σημαίνει \(h\le h^*\).

• \(h_1+h_2\): όχι γενικά (π.χ. \(h_1=h_2=h^*\) δίνει \(2h^*>h^*\)).
• \((h_1+h_2)/2\): ναι, ο μέσος όρος δεν ξεπερνά το \(\max(h_1,h_2)\le h^*\).
• \(h_1h_2\): όχι γενικά (π.χ. \(h_1=h_2=h^*=3\) δίνει \(9>3\)).
• \(\sqrt{h_1h_2}\): ναι, ο γεωμετρικός μέσος είναι \(\le \max(h_1,h_2)\le h^*\).
• \(h_1/h_2\): όχι (αν το \(h_2\) είναι μικρό ή 0, το πηλίκο είναι μεγάλο/απροσδιόριστο).
• \(h_2/h_1\): όχι, για τον ίδιο λόγο.
• \(h_1/(1+h_2)\): ναι, είναι \(\le h_1\le h^*\) αφού \(1+h_2\ge1\).
• \(h_2/(1+h_1)\): ναι, είναι \(\le h_2\le h^*\).

Θέμα 2

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

Α) Μία βασίλισσα ανά γραμμή και ανά στήλη ⇒ κάθε κατάσταση είναι μετάθεση των 5 γραμμών στις 5 στήλες: \(5! = \mathbf{120}\) καταστάσεις.

Β) Συνάρτηση κόστους: \(h\) = πλήθος ζευγαριών βασιλισσών που απειλούνται διαγώνια (οριζόντια/κάθετα δεν υπάρχουν λόγω της μετάθεσης). Στόχος \(h=0\).

Αρχική κατάσταση (γραμμή της βασίλισσας κάθε στήλης, 1..5 από κάτω): \((3,4,2,5,1)\). Ζεύγη διαγωνίων: στήλες (1,2): γραμμές 3,4 ⇒ απειλή. Στήλες (2,5): γραμμές 4,1, διαφορά 3 και απόσταση στηλών 3 ⇒ απειλή. Άλλα ζεύγη όχι. Άρα \(h_0=2\).

Γείτονες με swap γειτονικών στηλών (επαληθεύτηκε με Python):

Swap	Κατάσταση	\(h\)
(1,2)	(4,3,2,5,1)	4
(2,3)	(3,2,4,5,1)	2
(3,4)	(3,4,5,2,1)	6
(4,5)	(3,4,2,1,5)	2

Κανένας γείτονας δεν έχει \(h<2\), άρα η ορεινή αναρρίχηση (κατάβαση κλίσης με επιλογή του καλύτερου) σταματά αμέσως στην αρχική κατάσταση \((3,4,2,5,1)\) με \(h=2\): τοπικό ελάχιστο / οροπέδιο, δεν είναι λύση. (Αν επιτρέπονταν πλάγιες κινήσεις στις ισοδύναμες καταστάσεις με \(h=2\), η αναζήτηση θα συνέχιζε στο οροπέδιο· στις 120 καταστάσεις υπάρχουν 10 λύσεις, π.χ. \((1,3,5,2,4)\).)

Γ) Προσομοιωμένη ανόπτηση με \(T\to\infty\)

Η πιθανότητα αποδοχής χειρότερης κίνησης \(e^{-\Delta E/T}\to 1\). Άρα γίνεται δεκτή οποιαδήποτε τυχαία κίνηση, και καλή και κακή: τυχαίος περίπατος, χωρίς επιλογή του καλύτερου ή του πρώτου καλύτερου. Η στοχαστική κατάβαση (ii) δέχεται μόνο βελτιωτικές κινήσεις, η τυχαία επανεκκίνηση (iv) είναι άλλη μέθοδος. Άρα (v) κανένα από τα παραπάνω (τυχαίος περίπατος).

Θέμα 3

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

Α) Πλαίσια

Ζώο:            δέρμα: ναι; χρώμα: (τιμή); κίνηση: (τιμή)
Πουλί:          is-a: Ζώο; φτερά: ναι; ράμφος: ναι; ουρά: ναι; πετά: ναι (κίνηση: πτήση)
Ψάρι:           is-a: Ζώο; λέπια: ναι; βράγχια: ναι; ουρά: ναι; πετά: όχι
Καναρίνι:       is-a: Πουλί; χρώμα: κίτρινο (default)
Στρουθοκάμηλος: is-a: Πουλί; πετά: όχι; κίνηση: περπάτημα
Τουΐτι:         instance-of: Καναρίνι
Στέφυ:          instance-of: Στρουθοκάμηλος
Τσίου:          instance-of: Καναρίνι; χρώμα: λευκό

Η ρητή τιμή «πετά: όχι» στη Στρουθοκάμηλο υπερισχύει της προεπιλογής του Πουλιού.

Β) «Τι χρώμα έχει ο Τουΐτι;»

Ο Τουΐτι δεν έχει τιμή στη θέση «χρώμα», άρα αναζητούμε στα πλαίσια προς τα πάνω. Στη συγκεκριμένη βάση υπάρχει μόνο μία διαδρομή is-a (\(Τουΐτι \to Καναρίνι \to Πουλί \to Ζώο\)) και καμία σύγκρουση, οπότε κάθε αλγόριθμος καταλήγει στην ίδια απάντηση:

1. Απόσταση συλλογισμού: επιλέγεται η τιμή από την κλάση που είναι πιο κοντά στο στιγμιότυπο. Το Καναρίνι (απόσταση 1) έχει «κίτρινο», ενώ το «χρώμα» του Ζώου (απόσταση 3) δεν έχει τιμή. Απάντηση: κίτρινο.
2. Αλγόριθμος τύπου Ν και 3. αλγόριθμος τύπου Ζ: είναι αλγόριθμοι διάσχισης του γράφου κληρονομικότητας (χρήσιμοι κυρίως όταν υπάρχουν πολλοί γονείς / συγκρούσεις). Δεν θυμάμαι με βεβαιότητα την ακριβή διατύπωσή τους από τις διαφάνειες· εδώ, επειδή η κληρονομικότητα είναι απλή αλυσίδα, δίνουν το ίδιο αποτέλεσμα: κίτρινο. Ελέγξτε τον ορισμό τους στις διαφάνειες.

Θέμα 4

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

Συμβάσεις: ΣΒ συμπεράσματος = ΣΒ κανόνα \(\times\) \(\min\) (ΣΒ συνθηκών). Συνδυασμός δύο θετικών ΣΒ του ίδιου συμπεράσματος: \(cf_1+cf_2-cf_1cf_2\). Κανόνας δεν πυροδοτείται αν το ΣΒ των συνθηκών είναι \(\le 0\).

Δεδομένο	Κανόνες που πυροδοτούνται	ΜΕ
shape round (1)	R1: mandarin \(0.4\cdot1=0.4\)· R2: apple \(0.3\cdot1=0.3\)	mandarin 0.4, apple 0.3
surface weasand (−0.5)	R3: συνθήκη \(\min(1,-0.5)=-0.5<0\) ⇒ δεν πυροδοτείται	αμετάβλητη
color red (0.8)	R4: \(0.7\cdot\min(1,0.8)=0.56\) ⇒ apple: \(0.3+0.56-0.168=0.692\)	apple 0.692
size small (0.4)	R5: \(0.5\cdot\min(1,0.8,0.4)=0.2\) ⇒ apple: \(0.692+0.2-0.1384=0.7536\)· R6: \(0.6\cdot\min(1,0.4)=0.24\) ⇒ mandarin: \(0.4+0.24-0.096=0.544\)	apple 0.7536, mandarin 0.544

(Οι υπολογισμοί ελέγχθηκαν με Python.)

Αποτέλεσμα: η τιμή με το μεγαλύτερο ΣΒ είναι fruit = apple (ΣΒ 0.7536), ενώ το mandarin έχει 0.544.

Θέμα 5

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

Κατηγορήματα: \(Org(x)\), \(Animal(x)\), \(Plant(x)\), \(Herb(x)\), \(Carn(x)\), \(Omni(x)\), \(Eats(x,y)\) («το \(x\) τρώει το \(y\)»), \(Smaller(y,x)\) («το \(y\) μικρότερο του \(x\)»), σταθερά \(Dog\).

Α) ΚΛΠΤ

1. \(\forall x\,[Org(x)\Rightarrow \exists y\,(Org(y)\land Eats(x,y))]\) (κάθε οργανισμός τρώει κάποιον οργανισμό ως τροφή)
2. \(\forall x\,[Org(x)\Rightarrow \exists y\,(Org(y)\land Eats(y,x))]\) (κάθε οργανισμός μπορεί να είναι τροφή άλλου)
3. \(\forall x\,[Animal(x)\Rightarrow Org(x)]\), \(\forall x\,[Plant(x)\Rightarrow Org(x)]\)
4. \(\forall x\,[Herb(x)\Rightarrow Animal(x)\land \forall y\,(Eats(x,y)\Rightarrow Plant(y))]\)
5. \(\forall x\,[Carn(x)\Rightarrow Animal(x)\land \forall y\,(Eats(x,y)\Rightarrow Animal(y))]\)
6. \(\forall x\,[Omni(x)\Rightarrow Animal(x)\land \exists y\,(Plant(y)\land Eats(x,y))\land \exists z\,(Animal(z)\land Eats(x,z))]\)
7. \(\forall x\forall y\,[(Carn(x)\lor Omni(x))\land Animal(y)\land Eats(x,y)\Rightarrow Smaller(y,x)]\)
8. \(Omni(Dog)\)

Β) Προτασιακή μορφή (Skolem: \(f,g\) για τις 1,2· \(p,a\) για την 6):

1. \(\{\neg Org(x),\ Org(f(x))\}\), \(\{\neg Org(x),\ Eats(x,f(x))\}\)
2. \(\{\neg Org(x),\ Org(g(x))\}\), \(\{\neg Org(x),\ Eats(g(x),x)\}\)
3. \(\{\neg Animal(x),\ Org(x)\}\), \(\{\neg Plant(x),\ Org(x)\}\)
4. \(\{\neg Herb(x),\ Animal(x)\}\), \(\{\neg Herb(x),\ \neg Eats(x,y),\ Plant(y)\}\)
5. \(\{\neg Carn(x),\ Animal(x)\}\), \(\{\neg Carn(x),\ \neg Eats(x,y),\ Animal(y)\}\)
6. \(\{\neg Omni(x),\ Animal(x)\}\), \(\{\neg Omni(x),\ Plant(p(x))\}\), \(\{\neg Omni(x),\ Eats(x,p(x))\}\), \(\{\neg Omni(x),\ Animal(a(x))\}\), \(\{\neg Omni(x),\ Eats(x,a(x))\}\)
7. \(\{\neg Carn(x),\ \neg Animal(y),\ \neg Eats(x,y),\ Smaller(y,x)\}\), \(\{\neg Omni(x),\ \neg Animal(y),\ \neg Eats(x,y),\ Smaller(y,x)\}\)
8. \(\{Omni(Dog)\}\)

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

---

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