Diario delle Lezioni (Angelo Monti) a.a. 2021/2022

Le lezioni di questo semestre sono in modalità blended.

NOTA: le lezioni NON verranno registrate, ma trovate qui il dettaglio degli argomenti svolti ed il pdf delle slides utilizzate.

.

Settimana 01 - 21 Febbraio

Lezione di lunedì 21 febbraio 2022: Introduzione agli argomenti del corso lez01Introduzione22.pdf*

Lezione di giovedì 24 febbraio 2022: introduzione all'asintotica delle funzioni. Definizione e significato degli insiemi O, Ω e Θ

lez02Asintotica22.pdf

Settimana 02 - 28 Febbraio

28 Febbraio 2022 (Lunedì):- ESERCIZI sul calcolo dell'asintotica delle funzioni Esempi_ed_eserciziAsintotica.pdf

3 Marzo 2022 (Giovedì): lezione sul calcolo della complessità asintotica di un algoritmo lez03CostoAlgoritmi22.pdf

Settimana 03 - 7 Marzo

7 Marzo 2022 (Lunedì): ESERCIZI lez03CostoAlgoritmiEsercizi.pdf Algoritmi ingenui di ordinamento: Bubble sort e Selection sort lez08Ordinamento1Naive.pdf

10 Marzo 2022 (Giovedì): -Dalle dispense della lezione precedente: algoritmi ingenui di ordinamento: Insertion sort. Gli algoritmi di ordinamento basati sul confronto richiedono Ω(nlog n) confronti. ESERCIZI.

Settimana 04 - 14 Marzo

14 Marzo 2022 (Lunedì): - Il problema della ricerca. Algoritmo sequenziale e sua complessità nel caso pessimo, ottimo e medio. L'algoritmo di ricerca binaria per la ricerca in vettori ordinati e cua complessita' nel caso pessimo, ottimo e medio lez04ProblemaRicercab.pdf

17 Marzo 2022 (Giovedì): -Esempi di algoritmi ricorsivi: ricerca sequenziale, ricerca binaria, calcolo delle palindromi, calcolo dei numeri di fibonacci. Impostazione dell'equazione di ricorrenza per il calcolo della complessita' degli algoritmi ricorsivi lez05AlgoritmiRicorsivi.pdf

Settimana 05 - 21 Marzo

21 Marzo 2022 (Lunedì): - Esercizi: scrivere algoritmi ricorsivi per i seguenti tre problemi : trovare il minimo in una lista, stampare gli elementi di una lista, stampare gli elementi di una lista in ordine inverso. L'equazione di ricorrenza per la complessità di ciascuno dei tre algoritmi deve essere sempre T(n==T(n-1)+Θ(1) (vedere i lucidi della lezione precedente). Risolvere equazioni di ricorrenza tramite il metodo iterativo. Esempi svolti in aula:

T(n)=T(n-1) +Θ(1) , T(1)=Θ(1). Soluzione: Θ(n)

T(n)=T(n/2) +Θ(1) , T(1)=Θ(1). Soluzione: Θ(log n)

T(n)=2T(n/2) +Θ(1) , T(1)=Θ(1). Soluzione: Θ(n)

T(n)=T(n/2) +Θ(n) , T(1)=Θ(1). Soluzione: Θ(n)

lez06EquazioniRicorrenza.pdf

24 Marzo 2022 (Giovedì): Lower ed upper bound per l'equazione di fibonacci: T(n)=T(n-1)+T(n-2)+Θ(n) risolvere equazioni di ricorrenza tramite il metodo principale, l'albero di ricorrenza o il metodo di sostituzione (lucidi della lezione precedente)

Settimana 06 - 28 Marzo

28 Marzo 2022 (Lunedì): -risolvere equazioni di ricorrenza col metodo di sostituzione:

T(n)=T(n-1)+Θ(1) , T(1)=Θ(1). Soluzione: Θ(n)

T(n)=2T(n/2)+Θ(n), T(1)=Θ(1). Soluzione: Θ(nlog n)

Esercizi sulla risoluzione di equazioni di ricorreza utilizzando tutti e quattro i metodi:

T(n)=9T(n/3)+Θ(n^2), T(1)=Θ(1). Soluzione: Θ(n^2log n)

esercizi svolti per la soluzione delle equazioni di ricorrenza lez07EserciziEquaRic.pdf

31 Marzo 2022 (Giovedì): LEZIONE ANNULLATA PER APPELLO STRAORDINARIO DI INTRODUZIONE AGLI ALGORITMI

Settimana 07 - 4 Aprile

4 Aprile 2022 (Lunedì): -L' Algoritmo di ordinamento Θ(nlog n) mergesort e la sua funzione "fondi" di tempo Θ(n).

ESERCIZI sulla risoluzione di equazioni di ricorrenza utilizzando il metodo iterativo:

T(n)=T(√n)+Θ(1), T(2)=Θ(1). Soluzione: Θ(log log n)

T(n)=T(n-1)+Θ(√n), T(1)=Θ(1). Soluzione: Θ( n^(3/2))

lez09Merge.pdf

7 Aprile 2022 (Giovedì): - l'algoritmo di ordinamento O(n^2) quicksort con la sua procedura partition. Analisi Θ(n log n) del caso medio. lez10Quick.pdf

ESERCIZIO: limitre superiormente il valore che e' possibile dare a k perche' l'algoritmo che utilizza il mergesort su array di dimensione maggiori di k e l'insertion sort per array di dimensione minore o uguale a k abbia comunque complessità O(n log n).

ESERCIZIO: dato un array ordinato di n interi ed un itero k progettare un algoritmo che in tempo Θ(n) determini ilnumero di coppie di valori presenti nell'array la cui somma dia k.

Settimana 08 - 11 Aprile

11 Aprile 2022 (Lunedì): l'algoritmo di ordinamento counting-sort per ordinare interi non negativi e sua implementazione in O(k+n) dove k e' l'intero massimo tra quelli da ordinare. L'algoritmo bucket-sort per ordinare elementi non necessariamente interi nell'intervallo [0...M],

sua implementazione che da tempo di esecuzione Θ(n) quando i buckets sono Θ(n) e gli interi da ordinare sono equamente distribuiti nell'intervallo [0...M] lez12OrdinamentiLineari.pdf

ESERCIZIO risolvere la seguente equazione di ricorrenza utilizzando il metodo iterativo, il metodo dell'albero e il metodo di sostituzione:

T(n)=9T(n-3)+Θ(2^n), T(0)=Θ(1). Soluzione: Θ(9^(n/3))

14 Aprile 2022 (Giovedì): Nessuna lezione

Settimana 09 - 18 Aprile

18 Aprile 2022 (Lunedì): Nessuna lezione

21 Aprile 2022 (Giovedì): -alberi binari completi o quasi completi. Relazione h=Θ(log n) tra l'altezza h e il numero di nodi n di un albero binario completo o quasi completo. Heap massimo e sua rappresentazione tramite Array (o liste) . trovare e il massimo in un heap massimo in Θ(1) e cancellare il massimo in un heap massimo in tempo Θ(log n) tramite la funzione heapify. Costruire un heap di n elementi in tempo Θ(nlog n) lez11.pdf

Settimana 10 - 25 Aprile

25 Aprile 2022 (Lunedì): Nessuna lezione

28 Aprile 2022 (Giovedì): Costruire un heap in tempo Θ(n) - ordinare con Heapsort in tempo Θ(nlog n) (lucidi lez11.pdf). La struttura dati Array e la struttura dati lista a puntatori.

ESERCIZI:

1) creare una lista a puntatori a partire da un array. Tempo Θ(n)

2) stampare una lista a puntatori dato il puntaore alla testa della lista. Tempo Θ(n)

3) inserire un nodo in testa ad una lista. Tempo Θ(1)

4) dato un puntatore p alla lista, un puntatore d ad un nodo della lista ed un nodo q inserire il nodo q nella lista DOPO il nodo puntato da d. Tempo Θ(1)

5) dato un puntatore p alla lista, un puntatore d ad un nodo della lista ed un nodo q inserire il nodo q nella lista PRIMA del nodo puntato da d. Tempo Θ(n)

Liste a doppio puntatore

6) svolgere l'esercizio 5 assumendo che la lista ia a doppio puntatore. Tempo Θ(1)

lez13.pdf

Settimana 11 - 2 Maggio

2 Maggio 2022 (Lunedì): -Pile e code su array e su liste concatenate. Implementazione tramite array e tramite liste concatenate lez14.pdf

ESERCIZI:

1) dato il puntatore alla testa di una lista e un intero x progettare una funzione ITERATIVA che in tempo Θ(n) restituisce il numero di occorrenze dell'intero x nel camopio chiave dei nodi della lista. Progettare poi una analoga funzione RICORSIVA.

2) dato un puntatore ad una lista progettare una funzione che in tempo O(n) restituisce valore massimo tra quelli presenti nelle chiavi dei nodi della lista e il puntatore alla lista in cui il nodo contenente il massimo sia stato cancellato.

3) dato un puntatore ad una lista ordinata (vale a dire che i nodi compaiono con chiavi di valore non decrescente) ed il puntatore ad un nodo d. Progettare una funzione che in O(n) inserisce nella lista il nodo d in modo che la nuova lista risulti ancora ordinata. La funzione deve restituire il puntatore alla nuova lista. Progettare la funzione nell versione iterativa e poi in quella ricorsiva.

EserciziListeLinkate.pdf-

5 Maggio 2022 (Giovedì): Alberi: dalle liste a puntatori agli alberi. Alberi binari, alberi completi o quasi completi, relazione logaritmica tra il numero di nodi e l'altezza dell'albero.

Funzione che dato n ed m genera un albero binario a caso con n nodi e con chiavi nell'intervallo [1,m] e restituisc eil puntatore alla radice.

funzione che dato il puntatore alla radice di un albero restituisce le chiavi dei nodi dell'albero facendo si che le chiavi dei nodi figli vengano stampate a destra della colonna con le chiavi dei nodi padre.

Rappresentazione alternativa di alberi tramite array (rappresentazione posizionale) vantaggi e svantaggi.

Rappresentazione di alberi tramite il vettore dei padri, vantaggi e svantaggi.

lez16b.pdf

Settimana 12 - 9 Maggio

9 Maggio 2022 (Lunedì): - Dai grafi agli alberi: alvbero come grafo connesso senza cicli, alberi radicati. In un albero di n nodi sono presenti esattamente n-1 archi lez16a.pdf

Visite di alberi: la visita preorder, la visita postorder la visita inorder. Queste visite hanno tutte costo Θ(n).

Esercizi con esempi di visita postorder:

1) dato il puntatore r alla radice di un albero calcolare il numero di nodi dell' albero. Tempo Θ(n).

2) dato il puntatore r alla radice di un albero calcolare l'altezza dell' albero. Tempo Θ(n).

Esempi di visita preorder:

1) dato il puntatore r alla radice di un alberoe un intero x restituire True o False a seconda che l'albero abbia un nodo con chiave x o meno. Tempo O(n)

lez17.pdf

12 Maggio 2022 (Giovedì):

Esercizi:

1) dato il puntatore adlla radice di un albero binario stampare i contenuti dei nodi per livello grazie all'utilizzo di una coda.

2) dato il puntatore alla radice di un albero binario ed un intero k calcolare il numero di nodi dell'albero che compaiono al libvello k.

(vedi lez17.pdf)

Alberi binari di ricerca. Sia h l'altezza dell'albero:

1) Algoritmo di ricerca di una chiave in tempo O(h)

2) inserimento di un nodo nell'albero in tempo O(h)

3) cancellazione di un nodo nell'albero in tempo O(h)

lez18ABR.pdf-

Settimana 13 - 16 Maggio

*16 Maggio 2022 (Lunedì):*operazione di rotazione sinistra (e rotazione destra) in un albero di ricerca. Implementazione delle rotazioni in tempo Θ(1). Bilanciamento di alberi di ricerca per portare il costo di inserimenti, cancellazioni e ricerche da tempo O(h) a tempo O(log n). Definizione di alberi rosso neri, prova che gli alberi rosso neri sono bilanciati (in pratica hanno altezza limitata da 2log (n+1)). lez19ABR_RB.pdf-

19 Maggio 2022 (Giovedì): Dizionari ad Indirizzamento diretto. Fattori di carico α. Dizionari tramite tabelle hash. Hash chiuso e tempo di ricerca 1/2(1+1/(1-α)). Hash con liste di trabocco e tempo di ricerca 1+α lez20Dizionari1.pdf

Settimana 14 - 23 Maggio

23 Maggio 2022 (Lunedì): -esercizi preparatori all'esame Lez21tracce.pdf Lez21Esercizi.pdf

26 Maggio 2022 (Giovedì): - Lez22tracce.pdf Lez22Esercizi.pdf

Settimana 15 - 30 Maggio

30 Maggio 2022 (Lunedì): -