Diario delle lezioni (Introduzione agli Algoritmi, secondo canale, A.A. 2011-2012)

Lunedì 5 Marzo - Introduzione al corso. Administrivia. Come si misura il tempo di esecuzione? Analisi del numero di linee di codice 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
     

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

Giovedì 8 Marzo - Ancora analisi di programmi iterativi: cicli nidificati, serie aritmetica (con dimostrazione), cambiamento di variabile. Introduzione alla notazione asintotica O ed esempi.

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

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

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

Esercizi di riepilogo (A). 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"
(A1)	(A2)	(A3)	(A4)

(A5) Esercizio 2 della prova intermedia del 28 aprile 2011, traccia 1. Nel punto 2b, rimpiazzate Θ(n²) con n².

Lunedì 12 Marzo - Operazione dominante. Ancora su programmi iterativi con cicli nidificati:

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

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

Giovedì 15 Marzo - Analisi dell'algoritmo ricorsivo per il calcolo di F_n: calcolo del numero di linee di codice eseguite tramite analisi dell'albero della ricorsione, proprietà dell'albero della ricorsione (numero di foglie, numero di nodi interni), impostazione equazione di ricorrenza. Due algoritmi iterativi con tempo lineare, analisi della quantità di memoria richiesta. Soluzione degli esercizi A3 ed A5.

Esercizi di riepilogo (B).

Esercizio B1. Disegnate gli alberi delle chiamate ricorsive corrispondenti alle esecuzioni degli algoritmi algo1 e algo2 assumendo che n=10:

algo1(intero n) -> intero if (n<=7) return n; else sum=0; for i=1 to n-1 sum = sum + algo1(i) return sum	algo2(intero n) -> intero if (n<=2) return 5; else return 8+algo2(n-2)
(1)	(2)

Esercizio B2. Sia Fib un array di n interi, inizializzati tutti a 0. Progettate un algoritmo che memorizzi in Fib[i] l'i-esimo numero di Fibonacci F_i, per ogni i in [1,n]. L'algoritmo, a partire dal calcolo di F_n, deve operare ricorsivamente secondo la seguente strategia: a) se i=1 o i=2, pone Fib[i]=1 ed esce; b) se Fib[i-1]=0, calcola Fib[i-1] ricorsivamente; c) se Fib[i-2]=0, calcola Fib[i-2] ricorsivamente; d) memorizza in Fib[i] la somma Fib[i-1]+Fib[i-2] ed esce.

• Date lo pseudocodice dell'algoritmo
• Disegnate l'albero della ricorsione per il calcolo di F₆
• Analizzate il tempo di esecuzione dell'algoritmo
• Ripetete i punti precedenti assumendo che i passi b) e c) siano invertiti

Esercizio B3. 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
• 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 B4. 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 cascun nodo, calcolate il numero di nodi dell'albero sommando i numeri di nodi che si trovano su ciascun livello (dovete ottenere una serie geometrica).

Lunedì 19 Marzo - Notazione asintotica Ω e Θ. Dimostrazione della seguente proprietà: f(n)=Θ(g(n)) se e solo se f(n)=O(g(n)) e f(n)=Ω(g(n)). Un algoritmo logaritmico per il calcolo di F_n: numeri di Fibonacci e potenze di matrice. Esponenziazione di interi tramite il metodo dei quadrati ripetuti: algoritmo per il calcolo della n-esima potenza di un numero in tempo O(log n), analisi dell'albero della ricorsione, impostazione dell'equazione di ricorrenza e soluzione per iterazione.

Giovedì 22 Marzo - Ancora sulla notazione asintotica. Dualità di O e Ω. Dimostrazione della seguente proprietà: ogni polinomio di grado d≥0 il cui termine di grado massimo abbia coefficiente positivo è in Θ(n^d). Metodo analitico. Soluzione degli esercizi A4, B1(1), B2, e dell'esercizio 3 della prova intermedia del 29/4/2010.

Lunedì 26 Marzo - Esponenziazione di matrici tramite il metodo dei quadrati ripetuti: algoritmo per il calcolo di F_n in tempo O(log n). Come analizzare l'occupazione di memoria di algoritmi ricorsivi. Analisi del tempo di esecuzione in funzione della dimensione dell'input. Definizione di tempo di esecuzione nel caso migliore, nel caso peggiore e nel caso medio. Analisi dell'algoritmo di ricerca sequenziale nei tre casi. Analisi del tempo di esecuzione dell'algoritmo di ricerca binaria (implementazione iterativa) nel caso peggiore.

Esercizi di riepilogo (C).

Esercizio C1. Proporre 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 C2. Proporre 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?

Altri esercizi. Dal libro di testo:

• esercizi 2.1, 2.2, 2.3, 2.9
• problemi 2.2, 2.4, 2.9, 2.10

Da prove d'esame:

• esercizio 2 della prova intermedia del 29/4/2010
• esercizio 2 dell'appello del 24/6/2010

Giovedì 29 Marzo - Ricerca binaria con algoritmo ricorsivo con suddivisione bilanciata e sbilanciata del vettore. Serie geometrica. Soluzione degli esercizi B3 e B4.

Lunedì 2 Aprile - Come ordinare 1GB di dati... in meno di cento anni: il mergesort (implementazione ricorsiva ed analisi).

Esercizi di preparazione all'esonero (D). Buon lavoro, e buona Pasqua!

Esercizio D1. Nella implementazione del mergesort proposta sul libro di testo, rimpiazzate la scelta dell'indice m come segue: m=(2i+f-2)/3. Con tale scelta, l'array da ordinare viene partizionato in due sottoarray, il secondo dei quali è grande il doppio del primo. Disegnate l'albero della ricorsione ed impostate (senza risolverla, per ora) l'equazione di ricorrenza che descrive il numero di confronti eseguiti dall'algoritmo nel caso peggiore. Per semplificare i calcoli, potete assumere che la dimensione n dell'array da ordinare sia una potenza di 3.

Esercizio D2. Nella implementazione del mergesort proposta sul libro di testo, rimpiazzate la scelta dell'indice m come segue: m=min { (i+f)/2, i+3 }. Con tale scelta, se c'e' un numero di elementi sufficiente, l'array da ordinare viene partizionato in due sottoarray, il primo dei quali ha dimensione 4. Disegnate l'albero della ricorsione ed impostate l'equazione di ricorrenza che descrive il numero di confronti eseguiti dall'algoritmo nel caso peggiore. Risolvete per iterazione l'equazione di ricorrenza impostata. Per semplificare i calcoli, osservate che se l'input ha dimensione costante, il numero di passi eseguito dall'algoritmo è O(1).

Esercizio D3. Quanti confronti tra elementi sono eseguiti nel caso migliore dall'algoritmo merge per fondere due sequenze ordinate di lunghezza n1 e n2? Si può assumere senza perdita di generalità che n1<=n2. Qual è il tempo di esecuzione dell'algoritmo nel caso migliore?

Esercizi da prove d'esame. Esercizio 2 dell'appello del 17 giugno 2008; esercizio 2 degli appelli del 22 gennaio 2009; esercizi 1 e 2 degli appelli del 5 febbraio 2009 e 9 settembre 2008; esercizi 2 e 3 della prova intermedia del 27 novembre 2008; esercizio 2 della prova intermedia del 14 novembre 2007; esercizi 1, 3 e 4 della prova intermedia del 23 aprile 2009; tutti gli esercizi della prova intermedia del 29 aprile 2010 (nell'esercizio 4 omettere il punto 1); esercizi 1.1 e 1.2 dell'appello del 14 luglio 2009; esercizio 3 dell'appello del 15 settembre 2009; esercizio 2 dell'appello del 2 marzo 2010; esercizio 1 dell'appello del 21 luglio 2010; esercizi 2 e 3 dell'appello del 6 luglio 2009; esercizio 3 dell'appello del 10 settembre 2009.

Giovedì 5 Aprile - vacanze di Pasqua

Lunedì 9 Aprile - vacanze di Pasqua

Giovedì 12 Aprile - Bubble Sort e Insertion Sort. Soluzione problema 2.2 ed esercizio 2 della prova intermedia del 5/02/2009.

Lunedì 16 Aprile - Quicksort: partizionamento in loco, analisi nel caso peggiore, intuizione nel caso medio. Alberi della ricorsione bilanciati e non: analisi di equazioni di ricorrenza della forma T(n) = T(n/k) + T(n(k-1)/k) + Θ(n). Soluzione esercizi D1 e D2.

Giovedì 19 Aprile - Esercizi di preparazione all'esonero:

• Problema 2.9 del libro di testo
• Esercizio 1 prova intermedia del 23 aprile 2009
• Esercizio 3 prova intermedia del 23 aprile 2009
• Problema 3 appello del 6 luglio 2009
• Esercizio 1 appello del 20 settembre 2010

Lunedì 23 Aprile - interruzione didattica per prove intermedie

Giovedì 26 Aprile - prova intermedia

Lunedì 30 Aprile - didattica sospesa per il ponte del 1 maggio (come da delibera del Consiglio di Area Didattica)

Giovedì 3 Maggio - Selection sort, integer sort e correzione della prova intermedia

Lunedì 7 Maggio - Heap binari: definizioni, calcolo dell'altezza, procedura fixheap e cancellazione del massimo. Rappresentazione tramite vettore posizionale, heapsort, ordinamento in loco.

Giovedì 10 Maggio - Costruzione ricorsiva di un heap e soluzione dell'equazione di ricorrenza per sostituzione. Suggerimenti e tranelli nell'uso del metodo di sostituzione. Svolgimento del problema 4.3 del libro di testo: inserimento di un nuovo elemento in un heap. Svolgimento del problema 4.11 e primi esempi di delimitazioni inferiori (lower bound).

Esercizi di riepilogo (E).

Dal libro di testo:

• esercizi 4.3, 4.4, 4.5
• problemi 4.4, 4.5, 4.8, 4.10

Prova d'esame del 21 luglio 2010: esercizio 3

Prova d'esame del 24 giugno 2010: esercizio 3

Prova d'esame del 2 marzo 2010: esercizio 1

Prova d'esame del 15 settembre 2009: esercizi 1 e 2

Lunedì 14 Maggio - Alberi di decisione. Lower bound per il problema dell'ordinamento basato su confronti.

Giovedì 17 Maggio - Rappresentazioni di alberi mediante un strutture indicizzate (vettore padri e vettore posizionale) e mediante un strutture collegate (puntatoria figlio sinistro e destro, liste di figli, primo-figlio fratello successivo). Visite di alberi: visita generica, frangia, visita in ampiezza (con code), visita in profondità (con pile), implementazione ricorsiva della visita in profondità di alberi binari (preorder, inorder, postorder). Esercizi: problema 3.3 del libro di testo, variante del problema 3.7.

Lunedì 21 Maggio - Il tipo di dato astratto dizionario. Implementazioni banali mediante liste ed array ordinati e non. Alberi binari di ricerca: proprietà, operazioni search, insert e delete (con calcolo del predecessore). Analisi dei tempi di esecuzione in funzione dell'altezza h dell'albero.

Esercizi di riepilogo (F).

Dal libro di testo:

• esercizi 4.13, 4.14, 3.4, 3.5, 6.1, 6.10
• problemi 3.6, 3.7, 3.8, 6.1

Prova d'esame del 20 giugno 2011: esercizio 4

Prova d'esame del 15 novembre 2011: esercizi 2 e 3

Prova d'esame del 2 febbraio 2011: esercizio 3

Prova d'esame del 21 luglio 2010: esercizi 3 e 4

Prova d'esame del 2 marzo 2010: esercizio 3

Prova d'esame del 14 luglio 2009: esercizio 2.1

Prova d'esame del 23 giugno 2009: esercizio 2 della parte 1, esercizi 1 e 2 della parte 2

Giovedì 24 Maggio - Esercizi 3 e 4 della prova d'esame del 21 luglio 2010. Esercizio 3 della prova d'esame del 2 marzo 2010. Esercizio 2 parte 1 della prova d'esame del 23 giugno 2009. Esercizio 2 della prova d'esame del 15 novembre 2011.

Lunedì 28 Maggio - Alberi AVL. Bilanciamento in altezza. Dimostrazione del fatto che l'altezza è logaritmica tramite alberi di Fibonacci. Operazione di inserimento. Rotazione di base e classificazione delle rotazioni: SS, DD, SD e DS.

Giovedì 31 Maggio - Dimostrazione della seguente proprietà: nel caso di inserimenti, le rotazioni ribilanciano l'albero localmente ed una sola rotazione è sufficiente. Cancellazione. Sottoalbero fonte dello sbilanciamento non univoco. Rotazioni a cascata. Svolgimento di esercizi: problemi 6.4 e 6.5 del libro, ricerca del quarto minimo in un min-heap, creazione di un albero di ricerca a partire da tre vettori ordinati in tempo Θ(n).

Lunedì 4 Giugno - Esercizi di preparazione all'esame.

Giovedì 7 Giugno - Esercizi di preparazione all'esame.