Παρουσίαση/Προβολή
ΥΠΟΛΟΓΙΣΙΜΟΤΗΤΑ και ΠΟΛΥΠΛΟΚΟΤΗΤΑ
(1769) - ΓΡΗΓΟΡΙΟΣ ΚΑΡΑΓΙΩΡΓΟΣ
Περιγραφή Μαθήματος
Τηλεδιασκέψεις του μαθήματος. Για πληροφορίες σχετικά με την εγγραφή σας στην ομάδα του μαθήματος στο MS TEAMS, θα βρείτε στις ανακοινώσεις.
Ημερομηνία δημιουργίας
Σάββατο 20 Φεβρουαρίου 2021
-
Περιεχόμενο μαθήματος
Τυπικές γλώσσες και πεπερασμένα αυτόματα: Αλφάβητα και γλώσσες, Ντετερμινιστικά πεπερασμένα αυτόματα, Μη ντετερμινιστικά πεπερασμένα αυτόματα.
Μηχανές Turing: Ορισμός της μηχανής Turing, Υπολογισμοί με μηχανές Turing, Επεκτάσεις των μηχανών Turing, Μη ντετερμινιστικές μηχανές Turing, Αριθμητικές συναρτήσεις.
Μη επιλυσιμότητα: Η θέση Church-Turing, Καθολικές μηχανές Turing, Το πρόβλημα του τερματισμού, Μη επιλύσιμα προβλήματα σχετικά με μηχανές Turing.
Υπολογιστική πολυπλοκότητα. Εισαγωγή στη θεωρία της υπολογιστικής πολυπλοκότητας. Οι βασικές κλάσεις πολυπλοκότητας χρόνου και χώρου. Το πρόβλημα P vs NP.
NP-πληρότητα. Εισαγωγή στη θεωρία της NP-πληρότητας. Αναγωγές πολυωνυμικού χρόνου. Το θεώρημα του Cook.
Προσεγγιστικοί αλγόριθμοι. Εισαγωγή στη θεωρία των προσεγγιστικών αλγορίθμων. Βασικές κλάσεις πολυπλοκότητας. Το πρόβλημα του αθροίσματος υποσυνόλου.
Μέθοδοι αξιολόγησης
Τρόποι αξιολόγησης / εξέτασης: Γραπτή εξέταση στο τέλος του εξαμήνου.
Προτεινόμενα συγγράμματα
Α1) Στοιχεία θεωρίας υπολογισμού, Lewis Harry R.,Παπαδημητρίου Χρίστος Χ.
Α2) Εισαγωγή στη Θεωρία Υπολογισμού , Michael Sipser.Μαθησιακοί στόχοι
Μαθησιακά αποτελέσματα: Στο τέλος του μαθήματος ο φοιτητής θα μπορεί να:
-
διακρίνει και να περιγράφει τα διάφορα αφηρημένα υπολογιστικά μοντέλα και τη σχέση τους με την έν-
νοια του αλγοριθμικού υπολογισμού (Church-Turing thesis)
-
εξηγεί την έννοια της αλγοριθμικής υπολογισιμότητας και τα βασικά αποτελέσματα αλγοριθμικής ανα-
ποκρισιμότητας
-
προσδιορίζει και να περιγράφει την ταξινόμηση των προβλημάτων ανάλογα με το μέγεθος των υπολογι-
στικών πόρων (χρόνος, μνήμη, κτλ.) που απαιτούνται για την επίλυση τους
-
διακρίνει τα βασικά στοιχεία της θεωρίας NP-πληρότητας και την σημασία του προβλήματος P vs NP για
την Επιστήμη των Υπολογιστών
-
αναλύει,να σχεδιάζει και να διατυπώνει αποδείξεις NP-πληρότητας
Ώρες γραφείου
Ώρες γραφείου κάθε Τετάρτη και ώρες 10:00- 11:00 και 15:00 - 16:00, ή μετά από συνεννόηση μέσω email.
-