Gianluca DE MARCO | INTRODUZIONE AGLI ALGORITMI RANDOMIZZATI
Gianluca DE MARCO INTRODUZIONE AGLI ALGORITMI RANDOMIZZATI
cod. NF22500059
INTRODUZIONE AGLI ALGORITMI RANDOMIZZATI
| NF22500059 | |
| DIPARTIMENTO DI INFORMATICA | |
| CORSO DI LAUREA MAGISTRALE | |
| INFORMATICA | |
| 2025/2026 |
| ANNO CORSO 1 | |
| ANNO ORDINAMENTO 2025 | |
| PRIMO SEMESTRE |
| SSD | CFU | ORE | ATTIVITÀ | |
|---|---|---|---|---|
| INF/01 | 6 | 48 | LEZIONE |
| Obiettivi | |
|---|---|
| OBIETTIVO GENERALE FORNIRE UNA COMPRENSIONE CRITICA DEI PRINCIPI TEORICI E PRATICI DEGLI ALGORITMI RANDOMIZZATI, NECESSARI PER PROGETTARLI, ANALIZZARLI E APPLICARLI IN CONTESTI COMPUTAZIONALI COMPLESSI. IL CORSO INTEGRA STRUMENTI PROBABILISTICI CON TECNICHE DI ANALISI AVANZATE, CONCENTRANDOSI SUGLI ALGORITMI DI LAS VEGAS E MONTE CARLO E SULLE LORO APPLICAZIONI. CONOSCENZA E CAPACITÀ DI COMPRENSIONE FONDAMENTI DI PROBABILITÀ DISCRETA: VARIABILI CASUALI, DISTRIBUZIONI (BERNOULLI, BINOMIALE, GEOMETRICA, POISSON), VALORE ATTESO, VARIANZA. - TECNICHE DI ANALISI PROBABILISTICA: DISUGUAGLIANZE DI CONCENTRAZIONE (MARKOV, CHEBYSHEV, CHERNOFF), LIMITI DI CODA. - ALGORITMI DI LAS VEGAS E MONTE CARLO. - METODO PROBABILISTICO E DERANDOMIZZAZIONE. - VALUTAZIONE DEI COMPROMESSI TRA CORRETTEZZA, EFFICIENZA E PROBABILITÀ DI ERRORE CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE LO STUDENTE ACQUISIRÀ LA CAPACITÀ DI - PROGETTARE E ANALIZZARE ALGORITMI RANDOMIZZATI. - APPLICARE DISUGUAGLIANZE DI CONCENTRAZIONE PER ANALIZZARE PRESTAZIONI E AFFIDABILITÀ. - IMPLEMENTARE ALGORITMI PER PROBLEMI CONCRETI. - CONFRONTARE SOLUZIONI RANDOMIZZATE CON APPROCCI DETERMINISTICI. AUTONOMIA DI GIUDIZIO LO STUDENTE SARÀ IN GRADO DI: - VALUTARE L'APPROPRIATEZZA DELLA RANDOMIZZAZIONE IN CONTESTI COMPUTAZIONALI. - STIMARE I COMPROMESSI TRA RISORSE COMPUTAZIONALI, PRECISIONE E AFFIDABILITÀ. - ANALIZZARE I RISULTATI TEORICI E SPERIMENTALI PRESENTI IN LETTERATURA. ABILITÀ COMUNICATIVE LO STUDENTE SARÀ IN GRADO DI: - DISCUTERE PROPRIETÀ E APPLICAZIONI DEGLI ALGORITMI RANDOMIZZATI. - PRESENTARE SOLUZIONI ALGORITMICHE CON CHIAREZZA E RIGORE. CAPACITÀ DI APPRENDIMENTO LO STUDENTE SARÀ IN GRADO DI: - APPROFONDIRE ARGOMENTI AVANZATI ATTRAVERSO LA LETTERATURA SCIENTIFICA. - USE ONLINE RESOURCES FOR UPDATES. - APPLY PROBABILISTIC CONCEPTS IN INTERDISCIPLINARY CONTEXTS |
| Prerequisiti | |
|---|---|
| CONOSCENZE DI MATEMATICA DISCRETA, ALGEBRA LINEARE, TEORIA DELLA PROBABILITÀ E ALGORITMI (LAUREA TRIENNALE IN INFORMATICA). |
| Contenuti | |
|---|---|
| PARTE I: FONDAMENTI DI PROBABILITÀ (12 ORE) - RICHIAMI MATEMATICI (2H): SERIE, COMBINATORIA, NOTAZIONE ASINTOTICA. - PROBABILITÀ SU EVENTI (4H): SPAZIO CAMPIONARIO, PROBABILITÀ CONDIZIONATA, INDIPENDENZA, LEGGE DELLA PROBABILITÀ TOTALE, TEOREMA DI BAYES. - VARIABILI ALEATORIE DISCRETE (6H): DISTRIBUZIONI COMUNI, VALORE ATTESO, VARIANZA. PARTE II: ANALISI DEI LIMITI DI CODA E APPLICAZIONI (14 ORE) - DISUGUAGLIANZE DI CONCENTRAZIONE (8H): MARKOV, CHEBYSHEV, CHERNOFF. - APPLICAZIONI (6H): MODELLI "BALLS AND BINS", HASHING. PARTE III: ALGORITMI RANDOMIZZATI (22 ORE) - ALGORITMI LAS VEGAS (8H). - ALGORITMI MONTE CARLO (8H). - ANALISI DELLA COMPLESSITÀ ATTESA E DERANDOMIZZAZIONE (6H). |
| Metodi Didattici | |
|---|---|
| - LEZIONI TEORICHE CON ESEMPI E CASI DI STUDIO. - ESERCITAZIONI PRATICHE CON IMPLEMENTAZIONI. - DISCUSSIONE DI ARTICOLI SCIENTIFICI. |
| Verifica dell'apprendimento | |
|---|---|
| PROVA SCRITTA (50%): VALUTA L’ABILITÀ DI APPLICARE NOZIONI TEORICHE ALLA RISOLUZIONE DI PROBLEMI, COME: PROGETTAZIONE E ANALISI DI ALGORITMI RANDOMIZZATI, APPLICAZIONE DI DISUGUAGLIANZE DI CONCENTRAZIONE (ES. CHERNOFF), ANALISI DI SCENARI DI HASHING O MODELLI "BALLS AND BINS". PROVA ORALE (50%): VERIFICA LA PREPARAZIONE TEORICA SU TEMI QUALI: DIFFERENZE TRA ALGORITMI LAS VEGAS/MONTE CARLO, DIMOSTRAZIONI INTUITIVE DI DISUGUAGLIANZE, APPLICAZIONI AVANZATE (ES. TEST DI PRIMALITÀ), COLLEGAMENTI TRA TEMI DEL CORSO. VALUTAZIONE FINALE: VOTO IN TRENTESIMI (50% SCRITTO + 50% ORALE). PER OTTENERE LA LODE, È NECESSARIA UNA PADRONANZA INTERDISCIPLINARE E LA CAPACITÀ DI APPLICARE AUTONOMAMENTE LE CONOSCENZE ACQUISITE, ANCHE IN CONTESTI PRATICI NON AFFRONTATI DURANTE LE LEZIONI. |
| Testi | |
|---|---|
| TESTO PRINCIPALE: MOR HARCHOL-BALTER, "INTRODUCTION TO PROBABILITY FOR COMPUTING", CAMBRIDGE UNIVERSITY PRESS, 2024. APPROFONDIMENTI: - MICHAEL MITZENMACHER E ELI UPFAL, "PROBABILITY AND COMPUTING". - RAJEEV MOTWANI E PRABHAKAR RAGHAVAN, "RANDOMIZED ALGORITHMS". |
| Altre Informazioni | |
|---|---|
| MATERIALE DIDATTICO SUPPLEMENTARE FORNITO DAL DOCENTE E DISPONIBILE ONLINE. |
BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2025-08-21]
