Algoritmi avanzati (2006/2007)

Corso a esaurimento

Codice insegnamento
4S01076
Docente
Roberto Posenato
crediti
5
Altri corsi di studio in cui è offerto
Settore disciplinare
INF/01 - INFORMATICA
Lingua di erogazione
Italiano
Sede
VERONA
Periodo
3° Q dal 2-apr-2007 al 8-giu-2007.

Orario lezioni

Obiettivi formativi

Acquisire un'adeguata conoscenza dei principali paradigmi avanzati di algoritmi per problemi di ottimizzazione combinatorica con particolare attenzione per i paradigmi che permettono di determinare soluzione approssimante per problemi di ottimizzazione combinatoria NP-difficili.

Programma

Richiamo dei principali concetti inerenti ai problemi computazionali: descrizione, istanze, codifica, modelli precisi e modelli approssimati. Problemi computazioni di ottimizzazione. Esempi di problemi computazionali.

Richiamo dei principali concetti inerenti agli algoritmi: risorse computazionali, codifica dell'input, dimensione dell'input, definizione di tempo computazionale. Analisi caso peggiore e caso medio. Tempo di calcolo e ordini di grandezza: possibili insidie.

Tempi di calcolo e miglioramenti hardware: relazioni principali. Algoritmi efficienti e problemi trattabili.

Paradigma divide et impera
--------------------------
Richiamo struttura. Analisi complessità. Esempi di applicazione: prodotto tra due numeri, Prodotto fra due matrici.
Schema divide et impera per il prodotto di due polinomi. Uso delle radici primitive complesse per la valutazione veloce di un polinomio: Trasformata veloce di Fourier (FFT). Uso di FFT anche per l'interpolazione.
Introduzione al problema della mediana e, generalizzazione, al problema della selezione. Risoluzione del problema della selezione. Illustrazione di altri problemi risolvibili con la tecnica divide et impera: ricerca massimo di un piano, ricerca della coppia di punti più vicina.

Paradigma greedy
----------------
Richiamo struttura. Esempio di applicazione per il problema dell'albero minimo di ricoprimento. Richiamo sulla struttura dati per insiemi disgiunti. Esempio di applicazione per il problema dei cammini minimi da sorgente singola (algoritmo di Dijkstra).
Introduzione ai matroidi: definizione, proprietà fondamentali. Problema del Massimo di un matroide pesato. Dimostrazione che la tecnica greedy determina sempre la soluzione ottima per il problema del Massimo di un matroide pesato.
Valutazione due soluzioni all'esercizio di ricerca elemento in una matrice ordinata.
Uso dei matroidi per la risoluzione del problema di programmazione di task unitari su singolo processore. Limiti della rappresentazione con i matroidi. Esempi di problemi risolvibili con tecnica greedy che non sono rappresentabili da matrodidi.

Tecnica backtracking
--------------------
Introduzione. Schema generale. Aspetti cruciali.
Applicazione della tecnica al problema dello zaino con ripetizione. Analisi correttezza e complessità.
Introduzione uso della tecnica al problema dell'inviluppo convesso: algoritmo di Graham. Uso della tecnica backtracking al problema del string matching: algoritmo di Knuth, Morris & Pratt.

Tecnica branch & bound
----------------------
Introduzione. Schema generale. Aspetti cruciali.
Scelta ordine di visita dei figli: strategia hill climbing. Tecnica come nuova tecnica ricerca in un albero: strategia best-first.
Applicazione della tecnica al problema dell'assegnamento e al problema dello zaino.
Applicazione della tecnica al problema del commesso viaggiatore come esempio di funzione lower bound non banale.

Paradigma programmazione dinamica
---------------------------------
Introduzione. Schema generale. Aspetti cruciali. Applicazione della tecnica al problema della massima sottosequenza crescente. Applicazione della tecnica al problema del string matching approssimato e al problema dello zaino.
Analisi di esempi di applicazione. Pattern ricorrenti per la determinazione di sottoproblemi.
Tecnica memoization (annotazione)
Introduzione e analisi vantaggi svantaggi.

Tecnica ricerca locale
----------------------
Introduzione e studio caso applicazione al problema dell'albero minimo di ricoprimento. Risoluzione del problema dell'ordinamento mediante tecnica di ricerca locale: ordinamento per inserimento e ShellSort.

Algoritmi di approssimazione
----------------------------
Classi NPO e PO. Errore relatio e indice di performance. Algorimo r-approssimante. Problema r-approssimabile.
Studio dell'approssimabilità del problema Min Vertex Cover: dall'algoritmo greedy all'algoritmo pseudo-casuale.
Simulated annealing.
Tabù search.

Algoritmi probabilistici
------------------------
Definizione. Algoritmi probabilistici numerici, algoritmi di Monte Carlo e algoritmi di Las Vegas. Esempi di problemi risolti con tali algoritmi: Buffon's needle, Pattern Matching e Universal hashing.

Algoritmi quantistici
---------------------
Introduzione ai concetti di qubit, stato di sistema quantistico, codifica di informazioni con i qubit, algoritmo quantistico. Determinazione della trasformata di Fourier mediante algoritmo quantistico.

Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani Algorithms (Edizione 1) McGraw-Hill Higher Education 2007 978-0-07-352340-8 consultazione
Alan Bertossi Algoritmi e strutture dati (Edizione 1) UTET 2000 88-7750-611-3 consultazione
G. Brassard, P. Bratley Fundamentals of Algorithms Prentice-Hall 1996 0133350681 consultazione
T. Cormen, C. Leiserson, R. Rivest, C. Stein Introduzione agli Algoritmi e Strutture Dati (Edizione 2) McGraw-Hill 2005 88-386-6251-7 consultazione

Modalità d'esame

L'esame consiste in una prova scritta e una orale.

Nella prova scritta il candidato dovrà risolvere degli esercizi in ordine crescente di difficoltà. Gli esercizi hanno lo scopo di verificare la preparazione dello studente sui concetti fondamentali e la loro applicazione. Non viene MAI richiesto di conoscere a memoria dettagli di dimostrazioni, ma di conoscere i teoremi, la loro dimostrazione nei punti fondamentali e di saperli applicare. Solitamente gli esercizi sono quattro a difficoltà crescente. I primi due esercizi valgono al massimo 7 punti ciascuno mentre gli ultimi due 8. La prova è superata se per ciascuno dei primi due esercizi si ottengono almeno 4 punti E si raggiunge il punteggio finale di 18. La prova ha una durata di un'ora e mezza.

La prova orale consiste in un colloquio dove viene richiesto di 'ragionare' su almeno due argomenti (a scelta del docente) del programma del corso. Il colloquio ha lo scopo di verificare la capacità dello studente di presentare gli argomenti e i principali risultati. Per quanto riguarda le dimostrazioni dei teoremi, lo studente è tenuto a conoscere le dimostrazioni principali fatte durante il corso (segnalate dal docente e sul programma).

Materiale didattico

Documenti

Condividi