Θεωρία Υπολογισμού


Διδάσκων/ουσα: Ανδρόνικος Θεόδωρος
Κωδικός Μαθήματος: HY-025
Τύπος Μαθήματος: Μάθημα Επιλογής
Επίπεδο Μαθήματος: Προπτυχιακό
Γλώσσα Μαθήματος: Ελληνικά
Εξάμηνο: Δ΄
ECTS: 4
Διδακτικές Μονάδες: 4
Ώρες Διάλεξης: 4
Σύνολο Ωρών: 4
Σελίδα E Class: https://opencourses.ionio.gr/courses/DDI188/


Αντικειμενικοί Στόχοι - Επιδιωκόμενα Μαθησιακά Αποτελέσματα:

Το μάθημα επιδιώκει την εμπέδωση από την πλευρά των φοιτητριών και φοιτητών της έννοιας του υπολογισμού, καθώς και των σημαντικότερων μοντέλων υπολογισμού.

          Με την επιτυχή ολοκλήρωση των σπουδών στο μάθημα οι φοιτήτριες και φοιτητές θα είναι σε θέση:

  • Να κατανοήσουν την έννοια του υπολογισμού από τη σκοπιά της Θεωρητικής Πληροφορικής.
  • Να εξοικειωθούν με τα απλούστερα υπολογιστικά μοντέλα, όπως είναι τα πεπερασμένα αιτιοκρατικά και μη αιτιοκρατικά αυτόματα, καθώς και οι αντίστοιχες κανονικές γλώσσες.
  • Να εξοικειωθούν με τις γραμματικές χωρίς συμφραζόμενα, τα αυτόματα στοίβας και τις αντίστοιχες γλώσσες χωρίς συμφραζόμενα.
  • Να εξοικειωθούν με τις μηχανές Turing και τις γνωστότερες κλάσεις πολυπλοκότητας, P, ΝΡ, PSPACE, καθώς και με την έννοια της NP-πληρότητας.

Περιεχόμενο (Syllabus):

Το μάθημα απευθύνεται σε φοιτήτριες και φοιτητές του δεύτερου έτους σπουδών. Καλύπτει τα εξής θέματα:

  • Αλφάβητα και γλώσσες.
  • Πεπερασμένα αυτόματα. Ιδιότητες των πεπερασμένων αυτομάτων και των γλωσσών που δέχονται. Κανονικές εκφράσεις και κανονικές γλώσσες. Ισοδυναμία πεπερασμένων αυτομάτων και κανονικών εκφράσεων. Λήμμα άντλησης για κανονικές γλώσσες.
  • Γραμματικές και η ιεραρχία του Chomsky. Γραμματικές και γλώσσες χωρίς συμφραζόμενα.
  • Αυτόματα στοίβας και λήμμα άντλησης για γλώσσες χωρίς συμφραζόμενα. Ισοδυναμία γραμματικών χωρίς συμφραζόμενα και αυτομάτων στοίβας.
  • Η έννοια της υπολογισιμότητας. Mηχανές Turing. Aποφασίσιμες και απαριθμήσιμες γλώσσες. Η θέση των Church-Turing.
  • Eπιλύσιμα και μη επιλύσιμα προβλήματα. Το πρόβλημα του τερματισμού (halting problem).
  • Εισαγωγή στην υπολογιστική πολυπλοκότητα. Χρονική πολυπλοκότητα, η κλάση Ρ, η θέση των Cook-Karp.
  • Αναγωγή και πληρότητα. Μη-ντετερμινισμός και NP-πληρότητα, σχέση Ρ και ΝΡ, αλγοριθμικές συνέπειες NP-πληρότητας.
  • Πολυπλοκότητα χώρου, η κλάση PSPACE, το θεώρημα του Savitch. PSPACE-πλήρη προβλήματα.

Συνιστώμενη βιβλιογραφία προς μελέτη:
  1. “Εισαγωγή στη Θεωρία Υπολογισμού”, Sipser Michael, Εκδόσεις ΙΤΕ-Πανεπιστημιακές Εκδόσεις Κρήτης, ISBN 978-960-524-558-0, 2019
  2. “Στοιχεία θεωρίας υπολογισμού”, Lewis Harry R., Παπαδημητρίου Χρίστος Χ., Εκδόσεις Κριτική ΑΕ, ISBN 978-960-218-397-7, 2005
Ενημέρωση: 15-01-2020

Επιστροφή
<< <
Ιανουάριος 2022
> >>
Δε Τρ Τε Πε Πα Σα Κυ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Σήμερα, Τρίτη 18-01-2022
Δεν βρέθηκαν εγγραφές για αυτήν την ημέρα
Προσεχώς