Sintesi delle lezioni

  • 14 Marzo
    • Presentazione del corso.
    • 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.
Edit | Attach | Watch | Print version | History: r21 < r20 < r19 < r18 < r17 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r21 - 2011-06-08 - AngeloMonti






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