Computational Complexity

Course Code: 
CEID_NY302
Type: 
Semester: 
Instructors: 
Credit Points: 
4

Μηχανές Turing. Ειδικοί τύποι και συνδυασμοί μηχανών Turing. Μη ντετερμινιστικές μηχανές Turing. Καθολικές μηχανές Turing. Αλγοριθμικά επιλύσιμα προβλήματα. Η θέση του Church. Αλγοριθμικά μη επιλύσιμα προβλήματα. Το πρόβλημα της περάτωσης. Η έννοια της υπολογιστικής πολυπλοκότητας αλγορίθμων. Προβλήματα επιλύσιμα με αποδοτικό τρόπο. Κλάσεις πολυπλοκότητας. Οι κλάσεις P και NP. Αναγωγές μεταξύ προβλημάτων. Προβλήματα πλήρη στην κλάση NP. Η σχέση των κλάσεων P και NP. Η πολυωνυμική ιεραρχία κλάσεων πολυπλοκότητας. Πολυπλοκότητα ως προς χώρο.

Startup Growth Lite is a free theme, contributed to the Drupal Community by More than Themes.