Θεωρία Υπολογισμού

 Γλώσσες και μοντέλα υπολογισμού. Ντετερμινιστικά πεπερασμένα αυτόματα. Μή-ντετερμινισμός. Κανονικές πράξεις. Κανονικές γλώσσες και κανονικές εκφράσεις. Γραμματικές. Μή-κανονικές γλώσσες. Το Λήμμα της Άντλησης. Ντετερμινιστικά και μή-ντετερμινιστικά αυτόματα στοίβας. Γλώσσες με συμφραζόμενα και χωρίς συμφραζόμενα. Ιεραρχία 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 εβδομάδες, ενδιάμεση γραπτή εξέταση (πρόοδος), τελικές γραπτές εξετάσεις.

Σημειώσεις