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

Τεχνητή Νοημοσύνη — Σεπτέμβριος 2025 (μερικό)

b110d816-0c31-4e80-9821-65533b95dc7f.jpg

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ, ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΓΡΑΠΤΗ ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ "ΤΕΧΝΗΤΗ ΝΟΗΜΟΣΥΝΗ ", 1 ΣΕΠΤΕΜΒΡΙΟΥ [2025] ΔΙΑΡΚΕΙΑ ΕΞΕΤΑΣΗΣ: 2,5 ΩΡΕΣ ΟΝΟΜΑΤΕΠΩΝΥΜΟ: _________________________ AM: ______ ΕΤΟΣ: ___

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

[Σχήμα: Πλέγμα 5x5 συντεταγμένων (x, y) από (1,1) έως (5,5). Αρχική κατάσταση A=(3,5), Τελική T=(3,1). Μαύρα τετράγωνα εμπόδια στα (3,2), (3,3), (3,4).]

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

  1. 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
  2. A, (2,5), (2,4), (2,3), (2,2), (2,1), (1,1), (1,2), (1,3), (1,4), (1,5), T
  3. A, (4,5), (5,5), (5,4), (5,3), (5,2), (5,1), (4,1), T
  4. A, (2,5), (4,5), (2,4), (4,4), (2,3), (4,3), (2,2), (4,2), (2,1), (4,1), T

Β) Ο αλγόριθμος WA* (weighted A*) χρησιμοποιεί ως συνάρτηση κόστους την \(f(n) = g(n) + w h(n)\), όπου w θετική σταθερά >1. Να εξηγήσετε γιατί μπορεί να είναι ταχύτερος σε σχέση με τον Α*. [10]

ΘΕΜΑ 2ο (μονάδες 20) Έστω το πρόβλημα των 4 Βασιλισσών, όπου χρειάζεται να τοποθετηθούν 4 βασίλισσες σε μια σκακιέρα 4Χ4, ώστε να μην επιτίθεται καμία στην άλλη (οριζόντια, κάθετα ή διαγώνια). Α) Να μοντελοποιήσετε το πρόβλημα ως πρόβλημα ικανοποίησης περιορισμών, δηλ. να οριστούν οι μεταβλητές, τα πεδία τιμών τους και οι περιορισμοί μεταξύ τους. [10] Β) Να εφαρμόσετε αλγόριθμο συνέπειας τόξου AC-3 και να αναφέρετε τα τελικά πεδία τιμών των μεταβλητών, με δεδομένο ότι η βασίλισσα της 1ης στήλης έχει τοποθετηθεί στην 1η γραμμή. [10]

ΘΕΜΑ 3ο (μονάδες 20) Δίνονται οι παρακάτω προτάσεις ΚΛΠΤ: 1. \((\forall x)(\exists y)(\text{μητέρα}(y, x))\) 2. \((\forall x)(\forall y)(\forall z)((\text{μητέρα}(z, x) \land \text{μητέρα}(z, y)) \Rightarrow \text{αδερφός}(x, y))\) 3. \(\text{μητέρα}(\text{Μαρία}, \text{Κώστας})\) 4. \(\text{μητέρα}(\text{Μαρία}, \text{Γιώργος})\)

Α) Μετατρέψτε τις προτάσεις 1-4 βήμα-βήμα σε Προτασιακή Μορφή. [5]

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

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

Προσοχή

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

AI λύσεις — 2025-09

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

Θέμα 1

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

Α) Εμπόδια \((3,2),(3,3),(3,4)\), αρχή \(A=(3,5)\), στόχος \(T=(3,1)\). Με προσομοίωση (Python) επιβεβαιώθηκε ότι ο BFS (επέκταση γειτόνων με σειρά αριστερά, δεξιά, κάτω, πάνω) δίνει ακριβώς τη σειρά 1 και ο A* με Manhattan ευρετική τη σειρά 4.

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

Β) Στον WA* είναι \(f(n)=g(n)+w\,h(n)\) με \(w>1\). Η ευρετική έχει μεγαλύτερο βάρος, οπότε η αναζήτηση προτιμά κόμβους που φαίνονται κοντά στον στόχο (πλησιάζει τη συμπεριφορά του πρώτα-στο-καλύτερο) αντί να εξαντλεί όλους τους κόμβους με μικρό \(g\). Έτσι επεκτείνονται συνήθως πολύ λιγότεροι κόμβοι και η λύση βρίσκεται ταχύτερα, με λιγότερη μνήμη. Το τίμημα: αν η \(h\) είναι παραδεκτή, η λύση δεν είναι απαραίτητα βέλτιστη, αλλά το κόστος της είναι το πολύ \(w\times\) το βέλτιστο.

Θέμα 2

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

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

  • Μεταβλητές: \(Q_1,Q_2,Q_3,Q_4\), όπου \(Q_i\) η γραμμή της βασίλισσας της στήλης \(i\) (μία ανά στήλη).
  • Πεδία: \(D_i=\{1,2,3,4\}\).
  • Περιορισμοί για κάθε \(i<j\): \(Q_i\ne Q_j\) (όχι ίδια γραμμή) και \(|Q_i-Q_j|\ne j-i\) (όχι ίδια διαγώνιος).

Β) AC-3 με \(Q_1=1\) (\(D_1=\{1\}\))

Αρχικά όλα τα τόξα \((Q_i,Q_j)\) στην ουρά. Ενδεικτικά βήματα (επαλήθευση με Python):

  1. Revise(\(Q_2\),\(Q_1\)): διαγράφονται οι τιμές 1 (ίδια γραμμή) και 2 (διαγώνιος) ⇒ \(D_2=\{3,4\}\).
  2. Revise(\(Q_3\),\(Q_1\)): διαγράφονται 1 και 3 ⇒ \(D_3=\{2,4\}\).
  3. Revise(\(Q_3\),\(Q_2\)): η τιμή 4 δεν έχει υποστήριξη (με \(Q_2=3\) είναι διαγώνιος, με \(Q_2=4\) ίδια γραμμή) ⇒ \(D_3=\{2\}\).
  4. Revise(\(Q_4\),\(Q_1\)): διαγράφονται 1 και 4 ⇒ \(D_4=\{2,3\}\).
  5. Revise(\(Q_4\),\(Q_3\)): με \(Q_3=2\) δεν επιτρέπονται 2 (ίδια γραμμή) και 3 (διαγώνιος) ⇒ \(D_4=\emptyset\).

Το \(D_4\) άδειασε. Η διάδοση συνεχίζεται (π.χ. \(D_2\): η 3 αφαιρείται λόγω \(Q_3=2\), η 4 λόγω του κενού \(D_4\)) και καταλήγουμε σε όλα τα πεδία κενά: $\(D_1=D_2=D_3=D_4=\emptyset.\)$

Τελικά πεδία: κενά, δηλαδή αδυναμία λύσης. Με τη βασίλισσα της 1ης στήλης στην 1η γραμμή δεν υπάρχει λύση του προβλήματος των 4 βασιλισσών (οι δύο λύσεις είναι οι \((2,4,1,3)\) και \((3,1,4,2)\)). Ο AC-3 το ανιχνεύει χωρίς αναζήτηση.

Θέμα 3

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

Α) Προτασιακή μορφή. Γράφω μ για μητέρα, α για αδερφός.

  1. \((\forall x)(\exists y)\,\mu(y,x)\): Skolem, το \(y\) εξαρτάται από το \(x\) ⇒ \(y=f(x)\): \((\forall x)\,\mu(f(x),x)\). Πρόταση: \(\{\mu(f(x),x)\}\).
  2. \((\forall x)(\forall y)(\forall z)\,[(\mu(z,x)\land\mu(z,y))\Rightarrow\alpha(x,y)]\):
  3. απαλοιφή \(\Rightarrow\): \(\neg(\mu(z,x)\land\mu(z,y))\lor\alpha(x,y)\),
  4. De Morgan: \(\neg\mu(z,x)\lor\neg\mu(z,y)\lor\alpha(x,y)\),
  5. χωρίς ύπαρξη/ποσοδείκτες που να απομένουν (όλοι καθολικοί): πρόταση \(\{\neg\mu(z,x),\ \neg\mu(z,y),\ \alpha(x,y)\}\).
  6. \(\{\mu(\text{Μαρία},\text{Κώστας})\}\)
  7. \(\{\mu(\text{Μαρία},\text{Γιώργος})\}\)

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

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