3434 Αυτόματα και Πολυπλοκότητα

    Υποχρεωτικό Μάθημα Πυρήνα, Δ’ εξάμηνο, 7 μονάδες ECTS                      

    URL: https://eclass.aueb.gr/courses/INF148/

    Διδάσκουσα: Επίκουρη Καθηγήτρια Ευγενία Φουστούκου

    Περιεχόμενο

    Θεμελιώδεις τεχνικές απόδειξης (επαγωγικές αποδείξεις, αρχή περιστεριώνα, διαγωνιοποίηση). Αλφάβητα, συμβολοσειρές, γλώσσες και προβλήματα. Κανονικές γλώσσες. Κανονικές εκφράσεις. Πεπερασμένα αυτόματα (αιτιοκρατικά, μη αιτιοκρατικά και η ισοδυναμία τους). Μετατροπή κανονικών εκφράσεων σε πεπερασμένα αυτόματα και αντίστροφα. Πολυπλοκότητα προβλημάτων απόφασης που αφορούν πεπερασμένα αυτόματα. Λήμμα άντλησης για κανονικές γλώσσες. Παραδείγματα γλωσσών χωρίς συμφραζόμενα, αυτομάτων στοίβας και ισοδύναμων γραμματικών. Μηχανές Turing (αιτιοκρατικές, μη αιτιοκρατικές και η ισοδυναμία τους). Turing-αποφασίσιμες γλώσσες (αναδρομικές γλώσσες). Turing-αναγνωρίσιμες γλώσσες (αναδρομικά απαριθμήσιμες γλώσσες). Επιλυσιμότητα, αναγωγές, μη επιλύσιμα προβλήματα (πρόβλημα τερματισμού για μηχανές Turing κ.α.). Πολυπλοκότητα, κλάσεις P και NP, αναγωγές πολυωνυμικού χρόνου, ΝΡ-πλήρη προβλήματα (3-ικανοποιησιμότητα, κλίκα κ.α.).

    Μαθησιακά Αποτελέσματα

    Μετά την επιτυχή ολοκλήρωση του μαθήματος, οι φοιτητές θα είναι σε θέση:

    • Να κατανοούν και να χειρίζονται θεμελιώδεις έννοιες της θεωρίας Τυπικών Γλωσσών και Υπολογισμού (όπως υπολογισμός, μηχανή πεπερασμένων καταστάσεων, ντετερμινισμός, μη ντετερμινισμός) καθώς και βασικά θεωρήματα (όπως το Λήμμα Άντλησης, η ισοδυναμία ντετερμινιστικών και μη ντετερμινιστικών αυτομάτων, η μη επιλυσιμότητα του προβλήματος του τερματισμού μηχανών Turing κτλ.).
    • Να περιγράφουν και να χειρίζονται τα βασικά υπολογιστικά μοντέλα, δηλ. πεπερασμένα αυτόματα, αυτόματα στοίβας, μηχανές Turing (σε αύξουσα σειρά εκφραστικότητας).
    • Να μοντελοποιούν και να ταξινομούν τα επιλύσιμα προβλήματα απόφασης ως γλώσσες (κανονικές γλώσσες, γλώσσες χωρίς συμφραζόμενα, Τuring-αποφασίσιμες γλώσσες και Τuring-αναγνωρίσιμες γλώσσες) ανάλογα με το υπολογιστικό μοντέλο που είναι επαρκές για να τα επιλύσει.
    • Να αποδεικνύουν τη μη επιλυσιμότητα γνωστών προβλημάτων απόφασης με χρήση διαγωνιοποίησης και αναγωγών.
    • Να ταξινομούν επιλύσιμα προβλήματα απόφασης ανάλογα με τους απαραίτητους σε χρόνο πόρους και ανάλογα με το ντετερμινιστικό ή όχι μοντέλο μηχανής (κλάσεις πολυπλοκότητας P και ΝP, NP-πλήρη προβλήματα, αναγωγές πολυωνυμικού χρόνου).

    Προαπαιτούμενα Μαθήματα

    Για να εγγραφεί στο μάθημα, ο φοιτητής πρέπει να έχει εξεταστεί επιτυχώς σε προηγούμενο εξάμηνο στο μάθημα «Διακριτά Μαθηματικά».

    Συνιστώμενη Βιβλιογραφία

    • Στοιχεία Θεωρίας Υπολογισμού, H. Lewis, Χ. Παπαδημητρίου, εκδόσεις Κριτική, 2005.
    • Εισαγωγή στη Θεωρία Υπολογισμού, M. Sipser, Πανεπιστημιακές Εκδόσεις Κρήτης, 2007.
    • Automata and Computability, Dexter Kozen, Undergraduate Texts in Computer Science Springer, 1997.
    • Theory of computation, George Tourlakis, Wiley Editions, 2012.

    Διδακτικές και Μαθησιακές Μέθοδοι

    Διαλέξεις (2 διαλέξεις των 2 ωρών εβδομαδιαίως), φροντιστήριο (1 φροντιστήριο των 2 ωρών εβδομαδιαίως), γραπτή προαιρετική ενδιάμεση εξέταση (πρόοδος) και προαιρετικές ατομικές ασκήσεις στο σπίτι.

    Μέθοδοι Αξιολόγησης/Βαθμολόγησης

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