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

Ύλη:

1. Η εξάρτηση της χρονικής πολυπλοκότητας ενός προβλήματος από το μοντέλο υπολογισμού
2. Εξομοίωση Πολυταινιακής ΤΜ
3. Εξομοίωση Αντατιοκρατικής ΤΜ

Sipser σελ. 335-339

Υλικό:

Διαφάνειες σελ. 35-46 (οι διαφάνειες 34, 47-54 είναι εκτός ύλης)

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

Ύλη:

1. Εισαγωγή στην Πολυπλοκότητα
2. Ασυμπτωτική Σημειογραφία
3. Η Έννοια της Κλάσης Χρονικής Πολυπλοκότητας

Sipser σελ. 327-335

Υλικό:

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

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

Ύλη:

1. Ασκήσεις σε Απεικονιστικές Αναγωγές

Υλικό:

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

Ασκήσεις σε Αναγωγές

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

Ύλη:

1. Ασκήσεις σε Απεικονιστικές Αναγωγές

Sipser σελ. 276-282

Υλικό:

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

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

Ύλη:

1. Γραμμικώς Φραγμένο Αυτόματο (LBA)
2. Η Γλώσσα ΑΠΟΔΟΧΗ_{LBA} είναι διαγνώσιμη
3. Η Γλώσσα ΚΕΝΟΤΗΤΑ_{LBA} είναι μη- διαγνώσιμη με αναγωγή μέσω υπολογιστικού χρονικού
4. Απεικονιστικές Αναγωγές

Sipser σελ. 260-266, 276-281

Υλικό:

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

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

Ύλη:

1. Επίλυση παλαιότερων θεμάτων και παραλλαγών τους.

Υλικό:

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

Έγγραφο με λυμμένες ασκήσεις σε αναγωγές.

Ασκήσεις Διαγνωσιμότητας-Αναγνωρισιμότητας

Παραδείγματα αναγωγών από παλιότερες διαφάνειες

Προσοχή: κάποιες από τις ασκήσεις αφορούν απεικονιστικές αναγωγές που θα παρουσιασθούν σε επόμενα μαθήματα.

Ύλη:

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