Tags:
create new tag
view all tags

Diario delle lezioni

A.A. 2017/2018

Venerdý 23 Febbraio 2018 - Lezioni 1-2

Introduzione (1)

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

Lunedý 26 Febbraio 2018

Lezioni sospese per le condizioni meteo

Esercitazioni 1-2: mercoledý 28 febbraio 2018

  • Problemi, classi di Problemi, Soluzioni [ L1, sezioni 1 e 2 ]
  • TinyC. Codifica in TinyC del programma che calcola la somma iterando +1 [ D1, sezione 2 ]
  • Indagini su un programma iterativo [ L1, sez. 2.1 ]:
    • Precondizioni, Postcondizioni, invarianti di ciclo.
    • Terminazione di un ciclo: funzione di terminazione.
  • Esempi:
    • funzione che calcola la moltiplicazione. Uso della funzione somma nel calcolo del prodotto [ D1, sez. 3 ].
    • funzione che calcola il predecessore. Specifica come contratto.

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

Venerdý 2 Marzo 2018 - Lezioni 3-4

Introduzione (2)

  • Esempio di calcolo del costo di un algoritmo con misura di costo uniforme e logaritmico.
Notazione asintotica (1)
  • Definizione e significato degli insiemi O, Ω e Θ
  • Metodo del limite
  • Algebra della notazione asintotica
  • Esempi
  • Pseudocodice

Esercizi assegnati:

  • Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione
  • Calcolare l'ordine asintotico stretto di alcune funzioni assegnate.

Lunedý 5 Marzo 2018

Lezioni sospese per le elezioni

Mercoledý 7 Marzo 2018

Lezioni sospese per le Olimpiadi di Matematica (aule occupate)

Venerdý 9 Marzo 2018 - Lezioni 5-6

Notazione asintotica (2)

  • Valutazione del costo computazionale di un algoritmo
  • Un primo esempio
  • 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

Il problema della ricerca (1)

  • ricerca sequenziale e suo costo computazionale nel caso migliore e peggiore

Esercizi assegnati:

  • Calcolare l'andamento asintotico di alcune funzioni ed alcune sommatorie
  • Calcolare il costo computazionale del Selection, dell'Insertion Sort e del Bubble Sort (pseudocodice sulle dispense)

Lunedý 12 Marzo 2018 - Lezioni 7-8

Il problema della ricerca (2)

  • ricerca dicotomica e suo costo computazionale nel caso migiore e peggiore

Ricorsione

  • funzioni matematiche ricorsive;
  • ricerca sequenziale e binaria: pseudocodice 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 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) (dove x%y indica il resto della divisione intera tra x e y)

Esercitazioni 3-4: mercoledý 14 marzo 2018

  • Funzione compareTo che confronta due numeri naturali. Osservazioni sulla complessitÓ dei programmi TinyC.
  • Progetto di funzioni a partire dalle specifiche logiche [ L1, sez. 2.3 ].
    • Esempio: divisione intera.
  • Introduzione alla pila di sistema, variabili locali, globali [ D1, sez. 3 ].
  • Uso di passaggi per riferimento per passare pi¨ risultati: funzione int divRef(int, int, int*, int*).
  • Utilizzo della funzione divRef nell'algoritmo mcdMaestra [ D1, sez. 4 ].
  • Valutazione dei parametri: impossibilitÓ di scrivere una funzione myAnd equivalente a &&.

  • Esercizi consigliati: Dispensa L1, sez. 2.5, esercizi da 2 a 8.
  • Elucubrazioni: InutilitÓ dell' if in TinyC. Altri esercizi in Disp. D1, sez. 1.2.

Venerdý 16 Marzo 2018 - Lezioni 9-10 Soluzioni delle equazioni di ricorrenza (1)

  • 4 metodi risolutivi:
    • metodo iterativo;
    • metodo di sostituzione;

Esercizi assegnati:

  • Calcolare la soluzione di alcune equazioni di ricorrenza

Lunedý 19 Marzo 2018 - Lezioni 11-12 Soluzioni delle equazioni di ricorrenza (2)

  • 4 metodi risolutivi:
    • metodo dell'albero;
    • metodo principale: enunciato del teorema senza dimostrazione

Esercizi assegnati:

  • Calcolare la soluzione di alcune equazioni di ricorrenza

Esercitazioni 5-6: mercoledý 21 marzo 2018

  • Ancora sui passaggi per riferimento: funzione scambia(int*,int*), ap(int*,int*,int,int) (assegnamento parallelo Ó la Python) [ D2, sez. 2 ].
  • I problemi di alias: funzione scambia(int*,int*) senza variabile di appoggio [ D2, sez. 3 ].
  • Induzione e Ricorsione: definizione induttiva di + e funzione sommaRec(int, int) [ D3, sez. 1.1 ].
  • Esercizio: predecessore ricorsivo in TinyReC. Riflessioni sulla completezza computazioneale di TinyReC.
  • Fattoriale: definizione induttiva e programma ricorsivo. Considerazioni sulla sua complessitÓ in TinyC.
  • Ricorsione: funzione di Fibonacci. Efficienza e albero delle chiamate generato.
  • Funzioni: stack di attivazione delle chiamate [ D2, sez. 3 ].
  • Fibonacci Iterativo.

  • Esercizi consigliati: Dispensa D2 [sez. 4 ]
  • Esercizi consigliati: Dispensa D3 [sez. 1.3 ]

Venerdý 23 Marzo 2018 - Lezioni 13-14 Soluzioni delle equazioni di ricorrenza (3)

Esercizi riepilogativi sulle equazioni di ricorrenza

Esercizi assegnati:

  • Calcolare la soluzione delle equazioni di ricorrenza giÓ assegnate usando tutti e 4 i metodi

Lunedý 26 Marzo 2018 - Lezioni 15-16

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).
  • Determinare l'albero delle decisioni del Selection Sort.

Esercitazioni 7-8: mercoledý 28 marzo 2018

  • Iterazione e ricorsione: Fibonacci iterativo efficiente. Trasformazione sistematica di un ciclo in una funzione ricorsiva.
  • Dimostrazioni di correttezza per programmi ricorsivi. [ D3, sez. 2 ]
  • Problemi con soluzione inerentemente ricorsiva: il problema della Torre di Hanoi [ D3, sez. 3 ]
  • Soluzione di un esonero sul tema: il problema del massimo fattore primo [ S4 ]
  • Un aiutino sull'Homework, esercizio 3: il problema delle partizioni [ S3, sez. 1 ]

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

Da Giovedý 29 Marzo a Martedý 3 Aprile 2018 inclusi

Vacanze di Pasqua

Mercoledý 4 Aprile 2018 - Lezioni 17-18

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, costo computazionale nei casi migliore e peggiore, idea di caso medio)

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

Venerdý 6 Aprile 2018 - Lezioni 19-20

Il problema dell'ordinamento (3)

  • algoritmi efficienti: quick sort (pseudocodice e costo 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.

Esercitazioni 9-10: lunedý 9 aprile 2018

  • Introduzione ai vettori in C: definizione e allocazione [ D4, sez. 1 ]. Passaggio di parametri vettori. Vettori e puntatori [ D4, sez. 1.1 ].
  • Un primo programma sui vettori: stampa di un vettore, iterativa e ricorsiva [ D4, sez. 1.1 ].
  • Un esempio di programma con asserzioni logiche: minimo di un vettore [ D4, sez. 2.1 ]. Utilizzo nell'algoritmo di Selection Sort.
  • Esercizio: il Problema del baricentro [ S1 ].

  • Esercizi consigliati: Dispensa 4 [sez. 1.3 e 2.6 ],
  • Lettura: due grandi classici: crivello di Eratostene [ D4, sez. 2.4 ] e coefficienti binomiali [ D4, sez. 2.5 ].

Esercitazioni 11-12: mercoledý 11 aprile 2018

  • Esercizi su vettori e ricorsione in vista dell'esonero:
    • Virtuosismi 1: funzione baricentroRec che fa un'unica scansione del vettore [ S1 ].
    • Il problema della verifica della combinazione del mastermind [ S3, sez. 2 ]: uso di vettori locali a una funzione.
    • Virtuosismi 2: funzione mergeRecVPC: merge ricorsiva da Veri Programmatori C [ L2 ]. Errata corrige alla Funzione in Fig.6 pag. 8.
    • Coefficienti binomiali con generazione delle righe del triangolo di Tartaglia [ D4, sez. 2.5 ].

  • Esercizi consigliati: Di tutto un po', su vettori e ricorsione, dispensa D3 e D4.

Venerdý 13 Aprile 2018 - Lezioni 21-22

  • Esercizi in vista dell'esonero

Esercitazioni 13-14: lunedý 23 aprile 2018

  • Introduzione alla memoria allocata dinamicamente: stack e heap.
  • Funzioni di libreria malloc(int) e calloc(int, int).
  • Il tipo void *.
  • Differenza tra vettori a lunghezza variabile e vettori dinamici.
  • Introduzione ai record: definizioni di struct. [ D6, sez. 1 ]
  • Vettori bidimensionali: allocazione statica [ D5, sez. 2 ].
  • Allocazione di una matrice dinamica [ D5, sez. 3 ].

  • Esercizi consigliati: nessuno.

Venerdý 27 Aprile 2018 - Lezioni 23-24

Il problema dell'ordinamento (4)

  • algoritmi efficienti: heapsort (costo computazionale di Heapify, BuildHeap: pseudocodice e costo, Heapsort: pseudocodice e costo)
  • algoritmi lineari: counting sort (versione semplificata e versione completa) e bucket sort (idea)

  • Strutture dati fondamentali (1)
    • strutture dati ed insiemi dinamici
    • confronto tra vettore qualunque e vettore ordinato

Mercoledý 2 Maggio 2018 - Lezioni 25-26

  • Strutture dati fondamentali (2)
    • introduzione alle liste: ricerca e inserimento in testa
    • cancellazione nelle liste, liste doppiamente puntate
    • code con prioritÓ
    • la struttura dati coda
    • le operazioni enqueue e dequeue

Venerdý 4 Maggio 2018 - Lezioni 27-28

  • Strutture dati fondamentali (3)
    • pila
    • le operazioni Push e Pop
    • Esercizio: simulazione di una coda tramite due pile
    • 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:

  • 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

Lunedý 7 Maggio 2018 - Lezioni 29-30

  • Strutture dati fondamentali (4)
    • alberi (2)
      • visite di alberi: in-ordine, pre-ordine e post-ordine
        • pseudocodice ricorsivo
        • costo computazionale tramite equazione di ricorrenza e metodo di sostituzione (sol. lasciata per esercizio)
        • esercizi che si risolvono utilizzando le visite
        • esercizi che si risolvono usando alberi, pile e code

Esercitazioni 15-16: mercoledý 9 maggio 2018

  • Tipo di dato sequenza e sua definizione induttiva.
  • Rappresentazione in C delle sequenze: uso di struct 'ricorsive' [dispensa D6, sez. 3 ].
  • Costruttori e distruttori del tipo sequenza.
  • Prime funzioni C su liste: length, sumL [dispensa D6, sez. 3.1 ].
  • Attenzione alla memoria raggiungibile: side effects. L'esempio di twiceL [dispensa D6, sez. 3.2 ].

  • Esercizi consigliati: i pi¨ semplici di quelli alla fine della dispensa D6 .

Venerdý 11 Maggio 2018 - Lezioni 31-32

  • Strutture dati fondamentali (5)
    • alberi (3)
      • visite di alberi: in-ordine, pre-ordine e post-ordine
        • esercizio: visita in preordine sul vettore dei padri
  • 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) (1):
      • definizione e proprietÓ dell' "ordinamento orizzontale"
      • algoritmo per il massimo e minimo

Esercizi assegnati:

  • Scrivere lo pseudocodice degli algoritmi per la ricerca del massimo e del minimo in un ABR

Lunedý 14 Maggio 2018 - Lezioni 33-34*

  • Dizionari (2)
    • Alberi binari di ricerca (ABR) (2):
      • 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:

  • Scrivere lo pseudocodice degli algoritmi per la ricerca del predecessore e del successore in un ABR
  • Dato due ABR 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 17-18: mercoledý 16 maggio 2018

  • Inserzione di elementi in coda [dispensa D6, sez. 3.3 ]:
    • specifica con equazioni ricorsive,
    • versione iterativa addLastIt,
    • ricorsiva addLastRec,
    • con generazione di una nuova lista addLastFun .
  • Concatenazione di liste [dispensa D6, sez. 3.4 ]:
    • specifica con equazioni ricorsive,
    • versioni 'mista' append,
    • ricorsiva appendRec,
    • con generazione nuove liste appendFun .
  • Rovesciamento di liste [dispensa D6, sez. 3.5 ]:
    • specifica con equazioni ricorsive,
    • versione 'fun' inefficiente reverseFun,
    • iterativa reverseIt,
    • versione ricorsiva efficiente reverseFunEff .
  • Rovesciamento di Liste in place: versione ricorsiva reverseRec [dispensa D6, sez. 3.5 ].
  • Eliminazione di elementi: removeFun e removeRec [dispensa D6, sez. 3.6 ].
  • Il problema della deallocazione di memoria dinamica: free() [dispensa D6, sez. 2.1 ].

  • Esercizi consigliati: reverse in place iterativa (virtuosismo) e altri esercizi tra di quelli alla fine della dispensa D6 .

Venerdý 18 Maggio 2018 - Lezioni 35-36*

  • Dizionari (3)
    • Alberi binari di ricerca (ABR) - segue:
      • alberi bilanciati: alberi rosso-neri
      • dimostrazione che gli alberi rosso-neri hanno altezza logaritmica
      • rotazioni
      • cenno all'operazione di inserimento

Esercizi assegnati:

  • Costruire un ABR inserendo successivamente le chiavi 41, 38, 31, 12, 19, 8.

Lunedý 21 Maggio 2018 - Lezioni 37-38*

  • Grafi (1)
    • Definizione e alcune 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

A.A. 2016/2017

Mercoledý 1 Marzo 2017 - 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ý 3 Marzo 2017 - Lezioni 3-4

Notazione asintotica (1)

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

Esercizi assegnati:

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

Esercitazioni 1-2: lunedý 6 marzo 2017

  • TinyC. Codifica in TinyC del programma che calcola la somma iterando +1 [ D2, sezione 2 ]
  • Indagini su un programma iterativo [ D1, sez. 2.1 ]:
    • Precondizioni, Postcondizioni, invarianti di ciclo.
    • Terminazione di un ciclo: funzione di terminazione.
  • Esempi:
    • funzione che calcola la moltiplicazione. Uso della funzione somma nel calcolo del prodotto [ D2, sez. 3 ].
    • funzione che calcola il predecessore. Specifica come contratto.
    • somma che usa predecessore. Osservazioni sulla complessitÓ dei programmi TinyC.
    • Esempio: fattoriale: discussione della sua complessitÓ in TinyC e in C.

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

Esercitazioni 3-4: mercoledý 8 marzo 2017

  • Progetto di funzioni a partire dalle specifiche logiche [ D1, sez. 2.3 ].
    • Esempio: divisione intera.
  • Introduzione alla pila di sistema, variabili locali, globali [ D2, sez. 3 ].
  • Uso di passaggi per riferimento per passare pi¨ risultati: funzione int divRef(int, int, int*, int*).
  • Utilizzo della funzione divRef nell'algoritmo mcdMaestra [ D2, sez. 4 ].
  • Valutazione dei parametri: impossibilitÓ di scrivere una funzione myAnd equivalente a &&.

  • Esercizi consigliati: Dispensa D1, sez. 2.5, esercizi da 2 a 8.
  • Elucubrazioni: InutilitÓ dell' if in TinyC. Altri esercizi in Disp. D2, sez. 1.2.

Venerdý 10 Marzo 2017 - 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 funzioni ed alcune sommatorie
  • Calcolare il costo computazionale del Selection, dell'Insertion Sort e del Bubble Sort (pseudocodice sulle dispense)

Lunedý 11 Marzo 2017 - Lezioni 7-8

Ricorsione

  • funzioni matematiche ricorsive;
  • ricerca sequenziale e binaria: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;
  • altri esempi di problemi risolti con algoritmi ricorsivi.

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ý 15 marzo 2017

  • Ancora sui passaggi per riferimento: funzione scambia(int*,int*), ap(int*,int*,int,int) (assegnamento parallelo Ó la Python) [ D3, sez. 2 ].
  • I problemi di alias: funzione scambia(int*,int*) senza variabile di appoggio [ D3, sez. 3 ].
  • Induzione e Ricorsione: definizione induttiva di + e funzione sommaRec(int, int) [ D4, sez. 1.1 ].
  • Esercizio: predecessore ricorsivo in TinyReC. Riflessioni sulla completezza computazioneale di TinyReC.
  • Ricorsione: funzione di Fibonacci. Efficienza e albero delle chiamate generato.
  • Funzioni: stack di attivazione delle chiamate [ D2, sez. 3 ].
  • Fibonacci Iterativo.

  • Esercizi consigliati: Dispensa 3 [sez. 4 ]
  • Esercizi consigliati: Dispensa 4 [sez. 1.3 ]

Venerdý 17 Marzo 2017 - Lezioni 9-10

Soluzioni delle equazioni di ricorrenza (1)

  • carrellata sui 4 metodi:
    • metodo iterativo;
    • metodo di sostituzione;
    • metodo dell'albero;
    • metodo principale: enunciato del teorema senza dimostrazione

Esercizi assegnati:

  • Calcolare la soluzione di alcune equazioni di ricorrenza

Lunedý 20 Marzo 2017 - Lezioni 11-12

Soluzioni delle equazioni di ricorrenza (2)

  • esempi di soluzione di equazioni di ricorrenza tramite i quattro metodi

Esercizi assegnati:

  • Calcolare la soluzione delle seguenti equazioni di ricorrenza con i quattro metodi studiati, ove 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)=2T(n/2)+Θ(n^3)
    • T(n)=T(n-1)+Θ(n)

Esercitazioni 7-8: mercoledý 22 marzo 2017

  • Fibonacci ricorsivo efficiente [ D4, sez. 2 ].
  • Dimostrazioni induttive di correttezza per funzione ricorsive [ D4, sez. 2 ].
  • Trasformazione sistematica di programmi iterativi in ricorsivi [ D4, sez. 2 ].
  • Esempi di problemi con soluzioni inerentemente ricorsive:
    • Funzione maxPrimo (Esonero 2014) [ S4 ].
    • Calcolo del numero delle partizioni (Homework 1, 2012) [ S3, sez. 1 ]
  • Introduzione ai vettori. Vettori e puntatori. Stampa iterativa di un vettore. [ D6, sez. 1 ]
  • Esempio di sviluppo di programmi su vettori con asserzioni logiche: minimo di un vettore. [ D6, sez. 2.1 ]

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

Venerdý 24 Marzo 2017 - 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.
  • Determinare l'albero delle decisioni del Selection Sort e dell'Insertion Sort
  • 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ý 27 Marzo 2017 - 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, pseudocodice della funzione Partiziona)

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

Esercitazioni 9-10: mercoledý 29 marzo 2017

  • Esercizi sui vettori: il problema del baricentro [Esonero 2012, S1 ].
  • Virtuosismi: funzione baricentroRec che calcola il baricentro con un'unica scansione ricorsiva.
  • Generazione delle combinazioni di n oggetti presi k a k . [Esonero 2016, S4 ].
  • Virtuosismi: versione ricorsiva che genera le combinazioni.

  • Letture consigliate: Due grandi classici: crivello di Eratostene e Coefficienti Binomiali [ D6 sez. 2.4 e 2.5 ]
  • Esercizi consigliati: Dispensa 6 [sez. 1.3 e 2.6 ]

Venerdý 31 Marzo 2017 - Lezioni 17-18 Il problema dell'ordinamento (3)

  • algoritmi efficienti: quick sort (costo computazionale nel caso peggiore, migliore e 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.

Lunedý 3 Aprile 2017 - Lezioni 19-20 Il problema dell'ordinamento (4)

  • algoritmi efficienti: heapsort (buildheap, e heapsort: pseudocodice e costo computazionale)
  • algoritmi lineari: counting sort (versione semplificata e 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 11-12: mercoledý 5 aprile 2017

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

  • Il problema 3 dell'Homework di Prova: conteggio delle k uple ordinate di prodotto n .
  • Il problema della prossima permutazione [ dispensa A1 ].
  • Generazione ricorsiva delle permutazioni (o anagrammi) [ D4 sez. 3.2 ].
  • merge tra due vettori ordinati ricorsiva.
  • Virtuosismi: merge ricorsiva da Vero Programmatore C [ Esercizi di stile, L2 sez. 1 ]. Errata corrige alla Funzione in Fig.6 pag. 8.

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

Venerdý 7 Aprile 2017 - Lezioni 21-22 Esercizi in preparazione dell'esonero

Lunedý 12 aprile 2017 - Primo Esonero

Esercitazioni 13-14: mercoledý 12 aprile 2017

  • Breve discussione soluzioni esonero ed errori tipici [dispensa A2 ].
  • Introduzione alla memoria allocata dinamicamente: stack e heap.
  • Funzioni di libreria malloc(int) e calloc(int, int).
  • Differenza tra vettori a lunghezza variabile e vettori dinamici.
  • Vettori bidimensionali: allocazione statica [dispensa D7, sez. 2 ].
  • Allocazione di una matrice dinamica [dispensa D7, sez. 3 ].
  • Esempio: allocazione e costruzione del Triangolo di Tartaglia.

  • Esercizi consigliati: nessuno.

Venerdý 21 Aprile 2017 - Lezioni 23-24 Correzione degli esercizi d'esonero e consegna dei compiti

Esercitazioni 15-16: mercoledý 26 aprile 2017

  • Breve discussione esercizi Homework 1.
  • Tipo di dato sequenza e sua definizione induttiva.
  • Rappresentazione in C delle sequenze: costruttore di tipo struct [dispensa D8, sez. 1 ].
  • Costruttori e distruttori del tipo sequenza.
  • Prime funzioni C su liste: length, sumL [dispensa D8, sez. 3.1 ].

  • Esercizi consigliati: nessuno.

Venerdý 28 Aprile 2017 - Lezioni 25-26

  • Strutture dati fondamentali (1)
    • strutture dati ed insiemi dinamici
    • confronto tra vettore qualunque e vettore ordinato
    • introduzione alle liste: ricerca e inserimento in testa
    • cancellazione nelle liste, liste doppiamente puntate e liste circolari

Esercitazioni 17-18: mercoledý 3 maggio 2017

  • Funzioni che modificano liste: twiceL. Trasparenza referenziale: versioni che generano nuove liste e versioni in place [dispensa D8, sez. 3.2 ].
  • Inserimento e concatenazione di liste. Side effects indesiderati. Versioni ricorsive, iterativa e funzionali [dispensa D8, sez. 3.3 e 3.4 ].
  • Il problema del rovesciamento. Versione ricorsiva inefficiente quadratica, iterativa e versione efficiente con parametro ausiliario.
  • Rovesciamento ricorsivo in place [dispensa D8, sez. 3.5 ].

  • Esercizi consigliati: rovesciamento iterativo in place. Esercizi alla fine di dispensa D8.

Venerdý 5 Maggio 2017 - 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

Lunedý 8 Maggio 2017 - Lezioni 29-30

  • 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

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

Esercitazioni 19-20: mercoledý 10 maggio 2017

  • Breve discussione delle liste alternative da usare nell'Homework 2. Liste con pointer all'ultimo elemento e liste doppiamente concatenate.
  • Funzioni che rimuovono elementi dalle liste: remove. Versioni funzionali e versioni in place. La funzione di libreria free(void * ) [dispensa D8 , sez. 3.6 ]
  • Differenza tra liste. Cautela nell'uso di chiamate annidate di funzioni di tipo Fun.
  • Alcuni esercizi di compiti passati: immersa, mcdDaLista [dispensa S6 ].

  • Esercizi consigliati: remove iterativa in place. Esercizi alla fine di dispensa D8.

Venerdý 12 Maggio 2017 - Lezioni 31-32

  • 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

Lunedý 15 Maggio 2017 - 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):
      • definizione e proprietÓ dell' "ordinamento orizzontale"

Esercitazioni 21-22: mercoledý 17 maggio 2017

  • Definizione induttiva di albero binario.
  • Costruttori e distruttori di alberi binari: makeTree, emptyTree, isEmptyTree.
  • Semplici funzioni definite per ricorsione su alberi binari: numero nodi, peso, altezza.
  • Rivisitazioni delle visite: stampa (preorder) di un albero a parentesi nella forma r(L,R), stampa (inorder) indentata.
  • Funzione makeTreeFromArray che ricostruisce un albero binario partendo da una visita preorder e da una inorder.

Venerdý 19 Maggio 2017 - Lezioni 35-36

  • Dizionari (2) * Alberi binari di ricerca (ABR) - segue: * 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:

  • Scrivere lo pseudocodice degli algoritmi per la ricerca del predecessore e del successore in un ABR
  • Dato due ABR 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.

Lunedý 22 Maggio 2017 - Lezioni 37-38

  • Dizionari (3) * Alberi binari di ricerca (ABR) - segue:
      • alberi bilanciati: alberi rosso-neri
      • dimostrazione che gli alberi rosso-neri hanno altezza logaritmica
  • Grafi (1)
    • Definizioni e semplici proprietÓ
Esercizi assegnati:
  • Costruire un ABR inserendo successivamente le chiavi 41, 38, 31, 12, 19, 8.

Mercoledý 24 Maggio 2017 - Lezioni 39-40

  • Grafi (2)
    • 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
    • Visita in ampiezza: proprietÓ dell'albero di visita in ampiezza, pseudocodice
    • Esempi di uso di visita in ampiezza: cammini pi¨ corti

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

Esercitazioni 23-24: venerdý 26 maggio 2017

  • Ancora sugli alberi: funzioni eqTree e subTree per uguaglianza e relazione di sottoalbero.
  • Il problema del bilanciamento: versioni ingenue (quadratiche) ed efficienti (lineari) [dispensa D9 ].
  • Presentazione terzo Homework.
  • Esercizi da compiti precedenti:
    • creare una lista con i nodi del livello k: list levelK(binTree B, int k).
    • restituire una lista con i nodi nel cammino dalla radice a un nodo: list pathToX(binTree B, int x) [dispensa S6 ].

Lunedý 29 Maggio 2017 - Lezioni 41-42

  • Grafi (3)
    • Visita in ampiezza: costo computazionale in funzione della struttura dati usata
    • Visita in profonditÓ: pseudocodice, costo computazionale in funzione della struttura dati usata, proprietÓ dell'albero di visita in profonditÓ
    • Esercizi su grafi: cammini pi¨ corti e calcolo delle componenti connesse
    • Grafi euleriani e loro caratterizzazione

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 25-26: mercoledý 31 maggio 2017

  • Discussione terzo Homework.
  • Esercizi da compiti precedenti:
    • relazione prefisso tra alberi: int prefixTree(binTreeList L);
    • numeri naturali implementati come liste;
    • divisione di una lista [dispensa S6 ].

Lunedý 5 Giugno 2017 - Lezioni 43-44

  • Grafi (3)
    • Grafi bipartiti e loro caratterizzazione
    • Accoppiamenti massimi e massimali
    • Colorazioni minime e minimali

Mercoledý 7 Giugno 2017 - Lezioni 45-46

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

Anni Precedenti

alt="joomla visitor" >

Topic attachments
I Attachment History Action Size Date Who Comment
C source code filec coda.c r1 manage 1.5 K 2011-05-12 - 14:07 SimoneSilvestri  
Texttxt elemento_comune_vettori.txt r1 manage 0.4 K 2011-04-01 - 13:01 SimoneSilvestri  
C source code filec elimina_occorrenze.c r1 manage 2.0 K 2011-05-19 - 10:51 SimoneSilvestri  
C source code filec esempio1.c r1 manage 0.2 K 2011-03-15 - 10:25 SimoneSilvestri  
C source code filec fattoriale_iterativo.c r1 manage 0.3 K 2011-03-18 - 07:26 SimoneSilvestri Fattoriale iteraivo
C source code filec find_max_array.c r1 manage 0.6 K 2011-03-18 - 07:30 SimoneSilvestri  
C source code filec inserimento_ordinato.c r1 manage 1.0 K 2011-05-26 - 08:09 SimoneSilvestri  
C source code filec int_list.c r1 manage 0.8 K 2011-05-10 - 09:16 SimoneSilvestri  
C source code filec inverti_list.c r1 manage 1.5 K 2011-05-19 - 10:50 SimoneSilvestri  
C source code filec inverti_lista.c r1 manage 1.7 K 2011-05-12 - 14:09 SimoneSilvestri  
C source code filec liste_funzioni_ricorsive.c r1 manage 2.5 K 2011-05-26 - 08:09 SimoneSilvestri  
Texttxt minimo_vettore_ricorsivo.txt r1 manage 0.2 K 2011-03-31 - 11:05 SimoneSilvestri  
Texttxt occorrenze_vettore_ricorsivo.txt r1 manage 0.3 K 2011-04-01 - 13:00 SimoneSilvestri  
Texttxt palidromo_ricorsivo.txt r1 manage 0.4 K 2011-04-01 - 13:01 SimoneSilvestri  
C source code filec pila.c r1 manage 1.2 K 2011-05-12 - 14:07 SimoneSilvestri  
C source code filec pop.c r1 manage 0.2 K 2011-05-19 - 10:50 SimoneSilvestri  
C source code filec power_function.c r1 manage 0.4 K 2011-03-24 - 08:48 SimoneSilvestri  
C source code filec sum_positive_matrix.c r1 manage 0.7 K 2011-03-24 - 08:42 SimoneSilvestri  
Texttxt to_binary.txt r1 manage 0.2 K 2011-04-15 - 08:55 SimoneSilvestri  
Texttxt trova_vip.txt r1 manage 1.1 K 2011-04-15 - 08:55 SimoneSilvestri  
Texttxt trova_vip_lineare.txt r1 manage 0.8 K 2011-04-28 - 08:27 SimoneSilvestri  
Edit | Attach | Watch | Print version | History: r219 < r218 < r217 < r216 < r215 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r219 - 2018-05-22 - 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