PARALLEL AND DISTRIBUTED ALGORITHMS
Academic year2016/17
CourseCOMPUTER SCIENCE AND NETWORKING
Code314AA
Credits6
PeriodSemester 2
LanguageEnglish
| Modules | Area | Type | Hours | Teacher(s) |
| ALGORITMI PARALLELI E DISTRIBUITI | INF/01 | LEZIONI | 48 | |
Programma non disponibile nella lingua selezionata
Knowledge
The goal of the course is to introduce the main algorithmic techniques in the framework of parallel and distributed models of computing, and to define the most significant complexity parameters and the computational limits of parallelism and concurrency. and to define the most significant complexity parameters and the computational limits of parallelism and concurrency. Finally, computational tools to design and analyze parallel and distributed algorithms are given.
Assessment criteria of knowledge
Methods:
- Final written exam
- Oral report
Further information:
Written Exam (50%).
Seminar presentation of a scientific paper chosen by the student, and approved by the teacher.
Teaching methods
Delivery: face to face
Learning activities:
- attending lectures
- participation in seminar
- Bibliography search
Attendance: Not mandatory
Teaching methods:
Syllabus
1. Models of computation
The PRAM model
Bounded degree networks. BSP.
The distributed model.
2. Design and analysis of parallel algorithms
Prefix sums, List Ranking, Euler tour.
Standard techniques and inner sequential problems.
3. Design and analysis of distributed algorithms
Communication complexity.
Control algorithms.
Fault tolerant algorithms.
Distributed data manipulation.
Classical examples: Broadcast e Spanning tree; Computationon trees: Saturation, functions evaluation; Election
on Ring and othernetworks; Routing.
Distributed coordination and control of autonomous mobile robots.
Bibliography
1. Nicola Santoro: "Design and Analysis of Distributed Algorithms", Whiley- Interscience, 2007.
2. Introduction to Parallel Algorithms, Joseph JaJa, 1992.
Updated: 14/11/2016 17:27
