Algoritmi efficienti, complessità polinomiale, complessità esponenziale, complessità di un problema, complessità 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à della BFS. Correttezza della BFS. Albero BFS dei cammini minimi.
21 Marzo
Visita in profondità. Complessità 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 è 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 è 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 è 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 è 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à 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 è 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 è 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à 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 è 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à
9 Maggio
Problema: Dati n punti sul piano trovare la coppia di punti più 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ù di 2logn +1 domande.
Problema: dato un vettore V ordinato di n interi verificare se nel vettore è presente una posizione i per cui vale V[i]=i in tempo O(log n).
13 Maggio
Calcolabilità
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 è la capacià dello zaino ed n è 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 è 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ù 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 è la probabilita che la moneta i dia testa, calcolare in tempo O(kn) la probabilità che il lancio delle n monete produca esattamente k teste.
Problema: abbiamo n lavori, ciascun lavoro i è 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 è 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à
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 è 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ù un numero dispari, in tempo O(D(n)n) dove D(n) è 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) è il numero di stringhe da stampare.
problema: dati n interi positivi ed un intero M, verificare in tempo O(nM) se è 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 è possibile ottenere il numero M come somma di alcuni degli n elementi sotto l'ipotesi che uno stesso elemento può essere utilizzato più volte.
problema: dati n interi positivi e due interi M e K, verificare in tempo O(nMK) se è possibile ottenere il numero M come somma di al più K degli n elementi sotto l'ipotesi che uno stesso elemento può essere utilizzato più volte.