Θεωρία Υπολογισμού και Πολυπλοκότητα — Αύγουστος 2022 (Υπολογιστική Πολυπλοκότητα)¶
Μεταγραφή από τις σελίδες θεμάτων του κειμένου του PDF «CC_Exams-31-08-2022.pdf» (πλήρες text layer).
CC_Exams-31-08-2022.pdf (σελ. 1,2,3,4)¶
ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ « ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ »¶
31/08/2022
Διάρκεια Εξέτασης (2 ώρες και 30 λεπτά) – Ομάδα Α
1. (15 μονάδες)¶
α) (7) Έστω ότι σας δίνεται μία ΤΜ 𝛭, μία είσοδος 𝑥 (που βρίσκεται στην αρχή της ταινίας) και ένας φυσικός αριθμός 𝑘. Ορίζουμε το εξής πρόβλημα:
𝐵𝑆𝐶= {〈𝑀, 𝑥, 𝑘〉: 𝛨 𝛵𝛭 𝛭 𝜏𝜀𝜌𝜇𝛼𝜏ί𝜁𝜀𝜄 𝜎𝜀 𝜀ί𝜎𝜊𝛿𝜊 𝑥 𝜒𝜌𝜂𝜎𝜄𝜇𝜊𝜋𝜊𝜄ώ𝜈𝜏𝛼𝜍 𝜏𝜊 𝜋𝜊𝜆ύ 𝑘 𝜃έ𝜎𝜀𝜄𝜍 𝜇𝜈ή𝜇𝜂𝜍} Είναι το 𝐵𝑆𝐶 διαγνώσιμο; Αιτιολογήστε την απάντησή σας.
β) (8) Έστω η γλώσσα 𝐴= {𝑎𝑛 𝑏𝑛 : 𝑛≥0}, που ανήκει στο 𝑃. Θα δείξουμε ότι 3𝑆𝐴𝑇≤𝑃 𝐴. Η αναγωγή είναι η εξής:
𝛼𝜈 𝜂 𝜑 έ𝜒𝜀𝜄 𝛼𝜆𝜂𝜃𝜊𝜋𝜊𝜄ό 𝜏𝜄𝜇𝜊𝛿𝜊𝜎ί𝛼 𝑓(〈𝜑〉) = {𝑎𝑎𝑏𝑏 𝑎𝑎𝑏 𝛿𝜄𝛼𝜑𝜊𝜌𝜀𝜏𝜄𝜅ά
όπου 𝜑 λογικός τύπος. Αφού 3𝑆𝐴𝑇∈𝑁𝑃𝐶, 3𝑆𝐴𝑇≤ 𝑃 𝐴 και 𝐴∈𝑃 συνεπάγεται ότι 𝑃= 𝑁𝑃. Να δείξετε ποιο είναι το «λάθος» σε αυτή την απόδειξη ότι 𝑃= 𝑁𝑃 εστιάζοντας στην αναγωγή.
2. (30 μονάδες)¶
(Α) (8) Έστω οι εξής γλώσσες:
2𝑆𝐴𝑇= {〈𝜑〉: 𝜊 𝜆ό𝛾𝜄𝜅𝜊𝜍 𝜏ύ𝜋𝜊𝜍 𝜑 𝜎𝜀 2 −𝜅𝛼𝜈𝜊𝜈𝜄𝜅ή 𝜎𝜐𝜁𝜀𝜐𝜅𝜏𝜄𝜅ή 𝜇𝜊𝜌𝜑ή 𝜀ί𝜈𝛼𝜄 𝛼𝜆𝜂𝜃𝜀ύ𝜎𝜄𝜇𝜊𝜍} ≥𝑊 𝜅𝛼𝜄 ∑𝑤𝑗 𝐾𝑁𝐴𝑃𝑆𝐴𝐶𝐾= {〈{𝑣1, … , 𝑣𝑛}, {𝑤1, … , 𝑤𝑛}, 𝑘, 𝑊〉: ∃𝐼⊆{1, … , 𝑛} έ𝜏𝜎𝜄 ώ𝜎𝜏𝜀 ∑𝑣𝑗∈𝐼 𝑗 𝑗∈𝐼 ≤𝑘}
Χαρακτηρίστε ως αληθείς ή ψευδείς τις παρακάτω δηλώσεις και δώστε σύντομη αιτιολόγηση. Για τις απαντήσεις σας θεωρήστε ότι 𝑃≠𝑁𝑃.
α. (2) Το πρόβλημα 2𝑆𝐴𝑇 ανήκει στην κλάση 𝑁𝑃.
β. (3) Υπάρχει αναγωγή του προβλήματος 2𝑆𝐴𝑇≤𝑃 𝐾𝑁𝐴𝑃𝑆𝐴𝐶𝐾.
γ. (3) Υπάρχει αναγωγή του προβλήματος 𝐾𝑁𝐴𝑃𝑆𝐴𝐶𝐾≤𝑃 2𝑆𝐴𝑇.
(Β) (22) Έστω μία μηχανή και ένα σύνολο εργασιών {𝑞1, 𝑞2, … , 𝑞𝑛} προς εκτέλεση στη μηχανή. Κάθε εργασία 𝑞𝑖 (1 ≤𝑖≤𝑛) απαιτεί χρόνο επεξεργασίας 𝑝𝑖, έχει κέρδος 𝑤𝑖 και έχει μία προθεσμία 𝑑𝑖. Θα πρέπει να δρομολογήσουμε τις εργασίες στη μηχανή με τον περιορισμό ότι η μηχανή εκτελεί το πολύ μία εργασία σε κάθε χρονική στιγμή και από τη στιγμή που μία εργασία 𝑞𝑖 ξεκινήσει να εκτελείται θα πρέπει να εκτελεσθεί για χρόνο 𝑝𝑖. Οι εργασίες 𝑞𝑖 που ολοκληρώνονται πριν την προθεσμία τους, μας δίνουν κέρδος 𝑤𝑖, αλλιώς το κέρδος που αποκομίζουμε είναι 0. Δείξτε ότι το πρόβλημα απόφασης για το αν υπάρχει πρόγραμμα δρομολόγησης με συνολικό κέρδος τουλάχιστον 𝑊 είναι NP-πλήρες.
Υπόδειξη: Χρησιμοποιήστε (χωρίς να είναι δεσμευτικό) αναγωγή με περιορισμό από το κατάλληλο πρόβλημα.
3. (30 μονάδες) Θα ονομάζουμε άχρηστη μία κατάσταση σε μία ΤΜ Μ αν για οποιαδήποτε είσοδο η Μ δεν διέρχεται από αυτή την κατάσταση ποτέ. Έστω το πρόβλημα καθορισμού του αν μία δοθείσα κατάσταση είναι άχρηστη.
α) (4) Να εκφράσετε τυπικά το συγκεκριμένο πρόβλημα ως γλώσσα (ονοματίστε τη γλώσσα ως 𝑈𝐿 – δείτε ως παράδειγμα την εκφώνηση της άσκησης 2(Α)).
β) (15) Να αποδείξετε ότι η συγκεκριμένη γλώσσα είναι μη-διαγνώσιμη (προτείνεται – χωρίς να είναι δεσμευτικό – να χρησιμοποιήσετε για την αναγωγή τη γλώσσα 𝛫𝛦𝛮𝛰𝛵𝛨𝛵𝛢𝛵𝛭 = {〈𝛭〉: 𝐿(𝑀) = ∅}) γ) (4) Η συμπληρωματική γλώσσα 𝑐𝑜−𝑈𝐿 είναι διαγνώσιμη ή μη-διαγνώσιμη (με αιτιολόγηση); δ) (7) Η 𝑈𝐿 είναι αναγνωρίσιμη, συμπληρωματικά αναγνωρίσιμη ή τίποτα από τα δύο (με αιτιολόγηση);
4. (20 μονάδες) Έστω η αιτιοκρατική ΤΜ 𝛭 όπου 𝛴= {𝛼} και 𝛤= {𝛼, ⌴} με τη διπλανή συνάρτηση μετάβασης. Έστω ότι η αρχική κατάσταση είναι η 𝑞0, η κατάσταση απόρριψης είναι η 𝑞𝑟 και η κατάσταση αποδοχής είναι η 𝑞𝛼. Είναι η 𝛭 διαγνώστης; Ποια είναι η γλώσσα που αναγνωρίζει η 𝛭; Σε κάθε περίπτωση αιτιολογήστε την απάντησή σας.
q3
α →Δ α →Δ
q1
⌴ →α,A
q 0 α →Δ
⌴ →Δ
⌴ →Δ
α →Δ
q2
qr qa
5. (20 μονάδες) Να αναφέρετε για κάθε μία πρόταση αν είναι Αληθής ή Ψευδής χωρίς αιτιολόγηση. Σε αυτό το θέμα εφαρμόζεται αρνητική βαθμολόγηση. Κάθε σωστή απάντηση δίνει +0.2 και κάθε λάθος -0.2. Η αρνητική βαθμολόγηση μεταφέρεται και εκτός της συγκεκριμένης άσκησης.
-
i. Αν A ≤ mB και η Α είναι αναγνωρίσιμη τότε και η Β είναι αναγνωρίσιμη
-
ii. Το σύνολο όλων των γλωσσών στο αλφάβητο Σ={0,1} είναι υπεραριθμήσιμο.
-
iii. Αν ΝP=co-NP τότε P=NP.
-
iv. Σε μία ΤΜ το αλφάβητο της ταινίας μπορεί να συμπίπτει με το αλφάβητο της εισόδου.
-
v. Η κλάση των NP-δυσχερών προβλημάτων εμπεριέχουν την κλάση NPC.
-
vi. Δεν γνωρίζουμε αν η κλάση NP είναι κλειστή ως προς την πράξη του συμπληρώματος.
-
vii. Υπάρχουν αριθμοί περιγράψιμοι που δεν είναι υπολογίσιμοι.
-
viii. Το σύνολο των μη-διαγνώσιμων γλωσσών αποτελείται από αναγνωρίσιμες και συμπληρωματικά αναγνωρίσιμες γλώσσες.
-
ix. Η κλάση των διαγνώσιμων γλωσσών είναι κλειστή ως προς την πράξη της ένωσης.
-
x. Το θεώρημα των Cook-Levin αναφέρει ότι οποιοσδήποτε αλγόριθμος μπορεί να αναπαρασταθεί από μία ΤΜ.
Καλή Επιτυχία!!!¶
ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ « ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ » 31/08/2022
Διάρκεια Εξέτασης (2 ώρες και 30 λεπτά) – Ομάδα B
1. (30 μονάδες) Θα ονομάζουμε άχρηστη μία κατάσταση σε μία ΤΜ Μ αν για οποιαδήποτε είσοδο η Μ δεν διέρχεται από αυτή την κατάσταση ποτέ. Έστω το πρόβλημα καθορισμού του αν μία δοθείσα κατάσταση είναι άχρηστη.
α) (4) Να εκφράσετε τυπικά το συγκεκριμένο πρόβλημα ως γλώσσα (ονοματίστε τη γλώσσα ως 𝑈𝐿 – δείτε ως παράδειγμα την εκφώνηση της άσκησης 2(Α)).
β) (15) Να αποδείξετε ότι η συγκεκριμένη γλώσσα είναι μη-διαγνώσιμη (προτείνεται – χωρίς να είναι δεσμευτικό – να χρησιμοποιήσετε για την αναγωγή τη γλώσσα 𝛫𝛦𝛮𝛰𝛵𝛨𝛵𝛢𝛵𝛭 = {〈𝛭〉: 𝐿(𝑀) = ∅}) γ) (4) Η συμπληρωματική γλώσσα 𝑐𝑜−𝑈𝐿 είναι διαγνώσιμη ή μη-διαγνώσιμη (με αιτιολόγηση);
δ) (7) Η 𝑈𝐿 είναι αναγνωρίσιμη, συμπληρωματικά αναγνωρίσιμη ή τίποτα από τα δύο (με αιτιολόγηση);
2. (30 μονάδες)¶
(Α) (8) Έστω οι εξής γλώσσες:
2𝑆𝐴𝑇= {〈𝜑〉: 𝜊 𝜆ό𝛾𝜄𝜅𝜊𝜍 𝜏ύ𝜋𝜊𝜍 𝜑 𝜎𝜀 2 −𝜅𝛼𝜈𝜊𝜈𝜄𝜅ή 𝜎𝜐𝜁𝜀𝜐𝜅𝜏𝜄𝜅ή 𝜇𝜊𝜌𝜑ή 𝜀ί𝜈𝛼𝜄 𝛼𝜆𝜂𝜃𝜀ύ𝜎𝜄𝜇𝜊𝜍} ≥𝑊 𝜅𝛼𝜄 ∑𝑤𝑗 𝐾𝑁𝐴𝑃𝑆𝐴𝐶𝐾= {〈{𝑣1, … , 𝑣𝑛}, {𝑤1, … , 𝑤𝑛}, 𝑘, 𝑊〉: ∃𝐼⊆{1, … , 𝑛} έ𝜏𝜎𝜄 ώ𝜎𝜏𝜀 ∑𝑣𝑗∈𝐼 𝑗 𝑗∈𝐼 ≤𝑘}
Χαρακτηρίστε ως αληθείς ή ψευδείς τις παρακάτω δηλώσεις και δώστε σύντομη αιτιολόγηση. Για τις απαντήσεις σας θεωρήστε ότι 𝑃≠𝑁𝑃.
α. (2) Το πρόβλημα 2𝑆𝐴𝑇 ανήκει στην κλάση 𝑁𝑃.
β. (3) Υπάρχει αναγωγή του προβλήματος 2𝑆𝐴𝑇≤𝑃 𝐾𝑁𝐴𝑃𝑆𝐴𝐶𝐾.
γ. (3) Υπάρχει αναγωγή του προβλήματος 𝐾𝑁𝐴𝑃𝑆𝐴𝐶𝐾≤𝑃 2𝑆𝐴𝑇.
(Β) (22) Έστω μία μηχανή και ένα σύνολο εργασιών {𝜀1, 𝜀2, … , 𝜀𝑚} προς εκτέλεση στη μηχανή. Κάθε εργασία 𝜀𝑖 (1 ≤𝑖≤𝑚) απαιτεί χρόνο επεξεργασίας 𝜋𝑖 , έχει κέρδος 𝜅𝑖 και έχει μία προθεσμία 𝜌𝑖 . Θα πρέπει να δρομολογήσουμε τις εργασίες στη μηχανή με τον περιορισμό ότι η μηχανή εκτελεί το πολύ μία εργασία σε κάθε χρονική στιγμή και από τη στιγμή που μία εργασία 𝜀𝑖 ξεκινήσει να εκτελείται θα πρέπει να εκτελεσθεί για χρόνο 𝜋𝑖. Οι εργασίες 𝜀𝑖 που ολοκληρώνονται πριν την προθεσμία τους, μας δίνουν κέρδος 𝜅𝑖 , αλλιώς το κέρδος που αποκομίζουμε είναι 0. Δείξτε ότι το πρόβλημα απόφασης για το αν υπάρχει πρόγραμμα δρομολόγησης με συνολικό κέρδος τουλάχιστον 𝛫 είναι NP-πλήρες.
Υπόδειξη: Χρησιμοποιήστε (χωρίς να είναι δεσμευτικό) αναγωγή με περιορισμό από το κατάλληλο πρόβλημα.
3. (15 μονάδες)¶
α) (7) Έστω ότι σας δίνεται μία ΤΜ 𝛭, μία είσοδος 𝑦 (που βρίσκεται στην αρχή της ταινίας) και ένας φυσικός αριθμός ℓ. Ορίζουμε το εξής πρόβλημα:
𝐶𝐵𝑆= {〈𝑀, 𝑦, ℓ〉: 𝛨 𝛵𝛭 𝛭 𝜏𝜀𝜌𝜇𝛼𝜏ί𝜁𝜀𝜄 𝜎𝜀 𝜀ί𝜎𝜊𝛿𝜊 𝑦 𝜒𝜌𝜂𝜎𝜄𝜇𝜊𝜋𝜊𝜄ώ𝜈𝜏𝛼𝜍 𝜏𝜊 𝜋𝜊𝜆ύ ℓ 𝜃έ𝜎𝜀𝜄𝜍 𝜇𝜈ή𝜇𝜂𝜍} Είναι το 𝐶𝐵𝑆 διαγνώσιμο; Αιτιολογήστε την απάντησή σας.
β) (8) Έστω η γλώσσα 𝐵= {1𝑛 0𝑛 : 𝑛≥0}, που ανήκει στο 𝑃. Θα δείξουμε ότι 3𝑆𝐴𝑇≤𝑃 𝐵. Η αναγωγή είναι η εξής:
𝛼𝜈 𝜂 𝜑 έ𝜒𝜀𝜄 𝛼𝜆𝜂𝜃𝜊𝜋𝜊𝜄ό 𝜏𝜄𝜇𝜊𝛿𝜊𝜎ί𝛼 𝑓(〈𝜑〉) = {111000 110 𝛿𝜄𝛼𝜑𝜊𝜌𝜀𝜏𝜄𝜅ά
όπου 𝜑 λογικός τύπος. Αφού 3𝑆𝐴𝑇∈𝑁𝑃𝐶, 3𝑆𝐴𝑇≤ 𝑃 𝐵 και 𝐵∈𝑃 συνεπάγεται ότι 𝑃= 𝑁𝑃. Να δείξετε ποιο είναι το «λάθος» σε αυτή την απόδειξη ότι 𝑃= 𝑁𝑃 εστιάζοντας στην αναγωγή.
4. (20 μονάδες) Να αναφέρετε για κάθε μία πρόταση αν είναι Αληθής ή Ψευδής χωρίς αιτιολόγηση. Σε αυτό το θέμα εφαρμόζεται αρνητική βαθμολόγηση. Κάθε σωστή απάντηση δίνει +0.2 και κάθε λάθος -0.2. Η αρνητική βαθμολόγηση μεταφέρεται και εκτός της συγκεκριμένης άσκησης.
-
i. Αν A ≤ mB και η B είναι αναγνωρίσιμη τότε και η A είναι αναγνωρίσιμη
-
ii. Το σύνολο όλων των γλωσσών στο αλφάβητο Σ={0,1} είναι αριθμήσιμο.
-
iii. Αν ΝP≠co-NP τότε P=NP.
-
iv. Σε μία ΤΜ το αλφάβητο της ταινίας δεν μπορεί να συμπίπτει με το αλφάβητο της εισόδου.
-
v. Η κλάση των NP-δυσχερών προβλημάτων εμπεριέχουν την κλάση NPC.
-
vi. Δεν γνωρίζουμε αν η κλάση NP είναι κλειστή ως προς την πράξη της ένωσης.
-
vii. Υπάρχουν πραγματικοί αριθμοί που δεν είναι περιγράψιμοι.
-
viii. Το σύνολο των μη-διαγνώσιμων γλωσσών αποτελείται από αναγνωρίσιμες και συμπληρωματικά αναγνωρίσιμες γλώσσες.
-
ix. Η κλάση των διαγνώσιμων γλωσσών είναι κλειστή ως προς την πράξη του συμπληρώματος.
-
x. Το αξίωμα των Church-Turing αναφέρει ότι οποιοσδήποτε αλγόριθμος μπορεί να αναπαρασταθεί από μία ΤΜ.
5. (20 μονάδες) Έστω η αιτιοκρατική ΤΜ 𝛭 όπου 𝛴= {1} και 𝛤= {1, ⌴} με τη διπλανή συνάρτηση μετάβασης. Έστω ότι η αρχική κατάσταση είναι η 𝑞0, η κατάσταση απόρριψης είναι η 𝑞𝑟 και η κατάσταση αποδοχής είναι η 𝑞𝛼. Είναι η 𝛭 διαγνώστης; Ποια είναι η γλώσσα που αναγνωρίζει η 𝛭; Σε κάθε περίπτωση αιτιολογήστε την απάντησή σας.
q3
1 →Δ 1 →Δ
q1
⌴ → 1 ,A
q 0 1 →Δ
⌴ →Δ
⌴ →Δ
1 →Δ
q2
qr qa