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

Ύλη:

1. Ασκήσεις σε κλάσεις πολυπλοκότητας
2. Λύσαμε ασκήσεις από τα θέματα Ιουνίου 2023

Υλικό:

Διαφάνειες σελ. 39-44, 54

Ύλη:

1. Αναγωγή από Κομβικό Κάλυμμα σε Κάλυμμα Συνόλου
2. Αναγωγή από 3SAT σε MAX2SAT
3. Αναγωγή με περιορισμό από ΑΘΡΟΙΣΜΑ_ΥΠΟΑΚΟΛΟΥΘΙΑΣ σε KNAPSACK

Υλικό:

Διαφάνειες σελ. 16-20, 36-38 (Οι αναγωγές από 3SAT σε ΑΘΡΟΙΣΜΑ_ΥΠΟΑΚΟΛΟΥΘΙΑΣ και από 3SAT σε HAMPATH είναι εκτός ύλης)

Ύλη:

1. Το πρόβλημα 2SAT
2. Κομβικό Κάλυμμα

Υλικό:

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

1ο σετ λυμμένων ασκήσεων

2ο σετ λυμμένων ασκήσεων 

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

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

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

Ύλη:

1. Ορισμοί: NP-Complete και NP-Hard
2. Θεώρημα Αναγωγής για Απόδειξη NP-Πληρότητας
3. Θεώρημα Cook-Levin
4. Αναγωγή από SAT σε 3SAT

Sipser σελ. 363-371 χωρίς την απόδειξη του Θεωρήματος Cook-Levin (Θεώρημα 7.30)

Υλικό:

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

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

Ύλη:

1. Αναγωγή μεταξύ Hamiltonian Path και Hamiltonian Cycle (και προς τις δύο κατευθύνσεις)

Υλικό:

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

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

Ύλη:

1. Απεικονιστικές Αναγωγές Πολυωνυμικού Χρόνου
2. Αναγωγή στην Κλάση P
3. Το Πρόβλημα της Αληθευσιμότητας Λογικού Τύπου
4. Αναγωγή από 3SAT σε ΚΛΙΚΑ
5. Αναγωγή μεταξύ των Προβλημάτων ΑΝΕΞΑΡΤΗΤΟ_ΣΥΝΟΛΟ και ΚΛΙΚΑ

Sipser σελ. 357-362

Υλικό:

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

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

Ύλη:

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