Section outline

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

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

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

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

    Διδάσκοντες

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

    Διαλέξεις

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

    Το πρώτο μάθημα θα πραγματοποιηθεί Τετάρτη 4/10. 

    Κάποιες φορές θα γίνεται φροντιστηριακό μάθημα ή/και αναπλήρωση μαθήματος την Παρασκευή, ώρα 12:45-14:30. Θα ενημερώνεστε σχετικά με έγκαιρη ανακοίνωση.

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

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

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

    • Ενότητα 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: Τεχνητή Νοημοσύνη

      • Εισαγωγή στην Τεχνητή Νοημοσύνη, Ευφυείς δράστες, αναπαράσταση προβλημάτων σε χώρο καταστάσεων, αλγόριθμοι αναζήτησης λύσης, πολυπλοκότητα προβλημάτων αναζήτησης λύσης, αλγόριθμοι τυφλής αναζήτησης (BFS, DFS, επαναληπτικής εκβάθυνσης), ευρετικοί αλγόριθμοι επίλυσης προβλημάτων (Hill climbing, Best-first), εύρεση βέλτιστης λύσης (απλή αναφορά και εποπτική περιγραφή αλγόριθμων εύρεσης βέλτιστης λύσης).


  • Υλικό