Θεωρία Αναδρομής (Μ.Π. Α.Λ.ΜΑ.)

Περιγραφή

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

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

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

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

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

Εξέταση: 10 μονάδες

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

Περιεχόμενο Μαθήματος
0. ΕΙΣΑΓΩΓΗ
    Σχέσεις και συναρτήσεις, Λέξεις και γλώσσες
 
1. ΜΗΧΑΝΕΣ TURING
    Ορισμός Μηχανής Turing
    Τι κάνουν οι Μηχανές Turing;
    Επεκτάσεις Μηχανών Turing
    Κλειστότητα REC και RE ως προς συνολοθεωρητικές πράξεις

2. ΕΛΑΧΙΣΤΙΚΑ ΑΝΑΔΡΟΜΙΚΕΣ ΣΥΝΑΡΤΗΣΕΙΣ
    Πρωτογενώς αναδρομικές συναρτήσεις
    Φραγμένη ελαχιστοποίηση
    Πλήρης πρωτογενής αναδρομή
    Ελαχιστικά αναδρομικές συναρτήσεις
    Δεύτερος ορισμός υπολογίσιμων συναρτήσεων

3. ΓΕΝΙΚΕΣ ΓΡΑΜΜΑΤΙΚΕΣ-ΙΕΡΑΡΧΙΑ CHOMSKY
    Γενικές γραμματικές
    Γραμματικές με συμφραζόμενα
    Γραμματικές χωρίς συμφραζόμενα
    Κανονικές γραμματικές
    Ιεραρχία Chomsky

4. ΜΗ-ΑΠΟΦΑΝΣΙΜΟΤΗΤΑ
    Θέση Church-Turing
    Μη-αποφανσιμότητα γλωσσών

5. ΤΟ ΘΕΩΡΗΜΑ ΤΟΥ RICE
    Το Θεώρημα του Rice για αναδρομικές γλώσσες
    Το Θεώρημα του Rice για αναδρομικά απαριθμήσιμες γλώσσες

6. ΤΟ ΘΕΩΡΗΜΑ ΑΝΑΔΡΟΜΗΣ
    Μπορούν οι μηχανές να αυτο-αναπαράγονται;
    Το Θεώρημα Αναδρομής
    Το Πρώτο Θεώρημα Μη-πληρότητας του Gödel

7. ΑΡΙΘΜΗΤΙΚΗ ΙΕΡΑΡΧΙΑ
    Αριθμητική Ιεραρχία
    Αλγοριθμικές Αναγωγές
    Πληρότητας γλωσσών ως προς σχέση αναγωγής
    Πέρα από την Αριθμητική Ιεραρχία
Βοηθήματα

- 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

Ημερολόγιο

Ανακοινώσεις