Υπολογιστική Πολυπλοκότητα 23-24 (CEID_NY302)

Τσίχλας Κωνσταντίνος

Περιγραφή

Το μάθημα γίνεται για τελευταία χρονιά (δυστυχώς :-)). Από το ακαδημαϊκό έτος 24-25 δεν θα υπάρχει ως υποχρεωτικό. Σχετικές μεταβατικές διατάξεις θα ανακοινωθούν.

Στα πλαίσια του μαθήματος, θα προσπαθήσουμε να ανακαλύψουμε τις δυνατότητες και τους περιορισμούς του υπολογισμού. Θα ορίσουμε απλές υπολογιστικές μηχανές, τις μηχανές Turing, οι οποίες (φαίνεται να) έχουν όλες τις δυνατότητες υπολογισμού των σύγχρονων (και των μελλοντικών) υπολογιστών. Θα δούμε τις ιδιότητές τους και θα αποδείξουμε ότι υπάρχουν προβλήματα που δεν πρόκειται ποτέ να λυθούν από υπολογιστές. Επίσης, θα ασχοληθούμε με τις κλάσεις υπολογιστικής πολυπλοκότητας P και NP και θα διατυπώσουμε το πρόβλημα P=?NP, ένα από τα πιο δύσκολα ανοικτά προβλήματα της Επιστήμης των Υπολογιστών και των Σύγχρονων Μαθηματικών. Επιπλέον, θα ανακαλύψουμε ένα πλήθος υπολογιστικών προβλημάτων που εμφανίζονται στην καθημερινή ζωή, τα οποία ναι μεν λύνονται αλλά η λύση τους απαιτεί υπερβολικά πολλούς υπολογιστικούς πόρους (π.χ., μεγάλο χρό

Περισσότερα  

Ημερολόγιο