Προχωρημένα Θέματα Θεωρητικής Πληροφορικής: Παράλληλοι Αλγόριθμοι και Πολυπλοκότητα
| Κωδικός | 400 |
|---|---|
| Εξάμηνο | Εαρινό |
| Ώρες Διδασκαλίας - Ώρες Εργαστηρίου | 4 - 0 |
| Διδάσκοντες | Ευστάθιος Ζάχος, Αριστείδης Παγουρτζής, Δημήτριος Φωτάκης |
Περιγραφή
Μοντέλα παράλληλου υπολογισμού: circuits, PRAM, BSP, map-reduce. Μελέτη παράλληλων αλγορίθμων και της πολυπλοκότητάς τους. Σχε¬διασμός, αναγνώριση, ανάλυση, αξιολόγηση αποδοτικότητας, σύγκριση και τα¬ξινόμηση διάφορων παράλληλων αλγορίθμων, Η τεχνική της απόδειξης κάτω φράγματος για την πολυπλοκότητα επίλυσης προβλημάτων με παράλληλες μεθό¬δους. Τοπολογίες παράλληλων συστολικών αλγορίθμων: πίνακες, δέντρα, meshes of trees, hypercubes. Κλάσεις πολυπλοκότητας NC, AC, TC, κ.λ.π. Εφαρμογές παράλληλων μεθόδων σε διάφορα προβλήματα: ταξινόμηση, αριθμητικές πράξεις, πράξεις σε πίνακες, γραφοθεωρητικά προβλήματα, κ.ά. Κατανεμημένοι υπολογισμοί: εκπομπή, εκλογή αρχηγού, χρωματιμσμός, MST, συντονισμός, αξιόπιστοι υπολογισμοί. Κινητοί πράκτορες: πρόβλημα συνάντησης, συγκέντρωση ρομποτ, αναζήτηση "μαύρης τρύπας, κλέφτες-και-αστυνόμοι, πρόβλημα πυροσβεστών, καθαρισμός δικτύου. Προαπαιτούμενα: Διακριτά μαθηματικά, Αλγόριθμοι και πολυπλοκότητα.