Διαλέξεις

 

Ύλη που θα συζητηθεί:

• από σύγγραμμα Εισαγωγή στη Θεωρία Υπολογισμού, M. Sipser (3η έκδοση): έως σελίδα 289

• από σύγγραμμα Στοιχεία Θεωρίας Υπολογισμού, H. Lewis, Χρ. Παπαδημητρίου: έως σελίδα 470

(Ενδεικτικός) Προγραμματισμός συναντήσεων:

• 18 και 20.2.2025: Εναρκτήρια συνάντηση

• 25 και 27.2.2025: Στοιχεία θεωρίας συνόλων - Τεχνικές απόδειξης

• 4 και 6.3.2025: Κανονικές γλώσσες: Κανονικές εκφράσεις

• 11 και 13.3.2025: Κανονικές γλώσσες: Ντετερμινιστικά Πεπερασμένα Αυτόματα (DFA)

• 18 και 20.3.2025: Κανονικές γλώσσες: Μη ντετερμινιστικά Πεπερασμένα Αυτόματα (NFA) και ισοδυναμία με DFA

• 25 και 27.3.2025: Κανονικές γλώσσες: Ισοδυναμία κανονικών εκφράσεων και πεπερασμένων αυτομάτων - Μη κανονικές γλώσσες (pumping lemma)

• 1 και 3.4.2025: Γλώσσες χωρίς συμφραζόμενα: Γραμματικές χωρίς συμφραζόμενα (CFG)

• 8 και 10.4.2025: Γλώσσες χωρίς συμφραζόμενα: αυτόματα στοίβας (PDA)

• 15 και 17.4.2025

• 22 και 24.4.2025

• 29.4 και 1.5.2025: Γλώσσες χωρίς συμφραζόμενα: ισοδυναμία PDA και CFG - Γλώσσες που δεν είναι χωρίς συμφραζόμενα (pumping lemma)

• 6 και 8.5.2025: Μηχανές Turing: ορισμός - ισοδύναμα μοντέλα - σχεδιασμός

• 13 και 15.5.2025: Διαγνωσιμότητα (Decidability/Undecidability), Αναγωγές (Reducibility)

• 20 και 22.5.2025: Υπολογιστική πολυπλοκότητα:  κλάσεις P και ΝP, NP-πληρότητα

• 27 και 29.5.2025: Υπολογιστική πολυπλοκότητα:  κλάσεις P και ΝP, NP-πληρότητα