Salta al contenuto principale
CODICE 80306
ANNO ACCADEMICO 2025/2026
CFU
SETTORE SCIENTIFICO DISCIPLINARE INF/01
LINGUA Italiano
SEDE
  • GENOVA
PERIODO 2° Semestre
PROPEDEUTICITA
Propedeuticità in ingresso
Per sostenere l'esame di questo insegnamento è necessario aver sostenuto i seguenti esami:
MATERIALE DIDATTICO AULAWEB

PRESENTAZIONE

Nella prima oarte si illustra come analizzare gli algorimi dal punto di vista di
correttezza ed efficienza, e si  presentano alcuni algoritmi classici nella formazione
di un informatico, assumendo dal corso di Algoritmi e Strutture Dati le
nozioni base relative a complessità e strutture dati elementari. Nella seconda parte si illustra come applicare nozioni fondamentali dalla teoria della probabilità nell’analisi di algoritmi randomizzati e come valutare i benefici della randomizzazione nella progettazione di algoritmi.

 

OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

Apprendere algoritmi e schemi algoritmici classici imparando ad analizzare correttezza ed efficienza di un algoritmo. Apprezzare le potenzialità della randomizzazione nella progettazione di algoritmi attraverso semplici esempi.

OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO

Al termine dell'insegnamento lo studente/la studentessa sarà in grado di:

Conoscere algoritmi e schemi algoritmici classic.

Analizzare correttezza ed efficienza di un algoritmo.

Apprezzare le potenzialità della randomizzazione nella progettazione di algoritmi attraverso semplici esempi.

PREREQUISITI

Nozioni base su algoritmi e strutture dati.

MODALITA' DIDATTICHE

Lezioni frontali.

PROGRAMMA/CONTENUTO

Prima parte: Complessità di algoritmi e di problemi. Principio di induzione, correttezza e complessità di algoritmi ricorsivi. Correttezza di algoritmi iterativi con invariante di ciclo. Grafi: algoritmi di Dijkstra, Prim e Kruskal, algoritmi per ordinamento topologico e componenti fortemente connesse. Programmazione dinamica. Teoria della NP-completezza: classe NP, riduzione polinomiale, classe NP-C, P=NP.

Seconda parte: Algoritmi randomizzati di tipo Las Vegas e Montecarlo: algoritmi di ordinamento, taglio minimo, albero di un gioco, tolleranza a guasti bizantini, test di primalità e programmazione lineare. Cenni a teoria dei giochi e a problemi di occupazione.

TESTI/BIBLIOGRAFIA

Note a cura del docente.
 

DOCENTI E COMMISSIONI

LEZIONI

INIZIO LEZIONI

In accordo con il calendario didattico approvato dal Consiglio dei Corsi di Studio in Informatica

ESAMI

MODALITA' D'ESAME

Prova scritta e orale.

MODALITA' DI ACCERTAMENTO

La prova scritta verifica la capacità dello studente di mettere in pratica le nozioni viste a lezione. La prova orale verifica la comprensione dei concetti e la capacità di illustrarli in modo appropriato.