2. Docenti
  3. DE PRISCO Roberto
  4. Didattica

ALGORITMI AVANZATI

Roberto DE PRISCO ALGORITMI AVANZATI

0522500064
DIPARTIMENTO DI INFORMATICA
CORSO DI LAUREA MAGISTRALE
INFORMATICA
2021/2022



ANNO CORSO 2
ANNO ORDINAMENTO 2016
PRIMO SEMESTRE
CFUOREATTIVITÀ
216LABORATORIO
756LEZIONE
ROBERTO DE PRISCO T Curriculum
Obiettivi
L’INSEGNAMENTO INTENDE FORNIRE AGLI STUDENTI GLI STRUMENTI NECESSARI PER UNA CONOSCENZA AVANZATA DEGLI ALGORITMI CHE PERMETTA DI GIUNGERE ALLA CAPACITÀ DI AFFRONTARE PROBLEMI REALI E RISOLVERLI NEL MIGLIOR MODO POSSIBILE.
CONOSCENZE E COMPRENSIONE
LO STUDENTE AVRÀ CONOSCENZA DELLE VARIE TIPOLOGIE DI ALGORITMI AVANZATI CHE VANNO AL DI LÀ DELLE CONOSCENZE DEGLI ALGORITMI DI BASE; IN PARTICOLARE SI INTENDE FORNIRE ALLO STUDENTE CONOSCENZE DI BASE RELATIVE A ALGORITMI APPROSSIMATI, RANDOMIZZATI, ONLINE E DISTRIBUITI.
CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE
LO STUDENTE SARÀ IN GRADO DI APPLICARE LE METODOLOGIE APPRESE A PROBLEMI REALI CON SPIRITO CRITICO E IN MODO SINERGICO.
Prerequisiti
È NECESSARIO CHE SI SIANO PREVENTIVAMENTE ACQUISITE CONOSCENZE RELATIVE A STRUTTURE DATI, ALGORITMI DI BASE, MATEMATICA DI BASE, TEORIA DELLA PROBABILITÀ. CONOSCENZE DI CRITTOGRAFIA SONO UTILI PER LA PARTE SUI SISTEMI DISTRIBUITI.
Contenuti
IL CORSO È DIVISO IN 6 PARTI IN OGNUNA DELLE QUALI SI FORNIRÀ UNA INTRODUZIONE AI SEGUENTI ARGOMENTI.
1.PROBLEMI DIFFICILI E CLASSI P E NP: RIDUZIONI, INDEPENDET SET, VERTEX COVER, SET COVER, SET PACKING, SAT, 3SAT, PROBLEMI NP-HARD, PSPACE.
2.TECNICHE PER AFFRONTARE PROBLEMI DIFFICILI: RICERCA ESAUSTIVA INTELLIGENTE: BACKTRACKING E BRANCH-AND-BOUND E ALTER TECNICHE.
3.ALGORITMI APPROSSIMATI: ALGORITMI APPROSSIMATI PER VERTEXCOVER, LOAD BALANCING, PROBLEMA DEI CENTRI, PROBLEMA DELLO ZAINO.
4.ALGORITMI RANDOMIZZATI: ALGORITMI RANDOMIZZATI PER IL QUICKSORT, TAGLIO MINIMO GLOBALE, MAX-3SAT.
5.ALGORITMI ONLINE: ALGORITMI ONLINE PER IL PAGING, PER L’ORDINAMENTO DI LISTE, PER IL LOAD BALANCING PER IL BIN PACKING. ANALISI PROBABILISTICA.
6.ALGORITMI DISTRIBUITI: PROBLEMA DEL CONSENSO, IMPOSSIBILITÀ E ALGORITMI PER VARI MODELLI SINCRONI, ASINCRONI, CON GUASTI STOP E GUASTI BIZANTINI, REGISTRI DISTRIBUITI, BLOCKCHAIN.
Metodi Didattici
72 ORE DI LEZIONE FRONTALE.
Verifica dell'apprendimento
L’ESAME CONSISTE IN UNA PROVA SCRITTA E DI UNA OPZIONALE, A DISCREZIONE DEL DOCENTE, PROVA ORALE
Testi
"ALGORITHM DESIGN", KLEINBERG, TARDOS. EDITORE: PEARSON
“DISTRIBUTED ALGORITHMS”, NANCY LYNCH. EDITORE: MORGAN KAUFFMAN
  BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2022-11-21]