Μάθημα : Αναδρομικές Συναρτήσεις

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

Στόχος του μαθήματος είναι η εισαγωγή των φοιτητών στην Θεωρία Αναδρομής, η παρουσίαση-ανάλυση των κεντρικών ιδεών αυτής. Για να επιτευχθεί αυτός ο στόχος, πέρα από τον «παραδοσιακό» φορμαλισμό των αναδρομικών συναρτήσεων, θα χρησιμοποιηθεί και ο «παραστατικότερος» φορμαλισμός των μηχανών Turing. Τα βασικά σημεία των διαλέξεων θα είναι: Πρωτογενώς Αναδρομικές και Ελαχιστικά Αναδρομικές συναρτήσεις, Ισοδυναμία των Ελαχιστικά Αναδρομικών συναρτήσεων με τις Turing Υπολογίσιμες συναρτήσεις, Θέση Church-Turing, Μη-αποφανσιμότητα γλωσσών, Θεώρημα Αναδρομής,  Πρώτο Θεώρημα Μη-πληρότητας Gödel.

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

Οι φοιτητές καλό θα ήταν να έχουν αποκτήσει κάποια εξοικείωση με την έννοια του Αλγορίθμου και να έχουν στοιχειώδεις γνώσεις από Μαθηματική Λογική και Θεωρία Συνόλων. 

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

Θα δίνεται μία τρίωρη διάλεξη την εβδομάδα στην οποία θα παρουσιάζεται η ύλη του μαθήματος. Όταν προχωράει αρκετά η παρουσίαση της ύλης κάποια από τις διαλέξεις αυτές (ή τμήμα τους) θα αφιερώνεται για την επίλυση ασκήσεων. 

Ως επιπλέον κίνητρο, οι φοιτητές θα κληθούν να επιλύσουν 2 πακέτα ασκήσεων που θα λειτουργούν βελτιωτικά στον συνολικό βαθμό που θα επιτύχουν στο μάθημα. Πιο συγκεκριμένα, οι φοιτητές θα κληθούν να σχηματίσουν ομάδες συνεργασίας (μέχρι 3 άτομα ανά ομάδα), οι ομάδες αυτές θα πρέπει να επιλύσουν τις ασκήσεις, να γράψουν τις απαντήσεις τους (κατά προτίμηση σε LaTeX) και να τις καταθέσουν στον διδάσκοντα μέσω της πλατφόρμας «η-τάξη». Μετά το πέρας αυτής της διαδικασίας, εφόσον η ορθότητα/πληρότητα των απαντήσεων που έδωσε η κάθε ομάδα ελεγχθεί από τον διδάσκοντα, τα μέλη των ομάδων θα παρουσιάσουν τις απαντήσεις των ασκήσεων στους υπόλοιπους φοιτητές (με τυχαία επιλογή). Οι παρουσιάσεις αυτές θα γίνουν τις ώρες διεξαγωγής των διαλέξεων εφόσον ο χρόνος το επιτρέπει, ή σε κάποιο έξτρα δίωρο. 

Στο τέλος του εξαμήνου οι φοιτητές θα κληθούν να συμμετάσχουν στην εξέταση του μαθήματος, κατά την διάρκεια της οποίας θα μπορούν να συμβουλεύονται τις σημειώσεις και τα βιβλία τους, αλλά δεν θα μπορούν να χρησιμοποιήσουν ηλεκτρονικές συσκευές συνδεδεμένες στο διαδίκτυο.

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

• Σχέσεις-Συναρτήσεις, Λέξεις-Γλώσσες 
• Μηχανές Turing 
• Επεκτάσεις Μηχανών Turing 
• Πρωτογενώς Αναδρομικές Συναρτήσεις
• Ελαχιστικά Αναδρομικές Συναρτήσεις
• Ισοδυναμία Ελαχιστικά Αναδρομικών και Turing Υπολογίσιμων συναρτήσεων
• Θέση Church-Turing
• Μη-αποφανσιμότητα γλωσσών 
• Απεικονιστικές αναγωγές
• Το Θεώρημα του Rice
• Το Θεώρημα Αναδρομής και εφαρμογές του
• Το (πρώτο) Θεώρημα Μη-πληρότητας του Gödel

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

Ασκήσεις: Το πολύ 1μονάδα (μισή μονάδα για κάθε πακέτο ασκήσεων)

Εξετάσεις: 10 μονάδες

Τελικός βαθμός: min{βαθμός εξέτασης+βαθμός ασκήσεων, 10}

Η επίλυση των πακέτων ασκήσεων είναι προαιρετική και δίνει την δυνατότητα στους φοιτητές που θα ασχοληθούν με αυτές να βελτιώσουν τον τελικό βαθμό τους κατά το πολύ 1 μονάδα. 

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

• Δημήτρης Ζώρος: (Πρόχειρες) σημειώσεις στη Θεωρία Αναδρομής  
• Michael Sipser: Εισαγωγή στην Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης 
• Harry R. Lewis, Χρήστος Παπαδημητρίου: Στοιχεία Θεωρίας Υπολογισμού, Εκδόσεις Κριτική
• Γιάννης Ν. Μοσχοβάκης: Αναδρομή και Υπολογισιμότητα
• John E. Hopcroft, Jefrey D. Ullman: Introduction to Automata Theory, Languages, and Computation (1st edition), Addison-Wesley
• Dexter C. Kozen: Automata and Computability, Springer
• Thomas Sudkamp: Languages and Machines An Introduction to the Theory of Computer Science (3rd Edition), Pearson