Tags:
create new tag
view all tags

Diario delle lezioni degli Anni precedenti


A.A. 2015/2016

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.

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, Ω e Θ.
  • 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)

Esercitazioni 1-2: lunedý 7 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.

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

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

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.

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

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)

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 ]

Tutoraggio 3-4: venerdý 18 marzo 2016

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

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

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.

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

Vacanze di Pasqua

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 ]

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

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

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 ]

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.

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

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.

Venerdý 15 Aprile 2016 - Lezioni 21-22 Esercizi in preparazione dell'esonero

18-22 Aprile 2016 - Settimana di interruzione della didiattica

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

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

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

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

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

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

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

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

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.

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

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

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.

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

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

Lunedý 30 Maggio 2016 - Lezioni 41-42

  • Esercizi di riepilogo in vista del secondo esonero e dell'esame scritto

Lunedý 6 Giugno 2016 - Lezioni 43-44

  • Esercizi di riepilogo in vista del secondo esonero e dell'esame scritto

A.A. 2014/2015

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.

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, Ω e Θ.
  • Algebra della notazione asintotica
  • Esempi

Esercizi assegnati:

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

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)

Esercitazioni 1-2: mercoledý 11 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.

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)

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

Esercitazioni 3-4: mercoledý 18 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.

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

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

Esercitazioni 5-6: mercoledý 25 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.

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

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.

Esercitazioni 7-8: mercoledý 1 aprile 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.

2-7 Aprile 2015: Vacanze di Pasqua

Esercitazioni 9-10: mercoledý 8 aprile 2015

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

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.

Esercitazioni 11-12: lunedý 13 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.

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

Venerdý 17 Aprile 2015 - Lezioni 23-24

  • Esercizi in preparazione dell'esonero

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

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

Esercitazioni 13-14: mercoledý 29 aprile 2015

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

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

Esercitazioni 15-16: mercoledý 6 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.

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

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

Esercitazioni 17-18: mercoledý 13 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.

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

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

Esercitazioni 19-20: mercoledý 20 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.

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

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

Esercitazioni 21-22: mercoledý 27 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.

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

Esercitazioni 23-24: mercoledý 3 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.

Venerdý 5 Giugno 2015 - Lezioni 43-44

  • Esercizi di riepilogo in vista del secondo esonero e dell'esame scritto

A.A. 2013/2014

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

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.

Lunedý 10 Marzo 2014 - Lezioni 3-4

Notazione asintotica (1)

  • Definizione e significato degli insiemi O, Ω e Θ.
  • Algebra della notazione asintotica
  • Esempi
  • Valutazione della complessitÓ computazionale di un algoritmo
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)

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
Esercizi assegnati:
  • Calcolare il caso migliore e peggiore del costo computazionale degli algoritmi di Selection Sort, Insertion Sort e Bubble Sort (pseudocodice sulle dispense)

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.

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

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;

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)

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

Giovedý 20 marzo 2014 - Tutoraggio 2

  • Funzioni sui numeri naturali.
  • Funzione MCD: algoritmo ingenuo, mcdDellaMaestra, mcdEuclide.

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.

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

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.

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

Giovedý 27 marzo 2014 - Tutoraggio 3

  • Esercizi sui puntatori: operatori * e &. Aritmetica dei puntatori.
  • Passaggi di parametro per indirizzo.

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.

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

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)

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.

Giovedý 3 aprile 2014 - Tutoraggio 4

  • Esercizi sui vettori.

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.

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

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

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

Giovedý 10 aprile 2014 - Tutoraggio 5

  • Esercizi sulla ricorsione.

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.

Lezioni 23-24: lunedý 14 aprile 2014

  • Esercizi di preparazione all'esonero

Interruzione della didattica per le festivitÓ pasquali e per le prove in itinere

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

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

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 raffinamenti successivi: il gioco del Forza Quattro.

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
Esercizi assegnati:
  • dato un albero delle espressioni, stampare l'espressione corrispondente opportunamente parentesizzata

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

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

Lezioni 35-36: lunedý 19 maggio 2014

  • Dizionari (3)
    • Alberi Red and Black
    • teorema sull'altezza
    • rotazioni
    • algoritmo di inserimento
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

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

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.

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

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

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Ó

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

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

A.A. 2012/2013

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.

Lezioni 3-4: giovedý 7 marzo 2013

Notazione asintotica (1)

  • Definizione e significato degli insiemi O, Ω e Θ.
  • Algebra della notazione asintotica
  • Esempi
  • Valutazione della complessitÓ computazionale di un algoritmo
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

Esercitazioni 1-2: venerdý 8 marzo 2013

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

Esercizi e ulteriori approfondimenti:

  • vedi dispense Parte 1 e Parte 2 (Sez. 1-2).

Esercitazioni 3-4: lunedý 11 marzo 2013

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

Esercizi e ulteriori approfondimenti:

  • vedi dispense Parte 2 (Sez. 3-4).

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)

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.

Lezioni 7-8: venerdý 15 marzo 2013

Ricorsione

  • funzioni matematiche ricorsive
  • algoritmi ricorsivi
    • fattoriale
    • ricerca sequenziale
    • ricerca binaria
    • numeri di Fibonacci
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

Esercitazioni 5-6: lunedý 18 marzo 2013

Puntatori in C. Utilizzo dei puntatori per passaggi di parametro per indirizzo.
Funzione scambia senza variabile di appoggio: il problema di alias e side-effects.
Esercizi e ulteriori approfondimenti:

  • vedi dispense Parte 3.

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

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!"

Esercitazioni 7-8: venerdý 22 marzo 2013

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

Esercizi e ulteriori approfondimenti:

  • vedi dispense Parte 4 (Sez. 1-2).

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

VACANZE DI PASQUA

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

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Ó

Tutoraggio 5-6: giovedý 4 aprile 2013

  • Ricorsione, problemi ricorsivi presi dalla dispensa "iterare Ŕ umano, ricorrere Ŕ divino" .

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

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 Θ(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.

Esercitazioni 9-10: lunedý 8 aprile 2013

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

Esercizi e ulteriori approfondimenti:

  • vedi dispense Parte 6 (Sez. 1-2) e Correzione Primo Esonero.

Lezioni 17-18: giovedý 11 aprile 2013

  • Il problema dell'ordinamento (3)
    • algoritmi efficienti: quicksort (pseudocodice e complessitÓ nei casi migliore, peggiore e medio)

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.

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

Lezioni 19-20: venerdý 12 aprile 2013

  • Il problema dell'ordinamento (4)
    • algoritmi efficienti: heapsort (struttura dati heap, pseudocodice e complessitÓ)

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

Esercitazioni 11-12: lunedý 15 aprile 2013

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

Esercizi e ulteriori approfondimenti:

  • vedi dispense Parte 6 (Sez. 2) e Correzione Homework 2012 (partizioni) e Esercizi di Stile (merge).

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

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

Tutoraggio 9-10: giovedý 18 aprile 2013

  • Esercizi e domande in preparazione dell'esonero

Lezioni 23-24: venerdý 19 aprile 2013

  • Esercizi in preparazione dell'esonero

Settimana di interruzione della didattica e primo esonero

Esercitazioni 13-14: lunedý 29 aprile 2013

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

Esercizi e ulteriori approfondimenti:

  • vedi dispense Parte 7.

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

Tutoraggio 11-12: giovedý 2 maggio 2013

  • Esercizi sulle stringhe di caratteri, uso del carattere '\0'

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

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

Esercitazioni 15-16: lunedý 6 maggio 2013

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

Esercizi e ulteriori approfondimenti:

  • vedi dispense Parte 8.

Esercitazioni 17-18: giovedý 9 maggio 2013

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

Esercizi e ulteriori approfondimenti:

  • vedi dispense Parte 7 e 8.

Esercitazioni 13-14: giovedý 9 maggio 2013

  • Utilizzo di matrici di caratteri, utilizzo di input numerici passati in formato 'char'

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

Esercitazioni 19-20: lunedý 13 maggio 2013

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

Esercizi e ulteriori approfondimenti:

  • vedi dispense Parte 8 e Correzione Secondo Esonero.

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

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

Esercitazioni 21-22: lunedý 20 maggio 2013

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

Esercizi e ulteriori approfondimenti:

  • vedi dispense Parte 8 e 10.

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

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Ó

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

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Ó

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

Esercitazioni 23-24: giovedý 30 maggio 2013

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

Esercizi e ulteriori approfondimenti:

  • vedi dispense Parte 10.

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Ó

Esercitazioni 25-26: lunedý 3 giugno 2013

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

Esercizi e ulteriori approfondimenti:

  • vedi dispense Parte 8 e 10.

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

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

A.A. 2011/2012

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.

Lezioni 3-4: giovedý 8 marzo 2012

Notazione asintotica

  • Definizione e significato degli insiemi O, Ω e Θ.
  • Algebra della notazione asintotica
  • Esempi
  • valutazione della complessitÓ computazionale di un algoritmo
Esercizi assegnati:
  • Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione

Esercitazioni 1-2: venerdý 9 marzo 2012

Introduzione alla nozione di problema, esecutore, soluzione a una classe di problemi.
Procedure risolutive per problemi elementari.

Esercizi assegnati:

  • vedi dispense collegate agli argomenti della lezione. (Parte 1, Sez. 1-2)

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

Lezioni 7-8: giovedý 15 marzo 2012

Ricorsione

  • funzioni matematiche ricorsive
  • algoritmi ricorsivi
    • fattoriale
    • ricerca sequenziale
    • ricerca binaria
    • numeri di Fibonacci
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

Esercitazioni 3-4: venerdý 16 marzo 2012

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

Esercizi assegnati:

  • vedi dispense collegate agli argomenti della lezione. (Parte 1, Sez. 3)

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

Esercizi assegnati:

  • Risolvere le seguenti equazioni di ricorrenza:
    • T(n)=2 T(n/2)+Θ(n); T(1)=Θ(1)
    • T(n)=3 T(n/2)+Θ(n); T(1)=Θ(1)

Lezioni 11-12: giovedý 22 marzo 2012

Equazioni di ricorrenza (2)

  • metodo principale
    • esempio di utilizzo
    • dimostrazione per potenze esatte

Esercizi assegnati:

  • Risolvere le seguenti equazioni di ricorrenza:
    • T(n)=2 T(n/2)+Θ(n^3); T(1)=Θ(1)
    • T(n)=16 T(n/4)+Θ(n^2); T(1)=Θ(1)
    • T(n)=T(n-1)+Θ(n); T(1)=Θ(1)
    • T(n)=3 T(n/2)+Θ(n log n); T(1)=Θ(1)

Tutoraggio 1-2: giovedý 22 marzo 2012

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

Esercitazioni 5-6: venerdý 23 marzo 2012

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

Introduzione alla ricorsione.
Moltiplicazione Egiziana ricorsiva.

Esercizi assegnati:

  • vedi dispense collegate agli argomenti della lezione. (Parte 2 e Parte 3, sezione 1)

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

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.

Lezioni 15-16: giovedý 29 marzo 2012

  • Il problema dell'ordinamento (2)
    • algoritmi efficienti: merge sort (pseudocodice e complessitÓ)

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 Θ(n log n).
  • Nonostante il merge sort funzioni in tempo Θ(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.

Tutoraggio 3-4: giovedý 29 marzo 2012

Esercitazione sul passaggio dei parametri per riferimento e uso dei puntatori:
Funzione divRef(int m, int n, int* q, int* r) che restituisce quoziente e resto della divisione intera sui parametri
e sua applicazione all'algoritmo del massimo comun divisore della maestra.

Esercitazioni 7-8: venerdý 30 marzo 2012

Ancora sulla ricorsione: Induzione e Ricorsione.
Calcolo dei numeri di Fibonacci ricorsivo efficiente.
Problemi inerentemente ricorsivi: determinare se un numero n Ŕ semiperfetto.

Esercizi assegnati:

  • vedi dispense collegate agli argomenti della lezione (Parte 3, Ricorsione, sezioni 2,3).

Lezioni 17-18: lunedý 1 aprile 2012

  • Il problema dell'ordinamento (3)
    • algoritmi efficienti: quicksort (pseudocodice e complessitÓ nei casi migliore, peggiore e medio)

Esercizi assegnati:

  • Determinare la complessitÓ del Quicksort se il vettore dato in input contiene n elementi uguali e se Ŕ giÓ ordinato in senso decrescente.

Vacanze di Pasqua

Esercitazioni 9-10: giovedý 12 aprile 2012

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

Esercizi assegnati:

  • vedi dispense collegate agli argomenti della lezione (Parte 5, Vettori).

Tutoraggio 5-6: giovedý 12 aprile 2012

Esercitazione sui vettori:
1) Funzione che conta gli elementi comuni in due array ordinati.
2) Crivello di Eratostene.

Lezioni 19-20: venerdý 13 aprile 2012

  • Il problema dell'ordinamento (4)
    • algoritmi efficienti: heapsort (struttura dati heap, pseudocodice e complessitÓ)

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

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

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

Lezioni 23-24: giovedý 19 aprile 2012

  • Esercizi in preparazione dell'esonero

Tutoraggio 7-8: giovedý 19 aprile 2012

Esercitazione sui vettori 2:
1) Funzione che verifica se due vettori contengono gli stessi elementi.
1) Funzione che verifica se due vettori contengono gli stessi elementi con lo stesso numero di occorrenze.
1) Funzione che verifica se due vettori contengono gli stessi elementi con lo stesso ordine, interpretando il vettore in modo circolare.

Esercitazioni 11-12: venerdý 20 aprile 2012

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

Esercizi assegnati:

  • vedi dispense collegate agli argomenti della lezione: Parte 4 (Strutture Dati e Codifiche) e Parte 5 (Vettori in C).

Interruzione della didattica e primo esonero

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

Esercitazioni 13-14: venerdý 4 maggio 2012

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

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

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
Esercizi assegnati:
  • scrivere sia lo pseudocodice che il codice C delle funzioni Pop, Push e PilaPiena quando la pila sia implementata su vettore

Esercitazioni 15-16: venerdý 11 maggio 2012

Esempio di programmazione per raffinamenti successivi (e problemi su matrici): il Forza Quattro.

Esercizi assegnati:

  • vedi dispense collegate agli argomenti della lezione: Parte 6 (Stringhe e Vettori Bidimensionali).

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

Esercitazioni 17-18: giovedý 17 maggio 2012

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

Esercizi assegnati:

  • vedi dispense collegate agli argomenti della lezione: Parte 7 (Strutture Dati Dinamiche Lineari).

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

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

Esercitazioni 19-20: giovedý 24 maggio 2012

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

Esercizi assegnati:

  • vedi dispense collegate agli argomenti della lezione: Parte 7 (Strutture Dinamiche Lineari).

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

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Ó

Esercitazioni 21-22: giovedý 31 maggio 2012

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

Esercizi assegnati:

  • Cimentarsi con le versioni su liste degli algoritmi di ordinamento.
  • Valutare la differenza tra quicksort su lista semplice e su lista doppiamente concatenata.

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Ó

Esercizi assegnati:

  • Dimostrare che la relazione "u e v sono nella stessa componente" Ŕ di equivalenza.

Esercitazioni 23-24: lunedý 5 giugno 2012

Alberi Binari Generici.
Cenni ai passaggi di funzioni come parametri.
Funzioni profonditÓ, numero nodi, specchio.

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

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)

A.A. 2010/2011

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.

Lezioni 3-4: Venerdý 11 marzo 2011

Notazione asintotica

  • Definizione e significato degli insiemi O, Ω e Θ.
  • Esempi

Esercitazioni 1-2: Martedý 15 marzo 2011

  • Discussione del programma di esempio: 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

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: fattoriale_iterativo.c
  • Operatori logici: and, or e not
  • Vettori:
    • Allocazione statica
    • Indicizzazione e accesso agli elementi
    • Esempio: trovare l'elemento di valore massimo: find_max_array.c

Lezioni 5-6: Giovedý 17 marzo 2011

Festa del 150░ anniversario dell'UnitÓ d'Italia

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

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

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: 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: power_function.c

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

Lezioni 11-12: Venerdi' 25 marzo 2011

Soluzioni delle equazioni di ricorrenza (1)

  • metodo di sostituzione
  • metodo iterativo
  • metodo dell'albero
  • teorema principale (enunciato)

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

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: minimo_vettore_ricorsivo.txt

Esercitazioni 9-10: Venerdi' 1 aprile 2011

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)

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

Lezioni 17-18: Giovedi' 7 aprile 2011

Il problema dell'Ordinamento (3)

  • funzione di fusione
  • Ordinamento in tempo lineare: il countig sort

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

Tutoraggio 3: Martedý 12 aprile 2011

Esercitazioni 11-12: Mercoledi' 13 Aprile 2011

  • Esercizi:
    • Funzione ricorsiva per trasformare un decimale in binario: to_binary.txt
    • Funzione iterativa per trovare un VIP in una matrice: trova_vip.txt

Esercitazioni 13-14: Mercoledi' 27 Aprile 2011

  • Esercizi:
    • Svolgimento esercizi primo esonero
    • Funzione iterativa per trovare un VIP in una matrice in costo lineare: trova_vip_lineare.txt

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'

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

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 max_heapifty per ripristinare la proprietÓ max-heap di un sottoalbero
  • Linee guida per la costruzione delle funzioni build-heap e heapsort

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

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

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: int_list.c

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

Esercitazioni 17-18: Mercoledi' 11 Maggio 2011

  • Code:
  • Pile
    • funzioni enqueue e dequeue: pila.c
  • Esercizio: creazione di una copia di una lista data con elementi invertiti: inverti_lista.c

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

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'

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

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
Esercitazioni 19-20: Giovedi' 19 Maggio 2011

  • Esercizi:
  • Passaggio di parametri per riferimento
    • Funzione pop che modifica la lista passata come parametro: pop.c

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

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)

Esercitazioni 21-22: Mercoledi' 25 Maggio 2011

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

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

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

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

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

-- Tiziana Calamoneri - 2017-03-15

Comments

Topic revision: r1 - 2017-03-15 - TizianaCalamoneri





 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback