Υπολογιστική Πολυπλοκότητα 23-24 (CEID_NY302)

Ύλη:

1. Άσκηση σε Παραλλαγή ΤΜ
2. Καθολική ΤΜ
3. Γιατί χρησιμοποιούμε προβλήματα απόφασης; (εκτός εξεταστέας ύλης)
4. Θεώρημα περί διαγνωσιμότητας και αναγνωρισιμότητας
5. Αναγνωρισιμότητα της Γλώσσας ΑΠΟΔΟΧΗ_{ΤΜ}
6. Συμπληρωματικά Αναγνωρίσιμες Γλώσσες και Μη-Αναγνωρίσιμες

Sipser σελ. 227-228 (όχι 4.1 εκτός του Σχήματος 4.2), σελ. 237-238, σελ. 246-247

Υλικό:

Διαφάνειες σελ. 34

Διαφάνειες σελ. 24-31

Διαφάνειες σελ. 1-14

Άσκηση σε ΤΜ

Αντίστοιχη διάλεξη μέσω zoom από το ακαδημαϊκό έτος 20-21. Προσοχή: το περιεχόμενο μπορεί να μη συμπίπτει ακριβώς με την αντίστοιχη διάλεξη στην αίθουσα.