FPprogramma0910 < Algoritmi2

Tags: view all tags

<H1>Progettazione di Algoritmi a.a. 2012-2013</H1>


<H2>Obiettivi</H2>
<DIV style="margin-left:5%; margin-right:10%">
<DIV ALIGN="justify">
<p>
Il corso ha l'obiettivo di presentare idee e tecniche per la progettazione e realizzazione 
di software efficiente ed elegante. In particolare tali idee e tecniche sono sfruttate in 
quelle parti di importanti sistemi software (sistemi operativi, compilatori/interpreti, 
DBMS, ecc.) che devono fornire elevate prestazioni. Enfasi &egrave; posta nella definizione 
e nella dimostrazione rigorosa delle propriet&agrave; dei concetti presentati (algoritmi e 
strutture dati). Il programma del corso si sviluppa in base alle principali tecniche 
algoritmiche (Greedy, Divide et Impera, Programmazione Dinamica e Backtracking) che sono 
esemplificate tramite numerosi esempi. I problemi considerati hanno maggiore importanza 
come esempi di applicazione di una certa tecnica che per il loro interesse intrinseco.
</p>
</DIV>
</DIV>

<H2>Programma</H2>
<DIV style="margin-left:5%; margin-right:10%">
<DIV ALIGN="justify">
<p>
Per ogni algoritmo nel programma &egrave; data una dimostrazione 
di correttezza e valutata la complessit&agrave; di possibili implementazioni. 
Alla fine di ogni argomento sono elencati i testi consigliati in ordine di rilevanza. Gli appunti 
saranno pubblicati durante lo svolgimento del corso.
</p>

<H3><B>Grafi</B></H3>
<p>
Rappresentazione tramite matrici di adiacenza o liste di adiacenza. Visite in ampiezza 
e visite in profondit&agrave;. Alberi di copertura, alberi dei cammini minimi, componenti 
fortemente connesse e ordinamento topologico. Cammini minimi in grafi orientati aciclici. 
</p>
<p>
[Testo 1: Cap. 3, 4. Testo 3: Cap. 22, 23. Testo 5: Cap. 12.]
</p>

<H3><B>Greedy</B></H3>
<p>
Descrizione generale della tecnica. Algoritmi per la pianificazione  di intervalli. Algoritmo per la 
pianificazione che minimizza il ritardo. Il problema dei cammini minimi: algoritmo di 
Dijkstra. Il problema del minimo albero di copertura: algoritmo di Prim ed algoritmo di 
Kruskal, strutture dati per insiemi disgiunti. Codici di Huffman. Algoritmi di 
approssimazione e quantificazione dell'errore. Il problema della copertura tramite vertici. 
</p>
<p>
[Appunti del corso. Testo 1: Cap. 4, 5. Testo 3: Cap. 16, 21, 23, 24. Testo 4: Cap. 4, 11.]
</p>      

<H3><B>Divide et Impera</B></H3>
<p>
Descrizione generale della tecnica. Il problema della somma di sottovettori. Algoritmo per la ricerca 
della coppia di punti pi&ugrave; vicini. Il problema della selezione. 
</p>
<p>
[Appunti del corso. Testo 1: Cap. 2. Testo 4: Cap. 5. Testo 5: Cap. 5, 10.]
</p>

<H3><B>Programmazione Dinamica</B></H3>
<p>
Descrizione generale della tecnica e confronto con Divide et Impera. Algoritmo per il 
problema della pi&ugrave; lunga sottosequenza comune. Distanza tra stringhe. 
Associativit&agrave; del prodotto di matrici. Come passare dal valore ottimo alla 
soluzione ottima. Il problema dei cammini minimi con pesi anche negativi: algoritmo di 
Bellman-Ford, algoritmo di Floyd e Warshall. Applicazioni: sistemi di vincoli di differenza. 
Algoritmi pseudopolinomiali: il problema dello zaino a variabili intere. 
</p>
<p>
[Appunti del corso. Testo 1: Cap. 6. Testo 2: Cap. 5. Testo 3: Cap. 15, 24, 25. Testo 4: Cap. 6. Testo 5: Cap. 10.]
</p>

<H3><B>Backtracking</B></H3>
<p>
Descrizione generale della tecnica. Enumerazione di strutture semplici: sottoinsiemi, 
sequenze, permutazioni. Generazione delle possibili soluzioni di un problema: cammini, 
cammini hamiltoniani, colorazioni. Euristiche di taglio: il problema dello zaino. 
</p>
<p>
[Appunti del corso. Test 1: Cap. 9. Testo 2: Cap. 7.]
</p>

<H3><B>Calcolabilit&agrave; e Complessit&agrave;</B></H3>
<p>
Automi a stati finiti. Macchine di Turing. Linguaggi ricorsivamente enumerabili. 
Linguaggi ricorsivi e linguaggi indecidibili. Indecidibilit&agrave; del problema della 
fermata. Riduzione tra linguaggi. La classe NP. La congettura su P ed NP. Problemi NP-completi. 
Riduzione polinomiale tra linguaggi. 
</p>
<p>
[Appunti del corso. Testo 1: Cap. 8. Testo 3: Cap. 34]
</p>
</DIV>
</DIV>



<H2>Testi consigliati</H2>

<DIV style="margin-left:5%; margin-right:10%">
<DIV ALIGN="justify">
<OL>
<LI>                                                                
  <P><FONT COLOR="#3c0eb7">  
<a href="http://highered.mcgraw-hill.com/sites/0073523402/">
S. Dasgupta, C. Papadimitriou, U. Vazirani &nbsp;&nbsp;&nbsp;&nbsp;  <i>Algorithms</i></a>&nbsp;&nbsp; 
Mac Graw-Hill 2007. Disponibile anche online: 
<a href="http://www.cs.berkeley.edu/~vazirani/algorithms.html">Algorithms</a></FONT></P>
</LI>
<LI>                                                                
<P><FONT COLOR="#3c0eb7">  
E. Horowitz, S. Sahni &nbsp;&nbsp;&nbsp;&nbsp; <i>Fundamentals of Computer Algorithms</i>&nbsp;&nbsp; 
Computer Science Press.</FONT></P>
</LI>
<li><p><FONT COLOR="#3c0eb7">  
<a href="http://www.ateneonline.it/cormen/">T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein
&nbsp;&nbsp;&nbsp;&nbsp; <i>	
Introduzione agli algoritmi e strutture dati</i></a>
&nbsp;&nbsp; Mac Graw-Hill 2005.</font></p>
</li>
<li><p><FONT COLOR="#3c0eb7">  
<a href="http://www.aw-bc.com/info/kleinberg/"> J. Kleinberg, E. Tardos &nbsp;&nbsp;&nbsp;&nbsp; <i> Algorithm Design</i></a>
&nbsp;&nbsp; Addison Wesley, 2005.</font></p>
</li>
<li><p><FONT COLOR="#3c0eb7">  
<a href="http://www.ateneonline.it/demetrescu2e/homeA.asp"> C. Demetrescu, I. Finocchi, G.F. Italiano 
&nbsp;&nbsp;&nbsp;&nbsp; <i>Algoritmi e Strutture di Dati</i></a>
&nbsp;&nbsp; Mac Graw-Hill 2008.</font></p>
</li>
</OL>
</DIV>
</DIV>