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'.
  2. Ricerca di un elemento in un array orinato (Ricerca Binaria). T(n) = c log₂(n) + c'.

Lezione di giovedì 27 febbraio 2020

• Algoritmo di ricerca Binaria:
  1. Dimostrazione di terminazione (per induzione sul numero di esecuzioni del while).
  2. Dimostrazione di correttezza (e completezza) tramite proprietà invariante.
  3. Esempi di esecuzione
  4. Albero decisionale per n = 9
• Algoritmo per la valutazione di un polinomio P_n(x) = ∑_i=0..n c_ixⁱ.
  1. Analisi con funzione pow lineare. T(n) = cn²/2 + …
  2. Analisi con funzione pow logaritmica. T(n) = c/2 n log₂ n + …
  3. 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). Esempi. Rappresentazione su grafico.
  • Definizione di ϴ (Theta). Esempi. Rappresentazione su grafico.
  • Relazione tra O, Ω e ϴ.
• 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 registrazione ¹.

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_d(n) = ϴ(n^d) con dimostrazione.
• La lezione è stata svolta via WebEx: è disponibile la registrazione ¹.

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 esempi di esecuzione.
  • Ordinamento stabile e in loco.
  • Albero di decisione per n = 3.
• La lezione è stata svolta via WebEx: è disponibile la registrazione ¹.

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 registrazione ¹.

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 registrazione ¹.

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 esercizi da svolgere a casa.
• La lezione è stata svolta via WebEx: è disponibile la registrazione ¹.

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 registrazione ¹.

Lezione di giovedì 02 aprile 2020

• Esercitazione: correzione degli 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 registrazione ¹.

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 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' esonero del 19/4/2018
  • Es 2 e 3 dell' 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 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 Google Drive.

Lezione di giovedì 23 aprile 2020

• Esercitazione. Svolgimento su Exam.net degli esoneri degli anni passati:
  • Es 1, 2 e 3 dell' esonero del 12/4/2019.
  • Es 1, 2 e 3 dell' esonero del 19/4/2018.
• Le soluzioni da me svolte sono disponibili in allegato:
  • Soluzioni_Esercitazione_23-04-202.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 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³, f(n) = c log_b n, f(n) = cn log_b n dove b > 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 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 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 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: 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 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 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 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 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 esercizio su ABR e AVL.
• La lezione è stata svolta via Google Meet: è disponibile la registrazione in mp4 direttamente dalla cartella condivisa del corso su 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 Google Drive.

Le lezioni sono terminate: buono studio.

Note:

1. Su WebEx 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 Google Drive dove si trovano anche tutte le lezioni registrate con Google Meet.