Section outline

    • Ενότητα 1: Αυτόματα, Γλώσσες, Τυπικές Γραμματικές

      • Διάλεξη 2/10: Εισαγωγή, πεπερασμένα αυτόματα, παραδείγματα, ντετερμινιστικά αυτόματα (DFA). Διαφάνειες: 1-21.
      • Διάλεξη 4/10: Μη ντετερμινιστικά αυτόματα (NFA, NFAε). Ισοδυναμία NFA και DFA. Μέθοδος μετατροπής NFA σε DFA. Διαφάνειες: 22-38.
      • Διάλεξη 9/10: Μετατροπή NFAε σε DFA. Ελαχιστοποίηση DFA. Διακρίσιμες και ισοδύναμες καταστάσεις. Διαφάνειες: 39-56.
      • Διάλεξη 11/10: Θεωρία γλωσσών και γραμματικών. Τυπικες γραμματικές, Ιεραρχία γραμματικών Chomsky, Κανονικές Γραμματικές, Διαφάνειες: 57-71.
      • Διάλεξη 16/10: Κανονικές Παραστάσεις, Ισοδυναμία Κανοικών Παραστάσεων και Αυτομάτων, Γινόμενο Αυτομάτων Διαφάνειες: 72-84.
      • Διάλεξη 18/10: Pumping Lemma, Διαφάνειες: 85-93.
      • Διάλεξη 23/10: Γραμματικές χωρίς συμφραζόμενα, Συντακτικά δένδρα, Διαφάνειες: 94-103.
      • Διάλεξη 25/10: Επίλυση αποριών.
      • Διάλεξη 30/10: Αυτόματα στοίβας, Γραμματικές με συμφραζόμενα, Γενικές γραμματικές, Ιεαρχία, Διαφάνειες: 104-119.

    • Ενότητα 2: Ασυμπτωτικός συμβολισμός

      • Διάλεξη 1/11: Ασυμπτωτικός συμβολισμός.

    • Ενότητα 3: Γράφοι, Συντομότερα μονοπάτια, Ελάχιστα συνδετικά δένδρα

      • Διάλεξη 6/11: Γράφοι, αλγόριθμος Dijkstra.
      • Διάλεξη 8/11: Aλγόριθμος Bellman-Ford. Ελάχιστα συνδετικά δένδρα: αλγόριθμοι Prim, Kruskal, Boruvka.

    • Ενότητα 4η: Αριθμητικοί υπολογισμοί - divide and conquer

      • Διάλεξη 13/11: Αλγόριθμοι εύρεσης ΜΚΔ. Ευκλείδειος αλγόριθμος: ανάλυση πολυπλοκότητας. Αλγόριθμοι ύψωσης σε δύναμη. Διαφάνειες: 1-10.