AnniPrecedenti < Intro_algo/AD

---+ DIARIO DELLE LEZIONI ANNI PRECEDENTI

---+++ <font color="blue" size="+1"> *A.A. 2023/2024* </font>

*%BLUE% Lunedì 26 Febbraio 2024 - 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.


*%BLUE% Giovedì 29 Febbraio 2024 - Lezioni 3-4-5* %ENDCOLOR%

*Notazione asintotica*
   * Definizione e significato degli insiemi O, &Omega; e &Theta;
   * Algebra della notazione asintotica
   * Metodo del limite
   * Esempi


%BLUE% *Lunedì 4 Marzo 2024 - Lezioni 6-7* %ENDCOLOR%

*Valutazione del costo computazionale (1)*
   * 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% *Giovedì 7 Marzo 2024 - Lezioni 8-9-10* %ENDCOLOR%

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

*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

%BLUE% *Lunedì 11 Marzo 2024 - Lezioni 11-12* %ENDCOLOR%

*Ricorsione (1)*
   * 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)
   * 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.

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

*Ricorsione (2)*
   * 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)*

   * metodi risolutivi (1):
      * metodo iterativo
      * metodo di sostituzione;
      * metodo dell'albero.

%BLUE% *Lunedì 18 Marzo 2024 - Lezioni 16-17* %ENDCOLOR%

*Soluzioni delle equazioni di ricorrenza (2)*

   * metodi risolutivi (2):
      * metodo principale
   * esempi di soluzione di equazioni di ricorrenza (1)

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

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

*Il problema dell'ordinamento (1)*
   * algoritmi naif: insertion sort, selection sort, bubble sort; calcolo del costo computazionale;


%BLUE% *Lunedì 24 Marzo 2024 - Lezioni 21-22* %ENDCOLOR%

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

*Il problema dell'ordinamento (2)*
   * albero delle decisioni e teorema sulla limitazione inferiore per il costo computazionale di un algoritmo per confronti

%RED% *Giovedì 28 Marzo 2024 e Lunedì 1 Aprile 2024* vacanze Pasquali %ENDCOLOR%


%BLUE% *Giovedì 4 Aprile 2024 - Lezioni 23-24-25* %ENDCOLOR%

*Il problema dell'ordinamento (3)*
   * algoritmi efficienti (1):
      * 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
      * quick sort (idea e pseudocodice, costo computazionale nei casi migliore e peggiore)
      * pseudocodice della funzione Partiziona
      * un esercizio svolto: Tim Sort (Merge Sort + Insertion Sort per il caso base)

%BLUE% *Lunedì 8 Aprile 2024 - Lezioni 26-27* %ENDCOLOR%

*Il problema dell'ordinamento (4)*
   * algoritmi efficienti (2):
      * quick sort (costo computazionale nel caso medio, randomizzazione)


%BLUE% *Giovedì 11 Aprile 2024 - Lezioni 28-29-30* %ENDCOLOR%

*Il problema dell'ordinamento (5)*
   * algoritmi efficienti (3):
      * heap sort: struttura dati heap; Heapify (pseudocodice e costo computazionale) e BuildHeap (pseudocodice)
      * Heap sort (pseudocodice e costo computazionale)


%BLUE% *Lunedì 15 Aprile 2024 - Lezioni 31-32* %ENDCOLOR%

*Il problema dell'ordinamento (4)*
   * algoritmi lineari
      * counting sort (versione semplificata e versione completa)
      * bucket sort (idea)

*Strutture dati fondamentali (1)*
   * strutture dati ed insiemi dinamici
   * confronto tra array qualunque e array ordinato


%BLUE% *Giovedì 18 Aprile 2024 - Lezioni 33-34-35* %ENDCOLOR%

*Strutture dati fondamentali (2)*
   * liste puntate
      * introduzione alle liste concatenate: ricerca e inserimento in testa
      * cancellazione nelle liste concatenate
   * pila
      * le operazioni Push e Pop
   * coda
      * le operazioni enqueue e dequeue
   * code con priorità


%BLUE% *Lunedì 22 Aprile 2024 - Lezioni 36-37* %ENDCOLOR%

*Strutture dati fondamentali (3)*
   * Esercizio svolto: simulazione di una coda tramite due pile
   * Esercizi svolti sulle liste

%RED% *Giovedì 25 Aprile 2024 - festa della Liberazione* %ENDCOLOR%

%RED% *Lunedì 29 Aprile 2024 - ponte con la festa dei lavoratori* %ENDCOLOR%


%BLUE% *Giovedì 2 Maggio 2024 - Lezioni 38-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% Lunedì 6 Maggio 2024 - Lezioni 41-42 </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


<b>%BLUE% Giovedì 9 Maggio 2024 - Lezioni 43-44-45 </b>%ENDCOLOR%


*Strutture dati fondamentali (6)*
   * alberi (3)
      * esercizi svolti: calcolo dell'altezza e del numero di nodi ad un dato livello; trasformazione da memorizzazione tramite vettore dei padri a notazione posizionale
   * dizionari
      * tabelle ad indirizzamento diretto
      * tabelle hash
         * collisioni
         * liste di trabocco
         * tabelle ad indirizzamento aperto
         * tabelle hash
            * hashing doppio

*Strutture dati fondamentali (7)*
   * Alberi binari di ricerca (ABR) (1):
      * definizione e proprietà dell' "ordinamento orizzontale"
      * algoritmo per la ricerca

Questionari Opis. Codice: *SIHRI6GK*


<b>%BLUE% Lunedì 13 Maggio 2024 - Lezioni 46-47 </b>%ENDCOLOR%

*Strutture dati fondamentali (7)*
   * Alberi binari di ricerca (ABR) (2):
      * algoritmo per il massimo e minimo
      * algoritmo per il successore e predecessore
      * algoritmo di inserimento
      * osservazioni sul costo computazionale delle operazioni viste come funzione dell'altezza


<b>%BLUE% Giovedì 16 Maggio 2024 - Lezioni 48-49-50 </b>%ENDCOLOR%

*Strutture dati fondamentali (8)*
   * Alberi binari di ricerca (ABR) (3):
      * Esercizi svolti sugli ABR
      * alberi bilanciati: alberi rosso-neri
         * dimostrazione che gli alberi rosso-neri hanno altezza logaritmica
         * rotazioni
         * algoritmo di inserimento


<b>%BLUE% Lunedì 20 Maggio 2024 - Lezioni 51-52 </b>%ENDCOLOR%

Esercizi ripeilogativi

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

Esercizi ripeilogativi

<b>%BLUE% Lunedì 27 Maggio 2024 - Lezioni 56-57 </b>%ENDCOLOR%

Esercizi ripeilogativi


---+  A.A. 2022/2023

*%BLUE% Lunedì 20 Febbraio 2023 - Lezioni 1-2* %ENDCOLOR%

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

*%BLUE% Giovedì 23 Febbraio 2023 - Lezioni 3-4-5* %ENDCOLOR%

*Notazione asintotica*
   * Definizione e significato degli insiemi O, &Omega; e &Theta;
   * Algebra della notazione asintotica
   * Metodo del limite
   * Esempi

*Esercizi assegnati:*
   * Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione
   * Calcolare l'ordine asintotico stretto di alcune funzioni assegnate.

%BLUE% *Lunedì 27 Febbraio 2023 - Lezioni 6-7* %ENDCOLOR%

*Valutazione del costo computazionale (1)*
   * 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

*Esercizi assegnati:*
   * Calcolare il costo computazionale del Selection, dell'Insertion Sort e del Bubble Sort (pseudocodice sulle slides)

%BLUE% *Giovedì 2 Marzo 2023 - Lezioni 8-9-10* %ENDCOLOR%

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

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

%BLUE% *Lunedì 6 Marzo 2023 - Lezioni 11-12* %ENDCOLOR%

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

*Ricorsione (1)*
   * funzioni matematiche ricorsive
   * algoritmi ricorsivi
   * fattoriale: pseudocodice iterativo e ricorsivo;
   * ricerca sequenziale: pseudocodice ricorsivo;
   * ricerca binaria: pseudocodice ricorsivo;

*Esercizi assegnati:*
   * Progettare degli algoritmi che calcolino quanti elementi di un array appartengono all'intervallo chiuso [a,b] sotto varie ipotesi.

%BLUE% *Giovedì 9 Marzo 2023 - Lezioni 13-14-15* %ENDCOLOR%

*Ricorsione (2)*
   * equazione di ricorrenza degli algoritmi ricorsivi già visti (fattoriale; ricerca sequenziale; ricerca binaria; numeri di Fibonacci)
   * esempi di algoritmi ricorsivi (potenza di n alla k, somma degli elementi di un vettore, minimo in un array, vettore palindromo, stampa dei valori in un array, Torri di Hanoi): pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;

Soluzioni delle equazioni di ricorrenza (1)

   * metodi risolutivi (1):
      * metodo iterativo

*Esercizi assegnati:*
   * Progettare degli algoritmi ricorsivi ed esprimerli tramite pseudocodice che risolvano i seguenti problemi:
      * calcolare il coefficiente binomiale n sopra k; 
      * calcolare il MCD tra due interi positivi x ed y come segue:
         * sia y<x
         * se y=0 allora MCD(x,y)=y
         * altrimenti MCD(x,y))MCD(y, x%y) (dove x%y indica il resto della divisione intera tra x e y)

%BLUE% *Lunedì 13 Marzo 2023 - Lezioni 16-17* %ENDCOLOR%

Soluzioni delle equazioni di ricorrenza (2)

   * metodi risolutivi (2):
      * metodo di sostituzione;
      * metodo dell'albero.

*Esercizi assegnati:*
   * Risolvere con i primi tre metodi alcune equazioni di ricorrenza assegnate

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

Soluzioni delle equazioni di ricorrenza (2)

   * metodi risolutivi (3):
      * metodo principale
   * esempi di soluzione di equazioni di ricorrenza (1)

*Esercizi assegnati:*
   * Risolvere con tutti i metodi alcune equazioni di ricorrenza assegnate

%BLUE% *Lunedì 20 Marzo 2022 - Lezioni 21-22* %ENDCOLOR%

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

*Esercizi assegnati:*
   * Risolvere alcune equazioni di ricorrenza assegnate

%BLUE% *Giovedì 23 Marzo 2023 - Lezioni 23-24-25* %ENDCOLOR%

Il problema dell'ordinamento (1)
   * 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
   * algoritmi efficienti (1):
      * paradigma del Divide et Impera

*Esercizi assegnati:*

   * Calcolare il costo computazionale dell'algoritmo di Insertion Sort in cui la posizione dell'elemento da inserire viene determinata tramite ricerca binaria.
   * Scrivere in pseudocodice una funzione che, dato un array A ed un indice j, calcoli il valore minimo nel sottoarray A[j..n]. Riscrivere lo pseudocodice del selection sort che utilizzi ripetutamente questa funzione.
   * Modificare l'algoritmo di Bubble Sort in modo che non prosegua la computazione se l’array risulta ordinato (con l'aggiunta di una flag).
   * Dato un array di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento


%BLUE% *Lunedì 27 Marzo 2023 - Lezioni 26-27* %ENDCOLOR%

Il problema dell'ordinamento (2)
   * algoritmi efficienti (2)
      * merge sort (pseudocodice e costo computazionale, pseudocodice della funzione Fondi, problematica dell'ordinamento in loco)
      * cosa non va nel merge sort: una parentesi sull'uso della memoria secondaria
      * quick sort (idea e pseudocodice)
      * pseudocodice della funzione Partiziona
      * un esercizio svolto: Tim Sort (Merge Sort + Insertion Sort per il caso base)

*Esercizi assegnati:*
   * Scrivere la funzione di fusione ricorsiva
   * Scrivere Merge Sort iterativo

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

Il problema dell'ordinamento (3)
   * quick sort (costo computazionale nei casi migliore e peggiore, costo computazionale nel caso medio, randomizzazione)
   * heap sort: struttura dati heap; Heapify (pseudocodice e costo computazionale) e BuildHeap (pseudocodice)

*Esercizi assegnati:*
   * Sia dato un array di lunghezza n contenente solo valori 0 e 2. Si progetti un algoritmo con costo computazionale lineare che modifichi l'array in modo che tutte le occorrenze di 0 si trovino più a sinistra di tutte le occorrenze di 2.
   * Si considerino i valori 0 1 2 3 4 5 6 7. Si determini una permutazione di questi valori che generi il caso peggiore per l'algortimo Quick sort.
   * Calcolare il costo computazionale del Quick sort nel caso in cui l'array contenga tutti elementi uguali.

%BLUE% *Lunedì 3 Aprile 2023 - Lezioni 31-32* %ENDCOLOR%

Il problema dell'ordinamento (4)
   * algoritmi efficienti:
      * Build Heap (costo computazionale)
      * Heap sort (pseudocodice e costo computazionale)
   * algoritmi lineari
      * counting sort (versione semplificata e versione completa)
      * bucket sort (idea)

*Esercizi assegnati:*
   * Scrivere una funzione che restituisca il valore minimo di un HeapMax e calcolarne il costo computazionale
   * Scrivere Heapsort sfruttando la struttura dati HeapMin
   * Scrivere la funzione di inserimento in un HeapMax e calcolarne il costo computazionale

%RED% *VACANZE PASQUALI: giovedì 6 aprile e lunedì 10 aprile* %ENDCOLOR%

%BLUE% *Giovedì 13 Aprile 2023 - Lezioni 33-34-35* %ENDCOLOR%

Strutture dati fondamentali (1)
   * strutture dati ed insiemi dinamici
   * confronto tra array qualunque e array ordinato
   * introduzione alle liste concatenate: ricerca e inserimento in testa
   * cancellazione nelle liste concatenate

*Esercizi assegnati:*
   * vari esercizi di manipolazione delle liste.

%BLUE% *Lunedì 17 Aprile 2023 - Lezioni 36-37* %ENDCOLOR%

Strutture dati fondamentali (2)
   * pila
      * le operazioni Push e Pop
      * code con priorità
      * la struttura dati coda
      * le operazioni enqueue e dequeue
      * Esercizio svolto: simulazione di una coda tramite due pile
      * Esercizio svolto: inserimento in una lista ordinata (versione iterativa e ricorsiva)

*Esercizi assegnati:*
   * scrivere lo pseudocodice delle funzioni Enqueue e Dequeue quando la coda sia circolare ed implementata su array
   * scrivere lo pseudocodice delle funzioni Pop, Push e Pila_Piena quando la pila sia implementata su array

%BLUE% *Giovedì 20 Aprile 2023 - Lezioni 38-39-40* %ENDCOLOR%

Strutture dati fondamentali (3)
   * Esercizi svolti sulle liste


%RED% *Lunedì 24 Aprile 2023 - Ponte con la festa della Liberazione* %ENDCOLOR%

<b>%BLUE% Giovedì 27 Aprile 2023 - Lezioni 41-42-43 </b>%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
    * 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

*Esercizi assegnati:*
   * scrivere lo pseudocodice di una funzione che, dato un albero in notazione posizionale, lo restituisca tramite vettore dei padri
   * scrivere lo pseudocodice di una funzione che, dato un albero tramite vettore dei padri, lo restituisca in notazione posizionale


<b>%RED% Lunedì 1 Maggio 2023 - Festa del lavoro </b>%ENDCOLOR%

<b>%BLUE% Giovedì 4 Maggio 2023 - Lezioni 44-45-46 </b>%ENDCOLOR%

Strutture dati fondamentali (5)
   * alberi (2)
      * visite di alberi
         * 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; trasformazione da memorizzazione tramite vettore dei padri a notazione posizionale

   * dizionari (1)
      * tabelle ad indirizzamento diretto
      * tabelle hash
         * collisioni
         * liste di trabocco
         * tabelle ad indirizzamento aperto

Questionari Opis. Codice: 4AEFX2KF

*Esercizi assegnati:*
   * Pseudocodice iterativo della visita in preordine

<b>%BLUE% Lunedì 8 Maggio 2023 - Lezioni 47-48 </b>%ENDCOLOR%

   * Strutture dati fondamentali (6)
      * dizionari (2)
         * tabelle hash
            * hashing doppio
   * Alberi binari di ricerca (ABR) (1):
      * definizione e proprietà dell' "ordinamento orizzontale"
      * algoritmo per il massimo e minimo
      * algoritmo per il successore e predecessore
      * algoritmo di inserimento
      * osservazioni sul costo computazionale delle operazioni viste come funzione dell'altezza

<b>%BLUE% Giovedì 11 Maggio 2023 - Lezioni 49-50-51 </b>%ENDCOLOR%

   * Strutture dati fondamentali (7)
      * Alberi binari di ricerca (ABR) (2):
         * Esercizi svolti sugli ABR
         * alberi bilanciati: alberi rosso-neri
            * dimostrazione che gli alberi rosso-neri hanno altezza logaritmica
            * rotazioni
            * algoritmo di inserimento

<b>%BLUE% Lunedì 15 Maggio 2023 - Laurea honoris causa a Silvio Micali </b>%ENDCOLOR%

<b>%BLUE% Giovedì 18 Maggio 2023 - no lezione per indisponibilità dell'aula </b>%ENDCOLOR%

<b>%BLUE% Lunedì 22 Maggio 2023 - Lezioni 52-53 </b>%ENDCOLOR%

Esercizi ripeilogativi

<b>%BLUE% Giovedì 25 Maggio 2023 - Lezioni 54-55-56 </b>%ENDCOLOR%

Esercizi ripeilogativi

<b>%BLUE% Lunedì 29 Maggio 2023 - Lezioni 57-58 </b>%ENDCOLOR%

Esercitazione d'esame


<!--


<b>%BLUE% Martedì 24 Maggio 2022 - Lezioni 58-59 </b>%ENDCOLOR%

   * Esercizi svolti riepilogativi in preparazione dell'esame

<b>%BLUE% Giovedì 26 Maggio 2022 - Lezioni 60-61-62 </b>%ENDCOLOR%

   * Esercizi svolti riepilogativi in preparazione dell'esame

%RED% *Lunedì 15 maggio 2023: sosepensione della didattica in occasione della laurea honoris causa a Silvio Micali* %ENDCOLOR%

---+ A.A. 2021-22


*%BLUE% Martedì 22 Febbraio 2022 - Lezioni 1-2* %ENDCOLOR%

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


*%BLUE% Giovedì 24 Febbraio 2022 - Lezioni 3-4-5* %ENDCOLOR%

*Notazione asintotica*
   * Definizione e significato degli insiemi O, &Omega; e &Theta;
   * Algebra della notazione asintotica
   * Metodo del limite
   * Esempi

*Esercizi assegnati:*
   * Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione
   * Calcolare l'ordine asintotico stretto di alcune funzioni assegnate.


%BLUE% *Martedì 1 Marzo 2022 - Lezioni 6-7* %ENDCOLOR%

*Notazione asintotica*
   * Esercizi svolti

*Esercizi assegnati:*
   * calcolare l'andamento asintotico stretto di alcune funzioni e sommatorie

%BLUE% *Giovedì 3 Marzo 2022 - Lezioni 8-9-10* %ENDCOLOR%

*Valutazione del costo computazionale*
   * 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

*Esercizi assegnati:*
   * Calcolare il costo computazionale del Selection, dell'Insertion Sort e del Bubble Sort (pseudocodice sulle slides)

%BLUE% *Martedì 8 Marzo 2022 - Lezioni 11-12* %ENDCOLOR%

*Valutazione del costo computazionale*
   * Esercizi svolti

%BLUE% *Giovedì 10 Marzo 2022 - Lezioni 13-14-15* %ENDCOLOR%

*Soluzione di alcuni esercizi sulla notazione asintotica*

*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)*
   * funzioni matematiche ricorsive

*Esercizi assegnati:*
   * Progettare degli algoritmi che calcolino quanti elementi di un vettore appartengono all'intervallo chiuso [a,b] sotto varie ipotesi.

%BLUE% *Martedì 15 Marzo 2022 - Lezioni 16-17* %ENDCOLOR%

*Ricorsione (2)*
   * algoritmi ricorsivi
   * fattoriale: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;
   * ricerca sequenziale: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;
   * ricerca binaria: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;
   * numeri di Fibonacci: pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;
   * esempi di algoritmi ricorsivi (potenza di n alla k, somma degli elementi di un vettore)


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

*Ricorsione (3)*
   * esempi di algoritmi ricorsivi (minimo in un vettore, vettore palindromo, stampa dei valori in un vettore, Torri di Hanoi): pseudocodice ricorsivo e calcolo dell'equazione di ricorrenza;

*Esercizi assegnati:*
   * Progettare degli algoritmi ricorsivi ed esprimerli tramite pseudocodice che risolvano i seguenti problemi:
      * calcolare il coefficiente binomiale n sopra k; 
      * calcolare il MCD tra due interi positivi x ed y come segue:
         * sia y<x
         * se y=0 allora MCD(x,y)=y
         * altrimenti MCD(x,y))MCD(y, x%y) (dove x%y indica il resto della divisione intera tra x e y)

%BLUE% *Martedì 22 Marzo 2022 - Lezioni 21-22* %ENDCOLOR%

Soluzioni delle equazioni di ricorrenza (1)

   * metodi risolutivi (1):
      * metodo iterativo;
      * metodo di sostituzione;
      * metodo dell'albero.

*Esercizi assegnati:*
   * Risolvere con i primi tre metodi alcune equazioni di ricorrenza assegnate

%BLUE% *Giovedì 24 Marzo 2022 - Lezioni 23-24-25* %ENDCOLOR%

Soluzioni delle equazioni di ricorrenza (2)

   * metodi risolutivi (2):
      * metodo principale
   * esempi di soluzione di equazioni di ricorrenza (1)

*Esercizi assegnati:*
   * Risolvere con tutti i metodi alcune equazioni di ricorrenza assegnate

%BLUE% *Martedì 29 Marzo 2022 - Lezioni 26-27* %ENDCOLOR%

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

*Esercizi assegnati:*
   * Risolvere alcune equazioni di ricorrenza assegnate

%BLUE% *Giovedì 31 Marzo 2022* %ENDCOLOR%

*Lezione sospesa per appello straordinario*

%BLUE% *Martedì 5 Aprile 2022 - Lezioni 28-29* %ENDCOLOR%

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

*Esercizi assegnati:*

   * Calcolare il costo computazionale dell'algoritmo di Insertion Sort in cui la posizione dell'elemento da inserire viene determinate tramite ricerca binaria.

%BLUE% *Giovedì 7 Aprile 2022 - Lezioni 30-31-32* %ENDCOLOR%

Il problema dell'ordinamento (2)
   * Un esercizio svolto
   * algoritmi efficienti:
      * paradigma del Divide et Impera
      * merge sort (pseudocodice e costo computazionale, pseudocodice della funzione Fondi, problematica dell'ordinamento in loco)
      * cosa non va nel merge sort: una parentesi sull'uso della memoria secondaria
      * quick sort (idea)
      * pseudocodice e costo della funzione Partiziona

*Esercizi assegnati:*

   * Scrivere in pseudocodice una funzione che, dato un vettore A ed un indice j, calcoli il valore minimo nel sottovettore A[j..n]. Riscrivere lo pseudocodice del selection sort che utilizzi ripetutamente questa funzione.
   * Modificare l'algoritmo di Bubble Sort in modo che non prosegua la computazione se il vettore risulta ordinato (con l'aggiunta di una flag).
   * Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (prima versione).
   * Scrivere la funzione di fusione ricorsiva
   * Scrivere Merge Sort iterativo

%BLUE% *Martedì 12 Aprile 2022 - Lezioni 33-34* %ENDCOLOR%

Il problema dell'ordinamento (3)
   * quick sort (pseudocodice, costo computazionale nei casi migliore e peggiore, costo computazionale nel caso medio, randomizzazione)
   * heapsort (struttura dati heap; Heapify e BuildHeap: pseudocodici e costi computazionali)

*Esercizi assegnati:*
   * Sia dato un vettore di lunghezza n contenente solo valori 0 e 2. Si progetti un algoritmo con costo computazionale lineare che modifichi il vettore in modo che tutte le occorrenze di 0 si trovino più a sinistra di tutte le occorrenze di 2.
   * Si considerino i valori 0 1 2 3 4 5 6 7. Si determini una permutazione di questi valori che generi il caso peggiore per l'algortimo Quick sort.
   * Calcolare il costo computazionale del Quick sort nel caso in cui il vettore contenga tutti elementi uguali.

*%RED% VACANZE PASQUALI: prossima lezione giovedì 21 aprile* %ENDCOLOR%

%BLUE% *Giovedì 21 Aprile 2022 - Lezioni 35-36-37* %ENDCOLOR%

Il problema dell'ordinamento (4)
   * algoritmi efficienti:
      * heapsort (Build Heap: pseudocodice e costo; Heapsort: pseudocodice e costo)
   * algoritmi lineari
      * counting sort (versione semplificata e versione completa)
      * bucket sort (idea)

*Esercizi assegnati:*
   * Scrivere una funzione che restituisca il valore minimo di un HeapMax e calcolarne il costo computazionale
   * Scrivere Heapsort sfruttando la struttura dati HeapMin
   * Scrivere la funzione di inserimento in un HeapMax e calcolarne il costo computazionale


%BLUE% *Martedì 26 Aprile 2022 - Lezioni 38-39* %ENDCOLOR%

Strutture dati fondamentali (1)
   * strutture dati ed insiemi dinamici
   * confronto tra array qualunque e array ordinato
   * introduzione alle liste concatenate: ricerca e inserimento in testa
   * cancellazione nelle liste concatenate

*svolgimento questionario Opis*

*Esercizi assegnati:*
   * vari esercizi di manipolazione delle liste.

%BLUE% *Giovedì 28 Aprile 2022 - Lezioni 40-41-42* %ENDCOLOR%

  * Strutture dati fondamentali (2)
      * pila
      * le operazioni Push e Pop
      * code con priorità
      * la struttura dati coda
      * le operazioni enqueue e dequeue
      * Esercizio svolto: simulazione di una coda tramite due pile

*Esercizi assegnati:*
   * scrivere lo pseudocodice delle funzioni Enqueue e Dequeue quando la coda sia circolare ed implementata su vettore
   * scrivere lo pseudocodice delle funzioni Pop, Push e Pila_Piena quando la pila sia implementata su vettore.

%BLUE% *Martedì 3 Maggio 2022 - Lezioni 43-44* %ENDCOLOR%

   * Strutture dati fondamentali (3)
      * Esercizi svolti sulle liste


<b>%BLUE% Giovedì 5 Maggio 2022 - Lezioni 45-46-47 </b>%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


<b>%BLUE% Martedì 10 Maggio 2022 - Lezioni 48-49 </b>%ENDCOLOR%

   * Strutture dati fondamentali (5)
      * alberi (2)
        * visite di alberi: in-ordine, pre-ordine e post-ordine
            * pseudocodice ricorsivo
            * costo computazionale tramite equazione di ricorrenza e metodo di sostituzione
            * esercizi che si risolvono utilizzando le visite


<b>%BLUE% Giovedì 12 Maggio 2022 - Lezioni 50-51-52 </b>%ENDCOLOR%

   * Strutture dati fondamentali (6)
      * dizionari (1)
         * tabelle ad indirizzamento diretto
         * tabelle hash
            * collisioni
            * liste di trabocco
            * tabelle ad indirizzamento aperto e hashing doppio
     * Alberi binari di ricerca (ABR) (1):
         * definizione e proprietà dell' "ordinamento orizzontale"


<b>%BLUE% Martedì 17 Maggio 2022 - Lezioni 53-54-55 </b>%ENDCOLOR%

   * Strutture dati fondamentali (7)
      * Alberi binari di ricerca (ABR) (2):
         * algoritmo per il massimo e minimo
         * algoritmo per il successore e predecessore
         * algoritmo di inserimento
         * osservazioni sul costo computazionale delle operazioni viste come funzione dell'altezza
         * Esercizi svolti sugli ABR.



<b>%BLUE% Giovedì 19 Maggio 2022 - Lezioni 56-57 </b>%ENDCOLOR%

   * Strutture dati fondamentali (8)
      * Alberi binari di ricerca (ABR) (3):
         * alberi bilanciati: alberi rosso-neri (1)
            * dimostrazione che gli alberi rosso-neri hanno altezza logaritmica
            * rotazioni
            * algoritmo di inserimento

<b>%BLUE% Martedì 24 Maggio 2022 - Lezioni 58-59 </b>%ENDCOLOR%

   * Esercizi svolti riepilogativi in preparazione dell'esame

<b>%BLUE% Giovedì 26 Maggio 2022 - Lezioni 60-61-62 </b>%ENDCOLOR%

   * Esercizi svolti riepilogativi in preparazione dell'esame


-- %USERSIG{TizianaCalamoneri - 2023-02-13}%

---++ Comments

%COMMENT%

-- %USERSIG{TizianaCalamoneri - 2024-02-27}%

---++ Comments

%COMMENT%
This topic: Intro_algo/AD > WebHome > DiarioDelleLezioni > AnniPrecedenti
Topic revision: r2 - 2025-03-03 - TizianaCalamoneri