Diario delle lezioni degli Anni precedenti

A.A. 2018/2019

Lunedì 25 Febbraio 2019 - Lezioni 1-2

Introduzione sull'importanza della valutazione dei corsi di studio (a cura del presidente di CAD)

Introduzione (1)

  • Informazioni sul corso.
  • Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale.

Mercoledì 27 febbraio 2019 - Esercitazioni 1-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.
    • funzione che calcola il minore o uguale.

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

Venerdì 1 Marzo 2019 - Lezioni 3-4

Introduzione (2)

  • Modello RAM; misura di costo uniforme e logaritmico.

Notazione asintotica (1)

  • Definizione e significato degli insiemi O, Ω e Θ
  • Metodo del limite
  • Algebra della notazione asintotica
  • Esempi

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ì 4 Marzo 2019 - Lezioni 5-6

Notazione asintotica (2)

  • Pseudocodice
  • 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
  • ricerca dicotomica e suo costo computazionale nel caso migiore e peggiore

Esercizi assegnati:

  • Calcolare il costo computazionale del Selection, dell'Insertion Sort e del Bubble Sort (pseudocodice sulle dispense)

Mercoledì 6 Marzo 2019 - Esercitazioni 3-4

  • Usando l'esempio del predecessore, revisione delle asserzioni logiche: precondizioni, postcondizioni, invarianti, funzioni di terminazione.
  • Progetto di funzioni a partire dalle specifiche logiche [ L1, sez. 2.3 ].
    • Esempio: divisione intera.
  • 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 ].

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

Venerdì 8 Marzo 2019 Lezioni sospese per le Olimpiadi di Matematica (aule occupate)

Lunedì 11 marzo 2019 - Esercitazioni 5-6

  • Ancora sui passaggi per riferimento: funzione scambia(int*,int*)
  • Passaggio di parametri: call-by-value: impossibilità di scrivere una funzione myAnd equivalente all'operatore && predefinito.
  • Call-by-value, funzione 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.
  • Ricorsione: funzione di Fibonacci. Efficienza e albero delle chiamate generato.

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

Mercoledì 13 Marzo 2019 - Lezioni 7-8

  • Calcolare l'andamento asintotico di alcune funzioni ed alcune sommatorie
  • Esempio pratico di funzionamento dei due algoritmi di ricerca
Ricorsione
  • 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)
    • dato un intero n, calcolare la somma di n valori immessi 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) (dove x%y indica il resto della divisione intera tra x e y)

Venerdì 15 Marzo 2019 - Lezioni 9-10

Soluzioni delle equazioni di ricorrenza (1)

  • 4 metodi risolutivi (1/2):
    • metodo iterativo;
    • metodo di sostituzione;
    • metodo dell'albero.

Esercizi assegnati:

  • Calcolare la soluzione di alcune equazioni di ricorrenza

Lunedì 18 Marzo 2019 - Lezioni 11-12

Soluzioni delle equazioni di ricorrenza (2)

  • 4 metodi risolutivi (2/2):
    • metodo principale: enunciato del teorema senza dimostrazione
  • soluzione di alcune equazioni di ricorrenza

Esercizi assegnati:

  • Calcolare la soluzione di alcune equazioni di ricorrenza

Mercoledì 20 marzo 2019: Esercitazioni 7-8:

  • Esecuzione della funzione ricorsiva di Fibonacci: evoluzione della pila di sistema.
  • 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 Esonero 2014 sul tema: il problema del massimo fattore primo [ S4 ]

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

Venerdì 22 Marzo 2019 - Lezioni 13-14

Soluzioni delle equazioni di ricorrenza (3)

  • Esercizi riepilogativi sulle equazioni di ricorrenza

Esercizi assegnati:

  • Calcolare la soluzione di alcune equazioni di ricorrenza

Lunedì 25 Marzo 2019 - Lezioni 15-16

Il problema dell'ordinamento (1)

  • algoritmi naif: insertion sort, selection sort e bubble sort; calcolo del costo computazionale; algoritmi input sensitive
  • albero delle decisioni e teorema sulla limitazione inferiore per la complessità di un algoritmo per confronti
  • paradigma del divide et impera

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 (con l'aggiunta di una flag).
  • Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (prima versione).
  • Determinare l'albero delle decisioni del Selection Sort.

mercoledì 27 marzo 2019 - Esercitazioni 9-10

  • 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 ].
  • Soluzione Esonero 2012: il Problema del baricentro [ S1 ].
  • Virtuosismi: Baricentro con un'unica scansione ricorsiva del vettore [ 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 ].

Venerdì 29 Marzo 2019 - Lezioni 17-18

Il problema dell'ordinamento (2)

  • algoritmi efficienti:
    • merge sort (pseudocodice e costo computazionale, pseudocodice della funzione Fondi, problematica dell'ordinamento in loco)
    • cosa non va nel merge sort: una parentesi sull'uso della memoria secondaria
    • quick sort (pseudocodice, pseudocodice e costo della funzione Partiziona, riflessioni sulla scelta del valore soglia, costo computazionale nei casi migliore e peggiore)

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ì 1 Aprile 2019 - Lezioni 19-20

Il problema dell'ordinamento (3)

  • algoritmi efficienti:
    • funzionamento pratico del merge sort
    • quick sort (costo computazionale nel caso medio)
    • heapsort (una parentesi sulle strutture dati, struttura dati heap)

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.

mercoledì 3 aprile 2019 - Esercitazioni 11-12

  • Soluzione Esonero 2018: il problema del minimo intero libero [ S7 ];
  • Vettori variabili (allocati dentro le funzioni e di dimensioni dipendenti da una variabile);
  • Vettori dinamici (allocati con malloc o calloc ). Il tipo void *
  • Esempio: il Crivello di Eratostene.
  • Un aiutino sull'Homework, esercizio 3: il problema delle partizioni [ S3, sez. 1 ]

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

Venerdì 5 Aprile 2019 - Lezioni 21-22

Il problema dell'ordinamento (4)

  • algoritmi efficienti
    • heapsort (Heapify: pseudocodice e costo computazionale; Build Heap: pseudocodice e costo; Heapsort: pseudocodice e costo)
  • algoritmi lineari
    • counting sort (versione semplificata e versione completa)

Lunedì 8 Aprile 2019 - Lezioni 23-24

Il problema dell'ordinamento (5)

  • algoritmi lineari
    • bucket sort (idea)
  • alcuni approfondimenti sugli algoritmi di ordinamento (algoritmo di cancellazione su un heap, costo di Heapify come funzione di n e dimostrazione del costo lineare di Build Heap)

mercoledì 10 aprile 2019 - Esercitazioni 13-14

  • Soluzione Esonero 2016: generazione delle combinazioni di n oggetti presi k a k [ S5 ]
  • Vettori bidimensionali: allocazione statica [ D5, sez. 2 ].
  • Allocazione di una matrice dinamica [ D5, sez. 3 ].
  • Virtuosismi: funzione mergeRecVPC: merge ricorsiva da Veri Programmatori C [ L2 ].

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

Venerdì 12 Aprile 2019 - Lezioni 25-26

  • Esercizi in vista dell'esonero

Vacanze di Pasqua, ponti del 25 Aprile e 1 Maggio

Lunedì 29 Aprile 2019 - Lezioni 27-28

  • 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
    • pila
    • le operazioni Push e Pop

Venerdì 3 Maggio 2019 - Lezioni 29-30

  • Correzione compito d'esonero
  • Strutture dati fondamentali (2)
    • code con priorità
    • la struttura dati coda
    • le operazioni enqueue e dequeue
    • Esercizio: simulazione di una coda tramite due pile
    • alberi (1)
      • definizione tramite la nozione di grafo

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ì 6 Maggio 2019 - Lezioni 31-32

  • Strutture dati fondamentali (3)
    • alberi (2)
      • caratterizzazione degli alberi
      • memorizzazione degli alberi:
        • tramite record e puntatori
        • posizionale
        • tramite vettore dei padri
  • Visione Es. 1 e 3 compito d'esonero

Esercitazioni 15-16: mercoledì 8 maggio 2019

  • Correzione esercizio 2 esonero.
  • Introduzione ai record: definizioni di struct. [ D6, sez. 1 ]
  • 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 ].

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

Venerdì 10 Maggio 2019 - Lezioni 33-34

  • Strutture dati fondamentali (4)
    • alberi (3)
      • 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

Lunedì 13 Maggio 2019 - Lezioni 35-36

  • Strutture dati fondamentali (5) * Alberi binari di ricerca (ABR) (1):
      • definizione e proprietà dell' "ordinamento orizzontale"
      • algoritmo per il massimo e minimo
      • algoritmo per il successore e predecessore
      • algoritmo di inserimento
      • osservazioni sul costo computazionale delle operazioni viste come funzione dell'altezza

  • SOMMINISTRAZIONE TEST DI VALUTAZIONE DEL CORSO

Esercizi assegnati:

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

Esercitazioni 17-18: mercoledì 15 maggio 2019

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

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

Venerdì 17 Maggio 2019 - Lezioni 37-38

  • Strutture dati fondamentali (6)
    • Alberi binari di ricerca (ABR) (2):
      • algoritmo di cancellazione
      • alberi bilanciati: alberi rosso-neri
      • dimostrazione che gli alberi rosso-neri hanno altezza logaritmica
      • rotazioni
      • cenno all'operazione di inserimento

Esercizi assegnati:

  • 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ì 20 Maggio 2019 - Lezioni 39-40

  • 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

Esercitazioni 19-20: mercoledì 22 maggio 2019

  • Eliminazione di elementi: removeFun e removeRec [dispensa D6, sez. 3.6 ].
  • Il problema della deallocazione di memoria dinamica: free() [dispensa D6, sez. 2.1 ].
  • Eliminazione di elementi: removeIt: attenzione a non perdere la testa (della lista)! [dispensa D6, sez. 3.6 ].
  • Esercizi da esoneri/esami passati:
    • differenza simmetrica tra liste (ordinate). Attenzione alle versioni che modificano [Dispensa S6, sez. 1.3 ].
    • problema di determinare se una lista è palindroma

  • Esercizi consigliati: differenza tra liste, rimozione di duplicati [dispensa D6, sez. 3.6 ] e altri esercizi nella dispensa S6 sezione 1.

Venerdì 24 Maggio 2019 - Lezioni 41-42

  • Grafi (2)
    • Visita in ampiezza: filosofia, esempio, pseudocodice, costo computazionale in funzione della struttura dati usata, proprietà dell'albero di visita in ampiezza (archi di riporto vs. di attraversamento, cammini più corti)
    • Esempi di uso di visita in ampiezza: calcolo dei cammini più corti da un nodo dato

    • Visita in profondità: filosofia, esempio, pseudocodice, costo computazionale in funzione della struttura dati usata, proprietà dell'albero di visita in profondità (archi di riporto vs. di attraversamento)

Lunedì 27 Maggio 2019 - Lezioni sospese dal Rettore per le elezioni*

Esercitazioni 21-22: mercoledì 29 maggio 2019

  • Introduzione agli alberi binari: definizione induttiva e rappresentazione in C [dispensa D7, sez. 1 e sez. 1.1 ].
  • Costruttori e distruttori: makeTree(int n, binTree L, binTree R) e isNotEmptyTree(binTree B, int r, binTree L, binTree R) [ *D7, sez. 1.1 ].
  • Funzioni base: numero di nodi, peso, profondità.
  • Stampare un albero binario: stampa a parentesi e indentata.
  • Produrre la lista di nodi. Versioni efficienti che usano solo aggiunte in testa.

  • Esercizi consigliati: vedi dispensa D7, sez. finale di esercizi.

Venerdì 31 Maggio 2019 - Lezioni 43-44

  • Grafi (3)
    • Esempi di uso di visita in profondità: calcolo delle componenti connesse
    • Esercizi su grafi: calcolo del grafo complemento e del quadrato di un grafo

Esercizi assegnati:

  • Dato un grafo G mediante le sue liste di adiacenza, progettare un algoritmo che dica se G è aciclico oppure no.

Esercitazioni 23-24: lunedì 3 giugno 2019

  • Alberi binari: visita per livelli [dispensa D7, sez. 1.3 ].
  • Discussione sull'equivalenza di tipi: equivalenza di struttura e per nome.
  • Il problema del bilanciamento: versioni naive e versioni efficienti con un'unica scansione dell'albero.
  • Esoneri passati
    • il problema di restituire la lista dei nodi al livello k: funzione livelloK [dispensa S6, sez. 2.2 ]
    • il problema di determinare il cammino fino a un nodo x: funzione pathToX [dispensa S6, sez. 2.3 ]

  • Esercizi consigliati: vedi dispensa D7, sez. finale di esercizi e dispensa S6.

Mercoledì 5 Giugno 2019 - Lezioni 45-46

  • Grafi (4)
    • Grafi euleriani: definizione, teorema di Eulero, esercizio
    • Grafi bipartiti: definizione, caratterizzazione, esercizio

Venerdì 7 Giugno 2019 - Lezioni 47-48

  • Grafi (5)
    • Grafi planari e relazione di Eulero
    • Colorazione di grafi
    • Un'applicazione alle reti cellulari

Lunedì 10 Giugno 2018 - Lezioni 49-50

  • Esercizi in preparazione dell'esonero

Esercitazioni 25-26: mercoledì 12 giugno 2019

  • Ricostruzione di un albero binario avendo due visite (ad esempio, preorder e inorder).
  • Esoneri passati
    • sostituire le etichette di un albero con la somma del sottoalbero
    • funzione che ordina una lista secondo l'algoritmo selection sort. Attenzione alla versione Fun!
    • deallocazione di un albero binario. Funzione che pruna un albero nella parte non crescente;
    • modificare una lista con la somma dei precedenti;
    • rappresentare i naturali con liste di puntatori.

  • Esercizi consigliati: vedi dispensa S6, con soluzioni agli esercizi di compiti passati.

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

Esercitazioni 19-20: mercoledì 23 maggio 2018

  • Discussione Homework 2: definizioni di tipi per il problema della Torre di Hanoi.
  • Eliminazione di elementi: removeFun e removeRec [dispensa D6, sez. 3.6 ].
  • Il problema della deallocazione di memoria dinamica: free() [dispensa D6, sez. 2.1 ].
  • Eliminazione di elementi: removeIt: attenzione a non perdere la testa (della lista)! [dispensa D6, sez. 3.6 ].
  • Esercizi da esoneri passati: il problema dello shuffle [Dispensa S6, sez. 1.5 ].

* Esercizi consigliati: differenza tra liste, rimozione di duplicati [dispensa D6, sez. 3.6 ] e altri esercizi nella dispensa S6 sezione 1.

Venerdì 25 Maggio 2018 - Lezioni 39-40*

  • Grafi (2)
    • Visita in ampiezza: filosofia, esempio, pseudocodice, costo computazionale in funzione della struttura dati usata, proprietà dell'albero di visita in ampiezza (archi di riporto vs. di attraversamento, cammini più corti)
    • Esempi di uso di visita in ampiezza: calcolo dei cammini più corti da un nodo dato

Lunedì 28 Maggio 2018 - Lezioni 41-42*

  • Grafi (3)
    • Visita in profondità: filosofia, esempio, pseudocodice, costo computazionale in funzione della struttura dati usata, proprietà dell'albero di visita in ampiezza (archi di riporto vs. di attraversamento)
    • Esempi di uso di visita in profondità: calcolo delle componenti connesse
    • Esercizi su grafi: calcolo del grafo complemento e del quadrato di un grafo

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.

Esercitazioni 21-22: mercoledì 30 maggio 2018

  • Introduzione agli alberi binari: definizione induttiva e rappresentazione in C [dispensa D7, sez. 1 e sez. 1.1 ].
  • Costruttori e distruttori: makeTree(int n, binTree L, binTree R), isNotEmptyTree(binTree B, int r, binTree L, binTree R) [ *D7, sez. 1.1 ].
  • Funzioni base: numero di nodi, profondità.
  • Il problema del bilanciamento: in profondità e in peso con un'unica visita dell'albero [dispensa D7, sez. 1.4 ].
  • Fuori programma: macro espansioni con #define: la macro min(x,y)=x<y?x:y.

* Esercizi consigliati: vedi dispensa D7, sez. finale di esercizi.

Venerdì 1 Giugno 2018 - Lezioni 43-44*

  • Grafi (4)
    • Grafi euleriani: definizione, teorema di Eulero, esercizio
    • Grafi bipartiti: definizione, caratterizzazione, esercizio
    • Colorazione di grafi

Esercitazioni 23-24: lunedì 4 giugno 2018

  • Discussione Homework 3.
  • Alberi binari: visita per livelli [dispensa D7, sez. 1.3 ].
  • Problemi con liste e alberi: il problema della frontiera [dispensa D7, sez. 1.2 ]. Versione efficiente che evita uso di append .
  • Esoneri passati
    • il problema di restituire la lista dei nodi al livello k: funzione livelloK [dispensa S6, sez. 2.2 ]
    • il problema di determinare il cammino fino a un nodo x: funzione pathToX [dispensa S6, sez. 2.3 ]

  • Esercizi consigliati: vedi dispensa D7, sez. finale di esercizi e dispensa S6.

Esercitazioni 25-26: mercoledì 6 giugno 2018

  • Relazione di uguaglianza e sottoalbero [ dispensa D7, sez. 1.5 ]
  • Esercizi in preparazione dell'esonero:
    • divisione di liste: funzione dividi [dispensa S6, sez. 1.1 ]
    • somma precedenti [dispensa S6, sez. 1.2 ] e somma successiv [dispensa S2 ]
    • prefisso tra alberi [dispensa S6, sez. 2.4 ]

  • Esercizi consigliati: dispensa S6.

Venerdì 8 Giugno 2018 - Lezioni 45-46*

  • Esercizi in preparazione dell'esonero

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


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


This topic: Info_gen > WebHome > DiarioDelleLezioni > AnniPrecedenti
Topic revision: r3 - 2020-01-14 - TizianaCalamoneri
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback