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

Ύλη:

1. Κλειστότητα Κλάσεων P και NP ως προς Συγκεκριμένες Πράξεις

2. Απεικονιστικές Αναγωγές Πολυωνυμικού Χρόνου

3. Αναγωγή στην Κλάση P

Sipser σελ. 357-360

Υλικό:

Διαφάνειες σελ. 39-41, 47-50

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

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

Ύλη:

1. Παραδείγματα Γλωσσών στην κλάση NP
2. Η Κλάση coNP

Sipser σελ. 353-356

Υλικό:

Διαφάνειες σελ. 31-38, 44-46

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

Ύλη:

1. Η Κλάση Χρονικής Πολυπλοκότητας NP
2. Παραδείγματα Προβλημάτων στην Κλάση NP
3. NP και Πολυωνυμική Επαληθευσιμότητα

Sipser σελ. 348-353

Υλικό:

Διαφάνειες σελ. 16-30

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

Ύλη:

1. Προβλήματα Απόφασης στην Πολυπλοκότητα
2. Η Κλάση Χρονικής Πολυπλοκότητας P
3. Παραδείγματα Προβλημάτων στην Κλάση P
4. Η Κλάση NP

Sipser σελ. 339-346

Υλικό:

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

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

Ύλη:

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

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

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

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

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