Tags:
create new tag
view all tags

Progettazione di Algoritmi a.a. 2017-2018

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

martedì 27 febbraio 2018: neve?!

giovedì 1 marzo 2018: Presentazione del corso. Algoritmi efficienti, complessità polinomiale, esponenziale superesponenziale e subesponenziale Definizioni di base su grafi diretti e non diretti, relazione tra numero di nodi e numero di archi. Alberi (come grafi connessi aciclici) e alberi radicati

venerdì 2 marzo 2018: Problemi inerententemente intrattabili: stampa di tutte le stringhe binarie lunghe n, stampa di tutte le permutazioni di n numeri.Rappresentazione di grafi tramite matrice di adiacenza e liste d'adiacenza, vantaggi e svantaggi. Grafi sparsi. DAG.Il problema del pozzo universale. Un algoritmo O(n) nel caso in cui il grafo è rappresentasto tramite matrice d'adiacenza ed un limite inferiore Ω(n+m) nel caso in cui il grafo è rappresentato tramite liste d'adiacenza.

martedì 6 marzo 2018: Visita in profondita: DFS, correttezza e complessità. Determinare se un grafo è connesso in tempo O(n+m). Il vettore dei padri per rappresentare alberi radicati. Albero di copertura di un grafo connesso. Trovare un albero di copertura di un grafo connesso in O(n+m). Determinare se un grafo non diretto è aciclico in tempo O(n).

giovedì 8 marzo 2018: operazioni su alberi rapresentati tramite vettore dei padri. Partizione degli archi di un grafo a seguito di una DFS: archi in avanti, archi all'indietro e archi di attraversamento. Determinare se un grafo diretto e' aciclico in O(n+m). Tri-colorazione di un grafo.

venerdì 9 marzo 2018: Un grafo, connesso o meno che sia, ha sempre almeno due vertici con lo stesso grado. Un grafo connesso ha 0 o 2 sole bicolorazioni. Bi-colorazione di un grafo in O(n+m). Ponti e Punti di articolazione di un grafo. Numero massimo di ponti in un grafo di n nodi. Algoritmo per la ricerca dei ponti di un grafo in O(n+m).

martedì 13 marzo 2018: Ordinamenti topologici. Numero massimo e numero minimo di ordinamenti topologici possibili. Consizioni necessarie e sufficienti perché nel grafo siano presenti ordinamenti topologici. Algoritmo per la ricerca di un ordinamento topologico in grafi aciclici basato sulle sorgenti. Algoritmo per la ricerca di un ordinamento topologico in grafi aciclici basato sulle visite DFS del grafo. Complessità e correttezza dei due algoritmi. Applicazione dell'algoritmo visto a lezione la volta scorsa per la ricerca dei ponti di un grafo connesso.

giovedì 15 marzo 2018: componenti connesse in grafi non diretti e componenti fortemente connesse in grafi diretti. Algoritmo per la ricerca delle componenti connesse di un grafo in tempo O(n+m). Algoritmo che dato un grafo diretto G ed un suo nodo u trova la componente fortemente cui quel nodo appartiene in tempo O(n+m). Provare che l'agoritmo appena visto applicato iterativamente alla ricerca di tutte le componenti fortemente connesse del grafo diretto richiede O(nm). Esercizio: Modificare la procedura di visita DFS di modo che questa restituisca il numero di archi all'indietro, il numero di archi di attraversamento ed il numero di archi in avanti che si sono incontrati nel corso della visita che parte da un determinato nodo.

venerdì 16 marzo 2018: Visita in ampiezza di un grafo (BFS), correttezza e complessità. Definizione di distanza in grafi non pesati. Dato un nodo sorgente calcolare le distanze di questo da tutti gli altir in tempo O(n+m). Albero dei Cammini minimi. Grafi pesati (con pesi sugli archi). Definizione di distanza in grafi pesati. Ricerca dell'albero dei cammini minimi in grafi pesati. Algoritmo di Dijkstra.

martedì 20 marzo 2018: Esercizio: trovare il diametro di un albero in O(n). Correttezza dell'algoritmo di Dijkstra. Esempi che mostrano che l'algoritmo non è corretto nel caso in cui nel grafo siano presenti anche archi di peso negativo. Complessità dell'algoritmo di Dijkstra: implementazione O(n^2) e implementazione O(mlogn). Esempi di algoritmi greedy: Il problema di massimizzare il numero di file su un disco in O(nlog n), l'algoritmo greedy scorretto per il problema simmetrico di minimizzare il numero di file su disco. Il problema dell'assegnamento di attività ad un processore: diversi criteri di scelta greedy che falliscono (segliere l'attivita' che dura meno, scegliere l'attivita' che inizia prima, scegliere l'attivita' che produce meno conflitti). Prova di correttezza dell'algoritmo greedy basato sul criterio di scegliere l'attività che finisce prima.

giovedì 22 marzo 2018: esercizio: dato un albero rappresentato tramite vettore dei padri ed un intero k contare in O(n) i nodi dell'albero alivello k (soluzione basata sul trasformare la rappresentazione dell'albero tramite vettore dei padri in quella tramite liste di adiacenza). Il problema della ricerca del minimo albero di copertura. L'albero dei cammini minimi non necessariamente e' il minimo albero di copertura. L'algoritmo di Kruskal. Correttezza dell'algoritmo di Kruskal.

venerdì 23 marzo 2018: Struttura dati UNION e FIND: implementazione dove UNION richiede O(n) e FIND O(1) e implementazione dove UNION richiede O(1) e FIND O(log n). Implementazioni dell'algoritmo di Kruskal in O(n^2) e O(mlog n). ESERCIZIO: Cosa accade all'albero di copertura di un grafo quando tutti gli archi del grafo subiscono uno stesso incremento di costo? Cosa accade nella stessa situazione all'abero dei cammini minimi del grafo?. ESERCIZIO: verificare se un certo algoritmo greedy per la colorazione del grafo è corretto (nel qual caso dare la prova di correttezza) o meno (nel qual caso esibire un controesempio).

martedì 27 marzo 2018: Algoritmo di Prim per la ricerca del minimo albero di copertura: dimostrazione di correttezza e sue implementazioni. Gli algoritmi e le euristiche. Problemi di ottimizzazione. Definizione di rapporto d'approssimazione per euristiche di problemi d'ottimizzazione. Il problema della minima copertura tramite nodi. L'euristica greedy basata sulla selezione dei nodi di grado massimo, dimostrazione che l'euristica non ha rapporto d'approssimazione limitato da una costante (esempio di istanze che producono un rapporto Θ(log n)). Un'euristica con complessità Θ(m) che ha rapporto d'approssimazione limitato da 2.

giovedì 29 marzo 2018: vacanze di pasqua

venerdì 30 marzo 2018: vacanze di pasqua

martedì 3 aprile 2018: vacanze di pasqua

giovedì 5 aprile 2018: paradigma del divide et impera. Risoluzione di tipiche ricorrenze che vengono fuori da algoritmi di divide et impera. Ricerca binaria (versione iterativa e versione ricorsiva). Dato un vettore ordinato di n interi ed un intero x scrivere il codice di una funzione che in O(log n) restituisca il numero di occorrenze di x ne vettore. Dato un vettore di n interi (non necessariamente positivi), ricercare il valore massimo che si può ottenere per i suoi sottovettori. Algoritmo banale di tempo O(n^2), algoritmo basato sul divide et impera di tempo O(n log n).

venerdì 6 aprile 2018: Il problema della ricerca della coppia di punti più vicina: algoritmo di tempo O(n^2) e algoritmo basato sulla tecnica del divide et impera a tempo O(nlog n). ESERCIZIO:Un vettore V ordinato di n interi distinti viene ruotato verso destra di k posizioni, 1<=k<n. Dato il vettore V progettare un algoritmo che in tempo O(nlog n) restituisca il numero k. Il problema della selezione: dato un vettore con n interi distinti ed un intero k, 1<=k<=n, vogliamo sapere in tempo O(n) cosa capiterebbe in posizione k se il vettore venisse ordinato.

martedì 10 aprile 2018: algoritmo randomizzato per il problema della selezione con tempo medio O(n) e tempo al caso pessimo O(n^2). Algoritmo per la selezione con tempo O(n). Dimostrare che le ricorrenze T(n)=T(an)+T(bn)+O(n) con a+b<n hanno soluzione O(n). ESERCIZIO: dato un vettore V di interi distinti contare il numero di inverisoni (vale a dire il numero di coppie (i,j) con 0<=i<j<n tali che v[i]>v[i]) in tempo O(n). ESERCIZIO: dato un vettore di interi dove esattamente un intero compare una sola volta mentre tutti gli altri compaiono duplicati trovare l'elemento che compare esattamente una volta in tempo O(lon n). ESERCIZIO: Dato un vettore contenente in teri in cui un intero compare nella maggioranza assoluta di posti (vale a dire in piu' della meta' delle posizion) trovare questo elemento in tempo O(n).

giovedì 12 aprile 2018: ESERCIZIO: dato un intero n trovare la parte intera di √n in tempo O(log n). ESERCIZIO: La moltiplicazione classica di due numeri di n cifre ciascuno richiede O(n) operazioni aritmetiche elementari, descrivere un algoritmo per moltiplicare i due numeri di n cifre in tempo o(n^2). ESERCIZIO valutare un'euristica per la ricerca del massimo sottografo aciclico in un grafo diretto (l'euristica in esame seleziona l' insieme A con archi che vanno da nodi i a nodi j con i<j. Se la maggioranza degli archi del grafo sono di questo tipo allora viene restituito il grafo che contiene solo questi archi, in caso contrario tutti questi archi vengono cancellati dal grafo). Dimostrare che il rapporto d'approssimazione è limitato da 2. ESERCIZIO: valutare un'euristica per il seguente problema: abbiamo scatole di capacità C e n oggetti ciascuno con un suo peso. Vogliamo inscatolare gli n oggetti utilizzando il minor numero di scatole. (l'euristica in esame mette gli oggetti finchè possibile nella prima scatola appena tocca inscatolare un oggetto che non può finire in quella scatola la sigillala ed inaugura una nuova scatola). Provare che l'euristica ha un rapporto d'approssimazione che tende a 2 ma che 2 è anche il limite superiore al suo rapporto d'approssimazione.

venerdì 13 aprile 2018: ESERCIZIO: assumendo di aver trovato le componenti fortemente connesse di un grafo diretto G costruire il grafo delle componenti fortemente connesse di G in O(n+m). Dimostrare che il grafo delle componenti fortemente connesse è sempre un grafo aciclico. ESERCIZIO: assumendo di aver trovato le componenti fortemente connesse di un grafo G verificare in tempo O(n+m) se G contiene un vertice universale. ESERCIZIO: dato un grafo diretto e due insiemi dei suoi nodi A e B rrovare in tempo O(n+m) la distanza minima per potersi spostare da un nodo di A ad un nodo di B. ESERCIZIO: Date n località ho una matrice M n x n dove nella locazione M[ i,j] trovo il costo per poter collegaretramite tubature le località i e j. Ed ho un vettore V di dimensione n dove nella locazione i trovo il costo per scavare un pozzo in corrispondenza della località i. Calcolare il costo minimo per far si che tutte le località siano rifornite d'acqua o grazie al fatto che in esse è stato scavato un pozzo o grazie al fatto che tramite una rete di tubature arrivino ad una località in cui e' presente un pozzo. L'algoritmo deve avere complessità O(n^2).

martedì 17 aprile 2018: simulazione della prova d'esonero tramite il compito d'esonero assegnato l'anno scorso. intermedia2017.pdf

giovedì 19 aprile 2018: PROVA D'ESONERO

venerdì 20 aprile 2018

martedì 24 aprile 2018: la tecnica della programmazione dinamica. Approccio top-down e approccio bottom-up. Overlapping di sottoproblemi: tabelle e memoizzazione. ESERCIZIO: il calcolo dell'ennesimo numero di Fibonacci. ESERCIZIO: dato un disco di capacità C ed n file di lunghezza l1,l2,...ln, trovare il sottoinsieme di file che massimizzano l'occupazione di spazio su disco. Algortimo che risolve il problema in tempo O(nC). Algoritmi pseudopolinomiali.

giovedì 26 aprile 2018: ESERCIZIO: dato n contare in O(n) il numero di stringhe binarie lunghe n in cui non compaiono due zeri adiacenti. ESERCIZIO: dato n contare in O(n) il numero di diverse sistemazioni di n persone in stanze da 1 o due posti. ESERCIZIO: dato un vettore di n interi (positivi e negativi) vogliamo trovare in O(n) il sottovettore di valore massimo (vale a dire la somma dei cui valori è massima). ESERCIZIO: dato un vettore di n interi positivi vogliamo trovare in O(n) il valore massimo ottenibile selezionando elementi del vettore non adiacenti.

venerdì 27 aprile 2018: ESERCIZIO: dato n contare in tempo O(n) il numero di numeri decimali lunghi n le cui cifre formano una sequenza non decrescente (i numeri possono cominciare anche con zero). ESERCIZIO: data una sequenza X di n interi, in O(n^2) trovare la sottosequenza crescente di X più lunga. ESERCIZIO: data una matrice M di dimensione nxn contenente interi, ci si può spostare da una cella all'altra di M o in orizzontale (da sinistra a destra) o in verticale (dall'alto verso il basso). Di tutti i cammini che partono dalla cella in altro a sinistra e terminano alla cella in basso a destra, vogliamo trovare in tempo O(n^2) quello di valore massimo. Il valore di un cammino è dato dalla somma degli interi delle celle che attraversa.

martedì 1 maggio 2018: FESTA

giovedì 3 maggio 2018: ESERCIZIO: algoritmo pseudopolinomiale di tempo O(nC) per la soluzione del problema dello zaino, dove n è il numero di oggetti e C la capacità dello zaino. ESERCIZIO: algoritmo di complessità O(nC) per la variante del problema dello zaino in cui per ogni oggetto si dispone di un numero arbitrario di copie. ESERCIZIO: dato un vettore di n interi vogliamo selezionare un sottoinsieme dei suoi elementi il cui valore totale sia minimo e con la proprietà che per ogni 5 posizioni adiacenti nel vettore almeno un elemento è stato selezionato. ESERCIZIO: Algoritmo psedopolinomiale di tempo O(nR) per il problema del Resto dove bisogna restituire un resto R utilizzando il numero minimo di monete da scegliere fra n tagli disponibili. ESERCIZIO: Per il problema del resto si vuole calcolare in O(nR) il numero di diveri modi di dare resto R utilizzando i tagli disponibili.

venerdì 4 maggio 2018: ESERCIZIO: algoritmo O(nR) per il problema del resto basato sulla ricerca di un cammino minimo in un grafo diretto. ESERCIZIO: algoritmo O(nC) per il problema dello zaino basato sulla ricerca del cammino di costo massimo in un grafo diretto aciclico. Dato un grafo diretto aciclico ed un nodo sorgente s, trovare in O(n+m) il costo massimo per andare da s a ciascuno degli altri nodi del grafo. ESERCIZIO: Il problema della pianificazione di attività, un progetto richiede l'esecuzione di n attività con tempi di esecuzione t1,t2, ...tn. Abbiamo una lista con m vincoli di dipendenza tra le attivita' (i vincoli sono del tipo i<j vale a dire si può cominciare l'esecuzione dell'attività j solo al termine dell'attività i), vogliamo sapere in tempo O(n+m) qual'e' il tempo minimo per completare il poter portare a termine il progetto e per ogni attività qual'e' il tempo d'inizio per poter terminare il progetto il prima possibile.

martedì 8 maggio 2018: ESERCIZIO: algoritmo di Bellman e Ford che in tempo O(n^2+nm) calcola i costi minimi per andare da un nodo sorgente a tutti li altri nodi di un grafo diretto e pesato con pesi anche negativi ma senza cicli di costo negativo. ESERCIZIO: Algoritmo di Floyd and Warshall che in tempo O(n^3) trova il costo minimo per spostarsi da i a j per ogni coppia di nodi (i,j) di un grafo diretto con pesi anche negativi ma senza cicli di costo negativo. ESERCIZIO: Il problema della soluzione di un sistema di n variabili con m vincoli di differenza, sua soluzione in tempo O(n^2+nm) tramite riduzione al problema della ricerca di cammini di costo minimo in grafi diretti con pesi anche negativi.

giovedì 10 maggio 2018: ESERCIZIO: date due stringhe x1..xn e y1...ym trovare la più lunga sottosequenza comune alle due stringhe (LCS) in tempo O(nm). Definizione di distanza tra parole, data una due stringhe x e y calcollare la distanza minima da x a y. Nel caso in cui le uniche operazioni sono inseirmento di caratteri e cancellazione di caratteri la distanza da x a y e' |X| + |Y| -2LCS(x,y). ESERCIZIO: Calcolo dell'EDIT DISTANCE (dove oltre a inserimento e cancellazione di caratteri è permesso anche la modifica di caratteri) in O(|X||Y|). Date n monete ciascuna avente una sua probabilita' pi di produrre testa, ed un intero k <=n calcolare in tempo O(nk) la probabilita' che un lancio delle n monete produca esattamente k teste. ESERCIZIO: Data una pila di n monete due giocatori si alternano e ciascun giocatore puo' eliminare dalla pila 1, 3 o 5 monete. Vince il giocatore che vuota la pila. Determinar ein tempo O(n) se il primo giocatore ha un astrategia vincente. ESERCIZIO: C'e' una sequenza di n interi, a turno due giocatori si alternano e ciascun giocatore puo' cancellare il primo o l'ultimo elemento della sequenza incassando una cifra ad essa corrispondente. Dei due giocatori vince chi al termine ha incassato di più. Determinare se il primo giocatore ha una strategia vincente.

venerdì 11 maggio 2018

martedì 15 maggio 2018: Ricerca esaustiva. Algoritmo ottimo che stampa in tempo O(n2^n) tutte le stringhe binarie lunghe n. Il numero di stringhe binarie lunghe n contenenti al più un numero costante c di uni è O(n^c). Algoritmo esaustivo che stampa tutte lestringhe di lunghezza n con al più c uni in tempo O(n2^n) ed algoritmo ottimo di backtraking che risolve il problema in tempo O(n^(c+1)). Sia S(n) il numero di stringhe da stampare, un teorema che da condizioni sufficienti perché l'algoritmo di backtraking abbia un tempo di calcolo funzione di S(n) anzicché di 2^n. ESERCIZIO: algoritmo ottimo per stampare tutte le stringhe binarie lunghe n con esattamente c uni in tempo O(n^(c+1)). ESERCIZIO: algoritmo ottimo per stampare tutte le stringhe binarie lunghe n in cui non compaiono mai tre uni consecutivi (l'algoritmo deve avere dunque tempo di calcolo O(nS(n)) dove S(n) sono l stringhe da stampare).

giovedì 17 maggio 2018: Impementazione in python di algoritmi di backtraking. ESERCIZIO: dato n stampare tutte le stringhe ternarie lunghe n dove il numero di caratteri 'a' è almeno quanto il numero di caratteri 'b' che è almeno il numero di caratteri 'c'. L'algoritmo deve avere complessità O(nS(n)) dove S(n) e' il numero di stringhe da stampare. ESERCIZIO: dati due interi n e k bisogna stampare tutte le sequenze di n cifre decimali la cui somma è k. L'algoritmo deve avere complessità O(nS(n)) dove S(n) e' il numero di stringhe da stampare. Alberi di permutazione di altezza n: hanno n! foglie e O(n!) nodi interni.

venerdì 18 maggio 2018: ESERCIZIO: dato n stampare tutte le permutazioni di n numeri in tempo O(nn!). ESERCIZIO: dato n stampare tutte le permutazioni di n numeri che nelle posizioni pari hanno un numero pari e in quelle dispari hanno un numero dispari in tempo O(nS(n)) dove S(n) e' il numero delle permutazioni da stampare. ESERCIZIO: Un grafo diretto di n nodi è hamiltoniano se contiene un ciclo semplice di n nodi. Dato un grafo diretto progettare un algoritmo basato sul backtraking che decida se un grafo è hamiltoniano o meno.

martedì 22 maggio 2018: ESERCIZIO: dato n stampare tutte le 2^{n^2}matrici binarie quadrate di lato n. ESERCIZIO: dato n stampare tutte le matrici ternarie di lato n dove non appaiono mai due valori zero in celle adiacenti (data una cella (i,j) le celle adiacenti sono al piu' 8: (i,j-1),(i,j+1),(i-1,j),(i+1,j),(i-1,j-1) (i+1,j+1), (i+1,j-1),(1+1,j-1)), l'algoritmo deve avere complessità O(n^2S(n)) dove S(n) sono le matrici da stampare. ESERCIZIO: Data una scacchiera n per n vogliamo trovare i possibili modi di posizionarvi n regine in modo che queste non si diano fastidio (vale a dire due regine non possono essere posizionate ne' sulla stessa riga, ne' sulla stessa colonna ne' sulla stessa diagonale). Notare che una soluzione può essere vista come una permutazione di n interi e produrre un algoritmo di backtraking che dato n stampi tutte le permutazioni di n interi corrispondenti a posizionamenti leciti delle n regine sulla scacchiera. ESERCIZIO: Dato un grafo di n nodi dare un algoritmo basato sulla tecnica del backtraking che produce una tricolorazione dei suoi nodi o scopra che questa non esiste.

giovedì 24 maggio 2018: Backtraking e problemi di ottimizzazione: il problema dello zaino. ESERCIZIO: dato un grafo aciclico di n nodi trovare tutti i suoi ordinamenti topologici in tempo O(n^2S(n)) dove S(n) è il numero gli ordinamenti da stampare. ESERCIZIO: data una stringa di n caratteri trovare in O(n^2) il numero minimo di caratteri che vanno inseriti nella stringa per renderla palindroma (programmazione dinamica).

venerdì 25 maggio 2018: somministrazione e correzione degli esercizi assegnati alla prova d'esonero giugno 2017

martedì 29 maggio 2018: ESERCIZIO Bisogna ricoprire con tessere di dimensioni 1 x 2 una superficie di dimenione 3 x n. Dato n calcolare in O(n) il numero delle diverse coperture possibili. (ad esempio per n=1 la risposta e' 0 mentre per n=2 la risposta e' 3 e per n=3 la risposta e' 0 ...). ESERCIZIO: Abbiamo un albero di n nodi evogliamo colorare i nodi di bianco o di nero in modo stando bene attenti a non avere archi dell'albero con entrambi gli estremi di colore nero. Dato l'albero in O(n) calcolare il numero massimo di nodi che e' possibile colorare di nero. ESERCIZIO data una sequenza ternaria X lunga n stampare tutte le sottosequenze non decrescenti di X contenenti tutti e tre i differenti simboli. L'algoritmo deve avere complessità O(n S(n)) dove S(n) è il numero di sottosequenze da stampare.

giovedì 31 maggio 2018: fine lezioni

Topic attachments
I Attachment History Action Size Date Who Comment
PDFpdf intermedia2017.pdf r1 manage 143.7 K 2018-04-19 - 07:15 AngeloMonti  
Edit | Attach | Watch | Print version | History: r135 < r134 < r133 < r132 < r131 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r135 - 2018-06-01 - AngeloMonti






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