Η έννοια του αλγορίθμου και της πολυπλοκότητας. Μέθοδοι σχεδιασμού καλών αλγορίθμων: “διαίρει και κυρίευε”, δυναμικός προγραμματισμός, άπληστοι αλγόριθμοι. Εφαρμογές στη θεωρία γραφημάτων (αναζήτηση σε βάθος, αναζήτηση σε πλάτος, ελάχιστο δένδρο-σκελετός, διαδρομή ελαχίστου κόστους). Επεξεργασία δεδομένων (διάταξη και αναζήτηση). Αλγεβρικά προβλήματα (υπολογισμός πολυωνύμων, πολλαπλασιασμός πινάκων). Αλγόριθμοι πολυωνυμικού χρόνου και ΝΡ-πλήρη προβλήματα. Εύκολα και δύσκολα προβλήματα συνδυαστικής βελτιστοποίησης, προβλήματα απόφασης, οι κλάσεις P και NP, προβλήματα NP-complete και αναγωγές. Το πρόβλημα του σακιδίου (knapsack problem), το πρόβλημα του πλανόδιου πωλητή (TSP). Παράλληλοι και κατανεμημένοι αλγόριθμοι.
Εαρ. Εξάμηνο. Μάθημα επιλογής 3ου έτους.
Πρόγραμμα:
Προαπαιτούμενες γνώσεις ή/και σχετικά μαθήματα:
Διακριτά Μαθηματικά, Εισαγωγή στον Προγραμματισμό, Αντικειμενοστρεφής Προγραμματισμός, Δομές Δεδομένων, Θεωρία Γράφων, Θεωρία Υπολογισμού
Μαθησιακοί Στόχοι:
- Ανάλυση αλγορίθμων (ορθότητα και πολυπλοκότητα)
- Μέθοδοι σχεδίασης αλγορίθμων
- Υπολογιστικά ‘δύσκολα’ προβλήματα
- Παράλληλοι και κατανεμημένοι αλγόριθμοι
Μέθοδοι Διδασκαλίας:
Διαλέξεις θεωρίας (3 ώρες/εβδομάδα) και επιπλέον φροντιστηριακά μαθήματα με επίλυση ασκήσεων (2 ώρες/ 3 εβδομάδες).
Τρόπος Εξέτασης:
Μία σειρά ασκήσεων κάθε 3 εβδομάδες, ενδιάμεση γραπτή εξέταση (πρόοδος), τελικές γραπτές εξετάσεις.
Υλικό: Σημειώσεις