Αλγόριθμοι και Πολυπλοκότητα (6ΕΠ05)
Διδάσκων : Ευριπίδης Μάρκου
Βοηθός : Γιαχούδης Νικόλαος
ΕίδοςΕπιλογής (υποχρεωτικό)
Εξάμηνο6
ΠερίοδοςΕΕ
ECTS5
Ώρες Θεωρίας3
Ώρες Εργαστηρίου
Περιγραφή
Η έννοια του αλγορίθμου και της πολυπλοκότητας. Μέθοδοι σχεδιασμού καλών αλγορίθμων: “διαίρει και κυρίευε”, δυναμικός προγραμματισμός, άπληστοι αλγόριθμοι. Εφαρμογές στη θεωρία γραφημάτων (αναζήτηση σε βάθος, αναζήτηση σε πλάτος, ελάχιστο δένδρο-σκελετός, διαδρομή ελαχίστου κόστους). Επεξεργασία δεδομένων (διάταξη και αναζήτηση). Αλγεβρικά προβλήματα (υπολογισμός πολυωνύμων, πολλαπλασιασμός πινάκων). Αλγόριθμοι πολυωνυμικού χρόνου και ΝΡ-πλήρη προβλήματα. Εύκολα και δύσκολα προβλήματα συνδυαστικής βελτιστοποίησης, προβλήματα απόφασης, οι κλάσεις 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 εβδομάδες, ενδιάμεση γραπτή εξέταση (πρόοδος), τελικές γραπτές εξετάσεις.
Υλικό
Σημειώσεις