Περιγραφή θέματος

• Γενικά
  

  Γενικά

  Δείτε πρώτα εδώ
  http://old.corelab.ntua.gr/courses/computability/

  
  

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

  
  

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

  
  

  Περιγραφή

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

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

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

   

  Διδάσκοντες

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

  Διαλέξεις

  • Παρασκευή 11:45-14:30, 1.1.29, Παλαιό Κτίριο Ηλεκτρολόγων (ΣΗΜΜΥ, ΣΕΜΦΕ)
  • Παρασκευή 9:30-13:30, 1.1.29, Παλαιό Κτίριο Ηλεκτρολόγων (ΑΛΜΑ)

  Έναρξη

  • 28/2/2020.

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

  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.

  
  

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

  • Mπορείτε να υποβάλετε τις λύσεις των ασκήσεων στο moodle του μαθήματος (https://courses.corelab.ntua.gr/course/view.php?id=40)

  • Το λινκ για το αυριανό μάθημα και για τις ημέρες που έχουμε μάθημα είναι το παρακάτω και θα συνδεόμαστε την ώρα του μαθήματος. Αύριο θα αρχίσουμε από τη διαφάνεια 113 (μεταπτυχιακοί) και 81 (προπτυχιακοί). Θα πρέπει να έχετε μελετήσει τις προηγούμενες διαφάνειες. Επίσης, σας παροτρύνουμε να ασχοληθείτε με τις ασκήσεις που υπάρχουν στη σελίδα του μαθήματος. Σύντομα θα δοθούν οδηγίες για την υποβολή τους.
    
    

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

  • Λαμβάνοντας υπόψη τη νέα κατάσταση, που ελπίζουμε να μην διαρκέσει πάρα πολύ, θα προσπαθήσουμε να συνεχίσουμε τα μαθήματα διαδικτυακά. Θα λάβετε νέα ανακοίνωση σύντομα για την πλατφόρμα που θα χρησιμοποιήσουμε και οδηγίες για το μάθημα της Παρασκευής 20/3 που θα γίνει ώρα 11:30πμ-14:30μμ.
  • Έναρξη: 28/2/2020

  
  

  Υλικό

  
  

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

  • Όλες οι διαφάνειες Υπολογισιμότητας, Αυτομάτων και Τυπικών Γραμματικών, Πολυπλοκότητας και Προσεγγιστικών αλγορίθμων.
  • Διαφάνειες για μη-ομοιόμορφα κυκλώματα (ΝΕΟ).
  • Διαφάνειες για 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)

  • Ανακοινώσεις Φόρουμ

    Γενικές ανακοινώσεις
• 1ο σετ ασκήσεων - Μοντέλα υπολογισμού
  

  1ο σετ ασκήσεων - Μοντέλα υπολογισμού

  • 1η σειρά ασκήσεων Ανάθεση εργασίας
  • 2η σειρά Ανάθεση εργασίας
  • 3η σειρά Ανάθεση εργασίας
  • 4η σειρά Ανάθεση εργασίας
  • 5η σειρά Ανάθεση εργασίας
  • 6η σειρά Ανάθεση εργασίας
  • 7η σειρά Ανάθεση εργασίας
  • 8η σειρά Ανάθεση εργασίας
  • 9η σειρά Ανάθεση εργασίας
  • 9'η σειρά ασκήσεων Ανάθεση εργασίας
• 2ο σετ ασκήσεων - Αυτόματα και Τυπικές Γραμματικές
  

  2ο σετ ασκήσεων - Αυτόματα και Τυπικές Γραμματικές

  • 10η σειρά Ανάθεση εργασίας
  • 11η σειρά Ανάθεση εργασίας
  • 12η σειρά Ανάθεση εργασίας
  • 13η σειρά Ανάθεση εργασίας
  • 14η σειρά Ανάθεση εργασίας
• 3ο σετ ασκήσεων - Πολυπλοκότητα
  

  3ο σετ ασκήσεων - Πολυπλοκότητα

  • 15η σειρά ασκήσεων Ανάθεση εργασίας