IAdiario0809 < Intro_algo/PZ

Tags: view all tags
<H1>Introduzione agli Algoritmi a.a. 2008-2009<BR><SMALL>(canale P-Z)</SMALL></H1>

<H2>Diario delle lezioni e delle esercitazioni</H2>

<DIV ALIGN="justify">
<B>Gioved&igrave; 26 febbraio 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Informazioni generali sul corso. Brevissima panoramica degli argomenti del corso. Gli obbiettivi della 
disciplina che si occupa degli algoritmi. Analisi dell'efficienza degli algoritmi: discussione delle 
problematiche relative alla valutazione dell'efficienza. Analisi del tempo di esecuzione di semplici 
algoritmi (somma dei valori di un vettore e ricerca di un valore in un vettore): indipendenza dalle 
caratteristiche della macchina. Tempo di calcolo in funzione della dimensione dell'input.
Analisi nei casi migliore, peggiore e medio.
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Marted&igrave; 3 marzo 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Esempio di due algoritmi per lo stesso problema e confronto diretto delle 
rispettive valutazioni asintotiche di complessit&agrave; temporale.
Ordini asintotici O(f(n)), &Omega;(f(n)) e &Theta;(f(n)). Propriet&agrave;
e esempi.
<BLOCKQUOTE>
<B>Esercizio 1</B>&nbsp;&nbsp;&nbsp;&nbsp;
n&radic;n &isin; O(n)? &nbsp;&nbsp; n&radic;n  &isin; O(n<SUP>2</SUP>)? &nbsp;&nbsp; 
2<SUP>n</SUP> &isin; &Omega;(n<SUP>1000</SUP>)? &nbsp;&nbsp; 2<SUP>n</SUP> &isin; 
O(3<SUP>n/2</SUP>)? &nbsp;&nbsp; 2<SUP>n</SUP> &isin; &Theta;(2<SUP>n + log n</SUP>)?
</BLOCKQUOTE>
</DIV>
<DIV ALIGN="justify">
<B>Gioved&igrave; 5 marzo 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Discussione esercizio 1. Ordine asintotico di un polinomio. Confronto tra polinomi ed esponenziali.
Analisi asintotica della complessit&agrave; di algoritmi ricorsivi: fattoriale e numeri di fibonacci.
Equazioni di ricorrenza. Risoluzione tramite iterazione.
<BLOCKQUOTE>
<B>Esercizio 2</B>&nbsp;&nbsp;&nbsp;&nbsp;
Analizzare la complessit&agrave; asintotica del seguente programma che implementa
una versione ricorsiva del selection-sort:
<PRE>
    int Ssort(int A[], int n) {
        if (n >= 2) {
            int i, imin = 0;
            for (i = 1 ; i < n ; i++)
                if (A[i] < A[imin]) imin = i;
            SWAP(A[0], A[imin])
            Ssort(A + 1, n - 1);
        }
    }
</PRE>
</BLOCKQUOTE>
</DIV>
<DIV ALIGN="justify">
<B>Marted&igrave; 10 marzo 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Esercitazione: discussione esercizio 2, analisi bubble-sort ricorsivo
ed esercizi di analisi asintotica.
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Gioved&igrave; 12 marzo 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Come semplificare una equazione di ricorrenza con due o pi&ugrave; termini
 per ottenere delimitazioni inferiori e superiori alla crescita asintotica 
della soluzione. Analisi della ricerca binaria (ricorsiva).
<BLOCKQUOTE>
<B>Esercizio 3</B>&nbsp;&nbsp;&nbsp;&nbsp;
Analizzare la complessit&agrave; asintotica del seguente programma che implementa
una variante ricorsiva del insertion-sort:
<PRE>
    int sort2(int A[], int n) {
        if (n >= 2) {
            sort2(A, n - 2);
            if (A[n-1] < A[n-2]) SWAP(A[n-1], A[n-2])
            int k1 = A[n-1], k2 = A[n-2];
            int i = n - 3;
            while (i >= 0 && k1 < A[i]) {
                A[i+2] = A[i];
                i--;
            }
            A[i+2] = k1;
            while (i >= 0 && k2 < A[i]) {
                A[i+1] = A[i];
                i--;
            }
            A[i+1] = k2;
        }
    }
</PRE>
</BLOCKQUOTE>
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Marted&igrave; 17 marzo 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Discussione esercizio 3. Algoritmo di ordinamento merge-sort: descrizione e 
analisi della complessit&agrave;.
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Gioved&igrave; 19 marzo 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Algoritmo di ordinamento quick-sort: descrizione, analisi della complessit&agrave;
nei casi migliore e peggiore, cenni sulla complessit&agrave; nel caso medio.
Albero di ricorsione: merge-sort e quick-sort con partizioni sbilanciate.
<BLOCKQUOTE>
<B>Esercizio 4</B>&nbsp;&nbsp;&nbsp;&nbsp;
Definire un algoritmo di ordinamento che &egrave; una versione
ternaria del merge-sort: il vettore &egrave; partizionato in tre parti
(uguali o quasi uguali) e poi le tre parti sono ordinate tramite
una versione ternaria dell'algoritmo di merge. Analizzare
la complessit&agrave; dell'algoritmo.
</BLOCKQUOTE>
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Marted&igrave; 24 marzo 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Sospensione della didattica: seminario del Prof. Madhu Sudan.
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Gioved&igrave; 26 marzo 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Esercitazione: discussione esercizio 4, mergesort k-ario, ricerca binaria (problemi 2.9 e 2.10).
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Marted&igrave; 31 marzo 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Teorema fondamentale delle ricorrenze (solo enunciato). Delimitazione inferiore sul numero di
confronti per algoritmi di ordinamento basati su confronti: albero delle decisioni. Counting-sort:
descrizione ed analisi. Code con priorit&agrave;: analisi di implementazioni tramite liste e vettori.
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Gioved&igrave; 2 aprile 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Alberi binari (terminologia). Struttura dati <EM>heap</EM>. Descrizione delle operazioni
di inserimento, estrazione del massimo, modifica e cancellazione. Analisi della complessit&agrave;.
Inizio di implementazione di una coda con priorit&agrave; tramite heap: procedure <CODE>heapUp()</CODE>
e <CODE>heapDown()</CODE>.
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Marted&igrave; 7 aprile 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Code con priorit&agrave; tramite heap: implementazione delle operazioni di inserimento, estrazione del massimo, modifica della priorit&agrave; e cancellazione. L'algoritmo di ordinamento heap-sort: analisi della complessit&agrave;.
Procedura di costruzione di un heap tramite <CODE>heapDown()</CODE> e analisi della complessit&agrave;.
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Gioved&igrave; 16 aprile 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Esercizi di preparazione alla prova intermedia.
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Marted&igrave; 28 aprile 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Definizioni e propriet&agrave; di alberi: 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: visita posticipata per valutare una espressione.
<BR>
Dizionari: operazioni fondamentali. Discussione di possibili implementazioni tramite
vettori e liste, ordinati e non.
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Gioved&igrave; 30 aprile 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Alberi binari di ricerca. Operazioni di ricerca, inserimento e rimozione: analisi
della complessit&agrave; e implementazione. Descrizione della procedura 
per trovare il predecessore (e il successore).
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Marted&igrave; 5 Maggio 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Esercitazione: procedure per trovare il predecessore e il successore di un nodo
in un albero binario di ricerca. Visita anticipata, posticipata e simmetrica. 
Descrizione della procedura per il calcolo dell' altezza di un albero k-ario 
rappresentato come albero binario.
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Gioved&igrave; 7 Maggio 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Alberi binari di ricerca bilanciati: alberi AVL. 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.
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Marted&igrave; 12 Maggio 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Implementazione delle operazioni di rotazione. Procedura di ribilanciamento a seguito
di una eliminazione: descrizione e dimostrazione di correttezza.
<BR>
Introduzione alle tabelle Hash.
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Gioved&igrave; 14 Maggio 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Tabelle hash. 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.
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Marted&igrave; 19 Maggio 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Esercitazione: Tabelle hash. Hashing perfetto. Alberi AVL. Ordinamento di un vettore tramite 
un generico albero binario di ricerca  ed un albero AVL.
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Gioved&igrave; 21 Maggio 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Esempi di grafi. Definizioni di base: grafi diretti e non diretti, adiacenza, grado, cammini e
cicli. Connessione: componenti connesse.
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Marted&igrave; 26 Maggio 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
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.
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Gioved&igrave; 28 Maggio 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Implementazione di grafi tramite liste di adiacenza. Implementazione della visita in ampiezza e 
della visita in profondit&agrave;. Applicazioni: componenti connesse e cammini minimi.
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Gioved&igrave; 4 giugno 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Esercizi di preparazione alla prova scritta: da [Esercizio_1] a [Esercizio_10] disponibili 
[[http://twiki.di.uniroma1.it/pub/Intro_algo/PZ/WebHome/IAeserciziSP.html][qui]].
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Marted&igrave; 9 giugno 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Esercizi di preparazione alla prova scritta: da [Esercizio_11] a [Esercizio_20] disponibili 
[[http://twiki.di.uniroma1.it/pub/Intro_algo/PZ/WebHome/IAeserciziSP.html][qui]].
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Gioved&igrave; 11 giugno 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Esercizi di preparazione alla prova scritta:  
[[http://twiki.di.uniroma1.it/pub/Intro_algo/PZ/WebHome/provaScritto110609.html][esercizi]] e [[http://twiki.di.uniroma1.it/pub/Intro_algo/PZ/WebHome/provaScritto110609sol.html][soluzioni]].
</DIV>
<BR>
<DIV ALIGN="justify">
<B>Marted&igrave; 16 giugno 2009</B>&nbsp;&nbsp;&nbsp;&nbsp;
Esercizi di preparazione alla prova scritta: [Esercizio_21], [Esercizio_22], [Esercizio_23],
[Esercizio_24] disponibili 
[[http://twiki.di.uniroma1.it/pub/Intro_algo/PZ/WebHome/IAeserciziSP.html][qui]].
</DIV>