Ενότητα 1: Αυτόματα, Γλώσσες, Τυπικές Γραμματικές
- Διάλεξη 4/10: Εισαγωγή, πεπερασμένα αυτόματα, παραδείγματα. Διαφάνειες: 1-14.
- Διάλεξη 6/10: Πεπερασμένα αυτόματα, ντετερμινιστικά (DFA) και μη ντετερμινιστικά (NFA). Μετατροπή NFA σε DFA. Διαφάνειες: 15-34.
- Διάλεξη 11/10: NFAε, μετατροπή σε DFA. Ελαχιστοποίηση αυτομάτων (εισαγωγή). Διαφάνειες: 35-41.
- Διάλεξη 13/10: Ελαχιστοποίηση αυτομάτων. Διακρισιμότητα και ισοδυναμία καταστάσεων. Τυπικές γλώσσες και τυπικές γραμματικές. Διαφάνειες: 42-58.
- Διάλεξη 18/10: Κανονικές γραμματικές. Κανονικές παραστάσεις. Διαφάνειες: 59-71.
- Διάλεξη 20/10: Ισοδυναμία κανονικών παραστάσεων και πεπερασμένων αυτομάτων. Διαφάνειες: 72-78.
- Διάλεξη 25/10: Γινόμενο αυτομάτων, κλειστότητα κανονικών γλωσσών. Μη κανονικές γλώσσες. Pumping Lemma. Διαφάνειες: 79-86.
- Διάλεξη 27/10: Pumping Lemma (συνέχεια). Γραμματικές και γλώσσες χωρίς συμφραζόμενα. Διαφάνειες: 87-94.
- Διάλεξη 1/11: Συντακτικά δέντρα για γλώσσες χωρίς συμφραζόμενα: συντακτικά δέντρα, γραμματικές, αυτόματα στοίβας (PDA). Γλώσσες με συμφραζόμενα, LBA. Γενικές γραμματικές, μηχανές Turing. Διαφάνειες: 95-115.
Ενότητα 2: Λογική, Υπολογισιμότητα, Πολυπλοκότητα
- Διάλεξη 3/11: Εισαγωγή στη λογική. Προτασιακός λογισμός. Διαφάνειες: 1-10.
- Διάλεξη 8/11: Κατηγορηματικός λογισμός. Θεωρήματα Γκέντελ: πληρότητα και μη πληρότητα. Διαφάνειες: 11-20.
- Διάλεξη 10/11: Μοντέλα υπολογισμού: μηχανές Turing, RAM. Υπολογισιμότητα, διαγωνιοποίηση, Πρόβλημα Τερματισμού. Διαφάνειες: 21-40.
Ενότητα 3: Αλγόριθμοι Γράφων
- Διάλεξη 22/11: Αναπαράσταση γράφων, εισαγωγικές έννοιες. Το πρόβλημα των συντομότερων μονοπατιών. Ο αλγόριθμος του Dijkstra: παραδείγματα, πολυπλοκότητα. Διαφάνειες: 1-54.
- Διάλεξη 24/11: Απόδειξη ορθότητας αλγορίθμου Dijkstra. Γράφοι με αρνητικά βάρη. Ο αλγόριθμος Bellman-Ford. Διαφάνειες: 55-74.
- Διάλεξη 29/11: Ελάχιστα συνδετικά δέντρα. Αλγόριθμοι Prim και Kruskal. Απόδειξη ορθότητας. Αλγόριθμος Boruvka (απλή αναφορά). Διαφάνειες: 75-99.
- Διάλεξη 1/12: Πολυπλοκότητα προβλημάτων γράφων. Επισκόπηση αλγοριθμικών τεχνικών. Διαφάνειες: 100-105.
Ενότητα 4: Αλγοριθμικές τεχνικές, αριθμητικοί υπολογισμοί, αποδοτικότητα αλγορίθμων
- Διάλεξη 1/12: Εισαγωγή στους αλγόριθμους. Επανάληψη, αναδρομή, επαγωγή. Πύργοι του Ανόι. Υπολογιστικά προβλήματα. Διαφάνειες: 1-15.
- Διάλεξη 6/12: Αποδοτικότητα αλγορίθμων. Πολυπλοκότητα: ασυμπτωτικός συμβολισμός, Ο, Ω, Θ. Διαφάνειες: 16-27.
- Διάλεξη 8/12: Ασυμπτωτικός συμβολισμός (συν.). Πολυπλοκότητα βασικών αλγορίθμων. Ευκλείδειος αλγόριθμος εύρεση ΜΚΔ. Διαφάνειες: 28-38.
Ενότητα 5: Τεχνητή Νοημοσύνη
- Εισαγωγή στην Τεχνητή Νοημοσύνη, Ευφυείς δράστες, αναπαράσταση προβλημάτων σε χώρο καταστάσεων, αλγόριθμοι αναζήτησης λύσης, πολυπλοκότητα προβλημάτων αναζήτησης λύσης, αλγόριθμοι τυφλής αναζήτησης, ευρετικοί αλγόριθμοι επίλυσης προβλημάτων, εύρεση βέλτιστης λύσης.