Υπολογιστική πολυπλοκότητα

Πανεπιστήμιο Πατρών

Μηχανικών Η/Υ και Πληροφορικής

Έτος: 2020-2021

Διδάσκων: Τσίχλας Κωνσταντίνος

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

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