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-14.
      • Διαλέξεις 22/11 (διπλό μάθημα): Ύψωση σε δύναμη με επαναλαμβανόμενο τετραγωνισμό, και modulo p. Έλεγχος πρώτων αριθμών κατά Fermat.  Αλγόριθμοι υπολογισμού n-οστού αριθμού Fibonacci. Divide-and-conquer. Πολλαπλασιασμός ακεραίων με τη μέθοδο Gauss-Karatsuba. Διαφάνειες: 15-40.

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

      • Διάλεξη 27/11: Εισαγωγή στην Τεχνητή Νοημοσύνη, Επίλυση προβλημάτων, Δύσκολα προβλήματα, Πρακτικά προβλήματα, Χώροι προβλημάτων, Πρόβλημα SAT, Πρόβλημα Πλανόδιου πωλητή, Εισαγωγή στην ευρετική επίλυση προβλημάτων  
      • Διάλεξη 29/11: Δράστες και επίλυση προβλημάτων, Ορθολογικοί δράστες, Δράστες βασισμένοι σε πίνακα, Απλοί αναπλαστικοί δράστες, Δράστες με μοντέλο, Δράστες επιδίωξης στόχου, Δράστες ωφέλειας, Δράστες με μάθηση, Τυπική διατύπωση προβλήματος, Χώρος αναζήτησης λύσης, Δέντρα αναζήτησης προβλημάτων, Αλγόριθμοι επίλυσης προβλημάτων, Αλγόριθμοι αναζήτησης λύσης
      • Διάλεξη 4/12: Γενική δομή αλγορίθμων αναζήτησης, Αλγόριθμοι τυφλής αναζήτησης, Αλγόριθμος αναζήτησης κατά πλάτος, Αλγόριθμος διπλής κατεύθυνσης, Αλγόριθμος αναζήτησης κατά βάθος, Αλγόριθμος επαναληπτικής εκβάθυνσης, Πολυπλοκότητα αλγορίθμων τυφλής αναζήτησης
      • Διάλεξη 11/12:  Αλγόριθμοι εμπεριστατωμένης αναζήτησης, Ευρετικοί μηχανισμοί, Αλγόριθμος αναρρίχησης λόφου (hill climbing), Αλγόριθμος πρώτα-στο-καλύτερο (best-first), Αλγόριθμοι εμπεριστατωμένης αναζήτησης εύρεσης βέλτιστης λύσης, Βασικές στρατηγικές, Αλγόριθμος branch and bound, Δυναμικός προγραμματισμός, Αλγόριθμος Α*
      • Διάλεξη 13/12: Ανάλυση αλγορίθμου Α*, Αποδεκτές ευρετικές συναρτήσεις, Πολυπλοκότητα αλγορίθμου Α* για αποδεκτές ευρετικές, Συνεπείς ευρετικές, Ιδιότητες ευρετικών, Ακρίβεια ευρετικών, Αποτελεσματικός παράγοντας διακλάδωσης
      • Διάλεξη 18/12: Αλγόριθμοι αναζήτησης για παίγνια, Αλγόριθμος min-max, Βελτιστοποίηση αλγόριθμου min-max, alpha κλάδεμα, beta κλάδεμα, Αλγόριθμος alpha-beta
      • Διάλεξη 20/12: Ασκήσεις στους αλγόριθμους αναζήτησης λύσης
      • Διάλεξη 8/1: Επανάληψη, Ασκήσεις στους αλγόριθμους παιγνίων

    • Ενότητα 6η: Ειδικά θέματα αλγορίθμων και πολυπλοκότητας

      Προσοχή: η ενότητα αυτή είναι εκτός εξεταστέας ύλης.