Αλγόριθμοι και Πολυπλοκότητα (6ΕΠ05)

Κωδικός: 
6ΕΠ05
Περιγραφή: 
Η έννοια του αλγορίθμου και της πολυπλοκότητας. Μέθοδοι σχεδιασμού καλών αλγορίθμων: “διαίρει και κυρίευε”, δυναμικός προγραμματισμός, άπληστοι αλγόριθμοι. Εφαρμογές στη θεωρία γραφημάτων (αναζήτηση σε βάθος, αναζήτηση σε πλάτος, ελάχιστο δένδρο-σκελετός, διαδρομή ελαχίστου κόστους). Επεξεργασία δεδομένων (διάταξη και αναζήτηση). Αλγεβρικά προβλήματα (υπολογισμός πολυωνύμων, πολλαπλασιασμός πινάκων). Αλγόριθμοι πολυωνυμικού χρόνου και ΝΡ-πλήρη προβλήματα. Εύκολα και δύσκολα προβλήματα συνδυαστικής βελτιστοποίησης, προβλήματα απόφασης, οι κλάσεις P και NP, προβλήματα NP-complete και αναγωγές. Το πρόβλημα του σακιδίου (knapsack problem), το πρόβλημα του πλανόδιου πωλητή (TSP). Παράλληλοι και κατανεμημένοι αλγόριθμοι.
Όνομα: 
Αλγόριθμοι και Πολυπλοκότητα
Είδος: 
Επιλογής (υποχρεωτικό)
Περίοδος: 
ΕΕ
Εξάμηνο: 
6
Ώρες Θεωρίας: 
4
ECTS: 
4
Συγγράμματα: 
- Εισαγωγή στους Αλγόριθμους (σε έναν τόμο), T. Cormen, C. Leiserson, R. Rivest, C. Stein, Πανεπιστημιακές Εκδόσεις Κρήτης, 2012 - Αλγόριθμοι, S. Dasgupta, C. Papadimitriou, U. Vazirani, Εκδόσεις Κλειδάριθμος ΕΠΕ, 2009
Βιβλιογραφία: 
- Εισαγωγή στους Αλγόριθμους (σε έναν τόμο), T. Cormen, C. Leiserson, R. Rivest, C. Stein, Πανεπιστημιακές Εκδόσεις Κρήτης, 2012 - Σχεδιασμός Αλγορίθμων, J. Kleinberg, E. Tardos, Εκδόσεις Κλειδάριθμος ΕΠΕ, 2009 - Αλγόριθμοι, S. Dasgupta, C. Papadimitriou, U. Vazirani, Εκδόσεις Κλειδάριθμος ΕΠΕ, 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 εβδομάδες, ενδιάμεση γραπτή εξέταση (πρόοδος), τελικές γραπτές εξετάσεις.
Υλικό: 
Σημειώσεις