Weekly outline

• General
  

  General

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

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

  
  

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

  
  

  Περιγραφή

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

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

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

   

  Διδάσκοντες

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

  Διαλέξεις

  • Παρασκευή 10:00-13:30, εξ αποστάσεως

  Σύνδεσμος

  Meeting link:
  
  

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

  Meeting number:121 081 8607
  
  

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

  
  

  Έναρξη

  • 26/2/2021.

  
  

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

  
  

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

  
  

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

  1. Σ. Ζάχος. Σημειώσεις μαθήματος.
  2. D. Sipser. Introduction to the Τheory of Computation.
  3. J.E. Hopcroft και J.D. Ullman. Introduction to Automata Theory, Languages and Computation.
  4. H. R. Lewis και C. Papadimitriou. Elements of the Theory of Computation, 2nd edition.
  5. M. Harrison. Introduction to Switching and Automata Theory. McGraw-Hill Book Company, New York (1965).
  6. D. C. Kozen. Automata and Computability (Undergraduate Texts in Computer Science).
  7. Martin D. Davis, Ron Sigal, Elaine J. Wayuker. Computability, Complexity, and Languages, 2nd edition.
  8. C. Papadimitriou. Computational Complexity.
  9. S. Arora, B. Barak. Computational Complexity: A modern approach.
  10. S. Homer, A. Selman. Computability and Complexity.
  11. N. Jones. Computability and Complexity From a Programming Perspective.

  
  

  Υλικό

  
  

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

  
  

  • Όλες οι διαφάνειες Υπολογισιμότητας, Αυτομάτων και Τυπικών Γραμματικών, Πολυπλοκότητας και Προσεγγιστικών αλγορίθμων.

  • Όλες οι διαφάνειες Υπολογισιμότητας, Αυτομάτων και Τυπικών Γραμματικών, Πολυπλοκότητας και Προσεγγιστικών αλγορίθμων (ΝΕΟ).
    
  • Διαφάνειες για μη-ομοιόμορφα κυκλώματα (ΝΕΟ).
  • Διαφάνειες για PCP θεώρημα (ΝΕΟ).
  • Διαφάνειες για Πολυπλοκότητα αναζήτησης.
  • Διαφάνειες για Παραμετρική Πολυπλοκότητα.
  • Διαφάνειες για Παραμετρική Πολυπλοκότητα (ΝΕΟ). 
  • Διαφάνειες για Κβαντική Πολυπλοκότητα.
  • Διαφάνειες για Κβαντική Πολυπλοκότητα (Ορέστη Χαρδούβελη).
    
  • Διαφάνειες για PPP-completeness - διαφάνειες Μ. Ζαμπετάκη
  • Διαφάνειες για PPP-completeness - διαφάνειες Α. Μέρτζιου
  • Σημειώσεις για παραμετρική πολυπλοκότητα.
  • Σημειώσεις για κβαντική πολυπλοκότητα.
  • Σημειώσεις για πολυπλοκότητα αναζήτησης.
  • Σημειώσεις για μη-ομοιόμορφα κυκλώματα (ΝΕΟ).

  Ασκήσεις (υπάρχουν και στο βιβλίο)

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

  • 1η Σειρά Προκαταρκτικά (ps) (pdf)
  • 2η Σειρά LOOP (ps) (pdf)
  • 3η Σειρά Κωδικοποίηση (ps) (pdf)
  • 4η Σειρά Πρωταρχικές αναδρομικές συναρτήσεις (ps) (pdf)
  • 5η Σειρά Σχήματα McCarthy - Στρατηγικές (ps) (pdf)
  • 6η Σειρά GOTO - Μηχανές Turing (ps) (pdf)
  • 7η Σειρά Καθολικότητα - Αναδρομικότητα (ps) (pdf)
  • 8η Σειρά Αναδρομικά αριθμήσιμα σύνολα (ps) (pdf) (Θ. 75, 76 - Θεώρ. παραμέτρων, Θεώρ. S-m-n)
  • 9η Σειρά Μαντεία - Αριθμητικά κατηγορήματα (ps) (pdf)
  • 9'η Σειρά (pdf)

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

  • 10η σειρά (ps) (pdf)
  • 11η σειρά (ps) (pdf)
  • 12η σειρά (ps) (pdf)
  • 13η σειρά (ps) (pdf)
  • 14η σειρά (ps) (pdf)

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

  • 15η σειρά (pdf)

  • Ανακοινώσεις Forum
  • Υποβολή 1ης σειράς ασκήσεων Assignment
  • Υποβολή 2ης σειράς ασκήσεων Assignment
  • Υποβολή 3ης σειράς ασκήσεων Assignment
  • Υποβολή 4ης σειράς ασκήσεων Assignment
  • Υποβολή 5ης σειράς ασκήσεων Assignment
  • Υποβολή σειρών ασκήσεων 6-9' Assignment
  • Υποβολή σειρών ασκήσεων 10-14 Assignment
  • Υποβολή 15ης σειράς ασκήσεων Assignment
  • Υποβολή 16η Σειράς Ασκήσεων - Βιβλιογραφική Assignment
  • Υποβολή 17ης σειράς ασκήσεων - expander graphs 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