Μετάβαση στο περιεχόμενο

Τεχνητή Νοημοσύνη — Φεβρουάριος 2025 — Ομάδα Β

IMG_20250207_121801.jpg

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ, ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΓΡΑΠΤΗ ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ "ΤΕΧΝΗΤΗ ΝΟΗΜΟΣΥΝΗ", 7 ΦΕΒΡΟΥΑΡΙΟΥ 2025 -ΔΙΑΡΚΕΙΑ ΕΞΕΤΑΣΗΣ: 2,5 ΩΡΕΣ-

ΟΝΟΜΑΤΕΠΩΝΥΜΟ: _________________________ AM: _________ ΕΤΟΣ: _____

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

[Σχήμα: Κατευθυνόμενο γράφημα: Κόμβοι με ευρετική \(h\): \(S(5)\), \(A(4)\), \(B(1)\), \(C(2)\), \(G(0)\). Ακμές και κόστη: \(S \to A: 2\) \(S \to G: 7\) \(A \to B: 3\) \(A \to G: 4\) \(B \to C: 1\) \(B \to G: 2\) \(C \to G: 2\)]

Εκτελέστε αναλυτικά τις παρακάτω μεθόδους αναζήτησης: i) Αναζήτηση Ομοιόμορφου Κόστους (UCS), ii) Αναζήτηση Πρώτα στο Καλύτερο (BestFS). Για κάθε έναν από τους αλγορίθμους δείξτε αναλυτικά τα βήματα που ακολουθεί μέχρι να βρει τη λύση. Δημιουργήστε πίνακα που θα περιέχει την τρέχουσα κατάσταση, το μέτωπο αναζήτησης, το κλειστό σύνολο καταστάσεων και τα παιδιά της τρέχουσας κατάστασης. Αναφέρετε το αποτέλεσμα του μονοπατιού και του κόστους κάθε αλγορίθμου.

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

Να συνεχίσετε την αναζήτηση, εφαρμόζοντας τον αλγόριθμο αναζήτησης με προοπτικό έλεγχο (forward checking) και το κριτήριο της συντομότερης αποτυχίας. Να σχεδιάσετε το δέντρο αναζήτησης που προκύπτει μέχρι και τις επόμενες 2 αναθέσεις τιμών. [10]

ΘΕΜΑ 3° (μονάδες 20) Α) Δίνεται το παρακάτω σύνολο προτάσεων κατηγορηματικής λογικής: [10] 5. \(\text{supplier}(\text{Anna}, \text{Peter})\) 6. \(\text{rich}(\text{Anna})\) 7. \(\forall x \forall y\ (\text{supplier}(x, y) \Rightarrow \text{partner}(x, y))\) 8. \(\forall x \forall y\ (\text{partner}(x, y) \land \text{rich}(x) \Rightarrow \text{can\_loan}(x, y))\) Ελέγξτε με την μέθοδο αντίφασης της επίλυσης εάν από τις παραπάνω προτάσεις (1) - (4) προκύπτει το συμπέρασμα \(\text{can\_loan}(\text{Anna}, \text{Peter})\).

Β) Θεωρήστε ένα σύνολο γεγονότων Prolog της μορφής \(\text{father}(\text{name1}, \text{name2})\). Να ορίσετε τα κατηγορήματα i) \(\alpha\delta\epsilon\rho\phi\acute{o}\varsigma/\eta(X, Y)\) και ii) \(\xi\acute{\alpha}\delta\epsilon\rho\phi\text{ος}/\eta\ (X, Y)\) [10]

20250207_120605.jpg

ΘΕΜΑ 4° (μονάδες 20)

Το νευρωνικό δίκτυο του σχήματος έχει ως συνάρτηση ενεργοποίησης την:

\[\text{ReLU}(z) = \begin{cases} z, & \alpha\nu\ z \ge 0 \\ 0, & \alpha\nu\ z < 0 \end{cases}\]

και βάρη: $\(w_{01} = -0.3,\quad w_{11} = -1,\quad w_{21} = 1\)$ $\(w_{02} = 1,\quad w_{12} = 1,\quad w_{22} = -1\)$ $\(v_0 = -0.5,\quad v_1 = -0.5,\quad v_2 = 1\)$

[Σχήμα: Νευρωνικό δίκτυο με 2 εισόδους \(x_1, x_2\), δύο κρυφούς νευρώνες \(h_1, h_2\) με βάρη \(w_{11}, w_{12}, w_{21}, w_{22}\) και πολώσεις \(w_{01}, w_{02}\), και ένα νευρώνα εξόδου \(O_1\) με βάρη \(u_1, u_2\) και πόλωση \(u_0\).]

Βρείτε την έξοδο για την είσοδο: \((x_1, x_2) = (2, -1)\)

ΘΕΜΑ 5° (μονάδες 20)
Ας υποθέσουμε ότι χρησιμοποιούμε ένα γλωσσικό μοντέλο bigram που βασίζεται στα παρακάτω δεδομένα εκπαίδευσης:
\ I am Sam \
\ Sam I am \
\ Sam I like \
\ Sam I do like \
\ do I like Sam \

iii. Ποια είναι η πιο πιθανή επόμενη λέξη που προβλέπεται από το μοντέλο για τις ακόλουθες ακολουθίες λέξεων; Δικαιολογήστε την απάντησή σας.
(1) \ Sam ...
(2) \ Sam I do ...
(3) \ Sam I am Sam ...
(4) \ do I like ...

iv. Ποια από τις ακόλουθες προτάσεις είναι καλύτερη, δηλαδή έχει μεγαλύτερη πιθανότητα με αυτό το μοντέλο; Δικαιολογήστε την απάντησή σας.
(5) \ Sam I do I like \
(6) \ Sam I am \
(7) \ I do like Sam I am \

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

Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις → 2025-02-b.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας): IMG_20250207_121811.jpg

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

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

Προσοχή

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

AI λύσεις — 2025-02-b

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

Θέμα 1

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

Η εκφώνηση λέει «αρχική κατάσταση \(A\)», όμως το γράφημα έχει ρίζα τον κόμβο \(S\) (με \(h(S)=5\)). Λύνω με αρχική την \(S\) (το φυσικό ανάγλυφο του γραφήματος) και δίνω στο τέλος και το αποτέλεσμα αν η αρχή είναι το \(A\).

Γράφημα: \(S\to A(2),G(7)\)· \(A\to B(3),G(4)\)· \(B\to C(1),G(2)\)· \(C\to G(2)\). Ευρετική: \(S=5,A=4,B=1,C=2,G=0\). Έλεγχος στόχου κατά την επέκταση. Τα βήματα επαληθεύτηκαν με πρόγραμμα.

i) UCS (κλειδί \(g\))

Τρέχουσα Μέτωπο πριν την επιλογή (κόμβος, \(g\)) Κλειστό Παιδιά (κόμβος, \(g\))
\(S\) \(\{S(0)\}\) \(\emptyset\) \(A(2),\ G(7)\)
\(A\) \(\{A(2),\ G(7)\}\) \(\{S\}\) \(B(5),\ G(6)\)
\(B\) \(\{B(5),\ G(6),\ G(7)\}\) \(\{S,A\}\) \(C(6),\ G(7)\)
\(G\) (μέσω \(A\)) \(\{C(6),\ G(6),\ G(7),\ G(7)\}\) — ισοβαθμία 6 (\(C\) και \(G\))· αν επιλεγεί πρώτα το \(C\), δίνει το \(G(8)\) και μετά επιλέγεται πάλι το \(G(6)\) \(\{S,A,B\}\) στόχος

Μονοπάτι: \(S\to A\to G\), κόστος \(2+4=\mathbf{6}\).

ii) BestFS (κλειδί \(h\))

Τρέχουσα Μέτωπο πριν την επιλογή (κόμβος, \(h\)) Κλειστό Παιδιά
\(S\) \(\{S(5)\}\) \(\emptyset\) \(A(4),\ G(0)\)
\(G\) \(\{G(0),\ A(4)\}\) \(\{S\}\) στόχος

Μονοπάτι: \(S\to G\), κόστος \(\mathbf{7}\) (όχι βέλτιστο· ο UCS βρίσκει 6).

Αν η αρχική κατάσταση είναι το \(A\): UCS: \(A\) ⇒ \(B(3),G(4)\), \(B\) ⇒ \(C(4),G(5)\), ισοβαθμία 4 (\(C\), \(G\)), στόχος \(G\) με \(A\to G\), κόστος 4. BestFS: \(A\) ⇒ \(B(h{=}1),G(h{=}0)\) ⇒ επιλέγεται το \(G\): \(A\to G\), κόστος 4.

Θέμα 2

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

Α) Μοντελοποίηση CSP

Ονομάζω τα κελιά 

a b c
d e f
g h i
- Μεταβλητές: \(a,b,c,d,e,f,g,h,i\). - Πεδία: \(\{1,\dots,9\}\) για καθεμία. - Περιορισμοί: - all-different: όλες οι μεταβλητές διαφορετικές ανά δύο. - άθροισμα 15 σε κάθε γραμμή: \(a+b+c=d+e+f=g+h+i=15\). - σε κάθε στήλη: \(a+d+g=b+e+h=c+f+i=15\). - στις διαγωνίους: \(a+e+i=c+e+g=15\).

Β) Forward checking με συντομότερη αποτυχία (MRV)

Από τον πίνακα της εκφώνησης οι ανατεθειμένες τιμές είναι: \(e=5,\ f=9,\ g=8\) (η πρώτη γραμμή είναι κενή).

Μετά τον προοπτικό έλεγχο (αφαίρεση των 5, 9, 8 από όλα τα πεδία και εφαρμογή των αθροισμάτων όπου μένει μία ελεύθερη μεταβλητή): - γραμμή 2: \(d+5+9=15\Rightarrow d=1\) ⇒ \(D_d=\{1\}\) - διαγώνιος \(c+e+g\): \(c+5+8=15\Rightarrow c=2\) ⇒ \(D_c=\{2\}\) - τα \(a,b,h,i\) έχουν πεδία \(\{1,2,3,4,6,7\}\).

Κριτήριο συντομότερης αποτυχίας (μικρότερο πεδίο): οι \(d\) και \(c\) έχουν πεδίο μεγέθους 1. Επιλέγω πρώτα το \(d\).

(e=5, f=9, g=8)
 └─ d=1   [FC: στήλη 1: a+1+8=15 ⇒ D_a={6}· αφαιρείται το 1 από τους άλλους]
      └─ c=2   [FC: στήλη 3: 2+9+i=15 ⇒ D_i={4}· D_a={6}· τα b,h: {3,4,6,7}]
           (επόμενη ανάθεση: a=6 [ή i=4], στη συνέχεια κ.ο.κ.)
Δηλαδή οι επόμενες δύο αναθέσεις είναι \(d=1\) και \(c=2\) (και οι δύο ήταν μονοσήμαντες, δεν υπάρχει διακλάδωση). Συνεχίζοντας: \(a=6,\ i=4\), από τη γραμμή 1 \(b=15-6-2=7\), από τη στήλη 2 \(h=15-7-5=3\).

Λύση: 

6 7 2
1 5 9
8 3 4
(μοναδική λύση, επαληθεύτηκε με πρόγραμμα· όλα τα αθροίσματα = 15.)

Σημείωση: η ανάγνωση του πίνακα (5 και 9 στη 2η γραμμή, 8 στην 3η στήλη 1) προέρχεται από τη μεταγραφή.

Θέμα 3

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

Α) Προτάσεις (πρόταση 5–8 της εκφώνησης), σε προτασιακή μορφή: 1. \(\{supplier(Anna, Peter)\}\) 2. \(\{rich(Anna)\}\) 3. \(\{\neg supplier(x,y),\ partner(x,y)\}\) 4. \(\{\neg partner(x,y),\ \neg rich(x),\ can\_loan(x,y)\}\) 5. Άρνηση του συμπεράσματος: \(\{\neg can\_loan(Anna, Peter)\}\)

Επιλύσεις: - (5)+(4), \(\{x/Anna,\ y/Peter\}\) ⇒ (6) \(\{\neg partner(Anna,Peter),\ \neg rich(Anna)\}\) - (6)+(2) ⇒ (7) \(\{\neg partner(Anna,Peter)\}\) - (7)+(3), \(\{x/Anna,\ y/Peter\}\) ⇒ (8) \(\{\neg supplier(Anna,Peter)\}\) - (8)+(1) ⇒ \(\{\}\)

Άρα \(can\_loan(Anna,Peter)\) προκύπτει.

Β) Prolog. Υποθέτω μόνο γεγονότα father(Πατέρας, Παιδί). Το φύλο δεν είναι γνωστό, άρα «αδερφός/η» = sibling.

sibling(X, Y) :- father(F, X), father(F, Y), X \= Y.

cousin(X, Y) :- father(P, X), father(Q, Y), sibling(P, Q).
Το δεύτερο καλύπτει μόνο ξαδέρφια μέσω των πατεράδων (αφού υπάρχουν μόνο γεγονότα father). Το X \= Y εμποδίζει να είναι κάποιος αδερφός του εαυτού του.

Θέμα 4

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

Συνάρτηση ReLU: \(\text{ReLU}(z)=\max(0,z)\). Είσοδος \((x_1,x_2)=(2,-1)\). Βάρη: \(w_{01}=-0.3,w_{11}=-1,w_{21}=1\); \(w_{02}=1,w_{12}=1,w_{22}=-1\); \(v_0=-0.5,v_1=-0.5,v_2=1\). (Επαλήθευση με Python.)

  • \(h_1=\text{ReLU}(-0.3+(-1)(2)+(1)(-1))=\text{ReLU}(-3.3)=0\)
  • \(h_2=\text{ReLU}(1+(1)(2)+(-1)(-1))=\text{ReLU}(4)=4\)
  • \(O=\text{ReLU}(-0.5+(-0.5)(0)+(1)(4))=\text{ReLU}(3.5)=3.5\)

Έξοδος: 3.5.

Θέμα 5

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

(Από την εκφώνηση υπάρχουν μόνο τα ερωτήματα iii και iv.) Μοντέλο bigram με εκτίμηση μέγιστης πιθανοφάνειας: \(P(w_2\mid w_1)=C(w_1w_2)/C(w_1)\). Μετρήσεις από τις 5 προτάσεις (υπολογισμός και με πρόγραμμα):

\(w_1\) \(C(w_1)\) επόμενες λέξεις (πλήθος)
<s> 5 Sam 3, I 1, do 1
I 5 am 2, like 2, do 1
Sam 5 I 3, </s> 2
am 2 Sam 1, </s> 1
do 2 like 1, I 1
like 3 </s> 2, Sam 1

iii) Πιο πιθανή επόμενη λέξη (το bigram κοιτά μόνο την τελευταία λέξη):

  1. <s> Sam ...: τελευταία λέξη Sam ⇒ \(P(I\mid Sam)=3/5\), \(P(</s>\mid Sam)=2/5\) ⇒ I.
  2. <s> Sam I do ...: τελευταία λέξη do ⇒ \(P(like\mid do)=P(I\mid do)=1/2\) ⇒ ισοβαθμία: like ή I (εξίσου πιθανές).
  3. <s> Sam I am Sam ...: τελευταία λέξη Sam ⇒ I (\(3/5\)).
  4. <s> do I like ...: τελευταία λέξη like ⇒ \(P(</s>\mid like)=2/3\), \(P(Sam\mid like)=1/3\) ⇒ </s>.

iv) Πιθανότητα προτάσεων (γινόμενο των bigram πιθανοτήτων):

  • (5) <s> Sam I do I like </s>: \(P(Sam|<s>)\,P(I|Sam)\,P(do|I)\,P(I|do)\,P(like|I)\,P(</s>|like)= rac35\cdot rac35\cdot rac15\cdot rac12\cdot rac25\cdot rac23=0.0096\)
  • (6) <s> Sam I am </s>: $ rac35\cdot rac35\cdot rac25\cdot rac12=0.072$
  • (7) <s> I do like Sam I am </s>: \(P(I|<s>)\,P(do|I)\,P(like|do)\,P(Sam|like)\,P(I|Sam)\,P(am|I)\,P(</s>|am)= rac15\cdot rac15\cdot rac12\cdot rac13\cdot rac35\cdot rac25\cdot rac12=0.0008\)

Καλύτερη πρόταση: η (6) (πιθανότητα 0.072) \(>\) (5) 0.0096 \(>\) (7) 0.0008.

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

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