DiarioDelleLezioni < Algoritmi1

---+++ <font color="green" size="+2"> *Diario delle lezioni A.A. 2025/2026* </font>

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


Trovate in questa pagina il dettaglio degli argomenti svolti; il pdf delle slides utilizzate è [[https://twiki.di.uniroma1.it/twiki/view/Algoritmi1/Slides][qui]].

*%BLUE% Lunedì 23 Febbraio 2026 - Lezioni 1-2* %ENDCOLOR%

*Introduzione*
   * Informazioni sul corso.
   * Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale.

*Notazione asintotica (1/2)*
   * Ripasso della definizione e significato degli insiemi O e &Omega;

*%BLUE% Giovedì 26 Febbraio 2026 - Lezioni 3-4-5* %ENDCOLOR%

*Notazione asintotica (2/2)*
   * Definizione e significato dell'insieme &Theta;
   * Algebra della notazione asintotica
   * Metodo del limite
   * Esempi

*Valutazione del costo computazionale (1/2)*
   * Pseudocodice
   * Valutazione del costo computazionale di un algoritmo
   * Un primo esempio
   * Esempi di problemi che si possono risolvere in modo più o meno efficiente e loro costo computazionale
      * somma dei primi n interi
      * valutazione di un polinomio in un punto


%BLUE% *Lunedì 2 Marzo 2026 - Lezioni 6-7* %ENDCOLOR%

*Valutazione del costo computazionale (2/2)*
   * Esercizi svolti

%BLUE% *Giovedì 5 Marzo 2025 - Lezioni 8-9-10* %ENDCOLOR%

*Il problema della ricerca*
   * ricerca sequenziale e suo costo computazionale nel caso migliore, peggiore e medio
   * ricerca binaria e suo costo computazionale nel caso migliore, peggiore e medio

*Ricorsione (1/2)*
   * funzioni matematiche ricorsive
   * algoritmi ricorsivi
   * fattoriale: pseudocodice iterativo e ricorsivo;
   * ricerca sequenziale: pseudocodice ricorsivo;
   * ricerca binaria: pseudocodice ricorsivo;
   * equazione di ricorrenza degli algoritmi ricorsivi già visti (fattoriale; ricerca sequenziale; ricerca binaria; numeri di Fibonacci)

%BLUE% *Lunedì 9 Marzo 2026 - Lezioni 11-12* %ENDCOLOR%

*Ricorsione (2/2)*
   * esempi di algoritmi ricorsivi (potenza di n alla k, somma degli elementi di un array, minimo in un array, array palindromo): pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza.
   * esempi di algoritmi ricorsivi (stampa dei valori in un array, Torri di Hanoi): pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;

*Soluzioni delle equazioni di ricorrenza (1/5)*
   * metodi risolutivi (1/2):
      * metodo iterativo - esempi
      * una parentesi sugli alberi binari completi


%BLUE% *Giovedì 12 Marzo 2026 - Lezioni 13-14-15* %ENDCOLOR%


*Soluzioni delle equazioni di ricorrenza (2/5)*
   * metodi risolutivi (2/2):
      * metodo dell'albero - esempi
      * metodo di sostituzione - esempi
      * metodo principale - esempi
   * esempi di soluzione di equazioni di ricorrenza (1/4)

%BLUE% *Lunedì 16 Marzo 2026 - Lezioni 16-17* %ENDCOLOR%

*Soluzioni delle equazioni di ricorrenza (3/5)*
   * esempi di soluzione di equazioni di ricorrenza (2/4)

*Il problema dell'ordinamento (1/4)*
   * ripasso degli algoritmi naif: insertion sort, selection sort, bubble sort; calcolo del costo computazionale
   * albero delle decisioni 

%BLUE% *Giovedì 19 Marzo 2026 - Lezioni 18-19-20* %ENDCOLOR%

*Soluzioni delle equazioni di ricorrenza (4/5)*
   * esempi di soluzione di equazioni di ricorrenza (3/4)

*Il problema dell'ordinamento (2/4)*
   * teorema sulla limitazione inferiore per il costo computazionale di un algoritmo per confronti
   * algoritmi efficienti (1/3):
      * paradigma del Divide et Impera
      * merge sort (pseudocodice e costo computazionale, pseudocodice della funzione Fondi)
      * problematica dell'ordinamento in loco: una parentesi sull'uso della memoria secondaria
      * un esercizio svolto: Tim Sort (Merge Sort + Insertion Sort per il caso base)
      * quick sort (idea e pseudocodice, costo computazionale in due casi di studio, caso medio)


%RED% *Lunedì 23 Marzo 2026 - NO Lezione per elezioni* %ENDCOLOR%

%BLUE% *Giovedì 26 Marzo 2026 - Lezioni 21-22-23*  %ENDCOLOR%

*Soluzioni delle equazioni di ricorrenza (5/5)*
   * esempi di soluzione di equazioni di ricorrenza (4/4)

*Il problema dell'ordinamento (3/4)*
   * algoritmi efficienti (2/3):
      * quick sort (randomizzazione)
   * struttura dati heap (1/2); funzione Heapify (pseudocodice e costo computazionale)

%BLUE% *Lunedì 30 Marzo 2026 - Lezioni 26-27* %ENDCOLOR%

*Il problema dell'ordinamento (4/4)*
   * struttura dati heap (2/2):
      * funzione Build Heap (pseudocodice e costo computazionale)
      * funzione Heapify Bottom Up (pseudocodice e costo computazionale)
      * funzioni di inserimento e cancellazione
   * algoritmi efficienti (3/3):
       * Heap sort (pseudocodice e costo computazionale)
   * algoritmi lineari
      * counting sort (versione semplificata e versione completa)
      * bucket sort (idea)

%RED% *giovedì 1/4-mercoledì 8/4 2026 - vacanze pasquali* %ENDCOLOR%

%RED% *giovedì 9/4-mercoledì 15/4 2026 - interruzione della didattica per appelli straordinari* %ENDCOLOR%

%BLUE% *Giovedì 16 Aprile 2026 - Lezioni 28-29-30* %ENDCOLOR%

*Strutture dati fondamentali (1)*
   * strutture dati ed insiemi dinamici
   * confronto tra array qualunque e array ordinato
   * liste puntate
      * Introduzione alle liste puntate semplici: ricerca, inserimento in testa o dopo un record prestabilito





<!-- PORTARE SU QUANTO SERVE



%BLUE% *Lunedì 14 Aprile 2025 - Lezioni 31-32* %ENDCOLOR%

%BLUE% *Lunedì 28 Aprile 2025 - Lezioni 33-34* %ENDCOLOR% 


%BLUE% *Lunedì 5 Maggio 2025 - Lezioni 35-36* %ENDCOLOR%

*Strutture dati fondamentali (2)*
   * liste puntate
      * cancellazione nelle liste concatenate
      * esercizi riepilogativi sulle liste
   * pila
      * definizione come struttura dati astratta ed esempi

%BLUE% *Giovedì 8 Maggio 2025 - Lezioni 37-38* %ENDCOLOR%
*Strutture dati fondamentali (3)*
   * pila
      * le operazioni Push e Pop
   * coda
      * definizione come struttura dati astratta ed esempi
      * le operazioni enqueue e dequeue
   * code con priorità
   * Esercizio svolto: simulazione di una coda tramite due pile
   * Esercizi svolti sulle liste

%BLUE% *Lunedì 12 Maggio 2025 - Lezioni 39-40* %ENDCOLOR%

*Strutture dati fondamentali (4)*
   * alberi (1)
      * definizione tramite la nozione di grafo
      * caratterizzazione degli alberi
      * memorizzazione degli alberi:
         * tramite record e puntatori
         * posizionale
         * tramite vettore dei padri
         * confronto delle tre memorizzazioni
   * Ancora esercizi svolti sulle liste


<b>%BLUE% Giovedì 15 Maggio 2025 - Lezioni 41-42-43 </b>%ENDCOLOR%

*Strutture dati fondamentali (5)*
   * alberi (2)
    * visite di alberi: in-ordine, pre-ordine e post-ordine
         * pseudocodice ricorsivo per memorizzazione con record e puntatori
         * costo computazionale tramite equazione di ricorrenza e metodo di sostituzione
         * esercizi che si risolvono utilizzando le visite: numero di nodi di un albero, ricerca in un albero
         * pseudocodice ricorsivo per memorizzazione con vettore dei padri e costo computazionale
         * visita per livelli
         * esercizi svolti: calcolo dell'altezza e del numero di nodi ad un dato livello

   * Alberi binari di ricerca (ABR) (1/2):
      * definizione e proprietà dell' "ordinamento orizzontale"
      * algoritmo per la ricerca
      * osservazioni sul costo computazionale delle operazioni viste come funzione dell'altezza

Durante una pausa: Questionario OPIS in aula - codice BUQYP1LT


<b>%BLUE% Lunedì 19 Maggio 2025 - Lezioni 44-45 </b>%ENDCOLOR%


*Strutture dati fondamentali (6)*
   * Alberi binari di ricerca (ABR) (2/2):
      * algoritmo per il massimo e minimo
      * algoritmo per il successore e predecessore
      * algoritmo di inserimento
      * algoritmo di cancellazione
      * Esercizi svolti sugli ABR
   * alberi bilanciati: AVL
      * definizione
      * dimostrazione dell'altezza logaritmica
      * rotazioni

<b>%BLUE% Giovedì 22 Maggio 2024 - Lezioni 46-47-48 </b>%ENDCOLOR%

*Strutture dati fondamentali (7)*
   * dizionari
      * tabelle ad indirizzamento diretto
      * tabelle hash
         * collisioni
         * liste di trabocco
         * tabelle ad indirizzamento aperto
         * tabelle hash
            * hashing doppio

*Esercizi riepilogativi*

<b>%BLUE% Lunedì 26 Maggio 2025 - Lezioni 49-50 </b>%ENDCOLOR%

Esercizi riepilogativi
-->
[[https://twiki.di.uniroma1.it/twiki/view/Algoritmi1/Algoritmi1PrimoCanale][home]]


<!-- 
questo è un commento
-->
This topic: Algoritmi1 > WebHome > Algoritmi1PrimoCanale > DiarioDelleLezioni
Topic revision: r13 - 2026-03-30 - TizianaCalamoneri