Diario delle lezioni
A.A. 2023/2024
Trovate in questa pagina il dettaglio degli argomenti svolti; il pdf delle slides utilizzate è
qui.
Lunedì 26 Febbraio 2024 - Lezioni 1-2
Introduzione
- Informazioni sul corso.
- Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale.
Giovedì 29 Febbraio 2024 - Lezioni 3-4-5
Notazione asintotica
- Definizione e significato degli insiemi O, Ω e Θ
- Algebra della notazione asintotica
- Metodo del limite
- Esempi
Lunedì 4 Marzo 2024 - Lezioni 6-7
Valutazione del costo computazionale (1)
- Pseudocodice
- Valutazione del costo computazionale di un algoritmo
- Un primo esempio
- Esempi di problemi che si possono risolvere in modo più o meno efficiente e loro costo computazionale
- somma dei primi n interi
- valutazione di un polinomio in un punto
Giovedì 7 Marzo 2024 - Lezioni 8-9-10
Valutazione del costo computazionale (2)
Il problema della ricerca
- ricerca sequenziale e suo costo computazionale nel caso migliore, peggiore e medio
- ricerca binaria e suo costo computazionale nel caso migliore, peggiore e medio
Lunedì 11 Marzo 2024 - Lezioni 11-12
Ricorsione (1)
- funzioni matematiche ricorsive
- algoritmi ricorsivi
- fattoriale: pseudocodice iterativo e ricorsivo;
- ricerca sequenziale: pseudocodice ricorsivo;
- ricerca binaria: pseudocodice ricorsivo;
- equazione di ricorrenza degli algoritmi ricorsivi già visti (fattoriale; ricerca sequenziale; ricerca binaria; numeri di Fibonacci)
- esempi di algoritmi ricorsivi (potenza di n alla k, somma degli elementi di un array, minimo in un array, array palindromo): pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza.
Giovedì 14 Marzo 2024 - Lezioni 13-14-15
Ricorsione (2)
- esempi di algoritmi ricorsivi (stampa dei valori in un array, Torri di Hanoi): pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;
Soluzioni delle equazioni di ricorrenza (1)
- metodi risolutivi (1):
- metodo iterativo
- metodo di sostituzione;
- metodo dell'albero.
Lunedì 18 Marzo 2024 - Lezioni 16-17
Soluzioni delle equazioni di ricorrenza (2)
- metodi risolutivi (2):
- esempi di soluzione di equazioni di ricorrenza (1)
Giovedì 21 Marzo 2024 - Lezioni 18-19-20
Soluzioni delle equazioni di ricorrenza (3)
- esempi di soluzione di equazioni di ricorrenza (2)
Il problema dell'ordinamento (1)
- algoritmi naif: insertion sort, selection sort, bubble sort; calcolo del costo computazionale;
Lunedì 24 Marzo 2024 - Lezioni 21-22
Soluzioni delle equazioni di ricorrenza (4)
- esempi di soluzione di equazioni di ricorrenza (3)
Il problema dell'ordinamento (2)
- albero delle decisioni e teorema sulla limitazione inferiore per il costo computazionale di un algoritmo per confronti
Giovedì 28 Marzo 2024 e Lunedì 1 Aprile 2024 vacanze Pasquali
Giovedì 4 Aprile 2024 - Lezioni 23-24-25
Il problema dell'ordinamento (3)
- algoritmi efficienti (1):
- paradigma del Divide et Impera
- merge sort (pseudocodice e costo computazionale, pseudocodice della funzione Fondi)
- problematica dell'ordinamento in loco: una parentesi sull'uso della memoria secondaria
- quick sort (idea e pseudocodice, costo computazionale nei casi migliore e peggiore)
- pseudocodice della funzione Partiziona
- un esercizio svolto: Tim Sort (Merge Sort + Insertion Sort per il caso base)
Lunedì 8 Aprile 2024 - Lezioni 26-27
Il problema dell'ordinamento (4)
- algoritmi efficienti (2):
- quick sort (costo computazionale nel caso medio, randomizzazione)
Giovedì 11 Aprile 2024 - Lezioni 28-29-30
Il problema dell'ordinamento (5)
- algoritmi efficienti (3):
- heap sort: struttura dati heap; Heapify (pseudocodice e costo computazionale) e BuildHeap (pseudocodice)
- Heap sort (pseudocodice e costo computazionale)
Lunedì 15 Aprile 2024 - Lezioni 31-32
Il problema dell'ordinamento (4)
- algoritmi lineari
- counting sort (versione semplificata e versione completa)
- bucket sort (idea)
Strutture dati fondamentali (1)
- strutture dati ed insiemi dinamici
- confronto tra array qualunque e array ordinato
Giovedì 18 Aprile 2024 - Lezioni 33-34-35
Strutture dati fondamentali (2)
- liste puntate
- introduzione alle liste concatenate: ricerca e inserimento in testa
- cancellazione nelle liste concatenate
- pila
- coda
- le operazioni enqueue e dequeue
- code con priorità
Lunedì 22 Aprile 2024 - Lezioni 36-37
Strutture dati fondamentali (3)
- Esercizio svolto: simulazione di una coda tramite due pile
- Esercizi svolti sulle liste
Giovedì 25 Aprile 2024 - festa della Liberazione
Lunedì 29 Aprile 2024 - ponte con la festa dei lavoratori
Giovedì 2 Maggio 2024 - Lezioni 38-39-40
Strutture dati fondamentali (4)
- Ancora esercizi svolti sulle liste
- alberi (1)
- definizione tramite la nozione di grafo
- caratterizzazione degli alberi
- memorizzazione degli alberi:
- tramite record e puntatori
- posizionale
- tramite vettore dei padri
- confronto delle tre memorizzazioni * visite di alberi: in-ordine, pre-ordine e post-ordine
- pseudocodice ricorsivo per memorizzazione con record e puntatori
- costo computazionale tramite equazione di ricorrenza e metodo di sostituzione
- esercizi che si risolvono utilizzando le visite: numero di nodi di un albero, ricerca in un albero
AnniPrecedenti