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 | |
| 2016/2017 |
| YEAR OF COURSE 2 | |
| YEAR OF DIDACTIC SYSTEM 2015 | |
| PRIMO SEMESTRE |
| SSD | CFU | HOURS | ACTIVITY | |
|---|---|---|---|---|
| INF/01 | 6 | 24 | 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. 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 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 | |
|---|---|
| 24 LESSON HOURS •CLASS OVERVIEW AND INTRODUCTORY NOTIONS (1 HOUR). •GRAPH COLORING: GRAPH GOLORING IN CONSTANT-DEGREE GRAPHS ALGORITHMS AND LOWER BOUNDS (4 HOURS) •MAXIMAL INDEPENDENT SET: RANDOMIZED ALGORITHMS; APPLICATIONS TO RELATED PROBLEMS SUCH AS MATCHING AND VERTEX COLORING. (5 HOURS) •MINIMUM SPANNING TREES: THE ALGORITHM OF KUTTEN AND PELEG. (4 HOURS) •LOWER BOUNDS ON COMMUNICATION COMPLEXITY: LOWER BOUNDS FOR MINIMUM SPANNING TREE (4 HOURS) •BROADCAST IN WIRELESS NEWORKS: RANDOMIZED ALGORITHMS, DETERMINISTIC ALGORITHMS BASED ON SELECTIVE FAMILIES (6 HOURS) |
| 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. |
| More Information | |
|---|---|
| http://elearning.informatica.unisa.it/el-platform/login/index.php |
BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2019-03-11]
