Παρουσίαση/Προβολή

(INF225) -  ΦΟΥΣΤΟΥΚΟΥ ΕΥΓΕΝΙΑ

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

Το μάθημα έχει στόχο να δείξει τους στενούς δεσμούς μεταξύ  Υπολογισιμότητας, Πολυπλοκότητας και Λογικής. To βασικό αντικείμενο της μελέτης μας είναι η έννοια του αλγορίθμου. Ενα πολύ βασικό αποτέλεσμα είναι η ύπαρξη μη επιλύσιμων προβλημάτων δηλαδή προβλημάτων για τα οποία (έχει αποδειχτεί ότι) δεν υπάρχει αλγόριθμος. Ενα άλλο πολύ βασικό αποτέλεσμα είναι ότι οι υπολογιστικοί πόροι (χρόνος/χώρος που χρειάζεται ένας αλγόριθμος) και οι περιγραφικοί πόροι (συμβολική έκφραση που περιγράφει έναν αλγόριθμο) είναι δύο χαραχτηριστικά των αλγορίθμων που σχετίζονται παρ’ότι φαίνονται διαφορετικά.

 

Στο πρώτο μέρος του μαθήματος μελετώνται οι υπολογίσιμες συναρτήσεις  σε δύο ισοδύναμες μοντελοποιήσεις τους (αναδρομικές συναρτήσεις και Turing υπολογίσιμες συναρτήσεις)  καθώς και οι έννοιες επιλυσιμότητας και μη επιλυσιμότητας.

Περιεχόμενο πρώτου μέρους: Επαγωγικές αποδείξεις και αναδρομικοί ορισμοί. Εισαγωγή μοντέλων υπολογισμού. Πρωτογενείς αναδρομικές συναρτήσεις και σχέσεις. Μερικές αναδρομικές συναρτήσεις και ελαχιστοποίηση. Μηχανική υπολογισιμότητα. Μηχανές Turing και Turing υπολογίσιμες συναρτήσεις. Θέση Church- Turing. Τα βασικά θεωρήματα: κανονικού τύπου, απαρίθμησης και παραμέτρων (s-m-n). Αναδρομικά απαριθμίσιμα σύνολα και ανεπίλυτα προβλήματα. Ορισιμότητα και αριθμητική ιεραρχία.

Στο δεύτερο μέρος του μαθήματος δίδονται στοιχεία Λογικής και Πολυπλοκότητας (κλασικής και  παραμετρικής)  και  ο λογικός  χαρακτηρισμός των κανονικών γλωσσών  μέσω  της Μοναδιαίας Δευτεροβάθμιας Λογικής (Monadic Second-order Logic ή ΜSO). Ειδικότερα μελετώνται κατασκευές αυτομάτων για τύπους της  ΜSO  σε δέντρα και σε δομές φραγμένου δεντροπλάτους και δείχνεται πώς διάφορα NP-πλήρη προβλήματα γράφων, που εκφράζoνται σε MSO, γίνονται πολυωνυμικού χρόνου όταν σταθεροποιούμε το δεντροπλάτος  ( δηλαδή μία παράμετρο που μετράει την «ομοιότητα» που έχει ένας γράφος με δέντρο). 

Περιεχόμενο δεύτερου μέρους: Λογικές (πρωτοβάθμια FO, δευτεροβάθμια SO, μοναδιαία δευτεροβάθμια MSO) και δομές, ειδικά δέντρα και γράφοι. Αυτόματα σε δέντρα, Αυτόματα σε δεντρικές αναπαραστάσεις γράφων. Εννοιες κλασσικής και παραμετρικής πολυπλοκότητας.

Αν το επιτρέπει ο χρόνος,  θα γίνει αναφορά σε βασικά θεωρήματα Περιγραφικής Πολυπλοκότητας όπως είναι  ο  λογικός χαρακτηρισμός  της  κλάσης πολυπλοκότητας P (P = inflationary fixpoint logic, on ordered structures) και της  κλάσης πολυπλοκότητας NP (NP=Εxistential second-order logic).

 

Ενδεικτική βιβλιογραφία:

Ι.1.   Μιχάλης Μυτιληναίος: Υπολογισιμότητα και Πολυπλοκότητα, Εκδόσεις Οικονομικού Πανεπιστημίου Αθηνών.                                                                                                          

 Ι.2.    Aθανάσιoς Τζουβάρας, Θεωρία Αναδρομικών συναρτήσεων και υπολογισιμότητας (το σύγγραμμα αυτό υπάρχει μόνο σε ηλεκτρονική μορφή).  

Ι.3.    A. Shen and N.K. Vereshchagin. Computable functions. Student Mathematical Library, Vol. 19 , American Mathematical Society 2003.

Ι. 4.   Γιώργος Τουρλάκης: Εισαγωγή στην Υπολογιστική, Πανεπιστημιακές Εκδόσεις Κρήτης, 1994. 

ΙΙ.5.    W. Thomas. Languages, automata, and logic. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume III, pages 389-455. Springer, New York, 1997.

ΙΙ.6.    Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer-Verlag Berlin Heidelberg 2006 Springer Berlin Heidelberg New York.

 

 

 

Ημερομηνία δημιουργίας

Παρασκευή, 4 Μαρτίου 2011