A.A. 2016/2017

Lezioni 1-2: mercoledì 1 marzo 2017

Presentazione del corso
Introduzione

• 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.
• Pseudocodice

Esercitazioni 1-2: venerdì 3 marzo 2017

• 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

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

Lezioni 3-4: lunedì 6 marzo 2017

Notazione asintotica (1)

• Definizione e significato degli insiemi O, Ω e Θ.
• Esempi.
• Algebra della notazione asintotica.
• Valutazione del costo computazionale di un algoritmo.

Esercizi assegnati:

• Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione

Lezioni 5-6: mercoledì 8 marzo 2017

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

• ricerca sequenziale e suo costo computazionale nel caso migliore, peggiore e medio
• ricerca dicotomica e suo costo computazionale nel caso migiore e peggiore

Esercizi assegnati:

• Calcolare l'andamento asintotico 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)

Esercitazioni 3-4: venerdì 10 marzo 2017

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

• Esercizi consigliati: Dispensa D1, sez. 2.5, esercizi da 2 a 8.

Lezioni 7-8: lunedì 13 marzo 2017

Ricorsione

• funzioni matematiche ricorsive;
• algoritmi ricorsivi: aspetti principali;
• ricerca sequenziale: pseudocodice ricorsivo;
• ricerca binaria: pseudocodice ricorsivo;

Soluzioni delle equazioni di ricorrenza (1)

• metodo di sostituzione; esempi
• metodo iterativo; esempi

Esercizi assegnati:

• Progettare degli algoritmi ricorsivi ed esprimerli tramite pseudocodice che risolvano i seguenti problemi:
  • dato in input un vettore, stampare i suoi valori dal primo all'ultimo
  • dato in input un vettore, stampare i suoi valori dall'ultimo al primo

Lezioni 9-10: mercoledì 15 marzo 2017

Soluzioni delle equazioni di ricorrenza (2)

• metodo dell'albero; esempi
• metodo del teorema principale (senza dimostrazione); esempi

Esercizi svolti in classe:

• 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)=Θ(1):
  • T(n)=3T(n/2)+Θ(n)
  • T(n)=2T(n/3)+Θ(n)

Esercitazioni 5-6: venerdì 17 marzo 2017

• I problemi di alias: funzione scambia(int*,int*) senza variabile di appoggio [ D3, sez. 3 ].
• Assegnamento parallelo à la Python: asPar(int*,int*,int,int).
• 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 ]

Lezioni 11-12: lunedì 20 marzo 2017

Soluzioni delle equazioni di ricorrenza (3)

Esercizio assegnato in classe e poi svolto:

• calcolare la soluzione della seguente equazione di ricorrenza con tutti e quattro i metodi:
  • T(n)=2T(n/2)+Θ(n)
  • T(1)=Θ(1)

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)=Θ(1):
  • T(n)=3T(n/4)+Θ(n)
  • T(n)=2T(n/2)+Θ(n^2)
  • T(n)=4T(n/2)+Θ(n)
  • T(n)=2T(n/2)+Θ(n^3)
  • T(n)=16T(n/4)+Θ(n^2)
  • T(n)=T(n-1)+Θ(n)

Lezioni 13-14: mercoledì 22 marzo 2017

Il problema dell'ordinamento (1)

• Algoritmi semplici: insertion sort, selection sort, bubble sort: pseudocodice e costo computazionale nel caso migliore e peggiore.
• Teorema sulla limitazione inferiore per il costo computazionale di un algoritmo basato su confronti e scambi.

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).

Esercitazioni 7-8: venerdì 24 marzo 2017

• 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 e ricorsiva) di un vettore. [ D6, sez. 1 ]

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

Lezioni 15-16: lunedì 27 marzo 2017

Il problema dell'ordinamento (2)

• Algoritmi efficienti: merge sort, pseudocodice e costo computazionale

Esercizi assegnati:

• 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.
• 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] 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))

Lezioni 17-18: mercoledì 29 marzo 2017

Il problema dell'ordinamento (3)

• Algoritmi efficienti: quicksort, pseudocodice e complessità nei casi migliore, peggiore e medio (senza dimostrazione)
• Algoritmi efficienti: heapsort (struttura dati heap; funzione heapify: pseudocodice e costo computazionale)

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.
• Calcolare il costo computazionale del Quick sort nei casi in cui: il vettore sia ordinato in senso crescente; il vettore sia ordinato in senso decrescente; il vettore contenga tutti elementi uguali.
• 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.

Esercitazioni 9-10: venerdì 31 marzo 2017

• 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 ].

• 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 ]

Lezioni 19-20: lunedì 3 aprile 2017

Il problema dell'ordinamento (4)

• Algoritmi efficienti: heapsort (funzioni buildheap e heapsort: pseudocodice e costo computazionale)
• Algoritmi di ordinamento lineari: counting sort (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.
• 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))

Lezioni 21-22: mercoledì 5 aprile 2017

• Assegnazione di alcuni esercizi preparatori al primo esonero, da risolvere a cura degli studenti.
• Successivo svolgimento alla lavagna degli esercizi stessi.

Esercitazioni 11-12: venerdì 7 aprile 2017

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 ].

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

Lunedì 10 aprile 2017

• 14:00 - 17:00: Svolgimento della prova scritta relativa al primo esonero

Mercoledì 12 aprile 2017

• Svolgimento alla lavagna degli esercizi 1 e 3 assegnati al primo esonero.

Esercitazioni 13-14: mercoledì 19 aprile 2017

• 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.

Venerdì 21 aprile 2017

• Consultazione dei compiti relativi al primo esonero.

Lezioni 23-24: mercoledì 26 aprile 2017

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
• la struttura dati coda
• le operazioni enqueue e dequeue

Esercitazioni 15-16: venerdì 28 aprile 2017

• 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.

Lezioni 25-26: mercoledì 3 maggio 2017

Strutture dati fondamentali (2)

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

Esercizi svolti in classe:

• Simulare il comportamento di una coda mediante l'uso di più pile

Esercitazioni 17-18: venerdì 5 maggio 2017

• 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.

Lezioni 27-28: lunedì 8 maggio 2017

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

Lezioni 29-30: mercoledì 10 maggio 2016

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 svolti in classe:

• Calcolare il numero di nodi di un albero binario
• Verificare se una data chiave k è presente in un albero binario
• Calcolare l'altezza di un albero binario
• Contare i nodi di un albero binario che si trovano a livello k (il livello della radice è zero)
• Realizzare una visita in pre-ordine senza ricorsione, mediante l'uso di una pila
• Realizzare una visita per livelli mediante l'uso di una coda

Esercitazioni 19-20: venerdì 12 maggio 2017

• 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.
• remove iterativa in place.

• Esercizi consigliati: Ancora esercizi alla fine di dispensa D8.

Lezioni 31-32: lunedì 15 maggio 2017

Dizionari (1)

• definizione di dizionario e problematiche associate
• tabelle ad indirizzamento diretto
• tabelle hash
• il 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

Lezioni 33-34: mercoledì 17 maggio 2017

Dizionari (2)

• alberi binari di ricerca
  • 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
  • algoritmo di cancellazione e suo costo computazionale

Esercizi assegnati:

• 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.

Esercitazioni 21-22: venerdì 19 maggio 2017

• 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.

Lezioni 35-36: lunedì 22 maggio 2017

Dizionari (3)

• alberi Red-Black
  • definizione
  • dimostrazione dell'altezza logaritmica
  • cenni ai meccanismi di ribilanciamento: cambi di colore e rotazioni

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

Esercitazioni 23-24: mercoledì 24 maggio 2017

• 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)

Lezioni 37-38: venerdì 26 maggio 2017

Grafi (2)

• 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

• 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
  • proprietà degli archi non dell'albero
  • proprieta' della distanza dalla radice

Lezioni 39-40: lunedì 29 maggio 2017

Grafi (3)

• 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

• Algoritmo di Dijkstra (1)
  • la rete Internet è modellata come un grafo pesato sul quale individuare i cammini di costo minimo
  • cenni sul funzionamento store-and-forward dei router
  • fenomeni che possono modificare i cammini minimi: caduta di linee o di router, congestione

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
• Modificare la visita in ampiezza in modo da verificare se il grafo contiene cicli oppure no
• Modificare la visita in ampiezza in modo da verificare se il grafo è connesso oppure no

Lezioni 41-42: lunedì 31 maggio 2017

Grafi (4)

• 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

Lezioni 43-44: mercoledì 8 giugno 2017

Svolgimento in classe di esercizi preparatori al secondo esonero:

• Dati due alberi binari di ricerca, fonderli in un unico albero binario di ricerca (che può essere uno dei due a cui si aggiungono i nodi dell'altro). Non occorre distruggere l'albero dal quale si ricopiano i nodi.
• Esercizio n. 1 del compito scritto assegnato in data 11 giugno 2015 (reperibile alla pagina dei vecchi scritti)
• Dato un albero binario, calcolare la larghezza dell'albero, definita come il massimo numero di nodi che si trovano allo stesso livello..
• Dato un albero binario, trovare il nodo (o uno dei nodi) che presenta la massima differenza fra i numeri di nodi del proprio sottoalbero sinistro e del proprio sottoalbero destro.
• Dato un albero binario, aggiungere ad ogni foglia un figlio sinistro la cui chiave abbia valore uguale alla somma delle chiavi contenute nei nodi che si trovano lungo il cammino dalla radice alla foglia stessa.
• Dato un vettore contenente interi non nulli, scrivere una funzione che sistemi tutti i valori negativi a sinistra di tutti i valori positivi