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

Ύλη:

1. Αναγωγές στην Υπολογισιμότητα
2. Απόδειξη με Αναγωγή ότι η γλώσσα ΤΕΡΜΑΤΙΣΜΟΣ είναι μη-διαγνώσιμη
3. Μη-Διαγνωσιμότητα του Προβλήματος ΚΕΝΟΤΗΤΑ
4. Μη-Διαγνωσιμότητα του Προβλήματος ΙΣΟΔΥΝΑΜΙΑ

Sipser σελ. 253-260

Υλικό:

Διαφάνειες σελ. 1-16, 25

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

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

Ύλη:

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

Sipser σελ. 238-247

Υλικό:

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

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

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

Ύλη:

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. Προσοχή: το περιεχό

Ύλη:

1. Απαριθμητές
2. Η Θέση των Church-Turing
3. Κωδικοποίηση Εισόδου σε ΤΜ

Sipser σελ. 211-220

Υλικό:

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

Διαφάνειες σελ. 1-23, 32-38

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

Ύλη:

1. Πολυταινιακές ΤΜ
2. Ανταιτιοκρατικές ΤΜ

Sipser σελ. 206-211

Υλικό:

Διαφάνειες σελ. 7-23

Εδώ μπορείτε να βρείτε μία ωραία παρουσίαση σε Powerpoint, που να εξηγεί γιατί το Powerpoint είναι Turing_Complete.

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

Ύλη:

1. Ασκήσεις σε ΤΜς
2. Διαγνώσιμες Γλώσσες σε ΤΜ
3. Ισοδυναμία με Παραλλαγή της ΤΜ
4. Σχόλιο: Στο βιβλίο του Sipser, στον Ορισμό 3.1 της ΤΜ στη σελ. 196, γράφει στο (3): Σ \subseteq Γ. Αυτό είναι αληθές, αλλά αν θέλαμε να είμαστε πιο σωστοί θα γράφαμε Σ\subset Γ (δηλαδή δεν είναι ίσα), αφού όπως αναφέρεται και στο σημείο (3) το κενό ανήκει στο Γ ενώ από το (2) το κενό δεν ανήκει στο Σ.

Sipser σελ. 199-206

Υλικό:

Διαφάνειες σελ. 51-54

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

Αντίστοιχη διάλεξη μέσω zoom από το ακαδημαϊκό έ

Ύλη:

Άσκηση σχεδίασης μίας ΤΜ

Υλικό:

Διαφάνειες σελ. 45-51

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

Ύλη:

1. Τυπικός ορισμός Μηχανής Turing
2. Παραδείγματα

Sipser: σελ. 193-199

Υλικό:

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

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

Ύλη:

Έγινε μία εισαγωγή στο υλικό του μαθήματος.

Υλικό:

Διαφάνειες

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