Tags:
create new tag
view all tags

Progettazione di Algoritmi a.a. 2016-2017

Diario delle lezioni e delle esercitazioni - Canale II (Monti)

Lunedì 20 febbraio 2017     Algoritmi efficienti e problemi intrattabili. Grafi: diretti e non diretti, loro rappresentazione tramite matrici e liste di adiacenza. Alberi ed alberi radicati.

Mercoledì 22 febbraio 2017     Esempio: il problema del pozzo universale. Visite di grafi

Venerdì 24 febbraio 2017     visita in profonditÓ (DFS), correttezza e complessitÓ. Il calcolo delle componenti connesse di un grafo in O(n + m).

Lunedì 27 febbraio 2017     alberi di visita DFS, classificazione degli archi di un grafo a seguito di una visita DFS. Verificare se un grafo contiene cicli in O(n+m). Ricerca dei ponti e dei punti di articolazione in un grafo in tempo O(n+m). ESERCIZIO: determinare se un grafo Ŕ bipartito (o equivalentemente bicolorabile) in tempo O(n+m).

Mercoledì 1 marzo 2017     Visita DFS in grafi diretti. Classificazione degli archi di un grafo diretto a seguito di una DFS. Verificare in O(n+m) se un grafo diretto contiene cicli. Grafi diretti aciclici ( DAG) . Algoritmo O(n+m) basato su visita DFS per la ricerca di un sort topologico in un DAG

Venerdì 3 marzo 2017     Le componenti fortemente connesse. Algoritmo per verificare se un grafo diretto Ŕ fortemente connesso in O(n+m). Algoritmo di Tarjan per trovare tutte le componenti fortemente connesse di un grafo diretto in O(n+m).

Lunedì 6 marzo 2017     Il problema dei cammini minimi in grafi non pesati. La visita in ampiezza (BFS) e l'albero BFS dei cammini minimi. Correttezza e complessitÓ della visita in ampiezza. Il problema dei cammini minimi in grafi pesati.

Mercoledì 8 marzo 2017     Algoritmo di Dijkstra per la ricerca delle distanze minime e dei cammini minimi in grafi con pesi non negativi. Correttezza dell'algoritmo e implementazioni efficienti nel caso di grafi sparsi e nel caso di grafi densi.

Venerdì 10 marzo 2017     ESERCITAZIONI

Lunedì 13 marzo 2017     Esempi di algoritmi greedy: Il problema della selezione delle attivitÓ ed il problema dei file e del disco. Correttezza e complessitÓ dei due algoritmi proposti.

Mercoledì 15 marzo 2017     Il problema della partizione delle attivitÓ e l'esercizio "museo". Correttezza e complessita' dei due algoritmi. Il problema della ricerca dell'albero di copertura di costo minimo. Algoritmo di Prim correttezza e complessitÓ.

Venerdì 17 marzo 2017     ESERCITAZIONE

Lunedì 20 marzo 2017     Il problema della ricerca dell'albero di copertura di costo minimo. Algoritmo di Kruskal correttezza e complessitÓ. Esercizi sull'ordinamento topologico.

Mercoledì 22 marzo 2017     Euristiche ed algoritmi approssimanti. Rapporto d'approssimazione. Il problema della copertura tramite vertici: un algoritmo con rapporto d'approssimazione non limitato e un algoritmo con rapporto d'approssimazione limitato da 2.

Venerdì 24 marzo 2017     ESERCITAZIONE

Lunedì 27 marzo 2017     esempi di algoritmi approssimanti: euristiche per il bin paking e la selezione dei centri, calcolo del rapporto di approssimazione

Mercoledì 29 marzo 2017     Esercizi. Introduzione alla tecnica del divide et impera. Risoluzione di ricorrenze tramite il teorema Master. Il calcolo di a^n utilizzando O(log n) moltiplicazioni. Il calcolo del sottovettore di valore massimo

Venerdì 31 marzo 2017     ESERCITAZIONE

Lunedì 3 aprile 2017     Algoritmi pseudo-polinomiali : il test di primalitÓ per un numero n in O(n). Tempo. Esempi: Il prodotto di due matrici di dimensione n per n, algoritmo banale O(n^3) e lower bound O(n^2). Dato un vettore ordinato di n interi ed un intero x trovare il numero di occorrenze dell'intero x nel vettore in tempo O(log n).

Mercoledì 5 aprile 2017     ESERCITAZIONE

Venerdì 7 aprile 2017     Esercizi preparatori alla prova intermedia. Algoritmo per la ricerca della coppia di punti pi¨ vicina (prima parte)

Lunedì 10 aprile 2017     Esercizi preparatori alla prova intermedia: analisi di un euristica per il problema di rendere un grafo privo di triangoli eliminando il numero minimo di archi. Algoritmo per la ricerca della coppia di punti pi¨ vicina (seconda parte)

Mercoledì 12 aprile 2017    

PROVA INTERMEDIA


Venerdì 14 aprile 2017    

Vacanze pasquali


Lunedì 17 aprile 2017    

Vacanze pasquali


Mercoledì 19 aprile 2017    

Lezione annullata per far posto alla prova intermedia di reti


Venerdì 21 aprile 2017     ESERCITAZIONE

Lunedì 24 aprile 2017    

Ponte festivo


Mercoledì 26 aprile 2017    

Lezione annullata


Venerdì 28 aprile 2017     Panoramica sulla programmazione dinamica: Quando si applica: problemi di ottimizzazione con soluzioni con sottostruttura ottimale, spazio delle soluzioni spazio dei sottoproblemi. Come si applica. top-down con memoizzazione, bottom-up. ESEMPI: rod cutting. Moltiplicazione di catena di matrici.

Lunedì 1 maggio 2017    

PRIMO MAGGIO


Mercoledì 3 maggio 2017     il calcolo dei numeri di Fibonacci. Verisone esponenziale con overlapping di sottoproblemi. Versione top-down con memoizzazione di tempo O(n). Versione bottom-up di tempo O(n). Il problema della ricerca del sottovettore di valore massimo. Algoritmo di programmazione dinamica di tempo O(n)

Venerdì 5 maggio 2017     ESERCITAZIONI

Lunedì 8 maggio 2017     Il problema della sottosequenza crescente pi¨ lunga in O(n^2). Il conteggio delle stringhe binarie lunghe n senza uni consecutivi. Il gioco del gettone.

Mercoledì 10 maggio 2017     Il problema dello zaino e algoritmo che lo risolve in O(nC). Algoritmi pseudopolinomiali. Algoritmo di tempo O(n^2) per il calcolo della probabilitÓ di ottenere lo stesso numero di teste e croci dal lancio di 2n monete truccate.

Venerdì 12 maggio 2017     ESERCITAZIONE

Lunedì 15 maggio 2017     la tecnica del backtraking generazione di tutte le stringhe binarie in O(n2^n). Generazione di tutte le stringhe binarie con al pi¨ k zeri in tempo O(nS(n)) dove S(n) Ŕ il numero di stringhe da generare.

Mercoledì 17 maggio 2017     Backtraking: generare tutte le matrici binarie, generare matrici con vincoli. Albero delle permutazioni. Generare tutte le permutazioni, generare permutazioni con vincoli. Programmazione dinamica: date due stringhe di lunghezza n ed m, trovare la sottosequenza comune pi¨ lunga in tempo O(nm).

Venerdì 19 maggio 2017     ESERCITAZIONI.

Lunedì 22 maggio 2017     Esempi di applicazione della tecnica della programmazione dinamica: Algoritmo di Bellman-Ford per la ricerca dei cammini minimi su grafi con pesi anche negativi in tempo O(nm). Algoritmo di Floyd e Warshall per la ricerca dei cammini minimi tra tutte le possibili coppie di nodi in tempo O(n^3)

Esempio di applicazione della tecnica del backtraking a problemi di ottimizzazione: il problema dello zaino. Esempio di applicazione del backtraking a problemi di ricerca: il problema del ciclo Hamiltoniano. Esercizi sulla tecnica di programmazione dinamica.

Venerdì 26 maggio 2017     ...............

Lunedì 29 maggio 2017     ......

Mercoledì 31 maggio 2017     .......

Esercizi

Edit | Attach | Watch | Print version | History: r99 < r98 < r97 < r96 < r95 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r99 - 2017-05-24 - AngeloMonti






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback