Μαθηματική Θεωρία των Υπολογισμών (ΠΛ2)

English version
Περιγράμματα Μεταπτυχιακών Μαθημάτων
Τροποποίηση Περιγράμματος (η δυνατότητα αυτή απευθύνεται αποκλειστικά στα μέλη ΔΕΠ του Τμήματος)

Γενικά

Σχολή	Σχολή Θετικών Επιστημών
Τμήμα	Τμήμα Μαθηματικών
Επίπεδο Σπουδών	Μεταπτυχιακό
Κωδικός Μαθήματος	ΠΛ2
Εξάμηνο	1
Τίτλος Μαθήματος	ΜΑΘΗΜΑΤΙΚΗ ΘΕΩΡΙΑ ΤΩΝ ΥΠΟΛΟΓΙΣΜΩΝ
Αυτοτελείς Διδακτικές Δραστηριότητες	Διαλέξεις (Εβδομαδιαίες Ώρες Διδασκαλίας: 3, Πιστωτικές Μονάδες: 7.5)
Τύπος Μαθήματος	Μάθημα Ειδίκευσης
Προαπαιτούμενα Μαθήματα	Προπτυχιακά Μαθήματα στη Θεωρία Αυτομάτων και Τυπικών Γλωσσών, Δομές Δεδομένων και Εισαγωγή στους Αλγορίθμους.
Γλώσσα Διδασκαλίας και Εξετάσεων	Ελληνική
Το Μάθημα Προσφέρεται σε Φοιτητές Erasmus	Ναι (στην Αγγλική γλώσσα)
Ηλεκτρονική Σελίδα Μαθήματος (URL)	Δείτε το eCourse, την Πλατφόρμα Ασύγχρονης Εκπαίδευσης του Πανεπιστημίου Ιωαννίνων.

Μαθησιακά Αποτελέσματα

Μαθησιακά Αποτελέσματα	Σκοπός είναι η βαθύτερη κατανόηση της Θεωρίας Υπολογισμού που είναι η Θεωρία Αυτομάτων και Τυπικών Γλωσσών, η Υπολογισιμότητα και η Πολυπλοκότητα τους καθώς και η εισαγωγή των φοιτητών στην κριτική σκέψη και την ερευνητική διαδικασία. Στο μάθημα γίνεται λεπτομερής εξέταση των Πεπερασμένων Αυτομάτων (Αιτιοκρατικών, μη Αιτιοπρατικών, με ε-μεταβάσεις) και των εφαρμογών τους, των Κανονικών Εκφράσεων και Γλωσσών, των Ιδιοτήτων των Κανονικών Γλωσσών. Των Ανεξάρτητων Συμφραζομένων Γραμματικών και Γλωσσών, των Πεπερασμένων Αυτομάτων με Στοιβάδα (Αιτιοκρατικών, Παραλλαγές όπως αποδοχή με τελική κατάσταση ή με κενή στοιβάδα), των ιδιοτήτων των Ανεξάρτητων Συμφραζομένων Γλωσσών. Των Μηχανών Turing (standad ΜΤ, με πολλαπλές λωρίδες ΜΤ, με απεριόριστη ταινία με αμφότερες κατευθύνσεις, με πολλαπλές ταινίες ΜΤ, μη Αιτιοκρατικές ΜΤ, Καθολική ΜΤ). Των εννοιών της Επιλυσιμότητας και Υπολογισιμότητας καθώς και της Πολυπολοκότητας των Υπολογισμών. Μετά την ολοκλήρωση του μαθήματος ο φοιτητής /τρια μπορεί να χειριστεί: σε επίπεδο θεωρητικής τεκμηρίωσης προβλημάτων επίλυση ασκήσεων αναγνώριση εφαρμογών Πεπερασμένα Αυτόματα, τα Πεπερασμένα Αυτόματα με Στοιβάδα και τις Μηχανές Turing, την Επιλυσιμότητα και Υπολογισιμότητα καθώς και την Πολυπλοκότητα των Υπολογισμών.
Γενικές Ικανότητες	Αυτόνομη εργασία Βιβλιογραφική έρευνα Επιλογή και σχεδίαση της κατάλληλης μηχανής κάθε φορά

Περιεχόμενο Μαθήματος

Ιδιότητες των μαθηματικών μοντέλων των υπολογισμών
Κατάταξη προβλημάτων σε επιλύσιμα και μη
Κατάταξη επιλύσιμων προβλημάτων σε εύκολα

Διδακτικές και Μαθησιακές Μέθοδοι - Αξιολόγηση

Τρόπος Παράδοσης

Πρόσωπο με πρόσωπο

Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών

Ναι

Οργάνωση Διδασκαλίας

Δραστηριότητα	Φόρτος Εργασίας Εξαμήνου
Διαλέξεις	39
Αυτοτελής Μελέτη	78
Ασκήσεις, Εργασίες	70.5
Σύνολο Μαθήματος	187.5

Αξιολόγηση Φοιτητών

Τελική εργασία (40%)
Ασκήσεις - σχεδίαση αυτομάτων και γραμματικών - ερωτήσεις κρίσεως (30%)
Παρουσιάσεις σχετικών θεμάτων (30%)

Συνιστώμενη Βιβλιογραφία

Sudkamp, Thomas A. Languages and machines : an introduction to the theory of computer science / Thomas A. Sudkamp. - 2nd ed. ISBN 0-201-82136-2
Hopcroft, John E., Rajeev Motwani, Jeffrey . Ullman Introduction to automata theory, languages and computation -2nd ed. ISBN 0321210298
Michael Sipser. Introduction to the Theory of Computation (3rd ed.). Cengage Learning. ISBN 978-1-133-18779-0.