IAprogramma < Intro_algo/PZ

Tags: view all tags

<H1>Introduzione agli Algoritmi a.a. 2008-2009 <SMALL>(canale P-Z)</SMALL></H1>
<BR>
<H2>Prerequisiti e propedeuticit&agrave;</H2>
<DIV style="margin-left:5%; margin-right:10%">
<DIV ALIGN="justify">
Si presuppongono una conoscenza di base di analisi matematica (studio di funzioni ed equazioni numeriche) ed 
una buona conoscenza di un linguaggio di programmazione come C, Java o C++. Non ci sono propedeuticit&agrave;. 
Tuttavia &egrave; consigliabile aver superato, o almeno frequentato, il corso di Fondamenti di Programmazione.
</DIV>
</DIV>
<BR>
<H2>Programma breve</H2>
<DIV style="margin-left:5%; margin-right:10%">
<DIV ALIGN="justify">
Strutture dati fondamentali (pile, code, code con priorit&agrave;). Principali algoritmi di ordinamento e ricerca. 
Alberi binari di ricerca e tabelle hash: rappresentazione in memoria e algoritmi per la ricerca, la cancellazione 
e l'inserimento di un elemento. Metodi per l'analisi asintotica delle risorse di calcolo utilizzate da algoritmi 
iterativi e ricorsivi.
</DIV>
</DIV>
<BR>
<H2>Programma dettagliato</H2>
<DIV style="margin-left:5%; margin-right:10%">
<DIV ALIGN="justify">
<H3><B>Analisi asintotica della complessit&agrave; di calcolo</B></H3>
Discussione delle problematiche relative alla valutazione dell'efficienza di programmi/algoritmi:
indipendenza dalle caratteristiche della macchina; tempo di calcolo in funzione della dimensione 
dell'input; analisi nei casi migliore, peggiore e medio. 
Ordini asintotici O(f(n)), &Omega;(f(n)) e &Theta;(f(n)) e loro propriet&agrave;.
Analisi asintotica della complessit&agrave; di algoritmi ricorsivi.
Equazioni di ricorrenza: risoluzione tramite iterazione; albero di ricorsione.
Teorema fondamentale delle ricorrenze (solo enunciato). 
<H3><B>Algoritmi di ordinamento</B></H3>
Algoritmo di ordinamento <em>merge-sort</em>: descrizione e analisi della complessit&agrave;.
Algoritmo di ordinamento <em>quick-sort</em>: descrizione, analisi della complessit&agrave; nei 
casi migliore e peggiore, cenni sulla complessit&agrave; nel caso medio.
Delimitazione inferiore sul numero di confronti per algoritmi di ordinamento basati 
su confronti: albero delle decisioni. <em>Counting-sort</em>: descrizione ed analisi. 
L'algoritmo di ordinamento <em>heap-sort</em>: analisi della complessit&agrave;.
<H3><B>Strutture dati basate su alberi</B></H3>
Definizioni e propriet&agrave; di <em>alberi</em>: ordine, altezza e numero di nodi. Alberi ordinati e non. 
Alberi binari. Rappresentazione di un albero <em>m</em>-ario tramite un albero binario. 
Rappresentazione in memoria di alberi: strutture linkate e vettore dei padri. 
Visite di alberi.
<br>
&nbsp;&nbsp;&nbsp;&nbsp; Struttura dati <em>heap</em>. Descrizione delle operazioni di inserimento, estrazione 
del massimo, modifica e cancellazione. Analisi della complessit&agrave;.
Implementazione di una <em>coda con priorit&agrave;</em> tramite heap: confronto con
implementazioni tramite liste e vettori.
<br>
&nbsp;&nbsp;&nbsp;&nbsp; <em>Alberi binari di ricerca</em>. Operazioni di ricerca, inserimento e rimozione: analisi 
della complessit&agrave; e implementazione.
Alberi binari di ricerca bilanciati: <em>alberi AVL</em>. Dimostrazione che un albero 
AVL ha altezza O(log<em>n</em>). Operazioni di rotazione. Procedura di ribilanciamento 
a seguito di un inserimento: descrizione e dimostrazione di correttezza.
Procedura di ribilanciamento a seguito di una rimozione: descrizione e 
dimostrazione di correttezza. 
<br>
&nbsp;&nbsp;&nbsp;&nbsp; Implementazione di <em>Dizionari</em> tramite strutture dati basate su alberi: confronto
con implementazioni tramite vettori e liste, ordinati e non. 
<H3><B>Tabelle Hash</B></H3>
Universo delle chiavi e funzioni hash. Il problema delle collisioni. Hashing con liste di trabocco 
(o liste di collisione). Cenni sulla complessit&agrave; nel caso ideale. Hashing interno 
(o indirizzamento aperto): sequenze di scansione, scansione lineare (fenomeni di agglomerazione) 
e hashing doppio. Operazione di eliminazione. Cenni sulla complessit&agrave; nel caso ideale.
<br>
&nbsp;&nbsp;&nbsp;&nbsp; Implementazione di Dizionari tramite tabelle hash: confronto con
implementazioni tramite alberi.
<H3><B>Grafi</B></H3>
Definizioni di base: grafi diretti e non diretti, adiacenza, grado, cammini e cicli. 
Connessione: componenti connesse. Visite di grafi: visita in profondit&agrave; e visita in ampiezza. 
Uso delle visite per determinare le componenti connesse di grafi non diretti. Alberi di visita. 
Rappresentazioni di grafi: liste di adiacenza e matrici di adiacenza.
Uso della visita in ampiezza per trovare i cammini minimi.
</DIV>
</DIV>
<BR>
<H2>Testi consigliati</H2>
<DIV style="margin-left:5%; margin-right:10%">
<DIV ALIGN="justify">
<UL>
<LI>                                                                
C. Demetrescu, I. Finocchi, G.F. Italiano, <i>Algoritmi e Strutture Dati</i>, 
Mc Graw Hill, seconda edizione, 2008.
</LI>
<LI>                                                                
T.H. Cormen, C.E. Leiserson, R.L. Rivest e C. Stein, <i>Introduction to Algorithms</i>, 
second edition, MIT Press e Mc Graw Hill, 2001.
</LI>
</UL>
</DIV>
</DIV>