Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής

Πολυτεχνική Σχολή - Πανεπιστήμιο Ιωαννίνων

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

Course Feature
Περιγραφή μαθήματος

Κωδικός μαθήματος: ΜΥΥ501

Εβδομαδιαίες ώρες διδασκαλίας: 3,2,0

Εξάμηνο σπουδών: 5ο

Διδακτικές Μονάδες: 4

Μονάδες ECTS: 6

Ιστοσελίδα Μαθήματος: http://www.cse.uoi.gr/~palios/automata/

Προσφερόμενο:

Προαπαιτούμενα:

Περιεχόμενο:

Πεπερασμένα αυτόματα, κανονικές εκφράσεις, κανονικές γλώσσες, ιδιότητες κλειστότητας, λήμμα άντλησης, αλγόριθμοι. Αιτιοκρατία, μη αιτιοκρατία. Aυτόματα στοίβας, γραμματικές χωρίς συμφραζόμενα, γλώσσες χωρίς συμφραζόμενα, ιδιότητες κλειστότητας, λήμμα άντλησης, αλγόριθμοι. Κανονική μορφή Chomsky. Mηχανές Turing, ισοδυναμία διαφορετικών μοντέλων. Αναγνωρίσιμες, διαγνώσιμες, απαριθμήσιμες γλώσσες. Tο δόγμα των Church-Turing. Eπιλύσιμα και μη επιλύσιμα προβλήματα, το πρόβλημα αποδοχής για μηχανές Turing (halting problem), το πρόβλημα αντιστοιχίας του Post. Οι κλάσεις P και NP.

Παρατηρήσεις:

Εξ αποστάσεως διδασκαλία μέσω της εφαρμογής MS TEAMS:  Σχετικές πληροφορίες υπάρχουν στο site του μαθήματος.