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

Κωδ.: 
ΘΠ20
Εξάμηνο: 
8
Τύπος μαθήματος νέο ΠΠΣ : 
Προαιρετικά Μαθήματα (ΠΜ)
K (new pps): 
A
E1: 
B
Ώρες Θεωρίας: 
3
Ώρες Φροντιστηρίου: 
1
Προαπαιτούμενα Μαθήματα: 
Θεωρία Υπολογισμού
Κατεύθυνση: 
Ελεύθερα Μαθήματα

ΤΜΗΜΑ ΜΑΘΗΜΑΤΙΚΩΝ

618 Υπολογιστική Πολυπλοκότητα (5ο εξάμηνο)

Διδάσκοντες: Δ. Θηλυκός, Λ. Κυρούσης

• Μοντέλα υπολογισμού, Μηχανές Turing, Η έννοια του ευκόλως επιλύσιμου προβλήματος, Η κλάση PSPACE, Το θεώρημα του Savitch, Οι κλάσεις Ρ και EXP. • Μη Ντετερμινιστικές Μηχανές Turing. • Οι κλάσεις NP και co-NP. Το θεώρημα της προβολής. Αναγωγές και πληρότητα, η έννοια της NP-δυσκολίας. • Το θεώρημα Cook-Levin, NP-πλήρη προβλήματα, Τεχνικές απόδειξης NP- πληρότητας, Ψευδοπολυωνυμικότητα, Προβλήματα ισχυρώς NP-πλήρη. • NP-πληρότητα και προσεγγισιμότητα, Προβλήματα EXP-πλήρη και PSPACE-πλήρη.

Βιβλία:

ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ, SIPSER MICHAEL, Πανεπιστημιακές Εκδόσεις Κρήτης http://www.cup.gr/ΕΙΣΑΓΩΓΗ-ΣΤΗ-ΘΕΩΡΙΑ-ΥΠΟΛΟΓΙΣΜΟΥ_p-264687.aspx?LangId=1

ΣΤΟΙΧΕΙΑ ΘΕΩΡΙΑΣ ΥΠΟΛΟΓΙΣΜΟΥ, HARRY LEWIS, ΧΡΙΣΤΟΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ, Εκδόσεις Κριτική http://www.kritiki.gr/lewis_papadimitriou