[wpfilebase tag=list id=7 /]

Η θεματική ενότητα περιλαμβάνει τις ακόλουθες υποενότητες (γνωστικά αντικείμενα) με την πιο κάτω σειρά:

  • Αλγόριθμοι και Πολυπλοκότητα (Α’ Τόμος)
  • Αυτόματα και Τυπικές Γλώσσες (Γ’ Τόμος)
  • Θεωρία Υπολογισμού (Β’ Τόμος)

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

Στα πιο σημαντικά τμήματα της ύλης περιλαμβάνονται:

  • Πολυπλοκότητα αλγορίθμων
    • Βασικές γνώσεις θεωρίας πολυπλοκότητας. Συμβολισμοί Θ, Ο, Ω, ο και ω
    • Ταξινόμηση συναρτήσεων ως προς την πολυπλοκότητά τους.
    • Εφαρμογή του Θεωρήματος της Κυριαρχίας
    • Μέθοδος της Επανάληψης
  • Αλγόριθμοι Διαίρει και Βασίλευε
    • Λειτουργία βασικών αλγορίθμων Διαίρει και Βασίλευε: MergeSort, QuickSort, Δυαδική Αναζήτηση, Πρόβλημα της Επιλογής (QuickSelect), Αλγόριθμος Strassen κτλ.
    • Επίλυση προβλημάτων με την τεχνική «Διαίρει και Βασίλευε». Αναδρομική σχέση πολυπλοκότητας και υπολογισμός της συνάρτησης πολυπλοκότητας από την αναδρομική σχέση.
  • Δυναμικός Προγραμματισμός
    • Εφαρμογή αλγορίθμων Δυναμικού Προγραμματισμού για την επίλυση προβλημάτων.
  • Άπληστοι Αλγόριθμοι
    • Βασικές αρχές άπληστων αλγορίθμων και εφαρμογή τους για την επίλυση προβλημάτων.
    • Απόδειξη ορθότητας ή απόδειξη μη βελτιστότητας για άπληστους αλγόριθμους.
  • Κανονικές Εκφράσεις και Πεπερασμένα Αυτόματα
    • Παραγωγή κανονικής έκφρασης από την περιγραφή μίας γλώσσας
    • Κατασκευή Πεπερασμένου Αυτόματου από Κανονική Έκφραση
    • Ελάχιστο πλήθος καταστάσεων Πεπερασμένου Αυτόματου και ελαχιστοποίηση (απλοποίηση) Πεπερασμένου Αυτόματου
    • Πεπερασμένο Αυτόματο για το σύμπληρωμα, τομή, ένωση και διαφορά Κανονικών Γλωσσών
    • Απαλοιφή ε-μεταβάσεων
    • Μετατροπή Μη-Ντετερμινιστικού Πεπερασμένου Αυτόματου (ΜΠΑ) σε ντετερμινιστικό (ΝΠΑ)
  • Γραμματικές και Αυτόματα Στοίβας
    • Γραμματικές Ανεξάρτητες Συμφραζομένων (Α.Σ.). Ορισμός Γραμματικής που αντιστοιχεί σε κάποια Α.Σ.
    • Περιγραφή Ντετερμισνιστικού ή Μη-ντετερμινιστικού Αυτόματου Στοίβας
    • Δημιουργία Αυτόματου Στοίβας που αντιστοιχεί σε κάποια Γραμματική Ανεξάρτητων Συμφραζομένων
    • Δημιουργία Γραμματικής Α.Σ. που αντιστοιχεί σε κανονική έκφραση
  • Μηχανές Turing (ΜΤ)
    • Περιγραφή Μ.Τ. για συγκεκριμένη γλώσσα
    • Αποφασίσιμες και Αποδεκτές γλώσσες
  • Μη επιλυσιμότητα
    • Μη επιλύσιμα προβλήματα
    • Απόδειξη ότι μία γλώσσα είναι μη αποφασίσιμη
    • Γλώσσες που είναι αποδεκτές αλλά όχι αποφασίσιμες
    • Γλώσσες που δεν είναι αποδεκτές
    • Τομή, ένωση, διαφορά, συμπλήρωμα αποφασίσμων-αποδεκτών γλωσσών
  • ΝΡ-πλήρη προβλήματα
    • P, ΝΡ και EXP προβλήματα
    • ΝΠ-πλήρη και NP-hard (ΝΡ-δύσκολα) προβλήματα
    • Χρήση αναγωγής για να αποδείξουμε ότι ένα πρόβλημα είναι NP-πλήρες ή NP-hard