Annalisa DE BONIS | Advanced Algorithmic Techniques For Distributed Systems (English)
Annalisa DE BONIS Advanced Algorithmic Techniques For Distributed Systems (English)
| 0522500106 | |
| DIPARTIMENTO DI INFORMATICA | |
| EQF7 | |
| COMPUTER SCIENCE | |
| 2017/2018 |
| YEAR OF COURSE 2 | |
| YEAR OF DIDACTIC SYSTEM 2016 | |
| PRIMO SEMESTRE |
| SSD | CFU | HOURS | ACTIVITY | |
|---|---|---|---|---|
| INF/01 | 6 | 24 | LESSONS |
| Objectives | |
|---|---|
| THE MAIN GOAL OF THE CLASS IS TO STUDY THE TECHNIQUE FOR DESIGNING AND ANALYSING DISTRIBUTED GRAPH ALGORITHMS, AND FOR PROVING THE LIMITATIONS OF THESE ALGORITHMS. THE TOPICS CAN BE GROUPED IN THE FOLLOWING THREE AREAS: • LOCALITY IN GRAPH PROBLEMS: GRAPH COLOURING, MAXIMAL INDEPENDENT SET • THE PROBLEM OF CONGESTION: LOWER BOUNDS, RECENT DISTRIBUTED ALGORITHMS FOR MINIMUM SPANNING TREE • BROADCAST ALGORITHMS FOR WIRELESS NETWORKS: THE CLASS WILL COVER BOTH DETERMINISTIC ALGORITHMS AND RANDOMIZED ALGORITHMS. AS FAR AS IT CONCERNS DETERMINISTIC ALGORITHMS, IT WILL COVER RECENT ALGORITHMS BASED ON SELECTIVE FAMILIES. APPLYING KNOWLEDGE: • THE STUDENTS ARE EXPECTED TO BECOME FAMILIAR WITH THE MOST RELEVANT TECHNIQUES FOR DESIGNING AND ANALYSING DISTRIBUTED ALGORITHMS. • THE STUDENTS ARE EXPECTED TO UNDERSTAND THE IMPACT THAT THE ABOVE TECHNIQUES HAVE ON A NUMBER OF CONCRETE PROBLEMS RELATED TO MODERN NETWORK COMMUNICATION TECHNOLOGIES. THE STUDENT SHOULD HAVE ACQUIRED THE BASIC NOTIONS OF MATHEMATICS AND SHOULD ALSO HAVE LEARNED THE BASIC CONCEPTS OF THE DESIGN AND ANALYSIS OF ALGORITHMS. THE CLASS WILL FOCUS ON THE FOLLOWING SUBJECTS: • CLASS OVERVIEW AND INTRODUCTORY NOTIONS • GRAPH COLOURING: GRAPH COLOURING IN CONSTANT-DEGREE GRAPHS ALGORITHMS AND LOWER BOUNDS • MAXIMAL INDEPENDENT SET: RANDOMIZED ALGORITHMS; APPLICATIONS TO RELATED PROBLEMS SUCH AS MATCHING AND VERTEX COLOURING • MINIMUM SPANNING TREES: THE ALGORITHM OF KUTTEN AND PELEG • LOWER BOUNDS ON COMMUNICATION COMPLEXITY: LOWER BOUNDS FOR MINIMUM SPANNING TREE • BROADCAST IN WIRELESS NETWORKS: RANDOMIZED ALGORITHMS, DETERMINISTIC ALGORITHMS BASED ON SELECTIVE FAMILIES |
| Prerequisites | |
|---|---|
| THE STUDENT SHOULD HAVE ACQUIRED THE BASIC NOTIONS OF MATHEMATICS AND SHOULD ALSO HAVE LEARNED THE BASIC CONCEPTS OF THE DESIGN AND ANALYSIS OF ALGORITHMS. |
| Contents | |
|---|---|
| THE CLASS WILL FOCUS ON THE FOLLOWING SUBJECTS: • CLASS OVERVIEW AND INTRODUCTORY NOTIONS • GRAPH COLOURING: GRAPH COLOURING IN CONSTANT-DEGREE GRAPHS ALGORITHMS AND LOWER BOUNDS • MAXIMAL INDEPENDENT SET: RANDOMIZED ALGORITHMS; APPLICATIONS TO RELATED PROBLEMS SUCH AS MATCHING AND VERTEX COLOURING • MINIMUM SPANNING TREES: THE ALGORITHM OF KUTTEN AND PELEG • LOWER BOUNDS ON COMMUNICATION COMPLEXITY: LOWER BOUNDS FOR MINIMUM SPANNING TREE • BROADCAST IN WIRELESS NETWORKS: RANDOMIZED ALGORITHMS, DETERMINISTIC ALGORITHMS BASED ON SELECTIVE FAMILIES |
| Teaching Methods | |
|---|---|
| THE COURSE COINSISTS IN THEORETICAL LESSONS AND IN SEMINARS THAT MAY INVOLVE STUDENTS IN PRESENTING SPECIFIC TOPICS. |
| Verification of learning | |
|---|---|
| THERE WILL BE A FINAL ORAL EXAMINATION CONSISTING IN • A DISCUSSION ON THE THEORETICAL SUBJECTS AND THE METHODOLOGIES LISTED IN THE SYLLABUS • A BRIEF SEMINAR ON A TOPIC TO BE SELECTED AMONG A CHOICE OF TOPICS PROPOSED BY THE INSTRUCTOR |
| Texts | |
|---|---|
| TEACHING MATERIAL WILL BE MADE AVAILABLE IN CLASS AND ON THE CLASS WEBSITE. |
| More Information | |
|---|---|
| Further information can be found on the Degree official web site. |
BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2019-05-14]
