ORARIO RICEVIMENTO (Dott.ssa Rosalba Zizza):     martedi 14-17:30

DISPENSA ESERCIZI PROGRAMMAZIONE DINAMICA
LISTA ESERCIZI E SOLUZIONI DI P.D.
LISTA ESERCIZI E SOLUZIONI DI MATRODI

FAQ (risposte a domande formulate per e-mail... se e quando verranno formulate!)
 Prima lezione (Lunedi 19.11.2001, ore 16:30, aula U3-04)
Riferimento al testo:

• Riepilogo argomenti trattai nella prima parte del corso, alla luce di quanto sara' fatto in questa seconda parte (concetto di ricorsione, metodo divide-et-impera).

• Introduzione alla Programmazione dinamica. Concetti di base. Cosa e' un problema di ottimizzazione. Uso della ricorsione. Esempio del calcolo dei numeri di Fibonacci. Differenze tra programmazione dinamica e classica ricorsione. Astrazione delle due caratteristiche che deve avere un problema di ottimizzazione affinche' sia applicabile la tecnica di programmazione dinamica. I quattro passi della programmazione dinamica (+ passo 0: comprensione del problema!).
• Il problema della parentesizzazione ottima del prodotto tra n matrici compatibili: definizioni su matrici, cosa e' , come si calcola e proprieta' del prodotto tra due matrici, definizione del costo del prodotto matriciale in termini di numero di prodotti. Legame tra parentesizzazione e alberi binari.

Seconda lezione (Martedi 20.11.2001, ore 9:30, aula U3-01)
Riferimento al testo:

• Tabella della ricorsione di un programma ricorsivo per il calcolo dei numeri di Fibonacci: sottoproblemi comuni, ricorsione con memorizzazione.
• Riepilogo del problema del prodotto "piu' economico" tra matrici. Esempio dei modi diversi (in termini di numero di prodotti) per moltiplicare 4 matrici compatibili. Messa in evidenza della sottostruttura ottima del problema. Scrittura della equazione di ricorrenza, in termini generali, scrittura della base della ricorrenza, scrittura della soluzione.
• Passo 3 della programmazione dinamica: calcolo del valore di una soluzione ottima. Discussione circa la scrittura di un algoritmo ricorsivo che traduce "banalmente" la ricorsione = complessita' esponenziale. Visione dell'albero della ricorsione.

Terza lezione (Giovedi 22.11.2001, ore 9:30, aula U3-04)
Riferimento al testo:
 

• Ancora sulla caratteristiche di un problema di ottimizzazione risolvibile con tecnica di p.d.: sottostruttura ottima e sottoproblemi comuni.
• Ancora sulla parentesizzazione ottima: comprensione del problema, caratterizzazione della struttura di una soluzione ottima (dimostrazione), definizione ricorsiva del valore di una soluzione ottima (ricorrenza).
• Calcolo del valore di una soluzione ottima: come scrivere un algoritmo che traduce la ricorrenza (ricorsivo con memorizzazione - uso della Lookup; iterativo).
• Dunque tecniche di riempimento della tabella dei costi.  Spiegazione dell'algoritmo. Calcolo della complessita'. Esempio di riempimento.
• Quarto passo: costruzione di una soluzione con valore ottimo, a partire dalle informazioni calcolate... come e dove modificare l'algoritmo per il riempimento della tabella dei costi per memorizzare le informazioni sui vari indici corrispondenti ai massimi via via calcolati.
• Definizione del problema della piu' lunga sottosequenza comune a due sequenze (LCS).  Nozione di sequenza, sottosequenza, sottosequenza comune, piu' lunga sottosequenza comune.
• Spiegazione e analisi della struttura del problema della LCS: come collegare la soluzione del problema a quello dei sottoproblemi (dimostrazione sottostruttura ottima). Dimostrazione formale del Teorema sulla sottostruttura ottima di una LCS.

• Riepilogo LCS: definizione del problema e sottostruttura ottima.
• Definizione ricorsiva del valore di una soluzione ottima per LCS: scrittura della ricorrenza "ricopiando" il teorema e generalizzando gli indici...
• Scrittura di un algoritmo iterativo per il calcolo del valore di una soluzione ottima: riempimento della tabella dei costi con strategia bottom-up. Spiegazione del metodo: determino l'elemento in funzione di quelli (precedentemente calcolati) in posizione nord/nord-ovest/ovest.
• Costruzione di una LCS: modifica dell'algoritmo precedente per la costruzione di una tabellina che conservi le informazioni sui massimi (tabellina delle freccine). Procedura di stampa delle informazioni (usando le freccine). Complessita' degli algoritmi presentati in tempo e spazio.

• Riepilogo concetti di base della programmazione dinamica.
• Il metodo greedy. Concetti di base. Dov'e' l' "avidita' " dell'algoritmo. Criterio di convenienza.
• Passi della tecnica greedy: stabilire criterio di convenienza rispetto al quale ordinare l'input per fare di volta in volta le scelte. Dimostrazione della correttezza di una tale strategia (costruisco l'ottimo).
• Vantaggi e svantaggi della tecnica greedy.
• Schema greedy. Prova della correttezza (flash sulla teoria dei matroidi).
• Esempio di applicazione della tecnica greedy: selezione di attivita'. Descrizione del problema, con esempi di applicazioni. Specifica di ogni attivita' e definizione di compatibilita'. Strategia: ordinare in senso decrescente sui tempi di fine (si massimizza il tempo libero). Scrittura algoritmo. Esempio di applicazione. Prova della correttezza dell'algoritmo greedy: proprieta' della scelta greedy e sottostruttura ottima.
• Non tutti i criteri funzionano! Svolgimento esercizio 17.1-3 del testo.
• Possibile soluzione con p.d. (cenno).

• Riepilogo concetti su algoritmi sviluppati con tecnica greedy. Schema generale di algoritmo greedy.
• Confronto tra algoritmi greedy e programmazione dinamica. Esempio del problema dello zaino 0-1 e dello zaino frazionario.
• Codici di Huffman. Definizione di codice (a lunghezza fissa e variabile). Esempio del codice Morse. Proprieta' di univoca decifrabilita'. Codici prefissi. Definizione del problema: minimizzare la lunghezza media delle parole di codice, garantendo univoca decifrabilita'. Codici prefissi e rappresentazione su albero binario. Ottimalita' dei codici prefissi. Algoritmo di Huffman (costruzione di codice prefisso ottimale, date le frequenze delle lettere input). Esempio di applicazione. complessita' dell'algoritmo e cenno della correttezza (proprieta' della scelta greedy e della sottostruttura ottima).
• Teoria dei matroidi - fondamenti. Definizione di sistema di indipendenza e di matroide. Definizione di matroide grafico. Matroide pesato (e matroide grafico pesato). Un problema di ottimizzazione su matroidi pesati: problema del massimo peso di un sottoinsieme indipendente di un matroide pesato. Definizione del problema su matroidi grafici (Problema del minimo spanning tree) e parallelo con quello generale su matroidi.
• Algoritmo greedy per risolvere il problema di massimo peso su matroidi pesati. Commenti.

• Riepilogo definizione di un matroide. Algoritmo greedy per il massimo peso di un sottoinsieme indipendente di un matroide pesato.
• Teorema di Rado: dimostrazione. (Distribuzione fotocopia con prova ed esercizi su matroidi).

• Svolgimento esercizi sui matrodi (n. 1 e n. 5 della lista consegnata)
• Svolgimento esercizio di programmazione dinamica (n. 1 della lista): A-lista.
• Descrizione dell'esercizio n.2 (Problema 16.4 del testo): festa aziendale.

• Algoritmi su grafi.
• Definizione di grafo, cammino, ciclo, grafo connesso o non, orientato o non, grafo pesato. rappresentazione dei grafi in memoria.
• Definizione del problema del Minimun Spamming Tree (MST). Uso della tecnica greedy. Definizione di albero di copertura minimo: Generic-MST e archi sicuri.
• Nozione di taglio, attraversamento del taglio, taglio che rispetta un insieme di archi. Arco leggero. Vari esempi. Teorema per determinare un arco sicuro (con dimostrazione). Corollario sulle compomenti connesse (utilizzato per dimostrare la correttezza degli algoritmi).
• Presentazione della tecnica generale. Algoritmi di Kruskal e Prim: introduzione alle idee e alla differenze.
• Algoritmo di Kruskal: descrizione intuitiva. Presentazione algoritmo, calcolo della complessita'. Prova della correttezza. Digressione su Union e Find.
• Algoritmo di Prim: descrizione intuitiva. Presentazione algoritmo, calcolo della complessita'. Prova della correttezza. Digressione sulle strutture dati avanzate per migliorare la complessita'.

 

• Riepilogo degli algoritmi presentati per risolvere il MST. Presentazione delle visite di un grafo.
• Visita in ampiezza (BFS). Descrizione strategia di attraversamento, esplicitazione del calcolo effettuato dalla BFS. Albero BFS. Giustificazione della colorazione dei vertici e del predecessore. Strutture dati usate. Algoritmo BFS. Tempo di calcolo. Enunciato teorema di correttezza. Esempio di esecuzione. Applicazione: dato grafo G, calcolare il numero dei nodi a minima distanza k dalla sorgente.

 

• Visita in profondita' (DFS). Descrizione strategia ed esempio. Differenza con BFS. Foresta DFS. Uso dei colori e dei tempi. Algoritmo, tempi di calcolo, esempio di esecuzione.
• Proprieta' degli archi, grafi aciclici
• Ordinamento topologico: uso della DFS e giustificazione.
• Esempio di esecuzione di Prim. Introduzione al problema dei cammini minimi in un grafo.

Dodicesima lezione (Giovedi 13.12.2001, ore 9:30, aula U3-04)
Riferimento al testo: Cap. 25 (introduzione), Cap 25.1 (cenni di dimostrazione dei Lemmi, esclusi Lemmi per l'albero dei cammini minimi), Cap. 25.2.

• Cammini minimi in un grafo orientato e pesato. Varianti. Albero dei cammini minimi: definizione Uso del predecessore.
• Sottostruttura ottima di un cammino minimo.
• Rilassamento (confronto con Prim): giustificazione. Osservazioni sulle proprieta' del rilassamento.
• Algoritmo di Dijkstra sui cammini minimi con sorgente singola. Descrizione intuitiva. Strutture dati. Algoritmo. Tempi di calcolo, cenni alla correttezza della strategia greedy applicata dall'algoritmo. Esempio.
• Svolgimento di due esercizi di programmazione dinamica (LCS crescente, scatole, rispettivamente n. 3 e n.1 della dispensa).

Tredicesima lezione (Lunedi 17.12.2001, ore 16, aula U3-04)
Riferimento al testo: Cap. 26 (introduzione), Cap 26.1-2.

• Ridefinizione del problema dei Cammini minimi tra coppie di vertici in un grafo orientato e pesato. Osservazione sulla non negativita' dei pesi. Quando e' possibile usare Dijkstra, complessita'.
• Rappresentazione del grafo con matrice di adiacenza dei pesi.
• Tecnica dei predecessori: descrizione della sottostruttura ottima dei cammini minimi, definizione ricorsiva del valore di una soluzione ottima. Complessita'.
• Introduzione alla tecnica di Floyd-Warshall.

 

• Algoritmo di Floyd-Warshall. Definizione della sottostruttura ottima (tecnica dei vertici interni) e definizione ricorsiva del valore di una soluzione ottima (scrittura della ricorrenza). Algoritmo e complessita'.
• Chiusura transitiva di un grafo orientato: definizione. Prima possibilita': uso di Floyd-Warshall. Seconda possibilita': caratterizzazione della sottostruttura e  scrittura di una ricorrenza a valori booleani.
• Svolgimanto di un esercizio di Programmazione Dinamica, usando la tecnica applicata per la chiusura transitiva (Esercizio n.13 della dispensa).

 

• Riassunto "breve" degli argomenti della lezione precedente, evidenziando i ragionamenti fatto per la scrittura delle equazioni di ricorrenza nei vari algoritmi.
• Esercizi di programmazione dinamica su grafi: Esercizi  della dispensa)