ΕΠΛ 211: Θεωρία Υπολογισμού
Class Notes


Η ιστοσελίδα αυτή θα ενημερώνεται τακτικά με τις διαφάνειες των διαλέξεων σε μορφή pdf.
 
 
Διάλεξη 1
ΕΠΛ211
 - Περιγραφή και στόχοι του μαθήματος
download (pdf)
Διάλεξη 2
Εισαγωγή
 - Μαθηματικό Υπόβαθρο και Τεχνικές Αποδείξεων
download (pdf)
Διαλέξεις 3-6
Κανονικές Γλώσσες (1)
 - Ντετερμινιστικά και μη ντετερμινιστικά αυτόματα, ισοδυναμία, κλειστότητα ως προς τις κανονικές πράξεις. Κανονικές εκφράσεις και ισοδυναμία κανονικών εκφράσεων με κανονικές γλώσσες.

download (pdf)

Διαλέξεις 7-8
Κανονικές Γλώσσες (2)
 - Κανονικές εκφράσεις και ισοδυναμία με κανονικές γλώσσες. Μη κανονικές γλώσσες και το Λήμμα της ’ντλησης

download (pdf)

Διαλέξεις 9-10
Ασυμφραστικές Γλώσσες (1)
 - Ασυμφραστικές Γραμματικές, Σχεδίαση Ασυμφραστικών Γραμματικών, Πολυτροπία, Κανονική Μορφή Chomsky

download (pdf)

Διαλέξεις 11-12
Ασυμφραστικές Γλώσσες (2)
 - Αυτόματα Στοίβας, Ισοδυναμία με τις Ασυμφραστικές Γραμματικές

download (pdf)

Διάλεξη 13
Ασυμφραστικές Γλώσσες (3)
 - Μη Ασυμφραστικές Γλώσσες, Το Λήμμα της ’ντλησης για Ασυμφραστικές Γλώσσες

download (pdf)

Διαλέξεις 14-16
To Δόγμα Church-Turing
 - Μηχανές Turing, Ορισμός, Παραδείγματα, Παραλλαγές Μηχανών Turing, Αλγόριθμοι και το Δόγμα Church-Turing

download (pdf)

Διαλέξεις 17-20
Διαγνωσιμότητα
 - Διαγνώσιμες Γλώσσες. Επιλύσιμα Προβλήματα σχετικά με Κανονικές Γλώσσες, Επιλύσιμα Προβλήματα σχετικά με Ασυμφραστικές Γλώσσες. Το Πρόβλημα του Τερματισμού

download (pdf)

Διαλέξεις 21-22
Αναγωγές
 - Ανεπίλυτα Προβλήματα από τη Θεωρία Γλωσσών, Απεικονιστικές Αναγωγές

download (pdf)

Διαλέξεις 23-26
Χρονική Πολυπλοκότητα
 - Μέτρηση Πολυπλοκότητας. Η κλάσεις Ρ και ΝΡ. ΝΡ-πληρότητα

download (pdf)


 
 
 
EPL211
Tutorials
Solutions
Course Schedule
Announcements
Class Contract
Assignments
Related Links

’ννα Φιλίππου, Εαρινό Εξάμηνο 2020