Programma di massima A.A. 2024/25

(questo è un programma di massima; per il programma dettagliato di quest'anno consultare il diario delle lezioni)

• Notazione asintotica
  • Definizione e significato degli insiemi O, Ω e Θ
  • Calcolo della complessità di programmi iterativi
• Il problema della ricerca
  • Ricerca sequenziale in un vettore disordinato;
  • costo computazionale nel caso migliore, peggiore e medio
  • Ricerca binaria in un vettore ordinato (vers. iterativa)
  • costo computazionale nel caso migliore, peggiore e medio
• Introduzione alla ricorsione
  • funzioni ricorsive, esempi
  • calcolo del costo computazionale delle funzioni ricorsive tramite equazioni di ricorrenza
    • metodo di sostituzione
    • metodo iterativo
    • metodo dell'albero
    • teorema principale
• Il problema dell'ordinamento
  • algoritmi naif: filosofia, pseudocodice e costo computazionale
    • insertion, selection e bubble sort
  • limitazione inferiore sul costo computazionale degli algoritmi di ordinamento per confronti; dimostrazione
  • funzione di fusione e merge sort; cenno alla tecnica del divide et impera
  • ordinamento in tempo lineare: counting sort e bucket sort
  • quick sort e suo costo computazionale nel caso peggiore, migliore e medio
• Strutture dati fondamentali
  • Heap e heap sort
  • insiemi statici e insiemi dinamici
  • pila e coda, funzioni di inserimento ed estrazione
  • lista puntata
  • albero
    • alberi radicati, alberi binari, alberi ordinati, alberi binari completi
    • relazioni tra numero di nodi interni, numero di foglie ed altezza in un albero binario completo
    • rappresentazione in memoria di un albero binario
      • rappresentazione posizionale
      • rappresentazione con puntatori
      • vettore dei padri
    • visita in pre-, post- ed in-ordine
• Dizionari
  • indirizzamento diretto
  • tabelle hash
    • collisioni
    • soluzione delle collisioni per concatenazione (liste di trabocco e fattore di carico)
    • costo computazionale nel caso medio
    • soluzioni delle collisioni con indirizzamento aperto
    • vari tipi di scansione (lineare, quadratica ed hashing doppio)
    • costo computazionale nel caso medio
  • alberi binari di ricerca
    • definizione
    • algoritmo di ricerca e suo costo computazionale
    • algoritmi di ricerca del massimo, minimo e loro costo computazionale
    • algoritmo di inserimento e suo costo computazionale
    • algoritmo di cancellazione e suo costo computazionale
  • la problematica del bilanciamento per la limitazione del costo computazionale
    • alberi AVL e teorema per la limitazione dell'altezza
    • B-alberi