Anteprima

Selected image

Θεωρία Υπολογισμού [open]

(321-6701) -  Αλέξης Καπόρης

Descrizione del Corso

 

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

Creation Date

martedì 11 novembre 2014

  • Syllabus

    Περιεχόμενο μαθήματος

    • Κανονικές γλώσσες, πεπερασμένα αυτόματα.
    • Λήμμα άντλησης για κανονικές γλώσσες.
    • Γραμματικές και γλώσσες χωρίς συμφραζόμενα.
    • Αυτόματα στοίβας, λήμμα άντλησης για γλώσσες χωρίς συμφραζόμενα.
    • Μηχανές Turing, υπολογισιμότητα.
    • Η θέση των Church-Turing. Μη-υπολογισιμότητα, το πρόβλημα του τερματισμού.
    • Χρονική πολυπλοκότητα, η κλάση Ρ, η θέση των Cook-Karp.
    • Αναγωγή και πληρότητα.
    • Μη-ντετερμινισμός και NP-πληρότητα, σχέση Ρ και ΝΡ.
    • Αλγοριθμικές συνέπειες NP-πληρότητας.

    Μαθησιακοί στόχοι

    Ο στόχος είναι η κατανόηση των δυνατοτήτων και των περιορισμών των μοντέλων υπολογισμού που γνωρίζουμε ως σήμερα. 

    Βιβλιογραφία

    Online readings

    Μέθοδοι διδασκαλίας

    • Διδασκαλία καθ΄ έδρας και συμπληρωματική-ενισχυτική εκπαίδευση μέσω ασύγχρονης πλατφόρμας.
    • Εργαστήριο.

    Μέθοδοι αξιολόγησης

    • Εξετάσεις
    • Πρόοδοι

    Προαπαιτούμενα

    Προ απαιτούνται στοιχειώδεις γνώσεις προγραμματισμού και ωριμότητα σκέψης, ανάλυσης & σύνθεσης προβλημάτων.   

    Διδάσκοντες

     

    Αλέξης Καπόρης

    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.