Progettazione di Algoritmi a.a. 2024-2025

Diario delle lezioni e delle esercitazioni

NOTA: le lezioni NON verranno registrate, ma trovate qui il dettaglio degli argomenti svolti ed il link al pdf delle slides utilizzate.

Settimana 1 - 27 Febbraio

Presentazione del corso. Richiami di concetti fondamentali appresi ad introduzione agli algoritmi. Algoritmi efficienti, complessità polinomiale, superpolinomiale: esponenziale, superesponenziale e subesponenziale. ESERCIZIO: Progettare un algoritmo che verifichi se in un array di n interi esiste o meno un intero che compare in maggioranza assoluta. L'algoritmo deve avere complessità O(n). lez01A2Introduzione25.pdf

Settimana 1 - 28 Febbraio

): I grafi, vertici e archi, grafi diretti e non diretti, relazione tra il numero n di nodi e il numero m di archi. Grafi sparsi e grafi densi. Esempi di grafi sparsi: alberi e grafi planari. Rappresentazione di grafi tramite matrice di adiacenza e trazmite liste di adiacenza.ESERCIZIO risolvere il problema del pozzo universale in tempo O(n) avendo il grafo diretto rappresentato tramite matrice di adiacenza. Lez02A2Grafi1.pdf

Settimana 2 - 3 Marzo

Visita in profondità (DFS) in tempo O(n^2), rappresentazione di grafi tramite liste di adiacenza e visita in profondità in O(n+m). Albero DFS e sua costruzione mediante visita. Ottenere il cammino dalla radice dell'albero DFS ad un nodo raggiungibile in tempo O(n).ESERCIZIO: Dimostrare che in ogni grafo di almeno due nodi sono presenti almeno due nodi con lo stesso numero di vicini. Lez03A2Grafi2.pdf

Settimana 2 - 6 Marzo

Colorazione di grafi. Algoritmi per la ricerca delle componenti connesse in O(n+m) e algoritmo per la ricerca delle componenti fortemente connesse. Lez04A2Grafi3.pdf

Settimana 2 - 7 Marzo

Ordinamento topologico. Condizioni necessaria perchè esista un sort topologico, Algoritmo "delle sorgenti" per la ricerca di un sort topologico, correttezza e complessità.

Algoritmo basato sulla visita DFS per la ricerca di un sort topologico, correttezza e complessità. Lez05A2OrdinamentoTopologico25.pdf

Settimana 3 - 10 Marzo

Ricerca di cicli in grafi non diretti in tempo O(n) e in grafi diretti in tempo O(n+m) . Archi all'indietro, in avanti e di attraversamento durante le visite DFS in grafi diretti. Lez06A2GrafiCicli25.pdf

Settimana 3 - 13 Marzo

Il problema di determinare i ponti di un grafo: algoritmo per determinare se l'arco (a,b) è un ponte, algoritmo esaustivo che verifica tutti gli archi di complessita' O(m^2), algoritmo che verifica i soli archi dell'albero DFS di complessità O(nm). Algoritmo con un'unica visita DFS di complessita' O(n+m). Lez07A2grafiPonti25.pdf

Settimana 3 - 14 Marzo

Visita di grafi in ampiezza (BFS) e sua Implementazione in O(n+m). Generazione dell'albero BFS e prova che produce cammini minimi. Vettore delle distanze. Lez08A2grafiBFS25.pdf

Settimana 4 - 17 Marzo

Grafi pesati e loro rappresentazione. Algoritmo di Dijkstra per la ricerca di cammini minimi in grafi pesati con pesi positivi. Correttezza e implementazioni:

a) implementazione di costo O(n^2), ottima per grafi densi

b) implementazione di costo O((n + m) log n) tramite heap, adatta a grafi sparsi.

Lez09A2grafiPesati25.pdf

Settimana 4 - 20 Marzo

Alberi di copertura. L'algoritmo di Kruskal,per la ricerca dell'albero di copertura di costo minimo, prova di correttezza e implementazione con complessità O(nm). Lez10A2SpanningTree25.pdf

Settimana 4 - 21 Marzo

ESERCIZI TRACCEesercizi.pdf

Settimana 5 - 24 Marzo

La struttura dati Union-Find. Due implementazioni:

1) Union in O(n) e Find in O(1).

2) Union in O(1) e Find in O(log n).

Lez10aA2UnionFind25.pdf

Implementazione dell'algoritmo di Kruskal per la ricerca del minimo albero di copertura in tempo O(mlog n).

Settimana 5 - 27 Marzo

algoritmo di Bellman-Ford per la ricerca dei cammini di costo minimo in grafi con archi con pesi anche negativi. Lez11A2CamminiPesiNegativi25.pdf

Settimana 5 - 28 Marzo

esercizi su grafi. Lez11bA2esercizi.pdf

Settimana 6 - 31 Marzo

Problemi di ottimizzazione. Euristiche ed algoritmi di approssimazione. Rapporto di approssimazione per problemi di minimizzazione e per problemi di massimizzazione. Il problema della copertura tramite vertici: un algoritmo di approssimazione che non ha rapporto di approssimazione costante ed un algoritmo di approssimazione di tempo O(n+m) con rapporto d'approssimazione limitato da 2. Lez12A2Approssimazione25.pdf

Settimana 6 - 3 Aprile

ESONERO 1

Settimana 6 - 4 Aprile

Introduzione alla tecnica greedy. Il problema della selezione di attività algoritmo, prova di correttezza e sua implementazione in O(nlog n). Il problema dell'assegnazione di attività, algoritmo, prova di correttezza e sua implementazione in O(nlog n). Lez13A2greedy25.pdf

Settimana 7 - 7 Aprile

sospensione della didattica per commemorazione di Ilaria Sula.

Settimana 7 - 10 Aprile

(prof. Salvo (1)): revisione esonero, sbarramenti, esercizio 1, pseudocodice dettagliato DFS modificata soluzione esercizio 2.
Per rinfrancare lo spirito dopo l'esonero, una perla di progettazione di Algoritmi in salsa greedy/game theory: il problema dei Matrimoni Stabili.

Settimana 7 - 11 Aprile

esercizi sulla tecnica greedy e sui problemi d'approssimazione Lez13bA2EserciziGreedy.pdf

Settimana 8 - 14 Aprile

La tecnica del divide et impera. Il problema della selezione: dato un vettore A di interi distinti ed un intero k, con 1<=k<len(A), vogliamo trovare l'elemento di rango k (vale a dire l'elemento che si troverebbe al k-mo posto nel vettore A ordinato). Algoritmo banale di tempo O(nlog n). Algoritmo basato sulla tecnica del divide et impera randomizzato con tempo medio O(n) e caso pessimo O(n^2). Algoritmo ottimo che richiede Θ(n). Lez14A2DivideEtImpera1.pdf

Settimana 8 - 17 Aprile

Vacanze di Pasqua

Settimana 8 - 18 Aprile

Vacanze di Pasqua

Settimana 9 - 21 Aprile

Lunedì dell'Angelo

Settimana 9 - 24 Aprile

Introduzione alla programmazione dinamica.

Esempio 1: numeri di fibonacci e overlapping di sottoproblemi. Progettare un algoritmo Θ(n) basato sulla tecnica della programmazione dinamica prima top-down con memoizzazione e poi bottom up infine ottenere un algoritmo che utilizza spazio di lavoro Θ(n).

Esempio 2: dato una lista di file con le loro dimensioni e un hard disk di capacità C determinare il massimo spazio dell'hard disk che è possibile occupare. Progettare un algoritmo basato sulla programmazione dinamica di tempo Θ(nC). Algoritmi pseudopolinomiali.

Lez16A2ProgrammazioneD125.pdf

Primi esercizi: Lez17A2PD2a25.pdf

Settimana 9 - 25 Aprile

Festa della Liberazione

Settimana 10 - 28 Aprile

Esercizi sulla programmazione dinamica risolvibili con tabelle unidimensionali. Lez17A2PD2b25.pdf

Settimana 10 - 1 Maggio

Festa dei Lavoratori

Settimana 10 - 2 Maggio

ponte del primo maggio

Settimana 11 - 5 Maggio

(prof. Salvo (2)): Esercizio 5.6 (Divide et Impera): segmento più lungo di spessore al più C. Potete consultare i codici commentati oppure le slides.

Esercizio su Greedy: massimo insieme indipendente in un albero.

Settimana 11 - 8 Maggio

Esercizi sulla programmazione dinamica risolvibili con tabelle biidimensionali Lez18A2PD3a25.pdf

Settimana 11 - 9 Maggio

(prof. Salvo (3)): Esercizio 5.10 (Divide et Impera): ricerca binaria non sapendo il limite destro dello spazio di ricerca ( Slides).

Esercizio 6.18 (Programmazione Dinamica): supersequenza di lunghezza minima di due sequenze. Codici commentati delle versioni top-down, topdown con tabella, bottom-up e ricostruzione della soluzione dalla tabella.

Settimana 12 - 12 Maggio

Introduzione al backtracking: generare tutte le stringhe binarie lunghe n in tempo ottimo Θ(n2^n). Algoritmo esaustivo di complessità Θ(n2^n) che stampa tutte le stringhe di lunghezza n con esattamente c uni. Funzioni di taglio e algoritmo ottimo di tempo Θ(nS(n,c)) per generare tutte le stringhe binarie lunghe n contenenti esattamente c uni. Dove S(n,c) è il numero di stringhe esistenti che hanno lunghezza n ed esattamente c uni.

ESERCIZI sulla generazione di stringhe lunghe n con particolari vincoli da risolvere con algoritmi la cui complessità deve essere proporzionale al numero di stringhe da generare.

Lez19A2BT1.pdf

Settimana 12 - 15 Maggio

backtracking e generazione di matrici o permutazioni Lez20A2BT2.pdf

Settimana 12 - 16 Maggio

Soluzione esercizi dell'esonero 2024 SoluzioniSecondoEsonero.pdf

Esercizi:

1) Progettare un algoritmo di programmazione dinamica che, dato un intero n, in tempo $O(n)$, calcoli il numero di stringhe sull'alfabeto {0,1,2,3 } in cui non compaiono mai due cifre pari adiacenti.

2) Progettare un algoritmo di programmazione dinamica che, data una sequenza A di n interi positivi ed un intero k, in tempo O(nk), calcoli il numero di sottosequenze di A la somma dei cui elementi sia k.

Settimana 13 - 19 Maggio

Esempi di applicazioni del backtracking per la souzione di problemi di ricerca o ottimizzazione come il problema dello zaino o il problema della ricerca di un eventuale ciclo hamiltoniano in un grafo. Lez21A2BT3_.pdf

Settimana 13 - 22 Maggio

ESERCIZI:

1)Progettare un algoritmo che, dato n, in tempo O(n) calcoli il numero di modi che ci sono per risalire una scala con n pioli tenendo conto che per ciascuno step si puo' risalire di 1, 2 o 3 pioli.

Ad esempio per n=4 la risposta deve essere 7. Ecco di seguito i diversi modi di procedere: (1111), (112), (121), (112), (22), (13),(31)

2) Progettare un algoritmo che, date due stringhe X e Y ciascuna di n caratteri, in tempo O(n^2), restituisca la lunghezza massima tra quelle delle sottosequenze comuni ad X e Y.

Ad esempio per X='abzcdcd' e Y='baccbdz' la risposta deve essere 4 (la sottosequenza comune piu' lunga è 'accd')

3) data una matrice quadrata di lato n contenente interi non negativi a partire dalla cella (0,0) dobbiamo raggiungere la cella (n-1,n-1) e ad ogni step possiamo muoverci nella cella adiacente a destra o nella cella adiacente in basso. Il costo del cammino è dato dalla somma dei contenuti delle celle toccate.

Progettare un algoritmo che, data la matrice M ed un intero k, in tempo O(n^2) restituisce True se esiste un cammino di costo esattaqmente k, False altrimenti

4) Abbiamo una scacchiera di lato n>4, con un cavallo posizionato nella cella (o,o) bisogna trovare un cammino del cavallo che lo porti a toccare tutte le n^2 celle una ed una sola volta. Gli spostamenti possibili tra celle consecutive del cammino sono quelli possibili in base alle regole di spostamento del cavallo. Progettare un algoritmo di backtracking che dato n restituisca un possibile cammino.

Settimana 13 - 23 Maggio

(prof. Salvo (4)):

• (1) A gentile richiesta: Programmazione Dinamica (Es. 6.6): scomposizione di una stringa in sottostringhe primarie ( codice Python commentato)
• (2) backTrack (Es. 7.10): costruzione di quadrati magici di ordine n ( codice Python commentato)
• Versione alternativa basata sulla determinazione delle n tuple di sequenze magiche compatibili ( codice Python commentato) (per gli appassionati di sequenze di naturali, vedere quanti quadrati magici ci sono di ordine 5 (6 nessuno lo sa!), oppure quante sequenze magiche);

Settimana 14 - 28 Maggio

secondo esonero in aula cabibbo dalle 16 alle 19