Please ensure Javascript is enabled for purposes of website accessibility

Μάθημα : Θεωρία Αναδρομής

Κωδικός : MATH227

Θεωρία Αναδρομής

Μ.Π. Α.Λ.ΜΑ.  -  

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

This is the image of course

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

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

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

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

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

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

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

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

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

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

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

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

    6. ΤΟ ΘΕΩΡΗΜΑ ΤΟΥ RICE
        Η περίπτωση του REC
        Η περίπτωση του RE

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

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

    Βοηθήματα

    - 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

Ημερολόγιο

Προθεσμία
Γεγονός μαθήματος
Γεγονός συστήματος
Προσωπικό γεγονός

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

Όλες...