Diario delle lezioni A.A. 2025/2026

home

Trovate in questa pagina il dettaglio degli argomenti svolti; il pdf delle slides utilizzate è qui.

Lunedì 23 Febbraio 2026 - 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.

Notazione asintotica (1/2)

• Ripasso della definizione e significato degli insiemi O e Ω

Giovedì 26 Febbraio 2026 - Lezioni 3-4-5

Notazione asintotica (2/2)

• Definizione e significato dell'insieme Θ
• Algebra della notazione asintotica
• Metodo del limite
• Esempi

Valutazione del costo computazionale (1/2)

• 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

Lunedì 2 Marzo 2026 - Lezioni 6-7

Valutazione del costo computazionale (2/2)

• Esercizi svolti

Giovedì 5 Marzo 2025 - Lezioni 8-9-10

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

Ricorsione (1/2)

• 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)

Lunedì 9 Marzo 2026 - Lezioni 11-12

Ricorsione (2/2)

• 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.
• 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/2):
  • metodo iterativo - esempi
  • una parentesi sugli alberi binari completi

Giovedì 12 Marzo 2026 - Lezioni 13-14-15

Soluzioni delle equazioni di ricorrenza (2)

• metodi risolutivi (2/2):
  • metodo dell'albero - esempi
  • metodo di sostituzione - esempi
  • metodo principale - esempi
• esempi di soluzione di equazioni di ricorrenza (1)

Lunedì 16 Marzo 2026 - Lezioni 16-17

Soluzioni delle equazioni di ricorrenza (3)

• esempi di soluzione di equazioni di ricorrenza (2)

Il problema dell'ordinamento (1/6)

• ripasso degli algoritmi naif: insertion sort, selection sort, bubble sort; calcolo del costo computazionale
• albero delle decisioni

Giovedì 19 Marzo 2026 - Lezioni 18-19-20

Soluzioni delle equazioni di ricorrenza (4)

• esempi di soluzione di equazioni di ricorrenza (3)

Il problema dell'ordinamento (2/6)

• teorema sulla limitazione inferiore per il costo computazionale di un algoritmo per confronti
• 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
  • un esercizio svolto: Tim Sort (Merge Sort + Insertion Sort per il caso base)
  • quick sort (idea e pseudocodice, costo computazionale in due casi di studio, caso medio)

Lunedì 23 Marzo 2026 - NO Lezione per elezioni

home