Αλγόριθμοι και Πολυπλοκότητα

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

• Ανάλυση αλγορίθμων (ορθότητα και πολυπλοκότητα)
• Μέθοδοι σχεδίασης αλγορίθμων
• Υπολογιστικά ‘δύσκολα’ προβλήματα
• Παράλληλοι και κατανεμημένοι αλγόριθμοι

• ΕΙΣΑΓΩΓΗ ΣΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ , Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, ΙΤΕ/ΠΑΝΕΠΙΣΤΗΜΙΑΚΕΣ ΕΚΔΟΣΕΙΣ ΚΡΗΤΗΣ,  1η/2016, ΗΡΑΚΛΕΙΟ ΚΡΗΤΗΣ, 59359780
• ΣΧΕΔΙΑΣΜΟΣ ΑΛΓΟΡΙΘΜΩΝ, JON KLEINBERG, EVA TARDOS, “ΕΚΔΟΣΕΙΣ ΚΛΕΙΔΑΡΙΘΜΟΣ ΕΠΕ”, 1η/2009, ΑΘΗΝΑ, 13898
• ΑΛΓΟΡΙΘΜΟΙ, SANJOY DASGUPTA, CHRISTOS PAPADIMITRIOU, UMESH VAZIRANI, ΕΚΔΟΣΕΙΣ ΚΛΕΙΔΑΡΙΘΜΟΣ ΕΠΕ, 1η/2009, ΑΘΗΝΑ, 13583
• Αλγόριθμοι, 2η Έκδοση, Μποζάνης Παναγιώτης Δ., “ΕΚΔΟΣΕΙΣ Α. ΤΖΙΟΛΑ & ΥΙΟΙ Α.Ε. “, 1η/2006, ΘΕΣ/ΝΙΚΗ, 68369726
• Ανάλυση και Σχεδίαση Αλγορίθμων, 3η Έκδοση, Levitin Anavy, Mάνος Ρουμελιώτης (επιμέλεια), ΕΚΔΟΣΕΙΣ Α. ΤΖΙΟΛΑ & ΥΙΟΙ Α.Ε., 3η/2018, ΘΕΣ/ΝΙΚΗ, 68370088
• ΑΛΓΟΡΙΘΜΙΚΗ ΘΕΩΡΙΑ ΚΑΤΑΝΕΜΗΜΕΝΩΝ ΥΠΟΛΟΓΙΣΜΩΝ, ΕΥΡΙΠΙΔΗΣ ΜΑΡΚΟΥ, “Ελληνικά Ακαδημαϊκά Ηλεκτρονικά Συγγράμματα και Βοηθήματα – Αποθετήριο “”Κάλλιπος””” ,  1η/2016, ΑΘΗΝΑ, 59303549

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

Σημειώσεις