Tags:
create new tag
view all tags

Diario delle Lezioni (Angelo Monti) a.a. 2020/2021

*Lezione di lunedi 22 febbraio 2021*

  • Informazioni sul corso.
  • Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale.
  • lez01IntroduzionePDF.pdf

*Lezione di giovedý 25 febbraio 2021*

  • Notazione asintotica
    • Definizione e significato degli insiemi O, Ω e Θ
    • Algebra della notazione asintotica
    • lez02AsintoticaPDF.pdf

*Lezione di lunedý 1 marzo 2021*

  • Valutazione del costo computazionale di un algoritmo
    • Costi delle varie istruzioni nel modello adottato di costo uniforme
    • 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
    • lez03CostoAlgoritmiPDF.pdf

*Lezione di giovedý 4 marzo 2021*

  • 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
    • ESERCIZIO: ricerca degli algoritmi che calcolino quanti elementi di un vettore appartengono all'intervallo chiuso [a,b] sotto varie ipotesi.
    • lez04ProblemaRicercaPDF.pdf

*Lezione di lunedý 8 marzo 2021*

  • Ricorsione
    • funzioni matematiche ricorsive ed algoritmi ricorsivi
    • esempio: la funzione fattoriale, nelle due versioni iterativa e ricorsiva con definizione della equazione di ricorrenza.
    • esempio: ricerca sequenziale ricorsiva con definizione della equazione di ricorrenza
    • esempio: ricerca binaria ricorsiva con definizione della equazione di ricorrenza
    • esempio: calcolo di n^m con definizione della equazione di ricorrenza
    • esempio: calcolo dell'ennesimo numero di Fibonacci con definizione della equazione di ricorrenza
    • esempi di algoritmi ricorsivi per problemi su liste: calcolo del minimo, calcolo della somma, stampa degli elementi dal primo all'ultimo e stampa degli elementi dall'ultimo al primo
    • Esercizio: algoritmo ricorsivo per determinare se gli elementi di una lista formano o meno una parola palindroma.
    • lez05AlgoritmiRicorsiviPDF.pdf

*Lezione di giovedý 11 marzo 2021*

*Lezione di lunedý 15 marzo 2021*

*Lezione di giovedý 18 marzo 2021*

  • esempi di soluzione di equazioni di ricorrenza
  • Il problema dell'ordinamento
Lezione di lunedý 22 marzo 2021
  • esempi di soluzione di equazioni di ricorrenza:
    • La somma aritmetica. Equazione: T(n)=2T(n/2)+Θ(nlog n) ed esercizi. Lucidi solEqRic4PDF.pdf
    • La somma geometrica e la somma aritmetico-geometrica. Equazione: 3T(n/2)+Θ(nlog n). Lucidi solEqRic5PDF.pdf
    • La somma armonica. Equazione 2T(n/2)+Θ(n/log n). Lucidi solEqRic6PDF.pdf

*Lezione di giovedý 25 marzo 2021*

  • Il problema dell'ordinamento
    • Gli algoritmi di ordinamento basati sul confronto hanno complessitÓ Ω(nlog n). Seconda parte dei Lucidi lez08Ordinamento1NivePDF.pdf
    • L'algoritmo Merge sort di complessitÓ Θ(nlog n). ESERCIZIO svolto: L'algoritmo Merge_Insertion. Definizione e utilitÓ degli algoritmi di ordinamento stabili, Esercizi per casa. Lucidi lez09Ordinamento2MergePDF.pdf
Lezione di lunedý 29 marzo 2021. L'algoritmo d'ordinamento Quicksort. La funzione partiziona di costo Θ(n). La complessitÓ dell'equazione di ricorrenza risultante: O(n^2) al caso pessimo, Θ(nlog n) al caso ottimo, Θ(nlog n) al caso medio. Vantaggi dello scegliere l'elemento di pivot in modo random. Lucidi lez10Ordinamento3QuikPDF.pdf

* VACANZE PASQUALI: prossima lezione giovedý 8 aprile *

Lezione di giovedý 8 aprile 2021. La struttura dati heap (massimo). Costruzione di un heap in tempo O(n) grazie alle funzioni heapify e buildheap. L'algoritmo d'ordinamento heapsort di tempo O(nlog n) Lucidi lez11Ordinamento4HeapPDF.pdf

Lezione di lunedý 12 aprile 2021. Algoritmi di ordinamento lineari: Counting sort di tempo Θ(n+k) dove k Ŕ l'intero massimo tra quelli da ordinare. Bucket sort di tempo medio Θ(n). Lucidi lez12Ordinamento5LineariPDF.pdf

Lezione di giovedý 15 aprile 2021. Strutture dati:

  • strutture dati ed insiemi dinamici
  • confronto tra vettore qualunque e vettore ordinato
  • introduzione alle liste: ricerca e inserimento
  • cancellazione nelle liste,
  • liste doppiamente puntate
  • lucidi: lez13struttureDati1PDF.pdf
Esercizio: esercizioMatrice.pdf

Lezione di lunedý 19 aprile 2021. Strutture dati:

  • pile e code, loro implementazione tramite liste e tramite array in modo che entrambe le operazioni di inserimento e cancellazione abbiano costo Θ(n). Lucidi lez14StruttureDati2PDF.pdf
  • Esercizio sulle liste. lucidi ESERCIZIOlistaPDF.pdf
Lezione giovedý 22 aprile 2021. Esercizi svolti sulle liste concatenate. Lucidi EserciziListeLinkatePDF.pdf

Lezione lunedý 26 aprile 2021. Alberi:

  • alberi come grafi connessi aciclici
  • alberi come grafi con n nodi ed n-1 vertici
  • relazione tra altezza h e numero di nodi n in un albero binario completo.
  • relazione tra altezza h e numero di nodi n in un albero binario.
  • lucidi lez16Alberi1aPDF.pdf
Lezione giovedý 29 aprile 2021. Alberi:
  • rappresentazione di alberi in memoria: tramite nodi e puntatori, in modo posizionale, tramite il vettore dei padri. Vantaggi e svantaggi delle varie rappresentazioni. lucidi lez16Alberi1bPDF.pdf
  • Visite di alberi: preorder, inorder, postorder e per livelli (con l'utilizzo di una coda). Prova del costo Θ(n) di tutte queste visite. Esercizi:lucidi lez17VisiteAlberiPDF.pdf
    • calcolare il numero di nodi di un albero
    • calcolare l'altezza di un albero
    • ricercare una chiave in un albero
    • conteggio dei nodi presenti ad un certo livello k dell'albero

*Lezione lunedý 3 maggio 2021.* I Dizionari. Tabelle ad indirizzamento diretto. Tabelle hash, Funzioni hash e uniformitÓ semplice, liste di trabocco, fattore di carico. Indirizzamento aperto. Lucidi lez18Dizionari1.pdf

Lezione giovedý 6 maggio 2021. Alberi binari di ricerca. operazioni di ricerca, cancellazione e inserimento in O(h) dove h Ŕ l'altezza dell'albero. Rappresentazione degli alberi di ricerca tramite puntatori e nodi con puntatore anche al padre. Ricerca del predecessore e del successore in tempo O(h) grazie al puntatore al padre. Lucidi lez19Dizionari2ABRPDF.pdf

Lezione lunedý 10 maggio 2021. 3 esercizi svolti presenti nei ludici della lezione precedente. Alberi di ricerca rosso- neri e loro proprietÓ di essere bilanciati (avere altezza O(log n) dove n Ŕ il numero di nodi dell'albero). Lucidi lez20Dizionari3bPDF.pdf

Lezione giovedý 13 maggio 2021. Inserimento nodi in alberi di ricerca rosso-neri in tempo O(log n) (lucidi lezione precedente). Due esercizi d'esame. lucidi Lez21EserciziVari1PDF.pdf

Lezione lunedý 17 maggio 2021.

Lezione giovedý 20 maggio 2021. Niente lezione

Lezione lunedý 24 maggio 2021. esercizi Lez23EserciziPDF.pdf

<a name="topic-actions"></a>

Topic attachments
I Attachment History Action Size Date Who Comment
PDFpdf ESERCIZIOlistaPDF.pdf r1 manage 89.0 K 2021-04-19 - 13:22 AngeloMonti  
PDFpdf EserciziListeLinkatePDF.pdf r1 manage 551.7 K 2021-04-22 - 12:11 AngeloMonti  
PDFpdf Lez21EserciziVari1PDF.pdf r1 manage 483.6 K 2021-05-13 - 12:51 AngeloMonti  
PDFpdf Lez22EserciziPDF.pdf r1 manage 523.5 K 2021-05-18 - 16:00 AngeloMonti  
PDFpdf Lez23EserciziPDF.pdf r1 manage 914.1 K 2021-05-24 - 17:37 AngeloMonti  
PDFpdf Lez23TRACCEserciziPDF.pdf r1 manage 687.3 K 2021-05-18 - 16:07 AngeloMonti  
PDFpdf esercizioMatrice.pdf r1 manage 104.1 K 2021-04-15 - 16:39 AngeloMonti  
PDFpdf lez01IntroduzionePDF.pdf r1 manage 841.9 K 2021-02-22 - 13:53 AngeloMonti  
PDFpdf lez02AsintoticaPDF.pdf r1 manage 848.6 K 2021-02-25 - 18:27 AngeloMonti  
PDFpdf lez03CostoAlgoritmiPDF.pdf r1 manage 820.8 K 2021-03-01 - 13:22 AngeloMonti  
PDFpdf lez04ProblemaRicercaPDF.pdf r1 manage 525.4 K 2021-03-04 - 14:01 AngeloMonti  
PDFpdf lez05AlgoritmiRicorsiviPDF.pdf r1 manage 1217.9 K 2021-03-08 - 13:43 AngeloMonti  
PDFpdf lez06EquazioniRicorrenzaPDF.pdf r1 manage 599.2 K 2021-03-11 - 14:39 AngeloMonti  
PDFpdf lez08Ordinamento1NivePDF.pdf r1 manage 1524.1 K 2021-03-18 - 12:08 AngeloMonti  
PDFpdf lez09Ordinamento2MergePDF.pdf r1 manage 516.7 K 2021-03-25 - 13:20 AngeloMonti  
PDFpdf lez10Ordinamento3QuikPDF.pdf r1 manage 630.6 K 2021-03-29 - 16:59 AngeloMonti  
PDFpdf lez11Ordinamento4HeapPDF.pdf r1 manage 569.4 K 2021-04-08 - 11:17 AngeloMonti  
PDFpdf lez12Ordinamento5LineariPDF.pdf r1 manage 660.3 K 2021-04-12 - 13:15 AngeloMonti  
PDFpdf lez13struttureDati1PDF.pdf r1 manage 656.8 K 2021-04-15 - 16:39 AngeloMonti  
PDFpdf lez14StruttureDati2PDF.pdf r1 manage 644.7 K 2021-04-19 - 13:22 AngeloMonti  
PDFpdf lez16Alberi1aPDF.pdf r1 manage 577.8 K 2021-04-26 - 11:44 AngeloMonti  
PDFpdf lez16Alberi1bPDF.pdf r1 manage 456.1 K 2021-04-29 - 13:04 AngeloMonti  
PDFpdf lez17VisiteAlberiPDF.pdf r1 manage 620.4 K 2021-04-29 - 13:04 AngeloMonti  
PDFpdf lez18Dizionari1.pdf r1 manage 861.7 K 2021-05-03 - 17:55 AngeloMonti  
PDFpdf lez19Dizionari2ABRPDF.pdf r1 manage 743.2 K 2021-05-12 - 07:56 AngeloMonti  
PDFpdf lez20Dizionari3bPDF.pdf r1 manage 1143.1 K 2021-05-12 - 07:56 AngeloMonti  
PDFpdf solEqRic1PDF.pdf r1 manage 386.1 K 2021-03-18 - 12:01 AngeloMonti  
PDFpdf solEqRic4PDF.pdf r1 manage 417.1 K 2021-03-22 - 12:28 AngeloMonti  
PDFpdf solEqRic5PDF.pdf r1 manage 421.5 K 2021-03-22 - 12:28 AngeloMonti  
PDFpdf solEqRic6PDF.pdf r1 manage 404.8 K 2021-03-22 - 12:28 AngeloMonti  
PDFpdf solEsercizi1PDF.pdf r1 manage 425.4 K 2021-03-11 - 14:39 AngeloMonti  
Edit | Attach | Watch | Print version | History: r27 < r26 < r25 < r24 < r23 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r27 - 2021-05-24 - 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-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback