Roberto DE PRISCO | ADVANCED ALGORITHMS
Roberto DE PRISCO ADVANCED ALGORITHMS
cod. 0522500064
ADVANCED ALGORITHMS
| 0522500064 | |
| COMPUTER SCIENCE | |
| EQF7 | |
| COMPUTER SCIENCE | |
| 2021/2022 |
| YEAR OF COURSE 2 | |
| YEAR OF DIDACTIC SYSTEM 2016 | |
| AUTUMN SEMESTER |
| SSD | CFU | HOURS | ACTIVITY | |
|---|---|---|---|---|
| INF/01 | 2 | 16 | LAB | |
| INF/01 | 7 | 56 | LESSONS |
| Objectives | |
|---|---|
| THE GOAL OF THIS CLASS IS THAT OF TEACHING THE NECESSARY TOOLS FOR AN ADVANCED KNOWLEDGE OF THE FIELD OF ALGORITHMS ALLOWING THE STUDENT TO BEING ABLE TO TACKLE AND SOLVE IN THE BEST POSSIBLE WAY REAL-LIFE PROBLEMS. KNOWLEDGE AND UNDERSTANDING THE STUDENT WILL BE ACQUAINTED WITH THE VARIOUS TYPES OF ADVANCED ALGORITHMS BEYOND THE BASICS OF ALGORITHMS. IN PARTICULAR THE STUDENT WILL ACQUIRE KNOWLEDGE OF APPROXIMATION ALGORITHMS, RANDOMIZED ALGORITHMS, ONLINE ALGORITHMS AND DISTRIBUTED ALGORITHMS. ABILITY TO APPLY KNOWLEDGE AND UNDERSTANDING THE STUDENT WILL BE ABLE TO APPLY THE METHODOLOGIES LEARNED TO REAL PROBLEMS WITH A CRITICAL SPIRIT AND IN A SYNERGISTIC WAY. |
| Prerequisites | |
|---|---|
| NECESSARY KNOWLEDGE: DATA STRUCTURES, BASIC ALGORITHMS, BASIC MATH, BASIC PROBABILITY THEORY. CRYPTOGRAPHIC KNOWLEDGE IS USEFUL FOR THE PART ON DISTRIBUTED SYSTEMS. |
| Contents | |
|---|---|
| THE COURSE IS ORGANIZED IN 6 PARTS, EACH OF WHICH WILL PROVIDE AN INTRODUCTION TO THE FOLLOWING TOPICS. 1.P VS. NP: REDUCTIONS, INDEPENDENT-SET, VERTEX COVER, SET COVER, SET PACKING, SAT, 3SAT, NP-HARD PROBLEMS, PSPACE. 2.SMART EXHAUSTIVE SEARCH: BACKTRACKING E BRANCH-AND-BOUND E ADDITIONAL TECHNIQUES 3.APPROXIMATION ALGORITHMS FOR VERTEX COVER, LOAD BALANCING, K-CENTER, KNAPSACK. 4.RANDOMIZED ALGORITHMS: QUICKSORT, GLOBAL MIN CUT, MAX-3SAT 5.ONLINE ALGORITHMS: PAGING, LIST, LOAD BALANCING, BIN PACKING. PROBABILISTIC ANALYSIS. 6.DISTRIBUTED ALGORITHMS: CONSENSUS PROBLEM, IMPOSSIBILITY RESULTS, ALGORITHMS FOR VARIOUS COMPUTATION MODELS; DISTRIBUTED LEDGERS, BLOCKCHAIN. |
| Teaching Methods | |
|---|---|
| 72 HOURS OF LECTURES. |
| Verification of learning | |
|---|---|
| WRITTEN EXAM AND AN OPTIONAL (DECIDED BY THE TEACHER) ORAL EXAM. |
| Texts | |
|---|---|
| "ALGORITHM DESIGN", KLEINBERG, TARDOS. EDITORE: PEARSON “DISTRIBUTED ALGORITHMS”, NANCY LYNCH. EDITORE: MORGAN KAUFFMAN |
BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2022-11-21]
