Section outline

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

      • Διάλεξη 3/10/2025: Εισαγωγή, πεπερασμένα αυτόματα, παραδείγματα, ντετερμινιστικά αυτόματα (DFA). Διαφάνειες: 1-21.
      • Διάλεξη 8/10/2025: Μη ντετερμινιστικά αυτόματα (NFA, NFAε). Ισοδυναμία NFA και DFA. Μέθοδος μετατροπής NFA σε DFA. Διαφάνειες: 22-35.
      • Διάλεξη 10/10: Μέθοδος μετατροπής NFA σε DFA. Ελαχιστοποίηση DFA. Διακρίσιμες και ισοδύναμες καταστάσεις. Παράδειγμα αλγορίθμου. Διαφάνειες: 36-56.
      • Διάλεξη 15/10: Ελαχιστοποίηση DFA. Θεωρία γλωσσών και γραμματικών. Τυπικες γραμματικές, Ιεραρχία γραμματικών Chomsky. Διαφάνειες: 57-68.
      • Διάλεξη 17/10: Κανονικές Γραμματικές, Κανονικές Παραστάσεις, Ισοδυναμία Κανοικών Παραστάσεων και Αυτομάτων (1ο μέρος). Διαφάνειες: 69-76.
      • Διάλεξη 22/10: Ισοδυναμία Κανοικών Παραστάσεων και Αυτομάτων, Ιδιότητες κλειστότητας, Γινόμενο Αυτομάτων Διαφάνειες, Λήμμα άντλησης. Διαφάνειες: 77-90.
      • Διάλεξη 24/10: Λήμμα άντλησης, Γραμματικές χωρίς συμφραζόμενα, Συντακτικά δένδρα, Αυτόματα στοίβας. Διαφάνειες: 91-109.
      • Διάλεξη 29/10: Αυτόματα στοίβας, γραμματικές με συμφραζόμενα, γενικές γραμματικές, μηχανές Turing. Διαφάνειες: 109-119.

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

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

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

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

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

      • Διάλεξη 14/11: P vs NP, αναγωγές (από προηγούμενη ενότητα). Εισαγωγή στους αριθμητικούς αλγορίθμους (εύρεση ΜΚΔ, Ευκλείδειος αλγόριθμος). 
      • Διάλεξη 19/11: Ανάλυση πολυπλοκότητας Ευκλειδείου αλγορίθμου, ύψωση σε δύναμη με επαναλαμβανόμενο τετραγωνισμό.
      • Διάλεξη 21/11: Ύψωση σε δύναμη με επαναλαμβανόμενο τετραγωνισμό modulo p.  Αλγόριθμοι υπολογισμού n-οστού αριθμού Fibonacci. Divide-and-conquer: σχετικοί αναδρομικοί ορισμοί πολυπλοκότητας και αναδρομικά δέντρα. Πολλαπλασιασμός ακεραίων με τον αλγόριθμο του Karatsuba.

    • Ενότητα 5η: Δυναμικός προγραμματισμός 

      • Διάλεξη 26/11: master theorem (από προηγούμενη ενότητα), συντομότερες διαδρομές σε DAG, μέγιστη κοινή υπακολουθία (διαφάνειες 1-36).
      • Διάλεξη 28/11: μέγιστη κοινή υπακολουθία, διορθωτική απόσταση (διαφάνειες 37-86).

    • Ενότητα 5η: Τεχνητή Νοημοσύνη

      • Διάλεξη 03/12: Εισαγωγή στην Τεχνητή Νοημοσύνη, Επίλυση προβλημάτων, Δύσκολα προβλήματα, Πρακτικά προβλήματα, Χώροι προβλημάτων, Πρόβλημα SAT, Πρόβλημα Πλανόδιου πωλητή, Εισαγωγή στην ευρετική επίλυση προβλημάτων
      • Διάλεξη 05/12: Δράστες και επίλυση προβλημάτων, Ορθολογικοί δράστες, Δράστες βασισμένοι σε πίνακα, Απλοί αναπλαστικοί δράστες, Δράστες με μοντέλο, Δράστες επιδίωξης στόχου, Δράστες ωφέλειας, Δράστες με μάθηση, Τυπική διατύπωση προβλήματος, Χώρος αναζήτησης λύσης, Δέντρα αναζήτησης προβλημάτων, Αλγόριθμοι επίλυσης προβλημάτων, Αλγόριθμοι αναζήτησης λύσης.
      • Διάλεξη 10/12: Γενική δομή αλγορίθμων αναζήτησης, Αλγόριθμοι τυφλής αναζήτησης, Αλγόριθμος αναζήτησης κατά πλάτος, Αλγόριθμος διπλής κατεύθυνσης, Αλγόριθμος αναζήτησης κατά βάθος, Αλγόριθμος επαναληπτικής εκβάθυνσης, Πολυπλοκότητα αλγορίθμων τυφλής αναζήτησης
      • Διάλεξη 12/12:  Αλγόριθμοι εμπεριστατωμένης αναζήτησης, Ευρετικοί μηχανισμοί, Αλγόριθμος αναρρίχησης λόφου (hill climbing), Αλγόριθμος πρώτα-στο-καλύτερο (best-first), Αλγόριθμοι εμπεριστατωμένης αναζήτησης εύρεσης βέλτιστης λύσης, Βασικές στρατηγικές, Αλγόριθμος branch and bound, Δυναμικός προγραμματισμός, Αλγόριθμος Α*
      • Διάλεξη 17/12: Αναβολή
      • Διάλεξη 19/12: Ανάλυση αλγορίθμου Α*, Αποδεκτές ευρετικές συναρτήσεις, Πολυπλοκότητα αλγορίθμου Α* για αποδεκτές ευρετικές, Συνεπείς ευρετικές, Ιδιότητες ευρετικών, Ακρίβεια ευρετικών, Αποτελεσματικός παράγοντας διακλάδωσης. Δείτε εδώ παραδειγματα των αλγορίθμων για έυρεση διαδρομών σε πλέγμα. 
      • Διάλεξη 07/01: Ασκήσεις στους αλγορίθμους αναζήτησης λύσης.
      • Διάλεξη 09/01: Αλγόριθμοι αναζήτησης για παίγνια, Αλγόριθμος min-max, Βελτιστοποίηση αλγόριθμου min-max, alpha κλάδεμα, beta κλάδεμα, Αλγόριθμος alpha-beta. Ασκήσεις στους αλγορίθμους αναζήτησης για παίγνια.  Διαφάνειες εδώ.