AngeloMonti < Intro_algo/PZ

Tags: view all tags

---+++ <font color="green" size="+2">Programma di massima A.A. 2024/25</font>
---+++++ (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, &Omega; e &Theta;
   * 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 
   * 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
      * lista semplice e doppiamente 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 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
         * scansione lineare
         * 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 AVL teorema per la limitazione dell'altezza (<font color="grey"> ribilanciamento tramite rotazioni </font>)
         * B-alberi