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 log2(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 Pn(x) = ∑i=0..n cixi.
    1. Analisi con funzione pow lineare. T(n) = cn2/2 + …
    2. Analisi con funzione pow logaritmica. T(n) = c/2 n log2 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 Pd(n) = ϴ(nd) 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

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

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 n3, f(n) = c logb n, f(n) = cn logb 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:
  • 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.
Topic attachments
I Attachment History Action Size DateSorted ascending Who Comment
PDFpdf Esame2018_01_30.pdf r1 manage 96.5 K 2020-03-10 - 19:59 SaverioCaminiti  
PDFpdf Esame2019_07_05.pdf r1 manage 69.5 K 2020-03-10 - 20:02 SaverioCaminiti  
PDFpdf 2020-03-26_Esercizi.pdf r1 manage 58.4 K 2020-03-27 - 09:29 SaverioCaminiti  
PDFpdf Esonero1_2018_04_19.pdf r1 manage 53.7 K 2020-04-11 - 08:31 SaverioCaminiti  
PDFpdf Esonero1_2019_04_12.pdf r1 manage 37.0 K 2020-04-11 - 08:31 SaverioCaminiti  
PDFpdf Soluzioni_Esercitazione_23-04-202.pdf r1 manage 41.0 K 2020-04-24 - 17:36 SaverioCaminiti  
PDFpdf Soluzioni_Esercitazione_23-04-2020_parte_2.pdf r1 manage 60.1 K 2020-04-24 - 17:37 SaverioCaminiti  
Compressed Zip archivezip 2020-05-12_fibonacci.py.zip r1 manage 3.7 K 2020-05-13 - 12:10 SaverioCaminiti  
Texttxt 2020-05-26_esercizio_per_casa.txt r1 manage 0.6 K 2020-05-27 - 12:47 SaverioCaminiti  
PDFpdf 2020-05-05_Homework.pdf r1 manage 47.2 K 2020-05-29 - 14:51 SaverioCaminiti  
Edit | Attach | Watch | Print version | History: r144 < r143 < r142 < r141 < r140 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r144 - 2021-02-03 - AngeloMonti






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback