Αλγόριθμοι και Πολυπλοκότητα (6ΕΠ05)
Διδάσκων : Ευριπίδης Μάρκου
Βοηθός : Γιαχούδης Νικόλαος
ΕίδοςΕπιλογής (υποχρεωτικό)
Εξάμηνο6
ΠερίοδοςΕΕ
ECTS5
Ώρες Θεωρίας3
Ώρες Εργαστηρίου
Περιγραφή
Η έννοια του αλγορίθμου και της πολυπλοκότητας. Μέθοδοι σχεδιασμού καλών αλγορίθμων: “διαίρει και κυρίευε”, δυναμικός προγραμματισμός, άπληστοι αλγόριθμοι. Εφαρμογές στη θεωρία γραφημάτων (αναζήτηση σε βάθος, αναζήτηση σε πλάτος, ελάχιστο δένδρο-σκελετός, διαδρομή ελαχίστου κόστους). Επεξεργασία δεδομένων (διάταξη και αναζήτηση). Αλγεβρικά προβλήματα (υπολογισμός πολυωνύμων, πολλαπλασιασμός πινάκων). Αλγόριθμοι πολυωνυμικού χρόνου και ΝΡ-πλήρη προβλήματα. Εύκολα και δύσκολα προβλήματα συνδυαστικής βελτιστοποίησης, προβλήματα απόφασης, οι κλάσεις P και NP, προβλήματα NP-complete και αναγωγές. Το πρόβλημα του σακιδίου (knapsack problem), το πρόβλημα του πλανόδιου πωλητή (TSP). Παράλληλοι και κατανεμημένοι αλγόριθμοι.
Μαθησιακοί Στόχοι
  • Ανάλυση αλγορίθμων (ορθότητα και πολυπλοκότητα)
  • Μέθοδοι σχεδίασης αλγορίθμων
  • Υπολογιστικά ‘δύσκολα’ προβλήματα
  • Παράλληλοι και κατανεμημένοι αλγόριθμοι
Συγγράμματα/Βιβλιογραφία
  • Εισαγωγή στους Αλγόριθμους (σε έναν τόμο), T. Cormen, C. Leiserson, R. Rivest, C. Stein, Πανεπιστημιακές Εκδόσεις Κρήτης, 2012
  • Αλγόριθμοι, S. Dasgupta, C. Papadimitriou, U. Vazirani, Εκδόσεις Κλειδάριθμος ΕΠΕ, 2009
  • Σχεδιασμός Αλγορίθμων, J. Kleinberg, E. Tardos, Εκδόσεις Κλειδάριθμος ΕΠΕ, 2009
  • Αλγόριθμοι και Πολυπλοκότητα, Ε. Ζάχος, Σημειώσεις, Εθνικό Μετσόβιο Πολυτεχνείο, 2007
  • Αλγόριθμοι, Π. Μποζάνης, Εκδόσεις Α. Τζιολα & Υιοί Α. Ε., 2006
  • Ανάλυση και σχεδίαση αλγορίθμων, L. Anany, Εκδόσεις Α. Τζιολα & Υιοί Α. Ε., 2008
  • The design and Analysis of Computer Algorithms, A. Aho, J. Hopcroft, J. Ullman. Addison-Wesley Publishing Company, 1974.
  • Computers and Intractability: A Guide to the Theory of NP-Completeness, M. Garey, D. Johnson. W. H. Freeman and Company, 1979
  • Design and Analysis of Distributed Algorithms, N. Santoro. Wiley, 2006
  • The Mobile Agent Rendezvous Problem in the Ring, E. Kranakis, D. Krizanc, E. Markou. Morgan & Claypool Publishers, 2010
Τρόπος Εξέτασης
Μία σειρά ασκήσεων κάθε 3 εβδομάδες, ενδιάμεση γραπτή εξέταση (πρόοδος), τελικές γραπτές εξετάσεις.
Υλικό
Σημειώσεις