| Γνωστική Περιοχή: | Υπολογιστικών και Εφαρμοσμένων Μαθηματικών | ||
| Εξάμηνο: | 6ο | ||
| Κωδικός: | 62401 | ||
| Τύπος Μαθήματος: | Επιλογής | ||
| Ώρες Διδασκαλίας: | Θεωρία: 3 | Άσκηση: 0 | Εργαστήριο: 0 |
| ECTS : | 5 | ||
| Ιστοσελίδα Eclass: | |||
| Διδάσκοντες Μαθήματος: | |||
| Περίγραμμα μαθήματος: | Για να δείτε ή να αποθηκεύσετε το αρχείο πατήστε εδώ. | ||
Περιεχόμενο
Η έννοια του αλγορίθμου και της πολυπλοκότητας. Μέθοδοι σχεδιασμού καλών αλγορίθμων: “διαίρει και κυρίευε”, δυναμικός προγραμματισμός, άπληστοι αλγόριθμοι. Εφαρμογές στη θεωρία γραφημάτων (αναζήτηση σε βάθος, αναζήτηση σε πλάτος, ελάχιστο δένδρο-σκελετός, διαδρομή ελαχίστου κόστους). Επεξεργασία δεδομένων (διάταξη και αναζήτηση). Αλγεβρικά προβλήματα (υπολογισμός πολυωνύμων, πολλαπλασιασμός πινάκων). Αλγόριθμοι πολυωνυμικού χρόνου και ΝΡ-πλήρη προβλήματα. Εύκολα και δύσκολα προβλήματα συνδυαστικής βελτιστοποίησης, προβλήματα απόφασης, οι κλάσεις P και NP, προβλήματα NP-complete και αναγωγές. Το πρόβλημα του σακιδίου (knapsack problem), το πρόβλημα του πλανόδιου πωλητή (TSP). Παράλληλοι και κατανεμημένοι αλγόριθμοι.
Βιβλιογραφία
- T. Cormen, C. Leiserson, R. Rivest, C. Stein, Εισαγωγή στους Αλγόριθμους (σε έναν τόμο), Παν. Εκδ. Κρήτης, 2016. Κωδικός βιβλίου στον Εύδοξο: 59359780
- J. Kleinberg, E. Tardos, Σχεδιασμός Αλγορίθμων, Εκδ. Κλειδάριθμος, 2009. Κωδικός βιβλίου στον Εύδοξο: 13898
- S. Dasgupta, C. Papadimitriou, U. Vazirani, Αλγόριθμοι, Εκδ. Κλειδάριθμος, 2009. Κωδικός βιβλίου στον Εύδοξο: 13583
- L. Anany, Ανάλυση και σχεδίαση αλγορίθμων, Εκδ. Τζιόλα, 2008. Κωδικός βιβλίου στον Εύδοξο: 18549038
Πρόσθετο Διδακτικό Υλικό
- Ευρ. Μάρκου, Αλγοριθμική θεωρία κατανεμημένων Υπολογισμών, Ελληνικά Ακαδημαϊκά Ηλεκτρονικά Συγγράμματα και Βοηθήματα – Αποθετήριο Κάλλιπος, 2016.
