ΠΛΗ30 - Θεμελιώσεις Επιστήμης Η/Υ

Υποενότητες:

  • Αλγόριθμοι και Πολυπλοκότητα (1ος τόμος)
  • Αυτόματα και Τυπικές Γλώσσες (3ος τόμος)
  • Θεωρία υπολογισμού (2ος τόμος)
Προαπαιτούμενα: Η ενότητα απαιτεί κάποιες Μαθηματικές γνώσεις και έχει ως προαπαιτούμενη την ενότητα ΠΛΗ20.

Εργασίες: Οι φοιτητές θα πρέπει να εκπονήσουν 5 συνολικά εργασίες:
  • 1η εργασία: Εύρεση πολυπλοκότητας αλγορίθμων. Κατάταξη αλγορίθμων ανάλογα με την πολυπλοκότητά τους. Το θεώρημα Κυριαρχίας. Δυναμικός προγραμματισμός.
  • 2η εργασία: Δυναμικός προγραμματισμός. Άπληστοι αλγόριθμοι. Κανονικές γλώσσες και Πεπερασμένα Αυτόματα.
  • 3η εργασία: Ντετερμινιστικά και μη Ντετερμινιστικά Πεπεπρασμένα Αυτόματα. ε κινήσεις. Λήμμα Άντλησης. Γραμμαρικές ΑΣ.
  • 4η εργασία: Αυτόματα Στοίβας. Μηχανές Turing. Αποαφασίσιμες και αποδεκτές γλώσσες. Μη αποφασίσιμες γλώσσες.
  • 5η εργασία: Μη επιλυσιμότητα. Ρ και ΝΡ προβλήματα. Απόδειξη ΝΡ πληρότητας μέσω αναγωγής.
Ύλη: Στα πιο σημαντικά τμήματα της ύλης περιλαμβάνονται
  • Πολυπλοκότητα αλγορίθμων
    • Εύρεση πολυπλοκότητας αλγορίθμου
    • Υπολογισμόςπολυπλοκότητας με βάση τον αναδρομικό τύπο
    • Εφαρμογή θεωρήματος Κυριαρχίας
    • Κατασκευή δέντρου αναδρομής
  • Σχεδίαση αλγορίθμων
    • Αλγόριθμοι Διαίρει και Βασίλευε
    • Δυναμικός προγραμματισμός
    • Άπληστοι αλγόριθμοι
  • Κανονικές γλώσσες και Πεπερασμένα Αυτόματα
    • Εύρεση κανονικής έφρασης για γλώσσα
    • Περιγραφή γλώσσας με βάση την κανονική έκφραση
    • Κατασκευή Πεπερασμένου Αυτόματου
    • Μετατροπή από ΜΠΑ σε ΝΠΑ
    • Απαλοιφή ε κινήσεων
    • Κατασκευή κανονικής γλώσσας από Πεπερασμένο Αυτόματο
    • Λήμμα της Άντλησης
    • Απόδειξη μη κανονικότητας είτε με το Λήμμα της Άντλησης είτε με διακρινόμενες συμβολοσειρές
  • Γραμματικές Ανεξάρτητες Συμφραζομένων και Αυτόματα Στοίβας
    • Κατασκευή γραμματικής Ανεξάρτητης Συμφραζομένων
    • Κατασκευή ντετερμινιστικού Αυτόματου Στοίβας
    • Κατασκευή μη ντετερμινιστικού Αυτόματου Στοίβας
    • Λήμμα της άντλησης για γλώσσες Α.Σ.
  • Μηχανές Turing
    • Κατασκευή μηχανής Turing
    • Αποφασίσιμες και αποδεκτές γλώσσες
    • Απόδειξη μη επιλυσιμότητας μέσω αναγωγής
  • ΝΡ πληρότητα
    • Απόδειξη ότι ένα πρόβλημα είναι ΝΡ πλήρες ή ΝΡ δύσκολο
Εξετάσεις:
  • Με κλειστές σημειώσεις και βιβλία.
  • Δεν επιτρέπονται τυπολόγια.
  • Κάποια λίγα πράγματα όπως το Λήμμα της Άντλησης δίνονται ως υπόδειξη στα θέματα.
Μπορείτε να προβάλετε και να κατεβάσετε τις εργασίες και θέματα εξετάσεων παρελθόντων ετών, ακολουθώντας τον πιο κάτω σύνδεσμο: