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

Settimana 15 - 30 Maggio

30 Maggio 2022 (Lunedý): -

Topic attachments
I Attachment History Action Size Date Who Comment
PDFpdf ESERCIZIOlistaPDF.pdf r1 manage 89.0 K 2021-04-19 - 13:22 AngeloMonti  
PDFpdf Esempi_ed_eserciziAsintotica.pdf r2 r1 manage 122.1 K 2022-02-28 - 13:06 AngeloMonti  
PDFpdf EserciziListeLinkate.pdf r1 manage 472.1 K 2022-05-02 - 13:01 AngeloMonti  
PDFpdf EserciziListeLinkatePDF.pdf r1 manage 551.7 K 2021-04-22 - 12:11 AngeloMonti  
PDFpdf Lez21Esercizi.pdf r1 manage 696.0 K 2022-05-23 - 08:11 AngeloMonti  
PDFpdf Lez21EserciziVari1PDF.pdf r1 manage 483.6 K 2021-05-13 - 12:51 AngeloMonti  
PDFpdf Lez21tracce.pdf r1 manage 354.6 K 2022-05-23 - 05:00 AngeloMonti  
PDFpdf Lez22EserciziPDF.pdf r1 manage 523.5 K 2021-05-18 - 16:00 AngeloMonti  
PDFpdf Lez22tracce.pdf r1 manage 559.9 K 2022-05-23 - 08:16 AngeloMonti  
PDFpdf Lez23EserciziPDF.pdf r1 manage 914.1 K 2021-05-24 - 17:37 AngeloMonti  
PDFpdf Lez23TRACCEserciziPDF.pdf r1 manage 687.3 K 2021-05-18 - 16:07 AngeloMonti  
PDFpdf esercizioMatrice.pdf r1 manage 104.1 K 2021-04-15 - 16:39 AngeloMonti  
PDFpdf lez01Introduzione22.pdf r1 manage 390.7 K 2022-02-19 - 09:58 AngeloMonti  
PDFpdf lez01IntroduzionePDF.pdf r1 manage 841.9 K 2021-02-22 - 13:53 AngeloMonti  
PDFpdf lez02Asintotica22.pdf r2 r1 manage 942.2 K 2022-02-21 - 14:21 AngeloMonti  
PDFpdf lez02AsintoticaPDF.pdf r1 manage 848.6 K 2021-02-25 - 18:27 AngeloMonti  
PDFpdf lez03CostoAlgoritmi.pdf r1 manage 587.4 K 2022-02-27 - 09:56 AngeloMonti  
PDFpdf lez03CostoAlgoritmi22.pdf r1 manage 587.4 K 2022-02-27 - 09:57 AngeloMonti  
PDFpdf lez03CostoAlgoritmiEsercizi.pdf r2 r1 manage 422.2 K 2022-03-07 - 10:58 AngeloMonti  
PDFpdf lez03CostoAlgoritmiPDF.pdf r1 manage 820.8 K 2021-03-01 - 13:22 AngeloMonti  
PDFpdf lez04ProblemaRicerca.pdf r1 manage 504.8 K 2022-03-11 - 12:04 AngeloMonti  
PDFpdf lez04ProblemaRicercaPDF.pdf r1 manage 525.4 K 2021-03-04 - 14:01 AngeloMonti  
PDFpdf lez04ProblemaRicercab.pdf r1 manage 463.3 K 2022-03-13 - 14:11 AngeloMonti  
PDFpdf lez05AlgoritmiRicorsivi.pdf r1 manage 1343.4 K 2022-03-15 - 08:19 AngeloMonti  
PDFpdf lez05AlgoritmiRicorsiviPDF.pdf r1 manage 1217.9 K 2021-03-08 - 13:43 AngeloMonti  
PDFpdf lez06EquazioniRicorrenza.pdf r2 r1 manage 529.7 K 2022-03-25 - 08:28 AngeloMonti  
PDFpdf lez06EquazioniRicorrenzaPDF.pdf r1 manage 599.2 K 2021-03-11 - 14:39 AngeloMonti  
PDFpdf lez07EserciziEquaRic.pdf r1 manage 555.7 K 2022-03-25 - 17:07 AngeloMonti  
PDFpdf lez08Ordinamento1Naive.pdf r2 r1 manage 1473.2 K 2022-03-08 - 10:00 AngeloMonti  
PDFpdf lez08Ordinamento1NivePDF.pdf r1 manage 1524.1 K 2021-03-18 - 12:08 AngeloMonti  
PDFpdf lez09Merge.pdf r1 manage 433.0 K 2022-04-04 - 08:10 AngeloMonti  
PDFpdf lez09Ordinamento2MergePDF.pdf r1 manage 516.7 K 2021-03-25 - 13:20 AngeloMonti  
PDFpdf lez10Ordinamento3QuikPDF.pdf r1 manage 630.6 K 2021-03-29 - 16:59 AngeloMonti  
PDFpdf lez10Quick.pdf r2 r1 manage 522.1 K 2022-04-07 - 12:23 AngeloMonti  
PDFpdf lez11.pdf r2 r1 manage 585.8 K 2022-04-21 - 05:53 AngeloMonti  
PDFpdf lez11Ordinamento4HeapPDF.pdf r1 manage 569.4 K 2021-04-08 - 11:17 AngeloMonti  
PDFpdf lez12OrdinamentiLineari.pdf r1 manage 619.8 K 2022-04-09 - 07:52 AngeloMonti  
PDFpdf lez12Ordinamento5LineariPDF.pdf r1 manage 660.3 K 2021-04-12 - 13:15 AngeloMonti  
PDFpdf lez13.pdf r1 manage 685.6 K 2022-05-19 - 19:30 AngeloMonti  
PDFpdf lez13struttureDati1PDF.pdf r1 manage 656.8 K 2021-04-15 - 16:39 AngeloMonti  
PDFpdf lez14.pdf r1 manage 654.7 K 2022-04-30 - 09:35 AngeloMonti  
PDFpdf lez14StruttureDati2PDF.pdf r1 manage 644.7 K 2021-04-19 - 13:22 AngeloMonti  
PDFpdf lez16Alberi1aPDF.pdf r1 manage 577.8 K 2021-04-26 - 11:44 AngeloMonti  
PDFpdf lez16Alberi1bPDF.pdf r1 manage 456.1 K 2021-04-29 - 13:04 AngeloMonti  
PDFpdf lez16a.pdf r1 manage 534.2 K 2022-05-04 - 08:15 AngeloMonti  
PDFpdf lez16b.pdf r1 manage 439.8 K 2022-05-04 - 08:15 AngeloMonti  
PDFpdf lez17.pdf r1 manage 456.5 K 2022-05-06 - 12:56 AngeloMonti  
PDFpdf lez17VisiteAlberiPDF.pdf r1 manage 620.4 K 2021-04-29 - 13:04 AngeloMonti  
PDFpdf lez18ABR.pdf r1 manage 693.4 K 2022-05-16 - 08:29 AngeloMonti  
PDFpdf lez18Dizionari1.pdf r1 manage 861.7 K 2021-05-03 - 17:55 AngeloMonti  
PDFpdf lez19ABR_RB.pdf r1 manage 982.2 K 2022-05-15 - 07:14 AngeloMonti  
PDFpdf lez19Dizionari2ABRPDF.pdf r1 manage 743.2 K 2021-05-12 - 07:56 AngeloMonti  
PDFpdf lez20Dizionari1.pdf r1 manage 834.6 K 2022-05-18 - 15:22 AngeloMonti  
PDFpdf lez20Dizionari3bPDF.pdf r1 manage 1143.1 K 2021-05-12 - 07:56 AngeloMonti  
PDFpdf solEqRic1PDF.pdf r1 manage 386.1 K 2021-03-18 - 12:01 AngeloMonti  
PDFpdf solEqRic4PDF.pdf r1 manage 417.1 K 2021-03-22 - 12:28 AngeloMonti  
PDFpdf solEqRic5PDF.pdf r1 manage 421.5 K 2021-03-22 - 12:28 AngeloMonti  
PDFpdf solEqRic6PDF.pdf r1 manage 404.8 K 2021-03-22 - 12:28 AngeloMonti  
PDFpdf solEsercizi1PDF.pdf r1 manage 425.4 K 2021-03-11 - 14:39 AngeloMonti  

This topic: Intro_algo/PZ > WebHome > DiarioA
Topic revision: r76 - 2022-05-23 - AngeloMonti
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback