ΕΠΛ 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