Υπολογιστική θεωρία πολυπλοκότητας
- 1. Η θεωρία της υπολογιστικής πολυπλοκότητας είναι ένας κλάδος της θεωρητικής επιστήμης των υπολογιστών που επικεντρώνεται στην ταξινόμηση υπολογιστικών προβλημάτων με βάση την εγγενή δυσκολία τους και την ποσότητα των απαιτούμενων πόρων, όπως ο χρόνος και ο χώρος. Ασχολείται με την κατανόηση της αποτελεσματικότητας των αλγορίθμων, την ανάλυση της σκοπιμότητας επίλυσης προβλημάτων σε διαφορετικούς τύπους μηχανών και τον προσδιορισμό των περιορισμών της υπολογιστικής ισχύος. Μελετώντας τη θεωρία της υπολογιστικής πολυπλοκότητας, οι ερευνητές επιδιώκουν να διερευνήσουν τα όρια του υπολογισμού και να εντοπίσουν τις δυνατότητες και τους περιορισμούς των υπολογιστών στην επίλυση διαφόρων τύπων προβλημάτων. Σε τι εστιάζει η θεωρία της υπολογιστικής πολυπλοκότητας;
A) Ψυχολογικές πτυχές της αλληλεπίδρασης ανθρώπου-υπολογιστή
B) Ανάλυση των πόρων που απαιτούνται για την επίλυση υπολογιστικών προβλημάτων
C) Σχεδιασμός υλικού για υπολογιστές
D) Ανάπτυξη νέων γλωσσών προγραμματισμού
- 2. Ποια σημειογραφία χρησιμοποιείται συνήθως για να δηλώσει την πολυπλοκότητα των αλγορίθμων;
A) Ελληνικά γράμματα
B) Δυάδικος κώδικας
C) Σημείωση Big O
D) λατινικούς αριθμούς
- 3. Ποια κατηγορία πολυπλοκότητας περιέχει προβλήματα απόφασης που είναι αποτελεσματικά επαληθεύσιμα;
A) BPP
B) PSPACE
C) NP
D) ΛΗΞΗ
- 4. Ποιος είναι ο κύριος στόχος της θεωρίας υπολογιστικής πολυπλοκότητας;
A) Για να δημιουργήσετε ταχύτερους υπολογιστές
B) Για την κατασκευή υπερυπολογιστών
C) Να ταξινομεί υπολογιστικά προβλήματα με βάση την εγγενή δυσκολία τους
D) Για τη δημιουργία τυχαίων αριθμών
- 5. Ποια τάξη πολυπλοκότητας χρησιμοποιείται για την ταξινόμηση προβλημάτων που μπορούν να λυθούν από έναν κβαντικό υπολογιστή σε πολυωνυμικό χρόνο;
A) PSPACE
B) BQP
C) EXPSPACE
D) NP-πλήρες
- 6. Ποια είναι η κατηγορία πολυπλοκότητας που αντιπροσωπεύει τα δυσκολότερα προβλήματα στο NP;
A) NP-πλήρες
B) BPP
C) Π
D) EXPTIME
- 7. Τι σημαίνει «EXP» στη θεωρία υπολογιστικής πολυπλοκότητας;
A) Εκθετικός χρόνος
B) Ειδικός
C) Εξερευνητικός
D) Αναπτυγμένος
- 8. Με τι σχετίζεται το θεώρημα Cook-Levin στη θεωρία της υπολογιστικής πολυπλοκότητας;
A) NP-πληρότητα
B) Παράλληλος υπολογισμός
C) Πρόβλημα P εναντίον NP
D) Κβαντικοί αλγόριθμοι
|