ALGORITMI AVANZATI

Informatica ALGORITMI AVANZATI

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



ANNO ORDINAMENTO 2016
PRIMO SEMESTRE
CFUOREATTIVITÀ
756LEZIONE
216LABORATORIO
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. (12 ORE)
2.TECNICHE PER AFFRONTARE PROBLEMI DIFFICILI: RICERCA ESAUSTIVA INTELLIGENTE: BACKTRACKING E BRANCH-AND-BOUND E ALTER TECNICHE. (12 ORE)
3.ALGORITMI APPROSSIMATI: ALGORITMI APPROSSIMATI PER VERTEXCOVER, LOAD BALANCING, PROBLEMA DEI CENTRI, PROBLEMA DELLO ZAINO. (12 ORE)
4.ALGORITMI RANDOMIZZATI: ALGORITMI RANDOMIZZATI PER IL QUICKSORT, TAGLIO MINIMO GLOBALE, MAX-3SAT. (12 ORE)
5.ALGORITMI ONLINE: ALGORITMI ONLINE PER IL PAGING, PER L’ORDINAMENTO DI LISTE, PER IL LOAD BALANCING PER IL BIN PACKING. ANALISI PROBABILISTICA. (12 ORE)
6.ALGORITMI DISTRIBUITI: PROBLEMA DEL CONSENSO, IMPOSSIBILITÀ E ALGORITMI PER VARI MODELLI SINCRONI, ASINCRONI, CON GUASTI STOP E GUASTI BIZANTINI, REGISTRI DISTRIBUITI, BLOCKCHAIN. (12 ORE)
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-08-05]