Topic outline

• General
  

  General

  Δείτε πρώτα

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

  
  

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

  
  

  Περιγραφή

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

  
  

  Διδάσκοντες

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

  Βοηθοί διδασκαλίας

  • Γιάννης Παπαϊωάννου, Υ.Δ. (ipapaioannou@corelab.ntua.gr)

  Διαλέξεις

  • Τετάρτη 15:00-17:00, 1.1.29, Παλαιό Κτίριο Ηλεκτρολόγων
  • Παρασκευή 15:00-17:00, 1.1.29, Παλαιό Κτίριο Ηλεκτρολόγων

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

  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.

  
  

  Ανακοινώσεις

  • Στην ενότητα 'Εργασίες' του mycourses.ntua.gr, αναρτήθηκαν οι σειρές ασκήσεων.
    

  • Το μάθημα κάθε Τετάρτη και Παρασκευή αρχίζει στις 15:15 και από εδώ και στο εξής θα γίνεται πάντα σε αυτό τον σύνδεσμο, εκτός και αν υπάρξει κάποια νεότερη ανακοίνωση. 

    https://meetingsemea.webex.com/meet/ppotik

  • Λαμβάνοντας υπόψη τη νέα κατάσταση, που ελπίζουμε να μην διαρκέσει πάρα πολύ, θα προσπαθήσουμε να συνεχίσουμε τα μαθήματα διαδικτυακά. Θα λάβετε νέα ανακοίνωση σύντομα για την πλατφόρμα που θα χρησιμοποιήσουμε και οδηγίες για το μάθημα της Παρασκευής 20/3/20 που θα γίνει ώρα 15:00μμ-17:00μμ.
  • Το πρώτο μάθημα θα γίνει την Τετάρτη 26/2/20, 15:00-17:00.

  
  

  Υλικό

  Διαλέξεις

  • Διάλεξη 26/2/2020: Αυτόματα και Τυπικές Γραμματικές: Εισαγωγή, DFA/NFA/NFAε
  • Διάλεξη 28/2/2020: Αυτόματα και Τυπικές Γραμματικές: Ισοδυναμία DFA με NFAε, ελαχιστοποίηση DFA, τυπικές γλώσσες, τυπικές γραμματικές, ιεραρχία γραμματικών Chomsky, κανονικές γραμματικές, ισοδυναμία κανονικών γραμματικών και DFA, κανονικές παραστάσεις, ισοδυναμία κανονικών παραστάσεων και αυτομάτων, γινόμενο αυτομάτων

  
  

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

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

  
  

  Ασκήσεις

  Οι ασκήσεις παραδίδονται στο mycourses.ntua.gr. Εκεί υπάρχουν και οι αντίστοιχες προθεσμίες παράδοσης.

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

  • 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