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

Ύλη:

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. Προσοχή: το περιεχόμενο μπορεί να μη συμπίπτει ακριβώς με την αντίστοιχη διάλεξη στην αίθουσα.