Diario delle Lezioni (Angelo Monti) a.a. 2024/2025

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

Settimana 1 - 28 Febbraio

Presentazione del corso. lez01A1Introduzione25.pdf

Settimana 2 - 3 Marzo

Asintotica delle funzioni, definizione, significato ed esercizi per gli insiemi O, Ω e Θ. lez02A1Asintotica25.pdf

Settimana 2 - 7 Marzo

Asintotica di sommatorie tipo: somme aritmetiche, somme geometriche ecc.ecc. lez02bA1AsintoticaSomme.pdf

Settimana 3 - 10 Marzo

Calcolo della complessità asintotica temporale di programmi iterativi lez03A1CostoAlgoritmi.pdf

Settimana 3 - 14 Marzo

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. lez04A1ProblemaRicerca25.pdf

Settimana 4 - 17 Marzo

Esempi di algoritmi ricorsivi: fattoriale, ricerca sequenziale, ricerca binaria, sommare gli elementi di una lista, calcolo delle potenze, calcolo delle palindromi, calcolo delle permutazioni, calcolo dei numeri di fibonacci. Impostazione delle equazioni di ricorrenza per il calcolo della complessità degli algoritmi ricorsivi. lez05A1AlgoritmiRicorsivi.pdf

Settimana 4 - 21 Marzo

Risolvere equazioni di ricorrenza . lez06A1EquazioniRicorrenza25.pdf

Settimana 5 - 24 Marzo

Il teorema principale (master Theorem) e le equazioni di ricorrenza.

Settimana 5 - 28 Marzo

Algoritmi elementari di ordinamento a complessità Θ(n^2) al caso pessimo: insertion sort, seleciton sort e bubble sort. Loro implementazione in python. lez08A1OrdinamentiNaive25.pdf

Settimana 6 - 31 Marzo

Gli alberi di decisione e la prova Gli algoritmi di ordinamento basati sul confronto richiedono Ω(nlog n) confronti.

Algoritmi di ordinamento con tempi O(n) lez12A1OrdinamentiLineari25.pdf

Settimana 6 - 4 Aprile

La tenica algoritmica del divide et impera. L' Algoritmo di ordinamento Θ(nlog n) mergesort e la sua funzione "fondi" di tempo Θ(n). lez09A1Ordinamento2Merge25.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.- L'analisi al caso medio Θ(n log n) lez10A1Ordinamento3Quik25.pdf

Settimana 7 - 7 Aprile

Richiami sugli algoritmi di ordinamento del quickSort e del MergeSort di cui abbiamo parlato la volta scorsa Lez12bA1riassunto25.pdf

Esericizi risolti su equazioni di ricorrenza per l'esonero prossimo venturo 07_EserciziEqRicorrenza2025.pdf

Settimana 7 - 11 Aprile

Algoritmo di ordinamento heap sort La struttura dati heap minimo. Implementazione della funzione di heappop() in O(log n), implementazione della funzione di heappush() in tempo O(log n) e implementazione della funzione heapify in tempo Θ(n). lez11A1HeapSort25.pdf

Settimana 8 - 14 Aprile

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. ESERCIZI lez13A1struttureDati1.pdf

Settimana 8 - 18 Aprile

Pasqua

Settimana 9 - 21 Aprile

Pasqua

Settimana 9 - 25 Aprile

Liberazione

Settimana 10 - 28 Maggio

Pile e code su array e su liste concatenate. Implementazione tramite array e tramite liste concatenate in modo da avere tempi d'esecuzione Θ(1) sia per l'inserimento che per la cancellazione. lez14A2PileCode.pdf

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. Rappresentazione di alberi tramite puntatori. lez16A1Alberi25.pdf

Settimana 10 - 2 Maggio

ponte del primo maggio

Settimana 11 - 5 Maggio

lezione saltata

Settimana 11 - 9 Maggio

visite di alberi ed altri esercizi su alberi rappresentati tramite puntatore. lez17A1VisiteAlberi25.pdf

Settimana 12 - 12 Maggio

i dizionari e gli alberi binari di ricerca lez19A1ABR25.pdf

Settimana 12 - 16 Maggio

visite di alberi per livello (con l'ausilio di una coda) , vedi appunti di lezione 17

esercizi tra cui esercizi risolti dell'esonero dell'anno scorso SecondoEsonero24Soluzione.pdf

Settimana 13 - 19 Maggio

esercizi risolti su alberi binari: lez21A1EserciziAlberi1.pdf

Settimana 13 - 23 Maggio

dizionari e tabelle hash lez22A1Dizionari1.pdf

Eserzizi su liste concatenate progettare algoritmi nella versione ricorsiva ed in quella iterativa per ciascuno di questi due problemi:

1) l'algoritmo prende il puntatore alla testa di una lista concatenata e in tempo O(n), dove n è il numero di nodi della lista, restituisce la somma delle chiavi a valore pari dei nodi della lista.

2) l'algoritmo prende il puntatore alla testa di una lista concatenata e in tempo O(n), dove n è il numero di nodi della lista, restituisce cancella l'ultimo nodo della lista e restituisce il puntatore alla testa (che puo' eventualmente essere cambiato). Nel caso di lista vuota restituisce None.

Settimana 14 - 26 Maggio

ESERCIZI preparatori all'esonero:

1) qual'e' il numero di nodi foglia che puo' avere al massimo un albero quaternario? e qual'è il numero di nodi interni che può avere al massimo?

2) dato il puntatore ad un albero binario memorizzato tramite nodi e puntatori, progettare una funzione che restituisce la rappresentazione dell'albero tramite il vettore dei padri. La procedura deve avere complessità O(n) dove n è il numero di nodi.

3) lo sbilanciamento di un nodo è il valore assoluto tr ail numero di nodi presente nel suo sottoalbero di sinistra ed il numero di nodi presenti nel suo sottoalbero destro. Progettare un algoritmo che dato il puntatore alla radice di un albero rappresentato tramite nodi e puntatori restituisce lo sbilanciamento massimo tra quelli dei suoi nodi. L'algoritmo deve avere complessità O(n).

4) dimostrare che in un albro binario di n nodi vale h = Ω(log n)

<a name="Settimana 14 - 29 Maggio"></a>Settimana 14 - 30 Maggio

secondo esonero del corso tenuto nell'aula 11 di via scarpa dalle 17 alle 19

Settimana 14 - 30 Maggio

Soluzioni agli esercizi assegnati nell'esonero del 29 maggio.