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

Ο στόχος του μαθήματος είναι η κατανόηση των δυνατοτήτων και των περιορισμών του υπολογισμού. Παρουσιάζει την εξέλιξη των μοντέλων υπολογισμού ως τώρα. Αρχικά με απλές μηχανές, όπως τα πεπερασμένα αυτόματα, ως την πιο ισχυρή μηχανή Turing. Για κάθε ένα μοντέλο υπολογισμού παρουσιάζει τα προβλήματα που μπορούν να λυθούν, όπως και τα μη επιλύσιμα προβλήματα. Η παρουσίαση αρχίζει από τα απλούστερα προβλήματα, όπως οι κανονικές γλώσσες, ως τα πιο σύνθετα Turing επιλύσιμα προβλήματα. Παρουσιάζει την θέση των Church-Turing ότι η μηχανή Turing είναι ικανή να υλοποιεί κάθε αλγοριθμική ιδέα. Γίνεται εκτενής παρουσίαση των τεχνικών απόδειξης της μη επιλυσιμότητας ενός προβλήματος από το εκάστοτε μοντέλο υπολογισμού. Η εισαγωγή σε αυτές τις τεχνικές γίνεται με τις πιο απλές, όπως τα Λήμματα Άντλησης για γλώσσες κανονικές και ανεξάρτητες συμφραζομένων. Στην συνέχεια παρουσιάζουμε την πιο σύνθετη τεχνική της Διαγωνοποίησης για Turing μη επιλύσιμα προβλήματα, όπως επίσης και της Αναγωγής. Τέλος, όσον αφορά την χρονική πολυπλοκότητα, παρουσιάζονται οι κλάσεις P των ντετερμινιστικά πολυωνυμικού χρόνου επιλύσιμων προβλημάτων και NP των μη ντετερμινιστικά πολυωνυμικού χρόνου επιλύσιμων προβλημάτων. Παρουσιάζονται και οι σχέσεις και οι αλγοριθμικές συνέπειες των κλάσεων P και NP.

Video-Διαλέξεις