A.A. 2015/2016

Lezioni 1-2: mercoledì 2 marzo 2016

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ì 4 marzo 2016

• Introduzione ai concetti di problema, procedura risolutiva, automa. [dispensa parte D1, sezioni 1 ]
• Tiny-C. Codifica in Tiny-C del programma che calcola la somma iterando +1 [ D2, sez. 1 ]
• Indagini su un programma iterativo [ D1, sez. 2.1 ]:
  • Testing ed esecuzione "manuale" (trace).
  • Precondizioni, Postcondizioni, invarianti di ciclo.
  • Terminazione di un ciclo: funzione di terminazione.
• Esempio: Programma che calcola la moltiplicazione. Uso della funzione somma nel calcolo del prodotto.

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

Lezioni 3-4: lunedì 7 marzo 2016

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ì 9 marzo 2016

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)

Tutoraggio 1-2: giovedì 10 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.

Esercitazioni 3-4: venerdì 11 marzo 2016

• 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.
• Esercizio Funzione compareTo(int, int) fra numeri naturali.
• Introduzione alle funzioni ricorsive. Definizioni induttive e corrispondenti programmi ricorsivi [ D4, sez. 1.1 ].
  
  • Esempi: somma, fattoriale.

• Esercizi consigliati: Dispensa 2 [sez. 3.3 ]

Lezioni 7-8: lunedì 14 marzo 2016

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ì 16 marzo 2016

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)

Tutoraggio 3-4: giovedì 17 marzo 2016

• Anatomia di un errore ricorrente in C: attenzione a = e ==.
• Esperienze di overflow.
• MCD, algoritmo della Maestra.

Esercitazioni 5-6: venerdì 18 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-reC. Riflessioni sulla completezza computazioneale di Tiny-reC.

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

Esercitazioni 7-8: lunedì 21 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: assegnamento parallelo à la Dijkstra (o Python). Call-by-value.
  • Esempio: Scambia senza variabile di appoggio. Side effects e alias [ D3, sez. 1.2 ].
  • Esempio: funzione int divRef(int m, int n, int* q, int* r) che calcola divisibilità, quoziente e resto simultaneamente.

• Esercizi consigliati: Dispensa 3 [sez. 1.3 ] e Dispensa 4 [sez. 3.3 esercizi 5-8 ].

Lezioni 11-12: mercoledì 23 marzo 2016

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ì 30 marzo 2016

Il problema dell'ordinamento (1)

• Algoritmi semplici: insertion sort, selection sort, bubble sort: pseudocodici 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 9-10: venerdì 1 aprile 2016

• Presentazione Homework di Prova.
• Esercizio: funzione maxPrimo (esonero 2014) [ S4 ].
• Vettori in C. Vettori e puntatori. Esempio semplice: stampa di un vettore [ D6, sez. 1 ].
• Esercizio: funzione maxPrimo - versione iterativa (esonero 2014) [ S4 ].

• Esercizi consigliati: Dispensa 6 [sez. 1.3 ]

Lezioni 15-16: lunedì 4 aprile 2016

Il problema dell'ordinamento (2)

• Algoritmi efficienti: merge sort, pseudocodice e complessità

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’Insertion Sort. Le porzioni vengono combinate usando il meccanismo standard di fusione, con k che deve essere determinato. 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 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))

Lezioni 17-18: mercoledì 6 aprile 2016

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 11-12: venerdì 8 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 ]

Lezioni 19-20: lunedì 11 aprile 2016

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ì 13 aprile 2016

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

Esercitazioni 13-14: venerdì 15 aprile 2016

Esercizi su vettori e ricorsione in in vista dell'esonero.

• Virtuosismi I: baricentro con unica scansione ricorsiva [ S1 ]
• merge tra due vettori ordinati ricorsiva;
• Virtuosismi II: merge ricorsiva da Vero Programmatore C [ L2 ]
• non commutatitività degli operatori || e &&;
• impossibilità di scrivere una funzione myOr (o myAnd) con la stessa semantica;
• un grande classico intramontabile: crivello di Eratosten [ D6 ]

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

Lezioni 23-24: mercoledì 27 aprile 2016

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

Lezioni 25-26: lunedì 2 maggio 2016

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
• Discussione sull'esercizio n. 3 del primo esonero

Lezioni 27-28: mercoledì 4 maggio 2016

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

Esercitazioni 17-18: venerdì 6 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 ].

Lezioni 29-30: lunedì 9 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

Lezioni 31-32: mercoledì 11 maggio 2016

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

Esercitazioni 19-20: venerdì 13 maggio 2016

• 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 ]
• Rovesciamento di una lista: * funzione = reverseFun= quadratica, reverseFun lineare.
• deallocazione di una lista: funzione dealloc.

Lezioni 33-34: lunedì 16 maggio 2016

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

Lezioni 35-36: mercoledì 18 maggio 2016

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
• definizine di passeggiata, cammino, cammino semplice
• definizine di circuito e ciclo
• relazione di raggiungibilità e sue caratteristiche
• definizione di componente connessa
• definizione di sottografo, sottografo indotto, sottografo ricoprente

Esercitazioni 21-22: venerdì 20 maggio 2016

• Rovesciamento di una lista: funzione reverseRec che sposta i puntatori [ D8, sez. 3.4 ].
• Liste: problemi che eliminano elementi.
• 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.
• Definizione induttiva di alberi binari.
• alberi e liste doppiamente concatenate: il problema dell'equivalenza dei tipi (nome, struttura) e invarianti di tipo di dato.

• Esercizi consigliati: esercizi sulle liste [ D8, dopo sez. 3.5 ].

Lezioni 37-38: lunedì 23 maggio 2016

Grafi (2)

• rappresentazioni in memoria
  • liste di adiacenza
  • matrice di adiacenza
  • matrice di incidenza
  • lista di archi
  • confronto della complessita' 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: mercoledì 25 maggio 2016

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

Esercitazioni 23-24: venerdì 27 maggio 2016

• Funzioni base su alberi: visite, stampe [ D9, sez. 1.2 e 1.3 ].
• Il problema del bilanciamento: versioni ingenue ed efficienti [ D9, sez. 1.4 ].
• Il problema del sottoalbero [ D9, sez. 1.4 ].
• Esercizi sulle liste: sommaPrecedenti e sommaSuccessivi [ S3 ]

• Esercizi consigliati: esercizi su alberi [ D9, dopo sez. 1.6 ].

Lezioni 41-42: lunedì 30 maggio 2016

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ì 1 giugno 2016

Esercizi svolti in classe:

• Dato un albero binario, trovare il nodo che presenta la massima differenza fra i numeri di nodi del proprio sottoalbero sinistro e del proprio sottoalbero destro. Se vi sono più nodi con la massima differenza, restituirne uno fra quelli più vicini alla radice
• Dato un vettore di n elementi considerato come un albero binario gestito mediante la notazione posizionale, riempirlo con i primi n valori dell' albero di Kalkin-Wilf (contati nell'albero per livelli e, in ciascun livello, da sinistra a destra)
• 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.
• Dato un vettore contenente interi positivi e negativi, scrivere una funzione che sistemi tutti i valori negativi a sinistra di tutti i valori positivi

Lezioni 45-46: lunedì 6 giugno 2016

Discussione in classe sulla risoluzione di problemi.