ProgrammaDelCorso < Algoritmi1

---+++ <font color=green size="+2"> *Programma di massima A.A. 2025/26* </font>
(questo è un programma di massima; per il programma dettagliato consultare il diario delle lezioni)

[[https://twiki.di.uniroma1.it/twiki/view/Algoritmi1/Algoritmi1PrimoCanale][home]]


   * Introduzione
      * Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale;
      * modello RAM; misura di costo uniforme e logaritmico. 
   * Notazione asintotica
      * Ripasso della definizione e del significato degli insiemi O, &#937; e &#920;
   * 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 (<font color=grey> dimostrazione facoltativa </font>)
   * 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 AVL e teorema per la limitazione dell'altezza
         * B-alberi

[[https://twiki.di.uniroma1.it/twiki/view/Algoritmi1/Algoritmi1PrimoCanale][home]]
This topic: Algoritmi1 > WebHome > Algoritmi1PrimoCanale > ProgrammaDelCorso
Topic revision: r2 - 2026-02-17 - TizianaCalamoneri