AnniPrecedenti < Info

Tags: view all tags
---+ Diario delle lezioni degli Anni precedenti

---+++ <font color="red" size="+1"> *A.A. 2018/2019* </font>

*%BLUE% Lunedì 25 Febbraio 2019 - Lezioni 1-2*

Introduzione sull'importanza della valutazione dei corsi di studio (a cura del presidente di CAD)

*Introduzione (1)*
   * Informazioni sul corso.
   * Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale.
%ENDCOLOR%

%BLACK%
*Mercoledì 27 febbraio 2019 - Esercitazioni 1-2*
   * ==TinyC==. Codifica in ==TinyC== del programma che calcola la *somma* iterando +1 [ *D1*, sezione *2* ]
   * Indagini su un programma iterativo [ *L1*, sez. *2.1* ]:
      * Precondizioni, Postcondizioni, invarianti di ciclo.
      * Terminazione di un ciclo: funzione di terminazione.
   * *Esempi*:
      * funzione che calcola la *moltiplicazione*. Uso della funzione somma nel calcolo del prodotto [ *D1*, sez. *3* ].
      * funzione che calcola il *predecessore*. Specifica come contratto.
      * funzione che calcola il *minore o uguale*.

   * *Esercizi consigliati*: Dispensa *L1*, sez. *2.5*, esercizi da 2 a 8.
   * *Sperimentazioni*: Disp. *D1*, sez. *2.1*.
%ENDCOLOR%

*%BLUE% Venerdì 1 Marzo 2019 - Lezioni 3-4*

*Introduzione (2)*
   * Modello RAM; misura di costo uniforme e logaritmico.

*Notazione asintotica (1)*
   * Definizione e significato degli insiemi O, &Omega; e &Theta;
   * Metodo del limite
   * Algebra della notazione asintotica
   * Esempi

*Esercizi assegnati:*
   * Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione
   * Calcolare l'ordine asintotico stretto di alcune funzioni assegnate.
%ENDCOLOR%

*%BLUE% Lunedì 4 Marzo 2019   - Lezioni 5-6*

*Notazione asintotica (2)*
   * Pseudocodice
   * Valutazione del costo computazionale di un algoritmo
   * Un primo esempio
   * Esempi di problemi che si possono risolvere in modo più o meno efficiente e loro costo computazionale
      * somma dei primi n interi
      * valutazione di un polinomio in un punto

*Il problema della ricerca (1)*
   * ricerca sequenziale e suo costo computazionale nel caso migliore e peggiore
   * ricerca dicotomica e suo costo computazionale nel caso migiore e peggiore

*Esercizi assegnati:*
   * Calcolare il costo computazionale del Selection, dell'Insertion Sort e del Bubble Sort (pseudocodice sulle dispense)
%ENDCOLOR%

%BLACK%
*Mercoledì 6 Marzo 2019 - Esercitazioni 3-4*

   * Usando l'esempio del predecessore, revisione delle asserzioni logiche: precondizioni, postcondizioni, invarianti, funzioni di terminazione.
   * Progetto di funzioni a partire dalle specifiche logiche [ *L1*, sez. *2.3* ].
      * Esempio: divisione intera.
   * Uso di passaggi *per riferimento* per passare più risultati: funzione ==int divRef(int, int, int*, int*)==.
   * Utilizzo della funzione ==divRef== nell'algoritmo ==mcdMaestra== [ *D1*, sez. *4* ].

   * *Esercizi consigliati*: Dispensa *L1*, sez. *2.5*, esercizi da 2 a 8.
%ENDCOLOR%

<b>%RED% Venerdì 8 Marzo 2019 </b>
Lezioni sospese per le Olimpiadi di Matematica (aule occupate)%ENDCOLOR%

%BLACK%
*Lunedì 11 marzo 2019 - Esercitazioni 5-6* %ENDCOLOR%

   * Ancora sui passaggi per riferimento: funzione ==scambia(int*,int*)==
   * Passaggio di parametri: *call-by-value*: impossibilità di scrivere una funzione ==myAnd== equivalente all'operatore ==&&== predefinito.
   * Call-by-value, funzione ==ap(int*,int*,int,int)== (assegnamento parallelo à la Python) [ *D2*, sez. *2* ].
   * I problemi di *alias*: funzione ==scambia(int*,int*)== senza variabile di appoggio [ *D2*, sez. *3* ].
   * Induzione e Ricorsione: definizione induttiva di + e funzione ==sommaRec(int, int)== [ *D3*, sez. *1.1* ].
   * Esercizio: predecessore ricorsivo in ==TinyReC==. Riflessioni sulla completezza computazioneale di ==TinyReC==.
   * Ricorsione: funzione di Fibonacci. Efficienza e albero delle chiamate generato.

   * *Esercizi consigliati*: Dispensa *D2* [sez. *4* ]
   * *Esercizi consigliati*: Dispensa *D3* [sez. *1.3* ]
%ENDCOLOR%

*%BLUE% Mercoledì 13 Marzo 2019 - Lezioni 7-8*

   * Calcolare l'andamento asintotico di alcune funzioni ed alcune sommatorie
   * Esempio pratico di funzionamento dei due algoritmi di ricerca
*Ricorsione*
   * ricerca sequenziale e binaria: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;

*Esercizi assegnati:*
   * Progettare degli algoritmi ricorsivi ed esprimerli tramite pseudocodice che risolvano i seguenti problemi:
      * dato in input un vettore, visualizzare i suoi valori al contrario (dall'ultimo al primo)
      * dato un intero n, calcolare la somma di n valori immessi da tastiera (uno per ogni chiamata ricorsiva)
      * calcolare il MCD tra due interi positivi x ed y come segue:
         * sia y<x
         * se y=0 allora MCD(x,y)=y
         * altrimenti MCD(x,y))MCD(y, x%y) (dove x%y indica il resto della divisione intera tra x e y)

%ENDCOLOR%

*%BLUE% Venerdì 15 Marzo 2019 - Lezioni 9-10*

Soluzioni delle equazioni di ricorrenza (1)

   * 4 metodi risolutivi (1/2):
      * metodo iterativo;
      * metodo di sostituzione;
      * metodo dell'albero.

*Esercizi assegnati:*
   * Calcolare la soluzione di alcune equazioni di ricorrenza
%ENDCOLOR%

*%BLUE% Lunedì 18 Marzo 2019 - Lezioni 11-12*

Soluzioni delle equazioni di ricorrenza (2)

   * 4 metodi risolutivi (2/2):
      * metodo principale: enunciato del teorema senza dimostrazione
   * soluzione di alcune equazioni di ricorrenza

*Esercizi assegnati:*
   * Calcolare la soluzione di alcune equazioni di ricorrenza
%ENDCOLOR%

%BLACK%
*Mercoledì 20 marzo 2019: Esercitazioni 7-8:* %ENDCOLOR%
   * Esecuzione della funzione ricorsiva di Fibonacci: evoluzione della pila di sistema.
   * Iterazione e ricorsione: Fibonacci iterativo efficiente. Trasformazione sistematica di un ciclo in una funzione ricorsiva.
   * Dimostrazioni di correttezza per programmi ricorsivi. [ *D3*, sez. *2* ]
   * Problemi con soluzione inerentemente ricorsiva: il problema della Torre di Hanoi [ *D3*, sez. *3* ]
   * *Soluzione Esonero 2014* sul tema: il problema del massimo fattore primo [ *S4* ]

   * *Esercizi consigliati*: Dispensa *3* [sez. *2.4* e *3.3* ]

*%BLUE% Venerdì 22 Marzo 2019 - Lezioni 13-14*

Soluzioni delle equazioni di ricorrenza (3)

   * Esercizi riepilogativi sulle equazioni di ricorrenza

*Esercizi assegnati:*
   * Calcolare la soluzione di alcune equazioni di ricorrenza
%ENDCOLOR%

*%BLUE% Lunedì 25 Marzo 2019 - Lezioni 15-16*

Il problema dell'ordinamento (1)
   * algoritmi naif: insertion sort, selection sort e bubble sort; calcolo del costo computazionale; algoritmi input sensitive
   * albero delle decisioni e teorema sulla limitazione inferiore per la complessità di un algoritmo per confronti
   * paradigma del divide et impera

*Esercizi assegnati:*

   * Nell'algoritmo dell'insertion sort, la ricerca della posizione in cui inserire l'elemento corrente può essere effettuata tramite una ricerca binaria. Calcolare il costo computazionale dell'algoritmo così modificato.
   * Scrivere in pseudocodice una funzione che, dato un vettore A ed un indice j, calcoli il valore minimo nel sottovettore A[j..n]. Riscrivere lo pseudocodice del selection sort che utilizzi ripetutamente questa funzione.
   * Modificare l'algoritmo di Bubble Sort in modo che non prosegua la computazione se il vettore risulta ordinato (con l'aggiunta di una flag).
   * Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (prima versione).
   * Determinare l'albero delle decisioni del Selection Sort.
%ENDCOLOR%

%BLACK%
*mercoledì 27 marzo 2019 - Esercitazioni 9-10*
   * Introduzione ai vettori in C: definizione e allocazione [ *D4*, sez. *1* ]. Passaggio di parametri vettori. Vettori e puntatori [ *D4*, sez. *1.1* ].
   * Un primo programma sui vettori: stampa di un vettore, iterativa e ricorsiva [ *D4*, sez. *1.1* ].
   * Un esempio di programma con asserzioni logiche: minimo di un vettore [ *D4*, sez. *2.1* ].
   * *Soluzione Esonero 2012*: il Problema del baricentro [ *S1* ].
   * *Virtuosismi*: Baricentro con un'unica scansione ricorsiva del vettore [ *S1* ].

   * *Esercizi consigliati*: Dispensa *4* [sez. *1.3* e *2.6* ],
   * *Lettura*: due grandi classici: crivello di Eratostene [ *D4*, sez. *2.4* ] e coefficienti binomiali [ *D4*, sez. *2.5* ].
%ENDCOLOR%

*%BLUE% Venerdì 29 Marzo 2019 - Lezioni 17-18*

Il problema dell'ordinamento (2)
   * algoritmi efficienti:
      * merge sort (pseudocodice e costo computazionale, pseudocodice della funzione Fondi, problematica dell'ordinamento in loco)
      * cosa non va nel merge sort: una parentesi sull'uso della memoria secondaria
      * quick sort (pseudocodice, pseudocodice e costo della funzione Partiziona, riflessioni sulla scelta del valore soglia, costo computazionale nei casi migliore e peggiore)

*Esercizi assegnati:*
   * Scrivere la funzione di fusione ricorsiva
   * Determinare l'albero delle decisioni della funzione di fusione, quando i vettori da fondere sono a1 a2 e b1 b2 (con l'implicita ipotesi che a1<a2 e b1<b2)
   * Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (di nuovo: ma questa volta il costo computazionale dovrebbe essere un O(n log n))
%ENDCOLOR%

<b>%BLUE% Lunedì 1 Aprile 2019 - Lezioni 19-20 </b>

Il problema dell'ordinamento (3)
   * algoritmi efficienti: 
      * funzionamento pratico del merge sort
      * quick sort (costo computazionale nel caso medio)
      * heapsort (una parentesi sulle strutture dati, struttura dati heap)

*Esercizi assegnati:*
   * Sia dato un vettore di lunghezza n contenente solo valori 0 e 2. Si progetti un algoritmo con costo computazionale lineare che modifichi il vettore in modo che tutte le occorrenze di 0 si trovino più a sinistra di tutte le occorrenze di 2.
   * Si considerino i valori 0 1 2 3 4 5 6 7. Si determini una permutazione di questi valori che generi il caso peggiore per l'algortimo Quick sort.
   * Calcolare il costo computazionale del Quick sort nel caso in cui il vettore contenga tutti elementi uguali.
%ENDCOLOR%

%BLACK%
*mercoledì 3 aprile 2019 - Esercitazioni 11-12*
   * *Soluzione Esonero 2018*: il problema del minimo intero libero [ *S7* ];
   * Vettori variabili (allocati *dentro* le funzioni e di dimensioni dipendenti da una variabile);
   * Vettori dinamici (allocati con ==malloc== o ==calloc== ). Il tipo ==void *==
   * Esempio: il Crivello di Eratostene.
   * Un aiutino sull'Homework, esercizio *3*: il problema delle partizioni [ *S3*, sez. *1* ]

   * *Esercizi consigliati*: Dispensa *4* [sez. *1.3* e *2.6* ],
%ENDCOLOR%

<b>%BLUE% Venerdì 5 Aprile 2019 - Lezioni 21-22 </b>

 Il problema dell'ordinamento (4)
   * algoritmi efficienti
      * heapsort (Heapify: pseudocodice e costo computazionale; Build Heap: pseudocodice e costo; Heapsort: pseudocodice e costo)
   * algoritmi lineari
      * counting sort (versione semplificata e versione completa)
%ENDCOLOR%

<b>%BLUE% Lunedì 8 Aprile 2019 - Lezioni 23-24 </b>

 Il problema dell'ordinamento (5)
   * algoritmi lineari
      * bucket sort (idea)
   * alcuni approfondimenti sugli algoritmi di ordinamento (algoritmo di cancellazione su un heap, costo di Heapify come funzione di n e dimostrazione del costo lineare di Build Heap) 
%ENDCOLOR%

%BLACK%
*mercoledì 10 aprile 2019 - Esercitazioni 13-14*
   * *Soluzione Esonero 2016*: generazione delle combinazioni di _n_ oggetti presi _k_ a _k_ [ *S5* ]
   * Vettori bidimensionali: allocazione statica [ *D5*, sez. *2* ].
   * Allocazione di una matrice dinamica [ *D5*, sez. *3* ].
   * *Virtuosismi*: funzione ==mergeRecVPC==: merge ricorsiva da Veri Programmatori C [ *L2* ]. 

   * *Esercizi consigliati*: Di tutto un po', su vettori e ricorsione, dispensa *D3* e *D4*.
%ENDCOLOR%


<b>%BLUE% Venerdì 12 Aprile 2019 - Lezioni 25-26 </b>
   * Esercizi in vista dell'esonero
%ENDCOLOR%

<b>%RED% Vacanze di Pasqua, ponti del 25 Aprile e 1 Maggio %ENDCOLOR%</b>


<b>%BLUE% Lunedì 29 Aprile 2019 - Lezioni 27-28 </b>

   * Strutture dati fondamentali (1)
      * strutture dati ed insiemi dinamici
      * confronto tra vettore qualunque e vettore ordinato
      * introduzione alle liste: ricerca e inserimento in testa
      * cancellazione nelle liste, liste doppiamente puntate
      * pila
      * le operazioni Push e Pop
 %ENDCOLOR%

<b>%BLUE% Venerdì 3 Maggio 2019 - Lezioni 29-30 </b>

   * Correzione compito d'esonero
   * Strutture dati fondamentali (2)
      * code con priorità
      * la struttura dati coda
      * le operazioni enqueue e dequeue
      * Esercizio: simulazione di una coda tramite due pile
      * alberi (1)
         * definizione tramite la nozione di grafo

*Esercizi assegnati:*
   * scrivere sia lo pseudocodice che il codice C delle funzioni Enqueue e Dequeue quando la coda sia circolare ed implementata su vettore
   * scrivere sia lo pseudocodice che il codice C delle funzioni Pop, Push e Pila_Piena quando la pila sia implementata su vettore
 %ENDCOLOR%

<b>%BLUE% Lunedì 6 Maggio 2019 - Lezioni 31-32 </b>

   * Strutture dati fondamentali (3)
      * alberi (2)
         * caratterizzazione degli alberi
         * memorizzazione degli alberi:
            * tramite record e puntatori
            * posizionale
            * tramite vettore dei padri
   * Visione Es. 1 e 3 compito d'esonero
 %ENDCOLOR%

%BLACK%
*Esercitazioni 15-16: mercoledì 8 maggio 2019*

   * Correzione esercizio 2 esonero.
   * Introduzione ai record: definizioni di ==struct==. [ *D6*, sez. *1* ]
   * Tipo di dato sequenza e sua definizione induttiva.
   * Rappresentazione in C delle sequenze: uso di ==struct== 'ricorsive' [dispensa *D6*, sez. *3* ].
   * Costruttori e distruttori del tipo sequenza.
   * Prime funzioni C su liste: ==length==, ==sumL== [dispensa *D6*, sez. *3.1* ].

   * *Esercizi consigliati*: i più semplici di quelli alla fine della dispensa *D6* .
%ENDCOLOR%

<b>%BLUE% Venerdì 10 Maggio 2019 - Lezioni 33-34 </b>
   * Strutture dati fondamentali (4)
      * alberi (3)
         * visite di alberi: in-ordine, pre-ordine e post-ordine
            * pseudocodice ricorsivo
            * costo computazionale tramite equazione di ricorrenza e metodo di sostituzione (sol. lasciata per esercizio)
            * esercizi che si risolvono utilizzando le visite
            * esercizi che si risolvono usando alberi, pile e code
 %ENDCOLOR%

<b>%BLUE% Lunedì 13 Maggio 2019 - Lezioni 35-36 </b>
   * Strutture dati fondamentali (5)
     * Alberi binari di ricerca (ABR) (1):
         * definizione e proprietà dell' "ordinamento orizzontale"
         * algoritmo per il massimo e minimo
         * algoritmo per il successore e predecessore
         * algoritmo di inserimento
         * osservazioni sul costo computazionale delle operazioni viste come funzione dell'altezza

   * SOMMINISTRAZIONE TEST DI VALUTAZIONE DEL CORSO

*Esercizi assegnati:*
   * Scrivere lo pseudocodice degli algoritmi per la ricerca del massimo e del minimo in un ABR
   * Scrivere lo pseudocodice degli algoritmi per la ricerca del predecessore e del successore in un ABR
%ENDCOLOR%


%BLACK%
*Esercitazioni 17-18: mercoledì 15 maggio 2019*

   * Inserzione di elementi in coda [dispensa *D6*, sez. *3.3* ]:
      * specifica con equazioni ricorsive,
      * versione iterativa ==addLastIt==,
      * ricorsiva ==addLastRec==,
      * con generazione di una nuova lista ==addLastFun== .
   * Concatenazione di liste [dispensa *D6*, sez. *3.4* ]:
      * specifica con equazioni ricorsive,
      * versioni 'mista' ==append==,
      * ricorsiva ==appendRec==,
      * con generazione nuove liste ==appendFun== .
   * Rovesciamento di liste [dispensa *D6*, sez. *3.5* ]:
      * specifica con equazioni ricorsive,
      * versione 'fun' inefficiente ==reverseFun==,
      * iterativa ==reverseIt==,
      * versione ricorsiva efficiente ==reverseFunEff== .
   * Rovesciamento di Liste _in place_: versione ricorsiva ==reverseRec== [dispensa *D6*, sez. *3.5* ].

   * *Esercizi consigliati*: reverse _in place_ iterativa (*virtuosismo*) e altri esercizi tra di quelli alla fine della dispensa *D6* .
%ENDCOLOR%

<b>%BLUE% Venerdì 17 Maggio 2019 - Lezioni 37-38 </b>
   * Strutture dati fondamentali (6)
      * Alberi binari di ricerca (ABR) (2):
         * algoritmo di cancellazione
         * alberi bilanciati: alberi rosso-neri
         * dimostrazione che gli alberi rosso-neri hanno altezza logaritmica
         * rotazioni
         * cenno all'operazione di inserimento 

*Esercizi assegnati:*
   * Dato due ABR T1 e T2, progettare un algoritmo che produca in output un terzo albero binario di ricerca T contenente le chiavi di T1 e di T2. Fare le considerazioni del caso riguardo al costo computazionale.
%ENDCOLOR%

<b>%BLUE%Lunedì 20 Maggio 2019 - Lezioni 39-40 </b>
   * Grafi (1)
      * Definizione e alcune proprietà
      * Rappresentazione in memoria di grafi:
         * liste di adiacenza
         * matrice di adiacenza
         * matrice di incidenza
         * lista di archi
         * confronto tra rappresentazioni
      * Visite di grafi
      * Alberi di visita

*Esercizi assegnati:*
   * Dato G memorizzato con una struttura dati X, dare in output G memorizzato con un'altra struttura dati Y, dove X ed Y variano in tutti i modi possibili tra le 4 rappresentazioni viste
%ENDCOLOR%

%BLACK%
*Esercitazioni 19-20: mercoledì 22 maggio 2019*
   * Eliminazione di elementi: ==removeFun== e ==removeRec== [dispensa *D6*, sez. *3.6* ].
   * Il problema della deallocazione di memoria dinamica: ==free()== [dispensa *D6*, sez. *2.1* ].
   * Eliminazione di elementi: ==removeIt==: attenzione a non perdere la testa (della lista)! [dispensa *D6*, sez. *3.6* ].
   * Esercizi da *esoneri/esami* passati: 
      * differenza simmetrica tra liste (ordinate). Attenzione alle versioni che modificano [Dispensa *S6*, sez. *1.3* ].
      * problema di determinare se una lista è palindroma

   * *Esercizi consigliati*: differenza tra liste, rimozione di duplicati [dispensa *D6*, sez. *3.6* ] e altri esercizi nella dispensa *S6* sezione *1*.
%ENDCOLOR%

<b>%BLUE%Venerdì 24 Maggio 2019 - Lezioni 41-42 </b>
   * Grafi (2)
      * Visita in ampiezza: filosofia, esempio, pseudocodice, costo computazionale in funzione della struttura dati usata, proprietà dell'albero di visita in ampiezza (archi di riporto vs. di attraversamento, cammini più corti)
      * Esempi di uso di visita in ampiezza: calcolo dei cammini più corti da un nodo dato

      * Visita in profondità: filosofia, esempio, pseudocodice, costo computazionale in funzione della struttura dati usata, proprietà dell'albero di visita in profondità (archi di riporto vs. di attraversamento)

%ENDCOLOR%

<b>%RED%Lunedì 27 Maggio 2019 - Lezioni sospese dal Rettore per le elezioni* </b>
%ENDCOLOR%

%BLACK%
*Esercitazioni 21-22: mercoledì 29 maggio 2019*
   * Introduzione agli alberi binari: definizione induttiva e rappresentazione in C [dispensa *D7*, sez. *1* e sez. *1.1* ].
   * Costruttori e distruttori: ==makeTree(int n, binTree L, binTree R)== e ==isNotEmptyTree(binTree B, int *r, binTree* L, binTree *R)== [ *D7*, sez. *1.1* ].
   * Funzioni base: numero di nodi, peso, profondità.
   * Stampare un albero binario: stampa a parentesi e indentata.
   * Produrre la lista di nodi. Versioni efficienti che usano solo aggiunte in testa.

   * *Esercizi consigliati*: vedi dispensa *D7*, sez. finale di esercizi.
%ENDCOLOR%

<b>%BLUE%Venerdì 31 Maggio 2019 - Lezioni 43-44 </b>
   * Grafi (3)
      * Esempi di uso di visita in profondità: calcolo delle componenti connesse
      * Esercizi su grafi: calcolo del grafo complemento e del quadrato di un grafo

*Esercizi assegnati:*
   * Dato un grafo G mediante le sue liste di adiacenza, progettare un algoritmo che dica se G è aciclico oppure no.
%ENDCOLOR%

%BLACK%
*Esercitazioni 23-24: lunedì 3 giugno 2019*
   * Alberi binari: visita per livelli [dispensa *D7*, sez. *1.3* ].
   * Discussione sull'equivalenza di tipi: equivalenza di struttura e per nome.
   * Il problema del bilanciamento: versioni naive e versioni efficienti con un'unica scansione dell'albero.
   * *Esoneri passati* 
      * il problema di restituire la lista dei nodi al livello _k_: funzione ==livelloK== [dispensa *S6*, sez. *2.2* ] 
      * il problema di determinare il cammino fino a un nodo _x_: funzione ==pathToX== [dispensa *S6*, sez. *2.3* ]
 
   * *Esercizi consigliati*: vedi dispensa *D7*, sez. finale di esercizi e dispensa *S6*.

<b>%BLUE%Mercoledì 5 Giugno 2019 - Lezioni 45-46 </b>
   * Grafi (4)
      * Grafi euleriani: definizione, teorema di Eulero, esercizio
      * Grafi bipartiti: definizione, caratterizzazione, esercizio
%ENDCOLOR%

<b>%BLUE%Venerdì 7 Giugno 2019 - Lezioni 47-48 </b>
   * Grafi (5)
      * Grafi planari e relazione di Eulero
      * Colorazione di grafi
      * Un'applicazione alle reti cellulari
%ENDCOLOR%

<b>%BLUE%Lunedì 10 Giugno 2018 - Lezioni 49-50 </b>
   * Esercizi in preparazione dell'esonero
%ENDCOLOR%


%BLACK%
*Esercitazioni 25-26: mercoledì 12 giugno 2019*
   * Ricostruzione di un albero binario avendo due visite (ad esempio, preorder e inorder).
   * *Esoneri passati* 
      * sostituire le etichette di un albero con la somma del sottoalbero
      * funzione che ordina una lista secondo l'algoritmo _selection sort_. Attenzione alla versione Fun!
      * deallocazione di un albero binario. Funzione che pruna un albero nella parte non crescente;
      * modificare una lista con la somma dei precedenti;
      * rappresentare i naturali con liste di puntatori.
 
   * *Esercizi consigliati*: vedi dispensa *S6*, con soluzioni agli esercizi di compiti passati.



---+++ <font color="red" size="+1"> A.A. 2017/2018</font>

<b>%BLUE% Venerdì 23 Febbraio 2018 - Lezioni 1-2 </b>

*Introduzione (1)*
   * Informazioni sul corso.
   * Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale.
   * Modello RAM; misura di costo uniforme e logaritmico.%ENDCOLOR%

<b>%RED% Lunedì 26 Febbraio 2018  </b>

Lezioni sospese per le condizioni meteo
%ENDCOLOR%

%BLACK%
*Esercitazioni 1-2: mercoledì 28 febbraio 2018* 
   * Problemi, classi di Problemi, Soluzioni [ *L1*, sezioni *1* e *2* ]
   * ==TinyC==. Codifica in ==TinyC== del programma che calcola la *somma* iterando +1 [ *D1*, sezione *2* ]
   * Indagini su un programma iterativo [ *L1*, sez. *2.1* ]:
      * Precondizioni, Postcondizioni, invarianti di ciclo.
      * Terminazione di un ciclo: funzione di terminazione.
   * *Esempi*:
      * funzione che calcola la *moltiplicazione*. Uso della funzione somma nel calcolo del prodotto [ *D1*, sez. *3* ].
      * funzione che calcola il *predecessore*. Specifica come contratto.
 
   * *Esercizi consigliati*: Dispensa *L1*, sez. *2.5*, esercizi da 2 a 8.
   * *Sperimentazioni*: Disp. *D1*, sez. *2.1*.
%ENDCOLOR%

<b>%BLUE% Venerdì 2 Marzo 2018 - Lezioni 3-4 </b>

*Introduzione (2)*
   * Esempio di calcolo del costo di un algoritmo con misura di costo uniforme e logaritmico.
*Notazione asintotica (1)*
   * Definizione e significato degli insiemi O, &Omega; e &Theta;
   * Metodo del limite
   * Algebra della notazione asintotica
   * Esempi
   * Pseudocodice

*Esercizi assegnati:*
   * Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione
   * Calcolare l'ordine asintotico stretto di alcune funzioni assegnate.
%ENDCOLOR%

<b>%RED% Lunedì 5 Marzo 2018  </b>

Lezioni sospese per le elezioni%ENDCOLOR%

<b>%RED% Mercoledì 7 Marzo 2018  </b>

Lezioni sospese per le Olimpiadi di Matematica (aule occupate)%ENDCOLOR%

<b>%BLUE% Venerdì 9 Marzo 2018 - Lezioni 5-6 </b>

*Notazione asintotica (2)*
   * Valutazione del costo computazionale di un algoritmo
   * Un primo esempio
   * Esempi di problemi che si possono risolvere in modo più o meno efficiente e loro costo computazionale
      * somma dei primi n interi
      * valutazione di un polinomio in un punto

*Il problema della ricerca (1)*
   * ricerca sequenziale e suo costo computazionale nel caso migliore e peggiore

*Esercizi assegnati:*
   * Calcolare l'andamento asintotico di alcune funzioni ed alcune sommatorie
   * Calcolare il costo computazionale del Selection, dell'Insertion Sort e del Bubble Sort (pseudocodice sulle dispense)
%ENDCOLOR%

<b>%BLUE% Lunedì 12 Marzo 2018 - Lezioni 7-8 </b>

*Il problema della ricerca (2)*
   * ricerca dicotomica e suo costo computazionale nel caso migiore e peggiore

*Ricorsione*
   * funzioni matematiche ricorsive;
   * ricerca sequenziale e binaria: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;

*Esercizi assegnati:*
   * Progettare degli algoritmi ricorsivi ed esprimerli tramite pseudocodice che risolvano i seguenti problemi:
      * dato in input un vettore, visualizzare i suoi valori al contrario (dall'ultimo al primo)
      * calcolare il MCD tra due interi positivi x ed y come segue:
         * sia y<x
         * se y=0 allora MCD(x,y)=y
         * altrimenti MCD(x,y))MCD(y, x%y) (dove x%y indica il resto della divisione intera tra x e y)
%ENDCOLOR%

%BLACK%
*Esercitazioni 3-4: mercoledì 14 marzo 2018* %ENDCOLOR%

   * Funzione ==compareTo== che confronta due numeri naturali. Osservazioni sulla complessità dei programmi ==TinyC==.
   * Progetto di funzioni a partire dalle specifiche logiche [ *L1*, sez. *2.3* ]. 
      * Esempio: divisione intera.
   * Introduzione alla pila di sistema, variabili locali, globali [ *D1*, sez. *3* ].
   * Uso di passaggi *per riferimento* per passare più risultati: funzione ==int divRef(int, int, int*, int*)==.
   * Utilizzo della funzione ==divRef== nell'algoritmo ==mcdMaestra== [ *D1*, sez. *4* ].
   * Valutazione dei parametri: impossibilità di scrivere una funzione ==myAnd== equivalente a ==&&==.

   * *Esercizi consigliati*: Dispensa *L1*, sez. *2.5*, esercizi da 2 a 8.
   * *Elucubrazioni*: Inutilità dell' ==if== in ==TinyC==. Altri esercizi in Disp. *D1*, sez. *1.2*.

<b>%BLUE% Venerdì 16 Marzo 2018 - Lezioni 9-10 </b>
Soluzioni delle equazioni di ricorrenza (1)

   * 4 metodi risolutivi:
      * metodo iterativo;
      * metodo di sostituzione;

*Esercizi assegnati:*
   * Calcolare la soluzione di alcune equazioni di ricorrenza
%ENDCOLOR%

<b>%BLUE% Lunedì 19 Marzo 2018 - Lezioni 11-12 </b>
Soluzioni delle equazioni di ricorrenza (2)

   * 4 metodi risolutivi:
      * metodo dell'albero;
      * metodo principale: enunciato del teorema senza dimostrazione

*Esercizi assegnati:*
   * Calcolare la soluzione di alcune equazioni di ricorrenza
%ENDCOLOR%

%BLACK%
*Esercitazioni 5-6: mercoledì 21 marzo 2018* %ENDCOLOR%

   * Ancora sui passaggi per riferimento: funzione ==scambia(int*,int*)==, ==ap(int*,int*,int,int)== (assegnamento parallelo à la Python) [ *D2*, sez. *2* ].
   * I problemi di *alias*: funzione ==scambia(int*,int*)== senza variabile di appoggio [ *D2*, sez. *3* ].
   * Induzione e Ricorsione: definizione induttiva di + e funzione ==sommaRec(int, int)== [ *D3*, sez. *1.1* ].
   * Esercizio: predecessore ricorsivo in ==TinyReC==. Riflessioni sulla completezza computazioneale di ==TinyReC==.
   * Fattoriale: definizione induttiva e programma ricorsivo. Considerazioni sulla sua complessità in ==TinyC==.
   * Ricorsione: funzione di Fibonacci. Efficienza e albero delle chiamate generato.
   * Funzioni: stack di attivazione delle chiamate [ *D2*, sez. *3* ].
   * Fibonacci Iterativo.

   * *Esercizi consigliati*: Dispensa *D2* [sez. *4* ]
   * *Esercizi consigliati*: Dispensa *D3* [sez. *1.3* ]
%ENDCOLOR%

<b>%BLUE% Venerdì 23 Marzo 2018 - Lezioni 13-14 </b>
Soluzioni delle equazioni di ricorrenza (3)

Esercizi riepilogativi sulle equazioni di ricorrenza

*Esercizi assegnati:*
   * Calcolare la soluzione delle equazioni di ricorrenza già assegnate usando tutti e 4 i metodi
%ENDCOLOR%

<b>%BLUE% Lunedì 26 Marzo 2018 - Lezioni 15-16 </b>

Il problema dell'ordinamento (1) 
   * algoritmi naif: insertion sort, selection sort e bubble sort; calcolo del costo computazionale
   * albero delle decisioni e teorema sulla limitazione inferiore per la complessità di un algoritmo per confronti

*Esercizi assegnati:*

   * Nell'algoritmo dell'insertion sort, la ricerca della posizione in cui inserire l'elemento corrente può essere effettuata tramite una ricerca binaria. Calcolare il costo computazionale dell'algoritmo così modificato.
   * Scrivere in pseudocodice una funzione che, dato un vettore A ed un indice j, calcoli il valore minimo nel sottovettore A[j..n]. Riscrivere lo pseudocodice del selection sort che utilizzi ripetutamente questa funzione.
   * Modificare l'algoritmo di Bubble Sort in modo che non prosegua la computazione se il vettore risulta ordinato.
   * Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (prima versione).
   * Determinare l'albero delle decisioni del Selection Sort.
%ENDCOLOR%

%BLACK%
*Esercitazioni 7-8: mercoledì 28 marzo 2018* %ENDCOLOR%
   * Iterazione e ricorsione: Fibonacci iterativo efficiente. Trasformazione sistematica di un ciclo in una funzione ricorsiva.
   * Dimostrazioni di correttezza per programmi ricorsivi. [ *D3*, sez. *2* ]
   * Problemi con soluzione inerentemente ricorsiva: il problema della Torre di Hanoi [ *D3*, sez. *3* ]
   * Soluzione di un esonero sul tema: il problema del massimo fattore primo [ *S4* ]
   * Un aiutino sull'Homework, esercizio *3*: il problema delle partizioni [ *S3*, sez. *1* ]

   * *Esercizi consigliati*: Dispensa *3* [sez. *2.4* e *3.3* ]

 
<b>%RED% Da Giovedì 29 Marzo a Martedì 3 Aprile 2018 inclusi  </b>

Vacanze di Pasqua%ENDCOLOR%

<b>%BLUE% Mercoledì 4 Aprile 2018 - Lezioni 17-18 </b>

Il problema dell'ordinamento (2)
   * algoritmi efficienti:
      * paradigma del divide et impera
      * merge sort (pseudocodice e costo computazionale, pseudocodice della funzione Fondi, problematica dell'ordinamento in loco)
      * quick sort (pseudocodice, costo computazionale nei casi migliore e peggiore, idea di caso medio)

*Esercizi assegnati:*
   * Scrivere la funzione di fusione ricorsiva
   * Determinare l'albero delle decisioni della funzione di fusione, quando i vettori da fondere sono a1 a2 e b1 b2 (con l'implicita ipotesi che a1&lt;a2 e b1&lt;b2)
   * Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (di nuovo: ma questa volta il costo computazionale dovrebbe essere un O(n log n))
%ENDCOLOR%

<b>%BLUE% Venerdì 6 Aprile 2018 - Lezioni 19-20 </b>

Il problema dell'ordinamento (3)
   * algoritmi efficienti: quick sort (pseudocodice e costo della funzione Partiziona, costo computazionale nel caso medio, problematica della randomizzazione)
   * algoritmi efficienti: heapsort (struttura dati heap, heapify: pseudocodice)

*Esercizi assegnati:*
   * Sia dato un vettore di lunghezza n contenente solo valori 0 e 2. Si progetti un algoritmo con costo computazionale lineare che modifichi il vettore in modo che tutte le occorrenze di 0 si trovino più a sinistra di tutte le occorrenze di 2.
   * Si considerino i valori 0 1 2 3 4 5 6 7. Si determini una permutazione di questi valori che generi il caso peggiore per l'algortimo Quick sort.
   * Calcolare il costo computazionale del Quick sort nel caso in cui il vettore contenga tutti elementi uguali.
%ENDCOLOR%

%BLACK%
*Esercitazioni 9-10: lunedì 9 aprile 2018* %ENDCOLOR%
   * Introduzione ai vettori in C: definizione e allocazione [ *D4*, sez. *1* ]. Passaggio di parametri vettori. Vettori e puntatori [ *D4*, sez. *1.1* ].
   * Un primo programma sui vettori: stampa di un vettore, iterativa e ricorsiva [ *D4*, sez. *1.1* ].  
   * Un esempio di programma con asserzioni logiche: minimo di un vettore [ *D4*, sez. *2.1* ]. Utilizzo nell'algoritmo di Selection Sort. 
   * Esercizio: il Problema del baricentro [ *S1* ].

   * *Esercizi consigliati*: Dispensa *4* [sez. *1.3* e *2.6* ],
   * *Lettura*: due grandi classici: crivello di Eratostene [ *D4*, sez. *2.4* ] e coefficienti binomiali [ *D4*, sez. *2.5* ].


%BLACK%
*Esercitazioni 11-12: mercoledì 11 aprile 2018* %ENDCOLOR%
   * Esercizi su vettori e ricorsione in vista dell'esonero:
      * *Virtuosismi 1*: funzione ==baricentroRec== che fa un'unica scansione del vettore [ *S1* ].
      * Il problema della verifica della combinazione del mastermind [  *S3*, sez. *2* ]: uso di vettori locali a una funzione.
      * *Virtuosismi 2*: funzione ==mergeRecVPC==: merge ricorsiva da Veri Programmatori C [ *L2* ]. Errata corrige alla [[%ATTACHURL%/mergeRecVPC18.pdf][Funzione in Fig.6 pag. 8]].
      * Coefficienti binomiali con generazione delle righe del triangolo di Tartaglia [ *D4*, sez. *2.5* ].

   * *Esercizi consigliati*: Di tutto un po', su vettori e ricorsione, dispensa *D3* e *D4*.

<b>%BLUE% Venerdì 13 Aprile 2018 - Lezioni 21-22 </b>

   * Esercizi in vista dell'esonero
%ENDCOLOR%

%BLACK%
*Esercitazioni 13-14: lunedì 23 aprile 2018* %ENDCOLOR%

   * Introduzione alla memoria allocata dinamicamente: stack e heap.
   * Funzioni di libreria ==malloc(int)== e ==calloc(int, int)==.
   * Il tipo ==void *==.
   * Differenza tra vettori a lunghezza variabile e vettori dinamici.
   * Introduzione ai record: definizioni di ==struct==. [ *D6*, sez. *1* ]
   * Vettori bidimensionali: allocazione statica [ *D5*, sez. *2* ].
   * Allocazione di una matrice dinamica [ *D5*, sez. *3* ].

   * *Esercizi consigliati*: nessuno.

<b>%BLUE% Venerdì 27 Aprile 2018 - Lezioni 23-24 </b>

 Il problema dell'ordinamento (4)
   * algoritmi efficienti: heapsort (costo computazionale di Heapify, BuildHeap: pseudocodice e costo, Heapsort: pseudocodice e costo)
   * algoritmi lineari: counting sort (versione semplificata e versione completa) e bucket sort (idea)

   * Strutture dati fondamentali (1)
      * strutture dati ed insiemi dinamici
      * confronto tra vettore qualunque e vettore ordinato
%ENDCOLOR%

<b>%BLUE% Mercoledì 2 Maggio 2018 - Lezioni 25-26 </b>

   * Strutture dati fondamentali (2)
      * introduzione alle liste: ricerca e inserimento in testa
      * cancellazione nelle liste, liste doppiamente puntate
      * code con priorità
      * la struttura dati coda
      * le operazioni enqueue e dequeue
 %ENDCOLOR%

<b>%BLUE% Venerdì 4 Maggio 2018 - Lezioni 27-28 </b>

   * Strutture dati fondamentali (3)
      * pila
      * le operazioni Push e Pop
      * Esercizio: simulazione di una coda tramite due pile
      * alberi (1)
         * definizione tramite la nozione di grafo
         * caratterizzazione degli alberi
         * alberi binari completi: relazione tra altezza e numero di nodi
         * memorizzazione degli alberi:
            * tramite record e puntatori
            * posizionale
            * tramite vettore dei padri

*Esercizi assegnati:*
   * scrivere sia lo pseudocodice che il codice C delle funzioni Enqueue e Dequeue quando la coda sia circolare ed implementata su vettore
   * scrivere sia lo pseudocodice che il codice C delle funzioni Pop, Push e Pila_Piena quando la pila sia implementata su vettore
 %ENDCOLOR%

<b>%BLUE% Lunedì 7 Maggio 2018 - Lezioni 29-30 </b>
   * Strutture dati fondamentali (4)
      * alberi (2)
         * visite di alberi: in-ordine, pre-ordine e post-ordine
            * pseudocodice ricorsivo
            * costo computazionale tramite equazione di ricorrenza e metodo di sostituzione (sol. lasciata per esercizio)
            * esercizi che si risolvono utilizzando le visite
            * esercizi che si risolvono usando alberi, pile e code
 %ENDCOLOR%

%BLACK%
*Esercitazioni 15-16: mercoledì 9 maggio 2018*

   * Tipo di dato sequenza e sua definizione induttiva. 
   * Rappresentazione in C delle sequenze: uso di  ==struct== 'ricorsive' [dispensa *D6*, sez. *3* ].
   * Costruttori e distruttori del tipo sequenza.
   * Prime funzioni C su liste: ==length==, ==sumL== [dispensa *D6*, sez. *3.1* ].
   * Attenzione alla memoria raggiungibile: side effects. L'esempio di ==twiceL== [dispensa *D6*, sez. *3.2* ]. 

   * *Esercizi consigliati*: i più semplici di quelli alla fine della dispensa *D6* .
%ENDCOLOR%

<b>%BLUE% Venerdì 11 Maggio 2018 - Lezioni 31-32 </b>
   * Strutture dati fondamentali (5)
      * alberi (3)
         * visite di alberi: in-ordine, pre-ordine e post-ordine
            * esercizio: visita in preordine sul vettore dei padri
   * Dizionari (1)
      * tabelle ad indirizzamento diretto
      * tabelle hash
         * ipotesi di uniformità semplice e fattore di carico
         * soluzione delle collisioni tramite liste di trabocco
         * soluzione delle collisioni tramite indirizzamento aperto
      * Alberi binari di ricerca (ABR) (1):
         * definizione e proprietà dell' "ordinamento orizzontale"
         * algoritmo per il massimo e minimo
 
  *Esercizi assegnati:*
   * Scrivere lo pseudocodice degli algoritmi per la ricerca del massimo e del minimo in un ABR

<b>Lunedì 14 Maggio 2018 - Lezioni 33-34* </b>
   * Dizionari (2)
      * Alberi binari di ricerca (ABR) (2):
         * algoritmo per il successore e predecessore
         * algoritmo di inserimento
         * algoritmo di cancellazione
         * osservazioni sul costo computazionale delle operazioni viste come funzione dell'altezza

*Esercizi assegnati:*
   * Scrivere lo pseudocodice degli algoritmi per la ricerca del predecessore e del successore in un ABR
   * Dato due ABR T1 e T2, progettare un algoritmo che produca in output un terzo albero binario di ricerca T contenente le chiavi di T1 e di T2. Fare le considerazioni del caso riguardo al costo computazionale.
%ENDCOLOR%

%BLACK%
*Esercitazioni 17-18: mercoledì 16 maggio 2018*

   * Inserzione di elementi in coda [dispensa *D6*, sez. *3.3* ]: 
      * specifica con equazioni ricorsive, 
      * versione iterativa ==addLastIt==, 
      * ricorsiva ==addLastRec==, 
      * con generazione di una nuova lista ==addLastFun== .
   * Concatenazione di liste [dispensa *D6*, sez. *3.4* ]: 
      * specifica con equazioni ricorsive, 
      * versioni 'mista' ==append==, 
      * ricorsiva ==appendRec==, 
      * con generazione nuove liste ==appendFun== .
   * Rovesciamento di liste [dispensa *D6*, sez. *3.5* ]: 
      * specifica con equazioni ricorsive, 
      * versione 'fun' inefficiente ==reverseFun==, 
      * iterativa ==reverseIt==, 
      * versione ricorsiva efficiente ==reverseFunEff== .
   * Rovesciamento di Liste _in place_: versione ricorsiva ==reverseRec== [dispensa *D6*, sez. *3.5* ].
   * Eliminazione di elementi: ==removeFun== e ==removeRec== [dispensa *D6*, sez. *3.6* ].
   * Il problema della deallocazione di memoria dinamica: ==free()== [dispensa *D6*, sez. *2.1* ].

   * *Esercizi consigliati*: reverse _in place_ iterativa (virtuosismo) e altri esercizi tra di quelli alla fine della dispensa *D6* .
%ENDCOLOR%

<b>%BLUE%Venerdì 18 Maggio 2018 - Lezioni 35-36* </b>
   * Dizionari (3)
      * Alberi binari di ricerca (ABR) - segue:
         * alberi bilanciati: alberi rosso-neri
         * dimostrazione che gli alberi rosso-neri hanno altezza logaritmica
         * rotazioni
         * cenno all'operazione di inserimento 

*Esercizi assegnati:*
   * Costruire un ABR inserendo successivamente le chiavi 41, 38, 31, 12, 19, 8.
%ENDCOLOR%

<b>%BLUE%Lunedì 21 Maggio 2018 - Lezioni 37-38* </b>
   * Grafi (1)
      * Definizione e alcune proprietà
      * Rappresentazione in memoria di grafi:
         * liste di adiacenza
         * matrice di adiacenza
         * matrice di incidenza
         * lista di archi
         * confronto tra rappresentazioni
      * Visite di grafi
      * Alberi di visita

*Esercizi assegnati:*
   * Dato G memorizzato con una struttura dati X, dare in output G memorizzato con un'altra struttura dati Y, dove X ed Y variano in tutti i modi possibili tra le 4 rappresentazioni viste
%ENDCOLOR%

%BLACK%
*Esercitazioni 19-20: mercoledì 23 maggio 2018*
   * Discussione Homework 2: definizioni di tipi per il problema della Torre di Hanoi.
   * Eliminazione di elementi: ==removeFun== e ==removeRec== [dispensa *D6*, sez. *3.6* ].
   * Il problema della deallocazione di memoria dinamica: ==free()== [dispensa *D6*, sez. *2.1* ].
   * Eliminazione di elementi: ==removeIt==: attenzione a non perdere la testa (della lista)! [dispensa *D6*, sez. *3.6* ].
   * Esercizi da esoneri passati: il problema dello _shuffle_ [Dispensa *S6*, sez. *1.5* ].

  * *Esercizi consigliati*: differenza tra liste, rimozione di duplicati [dispensa *D6*, sez. *3.6* ] e altri esercizi nella dispensa *S6* sezione *1*.
%ENDCOLOR%

<b>%BLUE%Venerdì 25 Maggio 2018 - Lezioni 39-40* </b>
   * Grafi (2)
      * Visita in ampiezza: filosofia, esempio, pseudocodice, costo computazionale in funzione della struttura dati usata, proprietà dell'albero di visita in ampiezza (archi di riporto vs. di attraversamento, cammini più corti)
      * Esempi di uso di visita in ampiezza: calcolo dei cammini più corti da un nodo dato
%ENDCOLOR%

<b>%BLUE%Lunedì 28 Maggio 2018 - Lezioni 41-42* </b>
   * Grafi (3)
      * Visita in profondità: filosofia, esempio, pseudocodice, costo computazionale in funzione della struttura dati usata, proprietà dell'albero di visita in ampiezza (archi di riporto vs. di attraversamento)
      * Esempi di uso di visita in profondità: calcolo delle componenti connesse
      * Esercizi su grafi: calcolo del grafo complemento e del quadrato di un grafo

*Esercizi assegnati:*
   * Modificare lo pseudocodice della visita in ampiezza in modo che restituisca la lunghezza dei cammini minimi da un fissato nodo v a tutti gli altri nodi.
   * Dato un grafo G mediante le sue liste di adiacenza, progettare un algoritmo che dica se G è aciclico oppure no.
%ENDCOLOR%

%BLACK%
*Esercitazioni 21-22: mercoledì 30 maggio 2018*
   * Introduzione agli alberi binari: definizione induttiva e rappresentazione in C [dispensa *D7*, sez. *1* e sez. *1.1* ].
   * Costruttori e distruttori: ==makeTree(int n, binTree L, binTree R)==, ==isNotEmptyTree(binTree B, int *r, binTree* L, binTree *R)== [ *D7*, sez. *1.1* ]. 
   * Funzioni base: numero di nodi, profondità.
   * Il problema del bilanciamento: in profondità e in peso con un'unica visita dell'albero  [dispensa *D7*, sez. *1.4* ].
   * *Fuori programma*: macro espansioni con #define: la macro ==min(x,y)=x<y?x:y==. 

  * *Esercizi consigliati*: vedi dispensa *D7*, sez. finale di esercizi.
%ENDCOLOR%

<b>%BLUE%Venerdì 1 Giugno 2018 - Lezioni 43-44* </b>
   * Grafi (4)
      * Grafi euleriani: definizione, teorema di Eulero, esercizio
      * Grafi bipartiti: definizione, caratterizzazione, esercizio
      * Colorazione di grafi
%ENDCOLOR%

%BLACK%
*Esercitazioni 23-24: lunedì 4 giugno 2018*
   * Discussione Homework 3.
   * Alberi binari: visita per livelli [dispensa *D7*, sez. *1.3* ].
   * Problemi con liste e alberi: il problema della frontiera [dispensa *D7*, sez. *1.2* ]. Versione efficiente che evita uso di ==append== .
   * *Esoneri passati* 
      * il problema di restituire la lista dei nodi al livello _k_: funzione ==livelloK== [dispensa *S6*, sez. *2.2* ] 
      * il problema di determinare il cammino fino a un nodo _x_: funzione ==pathToX== [dispensa *S6*, sez. *2.3* ]
 
   * *Esercizi consigliati*: vedi dispensa *D7*, sez. finale di esercizi e dispensa *S6*.
%ENDCOLOR%

%BLACK%
*Esercitazioni 25-26: mercoledì 6 giugno 2018*
   * Relazione di uguaglianza e sottoalbero [ dispensa *D7*, sez. *1.5* ]
   * Esercizi in preparazione dell'esonero:
      * divisione di liste: funzione ==dividi==  [dispensa *S6*, sez. *1.1* ]
      * somma precedenti  [dispensa *S6*, sez. *1.2* ] e somma successiv  [dispensa *S2* ]
      * prefisso tra alberi  [dispensa *S6*, sez. *2.4* ]
 
   * *Esercizi consigliati*: dispensa *S6*.
%ENDCOLOR%

<b>%BLUE%Venerdì 8 Giugno 2018 - Lezioni 45-46* </b>
   * Esercizi in preparazione dell'esonero
%ENDCOLOR%






---+++ <font color="#336699" size="+1"> A.A. 2016/2017</font>

<font color="#336699">
*Mercoledì 1 Marzo 2017 - Lezioni 1-2* </font>

*Introduzione*
   * Informazioni sul corso.
   * Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale.
   * modello RAM; misura di costo uniforme e logaritmico.

<font color="#336699">
*Venerdì 3 Marzo 2017 - Lezioni 3-4* </font>

*Notazione asintotica (1)*
   * Definizione e significato degli insiemi O, &Omega; e &Theta;.
   * Algebra della notazione asintotica
   * Esempi
   * Valutazione del costo computazionale di un algoritmo
   * Un primo esempio

*Esercizi assegnati:*
   * Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione

%BLACK%
*Esercitazioni 1-2: lunedì 6 marzo 2017* %ENDCOLOR%

   * ==TinyC==. Codifica in ==TinyC== del programma che calcola la *somma* iterando +1 [ *D2*, sezione *2* ]
   * Indagini su un programma iterativo [ *D1*, sez. *2.1* ]:
      * Precondizioni, Postcondizioni, invarianti di ciclo.
      * Terminazione di un ciclo: funzione di terminazione.
   * *Esempi*:
      * funzione che calcola la *moltiplicazione*. Uso della funzione somma nel calcolo del prodotto [ *D2*, sez. *3* ].
      * funzione che calcola il *predecessore*. Specifica come contratto.
      * somma che usa predecessore. Osservazioni sulla complessità dei programmi ==TinyC==.
      * Esempio: *fattoriale*: discussione della sua complessità in ==TinyC== e in ==C==.

   * *Esercizi consigliati*: Dispensa *D1*, sez. *2.5*, esercizi da 2 a 8.
   * *Sperimentazioni*: Disp. *D2*, sez. *2.1*.

%BLACK%
*Esercitazioni 3-4: mercoledì 8 marzo 2017* %ENDCOLOR%

   * Progetto di funzioni a partire dalle specifiche logiche [ *D1*, sez. *2.3* ].
      * Esempio: divisione intera.
   * Introduzione alla pila di sistema, variabili locali, globali [ *D2*, sez. *3* ].
   * Uso di passaggi *per riferimento* per passare più risultati: funzione ==int divRef(int, int, int*, int*)==.
   * Utilizzo della funzione ==divRef== nell'algoritmo ==mcdMaestra== [ *D2*, sez. *4* ].
   * Valutazione dei parametri: impossibilità di scrivere una funzione ==myAnd== equivalente a ==&&==.

   * *Esercizi consigliati*: Dispensa *D1*, sez. *2.5*, esercizi da 2 a 8.
   * *Elucubrazioni*: Inutilità dell' ==if== in ==TinyC==. Altri esercizi in Disp. *D2*, sez. *1.2*.

<font color="#336699">
*Venerdì 10 Marzo 2017 - Lezioni 5-6* </font>

*Notazione asintotica (2)*
   * Esempi di problemi che si possono risolvere in modo più o meno efficiente e loro costo computazionale
      * somma dei primi n interi
      * valutazione di un polinomio in un punto
      * ricerca di un elemento in un vettore

*Il problema della ricerca*
   * ricerca sequenziale e suo costo computazionale nel caso migliore e peggiore
   * ricerca dicotomica e suo costo computazionale nel caso migiore e peggiore

*Esercizi assegnati:*
   * Calcolare l'andamento asintotico di alcune funzioni ed alcune sommatorie
   * Calcolare il costo computazionale del Selection, dell'Insertion Sort e del Bubble Sort (pseudocodice sulle dispense)

<font color="#336699">
*Lunedì 11 Marzo 2017 - Lezioni 7-8* </font>

Ricorsione
   * funzioni matematiche ricorsive;
   * ricerca sequenziale e binaria: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;
   * altri esempi di problemi risolti con algoritmi ricorsivi.

*Esercizi assegnati:*
   * Progettare degli algoritmi ricorsivi ed esprimerli tramite pseudocodice che risolvano i seguenti problemi:
      * dato in input un vettore, visualizzare i suoi valori al contrario (dall'ultimo al primo)
      * calcolare la somma di n numeri reali inseriti da tastiera (uno per ogni chiamata ricorsiva)
      * calcolare il MCD tra due interi positivi x ed y come segue:
         * sia y<x
         * se y=0 allora MCD(x,y)=y
         * altrimenti MCD(x,y))MCD(y, x%y)
</font>

%BLACK%
*Esercitazioni 5-6: mercoledì 15 marzo 2017* %ENDCOLOR%

   * Ancora sui passaggi per riferimento: funzione ==scambia(int*,int*)==, ==ap(int*,int*,int,int)== (assegnamento parallelo à la Python) [ *D3*, sez. *2* ].
   * I problemi di *alias*: funzione ==scambia(int*,int*)== senza variabile di appoggio [ *D3*, sez. *3* ].
   * Induzione e Ricorsione: definizione induttiva di + e funzione ==sommaRec(int, int)== [ *D4*, sez. *1.1* ].
   * Esercizio: predecessore ricorsivo in ==TinyReC==. Riflessioni sulla completezza computazioneale di ==TinyReC==.
   * Ricorsione: funzione di Fibonacci. Efficienza e albero delle chiamate generato.
   * Funzioni: stack di attivazione delle chiamate [ *D2*, sez. *3* ].
   * Fibonacci Iterativo.

   * *Esercizi consigliati*: Dispensa *3* [sez. *4* ]
   * *Esercizi consigliati*: Dispensa *4* [sez. *1.3* ]

<font color="#336699">
*Venerdì 17 Marzo 2017 - Lezioni 9-10* </font>

Soluzioni delle equazioni di ricorrenza (1)

   * carrellata sui 4 metodi:
      * metodo iterativo;
      * metodo di sostituzione;
      * metodo dell'albero;
      * metodo principale: enunciato del teorema senza dimostrazione

*Esercizi assegnati:*
   * Calcolare la soluzione di alcune equazioni di ricorrenza

<font color="#336699">
*Lunedì 20 Marzo 2017 - Lezioni 11-12* </font>

Soluzioni delle equazioni di ricorrenza (2)

   * esempi di soluzione di equazioni di ricorrenza tramite i quattro metodi

*Esercizi assegnati:*
   * Calcolare la soluzione delle seguenti equazioni di ricorrenza con i quattro metodi studiati, ove possibile, tenendo conto che per tutte il caso base è T(1)=&Theta(1):
      * T(n)=2T(n/2)+&Theta;(n)
      * T(n)=3T(n/2)+&Theta;(n)
      * T(n)=3T(n/4)+&Theta;(n)
      * T(n)=2T(n/2)+&Theta;(n^2)
      * T(n)=2T(n/2)+&Theta;(n^3)
      * T(n)=T(n-1)+&Theta;(n)

%BLACK%
*Esercitazioni 7-8: mercoledì 22 marzo 2017* %ENDCOLOR%
   * Fibonacci ricorsivo efficiente [ *D4*, sez. *2* ].
   * Dimostrazioni induttive di correttezza per funzione ricorsive [ *D4*, sez. *2* ].
   * Trasformazione sistematica di programmi iterativi in ricorsivi [ *D4*, sez. *2* ].
   * Esempi di problemi con soluzioni inerentemente ricorsive:
      * Funzione maxPrimo (Esonero 2014) [ *S4* ].
      * Calcolo del numero delle partizioni (Homework 1, 2012) [ *S3*, sez. *1* ]
   * Introduzione ai vettori. Vettori e puntatori. Stampa iterativa di un vettore. [ *D6*, sez. *1* ]
   * Esempio di sviluppo di programmi su vettori con asserzioni logiche: *minimo di un vettore*. [ *D6*, sez. *2.1* ]

   * *Esercizi consigliati*: Dispensa *4* [sez. *2.4* e *3.3* ]

<font color="#336699">
*Venerdì 24 Marzo 2017 - Lezioni 13-14*
Il problema dell'ordinamento (1) </font>
   * algoritmi naif: insertion sort, selection sort e bubble sort; calcolo del costo computazionale
   * albero delle decisioni e teorema sulla limitazione inferiore per la complessità di un algoritmo per confronti

*Esercizi assegnati:*

   * Nell'algoritmo dell'insertion sort, la ricerca della posizione in cui inserire l'elemento corrente può essere effettuata tramite una ricerca binaria. Calcolare il costo computazionale dell'algoritmo così modificato.
   * Scrivere in pseudocodice una funzione che, dato un vettore A ed un indice j, calcoli il valore minimo nel sottovettore A[j..n]. Riscrivere lo pseudocodice del selection sort che utilizzi ripetutamente questa funzione.
   * Determinare l'albero delle decisioni del Selection Sort e dell'Insertion Sort
   * Modificare l'algoritmo di Bubble Sort in modo che non prosegua la computazione se il vettore risulta ordinato.
   * Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (prima versione).

<font color="#336699">
*Lunedì 27 Marzo 2017 - Lezioni 15-16*
Il problema dell'ordinamento (2) </font>

   * algoritmi efficienti:
      * paradigma del divide et impera
      * merge sort (pseudocodice e costo computazionale, pseudocodice della funzione Fondi, problematica dell'ordinamento in loco)
      * quick sort (pseudocodice, pseudocodice della funzione Partiziona)

*Esercizi assegnati:*
   * Scrivere la funzione di fusione ricorsiva
   * Determinare l'albero delle decisioni della funzione di fusione, quando i vettori da fondere sono a1 a2 e b1 b2 (con l'implicita ipotesi che a1&lt;a2 e b1&lt;b2)
   * Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (di nuovo: ma questa volta il costo computazionale dovrebbe essere un O(n log n))

%BLACK%
*Esercitazioni 9-10: mercoledì 29 marzo 2017* %ENDCOLOR%
   * Esercizi sui vettori: il problema del *baricentro* [Esonero 2012, *S1* ].
   * *Virtuosismi*: funzione ==baricentroRec== che calcola il baricentro con un'unica scansione ricorsiva.
   * Generazione delle combinazioni di _n_ oggetti presi _k_ a _k_ . [Esonero 2016, *S4* ].
   * *Virtuosismi*: versione ricorsiva che genera le combinazioni.

   * *Letture consigliate*: Due grandi classici: crivello di Eratostene e Coefficienti Binomiali [ *D6* sez. *2.4* e *2.5* ]
   * *Esercizi consigliati*: Dispensa *6* [sez. *1.3* e *2.6* ]

*Venerdì 31 Marzo 2017 - Lezioni 17-18*
Il problema dell'ordinamento (3)
   * algoritmi efficienti: quick sort (costo computazionale nel caso peggiore, migliore e medio, problematica della randomizzazione)
   * algoritmi efficienti: heapsort (struttura dati heap, heapify: pseudocodice)

*Esercizi assegnati:*
   * Sia dato un vettore di lunghezza n contenente solo valori 0 e 2. Si progetti un algoritmo con costo computazionale lineare che modifichi il vettore in modo che tutte le occorrenze di 0 si trovino più a sinistra di tutte le occorrenze di 2.
   * Si considerino i valori 0 1 2 3 4 5 6 7. Si determini una permutazione di questi valori che generi il caso peggiore per l'algortimo Quick sort.
   * Calcolare il costo computazionale del Quick sort nel caso in cui il vettore contenga tutti elementi uguali.

<font color="#336699">
*Lunedì 3 Aprile 2017 - Lezioni 19-20*
Il problema dell'ordinamento (4) </font>
   * algoritmi efficienti: heapsort (buildheap, e heapsort: pseudocodice e costo computazionale)
   * algoritmi lineari: counting sort (versione semplificata e versione completa)

*Esercizi assegnati:*
   * Scrivere lo pseudocodice di Heapsort nel caso in cui, come struttura dati, si usi un heap minimo (cioè tale che A[i]&gt;=A[parent(i)]), che mantiene il minimo nella radice.
   * Scrivere lo pseudocodice di una funzione che, dato un heap, ritorni l'elemento con chiave minima. Valutare il costo computazionale.
   * Discutere la ragionevolezza di una struttura dati in cui:
      * si costruisce in tempo lineare
      * il minimo si trova in tempo costante
      * dopo l'estrazione del minimo, si riaggiusta in tempo costante

%BLACK%
*Esercitazioni 11-12: mercoledì 5 aprile 2017* %ENDCOLOR%

Esercizi su vettori e ricorsione in in vista dell'esonero.
   * Il problema 3 dell'Homework di Prova: conteggio delle _k_ uple ordinate di prodotto _n_ .
   * Il problema della prossima permutazione [ dispensa *A1* ].
   * Generazione ricorsiva delle permutazioni (o anagrammi) [ *D4* sez. *3.2* ].
   * ==merge== tra due vettori ordinati ricorsiva.
   * *Virtuosismi*: merge ricorsiva da Vero Programmatore C [ Esercizi di stile, *L2* sez. *1* ]. Errata corrige alla [[%ATTACHURL%/mergeRecVPC18.pdf][Funzione in Fig.6 pag. 8]].


   * *Esercizi consigliati*: Di tutto un po' su ricorsione, puntatori e vettori.
  

<font color="#336699">
*Venerdì 7 Aprile 2017 - Lezioni 21-22*
Esercizi in preparazione dell'esonero
</font>

%RED%
*Lunedì 12 aprile 2017 - Primo Esonero*
%ENDCOLOR%

%BLACK%
*Esercitazioni 13-14: mercoledì 12 aprile 2017* %ENDCOLOR%

   * Breve discussione soluzioni esonero ed errori tipici [dispensa *A2* ].
   * Introduzione alla memoria allocata dinamicamente: stack e heap.
   * Funzioni di libreria ==malloc(int)== e ==calloc(int, int)==.
   * Differenza tra vettori a lunghezza variabile e vettori dinamici.
   * Vettori bidimensionali: allocazione statica [dispensa *D7*, sez. *2* ].
   * Allocazione di una matrice dinamica [dispensa *D7*, sez. *3* ].
   * Esempio: allocazione e costruzione del Triangolo di Tartaglia.

   * *Esercizi consigliati*: nessuno.
  

<font color="#336699">
*Venerdì 21 Aprile 2017 - Lezioni 23-24*
Correzione degli esercizi d'esonero e consegna dei compiti
</font>

%BLACK%
*Esercitazioni 15-16: mercoledì 26 aprile 2017* %ENDCOLOR%

   * Breve discussione esercizi Homework 1.
   * Tipo di dato sequenza e sua definizione induttiva.
   * Rappresentazione in C delle sequenze: costruttore di tipo ==struct== [dispensa *D8*, sez. *1* ].
   * Costruttori e distruttori del tipo sequenza.
   * Prime funzioni C su liste: ==length==, ==sumL== [dispensa *D8*, sez. *3.1* ].

   * *Esercizi consigliati*: nessuno.
  

<font color="#336699">
*Venerdì 28 Aprile 2017 - Lezioni 25-26* </font>
   * Strutture dati fondamentali (1)
      * strutture dati ed insiemi dinamici
      * confronto tra vettore qualunque e vettore ordinato
      * introduzione alle liste: ricerca e inserimento in testa
      * cancellazione nelle liste, liste doppiamente puntate e liste circolari
 

%BLACK%
*Esercitazioni 17-18: mercoledì 3 maggio 2017* %ENDCOLOR%

   * Funzioni che modificano liste: ==twiceL==. Trasparenza referenziale: versioni che generano nuove liste e versioni _in place_ [dispensa *D8*, sez. *3.2* ].
   * Inserimento e concatenazione di liste. Side effects indesiderati. Versioni ricorsive, iterativa e _funzionali_ [dispensa *D8*, sez. *3.3* e *3.4* ].
   * Il problema del rovesciamento. Versione ricorsiva inefficiente quadratica, iterativa e versione efficiente con parametro ausiliario.
   * Rovesciamento ricorsivo _in place_ [dispensa *D8*, sez. *3.5* ].

   * *Esercizi consigliati*: rovesciamento iterativo in place. Esercizi alla fine di dispensa *D8*.
  

<font color="#336699">  
*Venerdì 5 Maggio 2017 - Lezioni 27-28* </font>
   * Strutture dati fondamentali (2)
      * la struttura dati coda
      * le operazioni enqueue e dequeue
      * code con priorità
      * pila
      * le operazioni Push e Pop
      * Esercizio: simulazione di una coda tramite due pile

*Esercizi assegnati:*
   * scrivere sia lo pseudocodice che il codice C delle funzioni Enqueue e Dequeue quando la coda sia circolare ed implementata su vettore
   * scrivere sia lo pseudocodice che il codice C delle funzioni Pop, Push e Pila_Piena quando la pila sia implementata su vettore
  

<font color="#336699">  
*Lunedì 8 Maggio 2017 - Lezioni 29-30* </font>
   * Strutture dati fondamentali (3)
      * alberi
         * definizione tramite la nozione di grafo
         * caratterizzazione degli alberi
         * alberi binari completi: relazione tra altezza e numero di nodi
         * memorizzazione degli alberi:
            * tramite record e puntatori
            * posizionale
            * tramite vettore dei padri

*Esercizi assegnati:*
   * dato un albero tramite vettore dei padri, restituirlo in output tramite notazione posizionale. Calcolare il costo computazionale
   * dato un albero tramite notazione posizionale, restituirlo in output tramite vettore dei padri. Calcolare il costo computazionale
 

%BLACK%
*Esercitazioni 19-20: mercoledì 10 maggio 2017* %ENDCOLOR%

   * Breve discussione delle liste alternative da usare nell'Homework 2. Liste con pointer all'ultimo elemento e liste doppiamente concatenate.
   * Funzioni che rimuovono elementi dalle liste: ==remove==. Versioni funzionali e versioni _in place_. La funzione di libreria ==free(void * )== [dispensa *D8* , sez. *3.6* ]
   * Differenza tra liste. Cautela nell'uso di chiamate annidate di funzioni di tipo ==Fun==.
   * Alcuni esercizi di compiti passati: ==immersa==, ==mcdDaLista== [dispensa *S6* ].

   * *Esercizi consigliati*: remove iterativa in place. Esercizi alla fine di dispensa *D8*.
  

<font color="#336699">  
*Venerdì 12 Maggio 2017 - Lezioni 31-32* </font>
   * Strutture dati fondamentali (4)
      * visite di alberi: in-ordine, pre-ordine e post-ordine
         * pseudocodice ricorsivo
         * costo computazionale tramite equazione di ricorrenza e metodo di sostituzione
         * esercizi che si risolvono utilizzando le visite
      * esercizi che si risolvono usando alberi, pile e code

<font color="#336699">  
*Lunedì 15 Maggio 2017 - Lezioni 33-34* </font>

   * Dizionari (1)
      * tabelle ad indirizzamento diretto
      * tabelle hash
         * ipotesi di uniformità semplice e fattore di carico
         * soluzione delle collisioni tramite liste di trabocco
         * soluzione delle collisioni tramite indirizzamento aperto
       * Alberi binari di ricerca (ABR):
         * definizione e proprietà dell' "ordinamento orizzontale"
 

%BLACK%
*Esercitazioni 21-22: mercoledì 17 maggio 2017* %ENDCOLOR%

   * Definizione induttiva di albero binario.
   * Costruttori e distruttori di alberi binari: ==makeTree==, ==emptyTree==, ==isEmptyTree==.
   * Semplici funzioni definite per ricorsione su alberi binari: numero nodi, peso, altezza.
   * Rivisitazioni delle visite: stampa (preorder) di un albero a parentesi nella forma _r(L,R)_, stampa (inorder) indentata.
   * Funzione ==makeTreeFromArray== che ricostruisce un albero binario partendo da una visita preorder e da una inorder.
  

<font color="#336699">  
*Venerdì 19 Maggio 2017 - Lezioni 35-36* </font>
   * Dizionari (2)
       * Alberi binari di ricerca (ABR) - segue:
        * algoritmo di ricerca
      * 
         * algoritmo per il massimo e minimo
         * algoritmo per il successore e predecessore
         * algoritmo di inserimento
         * algoritmo di cancellazione
         * osservazioni sul costo computazionale delle operazioni viste come funzione dell'altezza

*Esercizi assegnati:*
   * Scrivere lo pseudocodice degli algoritmi per la ricerca del predecessore e del successore in un ABR
   * Dato due ABR T1 e T2, progettare un algoritmo che produca in output un terzo albero binario di ricerca T contenente le chiavi di T1 e di T2. Fare le considerazioni del caso riguardo al costo computazionale.
 

<font color="#336699">  
*Lunedì 22 Maggio 2017 - Lezioni 37-38* </font>
   * Dizionari (3)
       * Alberi binari di ricerca (ABR) - segue:
      * 
         * alberi bilanciati: alberi rosso-neri
         * dimostrazione che gli alberi rosso-neri hanno altezza logaritmica
   * Grafi (1)
      * Definizioni e semplici proprietà
*Esercizi assegnati:*
   * Costruire un ABR inserendo successivamente le chiavi 41, 38, 31, 12, 19, 8.
 

<font color="#336699">  
*Mercoledì 24 Maggio 2017 - Lezioni 39-40* </font>
   * Grafi (2)
      * Rappresentazione in memoria di grafi:
         * liste di adiacenza
         * matrice di adiacenza
         * matrice di incidenza
         * lista di archi
         * confronto tra rappresentazioni
      * Visite di grafi
      * Alberi di visita
      * Visita in ampiezza: proprietà dell'albero di visita in ampiezza, pseudocodice
      * Esempi di uso di visita in ampiezza: cammini più corti

*Esercizi assegnati:*
   * Dato G memorizzato con una struttura dati X, dare in output G memorizzato con un'altra struttura dati Y, dove X ed Y variano in tutti i modi possibili tra le 4 rappresentazioni viste
 

%BLACK%
*Esercitazioni 23-24: venerdì 26 maggio 2017* %ENDCOLOR%
   * Ancora sugli alberi: funzioni ==eqTree== e ==subTree== per uguaglianza e relazione di sottoalbero.
   * Il problema del bilanciamento: versioni ingenue (quadratiche) ed efficienti (lineari) [dispensa *D9* ].
   * Presentazione terzo Homework.
   * Esercizi da compiti precedenti:
      * creare una lista con i nodi del livello _k_: ==list levelK(binTree B, int k)==.
      * restituire una lista con i nodi nel cammino dalla radice a un nodo: ==list pathToX(binTree B, int x)== [dispensa *S6* ].
 

<font color="#336699">  
*Lunedì 29 Maggio 2017 - Lezioni 41-42* </font>
   * Grafi (3)
      * Visita in ampiezza: costo computazionale in funzione della struttura dati usata
      * Visita in profondità: pseudocodice, costo computazionale in funzione della struttura dati usata, proprietà dell'albero di visita in profondità
      * Esercizi su grafi: cammini più corti e calcolo delle componenti connesse
      * Grafi euleriani e loro caratterizzazione

*Esercizi assegnati:*
   * Modificare lo pseudocodice della visita in ampiezza in modo che restituisca la lunghezza dei cammini minimi da un fissato nodo v a tutti gli altri nodi.
   * Dato un grafo G mediante le sue liste di adiacenza, progettare un algoritmo che dica se G è aciclico oppure no.
   * Dato un grafo G mediante le sue liste di adiacenza, progettare un algoritmo che restituisca il numero delle componenti connesse di G.

%BLACK%
*Esercitazioni 25-26: mercoledì 31 maggio 2017* %ENDCOLOR%
   * Discussione terzo Homework.
   * Esercizi da compiti precedenti:
      * relazione prefisso tra alberi: ==int prefixTree(binTreeList L)==;
      * numeri naturali implementati come liste;
      * divisione di una lista [dispensa *S6* ].
  

<font color="#336699">  
*Lunedì 5 Giugno 2017 - Lezioni 43-44* </font>
   * Grafi (3)
      * Grafi bipartiti e loro caratterizzazione
      * Accoppiamenti massimi e massimali
      * Colorazioni minime e minimali

<font color="#336699">  
*Mercoledì 7 Giugno 2017 - Lezioni 45-46* </font>
   * Esercizi di riepilogo in vista del secondo esonero e dell'esame scritto

---
---+++ <font color=#336699 size="+1"> A.A. 2015/2016</font>

<font color=#336699> 
*Mercoledì 2 Marzo 2016 - Lezioni 1-2*

*Introduzione*
   * Informazioni sul corso.
   * Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale.
   * modello RAM; misura di costo uniforme e logaritmico.
</font>

<font color=#336699> 
*Venerdì 4 Marzo 2016 - Lezioni 3-4*

*Introduzione (2)*
   * esempio di utilizzo delle misure di costo uniforme e logaritmico.
   * Pseudocodice

*Notazione asintotica (1)*
   * Definizione e significato degli insiemi O, &Omega; e &Theta;.
   * Algebra della notazione asintotica
   * Esempi
   * Valutazione del costo computazionale di un algoritmo
   * Esempi

*Esercizi assegnati:*
   * Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione
   * Calcolare l'andamento asintotico di alcune funzioni
   * Calcolare il costo computazionale degli algoritmi di Selection Sort e Insertion Sort (pseudocodice sulle dispense)
</font>

<font color=black> 
*Esercitazioni 1-2: lunedì 7 marzo 2016*

   * Introduzione ai concetti di problema, procedura risolutiva, automa. [dispensa parte *D1*, sezioni *1* ]<br>
   * Tiny C. Codifica in Tiny C del programma che calcola la somma iterando +1 [ *D2*, sez. *1* ]<br>
   * Indagini su un programma iterativo [ *D1*, sez. *2.1* ]: 
      * Testing ed esecuzione "manuale" (trace).<br>
      * Precondizioni, Postcondizioni, invarianti di ciclo.
      * Terminazione di un ciclo: funzione di terminazione.<br>

   * *Esercizi consigliati*: Dispensa *1*, sez. *2.5*, esercizi da 2 a 8.
</font>


<font color=black> 
*Esercitazioni 3-4: mercoledì 9 marzo 2016*

   * Funzione moltiplicazione. Esigenza e utilità delle funzioni.
   * Funzione predecessore. Funzione somma senza contatore. [ *D2*, sez. *3* ]
   * Complessità concreta: complessità delle funzioni in Tiny C.
   * Progetto di funzioni a partire dalle specifiche logiche [ *D1*, sez. *2.3* ]. 
      * Esempio: divisione intera. 
   * Introduzione alle funzioni ricorsive. Definizioni induttive e corrispondenti programmi ricorsivi [ *D4*, sez. *1.1* ].
      * Esempi: somma, fattoriale.

   * *Esercizi consigliati*: Dispensa *2*  [sez. *3.3* ].
</font>

<font color=&008080> 
*Tutoraggio 1-2: venerdì 11 marzo 2016*

   * Compilazione ed esecuzione di un programma C.
   * Opzioni base del =gcc=.
   * Cenni all'uso del debugger.
   * Esercizi: alcune funzioni scritte in Tiny-C. 
</font>

<font color=#336699> 
*Venerdì 11 Marzo 2016 - Lezioni 5-6*

*Notazione asintotica (2)*
   * Esempi di problemi che si possono risolvere in modo più o meno efficiente e loro costo computazionale
      * somma dei primi n interi
      * valutazione di un polinomio in un punto
      * ricerca di un elemento in un vettore
Il problema della ricerca
   * ricerca sequenziale e suo costo computazionale nel caso migliore e peggiore
   * ricerca dicotomica e suo costo computazionale nel caso migiore e peggiore

*Esercizi assegnati:*
   * Calcolare l'andamento asintotico di alcune sommatorie
   * Calcolare il costo computazionale del Bubble Sort
</font>

<font color=#336699> 
*Lunedì 14 Marzo 2016 - Lezioni 7-8*

Ricorsione (1)
   * funzioni matematiche ricorsive;
   * ricerca sequenziale e binaria: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;
   * altri esempi di problemi risolti con algoritmi ricorsivi e nota sulla pila di sistema.

*Esercizi assegnati:*
   * Progettare degli algoritmi ricorsivi ed esprimerli tramite pseudocodice che risolvano i seguenti problemi:
      * dato in input un vettore, visualizzare i suoi valori al contrario (dall'ultimo al primo)
      * calcolare la somma di n numeri reali inseriti da tastiera (uno per ogni chiamata ricorsiva)
      * calcolare il MCD tra due interi positivi x ed y come segue:
         * sia y<x
         * se y=0 allora MCD(x,y)=y
         * altrimenti MCD(x,y))MCD(y, x%y)
</font>

<font color=black> 
*Esercitazioni 5-6: mercoledì 16 marzo 2016*

   * Riscaldamento sulla ricorsione: Moltiplicazione egiziana [versione iterativa in *D2*, sez. *4* ]. 
   * Ricorsione: funzione di Fibonacci. Efficienza e albero delle chiamate generato.
   * Funzioni: stack di attivazione delle chiamate [ *D2*, sez. *3* ]. 
   * Fibonacci Iterativo. Funzione ricorsiva efficiente [ *D4*, sez. *1.2* ].
   * Dimostrazioni induttive di correttezza per funzione ricorsive [ *D4*, sez. *2* ]. 
   * Trasformazione sistematica di programmi iterativi in ricorsivi [ *D4*, sez. *2* ].
   * Esercizio: predecessore ricorsivo in Tiny(Re)C. Riflessioni sulla completezza computazioneale di Tiny(Re)C.
 
   * *Esercizi consigliati*: Dispensa *4*  [sez. *1.3* e *2.4* ]
</font>

<font color=&008080> 
*Tutoraggio 3-4: venerdì 18 marzo 2016*

   * Anatomia di un errore ricorrente in C: attenzione a = e ==.
   * Esperienze di overflow. 
   * MCD, algoritmo della Maestra.
</font>

<font color=#336699> 
*Venerdì 18 Marzo 2016 - Lezioni 9-10*

Soluzioni delle equazioni di ricorrenza (1)

   * metodo di sostituzione; esempi
   * metodo iterativo; esempi

*Esercizi assegnati:*
   * Calcolare la soluzione delle seguenti equazioni di ricorrenza con i due metodi studiati, tenendo conto che per tutte il caso base è T(1)=&Theta(1):
      * T(n)=2T(n/2)+&Theta;(n)
      * T(n)=3T(n/2)+&Theta;(n)
      * T(n)=3T(n/4)+&Theta;(n)
      * T(n)=2T(n/2)+&Theta;(n^2)
      * T(n)=2T(n/2)+&Theta;(n^3)
      * T(n)=T(n-1)+&Theta;(n)
</font>

<font color=#336699> 
*Lunedì 21 Marzo 2016 - Lezioni 11-12*

Soluzioni delle equazioni di ricorrenza (2)

   * metodo dell'albero; esempi
   * metodo principale: enunciato del teorema senza dimostrazione ed esempi 
   * esempi di soluzione di equazioni di ricorrenza tramite i quattro metodi

*Esercizi assegnati:*
   * Calcolare la soluzione delle equazioni di ricorrenza assegnate la scorsa lezione con i due metodi studiati, ove possibile.
</font>

<font color=black> 
*Esercitazioni 7-8: mercoledì 23 marzo 2016*
   * Funzioni inerentemente ricorsive: il problema della torre di Hanoi [ *D4*, sez. *3.1* ]. 
   * Passaggio di parametri: indirizzo e valore. Primi passi coi puntatori [ *D3*, sez. *1.1* ].
      * Esempio: Scambia senza variabile di appoggio. Side effects e alias [ *D3*, sez. *1.2* ].
   * Digressione sui tipi: caratteri, interi, coercions e type cast. 

   * *Esercizi consigliati*: Dispensa *3*  [sez. *1.3* ] e Dispensa *4* [sez. *3.3* esercizi *5-8* ].
  </font>

<font color=red> 
*Vacanze di Pasqua*
</font>

<font color=black> 
*Esercitazioni 9-10: mercoledì 30 marzo 2016*
   * Presentazione Homework di Prova.
   * Ancora sui parametri passati per "indirizzo".
      * Esempio: funzione =void assPar(int *x, int *y, int v, int u)= che esegue l'assegnamento parallelo à la Dijkstra o Python.
      * Esempio: funzione =int divRef(int m, int n, int* q, int* r)=  che calcola divisibilità, quoziente e resto simultaneamente.  
   * Call-by-value. Impossibilità di scrivere una funzione =int myOr(int, int)= (e =int myAnd(int, int)=) semanticamente equivalenti a =||= (e =&&=).
   * *Esercizio*: funzione maxPrimo (esonero 2014). Soluzione ricorsiva. [ *S4* ]
   * Vettori in C. Vettori e puntatori. Esempio semplice: stampa di un vettore [ *D6*, sez. *1* ].

   * *Esercizi consigliati*: Dispensa *6*  [sez. *1.3* ]
  </font>

<font color=#336699> 
*Venerdì 1 Aprile 2016 - Lezioni 13-14*
Il problema dell'ordinamento (1)
   * algoritmi naif: insertion sort, selection sort e bubble sort; calcolo del costo computazionale
   * albero delle decisioni e teorema sulla limitazione inferiore per la complessità di un algoritmo per confronti

*Esercizi assegnati:*

   * Nell'algoritmo dell'insertion sort, la ricerca della posizione in cui inserire l'elemento corrente può essere effettuata tramite una ricerca binaria. Calcolare il costo computazionale dell'algoritmo così modificato.
   * Scrivere in pseudocodice una funzione che, dato un vettore A ed un indice j, calcoli il valore minimo nel sottovettore A[j..n]. Riscrivere lo pseudocodice del selection sort che utilizzi ripetutamente questa funzione. 
   * Modificare l'algoritmo di Bubble Sort in modo che non prosegua la computazione se il vettore risulta ordinato.
   * Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (prima versione).
</font>

<font color=#336699> 
*Lunedì 4 Aprile 2016 - Lezioni 15-16*
Il problema dell'ordinamento (2)

   * algoritmi efficienti: 
      * paradigma del divide et impera
      * merge sort (pseudocodice e costo computazionale, pseudocodice della funzione Fondi, problematica dell'ordinamento in loco)
      * quick sort (pseudocodice e costo computazionale nel caso peggiore e migliore)


*Esercizi assegnati:*
   * Scrivere la funzione di fusione ricorsiva
   * Determinare l'albero delle decisioni della funzione di fusione, quando i vettori da fondere sono a1 a2 e b1 b2 (con l'implicita ipotesi che a1<a2 e b1<b2)
   * Modificare l'algoritmo di MergeSort in modo che venga eseguito il Selection Sort sui sottovettori di dimensione k (per un fissato paramentro k). Trovare il massimo valore di k che garantisca comunque costo computazionale ottimo.
   * Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (di nuovo: ma questa volta il costo computazionale dovrebbe essere un O(n log n))
</font>

<font color=black> 
*Esercitazioni 11-12: mercoledì 6 aprile 2016*
   * Rivisitazione Homework di Prova.
   * Ancora sui vettori: il problema dei Coefficienti Binomiali [ *D6*, sez. *2* ]
   * Vettori definiti globali e vettori locali alle funzioni. Allocazione dinamica di un vettore. 
   * *Esercizio*: funzione baricentro (esonero 2012). [ *S1* ]

   * *Esercizi consigliati*: Dispensa *6*  [sez. *2.6* ]
  </font>

<font color=#336699> 
*Venerdì 8 Aprile 2016 - Lezioni 17-18*
Il problema dell'ordinamento (3)
   * algoritmi efficienti: quick sort (pseudocodice della funzione Partiziona, costo computazionale nel caso medio, problematica della randomizzazione)
   * algoritmi efficienti: heapsort (struttura dati heap, heapify: pseudocodice)

*Esercizi assegnati:*
   * Sia dato un vettore di lunghezza n contenente solo valori 0 e 2. Si progetti un algoritmo con costo computazionale lineare che modifichi il vettore in modo che tutte le occorrenze di 0 si trovino più a sinistra di tutte le occorrenze di 2.
   * Si considerino i valori 0 1 2 3 4 5 6 7. Si determini una permutazione di questi valori che generi il caso peggiore per l'algortimo Quick sort. 
   * Calcolare il costo computazionale del Quick sort nel caso in cui il vettore contenga tutti elementi uguali.
   * Calcolare il costo computazionale del Quick sort nel caso in cui il vettore sia già ordinato da sinistra a destra.
</font>

<font color=#336699> 
*Lunedì 11 Aprile 2016 - Lezioni 19-20*
Il problema dell'ordinamento (4)
   * algoritmi efficienti: heapsort (heapify, buildheap, e heapsort: pseudocodice e costo computazionale)
   * algoritmi lineari: counting sort (versione semplificata e cenno alla versione completa)

*Esercizi assegnati:*
   * Scrivere lo pseudocodice di Heapsort nel caso in cui, come struttura dati, si usi un heap minimo (cioè tale che A[i]>=A[parent(i)]), che mantiene il minimo nella radice.
   * Scrivere lo pseudocodice di una funzione che, dato un heap, ritorni l'elemento con chiave minima. Valutare il costo computazionale.
   * Discutere la ragionevolezza di una struttura dati in cui:
      * si costruisce in tempo lineare
      * il minimo si trova in tempo costante
      * dopo l'estrazione del minimo, si riaggiusta in tempo costante
</font>

<font color=black> 
*Esercitazioni 13-14: mercoledì 13 aprile 2016*

Esercizi su vettori e ricorsione in in vista dell'esonero.
   * ==maxPrimo== iterativa [ *S4* ];
   * Virtuosismi I: baricentro con unica scansione ricorsiva [ *S1* ]
   * ==merge== tra due vettori ordinati ricorsiva;
   * Virtuosismi II: merge ricorsiva da Vero Programmatore C [ *L2* ]

   * *Esercizi consigliati*: Di tutto un po' su ricorsione, puntatori e vettori.
  </font>


<font color=#336699> 
*Venerdì 15 Aprile 2016 - Lezioni 21-22*
Esercizi in preparazione dell'esonero
</font>

<font color=red> 
*18-22 Aprile 2016 - Settimana di interruzione della didiattica*
</font>

<font color=black> 
*Esercitazioni 15-16: mercoledì 27 aprile 2016*
   * Correzione esonero: generazione ricorsiva delle combinazioni. Funzione ==allCbnRec==.  [ *S5* ];
   * Introduzione alle matrici: allocazione statica e dinamica [ *D7*, *sez. 2.1* ].
   * Metodologia Top-Down (o raffinamenti successivi): il gioco del Forza4 [ *D7*, *sez. 2.2* ].
  </font>

<font color=#336699>  
*Venerdì 29 Aprile 2016 - Lezioni 23-24*
   * Correzione esonero.
   * Strutture dati fondamentali (1)
      * strutture dati ed insiemi dinamici
      * confronto tra vettore qualunque e vettore ordinato
      * introduzione alle liste: ricerca e inserimento in testa
 </font>


<font color=#336699>  
*Lunedì 2 Maggio 2016 - Lezioni 25-26* 
   * Strutture dati fondamentali (2)
      * cancellazione nelle liste, liste doppiamente puntate e liste circolari
      * la struttura dati coda
      * le operazioni enqueue e dequeue
      * code con priorità
      * pila
      * le operazioni Push e Pop
      * Esercizio: simulazione di una coda tramite due pile

*Esercizi assegnati:*
   * scrivere sia lo pseudocodice che il codice C delle funzioni Enqueue e Dequeue quando la coda sia circolare ed implementata su vettore
   * scrivere sia lo pseudocodice che il codice C delle funzioni Pop, Push e Pila_Piena quando la pila sia implementata su vettore
  </font>

<font color=black> 
*Esercitazioni 17-18: mercoledì 4 maggio 2016*
   * Il gioco del Forza4: funzioni di verifica vittoria (scorrimento di linee di una matrice).  [ *D7*, *sez. 2.2* ];
   * Definizione di tipi di dato: strutture.
   * Tipi di dato = valori + operazioni. Esempio: tipo Data [ *D8*, *sez. 1* ].
   * Tipo di dato lista (o sequenza): definizione induttiva.
   * Tipo di dato lista: rappresentazione in linguaggio C. Costruttori (==cons==) e distruttori (==isEmpty==) delle Liste  [ *D8*, *sez. 3* ].
 
   * *Esercizi consigliati*: esercizi su matrici [ *D7*, *sez. 2.4* ].
</font>

<font color=#336699>  
*Venerdì 6 Maggio 2016 - Lezioni 27-28* 
   * Strutture dati fondamentali (3)
      * alberi
         * definizione tramite la nozione di grafo
         * caratterizzazione degli alberi
         * alberi binari completi: relazione tra altezza e numero di nodi
         * memorizzazione degli alberi:
            * tramite record e puntatori
            * posizionale
            * tramite vettore dei padri
         *cenni alle visite di alberi

*Esercizi assegnati:*
   * dato un albero tramite vettore dei padri, restituirlo in output tramite notazione posizionale. Calcolare il costo computazionale
   * dato un albero tramite notazione posizionale, restituirlo in output tramite vettore dei padri. Calcolare il costo computazionale
 </font>

<font color=#336699>  
*Lunedì 9 Maggio 2016 - Lezioni 29-30* 
   * Strutture dati fondamentali (4)
      * visite di alberi: in-ordine, pre-ordine e post-ordine
         * pseudocodice ricorsivo
         * costo computazionale tramite equazione di ricorrenza e metodo di sostituzione
         * esercizi che si risolvono utilizzando le visite
      * esercizi che si risolvono usando alberi, pile e code
</font>

<font color=black> 
*Esercitazioni 19-20: mercoledì 11 maggio 2016*
   * Alcune funzioni del forza4: verifica vittoria [ *D7*, *sez. 3* ]. 
   * Liste: costruzione di una lista  [ *D8*, *sez. 3* ]. 
   * Funzioni base sulle liste: lunghezza, somma etc.
   * Equazioni ricorsive per specificare funzioni sulle liste. 
   * Funzioni ==Fun== che creano nuove liste e funzioni ==Rec== che modificano la lista in ingresso: vantaggi e svantaggi. 
   * Side effects: *attenzione!* [ *D8*, *sez. 4.3* ]

   * *Esercizi consigliati*: esercizi su matrici e liste [ *D8*, dopo *sez. 3.5* ].
</font>

<font color=#336699>  
*Venerdì 13 Maggio 2016 - Lezioni 31-32* 

   * Dizionari (1)
      * tabelle ad indirizzamento diretto
      * tabelle hash
         * ipotesi di uniformità semplice e fattore di carico
         * soluzione delle collisioni tramite liste di trabocco
         * soluzione delle collisioni tramite indirizzamento aperto
       * Alberi binari di ricerca (ABR):
         * algoritmo di ricerca
         * algoritmo per il massimo e minimo
</font>

<font color=#336699>  
*Lunedì 16 Maggio 2016 - Lezioni 33-34* 
   * Dizionari (2)
       * Alberi binari di ricerca (ABR) - segue:
         * algoritmo per il successore e predecessore
         * algoritmo di inserimento
         * algoritmo di cancellazione
         * osservazioni sul costo computazionale delle operazioni viste come funzione dell'altezza
         * introduzione degli alberi Rosso-Neri: definizione e dimostrazione dell'altezza logaritmica

*Esercizi assegnati:*
   * Dato due alberi binari di ricerca T1 e T2, progettare un algoritmo che produca in output un terzo albero binario di ricerca T contenente le chiavi di T1 e di T2. Fare le considerazioni del caso riguardo al costo computazionale.
 </font>

<font color=black> 
*Esercitazioni 21-22: mercoledì 18 maggio 2016*
   * Funzione che aggiunge in coda e ==append==.
   * Rovesciamento di una lista:
       * funzione == reverseFun== quadratica, ==reverseFun== lineare, funzione ==reverseRec== che sposta i puntatori [ *D8*, *sez. 3.4* ]. 
   * Liste: problemi che eliminano elementi e deallocazione di memoria. 
   * Funzioni ==remove== (versione Fun, Rec e It), ==diffLista== , versioni Fun, Rec ed iterative [ *D8*, *sez. 3.5* ].
   * Cenni a variazioni sul tema: liste ordinate, liste doppiamente concatenate.

   * *Esercizi consigliati*: esercizi sulle liste [ *D8*, dopo *sez. 3.5* ].
</font>

<font color=#336699>  
*Venerdì 20 Maggio 2016 - Lezioni 35-36* 
   * Grafi (1)
      * Definizioni e semplici proprietà
      * Rappresentazione in memoria di grafi:
         * liste di adiacenza
         * matrice di adiacenza
         * matrice di incidenza
         * lista di archi
         * confronto tra rappresentazioni
      * Visite di grafi
      * Alberi di visita

*Esercizi assegnati:*
   * Dato G memorizzato con una struttura dati X, dare in output G memorizzato con un'altra struttura dati Y, dove X ed Y variano in tutti i modi possibili tra le 4 rappresentazioni viste
 </font>

<font color=#336699>  
*Lunedì 23 Maggio 2016 - Lezioni 37-38* 
   * Grafi (2)
      * Visita in ampiezza: pseudocodice, costo computazionale in funzione della struttura dati usata, proprietà dell'albero di visita in ampiezza
      * Esempi di uso di visita in ampiezza: cammini più corti
      * Visita in profondità: pseudocodice, costo computazionale in funzione della struttura dati usata, proprietà dell'albero di visita in profondità


*Esercizi assegnati:*
   * Modificare lo pseudocodice della visita in ampiezza in modo che restituisca la lunghezza dei cammini minimi da un fissato nodo v a tutti gli altri nodi.
   * Dato un grafo G mediante le sue liste di adiacenza, progettare un algoritmo che dica se G è aciclico oppure no.
   * Dato un grafo G mediante le sue liste di adiacenza, progettare un algoritmo che restituisca il numero delle componenti connesse di G.
</font>

<font color=black> 
*Esercitazioni 23-24: mercoledì 25 maggio 2016*
   * Introduzione agli alberi. Definizione induttiva di albero.
   * Rappresentazione in C di un albero, a puntatori  [ *D9*, *sez. 1.1* ].
   * Costruttori e distruttori degli alberi  [ *D9*, *sez. 1.1* ].
   * Funzioni ricorsive tipiche sugli alberi: .

   * *Esercizi consigliati*: esercizi su alberi [ *D9*, dopo *sez. 1.6* ].
</font>


<font color=#336699>  
*Venerdì 27 Maggio 2016 - Lezioni 39-40* 
   * Grafi (3)
      * Esercizi su grafi: cammini più corti e calcolo delle componenti connesse
      * Grafi euleriani e loro caratterizzazione
      * Grafi bipartiti e loro caratterizzazione
      * Accoppiamenti massimi e massimali
      * Colorazioni minime e minimali
</font>
<font color=#336699>
*Esercizi assegnati:*
   * Dato un grafo G mediante le sue liste di adiacenza, progettare un algoritmo che dica se ci sono due nodi con lo stesso grado.
   * Dato un grafo G mediante matrice di adiacenza, memorizzare il grafo complemento ed il grafo quadrato.

</font>


<font color=#336699>  
*Lunedì 30 Maggio 2016 - Lezioni 41-42* 
   * Esercizi di riepilogo in vista del secondo esonero e dell'esame scritto
</font>

<font color=#336699>  
*Lunedì 6 Giugno 2016 - Lezioni 43-44* 
   * Esercizi di riepilogo in vista del secondo esonero e dell'esame scritto
</font>




---+++ <font color=#336699 size="+1"> A.A. 2014/2015</font>

<font color=#336699> 
*Lunedì 2 Marzo 2015 - Lezioni 1-2*

*Introduzione (1)*
   * Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale.
   * modello RAM; misura di costo uniforme e logaritmico.
</font>

<font color=#336699> 
*Venerdì 6 Marzo 2015 - Lezioni 3-4*

*Introduzione (2)*
   * esempio di utilizzo delle misure di costo uniforme e logaritmico.
   * Pseudocodice

*Notazione asintotica (1)*
   * Definizione e significato degli insiemi O, &Omega; e &Theta;.
   * Algebra della notazione asintotica
   * Esempi

*Esercizi assegnati:*
   * Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione
</font>

<font color=#336699> 
*Lunedì 9 Marzo 2015 - Lezioni 5-6*

*Notazione asintotica (2)*
   * Valutazione del costo computazionale di un algoritmo
   * Esempi
   * Esempi di problemi che si possono risolvere in modo più o meno efficiente
      * somma dei primi n interi
      * valutazione di un polinomio in un punto
      * ricerca di un elemento in un vettore

*Esercizi assegnati:*
   * Calcolare l'andamento asintotico di alcune funzioni
   * Calcolare il costo computazionale degli algoritmi di Selection Sort, Insertion Sort e Bubble Sort (pseudocodice sulle dispense)
</font>

<font color=black> 
*Esercitazioni 1-2: mercoledì 11 marzo 2015*

Introduzione al Linguaggio C.<br>
Cenni alla struttura di un programma C. Funzione main().<br>
Primo programma in C: Helloworld.<br>
Semplici funzioni: somma e predecessore avendo un esecutore in grado solo di sommare 1.<br>
</font>

<font color=#336699> 
*Venerdì 13 Marzo 2015 - Lezioni 7-8*

Il problema della ricerca
   * ricerca sequenziale e suo costo computazionale nel caso migliore e peggiore
   * ricerca dicotomica e suo costo computazionale nel caso migiore e peggiore

Ricorsione (1)
   * funzioni matematiche ricorsive;
   * calcolo del fattoriale: pseudocodice iterativo, ricorsivo e calcolo dell'equazione di ricorrenza;
   * ricerca sequenziale: pseudocodice ricorsivo;

*Esercizi assegnati:*
   * Progettare degli algoritmi ricorsivi ed esprimerli tramite pseudocodice che risolvano i seguenti problemi:
      * dato in input un vettore, visualizzare i suoi valori al contrario (dall'ultimo al primo)
      * calcolare la somma di n numeri reali inseriti da tastiera (uno per ogni chiamata ricorsiva)
      * calcolare il MCD tra due interi positivi x ed y come segue:
         * sia y<x
         * se y=0 allora MCD(x,y)=y
         * altrimenti MCD(x,y))MCD(y, x%y)
</font>

<font color=#336699> 
*Lunedì 16 Marzo 2015 - Lezioni 9-10*

Ricorsione (2)
   * ricerca sequenziale: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;
   * ricerca binaria: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza.

Soluzioni delle equazioni di ricorrenza (1)

   * metodo di sostituzione; esempi
   * metodo iterativo; esempi

*Esercizi assegnati:*
   * Scrivere lo pseudocodice iterativo e ricorsivo, e per entrambe le versioni calcolare il costo computazionale, di algoritmi che risolvono i seguenti problemi:
      * dati in input due interi, n e k, calcolare n^k
      * calcolare la somma degli elementi di un vettore dato in input
      * verificare se un dato vettore di caratteri è palindromo
      * trovare il minimo di un vettore dato in input
</font>

<font color=black> 
*Esercitazioni 3-4: mercoledì 18 marzo 2015*

Ancora semplici funzioni in linguaggio C: divisione intera.<br>
Cenni all'uso di asserzioni logiche: precondizioni, postcondizioni e invarianti nella progettazione di un programma iterativo.<br>
Funzioni: stato locale e globale. Stack di attivazione delle funzioni.<br>
Passaggio di parametri: passaggi per valore e per indirizzo.<br>
Esempio: funzione scambia.<br>
Cenni alla definizione per induzione di funzioni (somma) e relativa funzione ricorsiva in C.
</font>

<font color=#336699> 
*Venerdì 20 Marzo 2015 - Lezioni 11-12*

Soluzioni delle equazioni di ricorrenza (2)

   * metodo dell'albero; esempi
   * metodo principale: enunciato del teorema senza dimostrazione ed esempi 
   * esempi di soluzione di equazioni di ricorrenza tramite i quattro metodi

*Esercizi assegnati:*
   * Calcolare la soluzione delle seguenti equazioni di ricorrenza con quanti più metodi è possibile, tenendo conto che per tutte il caso base è T(1)=&Theta(1):
      * T(n)=2T(n/2)+&Theta;(n)
      * T(n)=3T(n/2)+&Theta;(n)
      * T(n)=3T(n/4)+&Theta;(n)
      * T(n)=2T(n/2)+&Theta;(n^2)
      * T(n)=T(n/3)+T(2/3n)+&Theta;(n)
      * T(n)=4T(n/2)+&Theta;(n)
      * T(n)=2T(n/2)+&Theta;(n^3)
      * T(n)=16T(n/4)+&Theta;(n^2)
      * T(n)=T(n-1)+&Theta;(n)
      * T(n)=3T(n/2)+&Theta;(n log n)
</font>

<font color=#336699> 
*Lunedì 23 Marzo 2015 - Lezioni 13-14*
Il problema dell'ordinamento (1)
   * algoritmi naif: insertion sort, selection sort e bubble sort; calcolo del costo computazionale
   * albero delle decisioni e teorema sulla limitazione inferiore per la complessità di un algoritmo per confronti

*Esercizi assegnati:*

   * Nell'algoritmo dell'insertion sort, la ricerca della posizione in cui inserire l'elemento corrente può essere effettuata tramite una ricerca binaria. Calcolare il costo computazionale dell'algoritmo così modificato.
   * Scrivere in pseudocodice una funzione che, dato un vettore A ed un indice j, calcoli il valore minimo nel sottovettore A[j..n]. Riscrivere lo pseudocodice del selection sort che utilizzi ripetutamente questa funzione. 
   * Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (prima versione).
</font>

<font color=black> 
*Esercitazioni 5-6: mercoledì 25 marzo 2015*

Esempio di funzione ricorsiva: calcolo dei numeri di Fibonacci.<br>
Inefficienza della funzione ricorsiva che calcola i numeri di Fibonacci: albero delle chiamate ricorsive.<br>
Programma iterativo che calcola i numeri di Fibonacci.<br>
Programma ricorsivo efficiente. Cenni alla trasformazione sistematica di programmi iterativi in ricorsivi.<br>
Problemi con soluzione inerentemente ricorsiva: il problema della torre di Hanoi.<br>
Esercizi: predecessore con ricorsione, moltiplicazione egiziana.<br>
</font>

<font color=#336699> 
*Venerdì 27 Marzo 2015 - Lezioni 15-16*
Il problema dell'ordinamento (2)

   * algoritmi efficienti: paradigma del divide et impera e merge sort (pseudocodice e costo computazionale, problematica dell'ordinamento in loco)

*Esercizi assegnati:*
   * Scrivere la funzione di fusione ricorsiva
   * Determinare l'albero delle decisioni della funzione di fusione, quando i vettori da fondere sono a1 a2 e b1 b2 (con l'implicita ipotesi che a1<a2 e b1<b2)
   * Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (di nuovo: ma questa volta il costo computazionale dovrebbe essere un O(n log n))
</font>

<font color=#336699> 
*Lunedì 30 Marzo 2015 - Lezioni 17-18*
Il problema dell'ordinamento (3)
   * algoritmi efficienti: quick sort (pseudocodice e costo computazionale nel caso peggiore, migliore e medio, problematica della randomizzazione)

*Esercizi assegnati:*
   * Sia dato un vettore di lunghezza n contenente solo valori 0 e 2. Si progetti un algoritmo con costo computazionale lineare che modifichi il vettore in modo che tutte le occorrenze di 0 si trovino più a sinistra di tutte le occorrenze di 2.
   * Si considerino i valori 0 1 2 3 4 5 6 7. Si determini una permutazione di questi valori che generi il caso peggiore per l'algortimo Quick sort. 
   * Calcolare il costo computazionale del Quick sort nel caso in cui il vettore contenga tutti elementi uguali.
   * Calcolare il costo computazionale del Quick sort nel caso in cui il vettore sia già ordinato da sinistra a destra.
</font>

<font color=black> 
*Esercitazioni 7-8: mercoledì 1 aprile 2015*

Introduzione ai vettori in linguaggio C.<br>
Vettori e puntatori.<br>
Esempio: stampa di un vettore con indici, aritmetica dei puntatori e ricorsiva.<br>
Vettori statici e dinamici. Introduzione all'allocazione dinamica.<br>
Esercizio: calcolo del baricentro di un vettore. 
</font>

<font color=red> 
*2-7 Aprile 2015: Vacanze di Pasqua*
</font>

<font color=black> 
*Esercitazioni 9-10: mercoledì 8 aprile 2015*

Esercizi sui Vettori.<br>
Crivello di Eratostene. <br>
Calcolo dei Coefficienti Binomiali.<br>
Uso di vettori per memorizzare i valori già calcolati dalla funzione ricorsiva.<br>
</font>

<font color=#336699> 
*Venerdì 10 Aprile 2015 - Lezioni 19-20*
Il problema dell'ordinamento (4)
   * algoritmi efficienti: heapsort (struttura dati heap, heapify, buildheap, e heapsort: pseudocodice e costo computazionale)

*Esercizi assegnati:*
   * Scrivere lo pseudocodice di Heapsort nel caso in cui, come struttura dati, si usi un heap minimo (cioè tale che A[i]>=A[parent(i)]), che mantiene il minimo nella radice.
   * Scrivere lo pseudocodice di una funzione che, dato un heap, ritorni l'elemento con chiave minima. Valutare il costo computazionale.
</font>

<font color=black> 
*Esercitazioni 11-12: lunedì 13 aprile 2015*

Esercizi in preparazione all'esonero.<br>
Correzione esonero 2014: scomposizione in fattori primi. <br>
Correzione esonero 2013: verificare se un array è contenuto in un altro. <br>
</font>

<font color=#336699> 
*Mercoledì 15 Aprile 2015 - Lezioni 21-22*
   * Il problema dell'ordinamento (5)
      * algoritmi lineari: counting sort e bucket sort; dettagli nel caso in cui vi siano dati satellite
   * Svolgimento di alcuni esercizi (modifica di una chiave in un heap massimo, ricerca del minimo in un heap)

*Esercizi assegnati:*
   * Dato un vettore di n elementi, tutti compresi tra 0 e k, con k=O(n), verificare se contiene occorrenze ripetute dello stesso elemento (di nuovo: ma questa volta il costo computazionale dovrebbe essere un O(n))
 </font>

<font color=#336699> 
*Venerdì 17 Aprile 2015 - Lezioni 23-24*
   * Esercizi in preparazione dell'esonero
 </font>

<font color=red> 
*20-24 Aprile 2015: Settimana di interruzione della didattica e Primo esonero*
</font>

<font color=#336699>  
*Lunedì 27 Aprile 2015 - Lezioni 25-26*
   * Strutture dati fondamentali (1)
      * strutture dati ed insiemi dinamici
      * confronto tra vettore qualunque e vettore ordinato
      * liste, liste doppiamente puntate e liste circolari
 </font>

<font color=black> 
*Esercitazioni 13-14: mercoledì 29 aprile 2015*

Introduzione alle matrici.<br>
Programmazione top-down: gioco del forza4.<br>
</font>

<font color=#336699>  
*Lunedì 4 Maggio 2015 - Lezioni 27-28* 
   * Strutture dati fondamentali (2)
      * la struttura dati coda
      * le operazioni enqueue e dequeue
      * code con priorità
      * pila
      * le operazioni Push e Pop
      * Esercizio: simulazione di una coda tramite due pile

*Esercizi assegnati:*
   * scrivere sia lo pseudocodice che il codice C delle funzioni Enqueue e Dequeue quando la coda sia circolare ed implementata su vettore
   * scrivere sia lo pseudocodice che il codice C delle funzioni Pop, Push e Pila_Piena quando la pila sia implementata su vettore
  </font>

<font color=black> 
*Esercitazioni 15-16: mercoledì 6 maggio 2015*

Ancora sulle matrici: allocazione statica e dinamica delle matrici.<br>
Rappresentazione in memoria di una matrice.<br>
Esercizi: verifica che una matrice di interi è un quadrato magico.<br>
</font>

<font color=#336699>  
*Venerdì 8 Maggio 2015 - Lezioni 29-30* 
   * Strutture dati fondamentali (3)
      * alberi (1)
         * definizione tramite la nozione di grafo
         * caratterizzazione degli alberi
         * alberi binari completi: relazione tra altezza e numero di nodi
         * memorizzazione degli alberi:
            * tramite record e puntatori
            * posizionale
            * tramite vettore dei padri
         *cenni alle viite di alberi

*Esercizi assegnati:*
   * dato un albero tramite vettore dei padri, restituirlo in output tramite notazione posizionale. Calcolare il costo computazionale
   * dato un albero tramite notazione posizionale, restituirlo in output tramite vettore dei padri. Calcolare il costo computazionale
 </font>

<font color=#336699>  
*Lunedì 11 Maggio 2015 - Lezioni 31-32* 
   * Strutture dati fondamentali (4)
      * alberi (2)
         * visite di alberi: in-ordine, pre-ordine e post-ordine
            * pseudocodice ricorsivo
            * costo computazionale tramite equazione di ricorrenza e metodo di sostituzione
            * esercizi che si risolvono utilizzando le visite
         * esercizi che si risolvono usando alberi, pile e code
</font>

<font color=black> 
*Esercitazioni 17-18: mercoledì 13 maggio 2015*

Strutture.<br>
Liste o sequenze: definizione induttiva.<br>
Rappresentazione in C di liste.<br>
Primi programmi sulle liste: inserimento in testa, in coda.<br>
Funzione reverse e reverse efficiente ricorsiva.<br>
Funzione append.<br>
Versioni che creano nuove liste e funzioni che modificano la lista di input.<br>
</font>

<font color=#336699>  
*Venerdì 15 Maggio 2015 - Lezioni 33-34* 

   * Dizionari (1)
      * tabelle ad indirizzamento diretto
      * tabelle hash
         * ipotesi di uniformità semplice e fattore di carico
         * soluzione delle collisioni tramite liste di trabocco
         * soluzione delle collisioni tramite indirizzamento aperto
       * Alberi binari di ricerca (ABR):
         * algoritmo di ricerca
         * algoritmo per il massimo e minimo
</font>

<font color=#336699>  
*Lunedì 18 Maggio 2015 - Lezioni 35-36* 
   * Dizionari (2)
       * Alberi binari di ricerca (ABR) - segue:
         * algoritmo per il successore e predecessore
         * algoritmo di inserimento
         * algoritmo di cancellazione
         * osservazioni sul costo computazionale delle operazioni viste come funzione dell'altezza
         * introduzione degli alberi Rosso-Neri: definizione e dimostrazione dell'altezza logaritmica
</font>

<font color=black> 
*Esercitazioni 19-20: mercoledì 20 maggio 2015*

Specifica di funzioni su liste tramite equazioni ricorsive.<br>
Liste ordinate. Funzione merge su liste. Versione in-place e versione che genera una nuova lista.<br>
Funzione reverse in-place.<br>
</font>

<font color=#336699>  
*Lunedì 22 Maggio 2015 - Lezioni 37-38* 
   * Grafi (1)
      * Definizioni e semplici proprietà
      * Rappresentazione in memoria di grafi:
         * liste di adiacenza
         * matrice di adiacenza
         * matrice di incidenza
         * lista di archi
         * confronto tra rappresentazioni
      * Visite di grafi
      * Alberi di visita
</font>
<font color=#336699>
*Esercizi assegnati:*
   * Dato G memorizzato con una struttura dati X, dare in output G memorizzato con un'altra struttura dati Y, dove X ed Y variano in tutti i modi possibili tra le 4 rappresentazioni viste
 </font>

<font color=#336699>  
*Lunedì 25 Maggio 2015 - Lezioni 39-40* 
   * Grafi (2)
      * Visita in ampiezza: pseudocodice, costo computazionale in funzione della struttura dati usata, proprietà dell'albero di visita in ampiezza
      * Esempi di uso di visita in ampiezza: cammini più corti
</font>
<font color=#336699>
*Esercizi assegnati:*
   * Modificare lo pseudocodice della visita in ampiezza in modo che restituisca la lunghezza dei cammini minimi da un fissato nodo v a tutti gli altri nodi.
   * Dato un grafo G mediante le sue liste di adiacenza, progettare un algoritmo che dica se G è aciclico oppure no.
   * Dato un grafo G mediante le sue liste di adiacenza, progettare un algoritmo che restituisca il numero delle componenti connesse di G.
</font>

<font color=black> 
*Esercitazioni 21-22: mercoledì 27 maggio 2015*

Definizione induttiva di alberi.<br>
Rappresentazione in C di alberi binari.<br>
Specifica di funzioni su alberi tramite equazioni ricorsive.<br>
Prime funzioni su alberi: costruttori, distruttori, conteggio dei nodi, altezza.<br>
Il problema del bilanciamento: versione naif e versione efficiente con un'unica scansione dell'albero.<br>
</font>

<font color=#336699>  
*Venerdì 29 Maggio 2015 - Lezioni 41-42* 
   * Grafi (3)
      * Visita in profondità: pseudocodice, costo computazionale in funzione della struttura dati usata, proprietà dell'albero di visita in profondità
      * Esercizi su grafi: calcolo delle componenti connesse
      * Grafi euleriani e loro caratterizzazione
</font>
<font color=#336699>
*Esercizi assegnati:*
   * Dato un grafo G mediante le sue liste di adiacenza, progettare un algoritmo che dica se ci sono due nodi con lo stesso grado.
   * Dato un grafo G mediante matrice di adiacenza, memorizzare il grafo complemento ed il grafo quadrato.

</font>

<font color=black> 
*Esercitazioni 23-24: mercoledì 3 giugno 2015*

Esercitazione in vista dell'esame.<br>
Compiti precedenti: somma successivi e somma precedenti in una lista.<br>
Trucchi: usare i parametri per memorizzare valori in corso di computazione: stampa indentata di un albero.<br>
Altri esercizi sugli alberi: relazione di uguaglianza e di sottoalbero.<br>
</font>

<font color=#336699>  
*Venerdì 5 Giugno 2015 - Lezioni 43-44* 
   * Esercizi di riepilogo in vista del secondo esonero e dell'esame scritto
</font>






---+++ <font color=#336699 size="+1"> A.A. 2013/2014</font>

<font color=#FF6600> 
*Giovedì 6 Marzo 2014 - Lezioni 1-2*

Introduzione
   * Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale;
   * modello RAM; misura di costo uniforme e logaritmico.
   * Pseudocodice
</font>

<font color=#660099> 
*Venerdì 7 Marzo 2014 - Esercitazioni 1-2*
   * Struttura di un programma C: variabili, tipi, dichiarazioni. Il programma helloWorld.
   * tinyC: assegnazione, costrutto condizionale e iterazione.
   * Giocando col tinyC: somma e predecessore partendo dall'operazione di successore e test di uguaglianza. 
   * Introduzione all'uso di asserzioni nella stesura di programmi: precondizioni, postcondizioni, invarianti. 
</font>

<font color=#FF6600> 
*Lunedì 10 Marzo 2014 - Lezioni 3-4*

Notazione asintotica (1)
   * Definizione e significato degli insiemi O, &Omega; e &Theta;.
   * Algebra della notazione asintotica
   * Esempi
   * Valutazione della complessità computazionale di un algoritmo
</font>
<font color=#336699> 
*Esercizi assegnati:*
   * Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione
   * Calcolare l'andamento asintotico di alcune funzioni
   * Calcolare il costo computazionale degli algoritmi di Selection Sort, Insertion Sort e Bubble Sort (pseudocodice sulle dispense)
</font>

<font color=#FF6600> 
*Giovedì 13 Marzo 2014 - Lezioni 5-6*

Notazione asintotica (2)
   * Esempi di problemi che si possono risolvere in modo più o meno efficiente
      * somma dei primi n interi
      * valutazione di un polinomio in un punto
      * ricerca di un elemento in un vettore

Il problema della ricerca
   * ricerca sequenziale e suo costo computazionale nel caso migliore, peggiore e medio
   * ricerca dicotomica e suo costo computazionale nel caso migiore e peggiore
</font>
<font color=#336699> 
*Esercizi assegnati:*
   * Calcolare il caso migliore e peggiore del costo computazionale degli algoritmi di Selection Sort, Insertion Sort e Bubble Sort (pseudocodice sulle dispense)
</font>

<font color=#33CC00> 
*Giovedì 13 marzo 2014 - Tutoraggio 1*
   * Scrittura, compilazione ed esecuzione di un programma C. 
   * Esercizi: hello_world, stampa del successivo (uso di printf e scanf), stampa della somma, dei primi n numeri (costrutto iterativo while, for, e if ... else.    
</font>

<font color=#660099> 
*Venerdì 14 Marzo 2014 - Esercitazioni 3-4*
   * Progettazione di una funzione a partire dalle asserzioni logiche: la divisione intera.
   * Esercizi: differenza, test di minore uguale (funzione compare). 
   * Paradiso e inferno: proprietà algebriche versus fenomeni computazionali: non commutatività dell'operatore &&. 
   * Per me si va ne la città dolente: introduzione ai puntatori. Dichiarazione, operatori * e &.
</font>

<font color=#FF6600> 
*Lunedì 17 Marzo 2014 - Lezioni 7-8*

Ricorsione
   * funzioni matematiche ricorsive;
   * calcolo del fattoriale: pseudocodice iterativo, ricorsivo e calcolo dell'equazione di ricorrenza;
   * ricerca sequenziale: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;
   * ricerca binaria: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;
   * numeri di Fibonacci: pseudocodice iterativo, ricorsivo e calcolo dell'equazione di ricorrenza;
</font>

<font color=#336699>
*Esercizi assegnati:*
   * Progettare degli algoritmi ricorsivi ed esprimerli tramite pseudocodice che risolvano i seguenti problemi:
      * dato in input un vettore, visualizzare i suoi valori al contrario (dall'ultimo al primo)
      * calcolare la somma di n numeri reali inseriti da tastiera (uno per ogni chiamata ricorsiva)
      * calcolare il MCD tra due interi positivi x ed y come segue:
         * sia y<x
         * se y=0 allora MCD(x,y)=y
         * altrimenti MCD(x,y))MCD(y, x%y)
</font>

<font color=#FF6600> 
*Lezioni 9-10: giovedì 20 marzo 2014*
Soluzioni delle equazioni di ricorrenza (1)

   * metodo di sostituzione
   * metodo iterativo
   * metodo dell'albero
   * esempi di soluzione di equazioni di ricorrenza tramite i tre metodi
</font>
<font color=#336699>
*Esercizi assegnati:*
   * Calcolare la soluzione delle seguenti equazioni di ricorrenza con quanti più metodi è possibile, tenendo conto che per tutte il caso base è T(1)=&Theta(1):
      * T(n)=2T(n/2)+&Theta;(n)
      * T(n)=3T(n/2)+&Theta;(n)
      * T(n)=3T(n/4)+&Theta;(n)
      * T(n)=2T(n/2)+&Theta;(n^2)
      * T(n)=T(n/3)+T(2/3n)+&Theta;(n)
      * T(n)=4T(n/2)+&Theta;(n)
      * T(n)=2T(n/2)+&Theta;(n^3)
      * T(n)=16T(n/4)+&Theta;(n^2)
      * T(n)=T(n-1)+&Theta;(n)
      * T(n)=3T(n/2)+&Theta;(n log n)
   * Scrivere lo pseudocodice iterativo e ricorsivo, e per entrambe le versioni calcolare il costo computazionale, di algoritmi che risolvono i seguenti problemi:
      * dati in input due interi, n e k, calcolare n^k
      * calcolare la somma degli elementi di un vettore dato in input
      * verificare se un dato vettore di caratteri è palindromo
      * trovare il minimo di un vettore dato in input
</font>

<font color=#33CC00> 
*Giovedì 20 marzo 2014 - Tutoraggio 2*
   * Funzioni sui numeri naturali.
   * Funzione MCD: algoritmo ingenuo, mcdDellaMaestra, mcdEuclide.    
</font>

<font color=#660099> 
*Venerdì 21 Marzo 2014 - Esercitazioni 5-6*
   * Uso dei puntatori nel passaggio dei parametri. Funzione scambia.
   * Stack di attivazione delle chiamate di funzione. 
   * Cenni all'aritmetica dei puntatori. 
   * Quivi sospiri, pianti e alti guai: Alias e side effects. 
   * Esempio: funzione scambia senza variabile d'appoggio e suoi problemi. 
   * Uso dei parametri passati per indirizzo per ritornare piu' valori. Funzione divisione che calcola contemporaneamente quoziente e resto.
   * Introduzione ai vettori. Vettori statici e dinamici. Corrispondenza tra vettori e puntatori. 
</font>

<font color=#FF6600> 
*Lezioni 11-12: lunedì 24 marzo 2014*
Soluzioni delle equazioni di ricorrenza (2)
   * metodo principale (senza dimostrazione) ed esempi

Il problema dell'ordinamento (1)
   * algoritmi naif: insertion sort, selection sort e bubble sort; calcolo del costo computazionale

</font>
<font color=#336699>
*Esercizi assegnati:*
   * Risolvere le equazioni di ricorrenza assegnate durante la scorsa lezione con il metodo principale

   * Nell'algoritmo dell'insertion sort, la ricerca della posizione in cui inserire l'elemento corrente può essere effettuata tramite una ricerca binaria. Calcolare il costo computazionale dell'algoritmo così modificato.
   * Scrivere in pseudocodice una funzione che, dato un vettore A ed un indice j, calcoli il valore minimo nel sottovettore A[j..n]. Riscrivere lo pseudocodice del selection sort che utilizzi ripetutamente questa funzione. 
   * Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento.
</font>

<font color=#FF6600> 
*Lezioni 13-14: giovedì 27 marzo 2014*

Il problema dell'ordinamento (2)
   * albero delle decisioni e teorema sulla limitazione inferiore per la complessità di un algoritmo per confronti
   * algoritmi efficienti: paradigma del divide et impera e merge sort (pseudocodice e costo computazionale)
</font>
<font color=#336699>
*Esercizi assegnati:*
   * Scrivere la funzione di fusione ricorsiva
   * Determinare l'albero delle decisioni della funzione di fusione, quando i vettori da fondere sono a1 a2 e b1 b2 (con l'implicita ipotesi che a1<a2 e b1<b2)
   * Risolvere l'equazione di ricorrenza del Merge sort con tutti i metodi studiati
   * Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (di nuovo: ma questa volta il costo computazionale dovrebbe essere un O(n log n))
</font>

<font color=#33CC00> 
*Giovedì 27 marzo 2014 - Tutoraggio 3*
   * Esercizi sui puntatori: operatori * e &. Aritmetica dei puntatori.
   * Passaggi di parametro per indirizzo.    
</font>

<font color=#660099> 
*Venerdì 28 Marzo 2014 - Esercitazioni 7-8*
   * Vettori: uso dell'aritmetica dei puntatori per scorrere un vettore. Stampa di un vettore.
   * Sviluppo di programmi corretti con i vettori: minimo di un vettore.
   * Esempio di programma su vettori: il Crivello di Eratostene.  
   * Fatti non foste per viver come bruti: funzioni ricorsive. 
   * Esempio di problema inerentemente ricorsivo: la Torre di Hanoi. 
</font>

<font color=#FF6600> 
*Lezioni 15-16: lunedì 31 marzo 2014*

Il problema dell'ordinamento (3)
   * algoritmi efficienti: quick sort (pseudocodice e costo computazionale nel caso peggiore e nel caso medio, randomizzazione)
</font>
<font color=#336699>
*Esercizi assegnati:*
   * Sia dato un vettore di lunghezza n contenente solo valori 0 e 2. Si progetti un algoritmo con costo computazionale lineare che modifichi il vettore in modo che tutte le occorrenze di 0 si trovino più a sinistra di tutte le occorrenze di 2.
   * Si considerino i valori 0 1 2 3 4 5 6 7. Si determini una permutazione di questi valori che generi il caso peggiore per l'algortimo Quick sort. 
   * Calcolare il costo computazionale del Quick sort nel caso in cui il vettore contenga tutti elementi uguali ed in cui sia già ordinato da destra a sinistra.
</font>

<font color=#FF6600> 
*Lezioni 17-18: giovedì 3 aprile 2014*
   * Il problema dell'ordinamento (4)
      * algoritmi efficienti: heapsort (struttura dati heap, heapify, buildheap, e heapsort: pseudocodice e costo computazionale)
 </font>

<font color=#336699>
*Esercizi assegnati:*
   * Scrivere lo pseudocodice di Heapsort nel caso in cui, come struttura dati, si usi un heap minimo (cioè tale che A[i]>=A[parent(i)]), che mantiene il minimo nella radice.
   * Scrivere lo pseudocodice di una funzione che, dato un heap, ritorni l'elemento con chiave minima. Valutare il costo computazionale.
 </font>

<font color=#33CC00> 
*Giovedì 3 aprile 2014 - Tutoraggio 4*
   * Esercizi sui vettori.    
</font>

<font color=#660099> 
*Venerdì 4 aprile 2014 - Esercitazioni 9-10*
   * Funzioni ricorsive. L'esempio di fibonacci: inefficienza della versione ricorsiva. 
   * Fibonacci iterativo e versione ricorsiva che mima il programma iterativo: trasformazione sistematica di un'iterazione in ricorsione.
   * Dimostrazioni per induzione di correttezza di programmi ricorsivi. Il ruolo delle precondizioni.
   * Esercizio sui vettori: baricentro.  
</font>

<font color=#FF6600> 
*Lezioni 19-20: lunedì 7 aprile 2014*
   * Il problema dell'ordinamento (4)
      * algoritmi lineari: counting sort e bucket sort; dettagli nel caso in cui vi siano dati satellite
   * Svolgimento di alcuni esercizi
 </font>

<font color=#336699>
*Esercizi assegnati:*
   * Dato un vettore di n elementi, tutti compresi tra 0 e k, con k=O(n), verificare se contiene occorrenze ripetute dello stesso elemento (di nuovo: ma questa volta il costo computazionale dovrebbe essere un O(n))
 </font>

<font color=#FF6600> 
*Lezioni 21-22: giovedì 10 aprile 2014*
   * Strutture dati fondamentali (1)
      * strutture dati ed insiemi dinamici
      * confronto tra vettore qualunque e vettore ordinato
      * liste, liste doppiamente puntate e liste circolari
 </font>

<font color=#33CC00> 
*Giovedì 10 aprile 2014 - Tutoraggio 5*
   * Esercizi sulla ricorsione.    
</font>

<font color=#660099> 
*Venerdì 11 aprile 2014 - Esercitazioni 11-12*
   * L'allocazione dinamica della memoria: =malloc= e =calloc=. 
   * Vettori statici, vettori allocati dinamicamente e vettori con numero variabile di elementi. 
   * Esercizio: partizioni. Stampa delle partizioni cominciando dal programma che le conta.
   * Coefficienti binomiali: versione ricorsiva, versione iterativa con generazione delle righe del triangolo di tartaglia usando un solo vettore. 
</font>

<font color=#FF6600> 
*Lezioni 23-24: lunedì 14 aprile 2014*
   * Esercizi di preparazione all'esonero
 </font>

<font color=red> 
*Interruzione della didattica per le festività pasquali e per le prove in itinere*
 </font>

<font color=#FF6600> 
*Lezioni 25-26: lunedì 5 maggio 2014*
   * Correzione degli esercizi di esonero
   * Strutture dati fondamentali (2)
      * la struttura dati coda
      * le operazioni enqueue e dequeue
      * code con priorità
      * pila
      * le operazioni Push e Pop
      * Esercizio: simulazione di una coda tramite due pile
</font>
<font color=#336699>
*Esercizi assegnati:*
   * scrivere sia lo pseudocodice che il codice C delle funzioni Enqueue e Dequeue quando la coda sia circolare ed implementata su vettore
   * scrivere sia lo pseudocodice che il codice C delle funzioni Pop, Push e Pila_Piena quando la pila sia implementata su vettore
 </font>

<font color=#FF6600> 
*Lezioni 27-28: giovedì 8 maggio 2014*
   * Strutture dati fondamentali (3)
      * alberi (1)
         * definizione tramite la nozione di grafo
         * caratterizzazione degli alberi
         * alberi binari completi: relazione tra altezza e numero di nodi
         * memorizzazione degli alberi:
            * tramite record e puntatori
            * posizionale
            * tramite vettore dei padri
</font>
<font color=#336699>
*Esercizi assegnati:*
   * dato un albero tramite vettore dei padri, restituirlo in output tramite notazione posizionale. Calcolare il costo computazionale
   * dato un albero tramite notazione posizionale, restituirlo in output tramite vettore dei padri. Calcolare il costo computazionale
 </font>

<font color=#660099> 
*Venerdì 9 maggio 2014 - Esercitazioni 13-14*
   * Osservazioni sugli errori dell'esonero (esercizio 2). Funzione =maxPrimoRec=. Cenni alla soluzione iterativa. 
   * Introduzione ai vettori bidimensionali, con allocazione statica (e relativi problemi nel passaggio di parametri) e dinamica. 
   * Programmazione per <i>raffinamenti successivi</i>: il gioco del Forza Quattro.
</font>

<font color=#FF6600> 
*Lezioni 29-30: lunedì 12 maggio 2014*
   * Strutture dati fondamentali (4)
      * alberi (2)
         * visite di alberi: in-ordine, pre-ordine e post-ordine
            * pseudocodice ricorsivo
            * costo computazionale tramite equazione di ricorrenza
            * esercizi che si risolvono utilizzando le visite
</font>
*Esercizi assegnati:*
   * dato un albero delle espressioni, stampare l'espressione corrispondente opportunamente parentesizzata
 </font>

<font color=#FF6600> 
*Lezioni 31-32: giovedì 15 maggio 2014*
   * Dizionari (1)
      * tabelle ad indirizzamento diretto
      * tabelle hash
         * ipotesi di uniformità semplice e fattore di carico
         * soluzione delle collisioni tramite liste di trabocco
         * soluzione delle collisioni tramite indirizzamento aperto
         * dimostrazioni del numero medio di accessi alla struttura in alcuni casi
</font>

<font color=#FF6600> 
*Lezioni 33-34: venerdì 16 maggio 2014*
   * Dizionari (2)
      * Alberi binari di ricerca (ABR):
         * algoritmo di ricerca
         * algoritmo per il massimo e minimo
         * algoritmo per il successore e predecessore
         * algoritmo di inserimento
         * algoritmo di cancellazione
         * osservazioni sul costo computazionale delle operazioni viste come funzione dell'altezza
</font>
<font color=#336699>
*Esercizi assegnati:*
   * dati due ABR T1 e T2 con n1 ed n2 nodi, e di altezza h1 ed h2, progettare un algoritmo che dia in output un unico ABR contenente tutte le n1+n2 chiavi (che si possono supporre tutte distinte), e si facciano le opportune osservazioni sull'altezza dell'albero risultante.
 </font>

<font color=#FF6600> 
*Lezioni 35-36: lunedì 19 maggio 2014*
   * Dizionari (3)
      * Alberi Red and Black
      * teorema sull'altezza
      * rotazioni
      * algoritmo di inserimento
</font>
<font color=#336699>
*Esercizi assegnati:*
   * disegnare tutti gli ABR che si creano inserendo via via le chiavi 41, 38, 31, 12, 19, 8
   * disegnare tutti gli Alberi Red and Black che si creano inserendo via via le chiavi 41, 38, 31, 12, 19, 8
 </font>

<font color=#660099> 
*Giovedì 22 maggio 2014 - Esercitazioni 15-16*
   * Introduzione alle strutture dinamiche: liste. Costruttore di tipo =struct=.
   * Definizione induttiva delle liste e loro implementazione in linguaggio C come liste concatenate di nodi.
   * Definizione del tipo =lista= con =typedef= e come puntatore al nodo in testa alla lista. 
   * Funzioni base per manipolare liste: costruttori (=add= e =makeEmptyList=) e distruttori (=isEmpty=).
</font>

<font color=#660099> 
*Venerdì 23 maggio 2014 - Esercitazioni 17-18*
   * Specifica astratta induttiva di funzioni su liste o sequenze con equazioni ricorsive.
   * Funzione =append=: versioni funzionali (con creazione di nuove liste) e versioni in-place (che modificano le liste in ingresso).
   * Confronto tra gli approcci in-place e funzionali. 
   * Funzione =reverseFun=. Versione quadratica. Versione iterativa e versione efficiente ricorsiva.
   * Completamento dell'esercizio del Forza Quattro.
 </font>

<font color=#FF6600> 
*Lezioni 37-38: lunedì 26 maggio 2014*
   * Grafi (1)
      * Definizioni e semplici proprietà
      * Rappresentazione in memoria di grafi:
         * liste di adiacenza
         * matrice di adiacenza
         * matrice di incidenza
         * lista di archi
         * confronto tra rappresentazioni
      * Visite di grafi
      * Alberi di visita
</font>
<font color=#336699>
*Esercizi assegnati:*
   * Dato G memorizzato con una struttura dati X, dare in output G memorizzato con un'altra struttura dati Y, dove X ed Y variano in tutti i modi possibili tra le 4 rappresentazioni viste
 </font>

<font color=#FF6600> 
*Lezioni 39-40: giovedì 29 maggio 2014*
   * Grafi (2)
      * Visita in ampiezza: pseudocodice, costo computazionale in funzione della struttura dati usata, proprietà dell'albero di visita in ampiezza
      * Visita in profondità: pseudocodice, costo computazionale in funzione della struttura dati usata, proprietà dell'albero di visita in profondità

      * Alberi di visita
</font>
<font color=#336699>
*Esercizi assegnati:*
   * Modificare lo pseudocodice della visita in ampiezza in modo che restituisca la lunghezza dei cammini minimi da un fissato nodo v a tutti gli altri nodi.
   * Dato un grafo G mediante le sue liste di adiacenza, progettare un algoritmo che dica se G è aciclico oppure no.
   * Dato un grafo G mediante le sue liste di adiacenza, progettare un algoritmo che restituisca il numero delle componenti connesse di G.
</font>

<font color=#FF6600> 
*Lezioni 41-42: giovedì 5 giugno 2014*
   * Grafi (3)
      * esercizi sui grafi
         * lunghezze dei cammini più corti da un nodo con G memorizzato tramite liste di adiacenza
         * complemento  e quadrato di un grafo G, quando esso sia memorizzato tramite liste di adiacenza o tramite matrice di incidenza; confornto delle complessità
         * calcolo del numero delle componenti connesse di un grafo e sua complessità
</font>

<font color=#FF6600>
*Lezioni 43-44: lunedì 9 giugno 2014*
   *Grafi (4)
      * grafi euleriani
         * definizione
         * teorema di Eulero
      * grafi bipartiti ed accoppiamenti
         * definizioni
         * caratterizzazione di grafi bipartiti
         * esercizi: come modificare gli algoritmi di visita per determinare se un grafo e' bipartito e per trovare un accoppiamento massimale
         * teorema di Hall per la caratterizzazione di accoppiamenti completi in grafi bipartiti
</font>

<font color=#FF6600>
*Lezioni 45-46: giovedì 12 giugno 2014*
   *Grafi (5)
      * grafi planari
         * definizioni
         * teorema di Eulero
         * 2 grafi non planari
      * Colorazione di un grafo
         * teorema per una colorazione massimale
         * enunciato del teorema dei 4 colori
         * un'applicazione del problema della colorazione
 </font>






---+++ <font color=990000 size="+1"> A.A. 2012/2013</font>
<font color=blue> 
*Lezioni 1-2: Lunedì 4 marzo 2013*

Introduzione
   * Concetti di algoritmo, di struttura dati, di efficienza; di complessita' computazionale;
   * modello RAM; misura di costo uniforme e logaritmico.
</font>

<font color=blue> 
*Lezioni 3-4: giovedì 7 marzo 2013*

Notazione asintotica (1)
   * Definizione e significato degli insiemi O, &Omega; e &Theta;.
   * Algebra della notazione asintotica
   * Esempi
   * Valutazione della complessità computazionale di un algoritmo
</font>
<font color=green>
*Esercizi assegnati:*
   * Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione
   * Calcolare l'andamento asintotico di alcune funzioni
 </font>

<font color=#342826> 
*Esercitazioni 1-2: venerdì 8 marzo 2013*

Introduzione alla nozione di problema, esecutore, soluzione a una classe di problemi.<br>
Procedure risolutive per problemi elementari.<br>
Struttura di un programma C: variabili, tipi, dichiarazioni.<br>
Assegnazione, comandi condizionali ed iterativi.<br>
Codifica in C di alcune procedure elementari: somma di due numeri, predecessore. 
</font>

<font color=#41383C>
*Esercizi e ulteriori approfondimenti:*
   * vedi dispense Parte 1 e Parte 2 (Sez. 1-2).<br> 
 </font>

<font color=#342826> 
*Esercitazioni 3-4: lunedì 11 marzo 2013*

Le funzioni. Parametri, variabili locali e globali. <br> 
Regole di Scoping delle variabili. <br>
Introduzione alle asserzioni logiche. Nozione di precondizione, postcondizione, invariante.
</font>

<font color=#41383C>
*Esercizi e ulteriori approfondimenti:*
   * vedi dispense Parte 2 (Sez. 3-4).<br> 
 </font>

<font color=blue> 
*Lezioni 5-6: giovedì 14 marzo 2013*

Notazione asintotica (2)
   * esempi di semplici problemi e loro soluzione in modo più o meno efficiente.

Il problema della ricerca
   * ricerca sequenziale
      * pseudocodice
      * complessità nel caso migliore, peggiore e medio
   * ricerca binaria
      * pseudocodice
      * complessità nel caso migliore e peggiore (caso medio facoltativo)
</font>

<font color=red> 
*Tutoraggio 1-2: giovedì 14 marzo 2013*

   * Saper compilare un programma, uso di gcc.
   * Problemi semplici con impiego di cicli while e for, uso di if, dispensa di C "Introduzione al linguaggio C".
   * Chiamata di funzioni.
</font>

<font color=blue> 
*Lezioni 7-8: venerdì 15 marzo 2013*

Ricorsione
   * funzioni matematiche ricorsive
   * algoritmi ricorsivi
      * fattoriale
      * ricerca sequenziale
      * ricerca binaria
      * numeri di Fibonacci
</font>
<font color=green>
*Esercizi assegnati:*
   * Progettare degli algoritmi ricorsivi ed esprimerli tramite pseudocodice che risolvano i seguenti problemi:
      * dato in input un vettore, visualizzare i suoi valori al contrario (dall'ultimo al primo)
      * calcolare la somma di n numeri reali inseriti da tastiera (uno per ogni chiamata ricorsiva)
      * calcolare il MCD tra due interi positivi x ed y come segue:
         * sia y<x
         * se y=0 allora MCD(x,y)=y
         * altrimenti MCD(x,y))MCD(y, x%y)
   * Progettare degli algoritmi sia nella loro versione ricorsiva che iterativa, ed esprimerli tramite pseudocodice, che risolvano i seguenti problemi:
      * dati due interi n e k, calcolare la potenza k-esima di n
      * sommare gli n elementi di un vettore di interi
      * verificare se un vettore dato è palindromo
      * trovare il minimo di un vettore dato 
</font>

<font color=#342826> 
*Esercitazioni 5-6: lunedì 18 marzo 2013*

Puntatori in C.</font>
Utilizzo dei puntatori per passaggi di parametro per indirizzo.<br>
Funzione scambia senza variabile di appoggio: il problema di alias e side-effects.<br>
</font>
<font color=#41383C>
*Esercizi e ulteriori approfondimenti:*
   * vedi dispense Parte 3.<br> 
 </font>

<font color=blue> 
*Lezioni 9-10: giovedì 21 marzo 2013*
Soluzioni delle equazioni di ricorrenza (1)

   * metodo di sostituzione
   * metodo iterativo
   * metodo dell'albero
   * esempi di soluzione di equazioni di ricorrenza tramite i tre metodi
</font>
<font color=green>
*Esercizi assegnati:*
   * Calcolare la soluzione delle seguenti equazioni di ricorrenza con quanti più metodi è possibile, tenendo conto che per tutte il caso base è T(1)=&Theta(1):
      * T(n)=2T(n/2)+&Theta(n)
      * T(n)=3T(n/3)+&Theta(n)
      * T(n)=3T(n/4)+&Theta(n)
      * T(n)=2T(n/2)+&Theta(n^2)
      * T(n)=T(n/3)+T(2/3n)+&Theta(n)
      * T(n)=4T(n/2)+&Theta(n)
</font>

<font color=red> 
*Tutoraggio 3-4: giovedì 21 marzo 2013*

   * Puntatori, operatori & e *.
   * Problemi nell'uso di puntatori, side effect e alias.
   * Passaggio di parametri per valore e per indirizzo.
   * Problemi proposti nella dispensa "Parli del diavolo...e spuntano i puntatori!"
</font>

<font color=#342826> 
*Esercitazioni 7-8: venerdì 22 marzo 2013*

Ancora sui parametri passati per indirizzo: funzione div.<br>
Suo utilizzo nella funzione mdcDella Maestra.<br>
Funzioni Ricorsive: somma, fibonacci.<br>
Trasformazione di un ciclo while in funzioni ricorsive. <br>
</font>

<font color=#41383C>
*Esercizi e ulteriori approfondimenti:*
   * vedi dispense Parte 4 (Sez. 1-2).<br> 
 </font>

<font color=blue> 
*Lezioni 11-12: Lunedi' 25 marzo 2013*

Soluzioni delle equazioni di ricorrenza (2)

   * teorema principale (enunciato e dimostrazione per potenze esatte)
   * esempi di soluzione di equazioni di ricorrenza tramite teorema principale
</font>
<font color=green>
*Esercizi assegnati:*
   * Calcolare la soluzione delle seguenti equazioni di ricorrenza con il metodo principale ove possibile, e con un altro metodo altrimenti, tenendo conto che per tutte il caso base è T(1)=&Theta(1):
      * T(n)=2T(n/2)+&Theta(n^3)
      * T(n)=16T(n/4)+&Theta(n^2)
      * T(n)=T(n-1)+&Theta(n)
      * T(n)=3T(n/2)+&Theta(n log n)
      * T(n)=4T(n/2)+&Theta(n)
      * T(n)=4T(n/2)+&Theta(n^3)
</font>

<font color=red> 
*VACANZE DI PASQUA*
</font>

<font color=blue> 
*Lezioni 13-14: giovedì 4 aprile 2013*
   * Il problema dell'ordinamento (1)
      * algoritmi semplici: insertion sort, selection sort e bubble sort, pseudocodici e complessità nel caso migliore e peggiore
      * albero delle decisioni e teorema sulla limitazione inferiore per la complessità di un algoritmo per confronti
 </font>

<font color=green>
*Esercizi assegnati:*
   * tradurre in C tutti gli pseudocodici fatti a lezione
   * scrivere una funzione che, dato un vettore A di n elementi ed un indice j, trovi il minimo del sottovettore A[j..n] e lo metta in prima posizione (corrispondente all'indice j). Riscrivere il codice del selection sort in modo che chiami ripetutamente questa funzione
   * scrivere lo pseudocodice di una funzione che determini se una sequenza arbitraria di n numeri contiene occorrenze ripetute dello stesso numero. Valutare la complessità
 </font>

<font color=red> 
*Tutoraggio 5-6: giovedì 4 aprile 2013*

   * Ricorsione, problemi ricorsivi presi dalla dispensa "iterare è umano, ricorrere è divino" .
</font>

<font color=blue> 
*Lezioni 15-16: venerdì 5 aprile 2013*
   * Il problema dell'ordinamento (2)
      * algoritmi efficienti: paradigma del divide et impera e merge sort (pseudocodice e complessità)
 </font>

<font color=green>
*Esercizi assegnati:*
   * (già assegnato, ma...) scrivere lo pseudocodice di una funzione che determini se una sequenza arbitraria di n numeri contiene occorrenze ripetute dello stesso numero. Valutare la complessità, che dovrebbe essere &Theta;(n log n).
   * scrivere lo pseudocodice *ricorsivo* della funzione di fusione e valutarne la complessità, che dovrebbe comunque essere &Theta(n), tramite equazione di ricorrenza
   * Risolvere l'equazione di ricorrenza del Merge sort con tutti i metodi studiati
   * Rappresentare l'albero delle decisioni della funzione di fusione su a1 a2 e b1 b2 con le ipotesi che a1 < a2 e b1 < b2.
 </font>

<font color=#342826> 
*Esercitazioni 9-10: lunedì 8 aprile 2013*

Discussione Homework.<br>
Introduzione ai vettori in C. Relazione tra puntatori e vettori.<br>
Primi programmi sui vettori: stampa e minimo di un vettore.<br>
Esercitazione: il problema del baricentro.<br>
</font>

<font color=#41383C>
*Esercizi e ulteriori approfondimenti:*
   * vedi dispense Parte 6 (Sez. 1-2) e Correzione Primo Esonero.<br> 
 </font>

<font color=blue> 
*Lezioni 17-18: giovedì 11 aprile 2013*
   * Il problema dell'ordinamento (3)
      * algoritmi efficienti: quicksort (pseudocodice e complessità nei casi migliore, peggiore e medio)
 </font>

<font color=green>
*Esercizi assegnati:*
   * Risolvere l'equazione di ricorrenza del Qicksort con tutti i metodi consociuti.
   * Determinare la complessità del Quicksort se il vettore dato in input contiene n elementi uguali e se è già ordinato in senso decrescente.
 </font>

<font color=red> 
*Tutoraggio 7-8: giovedì 11 aprile 2013*

   * Vettori, dichiarazione di vettori e loro caratteristiche.
   * esercizi presi dalla dispensa "tipi di dato I: i vettori in linguaggio C".
</font>

<font color=blue> 
*Lezioni 19-20: venerdì 12 aprile 2013*
   * Il problema dell'ordinamento (4)
      * algoritmi efficienti: heapsort (struttura dati heap, pseudocodice e complessità)
 </font>

<font color=green>
*Esercizi assegnati:*
   * Scrivere lo pseudocodice di Heapsort nel caso in cui, come struttura dati, si usi un heap minimo (cioè tale che A[i]>=A[parent(i)]), che mantiene il minimo nella radice.
   * Scrivere lo pseudocodice di una funzione che, dato un heap, ritorni l'elemento con chiave minima. Valutare la complessità.
 </font>

<font color=#342826> 
*Esercitazioni 11-12: lunedì 15 aprile 2013*

Esercizi su ricorsione e vettori.<br>
Il problema del conteggio delle partizioni di un numero.<br>
Stampa di tutte le partizioni di un numero (usando un vettore per memorizzarle).<br>
Calcolo dei coefficienti binomiali: programma ingenuo, ricorsivo e con generazione delle righe del triangolo di Tartaglia.<br>
Funzione merge in C: versione iterativa e ricorsiva. <br>

<font color=#41383C>
*Esercizi e ulteriori approfondimenti:*
   * vedi dispense Parte 6 (Sez. 2) e Correzione Homework 2012 (partizioni) e Esercizi di Stile (merge).<br> 
 </font>

<font color=blue> 
*Lezioni 21-22: giovedì 18 aprile 2013*
   * Il problema dell'ordinamento (5)
      * algoritmi lineari: counting sort (pseudocodice, complessità, problematica dei dati satellite e stabilità)
   * Esercizi in preparazione dell'esonero
 </font>

<font color=green>
*Esercizi assegnati:*
   * Scrivere lo pseudocodice di una funzione che determini se una data una sequenza arbitraria di n numeri compresi tar 1 e k, con k=O(n), contiene occorrenze ripetute dello stesso numero. Valutare la complessità, che dovrebbe essere O(n).
 </font>

<font color=red> 
*Tutoraggio 9-10: giovedì 18 aprile 2013*

   * Esercizi e domande in preparazione dell'esonero
</font>

<font color=blue> 
*Lezioni 23-24: venerdì 19 aprile 2013*
   * Esercizi in preparazione dell'esonero
 </font>

<font color=red>
*Settimana di interruzione della didattica e primo esonero*
</font>

<font color=#342826> 
*Esercitazioni 13-14: lunedì 29 aprile 2013*

Introduzione alle stringhe. <br>
Correzione esercizio esonero. <br>
Introduzione agli array bidimensionali: il problema del Forza4. <br>
Metodologia Top-Down o per Raffinamenti Successivi. <br>
</font>

<font color=#41383C>
*Esercizi e ulteriori approfondimenti:*
   * vedi dispense Parte 7.<br> 
 </font>

<font color=blue>
*Lezioni 25-26: giovedì 2 maggio 2013*

   * Correzione esonero
   * Strutture dati fondamentali (1)
      * insiemi dinamici ed operazioni su di essi
      * implementazione di un insieme dinamico su un vettore non ordinato
      * implementazione di un insieme dinamico su un vettore ordinato
      * la struttura dati lista
      * operazioni elementari su liste: scorrimento, ricerca, inserimento in testa
</font>

<font color=red>
*Tutoraggio 11-12: giovedì 2 maggio 2013*

   * Esercizi sulle stringhe di caratteri, uso del carattere '\0'
</font>

<font color=blue>
*Lezioni 27-28: venerdì 3 maggio 2013*

   * Strutture dati fondamentali (2)
      * operazioni elementari su liste: cancellazione, predecessore/successore e minimo/massimo
      * cancellazione logica e cancellazione fisica
      * lista doppiamente puntata
      * la struttura dati coda
      * le operazioni enqueue e dequeue
      * code con priorità
      * pila
 
</font>
<font color=green>
*Esercizi assegnati:*
   * produrre lo pseudocodice della ricerca del predecessore (successore) su lista semplice
   * produrre lo pseudocodice di una funzione che, dato un puntatore che indica la testa di una lista con chiavi intere, la scomponga in due liste, una contenente gli elementi con chiave pari e una contenente gli elementi con chiave dispari
   * scrivere sia lo pseudocodice che il codice C delle funzioni Enqueue e Dequeue quando la coda sia circolare ed implementata su vettore
   * scrivere sia lo pseudocodice che il codice C delle funzioni Pop, Push e Pila_Piena quando la pila sia implementata su vettore
   * simulare una coda tramite due pile; in particolare, scrivere lo pseudocodice delle funzioni Enqueue e Dequeue sapendo che si possono usare le funzioni seguenti: Push(x,i), Pop(i), Test_di_Pila_Vuota(i), dove i indica su quale pila siano eseguite le operazioni
 </font>

<font color=#342826> 
*Esercitazioni 15-16: lunedì 6 maggio 2013*

Memoria allocata dinamicamente. Calloc e Malloc. <br>
Introduzione al tipo di dato lista: definizione induttiva del tipo di dato sequenza. <br>
Strutture in Linguaggio C. <br>
Rappresentazione in C del tipo di dato sequenza. Funzioni addH e addT. <br>
</font>

<font color=#41383C>
*Esercizi e ulteriori approfondimenti:*
   * vedi dispense Parte 8.<br> 
 </font>

<font color=#342826> 
*Esercitazioni 17-18: giovedì 9 maggio 2013*

Esercizi sulle matrici: verifica della vittoria nel forza 4. <br>
Scorrimento delle righe, colonne e diagonali di una matrice. <br>
Di nuovo sulle liste: rimozione di elementi e liberazione della memoria (istruzione free()). <br>
</font>

<font color=#41383C>
*Esercizi e ulteriori approfondimenti:*
   * vedi dispense Parte 7 e 8.<br> 
 </font>

<font color=red> 
*Esercitazioni 13-14: giovedì 9 maggio 2013*

   * Utilizzo di matrici di caratteri, utilizzo di input numerici passati in formato 'char'
</font>

<font color=blue>
*Lezioni 29-30: venerdì 10 maggio 2013*

   * Correzione dell'esercizio sulla simulazione della coda tramite le due pile
   * Strutture dati fondamentali (3)
     * alberi
         * definizione come grafo connesso e aciclico
         * teorema di caratterizzazione degli alberi 
      * alberi radicati, alberi ordinati ed alberi binari
      * limitazioni sul numero di nodi, numero di foglie ed altezza negli alberi binari
      * memorizzazione di alberi
         * rappresentazione posizionale
         * memorizzazione tramite record e puntatori
         * vettore dei padri
         * raffronto delle strutture in termini di spazio e di complessità delle operazioni di ricerca del padre di un nodo e di calcolo del numero dei figli di un nodo
</font>
<font color=green>
*Esercizi assegnati:*
   * scrivere lo pseudocodice di una funzione che prenda in input un albero memorizzato tramite vettore dei padri e restituisca in output lo stesso albero memorizzato con la notazione posizionale
 </font>

<font color=#342826> 
*Esercitazioni 19-20: lunedì 13 maggio 2013*

Esercizi sulle liste: reverse e reverse efficiente con creazione di una nuova lista.<br>
reverse con spostamento dei puntatori ricorsiva ed iterativa.<br> 
Esercizi dei compiti dello scorso anno: sommaSuccessivi e sommaPrecedenti. 
</font>

<font color=#41383C>
*Esercizi e ulteriori approfondimenti:*
   * vedi dispense Parte 8 e Correzione Secondo Esonero.<br> 
 </font>

<font color=blue>
*Lezioni 31-32: giovedì 16 maggio 2013*

   * Strutture dati fondamentali (4)
      * visita di alberi: pre-ordine, in-ordine e post-ordine 
      * complessità della visita (versione ricorsiva) tramite caso migliore e caso peggiore
      * applicazioni delle visite: calcolo del numero dei nodi e dell'altezza di un albero dato tramite memorizzazione record e puntatori, visita di un albero memorizzato tramite vettore dei padri e sua complessità
</font>
<font color=green>
*Esercizi assegnati:*
   * scrivere lo pseudocodice di una funzione che prenda in input un albero memorizzato tramite vettore dei padri e restituisca in output lo stesso albero memorizzato tramite record e puntatori
   * scrivere lo pseudocodice di una funzione che esegua una visita di un albero memorizzato tramite record e puntatori in modo iterativo
   * scrivere una funzione che prenda in input un albero memorizzato tramite record e puntatori ed un livello i, e restituisca il numero dei nodi dell'albero che si trovano a livello i. Indicato con nj il numero di nodi a livello j, la complessità non dovrebbe superare la somma, per j che va da 0 ad i, di nj. 
   * scrivere una funzione che visiti un albero memorizzato tramite notazione posizionale. Valutare la complessità.
 </font>

<font color=blue>
*Lezioni 33-34: venerdì 17 maggio 2013*

Dizionari (1)
   * definizione di dizionario e problematiche associate
   * tabelle ad indirizzamento diretto
   * tabelle hash
   * cenno al problema delle collisioni
   * soluzione al problema delle collisioni tramite liste di trabocco
   * soluzione al problema delle collisioni tramite indirizzamento aperto
      * scansione lineare
      * scansione quadratica
      * hashing doppio
   * definizione di albero binario di ricerca
</font>

<font color=#342826> 
*Esercitazioni 21-22: lunedì 20 maggio 2013*

Specifica di funzioni su liste mediante equazioni ricorsive su sequenze.<br>
Introduzione agli alberi e loro rappresentazione in linguaggio C.<br>
Bilanciamento: funzioni inefficienti.<br>

<font color=#41383C>
*Esercizi e ulteriori approfondimenti:*
   * vedi dispense Parte 8 e 10.<br> 
 </font>

<font color=blue> 
*Lezioni 35-36: giovedì 23 maggio 2013*
Dizionari (2)

   * alberi binari di ricerca
      * algoritmo di ricerca e sua complessita'
      * algoritmi di ricerca del massimo, minimo, successore e predecessore e loro complessità
      * algoritmo di inserimento e sua complessità
      * algoritmo di cancellazione e sua complessità
   * la problematica del bilanciamento per la limitazione della complessità: definizione di RB-albero e dimostrazione che ha altezza logaritmica
</font>
<font color=green> 
*Esercizi assegnati:*
   * Siano dati due alberi binari di ricerca T1 e T2, rispettivamente con n1 ed n2 nodi, e di altezza h1 ed h2. Si abbia l'ipotesi che tutte le chiavi contenute in T1 siano minori di tutte le chiavi contenute in T2.
Progettare un algoritmo efficiente che memorizzi tutte le n1+n2 chiavi in un unico albero binario di ricerca. Se ne calcoli la complessità nel caso peggiore e si facciano le opportune considerazioni sull'altezza dell'albero risultante, come funzione di h1 ed h2.
</font>

<font color=blue>
*Lezioni 37-38: Venerdì 24 maggio 2013*

Grafi (1)

   *alcune proprietà dei grafi (somma dei gradi, regola della stretta di mano)
   * rappresentazioni in memoria
      * liste di adiacenza
      * matrice di adiacenza
      * matrice di incidenza
      * lista di archi
      * confronto della complessita' spaziale e temporale in alcune operazioni elementari (calcolo del grado, ricerca di un arco)
   * il concetto di vista generica e cenno alla visita in ampiezza ed a quella in profondità
</font>

<font color=green>
*Esercizi assegnati:*
   * Dato G tramite liste di adiacenza, costruire la sua matrice di adiacenza e la sua matrice di incidenza. Calcolare la complessità.
   * Dato G tramite matrice di adiacenza, costruire le sue liste di adiacenza. Calcolare la complessità.
   * Dato G tramite matrice di incidnza, costruire la sua matrice di adiacenza e le sue liste di adiacenza. Calcolare la complessità.
</font>

<font color=blue>
*Lezioni 39-40: Lunedì 27 maggio 2013*

Grafi (2)

   * alberi ricoprenti di visita
   * visita in ampiezza
      * pseudocodice quando G è dato tramite liste di adiacenza
      * pseudocodice quando G è dato tramite matrice di incidenza
      * complessità nei due casi
      * proprietà dell'albero ricoprente della visita in ampiezza
   * visita in profondità
      * pseudocodice quando G è dato tramite liste di adiacenza
      * complessità
      * proprietà dell'albero ricoprente della visita in profondità
</font>

<font color=green>
*Esercizi assegnati:*
   * Dimostrare che la relazione "u e v sono nella stessa componente o u=v" è di equivalenza.
   * Modificare lo pseudocodice della visita in ampiezza in modo tale che restituisca tutte le lunghezze dei cammini più corti da un nodo dato a tutti gli altri nodi.
   * Dato un grafo G tramite liste di adiacenza, progettare un algoritmo che dica se G è aciclico oppure no. Calcolare la complessità.
</font>

<font color=#342826> 
*Esercitazioni 23-24: giovedì 30 maggio 2013*

Discussione esercizi Homework 4.<br>
Esercizi sugli alberi: bilanciamento in profondità e nel numero dei nodi.<br>
Versioni efficienti con un'unica scansione dell'albero.<br>
Uso di parametri ausiliari e del valore tornato da una funzione per trasmettere informazioni durante le chiamate ricorsive in avanti o all'indietro.<br>
</font>

<font color=#41383C>
*Esercizi e ulteriori approfondimenti:*
   * vedi dispense Parte 10.<br> 
 </font>

<font color=blue>
*Lezioni 41-42: Venerdì 31 maggio 2013*

Grafi (3)

   * esercizi su grafi:
      * lunghezze dei cammini più corti da un nodo con G memorizzato tramite liste di adiacenza
      * complemento  e quadrato di un grafo G, quando esso sia memorizzato tramite liste di adiacenza o tramite matrice di incidenza; confornto delle complessità
      * calcolo del numero delle componenti connesse di un grafo e sua complessità
</font>


<font color=#342826> 
*Esercitazioni 25-26: lunedì 3 giugno 2013*

Esercizi su alberi e liste.<br>
Differenza tra due liste: creando una nuova lista, modificando le liste di partenza.<br>
Differenza tra due liste ordinate.<br>
Dato un albero, restituire una lista che contiene le foglie (frontiera). Versione efficiente senza append.<br>
Esempio di programma con backtrack: sudoku solver.<br>
</font>

<font color=#41383C>
*Esercizi e ulteriori approfondimenti:*
   * vedi dispense Parte 8 e 10.<br> 
 </font>

<font color=blue>
*Lezioni 43-44: Giovedì 6 giugno 2013*

Grafi (4)

   * grafi euleriani
      * definizioni
      * teorema di Eulero
   * grafi bipartiti ed accoppiamenti
      * definizioni
      * caratterizzazione di grafi bipartiti
      * esercizi: come modificare gli algoritmi di visita per determinare se un grafo e' bipartito e per trovare un accoppiamento massimale
      * teorema di Hall per la caratterizzazione di accoppiamenti completi in grafi bipartiti
</font>

<font color=blue>
*Lezioni 45-46: Venerdì 7 giugno 2013*

Grafi (5)

   * grafi planari
      * definizioni
      * teorema di Eulero
      * 2 grafi non planari
   * Colorazione di un grafo
      * teorema per una colorazione massimale
      * enunciato del teorema di Brooks
      * enunciato del teorema dei 4 colori
 </font>







---+++ <font color=990000 size="+1"> A.A. 2011/2012</font>
<font color=blue> 
*Lezioni 1-2: Lunedì 5 marzo 2012*

Introduzione
   * Concetti di algoritmo, di struttura dati, di efficienza; di complessita' computazionale;
   * modello RAM; misura di costo uniforme e logaritmico.
</font>

<font color=blue> 
*Lezioni 3-4: giovedì 8 marzo 2012*

Notazione asintotica
   * Definizione e significato degli insiemi O, &Omega; e &Theta;.
   * Algebra della notazione asintotica
   * Esempi
   * valutazione della complessità computazionale di un algoritmo
</font>
<font color=green>
*Esercizi assegnati:*
   * Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione
 </font>

<font color=#342826> 
*Esercitazioni 1-2: venerdì 9 marzo 2012*

Introduzione alla nozione di problema, esecutore, soluzione a una classe di problemi.<br>
Procedure risolutive per problemi elementari.
</font>

<font color=#41383C>
*Esercizi assegnati:*
   * vedi dispense collegate agli argomenti della lezione. (Parte 1, Sez. 1-2)<br> 
 </font>

<font color=blue> 
*Lezioni 5-6: lunedì 12 marzo 2012*

Il problema della ricerca
   * ricerca sequenziale
      * pseudocodice
      * complessità nel caso migliore, peggiore e medio
   * ricerca binaria
      * pseudocodice
      * complessità nel caso migliore, peggiore e medio
</font>

<font color=blue> 
*Lezioni 7-8: giovedì 15 marzo 2012*

Ricorsione
   * funzioni matematiche ricorsive
   * algoritmi ricorsivi
      * fattoriale
      * ricerca sequenziale
      * ricerca binaria
      * numeri di Fibonacci
</font>
<font color=green>
*Esercizi assegnati:*
   * Progettare degli algoritmi ricorsivi ed esprimerli tramite pseudocodice che risolvano i seguenti problemi:
      * dato in input un vettore, visualizzare i suoi valori al contrario (dall'ultimo al primo)
      * calcolare la somma di n numeri reali inseriti da tastiera (uno per ogni chiamata ricorsiva)
      * calcolare il MCD tra due interi positivi x ed y come segue:
         * sia y<x
         * se y=0 allora MCD(x,y)=y
         * altrimenti MCD(x,y))MCD(y, x%y)
   * Progettare degli algoritmi sia nella loro versione ricorsiva che iterativa, ed esprimerli tramite pseudocodice, che risolvano i seguenti problemi:
      * dati due interi n e k, calcolare la potenza k-esima di n
      * sommare gli n elementi di un vettore di interi
      * verificare se un vettore dato è palindromo
      * trovare il minimo di un vettore dato 
 </font>

<font color=#342826> 
*Esercitazioni 3-4: venerdì 16 marzo 2012*

Introduzione al linguaggio C: variabili, tipi, dichiarazioni.<br>
Assegnazione, comandi condizionali ed iterativi. Interdefinizione tra i vari comandi. <br>
Le funzioni. Parametri, variabili locali e globali. Regole di Scoping delle variabili. <br>
Codifica in C di semplici programmi.
</font>

<font color=#41383C>
*Esercizi assegnati:*
   * vedi dispense collegate agli argomenti della lezione. (Parte 1, Sez. 3)<br> 
 </font>

<font color=blue> 
*Lezioni 9-10: lunedì 19 marzo 2012*

Equazioni di ricorrenza (1)
   * metodo di sostituzione
   * metodo iterativo
   * metodo dell'albero
   * esempi di soluzione di equazioni di ricorrenza con i vari metodi

</font>
<font color=green>
*Esercizi assegnati:*
   * Risolvere le seguenti equazioni di ricorrenza:
      * T(n)=2 T(n/2)+&Theta;(n); T(1)=&Theta;(1)
      * T(n)=3 T(n/2)+&Theta;(n); T(1)=&Theta;(1)
 </font>

<font color=blue> 
*Lezioni 11-12: giovedì 22 marzo 2012*

Equazioni di ricorrenza (2)
   * metodo principale
      * esempio di utilizzo
      * dimostrazione per potenze esatte

</font>
<font color=green>
*Esercizi assegnati:*
   * Risolvere le seguenti equazioni di ricorrenza:
      * T(n)=2 T(n/2)+&Theta;(n^3); T(1)=&Theta;(1)
      * T(n)=16 T(n/4)+&Theta;(n^2); T(1)=&Theta;(1)
      * T(n)=T(n-1)+&Theta;(n); T(1)=&Theta;(1)
      * T(n)=3 T(n/2)+&Theta;(n log n); T(1)=&Theta;(1)
 </font>

<font color=red> 
*Tutoraggio 1-2: giovedì 22 marzo 2012*

Scrittura, compilazione ed esecuzione di un programma C.<br>
Risolvere esercizi dati durante le esercitazioni: somma e predecessore (usando solo +1).<br>
 </font>

<font color=#342826> 
*Esercitazioni 5-6: venerdì 23 marzo 2012*

Introduzione all'uso dei puntatori in C: significato, tipi puntatore, dichiarazione di una variabile pointer.<br>
Operatori sui puntatori: &, * e aritmetica dei puntatori.<br>
Puntatori e Passaggio dei parametri: funzione scambia.<br>
Fenomeni connessi ai puntatori: alias e side effects. Funzione scambia senza variabile di appoggio.<br>

Introduzione alla ricorsione. <br> 
Moltiplicazione Egiziana ricorsiva.<br>
</font>

<font color=#41383C>
*Esercizi assegnati:*
   * vedi dispense collegate agli argomenti della lezione. (Parte 2 e Parte 3, sezione 1)<br> 
 </font>

<font color=blue> 
*Lezioni 13-14: lunedì 26 marzo 2012*
   * Il problema dell'ordinamento (1)
      * algoritmi semplici: insertion sort, selection sort e bubble sort, pseudocodici e complessità nel caso migliore e peggiore
      * teorema sulla limitazione inferiore per la complessità di un algoritmo per confronti
 </font>

<font color=green>
*Esercizi assegnati:*
   * scrivere una funzione che, dato un vettore, trovi il minimo e lo metta in prima posizione. Riscrivere il codice del selection sort in modo che chiami ripetutamente questa funzione
   * scrivere lo pseudocodice di una funzione che determini se una sequenza arbitraria di n numeri contiene occorrenze ripetute dello stesso numero. Valutare la complessità
   * dati n+1 coefficienti a_0, ..., a_n ed un reale y, scrivere lo pseudocodice di una funzione che calcoli il valore del polinomio a_0 + a_1x+ ... +a_n x^n nel punto y. Scrivere un'altra funzione che risolva lo stesso problema che sfrutti la regola di Horner: a_0+a_1x+ ... + a_n x^n=(...(a_n x + a_{n-1})x+ ... +a_1)x+a_0. Calcolare la complessità di entrambe le funzioni e fare le considerazioni del caso.
 </font>

<font color=blue> 
*Lezioni 15-16: giovedì 29 marzo 2012*
   * Il problema dell'ordinamento (2)
      * algoritmi efficienti: merge sort (pseudocodice e complessità)
 </font>

<font color=green>
*Esercizi assegnati:*
   * scrivere lo pseudocodice di una funzione che determini se una sequenza arbitraria di n numeri contiene occorrenze ripetute dello stesso numero. Valutare la complessità, che dovrebbe essere &Theta;(n log n).
   * Nonostante il merge sort funzioni in tempo &Theta;(n log n), l'insertion sort è più veloce del merge sort per valori piccoli di n. Quindi ha senso usare insertion sort dentro il merge sort quando i sottoproblemi diventano sufficientemente piccoli. Si consideri una modifica del merge sort in cui il caso base diviene una porzione del vettore di lunghezza k, con k che deve essere determinato, la quale viene ordinata usando insertion sort. Le porzioni ordinate vengono poi combinate usando il meccanismo standard di fusione. Determinare il massimo valore di k come funzione di n per cui l'algoritmo modificato ha lo stesso tempo di esecuzione asintotico del merge sort.
 </font>

<font color=red> 
*Tutoraggio 3-4: giovedì 29 marzo 2012*
 
Esercitazione sul passaggio dei parametri per riferimento e uso dei puntatori:<br>
Funzione divRef(int m, int n, int* q, int* r) che restituisce quoziente e resto 
della divisione intera sui parametri <br> e sua applicazione all'algoritmo del 
massimo comun divisore della maestra.
</font>

<font color=#342826> 
*Esercitazioni 7-8: venerdì 30 marzo 2012*

Ancora sulla ricorsione: Induzione e Ricorsione.<br>
Calcolo dei numeri di Fibonacci ricorsivo efficiente.<br>
Problemi inerentemente ricorsivi: determinare se un numero n è semiperfetto.<br>
</font>

<font color=#41383C>
*Esercizi assegnati:*
   * vedi dispense collegate agli argomenti della lezione (Parte 3, Ricorsione, sezioni 2,3).<br> 
 </font>

<font color=blue> 
*Lezioni 17-18: lunedì 1 aprile 2012*
   * Il problema dell'ordinamento (3)
      * algoritmi efficienti: quicksort (pseudocodice e complessità nei casi migliore, peggiore e medio)
 </font>

<font color=green>
*Esercizi assegnati:*
   * Determinare la complessità del Quicksort se il vettore dato in input contiene n elementi uguali e se è già ordinato in senso decrescente.
 </font>

<font color=cyan>
*Vacanze di Pasqua*
 </font>

<font color=#342826> 
*Esercitazioni 9-10: giovedì 12 aprile 2012*

Introduzione agli array in C.<br>
Vettori e puntatori.<br>
Semplici programmi su array e cenni alle asserzioni logiche per programmi su array.<br>
Esercizi di stile: funzione merge iterativa, ricorsiva e da vero programmatore C.<br>
</font>

<font color=#41383C>
*Esercizi assegnati:*
   * vedi dispense collegate agli argomenti della lezione (Parte 5, Vettori).<br> 
 </font>

<font color=red> 
*Tutoraggio 5-6: giovedì 12 aprile 2012*
 
Esercitazione sui vettori:<br>
1) Funzione che conta gli elementi comuni in due array ordinati.<br>
2) Crivello di Eratostene.<br>
</font>

<font color=blue> 
*Lezioni 19-20: venerdì 13 aprile 2012*
   * Il problema dell'ordinamento (4)
      * algoritmi efficienti: heapsort (struttura dati heap, pseudocodice e complessità)
 </font>

<font color=green>
*Esercizi assegnati:*
   * Scrivere lo pseudocodice di Heapsort nel caso in cui, come struttura dati, si usi un heap minimo (cioè tale che A[i]>=A[parent(i)]), che mantiene il minimo nella radice.
   * Scrivere lo pseudocodice di una funzione che, dato un heap, ritorni l'elemento con chiave minima. Valutare la complessità.
 </font>

<font color=blue> 
*Lezioni 21-22: lunedì 16 aprile 2012*
   * Il problema dell'ordinamento (5)
      * algoritmi lineari: counting sort (pseudocodice, complessità, problematica dei dati satellite e stabilità)
   * Esercizi in preparazione dell'esonero
 </font>

<font color=green>
*Esercizi assegnati:*
   * Scrivere lo pseudocodice di una funzione che determini se una data una sequenza arbitraria di n numeri compresi tar 1 e k, con k=O(n), contiene occorrenze ripetute dello stesso numero. Valutare la complessità, che dovrebbe essere O(n).
 </font>

<font color=blue> 
*Lezioni 23-24: giovedì 19 aprile 2012*
   * Esercizi in preparazione dell'esonero
 </font>

<font color=red> 
*Tutoraggio 7-8: giovedì 19 aprile 2012*
 
Esercitazione sui vettori 2:<br>
1) Funzione che verifica se due vettori contengono gli stessi elementi.<br>
1) Funzione che verifica se due vettori contengono gli stessi elementi con lo stesso numero di occorrenze.<br>
1) Funzione che verifica se due vettori contengono gli stessi elementi con lo stesso ordine, interpretando il vettore in modo circolare.<br>
</font>

<font color=#342826> 
*Esercitazioni 11-12: venerdì 20 aprile 2012*

Il problema degli anagrammi: progettazione della soluzione attraverso equazioni ricorsive.<br>
Codifica delle permutazioni di n elementi.<br> 
Esercizi sui vettori: <br>
1. Dire se un vettore è contenuto in un altro. Versione iterativa e ricorsiva.<br>
2. Trovare la sequenza non decrescente più lunga in un vettore.<br>
</font>

<font color=#41383C>
*Esercizi assegnati:*
   * vedi dispense collegate agli argomenti della lezione: Parte 4 (Strutture Dati e Codifiche) e Parte 5 (Vettori in C).<br> 
 </font>

<font color=cyan>
*Interruzione della didattica e primo esonero*
 </font>

<font color=blue>
*Lezioni 25-26: giovedì 3 maggio 2012*

Strutture dati fondamentali (1)

   * insiemi dinamici ed operazioni su di essi
   * implementazione di un insieme dinamico su un vettore non ordinato
   * implementazione di un insieme dinamico su un vettore ordinato
   * la struttura dati lista
   * operazioni elementari su liste: scorrimento, ricerca, inserimento in testa

</font>

<font color=#342826> 
*Esercitazioni 13-14: venerdì 4 maggio 2012*

Cose belle: una nuova versione della funzione scambia, basata sull'idea dell'assegnamento parallelo di Dijkstra.<br> 
Introduzione alle matrici. <br>
Esempio: verifica se un quadrato è magico.
</font>

<font color=blue>
*Lezioni 27-28: lunedì 7 maggio 2012*

Strutture dati fondamentali (2)
   * operazioni elementari su liste: cancellazione, predecessore/successore e minimo/massimo
   * cancellazione logica e cancellazione fisica
   * lista doppiamente puntata
   * la struttura dati coda
   * le operazioni enqueue e dequeue
</font>
<font color=green>
*Esercizi assegnati:*
   * produrre lo pseudocodice della ricerca del predecessore (successore) su lista semplice
   * produrre lo pseudocodice di una funzione che, dato un puntatore che indica la testa di una lista con chiavi intere, la scomponga in due liste, una contenente gli elementi con chiave pari e una contenente gli elementi con chiave dispari
   * scrivere sia lo pseudocodice che il codice C delle funzioni Enqueue e Dequeue quando la coda sia circolare ed implementata su vettore
 </font>

<font color=blue>
*Lezioni 29-30: giovedì 10 maggio 2012*

Strutture dati fondamentali (3)
   * code con priorità
   * pila
   * alberi
      * definizione come grafo connesso e aciclico
      * teorema di caratterizzazione degli alberi 
</font>
<font color=green>
*Esercizi assegnati:*
   * scrivere sia lo pseudocodice che il codice C delle funzioni Pop, Push e PilaPiena quando la pila sia implementata su vettore
 </font>

<font color=#342826> 
*Esercitazioni 15-16: venerdì 11 maggio 2012*

Esempio di programmazione per raffinamenti successivi (e problemi su matrici): il <b>Forza Quattro</b>.<br> 

<font color=#41383C>
*Esercizi assegnati:*
   * vedi dispense collegate agli argomenti della lezione: Parte 6 (Stringhe e Vettori Bidimensionali).<br> 

</font>

<font color=blue>
*Lezioni 31-32: lunedì 14 maggio 2012*

Strutture dati fondamentali (4)
   * alberi
      * alberi radicati, alberi ordinati ed alberi binari
      * limitazioni sul numero di nodi, numero di foglie ed altezza negli alberi binari
      * memorizzazione di alberi
         * rappresentazione posizionale
         * memorizzazione tramite record e puntatori
         * vettore dei padri
         * raffronto delle strutture in termini di spazio e di complessità delle operazioni di ricerca del padre di un nodo e di calcolo del numero dei figli di un nodo
      * visita di alberi: pre-ordine, in-ordine e post-ordine 
</font>
<font color=green>
*Esercizi assegnati:*
   * scrivere lo pseudocodice di una funzione che prenda in input un albero memorizzato tramite vettore dei padri e restituisca in output lo stesso albero memorizzato tramite record e puntatori
 </font>
 
<font color=#342826> 
*Esercitazioni 17-18: giovedì 17 maggio 2012*

Introduzione ai tipi di Dato in C.<br>
Struct e typedef. <br>.
Memoria allocata dinamicamente: malloc, calloc e free.<br>
Introduzione alle liste.<br>

<font color=#41383C>
*Esercizi assegnati:*
   * vedi dispense collegate agli argomenti della lezione: Parte 7 (Strutture Dati Dinamiche Lineari).<br> 

</font>

<font color=blue> 
*Lezioni 33-34: venerdì 18 maggio 2012*

Strutture dati fondamentali (5)
   * alberi
      * complessità della visita (versione ricorsiva) tramite caso migliore e caso peggiore
      * applicazioni delle visite: calcolo del numero dei nodi e dell'altezza di un albero dato tramite memorizzazione record e puntatori

Dizionari (1)
   * definizione di dizionario e problematiche associate
   * tabelle ad indirizzamento diretto
   * tabelle hash
   * cenno al problema delle collisioni
</font>
<font color=green>
*Esercizi assegnati:*
   * Scrivere lo pseudocodice di una funzione che prenda come parametri il puntatore alla radice di un albero (memorizzazione record e puntatori) ed un intero positivo i e restituisca in output il numero di nodi dell'albero che si trovano a distanza i dalla radice. La complessità dovrebbe essere dell'ordine del numero dei nodi a distanza minore o uguale ad i dalla radice.
   * Scrivere lo pseudocodice di una funzione che prenda come parametri il puntatore alla radice di un albero delle espressioni (memorizzazione record e puntatori) e stampi l'espressione correttamente parentesizzata
 </font>

<font color=blue> 
*Lezioni 35-36: lunedì 21 maggio 2012*

Dizionari (2)
   * soluzione al problema delle collisioni tramite liste di trabocco
   * soluzione al problema delle collisioni tramite indirizzamento aperto
      * scansione lineare
      * scansione quadratica
      * hashing doppio
      * analisi delle prestazioni nel caso medio
</font>

<font color=#342826> 
*Esercitazioni 19-20: giovedì 24 maggio 2012*

Programmazione su liste. Costruttori e Distruttori.<br>
Il problema della memoria: trattamento <i>funzionale</i> delle liste.<br>
Trattamento <i>in place</i> per side-effects.<br>
Tipici problemi su liste: append, reverse, remove. Versioni funzionali, ricorsive e iterative.<br>

<font color=#41383C>
*Esercizi assegnati:*
   * vedi dispense collegate agli argomenti della lezione: Parte 7 (Strutture Dinamiche Lineari).<br> 

</font>

<font color=blue> 
*Lezioni 37-38: venerdì 25 maggio 2012*
Dizionari (3)

   * alberi binari di ricerca
      * definizione
      * algoritmo di ricerca e sua complessita'
      * algoritmi di ricerca del massimo, minimo, successore e predecessore e loro complessita'
      * algoritmo di inserimento e sua complessita'
      * algoritmo di cancellazione e sua complessita'
   * la problematica del bilanciamento per la limitazione della complessita'
</font>
<font color=green> 
*Esercizi assegnati:*
   * Siano dati due alberi binari di ricerca T1 e T2, rispettivamente con n1 ed n2 nodi, e di altezza h1 ed h2. Si abbia l'ipotesi che tutte le chiavi contenute in T1 siano minori di tutte le chiavi contenute in T2.
Progettare un algoritmo efficiente che memorizzi tutte le n1+n2 chiavi in un unico albero binario di ricerca. Se ne calcoli la complessità nel caso peggiore e si facciano le opportune considerazioni sull'altezza dell'albero risultante, come funzione di h1 ed h2.
</font>

<font color=blue>
*Lezioni 39-40: Lunedi' 28 maggio 2012*

Grafi (1)

   * rappresentazioni in memoria
      * liste di adiacenza
      * matrice di adiacenza
      * matrice di incidenza
      * lista di archi
      * confronto della complessita' spaziale e temporale in alcune operazioni elementari
   * il concetto di vista generica e cenno alla visita in ampiezza ed a quella in profondità
</font>

<font color=#342826> 
*Esercitazioni 21-22: giovedì 31 maggio 2012*

Programmazione su Liste: discussione Homework 4.<br>
Ancora su reverse iterativa. <br>
Liste doppiamente concatenate. <br> 

<font color=#41383C>
*Esercizi assegnati:*
   * Cimentarsi con le versioni su liste degli algoritmi di ordinamento.<br>
   * Valutare la differenza tra quicksort su lista semplice e su lista doppiamente concatenata.<br> 
</font>

<font color=blue>
*Lezioni 41-42: Giovedi' 1 giugno 2012*

Grafi (2)

   * alberi ricoprenti di visita
   * visita in ampiezza
      * pseudocodice quando G è dato tramite liste di adiacenza
      * pseudocodice quando G è dato tramite matrice di incidenza
      * complessità nei due casi
      * proprietà dell'albero ricoprente della visita in ampiezza
   * visita in profondità
      * pseudocodice quando G è dato tramite liste di adiacenza
      * complessità
</font>

<font color=green>
*Esercizi assegnati:*
   * Dimostrare che la relazione "u e v sono nella stessa componente" è di equivalenza.<br>
</font>

<font color=#342826> 
*Esercitazioni 23-24: lunedì 5 giugno 2012*

Alberi Binari Generici.<br>
Cenni ai passaggi di funzioni come parametri. <br>
Funzioni profondità, numero nodi, specchio. <br> 

<font color=blue>
*Lezioni 43-44: Giovedi' 7 giugno 2012*

Grafi (3)

   * visita in profondità
      * proprietà dell'albero di visita in profondità
   * somiglianze tra visita in ampiezza e visita in profondità
   * complessità delle visite con le varie strutture dati
   * problema dei ponti di Konigsberg e grafi euleriani; caratterizzazione dei grafi euleriani
</font>

<font color=green>
*Esercizi assegnati:*
   * Dato un grafo G tramite liste di adiacenza, scrivere un algoritmo che costruisca la sua matrice di adiacenza e la sua matrice di incidenza. Calcolare la complessità.
   * Dato un grafo G tramite matrice di adiacenza, scrivere un algoritmo che costruisca le sue liste di adiacenza. Calcolare la complessità.
   * Dato un grafo G tramite matrice di incidenza, scrivere un algoritmo che costruisca le sue liste di adiacenza. Calcolare la complessità.
   * Dato un grafo G tramite liste di adiacenza, scrivere un algoritmo che dica se G è aciclico o no. (suggerimento: fare una visita che verifichi che non ci sono archi non dell'albero)
   * Dato un grafo G, scrivere un algoritmo che verifichi se G è euleriano oppure no. Considerare i tre casi in cui G è dato tramite liste di adiacenze, matrice di adiacenza e matrice di incidenza. Calcolare la complessità nei tre casi. (suggerimento: usare la caratterizzazione dei grafi euleriani)
<br>
</font>

---+++ <font color=990000 size="+1"> A.A. 2010/2011</font>
<font color=blue> 
*Lezioni 1-2: Giovedì 10 marzo 2011*

Introduzione
   * Concetti di algoritmo, di struttura dati, di efficienza; di complessita' computazionale;
   * modello RAM; misura di costo uniforme e logaritmico.
</font>

<font color=blue> 
*Lezioni 3-4: Venerdì 11 marzo 2011*

Notazione asintotica
   * Definizione e significato degli insiemi O, &Omega; e &Theta;.
   * Esempi
</font>

<font color=red> 
*Esercitazioni 1-2: Martedì 15 marzo 2011*

   * Discussione del programma di esempio:  [[%ATTACHURL%/esempio1.c][esempio1.c]]
   * Compilazione ed esecuzione di un programma C in Linux
   * Ripasso di nozioni elementari del linguaggio C:
      * Commenti 
      * Inclusione di librerie predefinite
      * Dal file C al file eseguibile: preprocessore, compilazione, linking
      * La funzione main
      * Variabili: tipi, dichiarazione, assegnamento
      * Operatori aritmetici, di uguaglianza e relazionali
      * Il comando if..else
</font>

<font color=red> 
*Esercitazioni 3-4: Mercoledì 16 marzo 2011*

   * Input da tastiera con la funzione scanf
   * Iterazione: ciclo while, for e do..while
   * Esempio di iterazione con il while:  [[%ATTACHURL%/fattoriale_iterativo.c][fattoriale_iterativo.c]]
   * Operatori logici: and, or e not
   * Vettori: 
      * Allocazione statica
      * Indicizzazione e accesso agli elementi
      * Esempio: trovare l'elemento di valore massimo: [[%ATTACHURL%/find_max_array.c][find_max_array.c]]
</font>

<font color=blue> 
*Lezioni 5-6: Giovedì 17 marzo 2011*

Festa del 150° anniversario dell'Unità d'Italia
</font>

<font color=blue> 
*Lezioni 7-8: Venerdi' 18 marzo 2011*

Il problema della ricerca
   * Ricerca sequenziale in un vettore disordinato;
   * complessita' nel caso migliore, peggiore e medio
   * Ricerca dicotomica o binaria in un vettore ordinato (vers. iterativa)
   * complessita' nel caso migliore, peggiore e medio

Introduzione alla Ricorsione
   * un esempio: il fattoriale
   * pregi e difetti di un algoritmo ricorsivo
</font>

<font color=green> 
*Tutoraggio 1: Martedì 22 marzo 2011*

   * Utilizzare la shell Linux
   * Comandi basilari della shell:
      * *ls* e *ls -l* - lista i file di una directory (l'opzione *-l* richiede anche gli attributi per riconoscere i file eseguibili)
      * *cd NOMEDIRECTORY* - change directory, ovvero entra nella directory NOMEDIRECTORY
      * *cd ..* - change directory, ovvero risale di una directory nella gerarchia delle directory
      * *pwd* - print working directory
   * Differenze fra gcc e dev-c++
   * Opzione *-c* di gcc - compilazione file sorgente C in Linux e ottenimento di un file oggetto
   * Linking di un eseguibile C in Linux (gcc senza opzioni, ma con l'elenco dei file oggetto da linkare)
   * Opzione *-o* di gcc - specifica del nome del file in output
   * Esecuzione di un programma in Linux dalla shell e considerazioni sull'utilizzo dei caratteri *./* prima del nome dell'eseguibile
   * Esempio di eseguibile generato da più file oggetto
   * Discussione esercizio min-max assegnato durante l'esercitazione
</font>

<font color=red> 
*Esercitazioni 5-6: Mercoledì 23 marzo 2011*

   * Operatori di incremento unitario ++ e -- : pre-incremento e post-incremento
   * Matrici di dati: 
      * Dichiarazione, rappresentazione in memoria
      * Esercizio: calcolare la somma degli elementi con valore positivo di una matrice: [[%ATTACHURL%/sum_positive_matrix.c][sum_positive_matrix.c]]
   * Funioni:
      * Motivazioni: modularità, riusabilità del codice
      * Dichiarazione
      * Variabili locali e valori di ritorno
      * Passaggio di parametri per valore
      * Chiamata di funzioni: stack, operazioni di push e pop, record di attivazione
      * Esercizio: funzione potenza: [[%ATTACHURL%/power_function.c][power_function.c]]
</font>

<font color=blue> 
*Lezioni 9-10: Giovedi' 24 marzo 2011*

La ricorsione

   * versione iterativa e ricorsiva di algoritmi: esempi (ricerca di doppioni in un vettore, ricerca in un vettore disordinato)
   * occupazione in memoria: l'esempio del calcolo dei numeri di Fibonacci
   * calcolo della complessita' delle funzioni ricorsive tramite equazioni di ricorrenza
</font>

<font color=blue> 
*Lezioni 11-12: Venerdi' 25 marzo 2011*

Soluzioni delle equazioni di ricorrenza (1)

   * metodo di sostituzione
   * metodo iterativo
   * metodo dell'albero
   * teorema principale (enunciato)
</font>

<font color=blue> 
*Lezioni 13-14: Mercoledi' 30 marzo 2011*

Soluzioni delle equazioni di ricorrenza (2)

   * teorema principale (dimostrazione per potenze esatte)

Il problema dell'Ordinamento (1)

   * Algoritmi Naif: filosofia, pseudocodice e complessita'
      * Insertion sort
      * Selection sort
</font>


<font color=red> 
*Esercitazioni 7-8: Giovedì 31 marzo 2011*

   * Dichiarazione di variabili nei blocchi del programma
   * Prototipi di funzione
   * Funzioni ricorsive:
      * Scrittura di una funzione ricorsiva: caso base e passo ricorsivo
      * Schema "generale" funzione ricorsiva
      * Esercizio: Trovare il minimo di un vettore: [[%ATTACHURL%/minimo_vettore_ricorsivo.txt][minimo_vettore_ricorsivo.txt]]
</font>

<font color=red> 
*Esercitazioni 9-10: Venerdi' 1 aprile 2011*

   * Esercizi sulle funzioni ricorsive:
      * Trovare il numero di occorrenze di un valore in un vettore:  [[%ATTACHURL%/occorrenze_vettore_ricorsivo.txt][occorrenze_vettore_ricorsivo.txt]]
      * Dire se un vettore e' palindromo: [[%ATTACHURL%/palidromo_ricorsivo.txt][palidromo_ricorsivo.txt]]
      * Dire se due vettori hanno almeno un elemento in comune: [[%ATTACHURL%/elemento_comune_vettori.txt][elemento_comune_vettori.txt]]
</font>

<font color=green> 
*Tutoraggio 2: Martedì 5 aprile 2011*

   * Riepilogo compilazione gcc
   * Prelevare un intero da tastiera
   * Stampare a video una stringa con numeri
   * Prendere da tastiera una sequenza di numeri e inserirli in un vettore
   * Scorrere i valori di un vettore
   * Accedere ai valori di un vettore (ricordare che gli indici partono da 0, quindi un vettore di 5 elementi ha i valori [0], [1], ..., [4])
   * Rischi di errore Segmentation Fault quando si usano i vettori (accesso a posizioni del vettore non esistenti)
   * Rischi di errore quando si usano variabili non inizializzate
   * Creazione file zip da riga di comando (zip OUTPUTFILE.zip NOMEFILE1 NOMEFILE2 NOMEFILE3 oppure zip OUTPUTFILE.zip *.c, per zippare tutti i file C presenti nella directory attuale)
</font>

<font color=blue> 
*Lezioni 15-16: Mercoledi' 6 aprile 2011*

Il problema dell'Ordinamento (2)

   * Algoritmi Naif: filosofia, pseudocodice e complessita'
      * Bubble sort
   * Limitazione inferiore sulla complessita' degli algoritmi per confronti (th. e dim.)
   * Un algoritmo ottimale: filosofia, pseudocodice e complessita'
      * Merge Sort; tecnica del Divide et Impera

CURIOSITA': Per divertirvi con gli algoritmi di ordinamento, vedete su http://www.i-programmer.info/news/150-training-a-education/2255-sorting-algorithms-as-dances.html
</font>

<font color=blue> 
*Lezioni 17-18: Giovedi' 7 aprile 2011*

Il problema dell'Ordinamento (3)

   * funzione di fusione
   * Ordinamento in tempo lineare: il countig sort
</font>

<font color=blue> 

*Lezioni 19-20: Venerdi' 8 aprile 2011*

Il problema dell'Ordinamento (4)

   * Altri algoritmi di ordinamento
      * Quick sort e funzione di partizione
      * complessita' del quick sort nel caso peggiore, migliore e medio

</font>

<font color=green> 
*Tutoraggio 3: Martedì 12 aprile 2011*

   * Passaggio da pseudo codice a codice C
   * Uso corretto degli indici di un vettore
   * Risoluzione degli esercizi assegnati a lezione:
      * [[%ATTACHURL%/palidromo_ricorsivo.c][palidromo_ricorsivo.c]]
      * [[%ATTACHURL%/conta_occorrenze.c][conta_occorrenze.c]]
      * [[%ATTACHURL%/somma_righe_ricorsivo.c][somma_righe_ricorsivo.c]]
      * [[%ATTACHURL%/trova_min.c][trova_min.c]]
</font>

<font color=red> 
*Esercitazioni 11-12: Mercoledi' 13 Aprile 2011*

   * Esercizi:
      * Funzione ricorsiva per trasformare un decimale in binario:  [[%ATTACHURL%/to_binary.txt][to_binary.txt]]
      * Funzione iterativa per trovare un VIP in una matrice: [[%ATTACHURL%/trova_vip.txt][trova_vip.txt]]
</font>

<font color=red> 
*Esercitazioni 13-14: Mercoledi' 27 Aprile 2011*

   * Esercizi:
      * Svolgimento esercizi primo esonero
      * Funzione iterativa per trovare un VIP in una matrice in costo lineare: [[%ATTACHURL%/trova_vip_lineare.txt][trova_vip_lineare.txt]]
</font>

<font color=blue> 
*Lezioni 21-22: Giovedi' 28 aprile 2011*

Il problema dell'Ordinamento (5)

   * struttura dati Heap massimo
   * funzione di estrazione del massimo dall'Heap
   * funzione di aggiustamento dell'Heap (Heapify) e sua complessita'
   * funzione di creazione dell'Heap (Build Heap) e sua complessita'
   * algoritmo di Heap Sort e sua complessita'

</font>

<font color=blue>
*Lezioni 23-24: Venerdi' 29 aprile 2011*

Strutture dati fondamentali (1)

   * insiemi dinamici ed operazioni su di essi
   * implementazione di un insieme dinamico su un vettore
   * la nozione di puntatore e la struttura dati lista
   * operazioni elementari su liste
   * lista doppiamente puntata
   * realizzazione di puntatori tramite vettori

</font>

<font color=green> 
*Tutoraggio 4: Martedì 3 maggio 2011*

   * Heap
   * Max-heap binario: rappresentazione ad albero e rappresentazione compatta con un array
   * Implementazione in C funzioni left, right e parent di un max-heap binario
   * Implementazione in C della funzione [[%ATTACHURL%/max_heapifty.txt][max_heapifty]] per ripristinare la proprietà max-heap di un sottoalbero
   * Linee guida per la costruzione delle funzioni build-heap e heapsort
</font>

<font color=blue>
*Lezioni 25-26: Mercoledi' 4 maggio 2011*

Strutture dati fondamentali (2)

   * la struttura dati pila
   * le operazioni Push e Pop
   * la struttura dati coda
   * le operazioni Enqueue e Dequeue
   * coda circolare
   * implementazione della pila e della coda tramite vettori e liste
   * code con priorita'
   * definizione di albero come grafo connesso aciclico
   * teorema di caratterizzazione degli alberi

</font>

<font color=blue>
*Lezioni 27-28: Giovedi' 5 maggio 2011*

Strutture dati fondamentali (3)

   * alberi radicati, alberi binari, alberi ordinati, alberi binari completi
   * relazioni tra numero di nodi interni, numero di foglie ed altezza in un albero binario completo
   * rappresentazione in memoria di un albero binario
      * rappresentazione posizionale
      * rappresentazione con puntatori
      * vettore dei padri
   * visita di un albero
      * visita in pre-, post- ed in-ordine
      * complessita' di una visita tramite equazione di ricorrenza
</font>

<font color=red> 
*Esercitazioni 15-16: Venerdi' 6 Maggio 2011*

   * Strutture
      * typedef
   * Puntatori
      * Dichiarazione
      * Operatori & e *
      * Puntatori a strutture
      * Allocazione dinamica: funzione malloc
   * Liste 
      * Dichiarazione struttura lista di interi
      * Esercizio: inserimento in testa e stampa: [[%ATTACHURL%/int_list.c][int_list.c]]
</font>

<font color=green> 
*Tutoraggio 5: Martedì 10 maggio 2011*

   * Heap
   * Max-heap binario
   * Creazione di un vettore con dimensione scelta a tempo di esecuzione (funzione malloc)
   * Costruzione delle funzioni build-heap e heapsort
</font>

<font color=red> 
*Esercitazioni 17-18: Mercoledi' 11 Maggio 2011*

   * Code:
      * funzioni push e pop: [[%ATTACHURL%/coda.c][coda.c]]
   * Pile
      * funzioni enqueue e dequeue: [[%ATTACHURL%/pila.c][pila.c]]
   * Esercizio: creazione di una copia di una lista data con elementi invertiti: [[%ATTACHURL%/inverti_lista.c][inverti_lista.c]]
</font>


<font color=blue>
*Lezioni 29-30: Giovedi' 12 maggio 2011*

Dizionari (1)

   * Indirizzamento diretto
   * tabelle hash
      * collisioni
      * soluzione delle collisioni per concatenazione (liste di trabocco e fattore di carico)
      * complessita' nel caso medio
      * alcuni esempi di funzioni hash
      * soluzioni delle collisioni con indirizzamento aperto
      * vari tipi di scansione (lineare, quadratica ed hashing doppio)
      * complessita' nel caso medio
</font>

<font color=blue>
*Lezioni 31-32: Venerdi' 13 maggio 2011*

Dizionari (2)

   * alberi binari di ricerca
      * definizione
      * algoritmo di ricerca e sua complessita'
      * algoritmi di ricerca del massimo, minimo, successore e predecessore e loro complessita'
      * algoritmo di inserimento e sua complessita'
      * algoritmo di cancellazione e sua complessita'
   * la problematica del bilanciamento per la limitazione della complessita'
</font>

<font color=green> 
*Tutoraggio 6: Martedì 17 maggio 2011*

   * Conclusione Heapsort
   * Differenza vettore di array e lista linkata di array
   * Rappresentazione puntatore e elementi lista nella memoria
   * Aggiunta elementi in un punto generico della lista
   * Eliminazione di elementi da una lista
   * Esercizio di inversione di una lista senza nuova allocazione
</font>

<font color=blue>
*Lezioni 33-34: Mercoledi' 18 maggio 2011*

Grafi (1)

   * rappresentazioni in memoria
      * liste di adiacenza
      * matrice di adiacenza
      * matrice di incidenza
      * lista di archi
      * confronto della complessita' spaziale e temporale in alcune operazioni elementari
   * visita in ampiezza (BFS)
      * definizione di albero ricoprente
      * proprietà degli archi non dell'albero 
      * proprieta' della distanza dalla radice
</font>
<font color=red> 
*Esercitazioni 19-20: Giovedi' 19 Maggio 2011*

   * Esercizi:
      * Invertire una lista senza creare copie degli elementi: [[%ATTACHURL%/inverti_list.c][inverti_list.c]]
      * Eliminare le occorrenze di un valore da una lista: [[%ATTACHURL%/elimina_occorrenze.c][elimina_occorrenze.c]]
   * Passaggio di parametri per riferimento
      * Funzione pop che modifica la lista passata come parametro: [[%ATTACHURL%/pop.c][pop.c]]
</font>

<font color=blue>
*Lezioni 35-36: Venerdi' 20 maggio 2011*

Grafi (2)

   * visita in profondita' (DFS)
      * proprietà degli archi non dell'albero 
      * proprieta' del numero di archi in funzione della lunghezza del cammino più lungo
   * similitudini e differenze tra le due visite
   * loro complessita' al variare della struttura dati usata
   * verifica della connessione di un grafo
   * calcolo della distanza da un nodo dato
</font>

<font color=green> 
*Tutoraggio 7: Martedì 24 maggio 2011*

   * Altra versione esercizio inversione di lista senza allocazione
   * Fusione di due liste
   * Passaggio di parametri per riferimento
   * Esempi di funzione con passaggio per riferimento (swap e merge_lista)
   * Implementazione delle funzioni push, pop, stack_empty e stack_notfull con vettore statico
   * Suggerimenti per la soluzione del secondo esercizio dell'homework 3 (uso di uno stack, o pila)
</font>

<font color=red> 
*Esercitazioni 21-22: Mercoledi' 25 Maggio 2011*

   * Esercizi: funzioni ricorsive sulle liste [[%ATTACHURL%/liste_funzioni_ricorsive.c][liste_funzioni_ricorsive.c]]
      * Numero di elementi
      * Eliminare occorrenze degli elementi con una chiave data
      * Inclusione di una lista in un'altra
      * Inserimento in lista ordinata: [[%ATTACHURL%/inserimento_ordinato.c][inserimento_ordinato.c]]
</font>

<font color=blue>
*Lezioni 37-38: Giovedi' 26 maggio 2011*

Grafi (3)

   * calcolo del quadrato di un grafo
   * grafi euleriani e loro caratterizzazione
   * grafi bipartiti e loro caratterizzazione
   * accoppiamenti massimi e accoppiamenti massimali
</font>

<font color=blue>
*Lezioni 39-40: Venerdi' 27 maggio 2011*

Grafi (4)

   * accoppiamenti completi per grafi bipartiti e teoram di P. Hall
   * colorazione di grafi ed enunciato del teroema di Brooks
   * grafi planari e formula di Eulero
   * enunciato del teorema dei 4 colori
</font>

<font color=green> 
*Tutoraggio 7: Martedì 31 maggio 2011*

   * Approfondimenti sulla scanf
   * Utilizzo della scanf per ricevere un numero arbitrario di valori da inserire in una lista
   * Differenze fra albero binario di ricerca e heap massimo/minimo
   * Ripetizione sulle funzioni per la ricerca, l'inserimento e la rimozione di elementi da un albero binario di ricerca
</font>

<font color=red> 
*Esercitazioni 23-24: Mercoledi' 1 Giugno 2011*

   * Definizione alberi binari in C
   * Esercizio: funzione ricorsiva per contare il numero di livelli
   * Esercizio: Ricostruire un albero binario data la visita in ordine e quella in preordine
</font>


<font color=green> 
*Tutoraggio 7: Martedì 7 giugno 2011*

   * Implementazioni sugli alberi binari di ricerca in C:
      * tree_max e tree_min
      * tree_successor
      * tree_search
      * tree_insert
   * Linee guida per la tree_delete
</font>


-- %USERSIG{TizianaCalamoneri - 2017-03-15}%

---++ Comments

%COMMENT%