Θεωρία Υπολογισμού (5ΕΠ08)
Διδάσκων : Ευριπίδης Μάρκου
ΕίδοςΕπιλογής (υποχρεωτικό)
Εξάμηνο5
ΠερίοδοςΧΕ
ECTS5
Ώρες Θεωρίας3
Ώρες Εργαστηρίου
Περιγραφή
Γλώσσες και μοντέλα υπολογισμού. Ντετερμινιστικά πεπερασμένα αυτόματα. Μή-ντετερμινισμός. Κανονικές πράξεις. Κανονικές γλώσσες και κανονικές εκφράσεις. Γραμματικές. Μή-κανονικές γλώσσες. Το Λήμμα της Άντλησης. Ντετερμινιστικά και μή-ντετερμινιστικά αυτόματα στοίβας. Γλώσσες με συμφραζόμενα και χωρίς συμφραζόμενα. Ιεραρχία Chomsky. Μηχανές Turing και υπολογίσιμες συναρτήσεις. Θέση Church-Turing. Αναγνωρίσιμες και αποφασίσιμες γλώσσες. Αναδρομικά και αναδρομικά αριθμήσιμα σύνολα. Μή-αποκρίσιμα προβλήματα. Το πρόβλημα του Τερματισμού. Υπολογιστική πολυπλοκότητα. Αναγωγές προβλημάτων. Οι κλάσεις P και NP. Πολυωνυμικοί μετασχηματισμοί και NP - πληρότητα. Το θεώρημα του Cook. NP - πλήρη προβλήματα και αναγωγές.
Μαθησιακοί Στόχοι
  • Μοντέλα υπολογισμού και τυπικές γραμματικές
  • Μηχανές Turing
  • Ντετερμινισμός και μή-ντετερμινισμός
  • Μή-επιλυσιμότητα
  • Πολυωνυμική ιεραρχία
  • Κλάσεις P και NP
Συγγράμματα/Βιβλιογραφία
  • ΘΕΜΕΛΙΩΔΕΙΣ ΕΝΝΟΙΕΣ ΤΗΣ ΕΠΕΞΕΡΓΑΣΙΑΣ ΣΗΜΑΤΩΝ, McCLELLAN, SCHAFER, YODER, "ΓΚΟΤΣΗΣ ΚΩΝ/ΝΟΣ & ΣΙΑ Ε.Ε.",  1η /2006, ΠΑΤΡΑ, 13255848
  • Βασικές Αρχές Σημάτων και Συστημάτων, Καραγιάννης Γιώργος, Μαραγκός Πέτρος, "Α. ΠΑΠΑΣΩΤΗΡΙΟΥ & ΣΙΑ Ι.Κ.Ε.", 1η έκδ./2010, ΑΘΗΝΑ, 9770
  • Βασικές Τεχνικές Ψηφιακής Επεξεργασίας Σημάτων, Μουστακίδης Γεώργιος Β., ΕΚΔΟΣΕΙΣ Α. ΤΖΙΟΛΑ & ΥΙΟΙ Α.Ε., 1η εκδ./2004, ΘΕΣ/ΝΙΚΗ, 18548755
Τρόπος Εξέτασης
Μία σειρά ασκήσεων κάθε 3 εβδομάδες, ενδιάμεση γραπτή εξέταση (πρόοδος), τελικές γραπτές εξετάσεις.
Υλικό
Σημειώσεις