Programma del corso di Introduzione agli Algoritmi (canale EO, A.A. 2008-2009)

Se non diversamente specificato, i riferimenti bibliografici sono relativi al libro di testo "Algoritmi e strutture dati", 2/ed. Demetrescu, Finocchi, Italiano, McGraw-Hill, 2008.

a) Introduzione

• Progettazione ed analisi di algoritmi
  • verifica di correttezza
  • analisi del tempo di esecuzione
  • analisi dell'occupazione di memoria
• Un esempio "giocattolo": il calcolo dei numeri di Fibonacci

Rif. Capitolo 1: tutto.

b) Metodologie di analisi

• Ordine di grandezza delle funzioni, la notazione asintotica O, Omega, Theta
• Algebra della notazione asintotica; analisi delle costanti additive e moltiplicative
• Delimitazioni inferiori e superiori alla complessità di un problema rispetto ad una data risorsa di calcolo
• Analisi nel caso peggiore e migliore
• Analisi di algoritmi ricorsivi:
  • equazioni di ricorrenza, albero della ricorsione
  • risoluzione di ricorrenze tramite analisi dell'albero della ricorsione
  • metodo dell'iterazione
  • metodo della sostituzione
  • il teorema fondamentale delle ricorrenze (teorema master): enunciato ed esempi.

Rif. Capitolo 2: paragrafi 2.2, 2.3, 2.4 (tranne caso medio), 2.5. Appendice: paragrafi 17.1, 17.2, 17.4

c) Algoritmi di ricerca e di ordinamento

• Ricerca sequenziale e binaria: analisi nel caso peggiore e migliore.
• Delimitazione inferiore al tempo di esecuzione di algoritmi di ordinamento basati su confronti: alberi di decisione
• Algoritmi di ordinamento quadratici (con analisi nel caso peggiore): insertionSort, selectionSort, bubbleSort
• Un algoritmo di ordinamento ottimo basato sulla tecnica del divide et impera (con analisi nel caso peggiore): mergeSort
• Un algoritmo di ordinamento ottimo basato sull'uso di strutture dati efficienti (con analisi nel caso peggiore): heapSort
  • la struttura dati heap
  • cancellazione del minimo e costruzione di un heap in tempo lineare
  • rappresentazione posizionale di alberi binari
  • ordinamento in loco
• Un algoritmo efficiente nel caso medio: quickSort (analisi nel caso peggiore, intuizione caso medio)
• Il concetto di stabilità nell'ordinamento.
• Ordinamento in tempo lineare: algoritmi intergerSort e bucketSort

Rif. Capitolo 2: paragrafo 2.4 (tranne caso medio). Capitolo 4: tutto tranne paragrafo 4.7. Appendice: paragrafo 17.4. Paragrafi 7.1, 7.2 e 7.4.1 del libro [CLRS01].

d) Dizionari

• Implementazioni banali: array ordinati e liste collegate
• Alberi binari di ricerca:
  • operazioni search, insert, delete
  • ricerca del massimo, del minimo, del predecessore e del successore
• Bilanciamento in altezza: alberi AVL
  • calcolo del fattore di bilanciamento
  • limitazione superiore all'altezza di un albero AVL
  • rotazioni semplici e doppie
  • mantenimento del bilanciamento durante inserimenti e cancellazioni * Tabelle ad accesso diretto * Tabelle hash
  • funzioni hash perfette
  • uniformità semplice
  • paradosso del compleanno e collisioni
  • liste di collisione
  • indirizzamento aperto: scansione lineare, quadratica e doppia

Rif. Capitolo 3: paragrafo 3.1. Capitolo 6: paragrafi 6.1 e 6.2. Capitolo 7: tutto.

e) Strutture dati elementari ed alberi

• Alberi: definizioni e proprietà fondamentali
• Rappresentazioni in memoria
  • strutture indicizzate
  • strutture collegate
• Algoritmo di visita generica di un albero
  • analisi del numero di iterazioni
  • tempo di esecuzione in funzione della rappresentazione usata
• Richiami a pile e code
• Visita in profondità (implementazione iterativa e ricorsiva)
  • visita preorder, simmetrica e postorder
  • esempi di applicazione delle visite
• Visita in ampiezza

Rif. Capitolo 3: tutto (tranne la tecnica del raddoppiamento-dimezzamento nel paragrafo 3.1).