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 2023 - 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)
- cosa non va nel merge sort: una parentesi sull'uso della memoria secondaria
- quick sort (idea e pseudocodice)
- pseudocodice della funzione Partiziona
- un esercizio svolto: Tim Sort (Merge Sort + Insertion Sort per il caso base)
AnniPrecedenti
This topic: Intro_algo/AD
> WebHome > DiarioDelleLezioni
Topic revision: r77 - 2024-03-26 - TizianaCalamoneri