Sintesi delle lezioni

• 5 Marzo
  • Presentazione del corso.
  • Definizioni di base sui grafi.
  • Strutture dati per rappresentare grafi: matrice di adiacenza e liste di adiacenza, vantaggi e svantaggi.
  • Algoritmi efficienti, complessità polinomiale, complessità esponenziale.

• 7 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: stabilire se un grafo orientato è fortemente connesso in O(n+m).
  • 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 è aciclico in O(n).
  • problema: stabilire se un grafo orientato è aciclico in O(n+m).

• 9 Marzo
  • problema: trovare un ordinamento topologico in un grafo orientato aciclico in O(n+m).
  • problema: trovare tutti i punti di articolazione di un grafo connesso in O(m).

• 12 Marzo
  • CALCOLABILITÀ e COMPLESSITÀ

• 14 Marzo
  • In un grafo orientato un pozzo universale è un nodo con grado entrante n-1 e grado uscente 0.
    • problema: stabilire in O(n) se un grafo orientato rappresentato tramite matrice d'adiacenza ha un pozzo universale o meno.
    • dimostrare che nel caso di un grafo rappresentato tramite liste d'adiacenza il problema non può essere risolto in tempo O(n).
  • problema: trovare il diametro di un albero in tempo O(n).

• 16 Marzo
  • Visita in ampiezza. Complessità della BFS. Correttezza della BFS.
  • problema: costruire l'albero dei cammini di lunghezza minima a partire da un vertice sorgente.
  • problema: soluzione al problema del diametro di un albero basata sulle visita BFS.
  • Un grafo orientato G è singolarmente connesso se per ogni coppia di vertici u,v esiste al più un cammino orientato semplice fra u e v.
    • stabilire in O(nm) se un grafo orientato è singolarmente connesso.

• 19 Marzo
  • CALCOLABILITÀ e COMPLESSITÀ

• 21 Marzo
  • problema: trovare le componenti fortemente connesse di un grafo orientato in tempo O(n+m).
  • problema : stabilire in O(n^2) se un grafo ha un ciclo di lunghezza 4.

• 23 Marzo
  • problema: dato un nodo x in un grafo, in tempo O(n+m) trovare il numero di camminini minimi che da x portano a ciascun altro nodo del grafo.
  • problema : provare o confutare che un grafo diretto ha un ciclo se e solo se durante la visita in ampiezza del grafo si incontra un arco all'indietro.
  • problema: dati due insiemi A e B di nodi in un grafo diretto trovare in O(n+m) il numero minimo di archi da attraversare per passare da un nodo in A ad un nodo in B.
  • Definizione e proprietà del grafo delle componenti fortemente connesse di un grafo orientato.
  • problema: a partire da un grafo G costruire il grafo G^SCC delle componenti fortemente connesse in O(n+m).
  • in un grafo orientato un nodo u si dice principale se da u è possibile raggiungere ogni altro nodo del grafo.
    • stabilire in O(n+m) se un grafo orientato ha un nodo principale.

• 26 Marzo
  • CALCOLABILITÀ e COMPLESSITÀ

• 28 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).

• 30 Marzo
  • 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)
  • problema: dimostrare che un grafo con archi di pesi tutti diversi ha un unico albero di copertura minimo.

• 2 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).

• 4 Aprile
  • problema: selezione di attività, correttezza dell'algoritmo greedy e sua implementazione in O(n log n).
  • problema: distribuzione di lezioni nel minor numero di aule, correttezza dell'algoritmo greedy e implementazioni in O(n^2) e O(n log n)

• 11 Aprile
  • CALCOLABILITÀ e COMPLESSITÀ
  • Codici, codici prefisso, codice di Huffman: un esempio di algoritmo greedy nel problema della compressione dati. Sua implementazione in O(n log n)

• 13 Aprile
  • CALCOLABILITÀ e COMPLESSITÀ

• 16 Aprile
  • Algoritmi di approssimazione, quantificazione dell'errore.
  • Problema della copertura tramite vertici. Un algoritmo greedy con fattore d'approssimazione non costante ed un algoritmo greedy con fattore d'approssimazione 2.
  • Problema: supponendo di aver gia calcolato un MST per un grafo G, a seguito dell'inserimento di un nuovo arco in G aggiornare opportunamente l'MST in tempo O(n).

• 18 Aprile
  • Tecnica del Divide et impera.
  • Problema: Dati n punti sul piano trovare la coppia di punti più vicina in tempo O(n log n).
  • Problema: Dato un vettore ordinato di n interi ed un intero x contare le occorrenze di x nel vettore in tempo O(log n).

• 20 Aprile
  • Problema. Dato un array A di n interi trovare la somma dei valori di uno dei sotto-array (contiguo) di somma massima (le soluzioni date per questo problema possono facilmente essere adattate in modo da restituire l'indice di inizio e fine di uno dei sottoarray di somma massima).
    • Soluzione Divide et Impera in O(nlogn).
    • Soluzione Divide et Impera in O(n).
  • Esercizi di preparazione alla Prova Intermedia.

• 27 Aprile
  • PROVA INTERMEDIA (in orario di lezione). Per "prenotarsi" (se non lo si è già fatto in classe) spedire un'email al docente.

• 2 Maggio
  • Soluzioni della prima prova intermedia e discussione.
  • Problema: Dato un insieme S di n elementi e un intero 1<=k<=n trovare l'elemento y di S avente rango k (ovvero l'elemento y di S per cui esistono esattamente k-1 elementi x di S tali che x<y). Soluzione in tempo O(n).
  • Programmazione dinamica. Caratteristiche principali, differenze da divide et impera
  • Problema. Dato un array A di n interi trovare la somma dei valori di uno dei sotto-array (contiguo) di somma massima (le soluzioni date per questo problema possono facilmente essere adattate in modo da restituire l'indice di inizio e fine di uno dei sottoarray di somma massima).
    • Soluzione Programmazione Dinamica in O(n).

• 4 Maggio
  • Problema (della sottosequenza crescente più lunga). Data una sequenza di n interi trovare la sottosequenza crescente di lunghezza massima in O(n^2)
  • Problema (del taglio dell'asse). Data una tabella V di n valori dove V_i rappresenta il prezzo di un' asse di lunghezza i. Determinare in O(n^2) la sequenza di tagli da effettuare su di un'asse di lunghezza n per massimizzare il profitto derivante dalla vendita dei pezzi ottenuti.

• 7 Maggio
  • Approccio top-down e fenomeno dei sottoproblemi comuni, memoizzazione ed approccio bottom-up.
  • Problema (del cambio delle monete). Date monete di n tagli diversi e dovendo produrre un resto C, trovare in O(nC) il minor numero di monete che occorrono per ottenere il valore C
    • Soluzione che utilizza la tecnica della riduzione (al problema della ricerca del cammino minimo in un grafo).
    • Soluzione basata sulla tecnica della programmazione dinamica che utilizza tabella monodimensionale.
    • Soluzione basata sulla tecnica della programmazione dinamica che utilizza tabella bidimensionale.
  • Problema. Data una matrice n per n di interi positivi trovare in tempo O(n^2) il cammino di valore minimo tra quelli che portano dalla locazione (1,1) alla locazione (n,n). Risolvere il problema nelle due seguenti versioni:
    • i soli spostamenti ammessi nel cammino, sono da una locazione all'eventuale locazione adiacente a destra o all'eventuale locazione adiacente in basso.
    • i soli spostamenti ammessi nel cammino, sono da una locazione all'eventuale locazione adiacente a destra o all'eventuale locazione adiacente in basso o all'eventuale locazione in alto.

• 9 Maggio
  • Problema (dello zaino). Dato uno zaino in grado di sopportare un determinato peso C ed n oggetti, ognuno dei quali caratterizzato da un valore ed un peso, trovare in O(nC) il sottoinsieme di oggetti da mettere nello zaino per ottenere il maggiore valore senza eccedere nel peso sostenibile dallo zaino stesso.
  • Problema (della sottosequenza comune più lunga). Data una sequenza di n interi X e una sequenza di m interi Y , trovare in O(nm) la sottosequenza comune ad X e Y di lunghezza massima.
    • Problema risolvere in O(n^2) il problema della sottosequenza crescente più lunga per riduzione dal problema della sottosequenza comune più lunga.
  • Data una matrice quadrata binaria n per n trovare in O(n^2) la sottomatrice quadrata di lato massimo contenente unicamente zeri.

• 11 Maggio
  • CALCOLABILITÀ e COMPLESSITÀ

• 14 Maggio
  • Problema (algoritmo di Bellman-Ford). Dato un grafo pesato (con pesi anche negativi) ed un suo nodo sorgente s, trovare in O(nm) i cammini di costo minimo da s agli altri nodi del grafo o segnalare che il grafo contiene cicli di costo negativo.
  • Problema (algoritmo di Floyd-Warshall). Dato un grafo pesato (con pesi anche negativi), trovare in O(n^3) i cammini di costo minimo tra tutte le coppie di nodi del grafo o segnalare che il grafo contiene cicli di costo negativo.

• 16 Maggio
  • Problema Dato un sistema di vincoli di differenza con n variabili ed m vincoli determinare se il sistema ammette soluzioni e nel caso produrne una.
    • risolvere il problema in tempo O(nm) mediante una riduzione al problema della ricerca di cicli negativi e cammini minimi in un grafo diretto e pesato con pesi anche negativi.
  • Problema Data una stringa X di n caratteri ed una stringa Y di m caratteri vogliamo determinare il numero minimo di operazioni da applicare per trsformare X nella stringa Y. Le sole operazioni possibili sono: inserimento di un carattere, cancellazione di un carattere e modifica di un carattere. Risolvere il problema in tempo O(nm).
  • Problema Date le probabilita' p1, ...pn con cui n monete truccate producono testa, calcolare in O(nk) la probabilità che un lancio delle n monete produca esattamente k teste.

• 18 Maggio
  • CALCOLABILITÀ e COMPLESSITÀ

• 21 Maggio
  • Problema. Data una stringa di n caratteri vogliamo determinare il numero minimo di caratteri che bisogna inserire nella stringa per renderla palindroma. Risolvere il problema in tempo O(n^2).
  • Problema Date n chiavi, ciascuna con la sua frequenza, vogliamo determinare per le n chiavi l'albero binario di ricerca di costo minimo, dove il costo dell'albero è dato dalla somma delle frequenze delle chiavi ciascuna moltiplicata per il livello dell'albero in cui si trova. Risolvere il problema in O(n^3).

• 23 Maggio
  • Problema. (prodotto catena di matrici) Disponiamo di una procedura in grado di moltiplicare matrici a coppie e che richiede a x b x c moltiplicazioni per effettuare il prodotto di due matrici di dimensioni a x b e b x c. Data una sequenza n matrici da moltiplicare, calcolare in O(n^3) il numero minimo di prodotti che bisognerà effettuare.
  • Problema. (commesso viaggiatore euclideo e bitonico) Dati n punti nel piano, un ciclo bitonico è un cammino che parte dal punto più a sinistra, va da sinistra verso destra fino a raggiungere il punto più a destra e poi si sposta da destra verso sinistra toccando tutti i punti che incontra non ancora toccati fino a ritornare al punto di partenza. Fra tutti i possibili cammini bitonici vogliamo quello più breve. Risolvere il problema in tempo O(n^2).

• 25 Maggio
  • CALCOLABILITÀ e COMPLESSITÀ

• 28 Maggio
  • enumerare tutti i possibili sottoinsiemi di n oggetti in O(n2^n)
  • la tecnica del backtracking. Le funzioni di taglio. Applicazione della tecnica al problema dello zaino.
  • Problema. Abbiamo una sequenza di n interi. A turno due giocatori selezionano e cancellano l'intero a destra o l'intero a sinistra della sequenza. Al termine il primo giocatore riceverà una vincita pari alla somma degli interi che ha via via cancellato. Descrivere un algoritmo che in tempo O(n^2) calcola qual'e' la vincita massima che il giocatore può essere sicuro di ricevere qualunque siano le mosse fatte dal suo avversario.

• 30 Maggio
  • 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.

• 1 Giugno
  • CALCOLABILITÀ e COMPLESSITÀ

• 4 Giugno
  • problema: dati n oggetti ed un intero k con k<=n, vogliamo enumerare tutti i possibili sottoinsiemi degli n oggetti contenenti esattamente k oggetti. Descrivere un algoritmo che risolve il problema in tempo O(D(n,k)n) dove D(n,k) è il numero di sottoinsiemi da stampare.
  • problema: Abbiamo una matrice n per n contenente degli zeri e 2n interi r1,r2,...rn e c1,c2,....cn dove la somma dei valori ri è uguale alla somma dei valori ci. Vogliamo inserire valori nelle caselle della matrice in modo che la somma dei valori risultanti nella riga i-esima sia pari a ri e la somma dei valori risultanti nella colonna j-esima sia cj. Descrivere un algoritmo che risolve il problema in O(n).
  • problema: Abbiamo un insieme di n oggetti su cui non è definita una relazione d'ordine e tra due coppie di oggetti è possibile chiedersi solo se questi sono uguali o meno. Sappiamo che tra gli n oggette ne e' presente uno che si ripete in maggioranza (i.e. compare almeno (n+1)/2 volte). Descrivere un algoritmo che in tempo O(nlogn ) individua l'elemento di maggioranza.

• 8 Giugno
  • Programma finale sulla parte di CALCOLABILITÀ e COMPLESSITÀ :
  • Calcolabilità:
    • Algoritmi on-line. Tempo reale. Macchine a stati finiti.
    • Fattorizzazioni di stringhe. Dizionari prefisso. Codici prefisso.
    • Macchine di Turing. Linguaggi e calcolabilità.
    • Linguaggi ricorsivi e ricorsivamente enumerabili. Indecidibilità.
    • Il problema della fermata. Tecniche di diagonalizzazione. Riduzioni fra linguaggi.
  • Complessità:
    • Non-determinismo e complessità. Le classi P ed NP.
    • La congettura su P e NP. Linguaggi NP-completi. Soddisfacibilità.
    • Riduzioni polinomiali. Sottografo completo. Ricoprimento di archi tramite vertici.