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ì): prima prova per la verifica delle conoscenze. PrimoEsonero24_conSol.pdf
per non tenervi sulle spine ecco i risultati (chi non ha superato ha il simbolo "-")
risultatiIntroduzione1.pdf
Settimana 07 - 8 Aprile
*8 Aprile 2024 (Lunedì):*La tenica algoritmica del divide et impera. L' Algoritmo di ordinamento Θ(nlog n) mergesort e la sua funzione "fondi" di tempo Θ(n). Implementazione iterativa del mergesort.
lez09Ordinamento2Merge.pdf
L'algoritmo di quicksort, implementazione con spazio di lavoro O(n^2) . Analisi al caso pessimo Θ(n^2). Analisi al caso ottimo Θ(n log n). Quicksort randomizzato.-
lez10Ordinamento3Quik.pdf
11 Aprile 2024 (Giovedì): La funzione partition del quicksort.Alberi completi e quasi completi. Definizione di heap (minimo) e sua rappresentazione tramite aray. La libreria heapq di python. Le funzioni heapify(), heappush(), heappop() per costruire un heap di n elementi, aggiungere un elemento ad un heap di n elementi ed estrarre il minimo dall'heap di n elementi in tempo O(n), O(log n), O(log n) , rispettivamente. Algoritmo di ordinamento
HeapSort con spazio di lavoro O(n). Implementazione della funzione di heappop() in O(log n).
lez11HeapSort1.pdf
Settimana 08 - 15 Aprile
15 Aprile 2024 (Lunedì):
- implementazione della funzione di heappush in tempo O(log n) e implementazione della funzione heapify in tempo Θ(n) (vedi le slide di lez11)
- l'algoritmo di ordinamento Counting-Sort per ordinare interi nell'intervallo [0...M] e sua implementazione in O(M+n).
- Soluzione dell'esercizio 2 assegnato nell'appello di marzo 2023
lez12OrdinamentiLineari.pdf
18 Aprile 2024 (Giovedì): strutture dati statiche e strutture dati dinamiche: vantaggi e svantaggi. Gli array e le liste a puntatori. Le liste di python. Creazione di una lista a puntatori da una lista e stampa di una lista a puntatori in tempo in tempo Θ(n). Inserimento e cancellazione da una lista a puntatori.
lez13struttureDati1.pdf
Settimana 19 - 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ì):