Algoritmi Avanzati [145005]
Primo Semestre, 2009-2010

Agli studenti del corso si richiede di inviare una e-mail a Paolo Campigotto per comunicare il proprio nome e indirizzo email. Usare l'indirizzo fornito dall'università (@studenti.unitn.it) e includere la parola AA0910 per evitare che il messaggio venga filtrato.

Dati del corso

Testi

• Introduction to Algorithms (Second Edition); T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein; MIT Press
• Traduzione italiana: Introduzione agli algoritmi e strutture dati, seconda edizione, McGraw-Hill

Programma svolto

• Martedì 15 settembre
  Flusso massimo: Definizione di reti di flusso, generalizzazioni, proprietà di base. Esercizi.
  Riferimenti: 26.1.
• Giovedì 17 settembre
  Flusso massimo: metodo di Ford-Fulkerson, grafi residui, cammini aumentanti, tagli, teorema min cut / max flow, algoritmo di Edmonds-Karp.
  Riferimenti: 26.2, esclusi lemma 26.8 e teorema 26.9.
• Martedì 22 settembre (esercitazione)
  Flusso massimo. Metodo di Ford-Fulkerson: un esempio di esecuzione dell'algoritmo. Problema dell'abbinamento massimo in grafi bipartiti, teorema dell'integralità e relativa dimostrazione.
• Giovedì 24 settembre
  Sistemi di equazioni lineari: richiami di nomenclatura e di risultati essenziali sulle matrici. Sistemi triangolari e loro risoluzione. Fattorizzazione LUP.
  Riferimenti: 28.1 (senza dimostrazioni), 28.3.
• Martedì 29 settembre
  Sistemi di equazioni lineari: fattorizzazione LUP (continuazione), sua complessità, inversione di una matrice, approssimazione ai minimi quadrati.
  Riferimenti: 28.3, 28.4 (solo Calcolo di una matrice inversa da una fattorizzazione LUP), 28.5 (da Approssimazione ai minimi quadrati in poi).
• Giovedì 1 ottobre (esercitazione)
  Flusso massimo: appunto sul problema dell'abbinamento massimo in grafi bipartiti risolto tramite algoritmo di Ford-Fulkerson per reti di flusso. Proprietà delle matrici : primi esercizi. Approssimazione ai minimi quadrati: richiami di teoria ed esercizi.
• Martedì 6 ottobre
  Programmazione lineare: esempio introduttivo (funzione obiettivo, vincoli), formulazione in forma standard e slack, algoritmo del simplesso (introduzione).
  Riferimenti: 29.1, 29.2, 29.4 (fino a Pivoting escluso).
• Giovedì 8 ottobre (esercitazione)
  Approssimazione ai minimi quadrati: caso in cui F(x) definisce una famiglia di rette. Proprietà delle matrici : esercizi.
  Programmazione lineare: breve introduzione all programmazione matematica ed in particolare alla programmazione lineare, formulazione di un problema come problema di programmazione matematica.
• Martedì 13 ottobre
  Programmazione lineare: algoritmo del simplesso (formalizzazione), ricerca di soluzioni di base ammissibili.
  Riferimenti: 29.4 (senza dimostrazioni), 29.6.
• Giovedì 15 ottobre (esercitazione)
  Programmazione lineare. Formulazione di un problema come problema di programmazione matematica, interpretazione grafica dell'algoritmo del simplesso (compresi i casi programma lineare non fattibile ed illimitato): richiami di teoria ed esercizi. Convessita': richiami di teoria. Forma standard e forma slack di un problema di programmazione lineare: esercizi.
• Martedì 20 ottobre
  Programmazione lineare. Formulazione del programma duale. Interpretazione economica del programma duale. Principio di dualità debole e forte. Ottimalità della soluzione fornita dall'algoritmo del Simplesso.
  Riferimenti: 29.5 (esclusa la sola dimostrazione del teorema 29.10).
  Polinomi e DFT. Rappresentazione dei polinomi per coefficienti e per punti. Complessità delle operazioni di base (addizione, moltiplicazione e valutazione) rispetto alle diverse rappresentazioni.
  Riferimenti: 30.1.
• Giovedì 22 ottobre (esercitazione)
  Programmazione lineare. Metodo del simplesso: applicazione dell'algoritmo. Caso particolare in cui la soluzione iniziale non sia fattibile e caso particolare di simplesso illimitato. Dualità: primi esercizi.
• Martedì 27 ottobre
  Polinomi e DFT. Richiami sulla rappresentazione polare dei numeri complessi e sulle radici dell'unità. Algoritmo divide-et-impera per la trasformata veloce di Fourier. Trasformata inversa.
  Riferimenti: 30.2.
• Giovedì 29 ottobre (esercitazione)
  Programmazione lineare. Dualità: esercizi. Polinomi e DFT. Richiami di teoria. Prorietà delle radici dell'unità: esercizi.
• Martedì 3 novembre
  DFT e campionamento di segnali: Teorema della convoluzione. Serie di Fourier, uso delle radici dell'unità per campionamento di segnali periodici.
  Riferimenti: 30.2.
  String matching: Algoritmo "ingenuo", complessità nel caso migliore, peggiore e medio.
  Riferimenti: 32.1, 32.2, esercizio 32.2-3.
• Giovedì 5 novembre (esercitazione)
  Polinomi e DFT. Proprietà delle radici dell'unità: esercizi. DFT: esercizi. FFT: esercizi.
• Martedì 10 novembre
  String matching: algoritmo di Rabin-Karp, automi a stati finiti, funzione prefisso.
  Riferimenti: 32.3, 32.4 (inizio).
• Giovedì 12 novembre (esercitazione)
  String matching. Algoritmo "ingenuo", algoritmo di Rabin-Karp: richiami di teoria ed esercizi. Automi a stati finiti: richiami di teoria.
• Martedì 17 novembre (esercitazione)
  String matching. Automi a stati finiti: esercizi. Esercizi di ripasso. Formulazione di un problema come problema di programmazione lineare.
• Giovedì 19 novembre (esercitazione (1h) /teoria (1h))
  Esercizi di ripasso. Ancora formulazione di un problema come problema di programmazione lineare. Metodi di ottimizzazione: ricerca locale stocastica . Ottimizzazione combinatoria: introduzione. Problemi SAT e TSP: definizione ed esempi. [Slides cap. 1 del libro SLS)]
• Martedì 24 novembre
  String matching: automa di string matching, implementazione dela funzione di matching, calcolo della funzione di transizione.
  Riferimenti: 32.4 tranne dimostrazioni dei teoremi.
  Geometria computazionale: segmenti di retta, inviluppo convesso, prodotto vettoriale. Determinazione del senso di svolta di due segmenti consecutivi, verifica dell'intersezione di due segmenti.
  Riferimenti: 33.1
• Giovedì 26 novembre
  Geometria computazionale: determinare se due segmenti si intersecano (conclusione), angolo polare, ordinamento in base alla sequenza di sweep di una semiretta. Poligoni semplici, verifica se n punto si trova all'interno di un poligono.
  Riferimenti: 33.1 (fine), esercizi 33.1-3, 33.1-5, 33.1-6, 33.1-7. Attenzione: alcuni esercizi discussi a lezione non sono sul libro.
• Martedì 1 dicembre
  Geometria computazionale: determinare se vi sono intersezioni in un insieme di segmenti. Inviluppo convesso e sue proprietà algoritmi di Jarvis e di Graham.
  Riferimenti: 33.2, 33.3
  Attenzione: le prossime due lezioni (giovedì 3 e giovedì 10) saranno dedicate agli algoritmi di ricerca locale; la lezione di martedì 15, sarà invece dedicata alla discussione sugli esercizi delle sezioni 33.2 e 33.3 del libro.
• Giovedì 3 dicembre
  Metodi di ottimizzazione: ricerca locale stocastica. Complessità computazionale, approcci per affrontare un problema NP-completo, paradigmi di ricerca, in particolare ricerca locale stocastica. [Slides cap. 1 del libro SLS)]
• Giovedì 10 dicembre
  Metodi di ottimizzazione: ricerca locale stocastica. Metodi di base della ricerca locale stocastica: iterative improvement, variable depth search, variable neighbourhood descent, randomized iterative improvement, probabilistic iterative improvement, simulated annealing, tabu search. [Slides cap. 2 del libro SLS)]
• Martedì 15 dicembre
  Geometria computazionale: discussione degli esercizi 33.1-5, 33.1-6.
  Algoritmi di approssimazione: coefficiente di approssimazione, schemi di approssimazione polinomiale e totalmente polinomiale. Il problema della copertura minima dei vertici di un grafo, algoritmo con coefficiente di approssimazione 2.
  Riferimenti: 35 (introduzione), 35.1.
• Giovedì 17 dicembre
  Metodi di ottimizzazione: ricerca locale stocastica. Tabu search, dynamic local search. Metodi ibridi di ricerca locale stocastica: iterated local search, GRASP method. Metodi di ricerca locale stocastica basati su "popolazioni": algoritmi evoluzionistici, algoritmi genetici.
• Martedì 22 dicembre (esercitazione)
  Algoritmi di approssimazione. Proposto un algoritmo di approssimazione per un dato problema di ottimizzazione, determinarne il fattore di approssimazione.
  Esercizi di ricapitolazione.

Esami ed esercizi di preparazione

• Esempio di esame scritto dato nell'edizione precedente del corso.
  Attenzione: il testo d'esame è riportato a titolo di esempio (su esplicita richiesta di alcuni studenti), quest'anno i testi degli scritti potrebbero subire cambiamenti anche significativi.
• Esercizi di preparazione allo scritto, versione del 3 gennaio 2010. Soluzioni (versione dell'8 gennaio).
• Scritto di lunedì 11 gennaio 2010 (English version). Soluzioni.
• Scritto di lunedì 8 febbraio 2010 (English version). Soluzioni.
• Scritto di giovedì 3 giugno 2010