PRESENTAZIONE

Nella prima parte si illustra come analizzare gli algoritmi 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 della 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 classici.

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.

Gli studenti con certificazioni valide per Disturbi Specifici dell’Apprendimento (DSA), per disabilità o altri bisogni educativi sono invitati a contattare il docente e il referente di Scuola per la disabilità all’inizio dell’insegnamento per concordare eventuali modalità didattiche che, nel rispetto degli obiettivi dell’insegnamento, tengano conto delle modalità di apprendimento individuali. 

I contatti del referente di Scuola per la disabilità sono disponibili al seguente link https://unige.it/commissioni/comitatoperlinclusionedeglistudenticondisabilita. 

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. 
• Tecniche di programmazione dinamica e tecniche golose.
• Algoritmi su grafi: visite, ordinamento topologico, componenti fortemente connesse, alberi di ricoprimento minimi, cammini minimi.
• Cenni di teoria della NP-completezza

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 dei docenti.

Per approfondimenti:

• Cormen, Leiserson, Rivest, Stein, 2005, Introduzione agli algoritmi e strutture dati (Seconda edizione), McGraw Hill. (o meglio Terza edizione, in lingua inglese)
   

DOCENTI E COMMISSIONI

Commissione d'esame

ENRICO PUPPO (Presidente)

PAOLA MAGILLO

ALESSANDRO VERRI (Presidente Supplente)

ELENA ZUCCA SCHILLANI (Supplente)

LEZIONI

INIZIO LEZIONI

In accordo con il calendario didattico approvato dal Consiglio dei Corsi di Studio in Informatica: https://easyacademy.unige.it/portalestudenti/index.php?view=easycourse&_lang=it&include=corso

Orari delle lezioni

L'orario di questo insegnamento è consultabile all'indirizzo: Portale EasyAcademy

ESAMI

MODALITA' D'ESAME

Test a quiz e prova orale.

Il test ha il solo scopo di ammissione alla prova orale: sono ammessi gli studenti che superano una soglia minima di risposte esatte.

Indicazioni per studenti con certificazione di DSA, di disabilità o di altri bisogni educativi speciali sono disponibili a partire da https://corsi.unige.it/corsi/8759/studenti-disabilita-dsa
 

MODALITA' DI ACCERTAMENTO

La prova orale verifica la comprensione dei concetti, la capacità di illustrarli in modo appropriato e di mettere in pratica le tecniche viste a lezione.

ALTRE INFORMAZIONI

Per ulteriori informazioni, consultare il modulo Aulaweb dell'insegnamento o contattare il docente.

Gli studenti con certificazioni valide per Disturbi Specifici dell’Apprendimento (DSA) possono richiedere adattamenti in sede d'esame, con almeno 7 giorni di anticipo rispetto alla data dell’esame, compilando il "modulo richieste adattamenti" (dai servizi online https://modulionline.unige.it/richiesta-adattamenti#no-back) che verrà inviato in automatico dal sistema al/alla docente responsabile dell’insegnamento e al/alla docente referente per gli studenti con disabilità e con DSA della propria Scuola/Area.  

Lo studente riceverà una copia della sua richiesta.