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

Υπολογιστική Πολυπλοκότητα — Θέματα ηλεκτρονικής εξέτασης (Ιούνιος, έτος μη επιβεβαιωμένο)

Μεταγραφή των αρχείων themata_june.pdf (σελίδες 1–5) και tm1.PNG (ερώτηση 1 με κενά).

themata_june.pdf

Ερώτηση 1 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.50 βαθμοί)

Για τη γλώσσα \(L = \{a^n b^n : n \ge 0\}\), ένας απαριθμητής θα εκτυπώσει:
Με \(\epsilon\) αναπαριστούμε την κενή λέξη.

  • [ ] \(a^n b^n\)
  • [ ] \(\{ab, a^2 b^2, a^3 b^3, \dots\}\)
  • [ ] \(\{\epsilon, ab, a^2 b^2, a^3 b^3, \dots\}\)
  • [ ] Καμία επιλογή.

Ερώτηση 2 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.50 βαθμοί)

Έστω ότι ο προϊστάμενός μας σε μία εταιρία σας ζητάει να του φτιάξετε ένα πρόγραμμα που να λύνει ένα μη-διαγνώσιμο πρόβλημα \(\Pi\). Τι θα του απαντήσετε από τα παρακάτω;

  • [ ] Το πρόβλημα είναι μη διαγνώσιμο. Δεν λύνεται. Τέλος!
  • [ ] Και επειδή είναι μη-διαγνώσιμο και τι έγινε; Θα σου φέρω το προγραμματάκι που να το λύνει εντός του μήνα!
  • [ ] Θα σου φέρω ένα πρόγραμμα, αλλά μερικές φορές μπορεί να σου απαντήσει λάθος. Πάντως, επειδή το πρόβλημα είναι μη-διαγνώσιμο, μείωση μισθού δεν θα δεχθώ!
  • [ ] Καμία επιλογή

Ερώτηση 3 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.50 βαθμοί)

Έστω \(L_1\) και \(L_2\) μη-διαγνώσιμες γλώσσες. Τότε, υπάρχει υπερσύνολο του \(L_1 \cup L_2\) που είναι διαγνώσιμο.

  • [ ] Το συμπέρασμα είναι σωστό για κάθε γλώσσα \(L_1\) και \(L_2\)
  • [ ] Το συμπέρασμα είναι λάθος για κάθε γλώσσα \(L_1\) και \(L_2\)
  • [ ] Η αλήθεια του συμπεράσματος εξαρτάται τις γλώσσες \(L_1\) και \(L_2\)
  • [ ] Καμία επιλογή.

Ερώτηση 4 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 1 βαθμός)

Η \(L_1\) είναι μία αναγνωρίσιμη γλώσσα στο αλφάβητο \(\Sigma\). Ένας αλγόριθμος \(A\) απαριθμεί όλες τις λέξεις της \(L_1\) - έστω \(w_1, w_2, w_3, \dots\). Ορίζουμε μία άλλη γλώσσα \(L_2\) στο \(\Sigma \cup \{\#\}\) ως εξής: \(\{w_i \# w_j : w_i, w_j \in L_1, i < j\}\). Το σύμβολο \(\#\) είναι ένα νέο σύμβολο. Έστω οι επόμενοι δύο ισχυρισμοί \(S_1\) και \(S_2\). \(S_1\): Αν η \(L_1\) είναι διαγνώσιμη τότε και \(L_2\) είναι διαγνώσιμη. \(S_2\): Αν η \(L_2\) είναι διαγνώσιμη τότε και η \(L_1\) είναι διαγνώσιμη. Ποια από τις παρακάτω προτάσεις είναι αληθής;

  • [ ] Και οι δύο ισχυρισμοί είναι αληθείς.
  • [ ] Ο \(S_1\) είναι αληθής αλλά ο \(S_2\) δεν είναι απαραίτητα αληθής.
  • [ ] Ο \(S_2\) είναι αληθής αλλά ο \(S_1\) δεν είναι απαραίτητα αληθής.
  • [ ] Και οι δύο δεν είναι απαραίτητα αληθείς.
  • [ ] Καμία επιλογή.

Ερώτηση 1 (Πολλαπλής Επιλογής (Πολλαπλές Απαντήσεις) — 2.50 βαθμοί)

Δίνεται η μηχανή Turing του σχήματος. Να συμπληρώσετε τα κενά με τις κατάλληλες επιλογές.
Με είσοδο aa, η TM ___________ (επιλογή από (1)-(3)). Η TM ___________ (επιλογή από (4)-(5)) διότι ___________ (επιλογή από (6)-(7)). Η γλώσσα της ΤΜ είναι η ___________ (επιλογή από (8)-(11)). (Με ε αναπαριστούμε την κενή λέξη)

[Σχήμα: Διάγραμμα καταστάσεων μηχανής Turing με καταστάσεις \(q_0, q_1, q_2, q_3, q_{\text{ΝΑΙ}}, q_{\text{ΟΧΙ}}\) και μεταβάσεις: \(q_0 \xrightarrow{\sqcup \to \text{A}} q_{\text{ΝΑΙ}}\), \(q_0 \xrightarrow{a \to \Delta} q_1\), \(q_1 \xrightarrow{\sqcup \to a, \Delta} q_{\text{ΟΧΙ}}\), \(q_1 \xrightarrow{a \to \Delta} q_2\), \(q_2\) βρόχος με \(\sqcup \to a, \text{A}\), \(q_2 \xrightarrow{a \to \Delta} q_3\), \(q_3 \xrightarrow{a \to \Delta} q_0\), \(q_3 \xrightarrow{\sqcup \to \text{A}} q_1\).]

  • [ ] (1) αποδέχεται
  • [ ] (2) απορρίπτει
  • [ ] (3) εγκλωβίζεται
  • [ ] (4) είναι διαγνώστης
  • [ ] (5) δεν είναι διαγνώστης
  • [ ] (6) τερματίζει σε οποιαδήποτε συμβολοσειρά
  • [ ] (7) εγκλωβίζεται σε κάποια συμβολοσειρά
  • [ ] \((\epsilon + aa + aaa)(aaa)^*\)
  • [ ] \((\epsilon + a + aa)(aaaa)^*\)
  • [ ] \(\epsilon + (aa + aaa)(aaaa)^*\)
  • [ ] \((\epsilon + aa + aaa)(aaaa)^*\)

Ερώτηση 1 (Πολλαπλής Επιλογής (Πολλαπλές Απαντήσεις) — 2 βαθμοί)

Το παρακάτω αποτελεί τμήμα απόδειξης ότι η γλώσσα B είναι μη διαγνώσιμη χρησιμοποιώντας αναγωγή από τη γλώσσα A.

Απόδειξη: Θα δείξουμε ότι η γλώσσα B είναι μη διαγνώσιμη κάνοντας αναγωγή από τη γνωστή μη διαγνώσιμη γλώσσα A. Έστω λοιπόν ότι η γλώσσα B είναι διαγνώσιμη και έστω R η μηχανή Turing που τη διαγιγνώσκει. Χρησιμοποιώντας την TM R, κατασκευάζουμε TM S που διαγιγνώσκει τη γλώσσα A ως εξής:

S = για είσοδο 1. Κατασκεύασε την TM M' που λειτουργεί ως εξής M' = για είσοδο x 1. Αν x = "aaa", τότε αποδέξου 2. Αλλιώς, αν x != "aaa", τότε προσομοίωσε την TM M με είσοδο w 3. Αν η M αποδεχτεί, τότε αποδέξου 4. Αν η M απορρίψει, τότε απόρριψε 2. Εκτέλεσε την TM R με είσοδο <M'> 3. Αν η R αποδεχτεί, τότε απόρριψε 4. Αν η R απορρίψει, τότε αποδέξου

Καθώς γνωρίζουμε ότι η γλώσσα A είναι μη διαγνώσιμη, καταλήγουμε σε άτοπο. Έτσι, έχουμε αποδείξει ότι, αντίθετα με την υπόθεσή μας, η γλώσσα B είναι μη διαγνώσιμη.

Από την παραπάνω απόδειξη, έχει παραληφθεί η απόδειξη ορθότητας της S (δηλαδή, ότι είναι πράγματι διαγνώστης της γλώσσας A). Απαντήστε αν οι παρακάτω συνδυασμοί για τις γλώσσες A και B οδηγούν σε σωστή ή λανθασμένη αναγωγή.

  • [ ] A = ΑΠΟΔΟΧΗ/ΤΜ και B = {: η M είναι TM που δεν αποδέχεται την κενή συμβολοσειρά}
  • [ ] A = ΠΕΡΑΤΩΣΗ/ΤΜ και B = {: η M είναι TM που δεν τερματίζει με είσοδο την κενή συμβολοσειρά}
  • [ ] A = ΠΕΡΑΤΩΣΗ/ΤΜ και B = ΚΕΝΟΤΗΤΑ/ΤΜ
  • [ ] A = ΑΠΟΔΟΧΗ/ΤΜ και B = {: η M είναι TM που τερματίζει μόνο για τη συμβολοσειρά aaa}
  • [ ] A = ΠΕΡΑΤΩΣΗ/ΤΜ και B = {: η M είναι TM που τερματίζει για όλες τις εισόδους}

Ερώτηση 1 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.30 βαθμοί)

Κάθε ετικέτα στο παρακάτω διάγραμμα εγκλεισμού κλάσεων αντιστοιχεί σε μία κλάση υπολογισιμότητας ή πολυπλοκότητας. Με δεδομένο ότι \(P \neq NP\), να επιλέξετε τη σωστή αντιστοίχιση που να σέβεται τις σχέσεις εγκλεισμού.

Το πρόθεμα co στην κλάση X αντιστοιχεί στο συμπλήρωμα της κλάσης X.

[Σχήμα: Εγκιβωτισμένα ελλειπτικά σχήματα με ετικέτες α, β, γ, δ, ε, στ, από το εξωτερικό προς το εσωτερικό· κάθε σχήμα περιέχεται στο προηγούμενο.]

  • [ ] (α) Διαγνώσιμη (β) Μη-Αναγνωρίσιμη (γ) \(\text{co}NP\) (δ) \(NTIME(n^2)\) (ε) \(P\) (στ) \(SPACE(n^3)\)
  • [ ] (α) Μη-Αναγνωρίσιμη (β) Διαγνώσιμη (γ) \(EXPTIME\) (δ) \(NTIME(n^2)\) (ε) \(NP\) (στ) \(\text{co}P\)
  • [ ] (α) Διαγνώσιμη (β) \(EXPTIME\) (γ) \(NPSPACE\) (δ) \(\text{co}NP\) (ε) \(P\) (στ) \(NTIME(n^2)\)
  • [ ] (α) Διαγνώσιμη (β) \(\text{co}NP\) (γ) \(P\) (δ) \(NPSPACE\) (ε) \(NTIME(n^3)\) (στ) \(SPACE(n^3)\)
  • [ ] Καμία Επιλογή.

Ερώτηση 2 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.30 βαθμοί)

Έστω S ένα πρόβλημα που ανήκει στην κλάση NP. Ποια από τις παρακάτω προτάσεις είναι αληθής;

  • [ ] Δεν υπάρχει πολυωνυμικός ανταιτιοκρατικός αλγόριθμος για το S.
  • [ ] Αν το S λύνεται σε αιτιοκρατικό πολυωνυμικό χρόνο τότε P = NP.
  • [ ] Αν το S είναι NP-δυσχερές τότε είναι NP-πλήρες.
  • [ ] Το S μπορεί να είναι μη-διαγνώσιμο.
  • [ ] Καμία Επιλογή.

Ερώτηση 3 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.30 βαθμοί)

Ποιο από τα παρακάτω προβλήματα δεν είναι NP-δυσχερές δεδομένου ότι \(P \neq NP\);

  • [ ] Hamiltonian διαδρομή
  • [ ] 3SAT
  • [ ] 2SAT
  • [ ] Πρόβλημα Τερματισμού (Halting)
  • [ ] Καμία Επιλογή.

Ερώτηση 4 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.30 βαθμοί)

Έστω ότι το πρόβλημα \(Y\) είναι NP-πλήρες και έστω ότι το πρόβλημα \(X\) ανάγεται απεικονιστικά σε πολυωνυμικό χρόνο στο \(Y\). Ποια από τις παρακάτω προτάσεις ισχύει;

  • [ ] Αν το \(X\) λύνεται σε πολυωνυμικό χρόνο τότε και το \(Y\) λύνεται σε πολυωνυμικό χρόνο
  • [ ] το \(X\) είναι NP-πλήρες
  • [ ] το \(X\) είναι NP-δυσχερές
  • [ ] το \(X\) ανήκει στην κλάση NP αλλά δεν είναι απαραίτητα NP-πλήρης
  • [ ] Καμία Επιλογή.

Ερώτηση 5 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.30 βαθμοί)

Έστω ότι υπάρχει ένα εκθετικό κάτω φράγμα για το πρόβλημα του αν ένας λογικός τύπος σε κανονική συζευκτική μορφή είναι αληθεύσιμος (αυτό σημαίνει ότι αποκλείεται να υπάρχει αιτιοκρατικός πολυωνυμικός αλγόριθμος για αυτό το πρόβλημα). Σε αυτή την περίπτωση να αναφέρετε ποιο από τα παρακάτω 4 διαγράμματα περιγράφει σωστά τις σχέσεις μεταξύ των κλάσεων P, NP και NPC.

[Σχήμα: Τέσσερα διαγράμματα: (α) Ένας κύκλος με ένδειξη P=NP=NPC. (β) Δύο κύκλοι NP και P που τέμνονται, με την κοινή περιοχή να ονομάζεται NPC. (γ) Κύκλος με ένδειξη NP=P που περιέχει μικρότερο κύκλο NPC. (δ) Κύκλος NP που περιέχει δύο κύκλους: έναν μικρό NPC κοντά στο εξωτερικό όριο και έναν κύκλο P στο εσωτερικό.]

  • [ ] (α)
  • [ ] (β)
  • [ ] (γ)
  • [ ] (δ)
  • [ ] Καμία Επιλογή.

Ερώτηση 1 (Συμπλήρωση Κενών (Χαλαρή Ταυτοποίηση) — 2 βαθμοί)

Έστω μία συλλογή συνόλων \(\{P_1, P_2, \dots, P_m\}\) έτσι ώστε για κάθε \(i\) να ισχύει ότι το \(P_i\) είναι υποσύνολο ενός συνόλου \(X\). Έστω το εξής πρόβλημα: \(ULSC = \{\langle \{X, \{P_1, P_2, \dots, P_m\}, p, q\} \rangle : \text{υπάρχει μία συλλογή από τουλάχιστον } p \text{ και το πολύ } q \text{ υποσύνολα } P_i \text{ του } X \text{ των οποίων η ένωση δίνει το } X\}\). Θέλουμε να δείξουμε ότι το πρόβλημα \(ULSC\) είναι NP-πλήρες.

Το πρώτο βήμα είναι να δείξουμε ότι το πρόβλημα \(ULSC\) ανήκει στη κλάση [ ] (1). Αυτό μπορούμε να το κάνουμε με δύο τρόπους: α) να κατασκευάσουμε μία [ ] (2) ΤΜ που σε [ ] (3) χρόνο να λύνει το πρόβλημα ή β) να κατασκευάσουμε έναν αιτιοκρατικό πολυωνυμικό [ ] (4) όπου το πιστοποιητικό θα είναι [ ] (5). Αυτό το πιστοποιητικό έχει [ ] (6) μέγεθος και μπορούμε να το ελέγξουμε αποδοτικά. Το δεύτερο βήμα είναι να βρούμε το κατάλληλο πρόβλημα από το οποίο θα κάνουμε αναγωγή. Θα επιλέξουμε να αποδείξουμε πολύ εύκολα την NP-πληρότητα του προβλήματος \(ULSC\) με περιορισμό. Το πρόβλημα που επιλέγουμε για να αποτελέσει περιορισμό του \(ULSC\) είναι το (δώστε πλήρη ορισμό του προβλήματος) [ ] (7), το οποίο γνωρίζουμε ήδη ότι είναι NP-πλήρες. Πράγματι, αν [ ] (8) τότε το πρόβλημα \(ULSC\) μετασχηματίζεται σε αυτό που δόθηκε στο (7). Άρα το πρόβλημα \(ULSC\) είναι NP-πλήρες.

Ερώτηση 2 (Πολλαπλής Επιλογής (Πολλαπλές Απαντήσεις) — 1 βαθμός)

Θεωρήστε την παρακάτω αναγωγή \(f\) από το πρόβλημα ΧΑΜΙΛΤΟΝΙΑΝΟΣΚΥΚΛΟΣ στο πρόβλημα ΜΑΚΡΥΤΕΡΗΔΙΑΔΡΟΜΗ. Επιλέξτε τις σωστές προτάσεις.

ΧΑΜΙΛΤΟΝΙΑΝΟΣΚΥΚΛΟΣ: Δίνεται μη-κατευθυνόμενο γράφημα \(G\). Υπάρχει μη-κατευθυνόμενος κύκλος που περνά από κάθε κόμβο του γραφήματος \(G\) ακριβώς μια φορά;

ΜΑΚΡΥΤΕΡΗΔΙΑΔΡΟΜΗ: Δίνεται μη-κατευθυνόμενο γράφημα \(H\) και δύο κόμβοι του \(s\) και \(t\) και ένας ακέραιος \(k\). Υπάρχει απλή διαδρομή (δεν απαναλαμβάνονται κόμβοι) από τον κόμβο \(s\) στον κόμβο \(t\) μήκους τουλάχιστον \(k\); Το μήκος μίας διαδρομής είναι ίσο με το πλήθος των ακμών που διαπερνά.

Αναγωγή \(f\): Με είσοδο το μη-κατευθυνόμενο γράφημα \(G\), η \(f\) επιστρέφει ως γράφημα \(H\) το ίδιο γράφημα \(G\) καθώς και δύο αυθαίρετους αλλά διαφορετικούς κόμβους \(s\) και \(t\). Επίσης, αν \(n\) είναι το πλήθος των κόμβων του \(G\), τότε η \(f\) θέτει \(k = n - 1\).

Αποσαφήνιση: Ένα ΝΑΙ-Στιγμιότυπο ενός προβλήματος είναι ένα στιγμιότυπο που ανήκει στην αντίστοιχη γλώσσα (π.χ., ένα ΝΑΙ-στιγμιότυπο της ΧΑΜΙΛΤΟΝΙΑΝΗΔΙΑΔΡΟΜΗΣ είναι ένα γράφημα που έχει Χαμιλτονιανή διαδρομή). Αντίστοιχα ορίζεται και ένα ΟΧΙ-στιγμιότυπο.

  • [ ] Είναι αναγωγή πολυωνυμικού χρόνου.
  • [ ] Η αναγωγή δεν είναι πολυωνυμικού χρόνου.
  • [ ] Η αναγωγή δεν είναι σωστή καθώς υπάρχει ΝΑΙ-στιγμιότυπο του προβλήματος ΧΑΜΙΛΤΟΝΙΑΝΟΣΚΥΚΛΟΣ που αντιστοιχίζεται σε ΟΧΙ-στιγμιότυπο του προβλήματος ΜΑΚΡΥΤΕΡΗΔΙΑΔΡΟΜΗ.
  • [ ] Η αναγωγή δεν είναι σωστή καθώς υπάρχει ΟΧΙ-στιγμιότυπο του προβλήματος ΧΑΜΙΛΤΟΝΙΑΝΟΣΚΥΚΛΟΣ που αντιστοιχίζεται σε ΝΑΙ-στιγμιότυπο του προβλήματος ΜΑΚΡΥΤΕΡΗΔΙΑΔΡΟΜΗ.

tm1.PNG

Ερώτηση 1 (Πολλαπλής Επιλογής (Πολλαπλές Απαντήσεις) — 2.50 βαθμοί)

Δίνεται η μηχανή Turing του σχήματος. Να συμπληρώσετε τα κενά με τις κατάλληλες επιλογές.

Με είσοδο \(\alpha\alpha\), η TM ________ (επιλογή από (1)-(3)). Η TM ________ (επιλογή από (4)-(5)) διότι ________ (επιλογή από (6)-(7)). Η γλώσσα της TM είναι η ________ (επιλογή από (8)-(11)). (Με \(\varepsilon\) αναπαριστούμε την κενή λέξη)

[Σχήμα: μηχανή Turing με καταστάσεις q_ΝΑΙ, q_0, q_1, q_2, q_3, q_ΟΧΙ. Μεταβάσεις: q_0 → q_ΝΑΙ: ⊔ → A· q_0 → q_1: α → Δ· q_1 → q_ΟΧΙ: ⊔ → α, Δ· q_1 → q_2: α → Δ· q_2 → q_2 (βρόχος): ⊔ → α, A· q_2 → q_3: α → Δ· q_3 → q_0: α → Δ· q_3 → q_1: ⊔ → A]

  • [ ] (1) αποδέχεται
  • [ ] (2) απορρίπτει
  • [ ] (3) εγκλωβίζεται
  • [ ] (4) είναι διαγνώστης
  • [ ] (5) δεν είναι διαγνώστης
  • [ ] (6) τερματίζει σε οποιαδήποτε συμβολοσειρά
  • [ ] (7) εγκλωβίζεται σε κάποια συμβολοσειρά
  • [ ] \((\varepsilon+\alpha\alpha+\alpha\alpha\alpha)(\alpha\alpha\alpha)^*\)
  • [ ] \((\varepsilon+\alpha+\alpha\alpha)(\alpha\alpha\alpha\alpha)^*\)
  • [ ] \(\varepsilon+(\alpha\alpha+\alpha\alpha\alpha)(\alpha\alpha\alpha\alpha)^*\)
  • [ ] \((\varepsilon+\alpha\alpha+\alpha\alpha\alpha)(\alpha\alpha\alpha\alpha)^*\)

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