DiarioDelleLezioni < Intro

Tags: view all tags
---++ Diario delle Lezioni (Saverio Caminiti) a.a. 2019/2020

*Lezionei di martedì 25 febbraio 2020*
   * Presentazione del corso.
   * Definizione di Algoritmo e sue proprietà.
   * Cenni storici e algoritmi nel quotidiano.
   * Modello di costo uniforme.
   * Esempi di algoritmi e loro analisi:
      1 Ricerca di un elemento in un array. T(n) = cn + c'.
      1 Ricerca di un elemento in un array orinato (Ricerca Binaria). T(n) = c log<sub>2</sub>(n) + c'.

*Lezione di giovedì 27 febbraio 2020*
   * Algoritmo di ricerca Binaria:
      1 Dimostrazione di terminazione (per induzione sul numero di esecuzioni del while).
      1 Dimostrazione di correttezza (e completezza) tramite proprietà invariante.
      1 Esempi di esecuzione
      1 Albero decisionale per n = 9
   * Algoritmo per la valutazione di un polinomio P<sub>n</sub>(x) = &sum;<sub>i=0..n</sub> c<sub>i</sub>x<sup>i</sup>.
      1 Analisi con funzione pow lineare. T(n) = cn<sup>2</sup>/2 + …
      1 Analisi con funzione pow logaritmica. T(n) = c/2 n log<sub>2</sub> n + …
      1 Modifica per evitare il calcolo di pow. T(n) = cn + …
   * Tecnica del raddoppio per calcolare pow(b, e: int) in tempo logaritmico.

*Lezione di martedì 3 marzo 2020*
   * Annullata per decisione individuale del docente.

*Lezione di giovedì 5 marzo 2020*
   * Annullata per sospensione dell'attività didattica a livello nazionale.

*Lezione di martedì 10 marzo 2020*
   * Notazione asintotica:
      * Definizione di O (O grande). Esempi. Rappresentazione su grafico.
      * Definizione di &Omega; (Omega). Esempi. Rappresentazione su grafico.
      * Definizione di &#x3F4; (Theta). Esempi. Rappresentazione su grafico.
      * Relazione tra O, &Omega; e &#x3F4;.
   * Esercizi per casa che svolgeremo insieme durante la prossima lezione:
      * Esame del 05/07/2019, Parte I, Esercizio 1 (pdf allegato in fondo a questa pagina).
      * Esame del 30/01/2018, Parte I, Esercizio 2 (pdf allegato in fondo a questa pagina).
   * La lezione è stata svolta via !WebEx: è disponibile la [[https://unitelmasapienza.webex.com/recordingservice/sites/unitelmasapienza/recording/playback/0813d9e1c3f9412da61637276bcf82b0][registrazione]] [[#note1][¹]].

*Lezione di giovedì 12 marzo 2020*
   * Correzione degli esercizi lasciati per casa a fine lezione precedente.
   * Algebra della notazione asintotica con dimostrazioni.
   * Teorema polinomi P<sub>d</sub>(n) = &#x3F4;(n<sup>d</sup>) con dimostrazione.
   * La lezione è stata svolta via !WebEx: è disponibile la [[https://unitelmasapienza.webex.com/recordingservice/sites/unitelmasapienza/recording/playback/08f39d430108445a9471b77aff3eccaf][registrazione]] [[#note1][¹]].

*Lezione di martedì 17 marzo 2020*
   * Il problema dell'ordinamento.
   * Esempio di ordinamento di carte.
   * !InsertionSort:
      * Pseudocodice, esempio di esecuzione.
      * Proprietà: terminazione, correttezza, completezza.
      * Analisi asintotica nel caso peggiore, migliore e medio.
      * Animazioni online con [[https://www.toptal.com/developers/sorting-algorithms][esempi di esecuzione]].
      * Ordinamento stabile e _in loco_.
      * Albero di decisione per n = 3.
   * La lezione è stata svolta via !WebEx: è disponibile la [[https://unitelmasapienza.webex.com/recordingservice/sites/unitelmasapienza/recording/playback/1bc9644ff9f544bca2684ca44ecd6be7][registrazione]] [[#note1][¹]].

*Lezione di giovedì 19 marzo 2020*
   * !SelectionSort:
      * Pseudocodice, esempio di esecuzione.
      * Proprietà: terminazione, correttezza, completezza, _in loco_ ma non stabile.
      * Analisi asintotica (caso peggiore = migliore = medio).
      * Albero di decisione per n = 3.
   * !BubbleSort:
      * Pseudocodice, esempio di esecuzione.
      * Proprietà: terminazione, correttezza, completezza, stabile e _in loco_.
      * Analisi asintotica (caso peggiore = migliore = medio).
      * Versione migliorata con verifica sugli scambi.
      * Analisi asintotica nel caso peggiore, migliore e medio.
   * Esercizio per casa:
      * Tracciare l'albero di decisione del !BubbleSort per n = 3 prima nella versione semplice, poi in quella migliorata.
   * La lezione è stata svolta via !WebEx: è disponibile la [[https://unitelmasapienza.webex.com/recordingservice/sites/unitelmasapienza/recording/playback/a4e4e9621c8548b5859372d66e52add5][registrazione]] [[#note1][¹]].

*Lezione di martedì 24 marzo 2020*
   * !BubbleSort:
      * Albero di decisione per n = 3 (versione semplice e migliorata).
   * Proprietà degli alberi di decisione.
   * Limite inferiore al numero di confronti di ogni algoritmo di ordinamento basato su confronti.
   * La lezione è stata svolta via !WebEx: è disponibile la [[https://unitelmasapienza.webex.com/recordingservice/sites/unitelmasapienza/recording/playback/c95446800aae4dac9c3418f1e80c9ad8][registrazione]] [[#note1][¹]].

*Lezione di giovedì 26 marzo 2020*
   * Esercitazione: analisi del costo di vare funzioni iterative con 1 o 2 cicli for e while.
   * Merge di due array ordinati in tempo lineare.
   * Assegnati alcuni [[%ATTACHURL%/2020-03-26_Esercizi.pdf][esercizi da svolgere a casa]].
   * La lezione è stata svolta via !WebEx: è disponibile la [[https://unitelmasapienza.webex.com/recordingservice/sites/unitelmasapienza/recording/playback/a419a6379ad44b87b28f0f73362bd5b6][registrazione]] [[#note1][¹]].

*Lezione di martedì 31 marzo 2020*
   * !MergeSort:
      * Pseudocodice con funzione ricorsiva.
      * Esempio di esecuzione.
      * Albero della ricorsione.
      * Merge di due porzioni contigue dello stesso array in tempo lineare.
      * Analisi del costo, equazione di ricorrenza, risoluzione per sostituzione.
   * La lezione è stata svolta via !WebEx: è disponibile la [[https://unitelmasapienza.webex.com/recordingservice/sites/unitelmasapienza/recording/playback/4e58c4837594441485ffffd5fde89a99][registrazione]] [[#note1][¹]].

*Lezione di giovedì 02 aprile 2020*
   * Esercitazione: correzione degli [[%ATTACHURL%/2020-03-26_Esercizi.pdf][esercizi]] lasciati il 26/03/2020.
   * Esercizio: !SelectionSort ricorsivo.
      * Valutazione del costo asintotico.
      * Risoluzione dell'equazione di ricorrenza con il metodo di sostituzione.
   * !MergeSort iterativo.
   * La lezione è stata svolta via !WebEx: è disponibile la [[https://unitelmasapienza.webex.com/recordingservice/sites/unitelmasapienza/recording/playback/02a867e962b74fd2a42c1cafe77e24ec][registrazione]] [[#note1][¹]].

*Lezione di martedì 07 aprile 2020*
   * !QuickSort:
      * Algoritmo ricorsivo.
      * Partizionamento di un array introno ad un pivot in tempo lineare.
      * Analisi del caso migliore.
      * Analisi del caso peggiore: array ordinato o semi ordinato.
      * Scelta randomizzata del pivot.
      * Analisi del caso medio.
      * Scelta del pivot come mediano tra 3 valori casuali nel vettore.
   * La lezione è stata svolta via Google Meet: è disponibile la registrazione in mp4 direttamente dalla cartella condivisa del corso su [[https://drive.google.com/open?id=14XjgaDZu2JX0k_An-TW2EQ6ueA9FRRDo][Google Drive]].

*Vacanze Pasquali da giovedì 9 a martedì 14 aprile 2020*
   * Non verranno svolte le lezioni.
   * Chi vuole può esercitarsi svolgendo i seguenti esercizi:
      * Es 2 e 3 dell' [[%ATTACHURL%/Esonero1_2018_04_19.pdf][esonero del 19/4/2018]]
      * Es 2 e 3 dell' [[%ATTACHURL%/Esonero1_2019_04_12.pdf][esonero del 12/4/2019]]
   * Buona Pasqua a tutti.

*Lezione di giovedì 16 aprile 2020*
   * Algoritmi + Strutture Dati = Programmi.
   * Heap:
      * Definizione e proprietà.
      * Altezza logaritmica.
      * Estrazione del massimo.
      * Funzione fixHeap e sua analisi.
   * !HeapSort:
      * Funzione heapify e sua analisi.
      * Ordinamento tramite heap.
      * Analisi, caso migliore, caso peggiore.
   * La lezione è stata svolta via Google Meet: è disponibile la registrazione in mp4 direttamente dalla cartella condivisa del corso su [[https://drive.google.com/open?id=14XjgaDZu2JX0k_An-TW2EQ6ueA9FRRDo][Google Drive]].

*Lezione di martedì 21 aprile 2020*
   * !IntegerSort:
      * Ordinare senza confronti.
      * Pseudocodice.
      * Esempio di esecuzione.
      * Proprietà.
      * Analisi del costo computazionale.
   * !CountingSort:
      * Pseudocodice.
      * Esempio di esecuzione.
      * Stabilità scorrendo al contrario.
   * La lezione è stata svolta via Google Meet: è disponibile la registrazione in mp4 direttamente dalla cartella condivisa del corso su [[https://drive.google.com/open?id=14XjgaDZu2JX0k_An-TW2EQ6ueA9FRRDo][Google Drive]].

*Lezione di giovedì 23 aprile 2020*
   * Esercitazione. Svolgimento su Exam.net degli esoneri degli anni passati:
      * Es 1, 2 e 3 dell' [[%ATTACHURL%/Esonero1_2019_04_12.pdf][esonero del 12/4/2019]].
      * Es 1, 2 e 3 dell' [[%ATTACHURL%/Esonero1_2018_04_19.pdf][esonero del 19/4/2018]].
   * Le soluzioni da me svolte sono disponibili in allegato:
      * [[%ATTACHURL%/Soluzioni_Esercitazione_23-04-202.pdf][Soluzioni_Esercitazione_23-04-202.pdf]].
      * [[%ATTACHURL%/Soluzioni_Esercitazione_23-04-2020_parte_2.pdf][Soluzioni_Esercitazione_23-04-2020_parte_2.pdf]].
   * Potete provare la piattaforma Exam.net facendo gli esami con chiavi uPZGjW e Gm9fyb li terrò aperti per alcuni giorni.
   * La lezione è stata svolta via Google Meet: è disponibile la registrazione in mp4 direttamente dalla cartella condivisa del corso su [[https://drive.google.com/open?id=14XjgaDZu2JX0k_An-TW2EQ6ueA9FRRDo][Google Drive]].

*Lezione di martedì 28 aprile 2020*
   * Risoluzione di equazioni di ricorrenza con il metodo iterativo.
   * Esempi di applicazione del metodo.
   * Per esercizio potete risolvere le eq di ricorrenza:
      * T(n) = 2T(n/2) + f(n), T(1) = c'
      * T(n) = 3T(n/4) + f(n), T(1) = c'
      * T(n) = 4T(n/3) + f(n), T(1) = c'
      * per ognuna considerare le 5 varianti in cui f(n)=c, f(n)=cn, f(n) = c n<sup>3</sup>, f(n) = c log<sub>b</sub> n, f(n) = cn log<sub>b</sub> n dove b &gt; 1 è una costante che potete scegliere di volta in volta per semplificarvi i conti.
   * La lezione è stata svolta via Google Meet: è disponibile la registrazione in mp4 direttamente dalla cartella condivisa del corso su [[https://drive.google.com/open?id=14XjgaDZu2JX0k_An-TW2EQ6ueA9FRRDo][Google Drive]]. Nota: nell'ultimo esercizio c'è un errore, è disponibile un file pdf con la correzione nella stessa cartella condivisa delle lezioni.

*Lezione di giovedì 30 aprile 2020*
   * Risoluzione di equazioni di ricorrenza analizzando l'albero della ricorsione.
      * Casi in cui domina asintoticamente il costo alla radice, alle foglie, nella somma dei nodi interni.
      * Corrispondenza tra l'analisi dell'albero della ricorsione e le componenti dell'equazione che si ottiene con il metodo iterativo.
   * Enunciato del Teorema Principale.
   * Esercizi.
   * La lezione è stata svolta via Google Meet: è disponibile la registrazione in mp4 direttamente dalla cartella condivisa del corso su [[https://drive.google.com/open?id=14XjgaDZu2JX0k_An-TW2EQ6ueA9FRRDo][Google Drive]].

*Settimana di interruzione della didattica da lunedì 4 a venerdì 8 maggio 2020*
   * Non verranno svolte le lezioni.
   * Martedì 5 maggio 2020 abbia svolto un [[%ATTACHURL%/2020-05-05_Homework.pdf][homework]].

*Lezione di martedì 12 maggio 2020*
   * Algoritmi per il calcolo dei numeri di Fibonacci:
      * Calcolo diretto e problemi di approssimazione.
      * Algoritmo esponenziale basato sulla definizione ricorsiva, analisi con albero della ricorsione.
      * Algoritmo lineare con array (ricorsivo e iterativo) e senza array, analisi.
      * Algoritmo logaritmico basato su esponenziazione di matrici con la tecnica del raddoppio, analisi.
   * Verifica pratica:
      * Confronto dei 3 algoritmi implementati in Python.
      * Il codice utilizzato può essere scaricato qui: [[%ATTACHURL%/2020-05-12_fibonacci.py.zip][2020-05-12_fibonacci.py.zip]].
   * La lezione è stata svolta via Google Meet: è disponibile la registrazione in mp4 direttamente dalla cartella condivisa del corso su [[https://drive.google.com/open?id=14XjgaDZu2JX0k_An-TW2EQ6ueA9FRRDo][Google Drive]].

*Lezione di giovedì 14 maggio 2020*
   * Strutture dati astratte e concrete.
   * Dizionari implementati con array.
   * Liste linkate, doppiamente linkate e cicliche.
   * Dizionari implementati con liste.
   * Alberi:
      * Definizioni e notazione. Limite sul numero minimo e massimo di nodi in alberi binari.
      * Rappresentazione con vettore: posizionale, vettore dei padri.
      * Con puntatori: figlio sinistro e desto (e padre), lista di figli, figlio sinistro e al fratello desto.
      * Visite inorder, preorder, postorder. Analisi intuitiva con albero della ricorsione e formale con metodo di sostituzione.
   * La lezione è stata svolta via Google Meet: è disponibile la registrazione in mp4 direttamente dalla cartella condivisa del corso su [[https://drive.google.com/open?id=14XjgaDZu2JX0k_An-TW2EQ6ueA9FRRDo][Google Drive]].

*Lezione di martedì 19 maggio 2020*
   * Applicazioni di visite su alberi binari:
      * Valutazione di un'espressione con una visita inorder.
      * Ricostruzione di un albero a partire dalla sue visite inorder e preorder.
   * Alberi Binari di Ricerca (ABR):
      * Definizione e proprietà.
      * Algoritmi di ricerca, inserimento, ricerca del massimo, del minimo, e del predecessore, cancellazione.
      * Dizionari basati su ABR.
   * La lezione è stata svolta via Google Meet: è disponibile la registrazione in mp4 direttamente dalla cartella condivisa del corso su [[https://drive.google.com/open?id=14XjgaDZu2JX0k_An-TW2EQ6ueA9FRRDo][Google Drive]].

*Lezione di giovedì 21 maggio 2020*
   * Correzione Homework del 05/05/2020.
   * Pile e Code:
      * Definizione delle strutture dati astratte (LIFO e FIFO).
      * Implementazioni tramite: array, array dinamici e liste linkate.
      * Esempio: valutazione di espressioni in forma prefissa tramite Pila.
   * Visite in ampiezza e profondità di alberi generici.
      * Visita in ampiezza (BFS) con Coda FIFO.
      * Visita in profondità /DFS) con Pila LIFO.
   * La lezione è stata svolta via Google Meet: è disponibile la registrazione in mp4 direttamente dalla cartella condivisa del corso su [[https://drive.google.com/open?id=14XjgaDZu2JX0k_An-TW2EQ6ueA9FRRDo][Google Drive]].

*Lezione di martedì 26 maggio 2020*
   * Sbilanciamento degli ABR e costo delle operazioni di inserimento, cancellazione e ricerca.
   * Rotazioni su alberi intorno ad un nodo perno.
   * Alberi AVL:
      * Definizione e proprietà.
      * Inserimento di una chiave in un AVL: mantenere il bilanciamento tramite rotazioni.
   * Assegnazione di un [[%ATTACHURL%/2020-05-26_esercizio_per_casa.txt][esercizio su ABR e AVL]].
   * La lezione è stata svolta via Google Meet: è disponibile la registrazione in mp4 direttamente dalla cartella condivisa del corso su [[https://drive.google.com/open?id=14XjgaDZu2JX0k_An-TW2EQ6ueA9FRRDo][Google Drive]].

*Lezione di giovedì 28 maggio 2020*
   * Alberi AVL:
      * Cancellazione di una chiave in un AVL: mantenere il bilanciamento tramite rotazioni.
      * Dimostrazione di altezza logaritmica tramite Alberi di Fibonacci.
   * Esercizi su ABR e AVL.
   * La lezione è stata svolta via Google Meet: è disponibile la registrazione in mp4 direttamente dalla cartella condivisa del corso su [[https://drive.google.com/open?id=14XjgaDZu2JX0k_An-TW2EQ6ueA9FRRDo][Google Drive]].

*Le lezioni sono terminate: buono studio.*

---

Note:
   1 <a name='note1'>Su !WebEx</a> potete vedere la lezione in streaming o scaricarla (c'è un'iconcina vicino al titolo). Se il sistema desse problemi a causa del carico di rete potete provare a scaricare le lezioni in mp4 direttamente dalla cartella condivisa del corso su [[https://drive.google.com/open?id=14XjgaDZu2JX0k_An-TW2EQ6ueA9FRRDo][Google Drive]] dove si trovano anche tutte le lezioni registrate con Google Meet.
Attachments
Topic attachments
I	Attachment	History	Action	Size	Date	Who
pdf	2020-03-26_Esercizi.pdf	r1	manage	58.4 K	2020-03-27 - 09:29	SaverioCaminiti
pdf	2020-05-05_Homework.pdf	r1	manage	47.2 K	2020-05-29 - 14:51	SaverioCaminiti
zip	2020-05-12_fibonacci.py.zip	r1	manage	3.7 K	2020-05-13 - 12:10	SaverioCaminiti
txt	2020-05-26_esercizio_per_casa.txt	r1	manage	0.6 K	2020-05-27 - 12:47	SaverioCaminiti
pdf	Esame2018_01_30.pdf	r1	manage	96.5 K	2020-03-10 - 19:59	SaverioCaminiti
pdf	Esame2019_07_05.pdf	r1	manage	69.5 K	2020-03-10 - 20:02	SaverioCaminiti
pdf	Esonero1_2018_04_19.pdf	r1	manage	53.7 K	2020-04-11 - 08:31	SaverioCaminiti
pdf	Esonero1_2019_04_12.pdf	r1	manage	37.0 K	2020-04-11 - 08:31	SaverioCaminiti
pdf	Soluzioni_Esercitazione_23-04-202.pdf	r1	manage	41.0 K	2020-04-24 - 17:36	SaverioCaminiti
pdf	Soluzioni_Esercitazione_23-04-2020_parte_2.pdf	r1	manage	60.1 K	2020-04-24 - 17:37	SaverioCaminiti