Μάθημα : Υπολογιστική Πολυπλοκότητα

Ύλη:

1. Η Μέθοδος της Διαγωνιοποίησης
2. Ισομεγέθη Άπειρα Σύνολα
3. Το Σύνολο των Πραγματικών Αριθμών είναι Υπεραριθμήσιμο
4. Χαρακτηριστική Ακολουθία Γλώσσας - Σύγκριση μεγέθους Συνόλων Γλωσσών και υποσυνόλου του Σ*
5. Απόδειξη με Διαγωνιοποίηση ότι η ΑΠΟΔΟΧΗ είναι μη-διαγνώσιμη

Sipser σελ. 238-247

Υλικό:

Διαφάνειες σελ. 15-37

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

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