Annalisa DE BONIS | Advanced Algorithmic Techniques For Distributed Systems
Annalisa DE BONIS Advanced Algorithmic Techniques For Distributed Systems
cod. 0522500105
ADVANCED ALGORITHMIC TECHNIQUES FOR DISTRIBUTED SYSTEMS
| 0522500105 | |
| DIPARTIMENTO DI INFORMATICA | |
| EQF7 | |
| COMPUTER SCIENCE | |
| 2016/2017 |
| YEAR OF COURSE 2 | |
| YEAR OF DIDACTIC SYSTEM 2015 | |
| SECONDO SEMESTRE |
| SSD | CFU | HOURS | ACTIVITY | |
|---|---|---|---|---|
| INF/01 | 6 | 48 | LESSONS |
| Objectives | |
|---|---|
| KNOWLEDGE AND UNDERSTANDING: THE MAIN GOAL OF THE CLASS IS TO STUDY THE TECHNIQUE FOR DESIGNING AND ANALYZING 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 COLORING, MAXIMAL INDEPENDENT SET, GRAPH DECOMPOSITON. THE PROBLEM OF CONGESTION: LOWER BOUNDS, RECENT DISTRIBUTED ALGORITHMS FOR MINIMUM SPANNING TREE AND SHORTEST PATHS. THE CLASS WILL ALSO ILLUSTRATE USEFUL ALGORITHMIC TOOLS LIKE GRAPH SPARSIFICATION AND SPANNERS. 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 AND UNDERSTANDING: THE STUDENTS ARE EXPECTED TO BECOME FAMILIAR WITH THE MOST RELEVANT TECHNIQUES FOR DESIGNING AND ANALYZING DISTRIBUTED ALGORITHMS AND SHOULD UNDERSTAND THE IMPACT THAT THESE TECHNIQUES HAVE ON A NUMBER OF CONCRETE PROBLEMS RELATED TO MODERN NETWORK COMMUNICATION TECNOLOGIES. COMMUNICATION SKILLS: THE CLASS WILL ENCOURAGE THE DEVELOPMENT OF THE FOLLOWING SKILLS OF THE STUDENT: CAPABILITY TO PRESENT IN PRECISE AND FORMAL TERMS AN ABSTRACT MODEL FOR CONCRETE PROBLEMS, FOCUSING ON THEIR MAIN FEATURES AND DISCARDING THOSE THAT ARE NOT RELEVANT. MAKING JUDGEMENTS: STUDENTS ARE GUIDED TO LEARN, IN A CRITICAL WAY, EVERYTHING IS EXPLAINED IN THE CLASS, TO COMPARE THE DIFFERENT APPROACHES FOR THE SOLUTION OF PROBLEMS ORIGINATING IN THE DISTRIBUTED MODEL. |
| 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 | |
|---|---|
| 48 LESSON HOURS: •CLASS OVERVIEW AND INTRODUCTORY NOTIONS. •GRAPH COLORING: GRAPH GOLORING IN CONSTANT-DEGREE GRAPHS ALGORITHMS AND LOWER BOUNDS; KUHN'S ALGORITHM THROUGH DEFECTIVE-COLORING •MAXIMAL INDEPENDENT SET: RANDOMIZED ALGORITHMS; APPLICATIONS TO RELATED PROBLEMS SUCH AS MATCHING AND VERTEX COLORING. •NETWORK DECOMPOSITIONS: THE DISTRIBUTED ALGORITHM OF AWERBUCH, GOLDBERG, LUBY, PLOTKIN. •MINIMUM SPANNING TREES: THE ALGORITHM OF KUTTEN AND PELEG. •LOWER BOUNDS ON COMMUNICATION COMPLEXITY: LOWER BOUNDS FOR MINIMUM SPANNING TREE AND SINGLE SOURCE SHORTEST PATHS. •SHORTEST PATHS: APPROXIMATION ALGORITHMS FOR SINGLE SOURCE SHORTEST PATHS AND A LINEAR DETERMINISTIC ALGORITM FOR ALL PAIRS SHORTES PATHS. •SPANNERS AND SPARSIFICATION. •BROADCAST IN WIRELESS NEWORKS: RANDOMIZED ALGORITHMS, DETERMINISTIC ALGORITHMS BASED ON SELECTIVE FAMILIES |
| Teaching Methods | |
|---|---|
| THE CLASS INCLUDES THEORETICAL LECTURES AND SEMINAR ACTIVITIES THAT WILL ACTIVELY INVOLVE STUDENTS IN DISCUSSIONS AND PRESENTATIONS. |
| Verification of learning | |
|---|---|
| THERE WILL BE A FINAL ORAL EXAMINATION. |
| Texts | |
|---|---|
| TEACHING MATERIAL WILL BE MADE AVAILABLE IN CLASS AND ON THE CLASS WEBSITE. |
BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2019-03-11]
