A.A. 2014/2015

Esercitazioni 1-2: venerdì 6 marzo 2015

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

Lezioni 3-4: lunedì 9 marzo 2015

Notazione asintotica (1)

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

Lezioni 5-6: mercoledì 11 Marzo 2015

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

Esercitazioni 3-4: venerdì 13 marzo 2015

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

Lezioni 7-8: lunedì 16 Marzo 2015

Ricorsione

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

Lezioni 9-10: mercoledì 18 Marzo 2015

Soluzioni delle equazioni di ricorrenza (2)

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

Esercitazioni 5-6: venerdì 20 marzo 2015

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

Lezioni 11-12: lunedì 23 Marzo 2015

Soluzioni delle equazioni di ricorrenza (3)

Esercizio svolto in classe:

• calcolare la soluzione della seguente equazione di ricorrenza con tutti e quattro i metodi, tenendo conto che per tutte il caso base è T(1)=&Theta(1):
  • T(n)=2T(n/2)+Θ(n)

Lezioni 13-14: mercoledì 25 Marzo 2015

Il problema dell'ordinamento (2)

• Algoritmi semplici: bubble sort, pseudocodice e complessità nel caso migliore e peggiore.
• Teorema sulla limitazione inferiore per la complessità di un algoritmo per confronti.
• Algoritmi efficienti: merge sort, pseudocodice e complessità

Esercitazioni 7-8: venerdì 27 marzo 2015

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

Lezioni 15-16: lunedì 30 Marzo 2015

Il problema dell'ordinamento (3)

• Algoritmi efficienti: quicksort, pseudocodice e complessità nei casi migliore, peggiore e medio (con dimostrazione)

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

Lezioni 17-18: mercoledì 1 Aprile 2015

Il problema dell'ordinamento (4)

• Algoritmi efficienti: heapsort (struttura dati heap, heapify, buildheap, e heapsort: pseudocodice e costo computazionale)

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

2-7 Aprile 2015: Vacanze di Pasqua

Lezioni 19-20: mercoledì 8 Aprile 2015

Il problema dell'ordinamento (5)

• Algoritmi di ordinamento lineari: counting sort, bucket sort (pseudocodice e 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ì 10 aprile 2015

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

Lezioni 21-22: lunedì 13 Aprile 2015

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

Lezioni 23-24: mercoledì 15 Aprile 2015

Svolgimento in classe di esercizi preparatori al primo esonero

Esercitazioni 11-12: venerdì 17 aprile 2015

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

20-24 Aprile 2015: Settimana di interruzione della didattica e Primo esonero

Esercitazioni 13-14: lunedì 27 aprile 2015

Introduzione alle matrici.
Programmazione top-down: gioco del forza4.

Lezioni 25-26: mercoledì 29 Aprile 2015

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

Lezioni 27-28: lunedì 4 Maggio 2015

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

Lezioni 29-30: mercoledì 6 Maggio 2015

Strutture dati fondamentali (4)

• alberi (2)
  • visite di alberi: in-ordine, pre-ordine e post-ordine
    • pseudocodice ricorsivo
    • costo computazionale tramite equazione di ricorrenza

Esercitazioni 15-16: venerdì 8 maggio 2015

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

Lezioni 31-32: lunedì 11 maggio 2015

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ì 13 maggio 2015

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'

Esercitazioni 17-18: venerdì 15 maggio 2015

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

Lezioni 35-36: lunedì 18 maggio 2015

Dizionari (3)

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

Lezioni 37-38: mercoledì 20 maggio 2015

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

Esercitazioni 19-20: venerdì 22 maggio 2015

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

Lezioni 39-40: lunedì 25 maggio 2015

Grafi (3)

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

Lezioni 41-42: mercoledì 27 maggio 2015

Grafi (4)

• Algoritmo di Dijkstra
  • 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

Esercitazioni 21-22: venerdì 29 maggio 2015

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

Lezioni 43-44: mercoledì 3 giugno 2015

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
• Dato un vettore contenente interi positivi e negativi, scrivere una funzione che sistemi tutti i valori negativi a sinistra di tutti i valori positivi

Esercitazioni 23-24: venerdì 5 giugno 2015

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

-- GiancarloBongiovanni - 05 Apr 2016