Weekly outline

• General
  

  General

  Δείτε πρώτα

  http://old.corelab.ntua.gr/courses/afl/
  

  
  

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

  
  

  Περιγραφή

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

  
  

  Διδάσκοντες

  • Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
  • Πέτρος Ποτίκας, Ε.Δι.Π. (ppotik@cs.ntua.gr)

  Διαλέξεις
  

  • Τετάρτη 15:00-17:00, εξ αποστάσεως
  • Παρασκευή 15:00-17:00, εξ αποστάσεως

  Σύνδεσμος
  

  Meeting link:

  https://centralntua.webex.com/centralntua/j.php?MTID=m2710044577fcb1aaff4569c196308c66 

  Meeting number:121 090 8900

  Password:automata@xxxx_21 (όπου xxxx το ακρωνύμιο του ΕΜΠ στα αγγλικά, όλα με πεζά)

  
  

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

  
  

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

  
  

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

  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.

  
  

  Υλικό

  Διαφάνειες μαθήματος
  

  • Αυτόματα και Τυπικές Γραμματικές, Μοντέλα Υπολογισμού, Υπολογιστική Πολυπλοκότητα και Προσεγγιστικοί Αλγόριθμοι
  • Αυτόματα και Τυπικές Γραμματικές, Μοντέλα Υπολογισμού, Υπολογιστική Πολυπλοκότητα και Προσεγγιστικοί Αλγόριθμοι (NEO)
  • Διαφάνειες Γλωσσών προγραμματισμού
  • Σημειώσεις Γλωσσών προγραμματισμού
  • Διαφάνειες διαλογικής αλληλεπίδρασης
  • Ω-αυτόματα, αυτόματα δέντρων (νέες διαφάνειες)
  • Ehrenfeucht-Fraisse games
  • Θεώρημα Parikh

  
  

  Ασκήσεις

  Αυτόματα και Τυπικές Γραμματικές

  • 1η σειρά (ps) (pdf)
  • 2η σειρά (ps) (pdf)
  • 3η σειρά (ps) (pdf)
  • 4η σειρά (ps) (pdf)
  • 5η σειρά (ps) (pdf)
  • 6η σειρά (ps) (pdf)

  Μοντέλα υπολογισμού

  • 7η σειρά (ps) (pdf)
  • 8η σειρά (pdf)
  • 9η σειρά (pdf)(όχι το GOTO)
  • 10η σειρά (pdf)

  Πολυπλοκότητα

  • 11η σειρά (pdf)

  • Ανακοινώσεις Forum
  • Υποβολή 1ης σειράς ασκήσεων Assignment
  • Υποβολή 2ης σειράς ασκήσεων Assignment
  • Υποβολή 3ης σειράς ασκήσεων Assignment
  • Υποβολή σειρών ασκήσεων 4-6 Assignment
  • Υποβολή σειρών ασκήσεων 7-10 Assignment
  • Υποβολή 11ης σειράς ασκήσεων Assignment
• 4 March - 10 March
  

  4 March - 10 March
• 11 March - 17 March
  

  11 March - 17 March
• 18 March - 24 March
  

  18 March - 24 March
• 25 March - 31 March
  

  25 March - 31 March
• 1 April - 7 April
  

  1 April - 7 April
• 8 April - 14 April
  

  8 April - 14 April
• 15 April - 21 April
  

  15 April - 21 April
• 22 April - 28 April
  

  22 April - 28 April
• 29 April - 5 May
  

  29 April - 5 May
• 6 May - 12 May
  

  6 May - 12 May