Salta al contenuto principale
CODICE 80306
ANNO ACCADEMICO 2023/2024
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

Nel primo modulo 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. Nel secondo modulo 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

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.

PREREQUISITI

Nozioni base su algoritmi e strutture dati.

MODALITA' DIDATTICHE

Lezioni frontali.

PROGRAMMA/CONTENUTO

Primo modulo: 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.

Secondo modulo: 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

Commissione d'esame

ELENA ZUCCA SCHILLANI (Presidente)

PAOLA MAGILLO

ALESSANDRO VERRI (Presidente Supplente)

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.

Calendario appelli

Dati Ora Luogo Tipologia Note
18/01/2024 09:00 GENOVA Scritto
01/02/2024 09:00 GENOVA Scritto
17/06/2024 09:00 GENOVA Scritto
04/07/2024 09:00 GENOVA Scritto
04/09/2024 09:00 GENOVA Scritto
16/01/2025 09:00 GENOVA Scritto
30/01/2025 09:00 GENOVA Scritto