Corso di Progettazione di Algoritmi

Docente: Annalisa De Bonis

matricole congrue ad uno

a.a. 2020-21

Orario delle lezioni

• Lunedì: 11-13
• Mercoledì: 11-13
• Giovedì: 11-13

Orario di ricevimento

• Durante tutto il periodo in cui la didattica sarà svolta nella modalità a distanza, gli studenti potranno contattare la docente via email per l'attività di ricevimento, attività che potrà eventualmente essere espletata nel corso di un meeting su Teams da concordarsi sempre via email.

Libri di testo

• KLEINBERG, TARDOS. ALGORITHM DESIGN. PEARSON ADDISON WESLEY.
• S. DASGUPTA, C. H. PAPADIMITRIOU, AND U. V. VAZIRANI. ALGORITHMS. MCGRAW-HILL

Altri testi utili

• CORMEN, LEISERSON, RIVEST, STEIN. INTRODUCTION TO ALGORITHMS. THE MIT PRESS, MCGRAW-HILL BOOK COMPANY.

Prove in itinere

• Risultati della prima prova in itinere

Slide delle lezioni

• Introduzione al corso
• Efficienza degli algoritmi e analisi asintotica degli algoritmi (I parte)
• Efficienza degli algoritmi e analisi asintotica degli algoritmi (II parte)
• Grafi (Definizioni di grafo e di albero, alcune semplici proprietà dei grafi e degli alberi, visita BFS,visita DFS) (il 18 marzo sono state aggiunte le slide su DFS)
• Grafi (Componenti connesse, Grafi bipartiti.)
• Grafi (Connetività forte di grafi direzionati, Ordinamento topologico di un DAG, Esercizi )
• Algoritmi greedy (Interval scheduling, Partizionamento di Intervalli)
• Algoritmi greedy (Minimizzazione dei ritardi)
• Algoritmi greedy (Caching offline, Cammini minimi)
• Algoritmi greedy (Minimo Albero Ricoprente: algoritmo di Prim e algoritmo di Kruskal)
• Algoritmi greedy (Minimo Albero Ricoprente: Correttezza algoritmi per MST senza il vincolo sui costi, k-clustering)
• Divide et impera (Merge Sort, Ricerca Binaria, Relazioni di ricorrenza derivanti dall'analisi di algoritmi basati su Divide et Impera)
• Divide et impera (QuickSort, QuickSelect)
• Divide et impera (Sottosequenza di somma massima)
• Divide et impera (Il problema della coppia più vicina e moltiplicazione veloce di interi)
• Divide et impera (Stime asintotiche quando il tempo di ricombinazione e decomposizione è polinomiale, Divide et Impera su alberi)
• Programmazione dinamica (Interval Scheduling pesato)
• Programmazione dinamica (Segmented Least Squares, Subset Sums)
• Programmazione dinamica (Problema dello zaino, I lezione sui cammini minimi)
• Programmazione dinamica (II lezione sui cammini minimi, coin change problem , sottosequenza comune piu` lunga)
• Programmazione dinamica (Allineamento di sequenze, Sottosequenza crescente più lunga, Parentesizzazione ottima)
• Problemi difficili e ricerca esaustiva intelligente.

Qui trovate le informazioni necessarie per partecipare agli esami a distanza di Progettazione di Algoritmi a.a. 2020-21.

Appelli

• Risultati della prova del 3 novembre 2021

Avvisi:

• 3 giugno 2021. A partire dall'appello di giugno 2021 tutti gli studenti che hanno nel piano di studio l'esame di PA da 9 CFU devono portare il nuovo programma di PA aggiornato all'anno accademico 2020-21 (sostanzialmente identico a quello 2019-20). Gli studenti che devono sostenere l'esame da 6 CFU potranno portare il vecchio programma (a.a. 2018-19) ma la prova scritta potrebbe non contenere quesiti relativi alla parte sul flusso e, in sostituzione di questi, contenere domande aggiuntive sugli altri argomenti. Si invitano gli studenti con PA da 6 CFU che intendono portare il vecchio programma a prendere attentamente visione del programma 2018-19. Gli studenti con PA da 6 CFU che intendono invece portare il nuovo programma devono inviare una email alla docente con oggetto "SOSTENIMENTO APPELLO data_appello CON NUOVO PROGRAMMA DA 6 CFU".
• 2 giugno 2021. La settimana prossima si terrà l'ultima lezione di tutorato.
• 6 maggio 2021. Calendario per vedere le correzioni agli elaborati della I prova intercorso
• 30 aprile 2021. A partire da mercoledì 5 maggio le lezioni si svolgerano in modalità mista: parte degli studenti seguiranno in presenza e parte a distanza. Le persone interessate a partecipare alle lezioni in presenza possono trovare qui le informazioni per prenotarsi alle lezioni e accedere al campus e qui quelle relative al protocollo di sicurezza adottato dall'Universita di Salerno in materia di prevenzione del COVID-19.
• 22 aprile 2021. Come suggerito ieri dagli studenti che parteciperanno alla prova intercorso, oggi non ci sarà lezione.
• 20 aprile 2021. Gli studenti che parteciperanno alla I prova intercorso sono pregati di leggere con estrema attenzione il file con le istruzioni per la partecipazione all'esame scritto a distanza. Come piu` volte ricordato, gli studenti devono fare delle prove al fine di accertarsi di riuscire a sddisfare i requisiti richiesti e in caso di problemi contattare immediatamente la docente via mail. Il giorno della prova non sarà possibile dedicare tempo alla soluzione di questi problemi per cui gli studenti che non sono in grado di svolgere la prova nel modo indicato saranno rimossi dal meeting.
• Gli studenti che si sono prenotati alla I prova in itinere e che non hanno piu` intenzione di partecipare alla prova, sono pregati di mandare una mail ad adebonis@unisa.it con oggetto "Cancellazione prenotazione I prova in itinere".