Θεωρητική Πληροφορική ΙΙ: Παράλληλοι Αλγόριθμοι και Πολυπλοκότητα
εαρινό εξάμηνο 2005-2006
Γενικά
Διδάσκων
- Στάθης Ζάχος, Καθηγητής ()
Διαλέξεις
- Πέμπτη 17:00-21:00, αίθουσα 1.1.29 Κτήριο Ηλεκτρολόγων (ΕΜΠ)
Περιεχόμενο μαθήματος
Μελέτη διάφορων παράλληλων αλγορίθμων και της πολυπλοκότητάς τους. Σχεδιασμός, αναγνώριση, ανάλυση, αξιολόγηση αποδοτικότητας, σύγκριση και ταξινόμηση διάφορων παράλληλων αλγορίθμων. Η τεχνική της απόδειξης κάτω φράγματος για την πολυπλοκότητα επίλυσης προβλημάτων με παράλληλες μεθόδους. Τοπολογίες παράλληλων αλγορίθμων: πίνακες, δέντρα, meshes of trees, hypercubes. Κλάσεις πολυπλοκότητας NC, κ.λ.π.
Επίσης εφαρμογές παράλληλων μεθόδων σε διάφορα προβλήματα:
- Ταξινόμηση.
- Αριθμητικές πράξεις.
- Πράξεις σε πίνακες.
- Γραφοθεωρητικά προβλήματα.
- Packet Routing.
Βιβλιογραφία
- F. T. Leighton: Introduction to Parallel Algorithms and architectures: Arrays, Trees, Hypercubes, Morgan Kaufman Publishers, San Mateo, California, 1992.
- L. Boxer: Algorithms Sequential and Parallel: A unified apprach, Russ Miller.
- M. J. Quinn: Desingning Efficient Algorithms for Parallel Computers, McGraw-Hill 1987, ISBN 0-07-100249-9.
- I. Parberry: Parallel Complexity Theory, Research Notes in Theoretical Computer Science, R.V. Book (Ed.), John Wiley and Sons (New York), 1987.
Ανακοινώσεις
Υλικό
Παρουσιάσεις
| Παράγραφος 1.1 | Στάθης Ζάχος | |
|---|---|---|
| Παράγραφος 1.2 | Βούλγαρης Παναγιώτης, Μωλ Πέτρος | |
| Παράγραφος 1.3 | Καούρη Γεωργία, Μήτσου Βασιλική | Matrix Algorithms |
| Παράγραφος 1.4 | Στάθης Ζάχος | |
| Παράγραφος 1.5 | Καούρη Γεωργία, Μήτσου Βασιλική | Graph Algorithms |
| Παράγραφος 1.6 | Τέντες Αριστείδης | Sorting |
| Παράγραφος 1.7 | Κομνηνός Σπύρος | Packet Routing |
| Παράγραφος 1.8 | Ποτίκας Πέτρος | Image Analysis and Computational Geometry |
| Παράγραφος 1.9 | Καούρη Γεωργία, Μήτσου Βασιλική | Higher Dimensional Algorithms |
| Παράγραφος 2.1 | Βούλγαρης Παναγιώτης, Μωλ Πέτρος | The 2-dimensional mesh of trees |
| Παράγραφος 2.2 | Κομνηνός Σπύρος, Τέντες Αριστείδης | Elementary O(logN)-Step Algorithms |
| Παράγραφος 2.3 | Βούλγαρης Παναγιώτης, Μωλ Πέτρος | Integer Arithmetic |
| Παράγραφος 2.4 | Καούρη Γεωργία, Μήτσου Βασιλική | Matrix Algorithms |
| Παράγραφος 2.5 | Καούρη Γεωργία, Μήτσου Βασιλική | Graph Algorithms |
| Παράγραφος 2.6 | ||
| Παράγραφος 2.7 | Κουτσώνας Θανάσης, Λαμπής Μιχάλης | Higher Dimensional Meshes of Trees |
| Παράγραφος 3.1 | Βούλγαρης Παναγιώτης, Μωλ Πέτρος | Παρουσίαση |
| Παράγραφος 3.2 | Κουτσώνας Θανάσης, Λαμπής Μιχάλης | Butterfly, CCC, Benes Network |
| Παράγραφος 3.3 | Κουτσώνας Θανάσης, Λαμπής Μιχάλης | Shuffle-Exchange De-Bruijn |
| Παράγραφος 3.4 | Κομνηνός Σπύρος | Packet Routing in hypercubic networks |
| Παράγραφος 3.5 | Τέντες Αριστείδης | Sorting οn hypercubic networks |
| Παράγραφος 3.6 | Μπαμπάς Ευάγγελος | Simulating a Parallel Random Access Machine + Sections 2,3,4 από Topics in parallel computing του Pavel Tvrdik |
| Παράγραφος 3.7 | Παπανικολάου Κωνσταντίνος | Fast Fourier Transform |
| Παράγραφος 3.8 |