Διαλέξεις

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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