ΘΕΩΡΙΑ ΤΥΠΙΚΩΝ ΓΛΩΣΣΩΝ

Πληροφορίες Μαθήματος
ΤίτλοςΘΕΩΡΙΑ ΤΥΠΙΚΩΝ ΓΛΩΣΣΩΝ / Formal Language Theory
Κωδικός0838
ΣχολήΘετικών Επιστημών
ΤμήμαΜαθηματικών
Κύκλος / Επίπεδο1ος / Προπτυχιακό, 2ος / Μεταπτυχιακό
Περίοδος ΔιδασκαλίαςΧειμερινή
Υπεύθυνος/ηΓεώργιος Ραχώνης
ΚοινόΝαι
ΚατάστασηΕνεργό
Course ID40000060

Πρόγραμμα Σπουδών: ΠΜΣ Τμήματος Μαθηματικών (2018-σήμερα)

Εγγεγραμμένοι φοιτητές: 6
ΚατεύθυνσηΤύπος ΠαρακολούθησηςΕξάμηνοΈτοςECTS
ΘΕΩΡΗΤΙΚΗ ΠΛΗΡΟΦΟΡΙΚΗ ΚΑΙ ΘΕΩΡΙΑ ΣΥΣΤΗΜΑΤΩΝ KAI ΕΛΕΓΧΟΥΑ1110
ΣΤΑΤΙΣΤΙΚΗ ΚΑΙ ΜΟΝΤΕΛΟΠΟΙΗΣΗΥποχρεωτικό1110

Πληροφορίες Τάξης
ΤίτλοςΘΕΩΡΙΑ ΤΥΠΙΚΩΝ ΓΛΩΣΣΩΝ
Ακαδημαϊκό Έτος2020 – 2021
Περίοδος ΤάξηςΧειμερινή
Διδάσκοντες μέλη ΔΕΠ
Ώρες Εβδομαδιαία3
Class ID
600181058
Τύπος Μαθήματος 2016-2020
  • Υποβάθρου
  • Επιστημονικής Περιοχής
  • Ανάπτυξης Δεξιοτήτων
Τύπος Μαθήματος 2011-2015
Ειδικού Υποβάθρου / Κορμού
Τρόπος Παράδοσης
  • Πρόσωπο με πρόσωπο
Ηλεκτρονική Διάθεση Μαθήματος
Γλώσσα Διδασκαλίας
  • Ελληνικά (Διδασκαλία, Εξέταση)
  • Αγγλικά (Διδασκαλία)
Προαπαιτήσεις
Γενικές Προαπαιτήσεις
Θεωρητική Πληροφορική Γλώσσες - Μηχανές - Γραμματικές
Μαθησιακά Αποτελέσματα
Οι φοιτητές με την περάτωση του μαθήματος γνωρίζουν την έννοια της ω-αναγνωρισμιότητας με τα δύο είδη αυτομάτων Büchi και Muller καθώς και τις ιδιότητας της κλάσης αυτών των γλωσσών. Καταλαβαίνουν την διαφορά των αποδεικτικών μεθόδων με τα πεπερασμένα αυτόματα. Εισάγονται στην έννοια της MSO λογικής και της εκφραστικής ισοδυναμίας της με την αναγνωρισιμότηατα (και ω-αναγνωρισμιμότητα). Τέλος έχουν κατανοούν τη σημαντική συμβολή των προηγούμενων σε πραγματικές εφαρμογές.
Γενικές Ικανότητες
  • Εφαρμογή της γνώσης στην πράξη
  • Αναζήτηση, ανάλυση και σύνθεση δεδομένων και πληροφοριών, με τη χρήση και των απαραίτητων τεχνολογιών
  • Προσαρμογή σε νέες καταστάσεις
  • Λήψη αποφάσεων
  • Αυτόνομη εργασία
  • Ομαδική εργασία
  • Εργασία σε διεθνές περιβάλλον
  • Εργασία σε διεπιστημονικό περιβάλλον
  • Παραγωγή νέων ερευνητικών ιδεών
  • Σχεδιασμός και διαχείριση έργων
  • Άσκηση κριτικής και αυτοκριτικής
  • Προαγωγή της ελεύθερης, δημιουργικής και επαγωγικής σκέψης
Περιεχόμενο Μαθήματος
Αλφάβητα. Άπειρες λέξεις και ω-γλώσσες. Αυτόματα σε άπειρες λέξεις: Büchi και Muller συνθήκες αναγνωρισιμότητας. ω-Αναγνωρίσιμες γλώσσες. Ιδιότητες ω-αναγνωρίσιμων γλωσσών. Το πρόβλημα της συμπληρωματικής μιας ω-αναγνωρίσιμης γλώσσας. Μοναδιακή λογική δεύτερης τάξης. Ισοδυναμία προτάσεων μοναδιακής λογικής δεύτερης τάξης και αυτομάτων σε άπειρες λέξεις. Εφαρμογή αυτομάτων σε άπειρες λέξεις στον έλεγχο μοντέλων.
Λέξεις Κλειδιά
Αυτόματα σε απειρες λέξεις, ω-αναγνωρίμες γλώσσες, μοναδιακή λογική δευτερης τάξης
Τύποι Εκπαιδευτικού Υλικού
  • Σημειώσεις
Οργάνωση Μαθήματος
ΔραστηριότητεςΦόρτος ΕργασίαςECTSΑτομικάΟμαδικάErasmus
Διαλέξεις391,3
Μελέτη και ανάλυση βιβλίων και άρθρων1173,9
Σύνολο1565,2
Αξιολόγηση Φοιτητών
Μέθοδοι Αξιολόγησης Φοιτητών
  • Γραπτή Εργασία (Διαμορφωτική, Συμπερασματική)
  • Προφορική Εξέταση (Διαμορφωτική)
Βιβλιογραφία
Επιπρόσθετη βιβλιογραφία για μελέτη
- C. Baier, J.-P. Katoen, Principles in model checking, MIT Press, 2008. B. Khoussainov, A. Nerode, Automata Theory and its Applications, Birkhäuser Boston, 2001. - W. Thomas, Automata on infinite objects, in: Handbook of Theoretical Computer Science, vol. B (J. v. Leeuwen, ed.), Elsevier Science Publishers, Amsterdam 1990, pp. 135-191. - W. Thomas, Languages, automata and logic, in: Handbook of Formal Languages, vol. 3 (G. Rozenberg, A. Salomaa, eds.), Springer, 1997, pp. 389-485. - M-H. Tsai, S. Fogarty, M.Y. Vardi, Y-K. Tsay, State of Büchi complementation, Full version of CIAA 2010 paper, http://www.cs.rice.edu/~vardi/papers/ciaa10rj.pdf - Q. Yan, Lower bounds for complementation of omega-automata via the full automata technique, Logical Methods in Computer Science 4(2005), 1-20.
Τελευταία Επικαιροποίηση
25-09-2018