Diario delle Lezioni (Angelo Monti) a.a. 2023/2024
NOTA: le lezioni NON verranno registrate, ma trovate qui il dettaglio degli argomenti svolti ed il link al pdf delle slides utilizzate.
Settimana 1 - 26 Febbraio
26 Febbraio 2024 (Lunedì): Presentazione del corso. Introduzione all'asintotica delle funzioni significato dell'insieme O
lez01Introduzione24.pdf
29 Febbraio 2024 (Giovedì): asintotica delle funzioni, definizione, significato ed esercizi per gli insiemi Ω e Θ.
lez02Asintotica24.pdf
Settimana 02 - 4 Marzo
4 Marzo 2024 (Lunedì):-lezione sul calcolo della complessità asintotica di un algoritmo
lez03CostoAlgoritmi.pdf ESERCIZI su sommatorie e altro
Esempi_ed_eserciziAsintotica24.pdf
7 Marzo 2024 (Giovedì): esercizi sul calcolo della complessità di semplici programmi iterativi
ESERCIZICostoAlgoritmi.pdf 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 sua complessità nel caso pessimo, ottimo e medio.
lez04ProblemaRicerca.pdf
Settimana 03 - 11 Marzo
11 Marzo 2024 (Lunedì): 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
14 Marzo 2024 (Giovedì):
Risolvere equazioni di ricorrenza tramite il metodo iterativo e\o il metodo dell'albero. Esempi svolti in aula:
T(n)=T(n-1) +Θ(1) , T(1)=Θ(1). Soluzione: Θ(n)
T(n)=T(n-1) +Θ(n) , T(1)=Θ(1). Soluzione: Θ(n^2)
T(n)=T(n-1) +Θ(log n) , T(1)=Θ(1). Soluzione: Θ(n log 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)
lez06EquazioniRicorrenza24.pdf
Settimana 04 - 18 Marzo
*
18 Marzo 2024 (Lunedì):* -Risolvere equazioni di ricorrenza tramite il teorema principale e\o il metodo di sostituzione.
21 Marzo 2024 (Giovedì): -Esercizi svolti in classe con tutti e 4 i metodi:
T(n)=T(n^{1/2}) +Θ(1) , T(1)=Θ(1). Soluzione: Θ(loglog n)
T(n)=2T(n/4) +Θ(n^{1/2}) , T(1)=Θ(1). Soluzione: Θ(n^{1/2}log n)
T(n)=2T(n/2) +Θ(n^3) , T(1)=Θ(1). Soluzione: Θ(n^3)
07_EserciziEqRicorrenza2024.pdf
Settimana 05 - 25 Marzo
*
25 Marzo 2024 (Lunedì):*algoritmi elementari di ordinamento a complessità Θ(n^2) al caso pessimo: insertion sort, seleciton sort e bubble sort. Loro implementazione in python. Gli alberi di decisione e la prova Gli algoritmi di ordinamento basati sul confronto richiedono Ω(nlog n) confronti.
lez08Ordinamento1Naive.pdf
esercizi sulle ricorrenze
eserciziEquazioniDiRicorrenza.pdf
28 Marzo 2024 (Giovedì): VACANZE DI PASQUA
Settimana 06 - 1 Aprile
Settimana 06 - 1 Aprile
1 Aprile 2024 (Lunedì): VACANZE DI PASQUA
4 Marzo 2024 (Giovedì):
Settimana 07 - 8 Aprile
8 Aprile 2024 (Lunedì): -
11 Aprile 2024 (Giovedì):
Settimana 08 - 15 Aprile
15 Aprile 2024 (Lunedì):
18 Aprile 2024 (Giovedì):
Settimana 09 - 22 Aprile
*
22 Aprile 2024 (Lunedì):
25 Aprile 2024 (Giovedì): festa della liberazione
Settimana 10 - 29 Aprile
29 Aprile 2024 (Lunedì):
2 Maggio 2024 (Giovedì):
Settimana 11 - 6 Maggio
6 Maggio 2024 (Lunedì):
9 Maggio 2024 (Giovedì):
Settimana 12 - 13 Maggio
13 Maggio 2023 (Lunedì):
16 Maggio 2023 (Giovedì):
Settimana 13 - 20 Maggio
*20 Maggio 2024 (Lunedì):*
23 Maggio 2024 (Giovedì):
Settimana 14 - 27 Maggio
27 Maggio 2024 (Lunedì):
30 Maggio 2024 (Giovedì):