Obiettivi formativi
Obiettivo del corso e' di fornire una panoramica dei piu' importanti algoritmi.
Prerequisiti
Algoritmi e strutture dati e laboratorio o Algoritmi e strutture dati.
Contenuti dell'insegnamento
<div align=""""justify"""">
<div align="""justify""">
<ul>
<li>tecnica greedy, programmazione dinamica, algoritmi branchbound, ricerca locale, metodo della discesa piu ripida, Metropolis, simulated annehaling;</li>
<li>geometria computazionale: inviluppo convesso, point location, triangolarizzazione di un poligono, algoritmo sweeping, algoritmo closest pair;</li>
<li>DFT-IDFT: algoritmo FFT di Cooley -Tuckey, prodotto/divisione di polinomi, polinomio di interpolazione, teorema cinese dei resti, FFT in strutture finite, algoritmo di Schonhage-Strassen per il prodotto di interi; </li>
<li>calcolo di forme bilineari, algoritmi per il prodotto di matrici, problemi collegati al prodotto di matrici; </li>
<li>string matching esatto: automi, algoritmi di Knuth-Morris-Pratt, Boyer-Moore, Aho-Corasick; string matching approssimato: distanza di Hamming, distanza di edit, programmazione dinamica; trie, suffix tree, compressione di Ziv-Lempel; </li>
<li>classi di complessita P, NP, NPC e loro relazioni, riduzioni polinomiali, le classi LOGSPACE e PSPACE, le classi probabilistiche, algoritmi probabilistici, algoritmi approssimanti. <br />
</li>
</ul>
</div>
</div>
Bibliografia
<ol>
<li>C. H. Papadimitriou, Computational Complexity, Addison Wesley, 1995. <br />
</li>
<li>D. Gusfield, Algorithms on String, Trees, and Sequences: Computer science <br />
and Computational Biology Cambridge University Press, 1997.</li>
<li>A. Bernasconi, B. Codenotti, Introduzione alla Complessita Computazionale, McGraw-Hill, 1998. <br />
</li>
</ol>
