Υπολογιστική Πολυπλοκότητα

Κωδικός Μαθήματος: 
CEID_NY302
Κατηγορία: 
Εξάμηνο: 
Διδάσκοντες: 
Διδακτικές Μονάδες: 
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.