Diario delle lezioni (Introduzione agli Algoritmi, secondo canale, A.A. 2014-2015)

Lunedì 23 Febbraio (2h) - Introduzione al corso. Administrivia. Cosa è un algoritmo (primo esempio: l'algoritmo per il calcolo del voto). Correttezza ed efficienza. Perché è importante progettare algoritmi efficienti: ordinare 1GB di dati eseguendo n² oppure n log n confronti, alcune considerazioni pratiche. Come si misura il tempo di esecuzione? Analisi del numero di linee di codice/numero di operazioni elementari eseguite da semplici programmi iterativi con cicli:

     Algoritmo 1 (int n)
      i=1
      while (i<=n) do i++
     

     Algoritmo 2 (int n) 
      i=0
      while (i<=n) do i=i+3
     

Giovedì 26 Febbraio (3h) - Da n a log n (cambiando un solo carattere!):

     Algoritmo 3 (int n) 
      i=1
      while (i<=n) do i=i+i
     

     Algoritmo 4 (int n) -> int 
      count=0
      i=1
      while (i<=n) do
         for j=1 to n
             count++
         i++
      return count
     

     Algoritmo 5 (int n) -> int 
      count=0
      i=1
      while (i<=n) do
         for j=1 to i
             count++
         i++
      return count
     

     Algoritmo 6 (int n) -> int 
     count=0
     x = n
     while (x>=1) do
         for j=1 to x
             count++
         x=x/2
     return count
     

Esercizi di riepilogo (A)

Esercizio A1. Quante volte viene stampato "Hello world" da ciascuno dei seguenti programmi?

i=1 if (n>5) i=n-5; while (i<=n) do print "Hello world" i=i+1	i=27 while (i<=n) do print "Hello world" i=i*3	for i=1 to n for j=1 to i for k=1 to j print "Hello world"	for i=1 to n for j=1 to i print "Hello world" for k=5 to 2i print "Hello world"	count=0 x = n while (x>=1) do for j=1 to n print "Hello world" x=x/2 return count
(A1.1)	(A1.2)	(A1.3)	(A1.4)	(A1.5)

Esercizio A2. Quanto sono grandi le istanze di input gestibili in 24h da un algoritmo con tempo di esecuzione n, n², 2ⁿ assumendo che una operazione elementare richieda un millisecondo? E se la CPU diventasse 10 volte più veloce? Quale dei tre algoritmi ne beneficerebbe di più?

Lunedì 2 Marzo (2h) - Introduzione alla notazione asintotica O, Omega, Theta. Limitazione stretta. Esempi di confronto tra funzioni applicando le definizioni e usando l'algebra elementare. Caratterizzazione dell'asintotica di un polinomio generico. Relazioni tra limite del rapporto e confronto tra funzioni.

Giovedì 5 Marzo (3h) - Introduzione all'analisi di algoritmi ricorsivi. Il problema dei conigli di Fibonacci: l'albero dei conigli, F_n=F_n-1+F_n-2, sezione aurea. Un algoritmo numerico non corretto. Algoritmo ricorsivo. Call stack, record di attivazione, albero delle chiamate ricorsive (call tree). Dalla call stack (visione istantanea dell'esecuzione) al call tree (visione storica). Impostazione equazione di ricorrenza. Relazione tra call tree ed equazione di ricorrenza.

Lunedì 9 Marzo (2h) - Dimostrazione delle relazioni tra limite del rapporto e relazione asintotica tra due funzioni. Criterio del rapporto. Classi di funzioni principali: logaritmica, polinomiale, esponenziale, fattoriale. Dimostrazione delle separazioni tra le classi.

Giovedì 12 Marzo (3h) - Analisi del tempo di esecuzione dell'algoritmo ricorsivo per il calcolo dei numeri di Fibonacci. Algoritmo iterativo.

Lunedì 16 Marzo (2h) - Analisi in funzione della dimensione dell'input. Caso peggiore, migliore e medio. Delimitazioni superiori e inferiori alle risorse di calcolo richieste da uno specifico algoritmo o per risolvere un certo problema. Bubblesort.

Giovedì 19 Marzo (3h) - Ordinamenti incrementali: selectionSort e insertionSort. Analisi correttezza e tempi di esecuzione. Esercizi presi da prove d'esame.

Lunedì 23 Marzo (2h) - Equazioni di ricorrenza

Giovedì 26 Marzo (3h) - Mergesort. Ricerca binaria. Equazioni di ricorrenza: analisi dell'albero della ricorsione e svolgimento della ricorrenza per iterazione. Problema 4.12 del libro di testo.

Esercizi di riepilogo (B)

Dal libro di testo: Problema 4.13. Esercizi 4.7 e 4.12

Da prove d'esame: 12 giugno 2012 (es. 2 e 3), 7 febbraio 2013 (es. 2), 24 aprile 2012 (es. 1, 2 e 3)

Lunedì 30 Marzo (2h) - Quicksort, partition in loco, analisi nel caso peggiore, intuizione nel caso medio. Ricorrenze: a) T(n) = T(n-1) + n; b) T(n) = T(n/4) + T(3n/4) + n.

Esercizi di riepilogo (C): preparazione all'esonero

Prove d'esame. 16 aprile 2013 (tutti), 26 aprile 2012 (testo 1, tutti gli esercizi), 28 aprile 2011 (tutti), 29 aprile 2010 (es. 1, 2 e 3).

Dal libro di testo. Problemi 1.1, 1.2, 1.3, 1.4, 2.2, 2.3, 2.4, 2.9, 2.10, 4.7.

Esercizio C1. Il Professor Bifolcacci sostiene di saper sfruttare la relazione di ricorrenza che definisce i numeri di Fibonacci per ottenere un algoritmo ricorsivo con tempo di esecuzione subesponenziale. In particolare, l'algoritmo del Professor Bifolcacci prima calcola ricorsivamente F_n-2 e F_n-3, e poi restituisce F_n=2F_n-2+F_n-3.

• Dimostrate che l'algoritmo è corretto (usate la definizione di numeri di Fibonacci).
• Disegnate l'albero della ricorsione per n=10.
• Impostate una relazione di ricorrenza per il tempo di esecuzione.
• [Diff] Dimostrate che il professore ha commesso un errore: il tempo di esecuzione è ancora esponenziale! E' sufficiente dare una minorazione al tempo di esecuzione, ovvero far vedere che il tempo di esecuzione T(n)≥g(n), dove g(n) è una opportuna funzione con crescita esponenziale.

Esercizio C2. Considerate il famoso gioco delle torri di Hanoi.

• Progettate un algoritmo ricorsivo che risolva il problema con n dischi e 3 torri.
• Impostate una relazione di ricorrenza per il numero di spostamenti di dischi eseguiti dall'algoritmo.
• Disegnate l'albero della ricorsione per n=5.
• [Diff] Analizzando l'albero, dimostrate che il numero di spostamenti effettuati è 2ⁿ-1. Suggerimento: dopo aver capito come etichettare ciascun nodo, calcolate il numero di nodi dell'albero sommando i numeri di nodi che si trovano su ciascun livello (dovete ottenere una serie geometrica).

Esercizio C3. Progettare ed analizzare un algoritmo iterativo ed un algoritmo ricorsivo per risolvere il seguente problema: dati due vettori A e B, entrambi di dimensione n, calcolare il prodotto scalare A x B. Il prodotto A x B è definito come la somma dei prodotti A[i] x B[i], dove A[i] è il valore dell'i-esima coordinata di A e B[i] è il valore dell'i-esima coordinata di B. Analizzare il tempo di esecuzione degli algoritmi proposti.

Esercizio C4. Progettare ed analizzare un algoritmo che, date due matrici quadrate A e B, entrambe di lato n, calcoli la matrice prodotto A x B. Qual è il tempo di esecuzione dell'algoritmo proposto in funzione di n? Generalizzare l'algoritmo assumendo che A abbia dimensione n x k e B abbia dimensione k x m. Calcolare inoltre il tempo di esecuzione T(n,k,m) come una funzione di n, k ed m.

Giovedì 2 Aprile (3h) - vacanze di Pasqua

Lunedì 6 Aprile (2h) - vacanze di Pasqua

Giovedì 9 Aprile (3h) - Esercizi in preparazione dell'esonero: es. 1 del 27/09/2011, es. 1.1 del 14/07/2009, es. 1.2 del 14/07/2009, es. 1 del 23 Aprile 2009, es. 1 del 20/09/2010, problema 2 16/04/2013, problema 2 26/04/2012, es. 2 del 29/04/2010

Lunedì 13 Aprile (2h) - interruzione didattica per svolgimento prove intermedie

Martedì 14 Aprile - prova intermedia, data da confermare.

Giovedì 16 Aprile (3h) - interruzione didattica per svolgimento prove intermedie

Lunedì 20 Aprile (2h) - Heap binari, proprietà, calcolo dell'altezza, cancellazione del massimo, procedure fixHeap, vettore posizionale.

Giovedì 23 Aprile (3h) - Costruzione di un heap binario: (1) tramite inserimenti ripetuti; (2) in tempo lineare tramite algoritmo heapify Teorema master: enunciato, esempi, intuizione sulla funzione n^log_ba.

Esercizi di riepilogo (D)

Dal libro di testo: esercizi 4.3, 4.4, 4.5. Problemi 4.4 e 4.5.

Da prove d'esame: es. 3 del 4 giugno 2013, es. 4 del 23 gennaio 2012, es. 5 del 12 giugno 2012, es. 3 del 20 giugno 2011 (parti a e b), es. 3 del 21 luglio 2010, es. 2 del 15 settembre 2009.

Lunedì 27 Aprile (2h) - Correzione esercizi prova intermedia.

Giovedì 30 Aprile (3h) - Lower bound al tempo di esecuzione di algoritmi di ordinamento basati su confronti. Counting sort: ordinare interi (piccoli) in tempo lineare.

Lunedì 4 Maggio (2h) - Correzione esercizi prova intermedia.

Giovedì 7 Maggio (3h) - Alberi: rappresentazioni collegate e indicizzate. Visite di alberi: generica, in ampiezza e in profondità.

Lunedì 11 Maggio (2h) - Visione e discussione esoneri. Introduzione ai dizionari: implementazioni banali.

Giovedì 14 Maggio (3h) - Alberi binari di ricerca. Alberi AVL. Fattore di bilanciamento. Alberi di Fibonacci. Dimostrazione altezza logaritmica.

Lunedì 18 Maggio (2h) -

Giovedì 21 Maggio (3h) - Rotazioni, classificazione e proprietà. Inserimento e cancellazione in alberi AVL.

Esercizi di riepilogo (E)

Dal libro di testo: esercizi 6.1, 6.2, 6.3, 6.4, 6.5, 6.6. Problemi 6.3, 6.4, 6.5, 6.6.

Da prove d'esame: . es. 3 e 4 del 23 gennaio 2014; es. 3, 4 e 5 del 4 giugno 2013; es. 4, 5 e 6 del 12 giugno 2012; es. 3 e 4 del 20 giugno 2011.

Lunedì 25 Maggio (2h) -

Giovedì 28 Maggio (3h) -