Παρουσίαση/Προβολή

Εικόνα επιλογής

ΥΠΟΛΟΓΙΣΙΜΟΤΗΤΑ KAI ΠΟΛΥΠΛΟΚΟΤΗΤΑ

(INF147) -  ΦΟΥΣΤΟΥΚΟΥ ΕΥΓΕΝΙΑ

Περιγραφή Μαθήματος

ΠΡΩΤΟ ΜΕΡΟΣ: ΥΠΟΛΟΓΙΣΙΜΟΤΗΤΑ

Αναδρομικές συναρτήσεις

Turing-υπολογίσιμες συναρτήσεις

Κωδικοποιήσεις

Βασικά Θεωρήματα (s-m-n θεώρημα κλπ)

Αναδρομικά σύνολα

Αναδρομικά απαριθμήσιμα σύνολα 

Turing Αναγωγησιμότητα

YΛΗ

Απο το βιβλίο Μ. Μυτιληναίου:          Μερος Ι   (Υπολογισιμότητα)

Από σημειώσεις Α. Τζουβάρα:            Κεφ. 1, 2, και 4.1.   

(Το περιεχόμενο του κεφ. 3 Τζουβάρα και 2.7. Τζουβάρα είναι στην ύλη αλλά καλύτερα να το διαβάσετε από το βιβλίο του Μυτιληναίου καθώς οι φορμαλισμοί διαφέρουν από το ένα εγχειρίδιο στο άλλο).

Επίσης από το βιβλίο του Μ. Sipser Εισαγωγή στην Θεωρία Υπολογισμού, το υποκεφάλαιο 6.3 για Turing-αναγωγησιμότητα.

 

ΔΕΥΤΕΡΟ ΜΕΡΟΣ:  ΠΟΛΥΠΛΟΚΟΤΗΤΑ

Kλάσεις ΝP και co-NP .
Οι κλάσεις της πολυωνυμικής ιεραρχίας.
η κλάση PSPACE.
Κλάσεις πολυπλοκότητας για προβλήματα εύρεσης (FP, FNP, PPAD)
Προβλήματα μέτρησης και η κλάση sharp-P (#P).
Τα θέματα αυτά αναπτύσσονται στο βιβλίο του Χ. Παπαδημητρίου Computational Complexity ειδικότερα στα Κεφάλαια 9,10, 14, 17,18)

Σχετικά με τα παραπάνω, για τις εξετάσεις μπορείτε να καλυφθείτε από το βιβλίο του Μ. Sipser Εισαγωγή στην Θεωρία Υπολογισμού και ειδικότερα από τα εξής υποκεφάλαια:
 7.3. για την κλάση NP,
 7.4  για την ΝP-πληρότητα,
 8.2  για την κλάση PSPACE
 8.3  για την κλάση PSPACE-πληρότητα
10.3  Εναλλασσόμενες μηχανές Turing και πολυωνυμική ιεραρχία

Επίσης  απο το βιβλίο Μ. Μυτιληναίου  Μερος ΙΙ  (Πολυπλοκότητα)

ΩΡΕΣ ΓΡΑΦΕΙΟΥ

Οι ώρες γραφείου για το τρέχον εαρινό εξάμηνο είναι:

Δευτέρα 11:00-13:00

Πέμπτη 11:00-13:00

Στο γραφειο μου Κοδριγκτώνος 12, 3ος οροφος.

Επίσης επικοινωνία με email στο eugenie@aueb.gr ή με rv στο Teams αφού έχει προηγηθεί συνεννόηση με email.

 

Ημερομηνία δημιουργίας

Παρασκευή, 23 Οκτωβρίου 2009

Σελίδα μαθήματος