Υπολογιστική Πολυπλοκότητα — Ιούνιος 2020 — Θεωρία (μηχανές Turing)¶
Μεταγραφή από τη φωτογραφία 2022-06-13_113810.png της εξέτασης Ιουνίου 2020· τα υπόλοιπα αντίγραφα αναφέρονται ως επιπλέον πηγές.
2022-06-13_113810.png¶
Θέμα Ιουνίου 2020 (3 μονάδες)¶
[Σχήμα: Διάγραμμα μηχανής Turing με καταστάσεις q_0, q_1, q_2, q_3, q_ΟΧΙ, q_ΝΑΙ. Μεταβάσεις: q_0 → q_1: α → Δ; q_0 → q_2: ⊔ → Α; q_1 → q_2: α → Δ; q_1 → q_3: ⊔ → α, Α; q_2 → q_3: α → Δ; q_2 → q_ΝΑΙ: ⊔ → α, Δ; q_3 → q_0: α → Δ; q_3 → q_ΟΧΙ: ⊔ → Α.]
(α1) Εκτελέστε την TM με είσοδο αααα. Επιλέξτε ένα από τα παρακάτω σχετικά με τη λειτουργία της TM: - [ ] A. Η TM αποδέχεται - [ ] B. Η TM απορρίπτει - [ ] Γ. Η TM εγκλωβίζεται
(α2) Είναι η TM διαγνώστης; - [ ] A. Ναι, η TM είναι διαγνώστης - [ ] B. Όχι, δεν είναι διαγνώστης γιατί με είσοδο τη συμβολοσειρά α εγκλωβίζεται - [ ] Γ. Όχι, δεν είναι διαγνώστης γιατί με είσοδο τη συμβολοσειρά αααα εγκλωβίζεται
(α3) Ποια είναι η γλώσσα της TM; - [ ] A. ε + αα(αααα)* - [ ] B. αα(αααα)* - [ ] Γ. (αααα)(ε + αα + ααα) - [ ] Δ. αα(ααα) - [ ] Ε. (ααα)*(αα + α)
Επιπλέον πηγές χωρίς μεταγραφή εδώ:
IMG_20220613_122731.jpgκαιIMG_20220613_122752.jpg(χειρόγραφες απαντήσεις φοιτητή, λύσεις →2020-06.solutions.md)·225fdeaf51aaa9c5.png(στιγμιότυπο ηλεκτρονικής εξέτασης με άλλη παραλλαγή της ερώτησης 2, δεν μεταγράφηκε).
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: φωτογραφία λύσης φοιτητή (χειρόγραφες σημειώσεις πάνω στις επιλογές του α3)
Προσοχή
Η φωτογραφία IMG_20220613_122752.jpg καλύπτει μόνο το ερώτημα (α3). Τα (α1) και (α2) έχουν χειρόγραφες απαντήσεις φοιτητή στην IMG_20220613_122731.jpg, που δεν έχουν αντιγραφεί εδώ. Οι επιλογές δ) και ε) αντιγράφηκαν ως «aa(aaa)» και «(aaa)(aa+a)», ώστε να ταυτίζονται με τις επιλογές Δ και Ε της μεταγραφής του 2020-06.md. Η προηγούμενη εκδοχή είχε λάθος ανάγνωση. Η επιλογή που σημειώνει ο φοιτητής (α: «ε + aa(aaaa)*») αντιστοιχεί στην επιλογή Α της μεταγραφής. Η ορθότητά της δεν επαληθεύτηκε. Η 225fdeaf51aaa9c5.png είναι στιγμιότυπο ηλεκτρονικής εξέτασης με άλλη παραλλαγή της ερώτησης 2 και δεν χρησιμοποιείται εδώ.
Λύσεις — Υπολογιστική Πολυπλοκότητα — Ιούνιος 2020 (θεωρία TM)¶
Η λύση προέρχεται από φωτογραφία φοιτητή. Καλύπτει μόνο το ερώτημα (α3) της γλώσσας της μηχανής· τα (α1) και (α2) έχουν χειρόγραφες απαντήσεις φοιτητή σε άλλη φωτογραφία. Η μεταγραφή ακολουθεί τη φωτογραφία.
IMG_20220613_122752.jpg¶
3) Ποια είναι η γλώσσα της TM;
a) ε + aa(aaaa)*
β) aa(aaaa)*
γ) (aaaa)*(ε + aa + aaa) — το aaaa απορρίπτεται, άρα λάθος· [δυσανάγνωστο] μπαίνει 2 φορές αυτό
δ) aa(aaa)* → aaaaaaaaa → 8 a → φτάνει σε κατάσταση απόρριψης
ε) (aaa)*(aa+a) — aaaa που απορρίπτεται, άρα λάθος
β) aa(aaaa)* → aa → αποδοχή [κυκλωμένο]
α) ε + aa(aaaa)* [κυκλωμένο] άρα σωστό, γιατί το β δεν περιέχει το ε, ενώ για ε [δυσανάγνωστο]
ε → αποδέχεται
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.