Alg2lezioni < Algoritmi2

Tags: view all tags
---++*Sintesi delle lezioni*

   * 14 Marzo
      * Presentazione del corso.
      * Algoritmi efficienti, complessit&agrave; polinomiale, complessit&agrave; esponenziale, complessit&agrave; di un problema, complessit&agrave; di un algoritmo, ecc. ecc. 

   * 16 Marzo
      * Definizioni di base sui grafi.
      * Strutture dati per rappresentare grafi: matrice di adiacenza e liste di adiacenza, vantaggi e svantaggi.

   * 18 Marzo
      * Visita in ampiezza. Complessit&agrave; della  BFS. Correttezza della BFS. Albero BFS dei cammini minimi.
      
   * 21 Marzo
      * Visita in profondit&agrave;. Complessit&agrave; della  DFS. Correttezza della DFS. Albero DFS di copertura. 
      * problema: trovare le componenti connesse di un grafo in O(n+m).
      * problema: trovare tutti i punti d'articolazione di un grafo connesso in O(m).

   * 23 Marzo
      * problema: stabilire se un grafo orientato &egrave; fortemente connesso in O(n+m).
      * problema: trovare le componenti fortemente connesse in un grafo orientato in O(n+m). Algoritmo di Tarjan e sua correttezza.
 

   * 25 Marzo
      * problema: stabilire se un grafo &egrave; bipartito in O(n+m).
      * problema:verificare l'esistenza di un pozzo universale in grafi rappresentati tramite liste di adiacenza ed in grafi rappresentati tramite matrice di adiacenza. 

   * 28 Marzo
      * problema: stabilire se un grafo &egrave; aciclico in O(n).
      * problema: trovare un ordinamento topologico in un grafo orientato aciclico in O(n+m). Algoritmo basato sulla visita DFS e algoritmo basato sulla ricerca di nodi senza archi entranti.
      * classificazione degli archi di un grafo (orientato) a seguito di una visita DFS: archi dell'albero, archi in avanti, archi all'indietro e archi di attraversamento.
      * problema: stabilire se un grafo orientato &egrave; aciclico in O(n+m).
      
   * 30 Marzo
      * problema: trovare il minimo albero di copertura in grafi pesati.Tecnica greedy.
      * Algoritmo di Prim, correttezza  e sue implementazioni  in O(n^2) e O(m log n).  
      * Strutture dati per insiemi disgiunti, implementazione delle operazioni FIND e UNION in O(log n) e O(1), rispettivamente.
      * Algoritmo di Kruskal, correttezza ed  implementazione in O(m log n)
      
   * 1 Aprile
      * problema: trovare il diametro di un albero in O(n).
      * problema:  supponendo di aver gia calcolato un MST per un grafo G, aggiornare in O(n) l'MST a seguito dell'inserimento  di un nuovo arco in G. 

   * 4 Aprile
      * problema: stabilire se un grafo orientato è singolarmente connesso in O(nm +n^2).
      * problema: stabilire se un grafo orientato è singolarmente connesso in O(n^2).
      * problema: stabilire se un grafo orientato contiene un vertice principale in O(n+m).

   * 6 Aprile
      * problema: trovare l'albero dei cammini minimi in grafi (orientati) con pesi non negativi.
      * Algoritmo di Dijkstra, correttezza e sue implementazioni  in O(n^2) e O(m log n).  
      * problema: trovare l'albero dei cammini minimi in grafi orientati aciclici. Algoritmo basato sull'ordinamento topologico, sua correttezza e implementazione  in O(n+m). 

   * 8 Aprile
      * Codici, codici prefisso, codice di Huffman: un esempio di algoritmo greedy nel problema della compressione dati. Sua implementazione in O(n log n)     
      * problema: dimostrare che  un grafo con archi di pesi tutti diversi ha un unico albero di copertura minimo.

   * 11 Aprile
      * corretteza dell'algoritmo di Huffman.
      * problema:trovare il codice di Huffman ottimo nel caso di n simboli le cui frequenze sono i primi n numeri di Fibonacci.

   * 13 Aprile
      * problema: selezione di attivit&agrave; in O(n log n) e correttezza dell'algoritmo greedy
      * problema distribuzione di lezioni nel minor numero di aule, correttezza dell'algoritmo greedy e implementazione in O(n^2)
      * problema: il cambio delle monete, correttezza dell'algoritmo greedy per particolari insiemi di tagli.

   * 15 Aprile
      * problema: Dato un grafo orientato G, dimostrare che G &egrave; semi-connesso se e solo se il grafo delle componenti fortemente connesse di G, contiene un cammino Hamiltoniano.
      * problema: Dato un grafo orientato G stabilire se il grafo  &egrave; semi-connesso in tempo O(n+m).
      * problema: Descrivere un algoritmo che, dato un grafo completo, ne orienta archi in modo che il grafo orientato risultate sia aciclico. La complessit&agrave; dell'algoritmo deve essere O(m).

   * 18 Aprile
      * problema: Dato un insieme di lavori ciascuno caratterizzato da un profitto e una deadline, assumendo di poter eseguire un singolo lavoro per volta e che ciscun lavoro richiede tempo
         unitario,  calcolare un sottoinsieme  dei lavori che possono  essere eseguiti rispettando le  deadline e che massimizza il profitto. 
      * problema: Dati 2n interi r1,r2,...rn e c1,c2,....cn verificare se &egrave; possibile posizionare delle pedine su di una scacchiera di dimensione n per n in modo che nella riga i-esima 
         risultino ri  pedine  e nella colonna j-esima   risultino cj pedine, per ogni riga i e colonna j.  

   * 20 Aprile
      * vacanze.

   * 29 Aprile
      *  ESONERO

-------------------------------------------

   * 4 Maggio
      * Problema: Dato un vettore di interi trovare il sottovettore di somma massima in O(n log n). Tecnica del Divide et impera.
      * Discussione dei compiti d'esonero.

   * 6 Maggio
      * Calcolabilit&agrave;

   * 9 Maggio
      * Problema: Dati n punti sul piano trovare la coppia di punti pi&ugrave; vicina in tempo O(n log n). 

   * 11 Maggio
      * Problema: Dato un insieme di n interi distinti ed un intero k  selezionare l'intero  che capiterebbe al k-mo posto a seguito dell'ordinamento degli elementi dell'insieme in tempo O(n)
      * Problema: indovinare un intero n>=1 facendo non pi&ugrave; di 2logn +1 domande.
      * Problema: dato un vettore V ordinato di n interi verificare se nel vettore &egrave; presente una posizione i per cui vale V[i]=i in tempo O(log n).

   * 13 Maggio
      * Calcolabilit&agrave;

   * 18 Maggio
      * Divide et impera, overlapping di sottoproblemi e numeri di Fibonacci. Tecnica della programmazione dinamica. 
      * Dato un vettore di interi trovare il sottovettore di somma massima in O(n ).      
      * Data una sequenza di n interi trovare la sottosequenza crescente di lunghezza massima in O(n^2)
      * Problema: dato un vettore di n interi ordinato ed un intero x contare le occorrenze di x nel vettore in O(log n)
      * Problema: dato un vettore di n interi contare il numero di coppie in ordine non crescente che compaiono  nel vettore in O(n log n).

   * 20 Maggio
      * risolvere il problema dello zaino in tempo O(nC) dove C &egrave; la capaci&agrave; dello zaino ed n &egrave; il numero di oggetti.
      * Date due stringhe di lunghezza n ed m rispettivamente, calcolarne la distanza in tempo  O(nm ).      
      * Problema: Data una matrice n per n di  interi trovare in tempo O(n^2)  il cammino di valore  massimo tra quelli che portano dalla locazione (1,1) alla locazione (n,n). I soli spostamenti ammessi nel  cammino, sono da una  locazione all'eventuale locazione  adiacente a  destra o all'eventuale locazione adiacente in basso.

   * 23 Maggio
      *  algoritmo di Bellman-Ford: trovare la distanza minima dei vertici da una stessa sorgente in un grafo con pesi anche negativi in O(nm).
      *  Tecnica della riduzione: risolvere  un sistema con n variabili ed m vincoli di differenza  in tempo  O(nm).  

   * 25 Maggio
      *  algoritmo di Floyd-Warshall: trovare la distanza minima tra tutte le coppie di vertici in un grafo con pesi anche negativi in O(n^3) tempo e O(n^2) spazio.
      *  Problema: trovare in O(n^2) tempo  il numero minimo di simboli che &egrave; necessario inserire in una stringa di n simboli per renderla palindroma.

   * 27 Maggio
      *  calcolare il prodotto di una catena di matrici utilizzando il minor numero di operazioni aritmetiche.
      *  Problema: trovare in O(n^2) tempo la pi&ugrave; grande sottomatrice quadrata di soli zeri in una matrice quadrata binaria n per n.
      *  Problema: dato un intero k ed  n valori p_1,p_2,....p_n dove p_i  &egrave; la probabilita che la moneta i dia testa, calcolare in tempo O(kn) la probabilit&agrave; che il lancio delle n monete produca esattamente k teste.
      * Problema: abbiamo  n lavori,  ciascun lavoro i &egrave; caratterizzato da una terna (a_i,v_i,c_i) dove a_i rappresenta il numero di operai necessari all'esecuzione del lavoro, v_i quel che si ottiene dall'esecuzione del lavoro e c_i la penale da pagare nel caso il lavoro non venga eseguito. Disponiamo di M operai. Vogliamo determinare il sottoinsieme di lavori che &egrave; possibile eseguire che massimizza il guadagno (i.e. il sottoinsieme di lavori eseguiti la somma dei cui operai non supera M e per cui risulta massima la somma del valore dei lavori esegui meno la somma dei lavori non eseguiti).

   * 1 Giugno
      * enumerare tutti i possibili sottoinsiemi di n oggetti. 
      * problema: dati n oggetti enumerarne tutti i possibili sottoinsiemi contenenti esattamente c elementi, per una fissata costante c. 
      * Il problema dello zaino e la tecnica del backtracking.      

   * 3 Giugno
      * Calcolabilit&agrave;

   * 6 Giugno
      * enumerare tutte le permutazioni di n numeri.
      * Il problema della ricerca di un  ciclo Hamiltoniano in un grafo.
      * problema: dato un intero n,   trovare tutti i modi in cui  &egrave; possibile posizionare n regine su di una scacchiera n per n in modo che nessuna di esse possa catturarne un'altra.

   * 8 Giugno
      * problema: dato un intero n, stampare tutti i sottoinsiemi dei primi n numeri che contengono al pi&ugrave; un numero dispari, in tempo O(D(n)n) dove D(n) &egrave; il numero di sottoinsiemi da stampare.
      * problema: dato un intero n, stampare  tutte le stringhe ternarie lunghe n dove il numero di simboli 0 non supera il numero di simboli 1 che a sua volta non supera il numero di simboli 2, in tempo O(D(n)n) dove D(n) &egrave; il numero di stringhe da stampare.
      * problema: dati n interi positivi ed un intero M,  verificare  in tempo O(nM) se  &egrave; possibile ottenere il numero M come somma di un sottoinsieme degli n elementi. 
      * problema: dati n interi positivi ed un intero M,  verificare  in tempo O(nM) se  &egrave; possibile ottenere il numero M come somma di alcuni degli n elementi sotto l'ipotesi che uno stesso elemento pu&ograve; essere utilizzato pi&ugrave; volte.
      * problema: dati n interi positivi e due interi M e K,  verificare  in tempo O(nMK) se  &egrave; possibile ottenere il numero M come somma di al pi&ugrave; K   degli n elementi sotto l'ipotesi che uno stesso elemento pu&ograve; essere utilizzato pi&ugrave; volte.