Θεωρητική Πληροφορική Ι

Περιγραφή

Προκαταρκτικά: Σύνολα, σχέσεις, αλγόριθμοι. Ρυθμός αύξησης συνάρτησης. Αλφάβητα και τυπικές γλώσσες. Πεπερασμένα αυτόματα: Πλήρη, προσδιοριστά, μη-προσδιοριστά, ισοδυναμία. Αναγνωρίσιμες Γλώσσες. Κριτήριο για τη μη-αναγνωρισιμότητα γλωσσών. Ρητές γλώσσες. Αλγόριθμοι για την ελαχιστοποίηση αυτομάτων. Αποτελέσματα αποφασιμότητας

Υπεύθυνοι Διδάσκοντες

Συγγράματα: 
Στοιχεία Θεωρίας Υπολογισμού των Η. Lewis, Χ. Παπαδημητρίου.
Εισαγωγή στη Θεωρία Υπολογισμού του M. Sipser.
Εξάμηνο: 
Διδακτικές Μονάδες: 
3
Πιστωτικές Μονάδες (ECTS): 
5.5
Ώρες: 
3ώρες
Κωδικός: 
0401
Τύπος Μαθήματος: 
X