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

Υποβλήθηκε από admin την Δευ, 04/05/2015 - 11:24.
Τύπος μαθήματος : 
Bασικό
Κωδ.: 
Μ104
ECTS: 
8
Διδακτικές μονάδες: 
4
Εξάμηνο: 
Χειμερινό
Ειδίκευση: 
1η
Ώρες διδασκαλίας: 
4
Ώρες φροντιστηρίου: 
0
Ώρες Εργαστηρίου: 
0
Ιστοσελίδα: 
http://eclass.uoa.gr/courses/D402/
Διδάσκων(εκτός τμήματος): 
ΦΩΤΑΚΗΣ

Μηχανές Turing, υπολογισιμότητα, πολυπλοκότητα χρόνου, πολυπλοκότητα χώρου, κλάσεις πολυπλοκότητας, αναγωγές, NP-completeness, coNP, πιθανοκρατικές κλάσεις πολυπλοκότητας, η πολυωνυμική ιεραρχία, προβλήματα μέτρησης, #P, συστήματα αποδείξεων, ψευδοτυχαιότητα, συναρτήσεις μονής κατεύθυνσης.