Αναβάθμιση πλατφόρμας eclass Προβολή

Παρουσίαση/Προβολή

Εικόνα επιλογής

Θεωρία Πολυπλοκότητας

(ICTE266) -  

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

Περιγραφή

  • Προβλήματα, αλγόριθμοι και υπολογιστική πολυπλοκότητα
  • Μηχανές Turing
  • Αναδρομικές και αναδρομικά αριθμήσιμες γλώσσες
  • Ειδικοί τύποι και συνδυασμοί μηχανών Turing
  • Μη ντετερμινιστικές μηχανές Turing
  • Καθολικές μηχανές Turing
  • Η θέση του Church
  • Μη απο­κρισιμότητα
  • Το πρόβλημα του τερματισμού
  • Το θεώρημα του Rice
  • Κλάσεις πολυπλοκότητας και σχέσεις μεταξύ τους
  • Οι κλάσεις L, NL, P, NP, PSPACE και EXPTIME
  • Αναγωγές
  • Η έννοια της Πληρότητας
  • Το θεώρημα των Cook-Levin
  • Πληρότητα κατά NP
  • Το συμπλήρωμα της κλάσης NP
 
Αξιολόγηση
 
•  Εργασίες
   - Τρεις υποχρεωτικές εργασίες (1 μονάδα η καθεμία)
 
•  Τελική γραπτή εξέταση
 
Τελικός βαθμός = 0.7 * βαθμός τελικής εξέτασης + βαθμός εργασιών (με απαραίτητη προϋπόθεση να έχετε γράψει τουλάχιστον βάση στις εξετάσεις για να περάσετε).
 

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

  • Στοιχεία Θεωρίας Υπολογισμού (2η αμερικάνικη έκδοση, 1η έκδοση στα ελληνικά): Harry Lewis και Παπαδημητρίου Χρίστος, Εκδόσεις Κριτική, 2005 (Κωδικός βιβλίου στον Εύδοξο: 11776)
    • Αντίτυπα στη βιβλιοθήκη με ταξινομικό αριθμό QA267.L49 2005
  • Εισαγωγή στη Θεωρία Υπολογισμού (3η αμερικάνικη έκδοση, 2η έκδοση στα ελληνικά): Sipser Michael, Πανεπιστημιακές Εκδόσεις Κρήτης, 2019 (Κωδικός βιβλίου στον Εύδοξο: 86195794)
    • Αντίτυπα στη βιβλιοθήκη με ταξινομικό αριθμό QA267.S5616 2007

Συμπληρωματική Βιβλιογραφία

  • Introduction to theory of computation: Anil Maheshwari and Michiel Smid, Carleton University, 2019.
  • Theory of computational complexity (2nd edition), Ding-Zhu Du, Ker-I Ko, Wiley, 2014.

Ημερομηνία δημιουργίας

Πέμπτη 24 Σεπτεμβρίου 2015

Σελίδα μαθήματος