ProgrammaDelCorso < Intro

---+++ <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, &#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
<!--
   * Grafi
      * rappresentazione in memoria
         * liste di adiacenza
         * matrice di adiacenza
         * matrice di incidenza
         * lista di archi
         * confronto del costo computazionale in termini di spazio e tempo in alcune operazioni elementari 
      * visita in ampiezza (BFS)
         * definizione di albero ricoprente
         * proprietà degli archi non dell'albero
         * proprieta' della distanza dalla radice 
      * visita in profondità (DFS)
         * proprietà degli archi non dell'albero
         * proprietà del numero di archi in funzione della lunghezza del cammino più lungo 
      * similitudini e differenze tra le due visite
      * loro costo computazionale al variare della struttura dati usata
      * esempi di utilizzo delle visite
</font>
-->

<!-- Start of StatCounter Code -->
<script type="text/javascript">
var sc_project=6759759; 
var sc_invisible=1; 
var sc_security="81bd8f62"; 
</script>

<script type="text/javascript"
src="http://www.statcounter.com/counter/counter.js"></script><noscript><div
class="statcounter"><a title="joomla visitor"
href="http://statcounter.com/joomla/" target="_blank"><img
class="statcounter"
src="http://c.statcounter.com/6759759/0/81bd8f62/1/"
alt="joomla visitor" ></a></div></noscript>
<!-- End of StatCounter Code -->
This topic: Intro_algo/AD > WebHome > ProgrammaDelCorso
Topic revision: r4 - 2025-02-06 - TizianaCalamoneri