Diario delle lezioni

Lezioni degli Anni Accademici Precedenti

Lezioni dell'anno accademico 2018/2019

Lezioni 1-2: lunedý 25 febbraio 2019

Presentazione agli studenti della visita ANVUR
Presentazione del corso
Introduzione

  • Concetti di algoritmo, di struttura dati, di efficienza; di costo computazionale; di problem solving e di problema computazionale.

Lezioni 3-4: mercoledý 27 febbraio 2019

Notazione asintotica (1)

  • Modello RAM; misura di costo uniforme e logaritmico.
  • Definizione e significato degli insiemi O, Ω e Θ.
  • Esempi.
  • Algebra della notazione asintotica.

Esercitazioni 1-2: venerdý 1 marzo 2019

  • TinyC. Codifica in TinyC del programma che calcola la somma iterando +1 [ D1, sezione 2 ]
  • Indagini su un programma iterativo [ L1, sez. 2.1 ]:
    • Precondizioni, Postcondizioni, invarianti di ciclo.
    • Terminazione di un ciclo: funzione di terminazione.
  • Esempi:
    • funzione che calcola la moltiplicazione. Uso della funzione somma nel calcolo del prodotto [ D1, sez. 3 ].
    • funzione che calcola il predecessore. Specifica come contratto.
    • funzione che calcola il minore o uguale.

  • Esercizi consigliati: Dispensa L1, sez. 2.5, esercizi da 2 a 8.
  • Sperimentazioni: Disp. D1, sez. 2.1.

Lezioni 5-6: lunedý 4 marzo 2019

Notazione asintotica (2)

  • Esempi di problemi che si possono risolvere in modo pi¨ o meno efficiente
    • somma dei primi n interi
    • valutazione di un polinomio in un punto

Il problema della ricerca (1)

  • ricerca sequenziale e suo costo computazionale nel caso migliore, peggiore e medio
  • ricerca dicotomica e suo costo computazionale nel caso migliore e peggiore

Lezioni 7-8: mercoledý 6 marzo 2019

Il problema della ricerca (2)

  • costo computazionale della ricerca dicotomica nel caso medio

Ricorsione

  • funzioni matematiche ricorsive
  • algoritmi ricorsivi: aspetti principali
  • equazioni di ricorrenza
  • ricerca sequenziale: pseudocodice ricorsivo ed equazione di ricorrenza
  • ricerca binaria: equazione di ricorrenza

Soluzioni delle equazioni di ricorrenza (1)

  • metodo di sostituzione; esempi

Esercizi assegnati:

  • Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione
  • Calcolare l'andamento asintotico stretto di alcune funzioni
  • Calcolare il caso migliore e peggiore del costo computazionale degli algoritmi di Selection Sort, Insertion Sort e Bubble Sort (pseudocodice sulle dispense)

Venerdý 8 Marzo 2019 Lezioni sospese per le Olimpiadi di Matematica (aule occupate)

Lezioni 9-10: lunedý 11 marzo 2019

Soluzioni delle equazioni di ricorrenza (2)

  • metodo iterativo; esempi
  • metodo dell'albero; esempi

Mercoledý 13 Marzo 2019 - Esercitazioni 3-4

  • Usando l'esempio del predecessore, revisione delle asserzioni logiche: precondizioni, postcondizioni, invarianti, funzioni di terminazione.
  • Progetto di funzioni a partire dalle specifiche logiche [ L1, sez. 2.3 ].
    • Esempio: divisione intera.
  • Uso di passaggi per riferimento per passare pi¨ risultati: funzione int divRef(int, int, int*, int*).
  • Utilizzo della funzione divRef nell'algoritmo mcdMaestra [ D1, sez. 4 ].

  • Esercizi consigliati: Dispensa L1, sez. 2.5, esercizi da 2 a 8.

Venerdý 15 marzo 2018 - Esercitazioni 5-6

  • Ancora sui passaggi per riferimento: funzione scambia(int*,int*)
  • Passaggio di parametri: call-by-value: impossibilitÓ di scrivere una funzione myAnd equivalente all'operatore && predefinito.
  • Call-by-value, funzione ap(int*,int*,int,int) (assegnamento parallelo Ó la Python) [ D2, sez. 2 ].
  • I problemi di alias: funzione scambia(int*,int*) senza variabile di appoggio [ D2, sez. 3 ].
  • Induzione e Ricorsione: definizione induttiva di + e funzione sommaRec(int, int) [ D3, sez. 1.1 ].
  • Esercizio: predecessore ricorsivo in TinyReC. Riflessioni sulla completezza computazioneale di TinyReC.
  • Ricorsione: funzione di Fibonacci. Efficienza e albero delle chiamate generato.

  • Esercizi consigliati: Dispensa D2 [sez. 4 ]
  • Esercizi consigliati: Dispensa D3 [sez. 1.3 ]

Lezione 11: lunedý 18 marzo 2019

Soluzioni delle equazioni di ricorrenza (3)

  • metodo del teorema principale (senza dimostrazione); esempi

Lezioni 12-13: mercoledý 20 marzo 2019 (Prof.ssa Calamoneri)

Soluzioni delle equazioni di ricorrenza (4)

Esercizi svolti in classe:

  • calcolare la soluzione delle seguenti equazioni di ricorrenza:
    • T(n)=T(n-1)+T(n-2) +Θ(1) con metodo iterativo
    • T(n)=T(n/3)+T(2/3 n)+Θ(n) con tutti i metodi tranne principale
    • T(n)=2T(n/2)+Θ(n**2) con tutti e quattro i metodi
    • T(n)=4T(n/2)+Θ(n) con tutti e quattro i metodi
  • dove per tutte si ha:
    • T(1)=Θ(1)

Venerdý 22 marzo 2019: Esercitazioni 7-8:

  • Iterazione e ricorsione: Fibonacci iterativo efficiente. Trasformazione sistematica di un ciclo in una funzione ricorsiva.
  • Dimostrazioni di correttezza per programmi ricorsivi. [ D3, sez. 2 ]
  • Sul tema, Soluzione Esonero 2014: il problema del massimo fattore primo [ S4 ]
  • Problemi con soluzione inerentemente ricorsiva: il problema della Torre di Hanoi [ D3, sez. 3 ]
  • Coefficienti binomiali.

  • Elucubrazioni: inutilitÓ dell' if else in Tiny C. Vera complessitÓ asintotica di Fibonacci iterativo.
  • Esercizi consigliati: Dispensa 3 [sez. 2.4 e 3.3 ]

Lezioni 14-15: lunedý 25 marzo 2019

Soluzioni delle equazioni di ricorrenza (5)

Esercizi assegnati agli studenti da svolgere in classe e poi svolti dal docente:

  • Calcolare la soluzione delle seguenti equazioni di ricorrenza col metodo del problema principale e col metodo iterativo, tenendo conto che per tutte il caso base Ŕ T(1)=Θ(1):
    • T(n)=2T(n/2)+Θ(n)
    • T(n)=3T(n/2)+Θ(n)
    • T(n)=2T(n/3)+Θ(n)

Il problema dell'ordinamento (1)

  • Algoritmi semplici: insertion sort: pseudocodice e costo computazionale nel caso migliore e peggiore.

Lezioni 16-17: mercoledý 27 marzo 2019

Il problema dell'ordinamento (2)

  • Algoritmi semplici: selection sort, bubble sort: pseudocodice e costo computazionale.
  • Teorema sulla limitazione inferiore per il costo computazionale di un algoritmo basato su confronti e scambi.
  • Algoritmi efficienti: merge sort, pseudocodice e costo computazionale

Esercizi assegnati:

  • Nell'algoritmo dell'insertion sort, la ricerca della posizione in cui inserire l'elemento corrente pu˛ essere effettuata tramite una ricerca binaria. Calcolare il costo computazionale dell'algoritmo cosý modificato.
  • 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 in modo che utilizzi ripetutamente questa funzione.
  • Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (prima versione).

venerdý 29 marzo 2019 - Esercitazioni 9-10

  • Introduzione ai vettori in C: definizione e allocazione [ D4, sez. 1 ].
  • Passaggio di parametri vettori. Vettori e puntatori [ D4, sez. 1.1 ].
  • Un primo programma sui vettori: stampa di un vettore, iterativa e ricorsiva [ D4, sez. 1.1 ].
  • Un esempio di programma con asserzioni logiche: minimo di un vettore [ D4, sez. 2.1 ].
  • Soluzione Esonero 2012: il Problema del baricentro [ S1 ].
  • Virtuosismi: Baricentro con un'unica scansione ricorsiva del vettore [ S1 ].

  • Esercizi consigliati: Dispensa 4 [sez. 1.3 e 2.6 ],
  • Lettura: due grandi classici: crivello di Eratostene [ D4, sez. 2.4 ] e coefficienti binomiali [ D4, sez. 2.5 ].

Lezioni 18-19: lunedý 1 aprile 2019

Il problema dell'ordinamento (3)

  • Algoritmi efficienti: quicksort, pseudocodice e costo computazionale (con dimostrazione per il caso medio)

Esercizio svolto in classe:

  • Si consideri una modifica del Merge Sort in cui il caso base si applica ad una porzione del vettore di lunghezza k, ordinata usando l'algoritmo Insertion Sort. Le porzioni cosý ordinate vengono combinate usando il meccanismo standard di fusione. Si determini il valore di k come funzione di n per cui l'algoritmo modificato ha lo stesso tempo di esecuzione asintotico del Merge Sort.

Esercizi assegnati:

  • Scrivere la funzione di fusione utilizzando la ricorsione
  • Determinare l'albero delle decisioni della funzione di fusione, quando i vettori da fondere sono [a1, a2, a3] e [b1, b2, b3] (con l'implicita ipotesi che a1<a2<a3 e b1<b2<b3)
  • Determinare il costo computazionale del Quicksort quando Ŕ applicato a un vettore contenente n elementi identici
  • 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.
  • Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (di nuovo: ma questa volta il costo computazionale dovrebbe essere un O(n log n))

Lezioni 20-21: mercoledý 3 aprile 2019

Il problema dell'ordinamento (4)

  • Algoritmi efficienti: heapsort (struttura dati heap; funzioni heapify e buildheap: pseudocodice e costo computazionale)

Esercizi assegnati:

  • Scrivere lo pseudocodice di una funzione che, dato un heap di n elementi al quale e' stata aggiunta nella posizione (n + 1) una nuova foglia con valore arbitrario, ripristini la proprieta' di heap nel nuovo albero di dimensione (n + 1). Valutare il costo computazionale.
  • Scrivere lo pseudocodice di una funzione che, dato un heap massimo di n elementi, ripristini la proprieta' di heap dopo che il valore di uno e uno solo dei nodi dello heap sia stato arbitrariamente modificato. Valutare il costo computazionale.

venerdý 5 aprile 2019 - Esercitazioni 11-12

  • Soluzione Esonero 2018: il problema del minimo intero libero [ S7 ];
  • Vettori variabili (allocati dentro le funzioni e di dimensioni dipendenti da una variabile);
  • Vettori dinamici (allocati con malloc o calloc ). Il tipo void *.
  • Esempio: il Crivello di Eratostene.

  • Esercizi consigliati: Dispensa 4 [sez. 1.3 e 2.6 ],

Lezioni 22-23: lunedý 8 aprile 2019

Il problema dell'ordinamento (4)

  • Algoritmi efficienti: heapsort (funzione heapsort: pseudocodice e costo computazionale)
  • Algoritmi di ordinamento lineari: counting sort (pseudocodice e costo computazionale); counting sort con dati satellite (descrizione generale dell'algoritmo); bucket sort (descrizione generale dell'algoritmo).

Esercizi assegnati:

  • Scrivere lo pseudocodice di Heapsort nel caso in cui, come struttura dati, si usi un heap minimo (cioŔ tale che A[i]>=A[parent(i)]), che mantiene il minimo nella radice.
  • Scrivere lo pseudocodice di una funzione che, dato un heap, ritorni l'elemento con chiave minima. Valutare il costo computazionale.
  • Dato un vettore di n elementi, verificare se contiene occorrenze ripetute dello stesso elemento (di nuovo: ma questa volta il costo computazionale dovrebbe essere un O(n))

Lezioni 24-25: mercoledý 10 aprile 2019 (Prof.ssa Calamoneri)

Esercitazione di preparazione al primo esonero (identica per entrambi i canali)

venerdý 12 aprile 2019 - Esercitazioni 13-14

  • Soluzione Esonero 2016: generazione delle combinazioni di n oggetti presi k a k [ S5 ]
  • Vettori bidimensionali: allocazione statica [ D5, sez. 2 ].
  • Allocazione di una matrice dinamica [ D5, sez. 3 ].
  • Virtuosismi: funzione mergeRecVPC: merge ricorsiva da Veri Programmatori C [ L2 ].

  • Esercizi consigliati: Di tutto un po', su vettori e ricorsione, dispensa D3 e D4.

Lunedý 15 aprile 2019

  • 14:00 - 17:00: Svolgimento della prova scritta relativa al primo esonero

Edit | Attach | Watch | Print version | History: r202 < r201 < r200 < r199 < r198 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r202 - 2019-04-15 - GiancarloBongiovanni





 
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-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback