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

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.