Programma di massima A.A. 2023/24

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

• Introduzione
  • Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale;
  • modello RAM; misura di costo uniforme e logaritmico.
• Notazione asintotica
  • Definizione e significato degli insiemi O, Ω e Θ
• Il problema della ricerca
  • Ricerca sequenziale in un vettore disordinato;
  • costo computazionale nel caso migliore, peggiore e medio
  • Ricerca dicotomica o binaria in un vettore ordinato (vers. iterativa)
  • costo computazionale nel caso migliore, peggiore e medio
• Introduzione alla ricorsione
  • funzioni ricorsive
  • versione iterativa e ricorsiva di algoritmi: esempi
  • occupazione in memoria: l'esempio del calcolo dei numeri di Fibonacci
  • calcolo del costo computazionale delle funzioni ricorsive tramite equazioni di ricorrenza
    • metodo di sostituzione
    • metodo iterativo
    • metodo dell'albero
    • teorema principale ( dimostrazione facoltativa )
• 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
  • heap e heap sort
• Strutture dati fondamentali
  • insiemi dinamici ed operazioni su di essi
  • vettore non ordinato e ordinato
  • pila e coda, funzioni di inserimento ed estrazione, coda circolare
  • lista semplice e doppiamente puntata
  • coda con priorità
  • albero
    • definizione come grafo connesso aciclico
    • teorema di caratterizzazione degli alberi e dimostrazione
    • 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 e calcolo del costo computazionale tramite equazione di ricorrenza
• 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, successore e predecessore 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 red black e teorema per la limitazione dell'altezza ( rotazioni ed altri dettagli facoltativi )