Section outline

  • Ανακοινώσεις

    Σύμπτυξη όλων Ανάπτυξη όλων

  • Γενικά στοιχεία

    Διδάσκοντες

    • Θάνος Βουλόδημος
    • Στάθης Ζάχος 
    • Νίκος Λεονάρδος
    • Άρης Παγουρτζής (σε εκπαιδευτική άδεια)
    • Νίκος Πρωτοπαπάς
    • Δώρα Σούλιου
    • Γιώργος Στάμου
    • Παρασκευή Τζούβελη

    Διαλέξεις

    Για τα 2 πρώτα τμήματα (διδασκαλία στην ελληνική γλώσσα):

    • Τετάρτη 10:45-12:30, Αμφ. 2 και 4
    • Παρασκευή 10:45-12:30, Αμφ. 2 και 4

    Το πρώτο μάθημα θα πραγματοποιηθεί Παρασκευή 3/10. 

    Για το 3ο τμήμα (φοιτητές Erasmus / διδασκαλία στην αγγλική γλώσσα):

    • Τρίτη 17:45-19:30, Αιθ. 05
    • Πέμπτη 17:45-19:30, Αμφ. 4

    Το πρώτο μάθημα για το τμήμα Erasmus/Αγγλικής γλώσσας θα πραγματοποιηθεί την Πέμπτη 2/10.

    Η σελίδα για το τμήμα αυτό βρίσκεται εδώ. Παρακαλούμε εγγραφείτε στη σελίδα αυτή αν επιθυμείτε να παρακολουθήσετε αυτό το τμήμα.

    Κάποιες φορές θα γίνεται φροντιστηριακό μάθημα ή/και αναπλήρωση μαθήματος σε ώρες που θα ανακοινωθούν στη συνέχεια. Θα ενημερώνεστε σχετικά με έγκαιρη ανακοίνωση.

    Επικουρικά, θα ανακοινωθούν σύντομα ώρες γραφείου για συναντήσεις με διδάσκοντες και βοηθούς προς επίλυση αποριών και βοήθεια με τις ασκήσεις. 

    Παρακάτω θα βρείτε σημειώσεις του μαθήματος καθώς και υλικό από προηγούμενα έτη (διαλέξεις, ασκήσεις). Μπορείτε να ανατρέχετε σε αυτό έως ότου αναρτηθεί το υλικό για το τρέχον έτος (θα προστίθεται σταδιακά).

      • Βαθμολογικό σχήμα

        Η τελική βαθμολογία προκύπτει ως εξής:

        • Ε: βαθμός τελικής εξέτασης, με άριστα το 10
        • Α: βαθμός ασκήσεων με άριστα το 2

        Τελικός Βαθμός = min{E * (1 + A/10), 10}

        Σημείωση: για να βαθμολογηθούν οι ασκήσεις σας θα πρέπει να τις παρουσιάσετε προφορικά σε ημερομηνία που θα καθοριστεί αργότερα. 

  • Περιεχόμενο Διαλέξεων

    • Ενότητα 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. Ασκήσεις στους αλγορίθμους αναζήτησης για παίγνια.  Διαφάνειες εδώ. 

  • Υλικό