AnnoAccademico2018-2019 < Infogen

Tags: view all tags
---+++ <font color="990000" size="+1">Lezioni dell'anno accademico 2018/2019</font>

%BLUE%
*Lezioni 1-2: lunedì 25 febbraio 2019*

Presentazione agli studenti della visita ANVUR<br />
Presentazione del corso<br />
Introduzione
   * Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale.
%ENDCOLOR%

%BLUE%
*Lezioni 3-4: mercoledì 27 febbraio 2019*

Notazione asintotica (1)
   * Modello RAM; misura di costo uniforme e logaritmico.
   * Definizione e significato degli insiemi O, &Omega; e &Theta;.
   * Esempi.
   * Algebra della notazione asintotica.
%ENDCOLOR%

%BLACK%
*Esercitazioni 1-2: venerdì 1 marzo 2019*
   * ==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%
*Lezioni 5-6: lunedì 4 marzo 2019*

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

Il problema della ricerca (1)
   * ricerca sequenziale e suo costo computazionale nel caso migliore, peggiore e medio
   * ricerca dicotomica e suo costo computazionale nel caso migliore e peggiore
%ENDCOLOR%

%BLUE%
*Lezioni 7-8: mercoledì 6 marzo 2019*

Il problema della ricerca (2)
   * costo computazionale della ricerca dicotomica nel caso medio

Ricorsione
   * funzioni matematiche ricorsive
   * algoritmi ricorsivi: aspetti principali
   * equazioni di ricorrenza
   * ricerca sequenziale: pseudocodice ricorsivo ed equazione di ricorrenza
   * ricerca binaria: equazione di ricorrenza

Soluzioni delle equazioni di ricorrenza (1)
   * metodo di sostituzione; esempi

Esercizi assegnati:
   * Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione
   * Calcolare l'andamento asintotico stretto di alcune funzioni
   * Calcolare il caso migliore e peggiore del costo computazionale degli algoritmi di Selection Sort, Insertion Sort e Bubble Sort (pseudocodice sulle dispense)
%ENDCOLOR%

*%RED% Venerdì 8 Marzo 2019%ENDCOLOR%* Lezioni sospese per le Olimpiadi di Matematica (aule occupate)

%BLUE%
*Lezioni 9-10: lunedì 11 marzo 2019*

Soluzioni delle equazioni di ricorrenza (2)
   * metodo iterativo; esempi
   * metodo dell'albero; esempi
%ENDCOLOR%

%BLACK%
*Mercoledì 13 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%

%BLACK%
*Venerdì 15 marzo 2018 - 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%
*Lezione 11: lunedì 18 marzo 2019*

Soluzioni delle equazioni di ricorrenza (3)
   * metodo del teorema principale (senza dimostrazione); esempi
%ENDCOLOR%

%BLUE%
*Lezioni 12-13: mercoledì 20 marzo 2019 (Prof.ssa Calamoneri)*

Soluzioni delle equazioni di ricorrenza (4)

Esercizi svolti in classe:
   * calcolare la soluzione delle seguenti equazioni di ricorrenza:
      * T(n)=T(n-1)+T(n-2) +&Theta;(1) con metodo iterativo
      * T(n)=T(n/3)+T(2/3 n)+&Theta;(n) con tutti i metodi tranne principale
      * T(n)=2T(n/2)+&Theta;(n**2) con tutti e quattro i metodi
      * T(n)=4T(n/2)+&Theta;(n) con tutti e quattro i metodi
   * dove per tutte si ha:
      * T(1)=&Theta;(1)
%ENDCOLOR%

%BLACK%
*Venerdì 22 marzo 2019: Esercitazioni 7-8:* %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* ]
   * Sul tema, *Soluzione Esonero 2014*: il problema del massimo fattore primo [ *S4* ]
   * Problemi con soluzione inerentemente ricorsiva: il problema della Torre di Hanoi [ *D3*, sez. *3* ]
   * Coefficienti binomiali.

   * *Elucubrazioni*: inutilità dell' ==if else== in Tiny C. Vera complessità asintotica di Fibonacci iterativo.
   * *Esercizi consigliati*: Dispensa *3* [sez. *2.4* e *3.3* ]

%ENDCOLOR%

%BLUE%
*Lezioni 14-15: lunedì 25 marzo 2019*

Soluzioni delle equazioni di ricorrenza (5)

Esercizi assegnati agli studenti da svolgere in classe e poi svolti dal docente:
   * Calcolare la soluzione delle seguenti equazioni di ricorrenza col metodo del problema principale e col metodo iterativo, 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)=2T(n/3)+&Theta;(n)

Il problema dell'ordinamento (1)
   * Algoritmi semplici: insertion sort: pseudocodice e costo computazionale nel caso migliore e peggiore.
%ENDCOLOR%

%BLUE%
*Lezioni 16-17: mercoledì 27 marzo 2019*

Il problema dell'ordinamento (2)
   * Algoritmi semplici: selection sort, bubble sort: pseudocodice e costo computazionale.
   * Teorema sulla limitazione inferiore per il costo computazionale di un algoritmo basato su confronti e scambi.
   * Algoritmi efficienti: merge sort, pseudocodice e costo computazionale

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 in modo che utilizzi ripetutamente questa funzione.
   * Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (prima versione).
%ENDCOLOR%

%BLACK%
*venerdì 29 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%
*Lezioni 18-19: lunedì 1 aprile 2019*

Il problema dell'ordinamento (3)
   * Algoritmi efficienti: quicksort, pseudocodice e costo computazionale (con dimostrazione per il caso medio)

Esercizio svolto in classe:
   * Si consideri una modifica del Merge Sort in cui il caso base si applica ad una porzione del vettore di lunghezza k, ordinata usando l'algoritmo Insertion Sort. Le porzioni così ordinate vengono combinate usando il meccanismo standard di fusione. Si determini il valore di k come funzione di n per cui l'algoritmo modificato ha lo stesso tempo di esecuzione asintotico del Merge Sort.

Esercizi assegnati:
   * Scrivere la funzione di fusione utilizzando la ricorsione
   * Determinare l'albero delle decisioni della funzione di fusione, quando i vettori da fondere sono [a1, a2, a3] e [b1, b2, b3] (con l'implicita ipotesi che a1&lt;a2&lt;a3 e b1&lt;b2&lt;b3)
   * Determinare il costo computazionale del Quicksort quando è applicato a un vettore contenente n elementi identici
   * 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.
   * 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%

%BLUE%
*Lezioni 20-21: mercoledì 3 aprile 2019*

Il problema dell'ordinamento (4)
   * Algoritmi efficienti: heapsort (struttura dati heap; funzioni heapify e buildheap: pseudocodice e costo computazionale)

Esercizi assegnati:
   * Scrivere lo pseudocodice di una funzione che, dato un heap di n elementi al quale e' stata aggiunta nella posizione (n + 1) una nuova foglia con valore arbitrario, ripristini la proprieta' di heap nel nuovo albero di dimensione (n + 1). Valutare il costo computazionale.
   * Scrivere lo pseudocodice di una funzione che, dato un heap massimo di n elementi, ripristini la proprieta' di heap dopo che il valore di uno e uno solo dei nodi dello heap sia stato arbitrariamente modificato. Valutare il costo computazionale.
%ENDCOLOR%

%BLACK%
*venerdì 5 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.

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

%BLUE%
*Lezioni 22-23: lunedì 8 aprile 2019*

Il problema dell'ordinamento (4)
   * Algoritmi efficienti: heapsort (funzione heapsort: pseudocodice e costo computazionale)
   * Algoritmi di ordinamento lineari: counting sort (pseudocodice e costo computazionale); counting sort con dati satellite (descrizione generale dell'algoritmo); bucket sort (descrizione generale dell'algoritmo).

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.
   * 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))
%ENDCOLOR%

%BLUE%
*Lezioni 24-25: mercoledì 10 aprile 2019 (Prof.ssa Calamoneri)*

Esercitazione di preparazione al primo esonero (identica per entrambi i canali)
%ENDCOLOR%

%BLACK%
*venerdì 12 aprile 2019 - Esercitazioni 13-14*
%BLACK%   
   * *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%

%RED%
*Lunedì 15 aprile 2019*

   * 14:00 - 17:00: Svolgimento della prova scritta relativa al primo esonero
%ENDCOLOR%

%BLUE%
*Lezioni 26-27: lunedì 29 aprile 2019*

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, eliminazione
   * la struttura dati lista doppiamente puntata
   * eliminazione di un elemento dalla lista doppiamente puntata
   * la lista circolare
%ENDCOLOR%

%BLACK%
*Esercitazioni 15-16: venerdì 3 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%

%BLUE%
*Lezioni 28-29: lunedì 6 maggio 2019*

Strutture dati fondamentali (2)
   * la struttura dati coda e le operazioni enqueue e dequeue
   * la struttura dati coda con priorità e le operazioni enqueue e dequeue
   * la struttura dati pila e le operazioni push e pop
   * funzionamento della pila di sistema (system stack) per la gestione delle chiamate di funzione

Esercizi svolti in classe:
   * Calcolare la somma degli elementi di una lista con una funzione iterativa e poi con una funzione ricorsiva
   * Simulare il comportamento di una coda mediante l'uso di due pile (descrizione sintetica della soluzione)
%ENDCOLOR%

%BLUE%
*Lezioni 30-31: mercoledì 8 maggio 2019*

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

Esercizi assegnati:
   * dato un albero memorizzato tramite vettore dei padri, crearne una copia memorizzata tramite notazione posizionale. Calcolare il costo computazionale
   * dato un albero memorizzato tramite notazione posizionale, crearne una copia memorizzata tramite vettore dei padri. Calcolare il costo computazionale
%ENDCOLOR%

%BLACK%
*Esercitazioni 17-18: venerdì 10 maggio 2019*

   * Attenzione alla memoria raggiungibile: side effects. L'esempio di ==twiceL== [dispensa *D6*, sez. *3.2* ].
   * 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%

%BLUE%
*Lezioni 32-33: lunedì 13 maggio 2019*

Dizionari (1)

   * definizione di dizionario e problematiche associate
   * alberi binari di ricerca (1)
      * definizione
      * algoritmo di ricerca e suo costo computazionale
      * algoritmi di ricerca del massimo, minimo, successore e predecessore e loro costo computazionale
      * algoritmo di inserimento e suo costo computazionale
%ENDCOLOR%

%BLUE%
*Lezioni 34-35: mercoledì 15 Maggio 2019 (Prof.ssa Calamoneri)*

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 19-20: venerdì 17 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 passati: differenza simmetrica tra liste (ordinate). Attenzione alle versioni che modificano [Dispensa *S6*, sez. *1.3* ].

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

%BLUE%
*Lezioni 36-37: lunedì 20 maggio 2019*

Dizionari (2)

   * alberi binari di ricerca (2)
      * algoritmo di cancellazione e suo costo computazionale
   * alberi Red-Black
      * definizione
      * dimostrazione dell'altezza logaritmica
      * cenni ai meccanismi di ribilanciamento: cambi di colore e rotazioni

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
   * Sia dato un albero binario di ricerca T memorizzato mediante record e puntatori e contenente chiavi intere. Si progetti un algoritmo il più efficiente possibile che trovi le due chiavi di T aventi distanza massima.
   * Sia dato un vettore V ordinato contenente n elementi distinti fra loro con n = 2**k -1 per un certo k. Si progetti una funzione ricorsiva il più efficiente possibile che crei un albero binario di ricerca completo contenente tutte le chiavi di V.
   * Sia dato un albero binario di ricerca T, memorizzato mediante record e puntatori e contenente chiavi intere, ed un valore intero a. Si progetti una funzione ricorsiva il più efficiente possibile che stampi tutte le chiavi di T che sono maggiori di a.
   * Dati due alberi binari di ricerca T1 e T2, si progetti una funzione che crei un albero binario di ricerca contenente tutte le chiavi di T1 e T2.
%ENDCOLOR%

%BLUE%
*Lezioni 38-39: mercoledì 22 maggio 2019*

Grafi (1)

   * definizione di grafo, grafo diretto, grafo pesato
   * definizione di passeggiata, cammino, cammino semplice
   * definizione di circuito e ciclo
   * relazione di raggiungibilità e sue caratteristiche
   * definizione di componente connessa
   * definizione di sottografo, sottografo indotto, sottografo ricoprente
   * rappresentazioni in memoria
      * liste di adiacenza
      * matrice di adiacenza
      * matrice di incidenza
      * lista di archi
      * confronto della costo computazionale spaziale e temporale per alcune operazioni elementari
%ENDCOLOR%

%BLACK%
*Esercitazioni 21-22: venerdì 24 maggio 2019*
   * Esercizi da *esoneri* passati:
      * differenza simmetrica tra liste (ordinate). Attenzione alle versioni che modificano [Dispensa *S6*, sez. *1.3* ];
      * suddividere una lista in due lista, una contenente gli elementi in posti pari e una con gli elementi in posto dispari;
      * cenni alla fusione ordinata tra liste e a un'eventuale implementazione di mergesort sulle liste.
   * 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, profondità.

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

%RED% *Lunedì 27 maggio 2019*: <span style="background-color: transparent;">Lezioni sospese per le Elezioni Europee</span>
%ENDCOLOR%

%BLUE%
*Lezioni 40-41: mercoledì 29 maggio 2019*

Grafi (2)

   * aspetti generali delle visite
      * differenza concettuale fra visita in ampiezza e visita in profondità
      * implementazioni possibili: iterativa (tramite coda o pila) e ricorsiva (solo per visita in profondità)
      * definizione di albero di visita
      * archi dell'albero e archi non dell'albero

   * visita in ampiezza (BFS)
      * pseudocodice della visita in ampiezza
      * esempio di funzionamento della visita in ampiezza
      * costo computazionale della visita in ampiezza

Esercizi assegnati:
   * Per ciascuno dei modi visti a lezione per memorizzare un grafo, scrivere le funzioni necessarie a crearne uno identico memorizzato in tutti gli altri modi
   * Modificare la visita in ampiezza in modo da calcolare e memorizzare, per ciascun nodo, la distanza dalla sorgente
   * Verificare se il grafo contiene cicli oppure no
   * Verificare se il grafo è connesso oppure no
%ENDCOLOR%

%BLACK%
*Esercitazioni 23-24: venerdì 31 maggio 2019*
   * Ancora sugli alberi binari:
      * stampa parentesizzata e indentata di un albero binario;
      * visite: funzioni che memorizzano le etichette di un albero in una lista. Versioni efficienti senza uso di ==append==.
      * code con liste semplici.
      * visita per livelli di un albero binario.
      * Il problema del bilanciamento: versioni naive e versioni che evitano di ricalcolare la profondità.

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

%BLUE%
*Lezioni 42-43: lunedì 3 giugno 2019*

Grafi (3)

   * visita in ampiezza (BFS)
      * proprietà degli archi non dell'albero
      * proprieta' della distanza dalla radice

   * visita in profondità (DFS)
      * pseudocodice della visita in profondità
      * costo computazionale della visita in profondità
      * proprietà degli archi non dell'albero
      * relazione fra lunghezza dei cammini e numero di archi del grafo
%ENDCOLOR%

%BLUE%
*Lezioni 44-45: mercoledì 5 giugno 2019*

Grafi (4)

   * Algoritmo di Dijkstra (1)
      * la rete Internet è modellata come un grafo pesato sul quale individuare i cammini di costo minimo
      * cenni storici sull'evoluzione del sistema telefonico e della rete Internet
      * cenni sul funzionamento store-and-forward dei router
      * fenomeni che possono modificare i cammini minimi: caduta di linee o di router, congestione
      * descrizione introduttiva dell'algoritmo di Dijkstra
%ENDCOLOR%

%BLACK%
*Esercitazioni 25-26: venerdì 7 giugno 2019*
   * Esercizi su 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* ]
      * 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.

   * *Esercizi consigliati*: vedi dispensa *S6*, con soluzioni agli esercizi di compiti passati.
%ENDCOLOR%

%BLUE%
*Lezioni 46-47: lunedì 10 giugno 2019*

Grafi (5)

   * Algoritmo di Dijkstra (2)
      * pseudocodice dell'algoritmo
      * esempio dettagliato di funzionamento su un grafo pesato
      * costo computazionale dell'algoritmo in funzione dell'implementazione della coda con priorità
      * dimostrazione per induzione della correttezza dell'algoritmo
%ENDCOLOR%

%BLACK%
*Esercitazioni 27-28: venerdì 14 giugno 2019*
   * Ricostruzione di un albero binario avendo due visite (ad esempio, preorder e inorder).
   * *Esoneri passati*
      * relazione di prefisso tra alberi. Verificare se una lista di alberi è ordinata;
      * sostituire le etichette di un albero con la somma del sottoalbero;
      * calcolare la distanza tra due nodi di un albero.

   * *Esercizi consigliati*: vedi dispensa *S6*, con soluzioni agli esercizi di compiti passati.
%ENDCOLOR%