Diario delle lezioni

A.A. 2024/2025

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

Lunedì 3 Marzo 2025 - 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)

• Definizione e significato degli insiemi O e Ω

Giovedì 6 Marzo 2025 - 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ì 10 Marzo 2025 - Lezioni 6-7

Valutazione del costo computazionale (2/2)

• Esercizi svolti

Giovedì 13 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ì 17 Marzo 2025 - 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/6)

• metodi risolutivi (1/3):
  • metodo iterativo - esempi

Giovedì 20 Marzo 2025 - Lezioni 13-14-15

Soluzioni delle equazioni di ricorrenza (2/6)

• metodi risolutivi (2/3):
  • metodo iterativo - esempi
  • metodo di sostituzione - esempi
  • metodo dell'albero - esempi

Lunedì 24 Marzo 2025 - Lezioni 16-17

Soluzioni delle equazioni di ricorrenza (3/6)

• metodi risolutivi (3/3):
  • metodo principale - esempi
• esempi di soluzione di equazioni di ricorrenza (1/4)

Giovedì 27 Marzo 2025 - Lezioni 18-19-20

Soluzioni delle equazioni di ricorrenza (4/6)

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

Il problema dell'ordinamento (1/6)

• algoritmi naif: insertion sort, selection sort, bubble sort; calcolo del costo computazionale;
• albero delle decisioni e teorema sulla limitazione inferiore per il costo computazionale di un algoritmo per confronti

Lunedì 31 Marzo 2025 - Lezioni 21-22

Soluzioni delle equazioni di ricorrenza (5/6)

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

Il problema dell'ordinamento (2/6)

• algoritmi efficienti (1):
  • paradigma del Divide et Impera
  • merge sort (pseudocodice e costo computazionale, pseudocodice della funzione Fondi)

Giovedì 3 Aprile 2025 - Lezioni 23-24-25 Soluzioni delle equazioni di ricorrenza (6/6)

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

Il problema dell'ordinamento (3/6)

• 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ì 7 Aprile 2025 - Lezioni 26-27

Il problema dell'ordinamento (4/6)

• algoritmi efficienti (2/3):
  • quick sort (randomizzazione) Alcuni esercizi svolti

Giovedì 10 Aprile 2025 - Lezioni 28-29-30 Il problema dell'ordinamento (5/6)

• algoritmi efficienti (3/3):
  • heap sort: struttura dati heap; Heapify (pseudocodice e costo computazionale) e BuildHeap (pseudocodice)
  • Heap sort (pseudocodice e costo computazionale)

PRIMA PROVA INTERMEDIA

Lunedì 14 Aprile 2025 - Lezioni 31-32 Il problema dell'ordinamento (6/6)

• algoritmi lineari
  • counting sort (versione semplificata e versione completa)
  • bucket sort (idea)

Vacanze Pasquali e Ponte con il 25 Aprile

Lunedì 28 Aprile 2025 - Lezioni 33-34

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

Giovedì 1 Maggio: festa

Lunedì 5 Maggio 2025 - Lezioni 35-36

Strutture dati fondamentali (2)

• liste puntate
  • cancellazione nelle liste concatenate
  • esercizi riepilogativi sulle liste
• pila
  • definizione come struttura dati astratta ed esempi

Giovedì 8 Maggio 2025 - Lezioni 37-38 Strutture dati fondamentali (3)

• pila
  • le operazioni Push e Pop
• coda
  • definizione come struttura dati astratta ed esempi
  • le operazioni enqueue e dequeue
• code con priorità
• Esercizio svolto: simulazione di una coda tramite due pile
• Esercizi svolti sulle liste

Lunedì 12 Maggio 2025 - Lezioni 39-40

Strutture dati fondamentali (4)

• 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
• Ancora esercizi svolti sulle liste

Giovedì 15 Maggio 2025 - Lezioni 41-42-43

Strutture dati fondamentali (5)

• alberi (2) * 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
    • pseudocodice ricorsivo per memorizzazione con vettore dei padri e costo computazionale
    • visita per livelli
    • esercizi svolti: calcolo dell'altezza e del numero di nodi ad un dato livello

• Alberi binari di ricerca (ABR) (1/2):
  • definizione e proprietà dell' "ordinamento orizzontale"
  • algoritmo per la ricerca
  • osservazioni sul costo computazionale delle operazioni viste come funzione dell'altezza

Durante una pausa: Questionario OPIS in aula - codice BUQYP1LT

Lunedì 19 Maggio 2025 - Lezioni 44-45

Strutture dati fondamentali (6)

• Alberi binari di ricerca (ABR) (2/2):
  • algoritmo per il massimo e minimo
  • algoritmo per il successore e predecessore
  • algoritmo di inserimento
  • algoritmo di cancellazione
  • Esercizi svolti sugli ABR
• alberi bilanciati: AVL
  • definizione
  • dimostrazione dell'altezza logaritmica
  • rotazioni

Giovedì 22 Maggio 2024 - Lezioni 46-47-48

Strutture dati fondamentali (7)

• dizionari
  • tabelle ad indirizzamento diretto
  • tabelle hash
    • collisioni
    • liste di trabocco
    • tabelle ad indirizzamento aperto
    • tabelle hash
      • hashing doppio

Esercizi riepilogativi

Lunedì 26 Maggio 2025 - Lezioni 49-50

Esercizi riepilogativi

AnniPrecedenti