Tags:
create new tag
view all tags

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 n2 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
     
Analisi del numero di linee di codice eseguite da semplici programmi iterativi con cicli nidificati:

     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
     
Variazioni sul tema. Serie aritmetica e serie geometrica di ragione 1/2 (con dimostrazione). Concetto di operazione dominante.

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, n2, 2n 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, Fn=Fn-1+Fn-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 Fn-2 e Fn-3, e poi restituisce Fn=2Fn-2+Fn-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 Ŕ 2n-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 nlogba.

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) -

Edit | Attach | Watch | Print version | History: r146 < r145 < r144 < r143 < r142 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r146 - 2015-05-22 - IreneFinocchi






 
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