Θεωρία Υπολογισμού (MAE745): Διαφορά μεταξύ των αναθεωρήσεων

Τελευταία αναθεώρηση της 10:08, 15 Ιουνίου 2023

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

Γενικά

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

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

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

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

Εισαγωγικά και Χρήσιμες Έννοιες
Κανονικές Γλώσσες, Κανονικές Εκφράσεις
Πεπερασμένα Αυτόματα, Γλώσσες που δεν είναι Κανονικές
Γλώσσες Ανεξάρτητες Συμφραζομένων - Αυτόματα Στοίβας
Μηχανές Turing, Αναγνωρίσιμες και διαγνώσιμες γλώσσες, Απαριθμήσιμες γλώσσες, το δόγμα Church-Turing
Διαγνωσιμότητα, το Πρόβλημα του Τερματισμού
Αναγωγές, μη διαγνώσιμες γλώσσες
Οι κλάσεις πολυπλοκότητας P και NP

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

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

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

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

Υποστήριξη Μαθησιακής διαδικασίας μέσω της ηλεκτρονικής πλατφόρμας e-course.

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

Δραστηριότητα	Φόρτος Εργασίας Εξαμήνου
Διαλέξεις (13Χ3)	39
Αυτοτελής Μελέτη	78
Επίλυση Ασκήσεων - εργασίες	33
Σύνολο Μαθήματος	150

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

Τελική γραπτή εξέταση

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

Δείτε την υπηρεσία Εύδοξος ή το τοπικό αποθετήριο του Τμήματος Μαθηματικών για τα παρεχόμενα συγγράμματα ανά ακαδημαϊκό έτος. Συγγράμματα και άλλες πηγές εκτός της υπηρεσίας Εύδοξος:

[11776]: Στοιχεία θεωρίας υπολογισμού, Lewis Harry R.,Παπαδημητρίου Χρίστος Χ.
[257]: ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ, SIPSER MICHAEL.

@@ Γραμμή 1: / Γραμμή 1: @@
-[[Περιγράμματα Προπτυχιακών Μαθημάτων]] - [https://math.uoi.gr Τμήμα Μαθηματικών]
+* [[Theory of Computation (MAE745)|English version]]
+{{Course-UnderGraduate-Top-GR}}
+{{Menu-OnAllPages-GR}}
 === Γενικά ===
@@ Γραμμή 26: / Γραμμή 28: @@
 | Διαλέξεις (Εβδομαδιαίες Ώρες Διδασκαλίας: 3, Πιστωτικές Μονάδες: 6)
 |-
-! Τύπος Μαθήματος
+! [[Τύποι Προπτυχιακών Μαθημάτων|Τύπος Μαθήματος]]
-| Ειδικού Υποβάθρου
+| Ειδίκευσης
 |-
 ! Προαπαιτούμενα Μαθήματα
@@ Γραμμή 47: / Γραμμή 49: @@
 |-
 ! Μαθησιακά Αποτελέσματα
-| Σκοπός είναι η βαθύτερη κατανόηση της Θεωρίας Αυτομάτων και Τυπικών Γλωσσών, αναλυτικότερα:
+|
-* Εισαγωγικές Έννοιες: Αυτόματα, Υπολογισιμότητα, Πολυπλοκότητα, Έννοιες, Ορισμοί, Θεωρήματα, Αποδείξεις και Είδη Αποδείξεων
+Σκοπός είναι η κατανόηση με τις βασικές έννοιες που σχετίζονται με τη Θεωρία Υπολογισμού. Αναλυτικότερα περιλαμβάνει τις ακόλουθες έννοιες:
-* Αφηρημένες Μηχανές και Γλώσσες: Εισαγωγή, η Στοιχειώδης Μηχανή (ΣΜ), Μηχανές Πεπερασμένων Καταστάσεων (ΜΠΚ). Πεπερασμένο Αυτόματο (ΠΑ), Αιτιοκρατικό Πεπερασμένο Αυτόματο (ΑΠΑ), Μη Αιτιοκρατικό Πεπερασμένο Αυτόματο (ΜΑΠΑ), Δένδρα Αποδοχής (ΔΑ), Πεπερασμένα Αυτόματα με ε-Μεταβάσεις (ΜΑΠΑΕΜ), Ισοδυναμία ΜΑΠΑ και ΜΑΠΑΕΜ, Ελαχιστοποίηση ενός ΑΠΑ, Θεώρημα της Επαναληπτικότητας
+* Πεπερασμένα αυτόματα, κανονικές εκφράσεις, κανονικές γλώσσες, ιδιότητες κλειστότητας, λήμμα άντλησης, αλγόριθμοι.
-* Πεπερασμένα Αυτόματα και Γραμματικές, Γραμματικές της Ιεραρχίας Chomsky, Κανονικά Σύνολα (ΚΣ), Κανονικά Σύνολα και Πεπερασμένα Αυτόματα, Εύρεση της Κανονικής Έκφρασης ενός ΠΑ, Ικανότητες και Ανεπάρκειες των ΠΑ
+* Αιτιοκρατία, μη αιτιοκρατία.
-* Πεπερασμένα Αυτόματα με Στοιβάδα (ΠΑΣ), Μη Αιτιοκρατικά Πεπερασμένα Αυτόματα με Στοιβάδα (ΜΑΠΑΣ), Αιτιοκρατικά Πεπερασμένα Αυτόματα με Στοιβάδα (ΑΠΑΣ), Αποδοχή με Κενή Στοιβάδα, Ισοδυναμία ΠΑΣ και Γλωσσών Ανεξάρτητων Συμφραζομένων
+* Aυτόματα στοίβας, γραμματικές χωρίς συμφραζόμενα, γλώσσες χωρίς συμφραζόμενα, ιδιότητες κλειστότητας, λήμμα άντλησης, αλγόριθμοι.
-* Μηχανές Turing (ΜΤ), Εισαγωγή, Μαθηματική Περιγραφή, Χρήσιμα Τεχνάσματα για την Κατασκευή της ΜΤ, Τροποποιήσεις της ΜΤ, η ΜΤ ως Διαδικασία
+* Κανονική μορφή Chomsky.
-* Μη Επιλυσιμότητα, η Θέση των Church-Turing, η Καθολική ΜΤ, το Πρόβλημα του Τερματισμού.Υπολογιστική Πολυπλοκότητα και NP-πληρότητα.
+* Mηχανές Turing, ισοδυναμία διαφορετικών μοντέλων.
-Μετά την ολοκλήρωση του μαθήματος ο φοιτητής / τρια μπορεί να χειριστεί:
+* Αναγνωρίσιμες, διαγνώσιμες, απαριθμήσιμες γλώσσες.
-* σε επίπεδο θεωρητικής τεκμηρίωσης προβλημάτων
+* Tο δόγμα των Church-Turing.
-* επίλυση ασκήσεων
+* Eπιλύσιμα και μη επιλύσιμα προβλήματα, το πρόβλημα αποδοχής για μηχανές Turing (halting problem), το πρόβλημα αντιστοιχίας του Post.
-* αναγνώριση εφαρμογών
+* Οι κλάσεις πολυπλοκότητας P και NP.
-Πεπερασμένα Αυτόματα, τα Πεπερασμένα Αυτόματα με Στοιβάδα και τις Μηχανές Turing, τη Μη Επιλυσιμότητα καθώς και την Πολυπλοκότητα των Υπολογισμών και προβλήματα NP-πληρότητας.
+Στο μάθημα περιλαμβάνονται ατομικές και ομαδικές ασκήσεις. Στόχος του μαθήματος είναι οι φοιτητές να είναι σε θέση:
+* να κατανοήσουν βασικούς τύπους αυτομάτων
+* να χειρίζονται κανονικές γλώσσες και μοντέλα υπολογισμού
+* να κατανοήσουν επιλύσιμα και μη επιλύσιμα αλγοριθμικά προβλήματα
 |-
 ! Γενικές Ικανότητες
 |
-* Προσαρμογή σε νέες καταστάσεις
+* Αναζήτηση, ανάλυση και σύνθεση δεδομένων και πληροφοριών, με τη χρήση και των απαραίτητων τεχνολογιών
-* Λήψη αποφάσεων
+* Αυτόνομη εργασία
-* Υλοποίηση - Εμπέδωση
+* Ομαδική εργασία
 |}
 === Περιεχόμενο Μαθήματος ===
-Εξοικείωση με:
+* Εισαγωγικά και Χρήσιμες Έννοιες
-* Τις Αφηρημένες Μηχανές και Γλώσσες: Εισαγωγή, η Στοιχειώδης Μηχανή (ΣΜ), Μηχανές Πεπερασμένων Καταστάσεων (ΜΠΚ). Πεπερασμένο Αυτόματο (ΠΑ), Αιτιοκρατικό Πεπερασμένο Αυτόματο (ΑΠΑ), Μη Αιτιοκρατικό Πεπερασμένο Αυτόματο (ΜΑΠΑ), Δένδρα Αποδοχής (ΔΑ), Πεπερασμένα Αυτόματα με ε-Μεταβάσεις (ΜΑΠΑΕΜ), Ισοδυναμία ΜΑΠΑ και ΜΑΠΑΕΜ, Ελαχιστοποίηση ενός ΑΠΑ, Θεώρημα της Επαναληπτικότητας
+* Κανονικές Γλώσσες, Κανονικές Εκφράσεις
-* Τα Πεπερασμένα Αυτόματα και Γραμματικές, Γραμματικές της Ιεραρχίας Chomsky, Κανονικά Σύνολα (ΚΣ), Κανονικά Σύνολα και Πεπερασμένα Αυτόματα, Εύρεση της Κανονικής Έκφρασης ενός ΠΑ, Ικανότητες και Ανεπάρκειες των ΠΑ
+* Πεπερασμένα Αυτόματα, Γλώσσες που δεν είναι Κανονικές
-* Τα Πεπερασμένα Αυτόματα με Στοιβάδα (ΠΑΣ), Μη Αιτιοκρατικά Πεπερασμένα Αυτόματα με Στοιβάδα (ΜΑΠΑΣ), Αιτιοκρατικά Πεπερασμένα Αυτόματα με Στοιβάδα (ΑΠΑΣ), Αποδοχή με Κενή Στοιβάδα, Ισοδυναμία ΠΑΣ και Γλωσσών Ανεξάρτητων Συμφραζομένων
+* Γλώσσες Ανεξάρτητες Συμφραζομένων - Αυτόματα Στοίβας
-* Τις Μηχανές Turing (ΜΤ), Εισαγωγή, Μαθηματική Περιγραφή, Χρήσιμα Τεχνάσματα για την Κατασκευή της ΜΤ, Τροποποιήσεις της ΜΤ, η ΜΤ ως Διαδικασία
+* Μηχανές Turing, Αναγνωρίσιμες και διαγνώσιμες γλώσσες, Απαριθμήσιμες γλώσσες, το δόγμα Church-Turing
-* Τη μη Επιλυσιμότητα, η Θέση των Church-Turing, η Καθολική ΜΤ, το Πρόβλημα του Τερματισμού.Υπολογιστική Πολυπλοκότητα, NP-πληρότητα.
+* Διαγνωσιμότητα, το Πρόβλημα του Τερματισμού
+* Αναγωγές, μη διαγνώσιμες γλώσσες
+* Οι κλάσεις πολυπλοκότητας P και NP
 === Διδακτικές και Μαθησιακές Μέθοδοι - Αξιολόγηση ===
@@ Γραμμή 84: / Γραμμή 91: @@
 |-
 ! Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών
-| Ναι. Χρήση του Εργαστηρίου Επεξεργασίας Φυσικής Γλώσσας και Μαθηματικών προβλημάτων
+|
+Υποστήριξη Μαθησιακής διαδικασίας μέσω της ηλεκτρονικής πλατφόρμας e-course.
 |-
 ! Οργάνωση Διδασκαλίας