Wiki Τμήματος Μαθηματικών
Θεωρία Υπολογισμού (MAE745): Διαφορά μεταξύ των αναθεωρήσεων

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

Από Wiki Τμήματος Μαθηματικών
Χωρίς σύνοψη επεξεργασίας
 
(6 ενδιάμεσες αναθεωρήσεις από τον ίδιο χρήστη δεν εμφανίζεται)
Γραμμή 1: Γραμμή 1:
[[Περιγράμματα Προπτυχιακών Μαθημάτων]] - [https://math.uoi.gr Τμήμα Μαθηματικών]
* [[Theory of Computation (MAE745)|English version]]
{{Course-UnderGraduate-Top-GR}}
{{Menu-OnAllPages-GR}}


=== Γενικά ===
=== Γενικά ===
Γραμμή 26: Γραμμή 28:
| Διαλέξεις (Εβδομαδιαίες Ώρες Διδασκαλίας: 3, Πιστωτικές Μονάδες: 6)
| Διαλέξεις (Εβδομαδιαίες Ώρες Διδασκαλίας: 3, Πιστωτικές Μονάδες: 6)
|-
|-
! Τύπος Μαθήματος
! [[Τύποι Προπτυχιακών Μαθημάτων|Τύπος Μαθήματος]]
| Ειδικού Υποβάθρου
| Ειδίκευσης
|-
|-
! Προαπαιτούμενα Μαθήματα
! Προαπαιτούμενα Μαθήματα
Γραμμή 72: Γραμμή 74:
=== Περιεχόμενο Μαθήματος ===
=== Περιεχόμενο Μαθήματος ===


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


=== Διδακτικές και Μαθησιακές Μέθοδοι - Αξιολόγηση ===
=== Διδακτικές και Μαθησιακές Μέθοδοι - Αξιολόγηση ===
Γραμμή 87: Γραμμή 91:
|-
|-
! Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών
! Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών
| Ναι. Χρήση του Εργαστηρίου Επεξεργασίας Φυσικής Γλώσσας και Μαθηματικών προβλημάτων
|
Υποστήριξη Μαθησιακής διαδικασίας μέσω της ηλεκτρονικής πλατφόρμας e-course.
|-
|-
! Οργάνωση Διδασκαλίας
! Οργάνωση Διδασκαλίας

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

Γενικά

Σχολή Σχολή Θετικών Επιστημών
Τμήμα Τμήμα Μαθηματικών
Επίπεδο Σπουδών Προπτυχιακό
Κωδικός Μαθήματος 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.
Ανακτήθηκε από «https://wiki.math.uoi.gr/index.php?title=Θεωρία_Υπολογισμού_(MAE745)&oldid=4393»