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/5)

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

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

Lunedì 16 Marzo 2026 - Lezioni 16-17

Soluzioni delle equazioni di ricorrenza (3/5)

• esempi di soluzione di equazioni di ricorrenza (2/4)

Il problema dell'ordinamento (1/4)

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

• esempi di soluzione di equazioni di ricorrenza (3/4)

Il problema dell'ordinamento (2/4)

• teorema sulla limitazione inferiore per il costo computazionale di un algoritmo per confronti
• algoritmi efficienti (1/3):
  • 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

Giovedì 26 Marzo 2026 - Lezioni 21-22-23

Soluzioni delle equazioni di ricorrenza (5/5)

• esempi di soluzione di equazioni di ricorrenza (4/4)

Il problema dell'ordinamento (3/4)

• algoritmi efficienti (2/3):
  • quick sort (randomizzazione)
• struttura dati heap (1/2); funzione Heapify (pseudocodice e costo computazionale)

Lunedì 30 Marzo 2026 - Lezioni 26-27

Il problema dell'ordinamento (4/4)

• struttura dati heap (2/2):
  • funzione Build Heap (pseudocodice e costo computazionale)
  • funzione Heapify Bottom Up (pseudocodice e costo computazionale)
  • funzioni di inserimento e cancellazione
• algoritmi efficienti (3/3): * Heap sort (pseudocodice e costo computazionale)
• algoritmi lineari
  • counting sort (versione semplificata e versione completa)
  • bucket sort (idea)

giovedì 1/4-mercoledì 8/4 2026 - vacanze pasquali

giovedì 9/4-mercoledì 15/4 2026 - interruzione della didattica per appelli straordinari

Giovedì 16 Aprile 2026 - Lezioni 28-29-30

Strutture dati fondamentali (1)

• strutture dati ed insiemi dinamici
• confronto tra array qualunque e array ordinato
• liste puntate
  • Introduzione alle liste puntate semplici: ricerca, inserimento in testa o dopo un record prestabilito

home