|
Class Notes |
| Η ιστοσελίδα αυτή θα ενημερώνεται τακτικά
με τις
διαφάνειες των διαλέξεων σε μορφή pdf. |
| Διάλεξη 1 |
ΕΠΛ211 - Περιγραφή και στόχοι του μαθήματος |
|
| Διάλεξη 2 |
Εισαγωγή - Μαθηματικό Υπόβαθρο και Τεχνικές Αποδείξεων |
download (pdf) |
| Διαλέξεις 3-6 |
Κανονικές Γλώσσες (1) - Ντετερμινιστικά και μη ντετερμινιστικά αυτόματα, ισοδυναμία, κλειστότητα ως προς τις κανονικές πράξεις. Κανονικές εκφράσεις και ισοδυναμία κανονικών εκφράσεων με κανονικές γλώσσες. |
|
| Διαλέξεις 7-8 |
Κανονικές Γλώσσες (2) - Κανονικές εκφράσεις και ισοδυναμία με κανονικές γλώσσες. Μη κανονικές γλώσσες και το Λήμμα της Άντλησης |
|
| Διαλέξεις 9-10 |
Ασυμφραστικές Γλώσσες (1) - Ασυμφραστικές Γραμματικές, Σχεδίαση Ασυμφραστικών Γραμματικών, Πολυτροπία, Κανονική Μορφή Chomsky |
|
| Διαλέξεις 11-12 |
Ασυμφραστικές Γλώσσες (2) - Αυτόματα Στοίβας, Ισοδυναμία με τις Ασυμφραστικές Γραμματικές |
|
| Διάλεξη 13 |
Ασυμφραστικές Γλώσσες (3) - Μη Ασυμφραστικές Γλώσσες, Το Λήμμα της Άντλησης για Ασυμφραστικές Γλώσσες |
|
| Διαλέξεις 14-16 |
To Δόγμα Church-Turing - Μηχανές Turing, Ορισμός, Παραδείγματα, Παραλλαγές Μηχανών Turing, Αλγόριθμοι και το Δόγμα Church-Turing |
|
| Διαλέξεις 17-20 |
Διαγνωσιμότητα - Διαγνώσιμες Γλώσσες. Επιλύσιμα Προβλήματα σχετικά με Κανονικές Γλώσσες, Επιλύσιμα Προβλήματα σχετικά με Ασυμφραστικές Γλώσσες. Το Πρόβλημα του Τερματισμού |
|
| Διαλέξεις 21-22 |
Αναγωγές - Ανεπίλυτα Προβλήματα από τη Θεωρία Γλωσσών, Απεικονιστικές Αναγωγές |
|
| Διαλέξεις 23-26 |
Χρονική Πολυπλοκότητα - Μέτρηση Πολυπλοκότητας. Η κλάσεις Ρ και ΝΡ. ΝΡ-πληρότητα |
|
|
|
|
|
|
|
|
|
|
Άννα Φιλίππου, Εαρινό Εξάμηνο
2019