Postgraduate Section 4 1021

• Ελληνικά
• English

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

Γενικά

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

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

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

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

Γενικές Ικανότητες

Αυτόνομη εργασία Βιβλιογραφική έρευνα Επιλογή και σχεδίαση της κατάλληλης μηχανής κάθε φορά

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

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

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

Τρόπος Διδασκαλίας	Πρόσωπο με πρόσωπο.
Τρόπος και Συχνότητα Επικοινωνίας με Φοιτητές	Η επικοινωνία με τους φοιτητές γίνεται: Μέσω email. Δια ζώσης στο γραφείο. Κατά τη διάρκεια των διαλέξεων. Η συχνότητα επικοινωνίας με τους φοιτητές καθορίζεται από τις ανάγκες των φοιτητών.
Διασφάλιση Τρόπου Επικοινωνίας Μεταξύ Φοιτητών	Συνέργεια στα πλαίσια της παράδοσης του μαθήματος.
Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών	Ναι.
Απαιτούμενος Τεχνολογικός Εξοπλισμός και Γνώσεις Τεχνολογίας	Δεν απαιτείται τεχνολογικός εξοπλισμός, καθώς παρέχεται. Δεν απαιτούνται εξειδικευμένες γνώσεις τεχνολογίας.
Πολιτική Μαθήματος για τη Λογοκλοπή και Εργαλεία Ελέγχου Λογοκλοπής	Η λογοκλοπή απαγορεύεται ρητά και τιμωρείται κλιμακούμενα, ανάλογα με την επανάληψη της χρήσης της. Ελέγχεται, δε, με σχετικά εργαλεία όπως το "Turnitin", που παρέχει η Βιβλιοθήκη του Πανεπιστημίου.
Πολιτική Μαθήματος για τη Χρήση Τεχνητής Νοημοσύνης	Επιτρέπεται η χρήση Τεχνητής Νοημοσύνης κατόπιν άδειας από τον διδάσκοντα/τη διδάσκουσα.
Οργάνωση Διδασκαλίας	Δραστηριότητα Φόρτος Εργασίας Εξαμήνου Διαλέξεις 39 Αυτοτελής Μελέτη 78 Ασκήσεις, Εργασίες 70.5 Σύνολο Μαθήματος 187.5
Αξιολόγηση Φοιτητών	Τελική εργασία (40%) Ασκήσεις - σχεδίαση αυτομάτων και γραμματικών - ερωτήσεις κρίσεως (30%) Παρουσιάσεις σχετικών θεμάτων (30%)

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

Δείτε την υπηρεσία Εύδοξος.

Theory of Computation

General

School	School of Science
Academic Unit	Department of Mathematics
Level of Studies	Graduate
Course Code	ΠΛ2
Semester	1
Course Title	Theory of Computation
Independent Teaching Activities	Lectures (Weekly Teaching Hours: 3, Credits: 7.5)
Course Type	Specialization
Prerequisite Courses	Undergraduate courses in Automata Theory and Formal Languages, Data Structures and Algorithms
Language of Instruction and Examinations	Greek
Mode of Course Delivery	Face-to-face (100%)
Is the Course Offered to Erasmus Students	Yes (in English)
Course Website (URL)	See eCourse, the Learning Management System maintained by the University of Ioannina.

Learning Outcomes

Learning outcomes

The goal of this course is the deeper understanding of Automata Theory and Language, Computability Theory and Complexity Theory as well as the introduction of students to critical thinking and research process. During the course a detailed examination of the following topics are done: Finite Automata (Deterministic FA, Nondeterministic FA, FA with Epsilon-Transitions) and their applications, Regular Expressions and Languages, Properties of Regular Languages Context-Free Grammars and languages, Pushdown Automata (Deterministic PDA, Acceptance by Final State, Acceptance by Empty Stack) , Properties of Context-Free Languages Turing Machines (Standard TM, Multitrack TM, Two-Way Tape TM, Multitape TM, Nondeterministic TM) Decidability and Computability Computational Complexity After completing the course the student can handle: theoretical documentation of problems solving exercises tracking applications which related to Finite Automata, Pushdown Automata, and Turing Machines as well as to Decidability and Computability and to Computational Complexity.

General Competences

Independent work Bibliographic search Effective selection and Design of the required machine and language.

Syllabus

Properties of the Computation Theory Mathematical Models Problems classification to solvable and unsolvable Solvable Problems Classification

Teaching and Learning Methods - Evaluation

Mode of Instruction	Face to face.
Mode and Frequency of Communication with Students	Communication with students takes place through: Email. In-person meetings during office hours. During lectures. The frequency of communication with students is determined by their needs.
Ensuring Communication Among Students	Collaboration and interaction are encouraged within the context of course delivery.
Use of Information and Communications Technology	Yes.
Required Technological Equipment and Technology Skills	No technological equipment is required from students, as all necessary equipment is provided. No specialized technology skills are required.
Course Policy on Plagiarism and Plagiarism Detection Tools	Plagiarism is strictly prohibited and is subject to progressively stricter penalties in the event of repeated offenses. It is monitored using plagiarism detection tools such as Turnitin, which is provided by the University Library.
Course Policy on the Use of Artificial Intelligence	The use of Artificial Intelligence is permitted only with the prior approval of the instructor.
Teaching Methods	Activity Semester Workload Lectures 39 Self study 78 Exercises 70.5 Course total 187.5
Student Performance Evaluation	Final essays (40%). Exercises - questions requiring critical thinking (30%). Presentations of related issues (30%).

Attached Bibliography

See the official Eudoxus site.