Θεωρία Υπολογισμού [open] (321-6701)
Αλέξης Καπόρης
Ο στόχος του μαθήματος είναι η κατανόηση των δυνατοτήτων και των περιορισμών του υπολογισμού. Παρουσιάζει την εξέλιξη των μοντέλων υπολογισμού ως τώρα. Αρχικά με απλές μηχανές, όπως τα πεπερασμένα αυτόματα, ως την πιο ισχυρή μηχανή Turing. Για κάθε ένα μοντέλο υπολογισμού παρουσιάζει τα προβλήματα που μπορούν να λυθούν, όπως και τα μη επιλύσιμα προβλήματα. Η παρουσίαση αρχίζει από τα απλούστερα προβλήματα, όπως οι κανονικές γλώσσες, ως τα πιο σύνθετα Turingεπιλύσιμα προβλήματα. Παρουσιάζει την θέση των Church-Turingότι η μηχανή Turing είναι ικανή να υλοποιεί κάθε αλγοριθμική ιδέα. Γίνεται εκτενής παρουσίαση των τεχνικών απόδειξης της μη επιλυσιμότητας ενός προβλήματος από το εκάστοτε μοντέλο υπολογισμού. Η εισαγωγή σε αυτές τις τεχνικές γίνεται με τις πιο απλές, όπως τα Λήμματα Άντλησης για γλώσσες κανονικές και ανεξάρτητες συμφραζομένων. Στην συνέχεια παρουσιάζουμε την πιο σύνθετη τεχνική της Διαγωνοποίησης για Turing μη επιλύσιμα προβλήματα, όπως επίσης και της Αναγωγής. Τέλος, όσον αφορά την χρονική πολυπλοκότητα, παρουσιάζονται οι κλάσεις Pτων ντετερμινιστικά πολυωνυμικού χρόνου επιλύσιμων προβλημάτων και NP των μη ντετερμινιστικά πολυωνυμικού χρόνου επιλύσιμων προβλημάτων. Παρουσιάζονται και οι σχέσεις και οι αλγοριθμικές συνέπειες των κλάσεων Pκαι NP.
Less
Ο στόχος του μαθήματος είναι η κατανόηση των δυνατοτήτων και των περιορισμών του υπολογισμού. Παρουσιάζει την εξέλιξη των μοντέλων υπολογισμού ως τώρα. Αρχικά με απλές μηχανές, όπως τα πεπερασμένα αυτόματα, ως την πιο ισχυρή μηχανή Turing. Για κάθε ένα μοντέλο υπολογισμού παρουσιάζει τα προβλήματα που μπορούν να λυθούν, όπως και τα μη επιλύσιμα προβλήματα. Η παρουσίαση αρχίζει από τα απλούστερα προβλήματα, όπως οι κανονικές γλώσσες, ως τα πιο σύνθετα Turingεπιλύσιμα προβλήματα. Παρουσιάζει την θέση των Church-Turingότι η μηχανή Turing είναι ικανή να υλοποιεί κάθε αλγοριθμική ιδέα. Γίνεται εκτενής παρουσίαση των τεχνικών απόδειξης της μη επιλυσιμότητας ενός προβλήματος από το εκάστοτε μοντέλο υπολογισμού. Η εισαγωγή σε αυτές τις τεχνικές γίνεται με τις πιο απλές, όπως τα Λήμματα Άντλησης για γλώσσες κανονικές και ανεξάρτητες συμφραζομένων. Στην συνέχεια παρουσιάζουμε την πιο σύνθετη τεχνική της Διαγωνοποίησης για Turing μη επιλύσιμα προβλήματα, όπως επίσης και της Αναγωγής. Τέλος
Ο στόχος του μαθήματος είναι η κατανόηση των δυνατοτήτων και των περιορισμών του υπολογισμού. Παρουσιάζει την εξέλιξη των μοντέλων υπολογισμού ως τώρα. Αρχικά με απλές μηχανές, όπως τα πεπερασμένα αυτόματα, ως την πιο ισχυρή μηχανή Turing. Για κάθε ένα μοντέλο υπολογισμού παρουσιάζει τα προβλήματα που μπορούν να λυθούν, όπως και τα μη επιλύσιμα προβλήματα. Η παρουσίαση αρχίζει από τα απλούστερα προβλήματα, όπως οι κανονικές γλώσσες, ως τα πιο σύνθετα Turingεπιλύσιμα προβλήματα. Παρουσιάζει την θέση των Church-Turingότι η μηχανή Turing είναι ικανή να υλοποιεί κάθε αλγοριθμική ιδέα. Γίνεται εκτενής παρουσίαση των τεχνικών απόδειξης της μη επιλυσιμότητας ενός προβλήματος από το εκάστοτε μοντέλο υπολογισμού. Η εισαγωγή σε αυτές τις τεχνικές γίνεται με τις πιο απλές, όπως τα Λήμματα Άντλησης για γλώσσες κανονικές και ανεξάρτητες συμφραζομένων. Στην συνέχεια παρουσιάζουμε την πιο σύνθετη τεχνική της Διαγωνοποίησης για Turing μη επιλύσιμα προβλήματα, όπως επίσης και της Αναγωγής. Τέλος
Syllabus
Περιεχόμενο μαθήματος
- Κανονικές γλώσσες, πεπερασμένα αυτόματα.
- Λήμμα άντλησης για κανονικές γλώσσες.
- Γραμματικές και γλώσσες χωρίς συμφραζόμενα.
- Αυτόματα στοίβας, λήμμα άντλησης για γλώσσες χωρίς συμφραζόμενα.
- Μηχανές Turing, υπολογισιμότητα.
- Η θέση των Church-Turing. Μη-υπολογισιμότητα, το πρόβλημα του τερματισμού.
- Χρονική πολυπλοκότητα, η κλάση Ρ, η θέση των Cook-Karp.
- Αναγωγή και πληρότητα.
- Μη-ντετερμινισμός και NP-πληρότητα, σχέση Ρ και ΝΡ.
- Αλγοριθμικές συνέπειες NP-πληρότητας.
Μαθησιακοί στόχοι
Ο στόχος είναι η κατανόηση των δυνατοτήτων και των περιορισμών των μοντέλων υπολογισμού που γνωρίζουμε ως σήμερα.
Βιβλιογραφία
Online readings
- ΜΙΤ Theory of Computation
- Berkley Theory
- Harvard Theory of Computation
- Princeton Theory of Computation
- Stanford Theory of Computation
- Coursera Automata J. Ullman and more lectures here.
- Πληροφορικής Αθηνών Θεωρία Υπολογισμού Σ. Κολλιόπουλος.
- NTUA Θεωρία Υπολογισμού Δ. Φωτάκης
Μέθοδοι διδασκαλίας
- Διδασκαλία καθ΄ έδρας και συμπληρωματική-ενισχυτική εκπαίδευση μέσω ασύγχρονης πλατφόρμας.
- Εργαστήριο.
Μέθοδοι αξιολόγησης
- Εξετάσεις
- Πρόοδοι
Προαπαιτούμενα
Προ απαιτούνται στοιχειώδεις γνώσεις προγραμματισμού και ωριμότητα σκέψης, ανάλυσης & σύνθεσης προβλημάτων.
Διδάσκοντες
Αλέξης Καπόρης
First academic degree, Department of Mathematics, U. Patras. Phd Department of Computer Engineering & Informatics,U. of Patras. Post doctoral researcher at the same Department. His research has also been supported by CTI "Diophantus". He serves as Assistant Professor at Information and Communication Systems Department.
Ομάδα στόχος
Οι φοιτητές/απόφοιτοι του τμήματος Μηχανικών Πληροφοριακών και Επικοινωνιακών Συστημάτων, Τμημάτων Πληροφορικής, Μαθηματικών και Πολυτεχνικών Σχολών Ηλεκτρολόγων και Ηλεκτρονικών Μηχανικών.
Ενδιαφερόμενοι για τη θεματική περιοχή της Θεωρίας Υπολογισμού, της Πολυπλοκότητας και της Ανάλυσης Αλγορίθμων.
Προτεινόμενα συγγράμματα
- Εισαγωγή στην Θεωρία Υπολογισμού Michael Sipser.
- H. Lewis και Χ. Παπαδημητρίου. Στοιχεία Θεωρίας Υπολογισμού. Κριτική, 2005.
- J. Hopcroft, R. Motwani, J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2000.
- C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
- Θεωρία Υπολογισμού μέρος Α, μέρος Β, μέρος Γ, Γ. Γεωργακόπουλος.
- S. Arora. Computational Complexity: A Modern Approach. 2006.
- M.R. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.
- Κανονικές γλώσσες, πεπερασμένα αυτόματα.
- Λήμμα άντλησης για κανονικές γλώσσες.
- Γραμματικές και γλώσσες χωρίς συμφραζόμενα.
- Αυτόματα στοίβας, λήμμα άντλησης για γλώσσες χωρίς συμφραζόμενα.
- Μηχανές Turing, υπολογισιμότητα.
- Η θέση των Church-Turing. Μη-υπολογισιμότητα, το πρόβλημα του τερματισμού.
- Χρονική πολυπλοκότητα, η κλάση Ρ, η θέση των Cook-Karp.
- Αναγωγή και πληρότητα.
- Μη-ντετερμινισμός και NP-πληρότητα, σχέση Ρ και ΝΡ.
- Αλγοριθμικές συνέπειες NP-πληρότητας.
Ο στόχος είναι η κατανόηση των δυνατοτήτων και των περιορισμών των μοντέλων υπολογισμού που γνωρίζουμε ως σήμερα.
Online readings
- ΜΙΤ Theory of Computation
- Berkley Theory
- Harvard Theory of Computation
- Princeton Theory of Computation
- Stanford Theory of Computation
- Coursera Automata J. Ullman and more lectures here.
- Πληροφορικής Αθηνών Θεωρία Υπολογισμού Σ. Κολλιόπουλος.
- NTUA Θεωρία Υπολογισμού Δ. Φωτάκης
- Διδασκαλία καθ΄ έδρας και συμπληρωματική-ενισχυτική εκπαίδευση μέσω ασύγχρονης πλατφόρμας.
- Εργαστήριο.
- Εξετάσεις
- Πρόοδοι
Προ απαιτούνται στοιχειώδεις γνώσεις προγραμματισμού και ωριμότητα σκέψης, ανάλυσης & σύνθεσης προβλημάτων.
Αλέξης Καπόρης
First academic degree, Department of Mathematics, U. Patras. Phd Department of Computer Engineering & Informatics,U. of Patras. Post doctoral researcher at the same Department. His research has also been supported by CTI "Diophantus". He serves as Assistant Professor at Information and Communication Systems Department.
Οι φοιτητές/απόφοιτοι του τμήματος Μηχανικών Πληροφοριακών και Επικοινωνιακών Συστημάτων, Τμημάτων Πληροφορικής, Μαθηματικών και Πολυτεχνικών Σχολών Ηλεκτρολόγων και Ηλεκτρονικών Μηχανικών.
Ενδιαφερόμενοι για τη θεματική περιοχή της Θεωρίας Υπολογισμού, της Πολυπλοκότητας και της Ανάλυσης Αλγορίθμων.
- Εισαγωγή στην Θεωρία Υπολογισμού Michael Sipser.
- H. Lewis και Χ. Παπαδημητρίου. Στοιχεία Θεωρίας Υπολογισμού. Κριτική, 2005.
- J. Hopcroft, R. Motwani, J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2000.
- C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
- Θεωρία Υπολογισμού μέρος Α, μέρος Β, μέρος Γ, Γ. Γεωργακόπουλος.
- S. Arora. Computational Complexity: A Modern Approach. 2006.
- M.R. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.
Τρόπος σύνταξης για Κανονικές γλώσσες, κατασκευές πεπερασμένων αυτομάτων.
Παρουσίαση Λήμματος άντλησης για κανονικές γλώσσες
Σύνταξη Γραμματικών και γλωσσών χωρίς συμφραζόμενα.
Περιγραφή και κατασκευή Αυτομάτων στοίβας, παρουσίαση και χρήση λήμματος άντλησης για γλώσσες χωρίς συμφραζόμενα.
Περιγραφή και κατασκευή μηχανών Turing, χρήση μηχανών για επίλυση προβλημάτων.
Η θέση των Church-Turing για το ποια προβλήματα μπορούν να υπολογιστούν. Περιγραφή και παρουσίαση μη-υπολογίσιμων προβλημάτων. Απόδειξη ότι το πρόβλημα του τερματισμού είναι μη επιλύσιμο με την μέθοδο της διαγωνοποίησης.
Υπολογισμός του χρόνου υπολογισμού ενός αλγορίθμου, η κλάση P των προβλημάτων που λύνονται αποδοτικά, η θέση των Cook-Karp.
Παρουσίαση και χρήση της τεχνικής της Αναγωγής και εφαρμογή της σε αποδείξεις πληρότητας.
Μη-ντετερμινισμός υπολογισμός από μηχανές Turing και NP-πληρότητα, σχέση μεταξύ κλάσης Ρ με προβλήματα που λύνονται αποδοτικά και κλάσης ΝΡ
Αλγοριθμικές συνέπειες NP-πληρότητας.
Open Academic Course
Num. of Visits : 4231
Num. of Hits : 30387
