Υπολογιστική Κρυπτογραφία

Προγραμματισμός Ηλεκτρονικών Υπολογιστών

Θεμελιώδη Θέματα Επιστήμης Η/Υ (ΣΕΜΦΕ)

Αυτόματα και Υπολογιστικά Μοντέλα

Εαρινό εξάμηνο 2021-2022

Περιγραφή

Οι γλώσσες και οι αναπαραστάσεις τους. Γραμματικές, context-sensitive και context-free γραμματικές. Πεπερασμένα αυτόματα και κανονικές γραμματικές. Pushdown Αυτόματα. Μηχανές Turing. Αυτόματα και αναγνώριση γλωσσών. Τυπικές γραμματικές. Εφαρμογές στη σύνταξη των γλωσσών προγραμματισμού. Προβλήματα (αν)αποκρισιμότητας και πολυπλοκότητας. Υπολογισιμότητα: LOOP προγράμματα, WHILE προγράμματα. Προσεγγισιμότητα. Τυχαιότητα. Ω-αυτόματα, αυτόματα δένδρων.


Διδάσκοντες

Διαλέξεις

  • Τετάρτη 15:00-17:00
  • Παρασκευή 15:00-17:00


Τρόπος εξέτασης

Η εξέταση του μαθήματος αποτελείται από δύο μέρη: α) Μέρος Α, ερωτήσεις θεωρίας και είναι με κλειστές σημειώσεις και βιβλία και β) Μέρος Β, ασκήσεις και είναι με ανοιχτές σημειώσεις (επιτρέπεται να χρησιμοποιήσετε τις σημειώσεις σας και βιβλία).


Βιβλιογραφία

  1. Σ. Ζάχος, Σημειώσεις
  2. Σ. Ζάχος, Α. Παγουρτζής, Τα Θεμέλια της Πληροφορικής, εκδόσεις Τσότρας, 2014
  3. Μ. Sipser. Introduction to the Theory of Computation.
  4. J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages and Computation.
  5. H. R. Lewis and C. Papadimitriou. Elements of the Theory of Computation, 2nd edition.
  6. D. C. Kozen. Automata and Computability (Undergraduate Texts in Computer Science).
  7. M. Harrison. Introduction to Switching and Automata Theory. McGraw-Hill Book Company, New York (1965).
  8. C. Papadimitriou. Computational Complexity.
  9. S. Arora, B. Barak. Computational Complexity: A modern approach.
  10. E. Grädel, W. Thomas, Th. Wilke. Automata, Logics and Infinite Games.

Υπολογισιμότητα και Πολυπλοκότητα (Μοντέλα Υπολογισμού, Τυπικές Γλώσσες και Αυτόματα)

Προσφέρεται ως Υπολογισιμότητα και Πολυπλοκότητα (ΣΕΜΦΕ, ΣΗΜΜΥ)

και ως Μοντέλα Υπολογισμού, Τυπικές Γλώσσες και Αυτόματα (ΑΛΜΑ, ΕΜΕ).


Εαρινό εξάμηνο 2021-2022

Περιγραφή

Υπολογισιμότητα, Λογική θεμελίωση πληροφορικής, Ιστορική αναδρομή στο πρόβλημα αποκρισιμότητας μαθηματικών προτάσεων, Eπιλυσιμότητα ή υπολογισιμότητα προβλημάτων με μηχανιστικό, δηλαδή αλγοριθμικό, τρόπο. Απλά ισοδύναμα υπολογιστικά μοντέλα: μηχανές Turing, προγράμματα WHILE. Επαγωγή και αναδρομή, κωδικοποίηση και σημασιολογία. Θεωρία σταθερού σημείου. Θεωρία Tarski και υπολογιστικών στρατηγικών. Αριθμητική ιεραρχία. Προχωρημένα θέματα από την θεωρία τυπικών. Γραμματικών. Υπολογιστική Πολυπλοκότητα. Σχέσεις μεταξύ κλάσεων πολυπλοκότητας.  

      L --> NL --> P --> NP --> PSPACE = NPSPACE --> EXPTIME. 

Co-κλάσεις, Αναγωγές και Πληρότητα. Μαντεία. Πολυωνυμική ιεραρχία. Πιθανοτικές, τυχαιότητα (randomness). Διαλογικές/αλληλεπίδραση, PCP.  Μετρητικές κλάσεις. Προσεγγιστική Πολυπλοκότητα. Πολυπλοκότητα αναζήτησης. Παραμετρική πολυπλοκότητα. Κβαντική πολυπλοκότητα.  Μη-ομοιομόρφα κυκλώματα.

 

Διδάσκοντες