DiarioDelleLezioni < Intro

Tags: view all tags
---+++ <font color="green" size="+2"> Diario delle lezioni</font>

---+++ <font color="red" size="+1"> *A.A. 2024/2025* </font>

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

*%BLUE% Lunedì 3 Marzo 2025 - 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)*
   * Definizione e significato degli insiemi O e &Omega;


*%BLUE% Giovedì 6 Marzo 2025 - 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ì 10 Marzo 2025 - Lezioni 6-7* %ENDCOLOR%

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

%BLUE% *Giovedì 13 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ì 17 Marzo 2025 - 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/6)*
   * metodi risolutivi (1/3):
      * metodo iterativo - esempi

%BLUE% *Giovedì 20 Marzo 2025 - Lezioni 13-14-15* %ENDCOLOR%


*Soluzioni delle equazioni di ricorrenza (2/6)*
   * metodi risolutivi (2/3):
      * metodo iterativo - esempi
      * metodo di sostituzione - esempi
      * metodo dell'albero - esempi

%BLUE% *Lunedì 24 Marzo 2025 - Lezioni 16-17* %ENDCOLOR%

*Soluzioni delle equazioni di ricorrenza (3/6)*
   * metodi risolutivi (3/3):
      * metodo principale - esempi
   * esempi di soluzione di equazioni di ricorrenza (1/4)


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

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

*Il problema dell'ordinamento (1/6)*
   * algoritmi naif: insertion sort, selection sort, bubble sort; calcolo del costo computazionale;
   * albero delle decisioni e teorema sulla limitazione inferiore per il costo computazionale di un algoritmo per confronti


%BLUE% *Lunedì 31 Marzo 2025 - Lezioni 21-22* %ENDCOLOR%

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

*Il problema dell'ordinamento (2/6)*
   * algoritmi efficienti (1):
      * paradigma del Divide et Impera
      * merge sort (pseudocodice e costo computazionale, pseudocodice della funzione Fondi)


%BLUE% *Giovedì 3 Aprile 2025 - Lezioni 23-24-25*  %ENDCOLOR%
*Soluzioni delle equazioni di ricorrenza (6/6)*
   * esempi di soluzione di equazioni di ricorrenza (4/4)

*Il problema dell'ordinamento (3/6)*
   * 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)

%BLUE% *Lunedì 7 Aprile 2025 - Lezioni 26-27* %ENDCOLOR%

*Il problema dell'ordinamento (4/6)*
   * algoritmi efficienti (2/3):
      * quick sort (randomizzazione)
   *Alcuni esercizi svolti*

%BLUE% *Giovedì 10 Aprile 2025 - Lezioni 28-29-30* %ENDCOLOR%
*Il problema dell'ordinamento (5/6)*
   * algoritmi efficienti (3/3):
      * heap sort: struttura dati heap; Heapify (pseudocodice e costo computazionale) e BuildHeap (pseudocodice)
      * Heap sort (pseudocodice e costo computazionale)

*PRIMA PROVA INTERMEDIA*

%BLUE% *Lunedì 14 Aprile 2025 - Lezioni 31-32* %ENDCOLOR%
*Il problema dell'ordinamento (6/6)*
   * algoritmi lineari
      * counting sort (versione semplificata e versione completa)
      * bucket sort (idea)

%RED% *Vacanze Pasquali e Ponte con il 25 Aprile* %ENDCOLOR%

%BLUE% *Lunedì 28 Aprile 2025 - Lezioni 33-34* %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

%RED% *Giovedì 1 Maggio: festa* %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


<!--LA ROBA QUI SOTTO SI PUO' CANCELLARE: C'E' GIA' UNA COPIA IN ANNI PRECEDENTI



<b>%BLUE% Giovedì 29 Maggio 2024 - Lezioni 51-52-53 </b>%ENDCOLOR%

NO LEZIONE (ci sono 2 esoneri) - segnare ore esonero su Gomp?

FINE SEMESTRE - RIMANGONO FUORI I B-ALBERI ED ALCUNI ESERCIZI

<b>%BLUE% Giovedì 23 Maggio 2024 - Lezioni 53-54-55 </b>%ENDCOLOR%

Esercizi riepilogativi


-->

<!-- 
questo è un commento
-->

AnniPrecedenti